Expressivity and Generalisation of Graph Neural Networks

par Johannes Lutzeyer (Ecole Polytechnique)

lundi 16 nov. 2026, 13:30 → 14:30 Europe/Paris

Salle Fokko du Cloux, bâtiment Braconnier (La Doua)

Graph Neural Networks (GNNs) have celebrated many academic and industrial successes in the past years; providing a rich ground for theoretical analysis and achieving state-of-the-art results in several learning tasks. A major line of research in this domain has focused on improving the expressivity of GNNs measured by their ability to distinguish non-isomorphic graphs, which has not always led to higher performing models in practice. In this talk, I will give an accessible introduction to GNNs and their expressivity. I will then share recent work (ICLR'26) in which we relate the generalisation and expressivity of GNNs. In particular, we prove a PAC-Bayes bound on the generalisation error of expressive GNNs, which allows us to show that more expressive GNNs may generalise worse unless their increased complexity is balanced by a sufficiently large training set or reduced distance between training and test graphs. To conclude, I will aim to provide a quick overview of related work we have been doing in recent years on the generalisation and robustness of GNNs.