mlsanityData to 7 Oct 2026

Generalization Guarantee of Training Graph Convolutional Networks with Graph Topology Sampling

arXiv 2207.03584 ↗First posted 7 Jul 2022cs.LGcited by 23

Not on the map. Why?

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.

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

Builds on

31 of 39 references.

References · 31

  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. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  6. 2018Graph Convolutional Neural Networks for Web-Scale Recommender Systemscited by 1,133
  7. 2015Convolutional Networks on Graphs for Learning Molecular Fingerprintscited by 751
  8. 2018FastGCN: Fast Learning with Graph Convolutional Networks via Importance Samplingcited by 583
  9. 2019Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networkscited by 540
  10. 2016Interaction Networks for Learning about Objects, Relations and Physicscited by 503
  11. 2018Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layerscited by 340
  12. 2017Few-Shot Learning with Graph Neural Networkscited by 324
19 more
  1. 2017Relation Networks for Object Detectioncited by 305
  2. 2018Graph networks as learnable physics engines for inference and controlcited by 242
  3. 2015Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decompositioncited by 241
  4. 2020Generalization and Representational Limits of Graph Neural Networkscited by 217
  5. 2019Layer-Dependent Importance Sampling for Training Deep and Large Graph Convolutional Networkscited by 177
  6. 2019Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernelscited by 160
  7. 2018Zero-shot Recognition via Semantic Embeddings and Knowledge Graphscited by 155
  8. 2021A Unified Lottery Ticket Hypothesis for Graph Neural Networkscited by 118
  9. 2017Cross-Sentence N-ary Relation Extraction with Graph LSTMscited by 101
  10. 2017Recovery Guarantees for One-hidden-layer Neural Networkscited by 94
  11. 2020A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networkscited by 84
  12. 2019Stability and Generalization of Graph Convolutional Neural Networkscited by 81
  13. 2021On Provable Benefits of Depth in Training Graph Convolutional Networkscited by 58
  14. 2021Optimization of Graph Neural Networks: Implicit Acceleration by Skip Connections and More Depthcited by 55
  15. 2017SGD Learns the Conjugate Kernel Class of the Networkcited by 54
  16. 2020Optimization and Generalization Analysis of Transduction through Gradient Boosting and Application to Multi-scale Graph Neural Networkscited by 31
  17. 2020Fast Learning of Graph Neural Networks with Guaranteed Generalizability: One-hidden-layer Casecited by 24
  18. 2018Guaranteed Recovery of One-Hidden-Layer Neural Networks via Cross Entropycited by 22
  19. 2021Generalization bounds for graph convolutional neural networks via Rademacher complexitycited by 17

Built on by

Cited by year (2026 to 7 Oct)

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

23 papers.

Sort:

By area:

  1. 2023A Theoretical Understanding of Shallow Vision Transformers: Learning, Generalization, and Sample Complexitycited by 77
  2. 2023Towards Understanding the Generalization of Graph Neural Networkscited by 41
  3. 2023Patch-level Routing in Mixture-of-Experts is Provably Sample-efficient for Convolutional Neural Networkscited by 35
  4. 2024How Do Nonlinear Transformers Learn and Generalize in In-Context Learning?cited by 35
  5. 2024A Provably Effective Method for Pruning Experts in Fine-tuned Sparse Mixture-of-Expertscited by 21
  6. 2023On the Convergence and Sample Complexity Analysis of Deep Q-Networks with ε-Greedy Explorationcited by 17
  7. 2023Joint Edge-Model Sparse Learning is Provably Efficient for Graph Neural Networkscited by 16
  8. 2024What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encodingcited by 14
  9. 2024Towards Bridging Generalization and Expressivity of Graph Neural Networkscited by 12
  10. 2024Learning on Transformers is Provable Low-Rank and Sparse: A One-layer Analysiscited by 8
  11. 2022Analysis of Convolutions, Non-linearity and Depth in Graph Neural Networks using Neural Tangent Kernelcited by 7
  12. 2022Not All Neighbors Are Worth Attending to: Graph Selective Attention Networks for Semi-supervised Learningcited by 6
11 more
  1. 2024How does promoting the minority fraction affect generalization? A theoretical study of the one-hidden-layer neural network on group imbalancecited by 6
  2. 2024Deeper Insights into Deep Graph Convolutional Networks: Stability and Generalizationcited by 6
  3. 2024Generalization Error of Graph Neural Networks in the Mean-field Regimecited by 4
  4. 2025How Can Mamba Learn In Context with Outliers and Generalize Provably?cited by 2
  5. 2024Introducing Diminutive Causal Structure into Graph Representation Learningcited by 1
  6. 2025A Note on Graphon-Signal Analysis of Graph Neural Networkscited by 1
  7. 2026Efficient Quantization of Mixture-of-Experts with Theoretical Generalization Guaranteescited by 1
  8. 2024Generalization of Graph Neural Networks through the Lens of Homomorphismcited by 0
  9. 2024The Transferability of Downsamped Sparse Graph Convolutional Networkscited by 0
  10. 2025Theoretical Learning Performance of Graph Neural Networks: The Impact of Jumping Connections and Layer-wise Sparsificationcited by 0
  11. 2025On Local Limits of Sparse Random Graphs: Color Convergence and the Refined Configuration Modelcited by 0