mlsanityData to 7 Oct 2026

Generalization Analysis of Message Passing Neural Networks on Large Random Graphs

arXiv 2202.00645 ↗First posted 1 Feb 2022cs.LG cs.AI cs.NAcited by 58

Not on the map. Why?

Abstract (arXiv)

Message passing neural networks (MPNN) have seen a steep rise in popularity since their introduction as generalizations of convolutional neural networks to graph-structured data, and are now considered state-of-the-art tools for solving a large variety of graph-focused problems. We study the generalization error of MPNNs in graph classification and regression. We assume that graphs of different classes are sampled from different random graph models. We show that, when training a MPNN on a dataset sampled from such a distribution, the generalization gap increases in the complexity of the MPNN, and decreases, not only with respect to the number of training samples, but also with the average number of nodes in the graphs. This shows how a MPNN with high complexity can generalize from a small dataset of graphs, as long as the graphs are large. The generalization bound is derived from a uniform convergence result, that shows that any MPNN, applied on a graph, approximates the MPNN applied on the geometric model that the graph discretizes.

Key facts. Cited by 58 papers in the map (data through 7 Oct 2026). Builds on 26 of its 58 references that are in the map. First posted on arXiv 1 Feb 2022.

Builds on

26 of 58 references.

References · 26

  1. 2017Inductive Representation Learning on Large Graphscited by 6,284
  2. 2018How Powerful are Graph Neural Networks?cited by 4,355
  3. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,414
  4. 2016Variational Graph Auto-Encoderscited by 1,373
  5. 2018Graph Convolutional Neural Networks for Web-Scale Recommender Systemscited by 1,133
  6. 2016Geometric deep learning: going beyond Euclidean datacited by 1,042
  7. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  8. 2019Graph Neural Networks for Social Recommendationcited by 711
  9. 2018Pixel2Mesh: Generating 3D Mesh Models from Single RGB Imagescited by 649
  10. 2020Generalization and Representational Limits of Graph Neural Networkscited by 217
  11. 2016Discriminative Embeddings of Latent Variable Models for Structured Datacited by 130
  12. 2019Stability Properties of Graph Neural Networkscited by 125
14 more
  1. 2020From Local Structures to Size Generalization in Graph Neural Networkscited by 119
  2. 2019Fake News Detection on Social Media using Geometric Deep Learningcited by 115
  3. 2018Billion-scale Commodity Embedding for E-commerce Recommendation in Alibabacited by 105
  4. 2019Transferability of Spectral Graph Convolutional Neural Networkscited by 90
  5. 2020A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networkscited by 84
  6. 2019Stability and Generalization of Graph Convolutional Neural Networkscited by 81
  7. 2020Graph Neural Networks: Architectures, Stability and Transferabilitycited by 79
  8. 2020Convergence and Stability of Graph Convolutional Networks on Large Random Graphscited by 75
  9. 2021Transferability of Graph Neural Networks: an Extended Graphon Approachcited by 51
  10. 2021Transferability Properties of Graph Neural Networkscited by 42
  11. 2021Interpretable Stability Bounds for Spectral Graph Filterscited by 28
  12. 2019On the Transferability of Spectral Graph Filterscited by 27
  13. 2021Learning by Transference: Training Graph Neural Networks on Growing Graphscited by 22
  14. 2020Graph and graphon neural network stabilitycited by 15

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 8; 2023: 15; 2024: 21; 2025: 8; 2026: 6.

58 papers.

Sort:

  1. 2022Out-Of-Distribution Generalization on Graphs: A Surveycited by 97
  2. 2022OOD Link Prediction Generalization Capabilities of Message-Passing GNNs in Larger Test Graphscited by 38
  3. 2024A Review of Graph Neural Networks in Epidemic Modelingcited by 31
  4. 2023WL meet VCcited by 30
  5. 2022Towards Better Out-of-Distribution Generalization of Neural Algorithmic Reasoning Taskscited by 29
  6. 2023A graphon-signal analysis of graph neural networkscited by 29
  7. 2023Joint Learning of Label and Environment Causal Independence for Graph Out-of-Distribution Generalizationcited by 29
  8. 2023Fine-grained Expressivity of Graph Neural Networkscited by 25
  9. 2022Graph Attention Retrospectivecited by 24
  10. 2022Geometric Scattering on Measure Spacescited by 17
  11. 2023Limits, approximation and size transferability for GNNs on sparse graphs via graphopscited by 17
  12. 2023Graph Neural Tangent Kernel: Convergence on Large Graphscited by 16
38 more
  1. 2023Approximately Equivariant Graph Networkscited by 16
  2. 2024Generalization Bounds for Message Passing Networks on Mixture of Graphonscited by 16
  3. 2024A Manifold Perspective on the Statistical Generalization of Graph Neural Networkscited by 16
  4. 2024What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encodingcited by 14
  5. 2023Optimality of Message-Passing Architectures for Sparse Graphscited by 13
  6. 2024Weisfeiler-Leman at the margin: When more expressivity matterscited by 13
  7. 2022FakeEdge: Alleviate Dataset Shift in Link Predictioncited by 12
  8. 2024Towards Bridging Generalization and Expressivity of Graph Neural Networkscited by 12
  9. 2023What functions can Graph Neural Networks compute on random graphs? The role of Positional Encodingcited by 11
  10. 2023Equivariant Neural Operator Learning with Graphon Convolutioncited by 10
  11. 2023Convergence of Message Passing Graph Neural Networks with Generic Aggregation On Large Random Graphscited by 9
  12. 2024Almost Surely Asymptotically Constant Graph Neural Networkscited by 7
  13. 2024Generalization of Geometric Graph Neural Networks with Lipschitz Loss Functionscited by 6
  14. 2022On Classification Thresholds for Graph Attention with Edge Featurescited by 5
  15. 2024Future Directions in the Theory of Graph Machine Learningcited by 5
  16. 2024Graph neural networks and non-commuting operatorscited by 5
  17. 2022Towards Better Generalization with Flexible Representation of Multi-Module Graph Neural Networkscited by 4
  18. 2024Generalization Error of Graph Neural Networks in the Mean-field Regimecited by 4
  19. 2024Generalization of Graph Neural Networks is Robust to Model Mismatchcited by 4
  20. 2025Graph Representational Learning: When Does More Expressivity Hurt Generalization?cited by 4
  21. 2023Framelet Message Passingcited by 3
  22. 2023Generalization Limits of Graph Neural Networks in Identity Effects Learningcited by 3
  23. 2024On the Generalization Capability of Temporal Graph Learning Algorithms: Theoretical Insights and a Simpler Methodcited by 3
  24. 2024Computing Systemic Risk Measures with Graph Neural Networkscited by 3
  25. 2023An Empirical Evaluation of Rewiring Approaches in Graph Neural Networkscited by 2
  26. 2024Statistical Guarantees for Link Prediction using Graph Neural Networkscited by 2
  27. 2024PAC-Bayesian Generalization Bounds for Knowledge Graph Representation Learningcited by 2
  28. 2024Analysis of Corrected Graph Convolutionscited by 2
  29. 2025Performance Heterogeneity in Graph Neural Networks: Lessons for Architecture Design and Preprocessingcited by 2
  30. 2025Understanding Generalization in Node and Link Predictioncited by 2
  31. 2023A Poincar'e Inequality and Consistency Results for Signal Sampling on Large Graphscited by 1
  32. 2025A Note on Graphon-Signal Analysis of Graph Neural Networkscited by 1
  33. 2025On the Rademacher Complexity of Graph Neural Networks: Unifying Expressivity and Geometrycited by 1
  34. 2025From Small to Large: Generalization Bounds for Transformers on Variable-Size Inputscited by 1
  35. 2026Topology-Aware PAC-Bayesian Generalization Analysis for Graph Neural Networkscited by 1
  36. 2026Any-Dimensional Learning by Samplingcited by 1
  37. 2024Perfect Recovery for Random Geometric Graph Matching with Shallow Graph Neural Networkscited by 0
  38. 2024Generalization of Graph Neural Networks through the Lens of Homomorphismcited by 0

50 most cited of 58 All 58 (JSON)