# A Manifold Perspective on the Statistical Generalization of Graph Neural Networks

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 43 of its 81 references that are in the map.
- First posted on arXiv 7 Jun 2024.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Distributed Representations of Words and Phrases and their Compositionality](https://mlsanity.com/paper/1310.4546/) (2013)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [Geometric deep learning: going beyond Euclidean data](https://mlsanity.com/paper/1611.08097/) (2016)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [Geometric deep learning on graphs and manifolds using mixture model CNNs](https://mlsanity.com/paper/1611.08402/) (2016)
- [A critical look at the evaluation of GNNs under heterophily: Are we really making progress?](https://mlsanity.com/paper/2302.11640/) (2023)
- [Point-GNN: Graph Neural Network for 3D Object Detection in a Point Cloud](https://mlsanity.com/paper/2003.01251/) (2020)
- [Generalization and Representational Limits of Graph Neural Networks](https://mlsanity.com/paper/2002.06157/) (2020)
- [Generalization in Deep Learning](https://mlsanity.com/paper/1710.05468/) (2017)
- [From Local Structures to Size Generalization in Graph Neural Networks](https://mlsanity.com/paper/2010.08853/) (2020)
- [Graphon Neural Networks and the Transferability of Graph Neural Networks](https://mlsanity.com/paper/2006.03548/) (2020)
- [MultiScale MeshGraphNets](https://mlsanity.com/paper/2210.00612/) (2022)
- [Transfer Learning of Graph Neural Networks with Ego-graph Information Maximization](https://mlsanity.com/paper/2009.05204/) (2020)
- [Transferability of Spectral Graph Convolutional Neural Networks](https://mlsanity.com/paper/1907.12972/) (2019)
- [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)
- [Convergence and Stability of Graph Convolutional Networks on Large Random Graphs](https://mlsanity.com/paper/2006.01868/) (2020)
- [Error estimates for spectral convergence of the graph Laplacian on random geometric graphs towards the Laplace--Beltrami operator](https://mlsanity.com/paper/1801.10108/) (2018)
- [Subgroup Generalization and Fairness of Graph Neural Networks](https://mlsanity.com/paper/2106.15535/) (2021)
- [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)
- [Transferability of Graph Neural Networks: an Extended Graphon Approach](https://mlsanity.com/paper/2109.10096/) (2021)
- [Learning Theory Can (Sometimes) Explain Generalisation in Graph Neural Networks](https://mlsanity.com/paper/2112.03968/) (2021)
- [Transferability Properties of Graph Neural Networks](https://mlsanity.com/paper/2112.04629/) (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)

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

- [Generalization of Geometric Graph Neural Networks with Lipschitz Loss Functions](https://mlsanity.com/paper/2409.05191/) (2024)
- [Graph Representational Learning: When Does More Expressivity Hurt Generalization?](https://mlsanity.com/paper/2505.11298/) (2025)
- [Generalization of Graph Neural Networks is Robust to Model Mismatch](https://mlsanity.com/paper/2408.13878/) (2024)
- [Mixture of Scope Experts at Test: Generalizing Deeper Graph Neural Networks with Shallow Variants](https://mlsanity.com/paper/2409.06998/) (2024)
- [Improved Image Classification with Manifold Neural Networks](https://mlsanity.com/paper/2409.13063/) (2024)
- [Memorization in Graph Neural Networks](https://mlsanity.com/paper/2508.19352/) (2025)
- [Beyond Accuracy: A Geometric Stability Analysis of Large Language Models in Chess Evaluation](https://mlsanity.com/paper/2512.15033/) (2025)
- [Size-Transferability of Graph Transformers with Convolutional Positional Encodings](https://mlsanity.com/paper/2602.15239/) (2026)
- [Finsler Geometry, Graph Neural Networks, and You](https://mlsanity.com/paper/2606.17185/) (2026)
- [Distributed Training of Large Graph Neural Networks with Variable Communication Rates](https://mlsanity.com/paper/2406.17611/) (2024)
- [Self-Reinforced Graph Contrastive Learning](https://mlsanity.com/paper/2505.13650/) (2025)
- [Graph Semi-Supervised Learning for Point Classification on Data Manifolds](https://mlsanity.com/paper/2506.12197/) (2025)
- [Unrolling Dynamic Programming via Graph Filters](https://mlsanity.com/paper/2507.21705/) (2025)
- [Graph Learning Should Move Beyond Restrictive Views of Spectral and Message-Passing GNNs](https://mlsanity.com/paper/2602.10031/) (2026)
- [Local-Global Geometric Insights for Graph Neural Networks via Entropic Curvature](https://mlsanity.com/paper/2607.22381/) (2026)
- [Graph Memory: Spectral Associative Memory via Dirichlet Energy](https://mlsanity.com/paper/2609.32365/) (2026)
- [Dimension-Free Scaling Laws for Size Generalization: An Exponential Separation](https://mlsanity.com/paper/2610.19279/) (2026)

## Abstract (arXiv)

Graph Neural Networks (GNNs) extend convolutional neural networks to operate on graphs. Despite their impressive performances in various graph learning tasks, the theoretical understanding of their generalization capability is still lacking. Previous GNN generalization bounds ignore the underlying graph structures, often leading to bounds that increase with the number of nodes -- a behavior contrary to the one experienced in practice. In this paper, we take a manifold perspective to establish the statistical generalization theory of GNNs on graphs sampled from a manifold in the spectral domain. As demonstrated empirically, we prove that the generalization bounds of GNNs decrease linearly with the size of the graphs in the logarithmic scale, and increase linearly with the spectral continuity constants of the filter functions. Notably, our theory explains both node-level and graph-level tasks. Our result has two implications: i) guaranteeing the generalization of GNNs to unseen data over manifolds; ii) providing insights into the practical design of GNNs, i.e., restrictions on the discriminability of GNNs are necessary to obtain a better generalization performance. We demonstrate our generalization bounds of GNNs using synthetic and multiple real-world datasets.