mlsanityData to 7 Oct 2026

Generalization Error of Graph Neural Networks in the Mean-field Regime

arXiv 2402.07025 ↗First posted 10 Feb 2024stat.ML cs.IT cs.LGcited by 4

Not on the map. Why?

Abstract (arXiv)

This work provides a theoretical framework for assessing the generalization error of graph neural networks in the over-parameterized regime, where the number of parameters surpasses the quantity of data points. We explore two widely utilized types of graph neural networks: graph convolutional neural networks and message passing graph neural networks. Prior to this study, existing bounds on the generalization error in the over-parametrized regime were uninformative, limiting our understanding of over-parameterized network performance. Our novel approach involves deriving upper bounds within the mean-field regime for evaluating the generalization error of these graph neural networks. We establish upper bounds with a convergence rate of O(1/n), where n is the number of graph samples. These upper bounds offer a theoretical assurance of the networks' performance on unseen data in the challenging over-parameterized regime and overall contribute to our understanding of their performance.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 51 of its 76 references that are in the map. First posted on arXiv 10 Feb 2024.

Builds on

51 of 76 references.

References · 51

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2017Graph Attention Networkscited by 8,854
  3. 2017Inductive Representation Learning on Large Graphscited by 6,284
  4. 2018How Powerful are Graph Neural Networks?cited by 4,355
  5. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  6. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  7. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,085
  8. 2018Relational inductive biases, deep learning, and graph networkscited by 1,341
  9. 2018Graph Convolutional Neural Networks for Web-Scale Recommender Systemscited by 1,133
  10. 2016Geometric deep learning: going beyond Euclidean datacited by 1,042
  11. 2018Reconciling modern machine learning practice and the bias-variance trade-offcited by 919
  12. 2018Hierarchical Graph Representation Learning with Differentiable Poolingcited by 786
38 more
  1. 2019Graph Neural Networks for Social Recommendationcited by 711
  2. 2019Graph U-Netscited by 489
  3. 2018Hypergraph Neural Networkscited by 482
  4. 2016Geometric deep learning on graphs and manifolds using mixture model CNNscited by 468
  5. 2018A Mean Field View of the Landscape of Two-Layers Neural Networkscited by 463
  6. 2018On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transportcited by 422
  7. 2019The generalization error of random features regression: Precise asymptotics and double descent curvecited by 410
  8. 2017A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networkscited by 309
  9. 2021Deep learning: a statistical viewpointcited by 239
  10. 2015Order Matters: Sequence to sequence for setscited by 236
  11. 2019Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networkscited by 221
  12. 2020Generalization and Representational Limits of Graph Neural Networkscited by 217
  13. 2019Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limitcited by 187
  14. 2020Feature Learning in Infinite-Width Neural Networkscited by 182
  15. 2019Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernelscited by 160
  16. 2019Linearized two-layers neural networks in high dimensioncited by 155
  17. 2016Discriminative Embeddings of Latent Variable Models for Structured Datacited by 130
  18. 2018Billion-scale Commodity Embedding for E-commerce Recommendation in Alibabacited by 105
  19. 2018Towards Sparse Hierarchical Graph Classifierscited by 100
  20. 2019What Can ResNet Learn Efficiently, Going Beyond Kernels?cited by 91
  21. 2020A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networkscited by 84
  22. 2019Stability and Generalization of Graph Convolutional Neural Networkscited by 81
  23. 2020Rethinking pooling in graph neural networkscited by 73
  24. 2018A jamming transition from under- to over-parametrization affects loss landscape and generalizationcited by 65
  25. 2021On Provable Benefits of Depth in Training Graph Convolutional Networkscited by 58
  26. 2022Generalization Analysis of Message Passing Neural Networks on Large Random Graphscited by 58
  27. 2021Learning Theory Can (Sometimes) Explain Generalisation in Graph Neural Networkscited by 51
  28. 2019Mean-Field Langevin Dynamics and Energy Landscape of Neural Networkscited by 49
  29. 2019Deep learning is adaptive to intrinsic dimensionality of model smoothness in anisotropic Besov spacecited by 46
  30. 2019Mean Field Analysis of Deep Neural Networkscited by 42
  31. 2023Towards Understanding the Generalization of Graph Neural Networkscited by 41
  32. 2023Generalization in Graph Neural Networks: Improved PAC-Bayesian Bounds on Graph Diffusioncited by 39
  33. 2020Optimization and Generalization Analysis of Transduction through Gradient Boosting and Application to Multi-scale Graph Neural Networkscited by 31
  34. 2020Fast Learning of Graph Neural Networks with Guaranteed Generalizability: One-hidden-layer Casecited by 24
  35. 2022Generalization Guarantee of Training Graph Convolutional Networks with Graph Topology Samplingcited by 23
  36. 2020Particle Dual Averaging: Optimization of Mean Field Neural Networks with Global Convergence Rate Analysiscited by 21
  37. 2021Generalization bounds for graph convolutional neural networks via Rademacher complexitycited by 17
  38. 2020Mathematical Models of Overparameterized Neural Networkscited by 15

50 most cited of 51 All 51 (JSON)

Built on by

Cited by year

Citing papers per year: 2024: 2; 2025: 2.

4 papers.

  1. 2025Unveiling Mode Connectivity in Graph Neural Networkscited by 3
  2. 2024When narrower is better: the narrow width limit of Bayesian parallel branching neural networkscited by 1
  3. 2024Understanding Transfer Learning via Mean-field Analysiscited by 1
  4. 2025Memorization in Graph Neural Networkscited by 0