Expressiveness and Generalisation in Graph Neural Networks

The expressive power of graph neural networks (GNNs) has been widely analysed through their connection to the 1-dimensional Weisfeiler–Leman (1-WL) algorithm, a key tool for addressing the graph isomorphism problem. While this link has deepened our understanding of how GNNs represent complex structures, it provides limited insight into their generalisation—specifically, their ability to accurately predict on unseen data. In this talk, we delve into the relationship between GNNs' expressive power and their generalisation capabilities, offering a unified perspective that bridges these two critical aspects of GNN performance.