# Survey on Generalization Theory for Graph Neural Networks

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Mar 2025.

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

- [From Features to Structure: Task-Aware Graph Construction for Relational and Tabular Learning with GNNs](https://mlsanity.com/paper/2506.02243/) (2025)
- [Backward Oversmoothing: why is it hard to train deep Graph Neural Networks?](https://mlsanity.com/paper/2505.16736/) (2025)
- [Bridging Input Feature Spaces Towards Graph Foundation Models](https://mlsanity.com/paper/2605.04834/) (2026)
- [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)
- [Estimating Heterogeneous Causal Effect on Networks via Orthogonal Learning](https://mlsanity.com/paper/2509.18484/) (2025)
- [Topology-Aware PAC-Bayesian Generalization Analysis for Graph Neural Networks](https://mlsanity.com/paper/2604.10553/) (2026)
- [PAC-Bayesian Generalization Bounds for Graph Convolutional Networks on Inductive Node Classification](https://mlsanity.com/paper/2509.06600/) (2025)
- [Graph Learning Should Move Beyond Restrictive Views of Spectral and Message-Passing GNNs](https://mlsanity.com/paper/2602.10031/) (2026)
- [Learning to Approximate Uniform Facility Location via Graph Neural Networks](https://mlsanity.com/paper/2602.13155/) (2026)
- [Generalization Bounds for Spectral GNNs via Fourier Domain Analysis](https://mlsanity.com/paper/2604.00918/) (2026)
- [Probabilistic Graphical Model using Graph Neural Networks for Bayesian Inversion of Discrete Structural Component States](https://mlsanity.com/paper/2604.23514/) (2026)
- [When and How to Canonize: A Generalization Perspective](https://mlsanity.com/paper/2605.11008/) (2026)
- [Different Statistical Perspectives for Understanding Generalisation in Graph Neural Networks](https://mlsanity.com/paper/2605.25452/) (2026)
- [Unifying Graph Neural Networks Through a Common Layer Equation](https://mlsanity.com/paper/2608.16097/) (2026)
- [Dimension-Free Scaling Laws for Size Generalization: An Exponential Separation](https://mlsanity.com/paper/2610.19279/) (2026)

## Abstract (arXiv)

Message-passing graph neural networks (MPNNs) have emerged as the leading approach for machine learning on graphs, attracting significant attention in recent years. While a large set of works explored the expressivity of MPNNs, i.e., their ability to separate graphs and approximate functions over them, comparatively less attention has been directed toward investigating their generalization abilities, i.e., making meaningful predictions beyond the training data. Here, we systematically review the existing literature on the generalization abilities of MPNNs. We analyze the strengths and limitations of various studies in these domains, providing insights into their methodologies and findings. Furthermore, we identify potential avenues for future research, aiming to deepen our understanding of the generalization abilities of MPNNs.