Weisfeiler and Leman go Machine Learning: Expressivity and Generalization Abilities of GNNs

Abstract

Graph-structured data is ubiquitous across domains ranging from chemo- and bioinformatics to image and social network analysis. To develop successful machine learning models in these domains, we need techniques mapping the graph’s structure to a vectorial representation in a meaningful way – so-called graph embeddings. Starting from the 1960s in chemoinformatics, different research communities have worked under various guises, often leading to recurring ideas. Moreover, triggered by the resurgence of (deep) neural networks, there is an ongoing trend in the machine learning community to design permutation-invariant or -equivariant neural architectures capable of dealing with graph input, often denoted as neural graph networks (GNNs). However, although often successful in practice, GNN’s capabilities and limits are understood to a lesser extent. In this talk, we overview some results shedding some light on the limitations and capabilities of GNNs, focusing on expressive power and generalization ability by leveraging tools from graph theory and related areas.

Date
Mar 23, 2023 11:00 AM
Location
Mila - Coworking space (in front of the Agora)

Speaker: Christopher Morris (Website)

About the speaker: Christopher Morris studied computer science at TU Dortmund University, Germany. In 2019, interleaved with a short stint at Stanford University, he finished his Ph.D. studies at the same institution focusing on machine learning for graph and relational data. After that, he spent one year as a postdoctoral fellow at Polytechnique Montréal in the Department of Mathematical and Industrial Engineering, followed by another postdoc stay in the Computer Science Department of McGill University and as a member of Mila – Quebec AI Institute. He joined RWTH Aachen University, Germany, as a tenure-track assistant professor in the Computer Science department in June 2022.