Theoretical foundations of Graph Neural Networks: from expressivity to generalization

Maskey, Sohir (2026): Theoretical foundations of Graph Neural Networks: from expressivity to generalization. Dissertation, LMU München: Faculty of Mathematics, Computer Science and Statistics

Abstract

Graph Neural Networks (GNNs) have become indispensable tools for learning from structured data, achieving strong empirical performance across domains such as chemistry and social network analysis. However, their theoretical foundations remain incomplete. Two key challenges persist: (1) the expressive power of GNNs is fundamentally limited—Message Passing Neural Networks (MPNNs) are provably bounded by the 1-Weisfeiler-Leman (1-WL) test (K. Xu et al., 2019), and (2) their generalization behavior is still poorly understood. This dissertation presents several contributions that improve our understanding of these challenges in GNNs. We begin by addressing the expressivity bottlenecks of standard GNNs. At the graph level, we introduce the r-loopy Weisfeiler–Leman (r-lWL) test—a scalable extension of 1-WL augmented with path embeddings (Paolino et al., 2024b). This extension improves expressivity without the computational overhead of higher-order WL tests. We prove that r-lWL is strictly more powerful than 1-WL and can distinguish graphs that differ in the number of generalized cycle (or "cactus") patterns they contain. As a corollary, r-lWL is not less powerful than other higher-order WL tests. We empirically validate these claims on tasks where cycle detection is essential. As another way to increase GNN expressivity, we propose a family of positional encodings based on p-norm dissimilarities between node embeddings (p-PEs) (Maskey et al., 2022b), which generalize the popular Laplacian Positional Encoding. We prove that MPNNs augmented with p-PEs are strictly more expressive than 1-WL. A key expressivity limitation is oversmoothing, where node embeddings become indistinguishable as the network depth increases. To address this, we develop a GNN architecture based on fractional graph Laplacians embedded into neural ODEs (Maskey et al., 2023b). This approach enables deeper message passing while provably mitigating oversmoothing and is effective on non-homophilic graphs. Beyond expressivity, we offer new insights into generalization in GNNs. While often implicit in practice, a central assumption in learning is that labels correlate with the input data. Our first line of work formalizes data-label correlation using graphons, i.e., limit objects of convergent graph sequences. We show that spectral GNNs with continuous filters exhibit asymptotic transferability (Maskey et al., 2023a): if input graphs converge to the same graphon, their learned predictions converge as well. We then extend this to a probabilistic setting by treating graphs as random samples from graphon-induced distributions and derive generalization bounds for MPNNs (Maskey et al., 2022a, 2025). These bounds show that generalization improves with both the number and the size of the training graphs. In (Maskey et al., 2026), we model structure-label correlation using pseudometrics such as the Tree Mover’s Distance (TMD) (Chuang et al., 2022). We generalize this notion by introducing generalized TMDs—task-adaptive pseudometrics that capture varying levels of GNN expressivity. This framework enables PAC-Bayesian generalization bounds that explicitly depend on the structural similarity between training and test graphs. Crucially, we show that generalization remains stable—even for highly expressive GNNs—when the model’s expressivity is aligned with the structural complexity of the task. Empirical results support this finding: both underpowered and overly expressive models perform poorly. Together, these contributions deepen the theoretical understanding of GNNs while providing concrete tools for building more expressive and scalable GNNs.

• Item Type: Theses (Dissertation, LMU Munich)
• Subjects: 500 Natural sciences and mathematics; 500 Natural sciences and mathematics > 510 Mathematics
• Faculties: Faculty of Mathematics, Computer Science and Statistics
• Language: English
• Date of oral examination: 17. April 2026
• 1. Referee: Kutyniok, Gitta
• Signature of the printed copy: 0001/UMC 32068