mlsanityData to 7 Oct 2026

Generalization Bounds for Message Passing Networks on Mixture of Graphons

arXiv 2404.03473 ↗First posted 4 Apr 2024cs.LGcited by 16

Not on the map. Why?

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.

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

Builds on

33 of 49 references.

References · 33

  1. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  2. 2017Inductive Representation Learning on Large Graphscited by 6,284
  3. 2018How Powerful are Graph Neural Networks?cited by 4,355
  4. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  5. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,414
  6. 2018Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learningcited by 1,099
  7. 2016Geometric deep learning: going beyond Euclidean datacited by 1,042
  8. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  9. 2019DeepGCNs: Can GCNs Go as Deep as CNNs?cited by 527
  10. 2018Invariant and Equivariant Graph Networkscited by 339
  11. 2022DiffDock: Diffusion Steps, Twists, and Turns for Molecular Dockingcited by 307
  12. 2019Revisiting Graph Neural Networks: All We Have is Low-Pass Filterscited by 260
21 more
  1. 2020Generalization and Representational Limits of Graph Neural Networkscited by 217
  2. 2019Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernelscited by 160
  3. 2019Stability Properties of Graph Neural Networkscited by 125
  4. 2020Graphon Neural Networks and the Transferability of Graph Neural Networkscited by 117
  5. 2022Not too little, not too much: a theoretical analysis of graph (over)smoothingcited by 106
  6. 2019Transferability of Spectral Graph Convolutional Neural Networkscited by 90
  7. 2020A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networkscited by 84
  8. 2019Stability and Generalization of Graph Convolutional Neural Networkscited by 81
  9. 2020Graph Neural Networks: Architectures, Stability and Transferabilitycited by 79
  10. 2020Convergence and Stability of Graph Convolutional Networks on Large Random Graphscited by 75
  11. 2022Generalization Analysis of Message Passing Neural Networks on Large Random Graphscited by 58
  12. 2021Transferability of Graph Neural Networks: an Extended Graphon Approachcited by 51
  13. 2021Transferability Properties of Graph Neural Networkscited by 42
  14. 2023WL meet VCcited by 30
  15. 2023A graphon-signal analysis of graph neural networkscited by 29
  16. 2020On the Stability of Graph Convolutional Neural Networks under Edge Rewiringcited by 25
  17. 2021Learning by Transference: Training Graph Neural Networks on Growing Graphscited by 22
  18. 2023Limits, approximation and size transferability for GNNs on sparse graphs via graphopscited by 17
  19. 2024Weisfeiler-Leman at the margin: When more expressivity matterscited by 13
  20. 2023Convergence of Message Passing Graph Neural Networks with Generic Aggregation On Large Random Graphscited by 9
  21. 2022Convergence of Invariant Graph Networkscited by 8

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 4; 2025: 5; 2026: 7.

16 papers.

Sort:

  1. 2024A Manifold Perspective on the Statistical Generalization of Graph Neural Networkscited by 16
  2. 2024Generalization of Geometric Graph Neural Networks with Lipschitz Loss Functionscited by 6
  3. 2024Graph neural networks and non-commuting operatorscited by 5
  4. 2024Generalization of Graph Neural Networks is Robust to Model Mismatchcited by 4
  5. 2025Graph Representational Learning: When Does More Expressivity Hurt Generalization?cited by 4
  6. 2025Learning from one graph: transductive learning guarantees via the geometry of small random worldscited by 3
  7. 2025Understanding Generalization in Node and Link Predictioncited by 2
  8. 2025A Note on Graphon-Signal Analysis of Graph Neural Networkscited by 1
  9. 2025From Small to Large: Generalization Bounds for Transformers on Variable-Size Inputscited by 1
  10. 2026Manifold limit for the training of shallow graph convolutional neural networkscited by 1
  11. 2026Topology-Aware PAC-Bayesian Generalization Analysis for Graph Neural Networkscited by 1
  12. 2026Graph Learning Should Move Beyond Restrictive Views of Spectral and Message-Passing GNNscited by 0
4 more
  1. 2026Size Transferability of Graph Transformers with Convolutional Positional Encodingscited by 0
  2. 2026When and How to Canonize: A Generalization Perspectivecited by 0
  3. 2026When Do Graph Foundation Models Transfer? A Data-Centric Theorycited by 0
  4. 2026A Spectral Theory of Normalized Corrected GNN Propagationcited by 0