mlsanityData to 14 Oct 2026

Convergence of Message Passing Graph Neural Networks with Generic Aggregation On Large Random Graphs

arXiv 2304.11140 ↗First posted 21 Apr 2023stat.ML cs.LGcited by 9

Not on the map. Why?

Abstract (arXiv)

We study the convergence of message passing graph neural networks on random graph models to their continuous counterpart as the number of nodes tends to infinity. Until now, this convergence was only known for architectures with aggregation functions in the form of normalized means, or, equivalently, of an application of classical operators like the adjacency matrix or the graph Laplacian. We extend such results to a large class of aggregation functions, that encompasses all classically used message passing graph neural networks, such as attention-based message passing, max convolutional message passing, (degree-normalized) convolutional message passing, or moment-based aggregation message passing. Under mild assumptions, we give non-asymptotic bounds with high probability to quantify this convergence. Our main result is based on the McDiarmid inequality. Interestingly, this result does not apply to the case where the aggregation is a coordinate-wise maximum. We treat this case separately and obtain a different convergence rate.

Key facts. Cited by 9 papers in the map (data through 14 Oct 2026). Builds on 33 of its 64 references that are in the map. First posted on arXiv 21 Apr 2023.

Builds on

33 of 64 references.

References · 33

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  2. 2017Graph Attention Networkscited by 8,923
  3. 2017Inductive Representation Learning on Large Graphscited by 6,320
  4. 2018How Powerful are Graph Neural Networks?cited by 4,393
  5. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  6. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,919
  7. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,434
  8. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,163
  9. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,089
  10. 2019Simplifying Graph Convolutional Networkscited by 1,477
  11. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 881
  12. 2020Principal Neighbourhood Aggregation for Graph Netscited by 478
21 more
  1. 2019Provably Powerful Graph Networkscited by 389
  2. 2019Universal Invariant and Equivariant Graph Neural Networkscited by 183
  3. 2019On the Universality of Invariant Networkscited by 152
  4. 2013Consistency of spectral clustering in stochastic block modelscited by 129
  5. 2020Graphon Neural Networks and the Transferability of Graph Neural Networkscited by 118
  6. 2022Not too little, not too much: a theoretical analysis of graph (over)smoothingcited by 106
  7. 2020Building powerful and equivariant graph neural networks with structural message-passingcited by 97
  8. 2019Transferability of Spectral Graph Convolutional Neural Networkscited by 92
  9. 2020Graph Neural Networks: Architectures, Stability and Transferabilitycited by 80
  10. 2020Convergence and Stability of Graph Convolutional Networks on Large Random Graphscited by 76
  11. 2022Theory of Graph Neural Networks: Representation and Learningcited by 61
  12. 2022Generalization Analysis of Message Passing Neural Networks on Large Random Graphscited by 59
  13. 2021Transferability of Graph Neural Networks: an Extended Graphon Approachcited by 53
  14. 2022A Theoretical Comparison of Graph Neural Network Extensionscited by 48
  15. 2021Transferability Properties of Graph Neural Networkscited by 43
  16. 2020Graphon Signal Processingcited by 37
  17. 2021On the Universality of Graph Neural Networks on Large Random Graphscited by 26
  18. 2017Design of graph filters and filterbankscited by 22
  19. 2021Learning by Transference: Training Graph Neural Networks on Growing Graphscited by 22
  20. 2014Subsampling Methods for Persistent Homologycited by 17
  21. 2015Rates of convergence for robust geometric inferencecited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 1; 2024: 5; 2025: 2; 2026: 1.

9 papers.

  1. 2024Generalization Bounds for Message Passing Networks on Mixture of Graphonscited by 17
  2. 2023What functions can Graph Neural Networks compute on random graphs? The role of Positional Encodingcited by 12
  3. 2024Almost Surely Asymptotically Constant Graph Neural Networkscited by 7
  4. 2024Graph neural networks and non-commuting operatorscited by 5
  5. 2025Adaptive Canonicalization with Application to Invariant Anisotropic Geometric Networkscited by 3
  6. 2026Any-Dimensional Invariant Universalitycited by 3
  7. 2024SaVe-TAG: LLM-based Interpolation for Long-Tailed Text-Attributed Graphscited by 1
  8. 2025On the Convergence and Size Transferability of Continuous-depth Graph Neural Networkscited by 1
  9. 2024Node Regression on Latent Position Random Graphs via Local Averagingcited by 0