Abstract

The expressive power of graph neural networks (GNNs) is typically understood through their correspondence with graph isomorphism tests such as the Weisfeiler–Leman (WL) hierarchy. While more expressive GNNs can distinguish a richer set of graphs, they are also observed to suffer from higher generalization error. This work provides a theoretical explanation for this trade-off by linking expressivity and generalization through the lens of coloring algorithms. Specifically, we show that the number of equivalence classes induced by WL colorings directly bounds the GNN’s Rademacher complexity – a key data-dependent measure of generalization. Our analysis reveals that greater expressivity leads to higher complexity and thus weaker generalization guarantees. Furthermore, we prove that the Rademacher complexity is stable under perturbations in the color counts across different samples, ensuring robustness to sampling variability across datasets. Importantly, our framework is not restricted to message-passing GNNs or 1-WL, but extends to arbitrary GNN architectures and expressivity measures that partition graphs into equivalence classes. These results unify the study of expressivity and generalization in GNNs, providing a principled understanding of why increasing expressive power often comes at the cost of generalization.

Short Bio

Caterina Graziani is a Research Associate in Artificial Intelligence at the University of Siena since February 2024. She earned both Bachelor’s and Master’s degrees in Mathematics and obtained her PhD in Artificial Intelligence at the University of Siena in 2024, under the supervision of Prof. Monica Bianchini, Prof. Moreno Falaschi, and Prof. Franco Scarselli. Her PhD thesis focused on the expressive power of GNNs beyond the Weisfeiler-Lehman test. She also spent four months at the Machine Learning Research Unit of the Technical University of Vienna under the supervision of Prof. Thomas Gartner. Her research interests lie in the mathematics of deep learning, with a focus on expressivity, approximation, and generalization in graph neural networks, as well as bioinformatics applications of neuro-symbolic methods.