# Generalization Guarantee of Training Graph Convolutional Networks with Graph Topology Sampling

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 39 references that are in the map.
- First posted on arXiv 7 Jul 2022.

## Builds on (most cited first, 30 of 31)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Convolutional Networks on Graphs for Learning Molecular Fingerprints](https://mlsanity.com/paper/1509.09292/) (2015)
- [FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling](https://mlsanity.com/paper/1801.10247/) (2018)
- [Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks](https://mlsanity.com/paper/1905.07953/) (2019)
- [Interaction Networks for Learning about Objects, Relations and Physics](https://mlsanity.com/paper/1612.00222/) (2016)
- [Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers](https://mlsanity.com/paper/1811.04918/) (2018)
- [Few-Shot Learning with Graph Neural Networks](https://mlsanity.com/paper/1711.04043/) (2017)
- [Relation Networks for Object Detection](https://mlsanity.com/paper/1711.11575/) (2017)
- [Graph networks as learnable physics engines for inference and control](https://mlsanity.com/paper/1806.01242/) (2018)
- [Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition](https://mlsanity.com/paper/1503.02101/) (2015)
- [Generalization and Representational Limits of Graph Neural Networks](https://mlsanity.com/paper/2002.06157/) (2020)
- [Layer-Dependent Importance Sampling for Training Deep and Large Graph Convolutional Networks](https://mlsanity.com/paper/1911.07323/) (2019)
- [Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels](https://mlsanity.com/paper/1905.13192/) (2019)
- [Zero-shot Recognition via Semantic Embeddings and Knowledge Graphs](https://mlsanity.com/paper/1803.08035/) (2018)
- [A Unified Lottery Ticket Hypothesis for Graph Neural Networks](https://mlsanity.com/paper/2102.06790/) (2021)
- [Cross-Sentence N-ary Relation Extraction with Graph LSTMs](https://mlsanity.com/paper/1708.03743/) (2017)
- [Recovery Guarantees for One-hidden-layer Neural Networks](https://mlsanity.com/paper/1706.03175/) (2017)
- [A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networks](https://mlsanity.com/paper/2012.07690/) (2020)
- [Stability and Generalization of Graph Convolutional Neural Networks](https://mlsanity.com/paper/1905.01004/) (2019)
- [On Provable Benefits of Depth in Training Graph Convolutional Networks](https://mlsanity.com/paper/2110.15174/) (2021)
- [Optimization of Graph Neural Networks: Implicit Acceleration by Skip Connections and More Depth](https://mlsanity.com/paper/2105.04550/) (2021)
- [SGD Learns the Conjugate Kernel Class of the Network](https://mlsanity.com/paper/1702.08503/) (2017)
- [Optimization and Generalization Analysis of Transduction through Gradient Boosting and Application to Multi-scale Graph Neural Networks](https://mlsanity.com/paper/2006.08550/) (2020)
- [Fast Learning of Graph Neural Networks with Guaranteed Generalizability: One-hidden-layer Case](https://mlsanity.com/paper/2006.14117/) (2020)
- [Guaranteed Recovery of One-Hidden-Layer Neural Networks via Cross Entropy](https://mlsanity.com/paper/1802.06463/) (2018)

## Built on by (most cited first, 23 of 23)

- [A Theoretical Understanding of Shallow Vision Transformers: Learning, Generalization, and Sample Complexity](https://mlsanity.com/paper/2302.06015/) (2023)
- [Towards Understanding the Generalization of Graph Neural Networks](https://mlsanity.com/paper/2305.08048/) (2023)
- [Patch-level Routing in Mixture-of-Experts is Provably Sample-efficient for Convolutional Neural Networks](https://mlsanity.com/paper/2306.04073/) (2023)
- [How Do Nonlinear Transformers Learn and Generalize in In-Context Learning?](https://mlsanity.com/paper/2402.15607/) (2024)
- [A Provably Effective Method for Pruning Experts in Fine-tuned Sparse Mixture-of-Experts](https://mlsanity.com/paper/2405.16646/) (2024)
- [On the Convergence and Sample Complexity Analysis of Deep Q-Networks with ε-Greedy Exploration](https://mlsanity.com/paper/2310.16173/) (2023)
- [Joint Edge-Model Sparse Learning is Provably Efficient for Graph Neural Networks](https://mlsanity.com/paper/2302.02922/) (2023)
- [What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encoding](https://mlsanity.com/paper/2406.01977/) (2024)
- [Towards Bridging Generalization and Expressivity of Graph Neural Networks](https://mlsanity.com/paper/2410.10051/) (2024)
- [Analysis of Convolutions, Non-linearity and Depth in Graph Neural Networks using Neural Tangent Kernel](https://mlsanity.com/paper/2210.09809/) (2022)
- [Learning on Transformers is Provable Low-Rank and Sparse: A One-layer Analysis](https://mlsanity.com/paper/2406.17167/) (2024)
- [Not All Neighbors Are Worth Attending to: Graph Selective Attention Networks for Semi-supervised Learning](https://mlsanity.com/paper/2210.07715/) (2022)
- [How does promoting the minority fraction affect generalization? A theoretical study of the one-hidden-layer neural network on group imbalance](https://mlsanity.com/paper/2403.07310/) (2024)
- [Deeper Insights into Deep Graph Convolutional Networks: Stability and Generalization](https://mlsanity.com/paper/2410.08473/) (2024)
- [Generalization Error of Graph Neural Networks in the Mean-field Regime](https://mlsanity.com/paper/2402.07025/) (2024)
- [How Can Mamba Learn In Context with Outliers and Generalize Provably?](https://mlsanity.com/paper/2510.00399/) (2025)
- [Efficient Quantization of Mixture-of-Experts with Theoretical Generalization Guarantees](https://mlsanity.com/paper/2604.06515/) (2026)
- [Generalization of Graph Neural Networks through the Lens of Homomorphism](https://mlsanity.com/paper/2403.06079/) (2024)
- [Introducing Diminutive Causal Structure into Graph Representation Learning](https://mlsanity.com/paper/2406.08709/) (2024)
- [A Note on Graphon-Signal Analysis of Graph Neural Networks](https://mlsanity.com/paper/2508.18564/) (2025)
- [The Transferability of Downsamped Sparse Graph Convolutional Networks](https://mlsanity.com/paper/2408.17274/) (2024)
- [Theoretical Learning Performance of Graph Neural Networks: The Impact of Jumping Connections and Layer-wise Sparsification](https://mlsanity.com/paper/2507.05533/) (2025)
- [On Local Limits of Sparse Random Graphs: Color Convergence and the Refined Configuration Model](https://mlsanity.com/paper/2510.21392/) (2025)

## Abstract (arXiv)

Graph convolutional networks (GCNs) have recently achieved great empirical success in learning graph-structured data. To address its scalability issue due to the recursive embedding of neighboring features, graph topology sampling has been proposed to reduce the memory and computational cost of training GCNs, and it has achieved comparable test performance to those without topology sampling in many empirical studies. To the best of our knowledge, this paper provides the first theoretical justification of graph topology sampling in training (up to) three-layer GCNs for semi-supervised node classification. We formally characterize some sufficient conditions on graph topology sampling such that GCN training leads to a diminishing generalization error. Moreover, our method tackles the nonconvex interaction of weights across layers, which is under-explored in the existing theoretical analyses of GCNs. This paper characterizes the impact of graph structures and topology sampling on the generalization performance and sample complexity explicitly, and the theoretical findings are also justified through numerical experiments.