mlsanityData to 7 Oct 2026

Convergence and Stability of Graph Convolutional Networks on Large Random Graphs

arXiv 2006.01868 ↗First posted 2 Jun 2020stat.ML cs.LGcited by 75

Not on the map. Why?

Abstract (arXiv)

We study properties of Graph Convolutional Networks (GCNs) by analyzing their behavior on standard models of random graphs, where nodes are represented by random latent variables and edges are drawn according to a similarity kernel. This allows us to overcome the difficulties of dealing with discrete notions such as isomorphisms on very large graphs, by considering instead more natural geometric aspects. We first study the convergence of GCNs to their continuous counterpart as the number of nodes grows. Our results are fully non-asymptotic and are valid for relatively sparse graphs with an average degree that grows logarithmically with the number of nodes. We then analyze the stability of GCNs to small deformations of the random graph model. In contrast to previous studies of stability in discrete settings, our continuous setup allows us to provide more intuitive deformation-based metrics for understanding stability, which have proven useful for explaining the success of convolutional representations on Euclidean domains.

Key facts. Cited by 75 papers in the map (data through 7 Oct 2026). First posted on arXiv 2 Jun 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 13; 2022: 14; 2023: 19; 2024: 13; 2025: 5; 2026: 11.

75 papers.

Sort:

By area:

  1. 2022Not too little, not too much: a theoretical analysis of graph (over)smoothingcited by 106
  2. 2022Generalization Analysis of Message Passing Neural Networks on Large Random Graphscited by 58
  3. 2021Transferability of Graph Neural Networks: an Extended Graphon Approachcited by 51
  4. 2021Learning Theory Can (Sometimes) Explain Generalisation in Graph Neural Networkscited by 51
  5. 2021Transferability Properties of Graph Neural Networkscited by 42
  6. 2023Towards Understanding the Generalization of Graph Neural Networkscited by 41
  7. 2022OOD Link Prediction Generalization Capabilities of Message-Passing GNNs in Larger Test Graphscited by 38
  8. 2022Generalised Implicit Neural Representationscited by 31
  9. 2023A graphon-signal analysis of graph neural networkscited by 29
  10. 2021On the Universality of Graph Neural Networks on Large Random Graphscited by 26
  11. 2023Fine-grained Expressivity of Graph Neural Networkscited by 25
  12. 2022FedGCN: Convergence-Communication Tradeoffs in Federated Training of Graph Convolutional Networkscited by 24
38 more
  1. 2021Learning by Transference: Training Graph Neural Networks on Growing Graphscited by 22
  2. 2021Graph-based Deep Learning for Communication Networks: A Surveycited by 21
  3. 2022Understanding Non-linearity in Graph Neural Networks from the Bayesian-Inference Perspectivecited by 19
  4. 2023Explainable Brain Age Prediction using coVariance Neural Networkscited by 19
  5. 2022coVariance Neural Networkscited by 18
  6. 2023Limits, approximation and size transferability for GNNs on sparse graphs via graphopscited by 17
  7. 2023Graph Neural Tangent Kernel: Convergence on Large Graphscited by 16
  8. 2024Generalization Bounds for Message Passing Networks on Mixture of Graphonscited by 16
  9. 2024A Manifold Perspective on the Statistical Generalization of Graph Neural Networkscited by 16
  10. 2022Convolutional Neural Networks on Manifolds: From Graphs and Backcited by 13
  11. 2023What functions can Graph Neural Networks compute on random graphs? The role of Positional Encodingcited by 11
  12. 2023BeMap: Balanced Message Passing for Fair Graph Neural Networkcited by 11
  13. 2021Subgraph-aware Few-Shot Inductive Link Prediction via Meta-Learningcited by 9
  14. 2021Stability of Neural Networks on Manifolds to Relative Perturbationscited by 9
  15. 2023Convergence of Message Passing Graph Neural Networks with Generic Aggregation On Large Random Graphscited by 9
  16. 2023Geometric Graph Filters and Neural Networks: Limit Properties and Discriminability Trade-offscited by 9
  17. 2021Stability to Deformations of Manifold Filters and Manifold Neural Networkscited by 8
  18. 2022Convergence of Invariant Graph Networkscited by 8
  19. 2023Zero-One Laws of Graph Neural Networkscited by 7
  20. 2024Almost Surely Asymptotically Constant Graph Neural Networkscited by 7
  21. 2024Enhancing Size Generalization in Graph Neural Networks through Disentangled Representation Learningcited by 6
  22. 2024Sparse Covariance Neural Networkscited by 6
  23. 2024Deeper Insights into Deep Graph Convolutional Networks: Stability and Generalizationcited by 6
  24. 2021On the Stability of Low Pass Graph Filter With a Large Number of Edge Rewirescited by 5
  25. 2022Space-Time Graph Neural Networks with Stochastic Graph Perturbationscited by 5
  26. 2023Stability of Graph Convolutional Neural Networks through the lens of small perturbation analysiscited by 5
  27. 2024Future Directions in the Theory of Graph Machine Learningcited by 5
  28. 2024Graph neural networks and non-commuting operatorscited by 5
  29. 2022Convolutional Filtering on Sampled Manifoldscited by 4
  30. 2023Transferability of coVariance Neural Networks and Application to Interpretable Brain Age Prediction using Anatomical Featurescited by 4
  31. 2024SAGMAN: Stability Analysis of Graph Neural Networks on the Manifoldscited by 4
  32. 2024Generalization of Graph Neural Networks is Robust to Model Mismatchcited by 4
  33. 2022Entropic Optimal Transport in Random Graphscited by 3
  34. 2023Robust Graph Neural Network based on Graph Denoisingcited by 3
  35. 2022Stable and Transferable Hyper-Graph Neural Networkscited by 2
  36. 2023Limitless stability for Graph Convolutional Networkscited by 2
  37. 2023Local-to-global Perspectives on Graph Neural Networkscited by 2
  38. 2023Transferability of Graph Neural Networks using Graphon and Sampling Theoriescited by 2

50 most cited of 75 All 75 (JSON)