# Towards Bridging Generalization and Expressivity of Graph Neural Networks

arXiv: https://arxiv.org/abs/2410.10051 · HTML: https://mlsanity.com/paper/2410.10051/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 41 of its 56 references that are in the map.
- First posted on arXiv 14 Oct 2024.

## Builds on (most cited first, 30 of 41)

- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [MoleculeNet: A Benchmark for Molecular Machine Learning](https://mlsanity.com/paper/1703.00564/) (2017)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting](https://mlsanity.com/paper/2006.09252/) (2020)
- [Modeling polypharmacy side effects with graph convolutional networks](https://mlsanity.com/paper/1802.00543/) (2018)
- [Generalization and Representational Limits of Graph Neural Networks](https://mlsanity.com/paper/2002.06157/) (2020)
- [From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awareness](https://mlsanity.com/paper/2110.03753/) (2021)
- [Equivariant Subgraph Aggregation Networks](https://mlsanity.com/paper/2110.02910/) (2021)
- [On the Properties of the Softmax Function with Application in Game Theory and Reinforcement Learning](https://mlsanity.com/paper/1704.00805/) (2017)
- [Nested Graph Neural Networks](https://mlsanity.com/paper/2110.13197/) (2021)
- [Large Margin Deep Networks for Classification](https://mlsanity.com/paper/1803.05598/) (2018)
- [A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networks](https://mlsanity.com/paper/2012.07690/) (2020)
- [Stability and Generalization of Graph Convolutional Neural Networks](https://mlsanity.com/paper/1905.01004/) (2019)
- [Expressiveness and Approximation Properties of Graph Neural Networks](https://mlsanity.com/paper/2204.04661/) (2022)
- [Generalization Analysis of Message Passing Neural Networks on Large Random Graphs](https://mlsanity.com/paper/2202.00645/) (2022)
- [On Provable Benefits of Depth in Training Graph Convolutional Networks](https://mlsanity.com/paper/2110.15174/) (2021)
- [Graph Neural Networks with Local Graph Parameters](https://mlsanity.com/paper/2106.06707/) (2021)
- [Learning Theory Can (Sometimes) Explain Generalisation in Graph Neural Networks](https://mlsanity.com/paper/2112.03968/) (2021)
- [Towards Understanding the Generalization of Graph Neural Networks](https://mlsanity.com/paper/2305.08048/) (2023)
- [Generalization in Graph Neural Networks: Improved PAC-Bayesian Bounds on Graph Diffusion](https://mlsanity.com/paper/2302.04451/) (2023)
- [Autobahn: Automorphism-based Graph Neural Nets](https://mlsanity.com/paper/2103.01710/) (2021)
- [Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness](https://mlsanity.com/paper/2401.08514/) (2024)
- [Optimization and Generalization Analysis of Transduction through Gradient Boosting and Application to Multi-scale Graph Neural Networks](https://mlsanity.com/paper/2006.08550/) (2020)
- [WL meet VC](https://mlsanity.com/paper/2301.11039/) (2023)
- [A graphon-signal analysis of graph neural networks](https://mlsanity.com/paper/2305.15987/) (2023)
- [Lov'asz Meets Weisfeiler and Leman](https://mlsanity.com/paper/1802.08876/) (2018)

## Built on by (most cited first, 12 of 12)

- [Graph Representational Learning: When Does More Expressivity Hurt Generalization?](https://mlsanity.com/paper/2505.11298/) (2025)
- [Towards Graph Foundation Models: A Study on the Generalization of Positional and Structural Encodings](https://mlsanity.com/paper/2412.07407/) (2024)
- [Understanding Generalization in Node and Link Prediction](https://mlsanity.com/paper/2507.00927/) (2025)
- [On the Rademacher Complexity of Graph Neural Networks: Unifying Expressivity and Geometry](https://mlsanity.com/paper/2510.10101/) (2025)
- [Memorization in Graph Neural Networks](https://mlsanity.com/paper/2508.19352/) (2025)
- [Theoretical Learning Performance of Graph Neural Networks: The Impact of Jumping Connections and Layer-wise Sparsification](https://mlsanity.com/paper/2507.05533/) (2025)
- [Exact Generalisation Error Exposes Benchmarks Skew Graph Neural Networks Success (or Failure)](https://mlsanity.com/paper/2509.10337/) (2025)
- [Message Passing on the Edge: Towards Scalable and Expressive GNNs](https://mlsanity.com/paper/2510.13615/) (2025)
- [Transductive Generalization via Optimal Transport and Its Application to Graph Node Classification](https://mlsanity.com/paper/2603.09257/) (2026)
- [MLGIB: Multi-Label Graph Information Bottleneck for Expressive and Robust Message Passing](https://mlsanity.com/paper/2605.13126/) (2026)
- [AutoGrable: What Is a Good Graph for a Table?](https://mlsanity.com/paper/2608.11431/) (2026)
- [Finite-Time Node Separation in Recurrent Graph Neural Networks with Persistent Gaussian Perturbations](https://mlsanity.com/paper/2609.13920/) (2026)

## Abstract (arXiv)

Expressivity and generalization are two critical aspects of graph neural networks (GNNs). While significant progress has been made in studying the expressivity of GNNs, much less is known about their generalization capabilities, particularly when dealing with the inherent complexity of graph-structured data. In this work, we address the intricate relationship between expressivity and generalization in GNNs. Theoretical studies conjecture a trade-off between the two: highly expressive models risk overfitting, while those focused on generalization may sacrifice expressivity. However, empirical evidence often contradicts this assumption, with expressive GNNs frequently demonstrating strong generalization. We explore this contradiction by introducing a novel framework that connects GNN generalization to the variance in graph structures they can capture. This leads us to propose a k-variance margin-based generalization bound that characterizes the structural properties of graph embeddings in terms of their upper-bounded expressive power. Our analysis does not rely on specific GNN architectures, making it broadly applicable across GNN models. We further uncover a trade-off between intra-class concentration and inter-class separation, both of which are crucial for effective generalization. Through case studies and experiments on real-world datasets, we demonstrate that our theoretical findings align with empirical results, offering a deeper understanding of how expressivity can enhance GNN generalization.