# Convergence and Stability of Graph Convolutional Networks on Large Random Graphs

arXiv: https://arxiv.org/abs/2006.01868 · HTML: https://mlsanity.com/paper/2006.01868/

## Key facts

- Cited by 76 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Jun 2020.

## Built on by (most cited first, 30 of 76)

- [Not too little, not too much: a theoretical analysis of graph (over)smoothing](https://mlsanity.com/paper/2205.12156/) (2022)
- [Generalization Analysis of Message Passing Neural Networks on Large Random Graphs](https://mlsanity.com/paper/2202.00645/) (2022)
- [Transferability of Graph Neural Networks: an Extended Graphon Approach](https://mlsanity.com/paper/2109.10096/) (2021)
- [Learning Theory Can (Sometimes) Explain Generalisation in Graph Neural Networks](https://mlsanity.com/paper/2112.03968/) (2021)
- [Transferability Properties of Graph Neural Networks](https://mlsanity.com/paper/2112.04629/) (2021)
- [Towards Understanding the Generalization of Graph Neural Networks](https://mlsanity.com/paper/2305.08048/) (2023)
- [OOD Link Prediction Generalization Capabilities of Message-Passing GNNs in Larger Test Graphs](https://mlsanity.com/paper/2205.15117/) (2022)
- [Generalised Implicit Neural Representations](https://mlsanity.com/paper/2205.15674/) (2022)
- [A graphon-signal analysis of graph neural networks](https://mlsanity.com/paper/2305.15987/) (2023)
- [On the Universality of Graph Neural Networks on Large Random Graphs](https://mlsanity.com/paper/2105.13099/) (2021)
- [Fine-grained Expressivity of Graph Neural Networks](https://mlsanity.com/paper/2306.03698/) (2023)
- [FedGCN: Convergence-Communication Tradeoffs in Federated Training of Graph Convolutional Networks](https://mlsanity.com/paper/2201.12433/) (2022)
- [Learning by Transference: Training Graph Neural Networks on Growing Graphs](https://mlsanity.com/paper/2106.03693/) (2021)
- [Graph-based Deep Learning for Communication Networks: A Survey](https://mlsanity.com/paper/2106.02533/) (2021)
- [coVariance Neural Networks](https://mlsanity.com/paper/2205.15856/) (2022)
- [Explainable Brain Age Prediction using coVariance Neural Networks](https://mlsanity.com/paper/2305.18370/) (2023)
- [Understanding Non-linearity in Graph Neural Networks from the Bayesian-Inference Perspective](https://mlsanity.com/paper/2207.11311/) (2022)
- [Limits, approximation and size transferability for GNNs on sparse graphs via graphops](https://mlsanity.com/paper/2306.04495/) (2023)
- [Generalization Bounds for Message Passing Networks on Mixture of Graphons](https://mlsanity.com/paper/2404.03473/) (2024)
- [A Manifold Perspective on the Statistical Generalization of Graph Neural Networks](https://mlsanity.com/paper/2406.05225/) (2024)
- [Graph Neural Tangent Kernel: Convergence on Large Graphs](https://mlsanity.com/paper/2301.10808/) (2023)
- [Convolutional Neural Networks on Manifolds: From Graphs and Back](https://mlsanity.com/paper/2210.00376/) (2022)
- [What functions can Graph Neural Networks compute on random graphs? The role of Positional Encoding](https://mlsanity.com/paper/2305.14814/) (2023)
- [BeMap: Balanced Message Passing for Fair Graph Neural Network](https://mlsanity.com/paper/2306.04107/) (2023)
- [Stability to Deformations of Manifold Filters and Manifold Neural Networks](https://mlsanity.com/paper/2106.03725/) (2021)
- [Subgraph-aware Few-Shot Inductive Link Prediction via Meta-Learning](https://mlsanity.com/paper/2108.00954/) (2021)
- [Stability of Neural Networks on Manifolds to Relative Perturbations](https://mlsanity.com/paper/2110.04702/) (2021)
- [Convergence of Invariant Graph Networks](https://mlsanity.com/paper/2201.10129/) (2022)
- [Convergence of Message Passing Graph Neural Networks with Generic Aggregation On Large Random Graphs](https://mlsanity.com/paper/2304.11140/) (2023)
- [Geometric Graph Filters and Neural Networks: Limit Properties and Discriminability Trade-offs](https://mlsanity.com/paper/2305.18467/) (2023)

## 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.