# Generalization Bounds for Message Passing Networks on Mixture of Graphons

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 49 references that are in the map.
- First posted on arXiv 4 Apr 2024.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [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)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [Geometric deep learning: going beyond Euclidean data](https://mlsanity.com/paper/1611.08097/) (2016)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [DeepGCNs: Can GCNs Go as Deep as CNNs?](https://mlsanity.com/paper/1904.03751/) (2019)
- [Invariant and Equivariant Graph Networks](https://mlsanity.com/paper/1812.09902/) (2018)
- [DiffDock: Diffusion Steps, Twists, and Turns for Molecular Docking](https://mlsanity.com/paper/2210.01776/) (2022)
- [Revisiting Graph Neural Networks: All We Have is Low-Pass Filters](https://mlsanity.com/paper/1905.09550/) (2019)
- [Generalization and Representational Limits of Graph Neural Networks](https://mlsanity.com/paper/2002.06157/) (2020)
- [Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels](https://mlsanity.com/paper/1905.13192/) (2019)
- [Stability Properties of Graph Neural Networks](https://mlsanity.com/paper/1905.04497/) (2019)
- [Graphon Neural Networks and the Transferability of Graph Neural Networks](https://mlsanity.com/paper/2006.03548/) (2020)
- [Not too little, not too much: a theoretical analysis of graph (over)smoothing](https://mlsanity.com/paper/2205.12156/) (2022)
- [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)
- [Graph Neural Networks: Architectures, Stability and Transferability](https://mlsanity.com/paper/2008.01767/) (2020)
- [Convergence and Stability of Graph Convolutional Networks on Large Random Graphs](https://mlsanity.com/paper/2006.01868/) (2020)
- [Generalization Analysis of Message Passing Neural Networks on Large Random Graphs](https://mlsanity.com/paper/2202.00645/) (2022)
- [Transferability of Graph Neural Networks: an Extended Graphon Approach](https://mlsanity.com/paper/2109.10096/) (2021)
- [Transferability Properties of Graph Neural Networks](https://mlsanity.com/paper/2112.04629/) (2021)
- [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)
- [On the Stability of Graph Convolutional Neural Networks under Edge Rewiring](https://mlsanity.com/paper/2010.13747/) (2020)
- [Learning by Transference: Training Graph Neural Networks on Growing Graphs](https://mlsanity.com/paper/2106.03693/) (2021)
- [Limits, approximation and size transferability for GNNs on sparse graphs via graphops](https://mlsanity.com/paper/2306.04495/) (2023)

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

- [A Manifold Perspective on the Statistical Generalization of Graph Neural Networks](https://mlsanity.com/paper/2406.05225/) (2024)
- [Generalization of Geometric Graph Neural Networks with Lipschitz Loss Functions](https://mlsanity.com/paper/2409.05191/) (2024)
- [Graph neural networks and non-commuting operators](https://mlsanity.com/paper/2411.04265/) (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)
- [Learning from one graph: transductive learning guarantees via the geometry of small random worlds](https://mlsanity.com/paper/2509.06894/) (2025)
- [Understanding Generalization in Node and Link Prediction](https://mlsanity.com/paper/2507.00927/) (2025)
- [A Note on Graphon-Signal Analysis of Graph Neural Networks](https://mlsanity.com/paper/2508.18564/) (2025)
- [From Small to Large: Generalization Bounds for Transformers on Variable-Size Inputs](https://mlsanity.com/paper/2512.12805/) (2025)
- [Manifold limit for the training of shallow graph convolutional neural networks](https://mlsanity.com/paper/2601.06025/) (2026)
- [Size-Transferability of Graph Transformers with Convolutional Positional Encodings](https://mlsanity.com/paper/2602.15239/) (2026)
- [Topology-Aware PAC-Bayesian Generalization Analysis for Graph Neural Networks](https://mlsanity.com/paper/2604.10553/) (2026)
- [Graph Learning Should Move Beyond Restrictive Views of Spectral and Message-Passing GNNs](https://mlsanity.com/paper/2602.10031/) (2026)
- [When and How to Canonize: A Generalization Perspective](https://mlsanity.com/paper/2605.11008/) (2026)
- [When Do Graph Foundation Models Transfer? A Data-Centric Theory](https://mlsanity.com/paper/2605.29828/) (2026)
- [A Spectral Theory of Normalized Corrected GNN Propagation](https://mlsanity.com/paper/2606.23572/) (2026)
- [Dimension-Free Scaling Laws for Size Generalization: An Exponential Separation](https://mlsanity.com/paper/2610.19279/) (2026)

## Abstract (arXiv)

We study the generalization capabilities of Message Passing Neural Networks (MPNNs), a prevalent class of Graph Neural Networks (GNN). We derive generalization bounds specifically for MPNNs with normalized sum aggregation and mean aggregation. Our analysis is based on a data generation model incorporating a finite set of template graphons. Each graph within this framework is generated by sampling from one of the graphons with a certain degree of perturbation. In particular, we extend previous MPNN generalization results to a more realistic setting, which includes the following modifications: 1) we analyze simple random graphs with Bernoulli-distributed edges instead of weighted graphs; 2) we sample both graphs and graph signals from perturbed graphons instead of clean graphons; and 3) we analyze sparse graphs instead of dense graphs. In this more realistic and challenging scenario, we provide a generalization bound that decreases as the average number of nodes in the graphs increases. Our results imply that MPNNs with higher complexity than the size of the training set can still generalize effectively, as long as the graphs are sufficiently large.