mlsanityData to 7 Oct 2026

Generalization bounds for graph convolutional neural networks via Rademacher complexity

arXiv 2102.10234 ↗First posted 20 Feb 2021stat.ML cs.LGcited by 17

Not on the map. Why?

Abstract (arXiv)

This paper aims at studying the sample complexity of graph convolutional networks (GCNs), by providing tight upper bounds of Rademacher complexity for GCN models with a single hidden layer. Under regularity conditions, theses derived complexity bounds explicitly depend on the largest eigenvalue of graph convolution filter and the degree distribution of the graph. Again, we provide a lower bound of Rademacher complexity for GCNs to show optimality of our derived upper bounds. Taking two commonly used examples as representatives, we discuss the implications of our results in designing graph convolution filters an graph distribution.

Key facts. Cited by 17 papers in the map (data through 7 Oct 2026). Builds on 20 of its 29 references that are in the map. First posted on arXiv 20 Feb 2021.

Builds on

20 of 29 references.

References · 20

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2017Inductive Representation Learning on Large Graphscited by 6,284
  3. 2018Graph Neural Networks: A Review of Methods and Applicationscited by 1,571
  4. 2014DeepWalk: Online Learning of Social Representationscited by 1,543
  5. 2018Graph Convolutional Neural Networks for Web-Scale Recommender Systemscited by 1,133
  6. 2013Spectral Networks and Locally Connected Networks on Graphscited by 1,097
  7. 2016Geometric deep learning: going beyond Euclidean datacited by 1,042
  8. 2015Gated Graph Sequence Neural Networkscited by 792
  9. 2017Spectrally-normalized margin bounds for neural networkscited by 681
  10. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
  11. 2016Interaction Networks for Learning about Objects, Relations and Physicscited by 503
  12. 2015Norm-Based Capacity Control in Neural Networkscited by 299
8 more
  1. 2017Size-Independent Sample Complexity of Neural Networkscited by 289
  2. 2020Generalization and Representational Limits of Graph Neural Networkscited by 217
  3. 2019Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernelscited by 160
  4. 2020A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networkscited by 84
  5. 2019Stability and Generalization of Graph Convolutional Neural Networkscited by 81
  6. 2018Generalization Error in Deep Learningcited by 46
  7. 2020Fast Learning of Graph Neural Networks with Guaranteed Generalizability: One-hidden-layer Casecited by 24
  8. 2017Unifying local and non-local signal processing with graph CNNscited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 3; 2023: 2; 2024: 4; 2025: 3; 2026: 3.

17 papers.

Sort:

  1. 2022Out-Of-Distribution Generalization on Graphs: A Surveycited by 97
  2. 2023Towards Understanding the Generalization of Graph Neural Networkscited by 41
  3. 2022Generalization Guarantee of Training Graph Convolutional Networks with Graph Topology Samplingcited by 23
  4. 2022Bounding the Rademacher Complexity of Fourier neural operatorscited by 16
  5. 2024On the hardness of learning under symmetriescited by 13
  6. 2024Deeper Insights into Deep Graph Convolutional Networks: Stability and Generalizationcited by 6
  7. 2024Generalization Error of Graph Neural Networks in the Mean-field Regimecited by 4
  8. 2024Foundations and Frontiers of Graph Learning Theorycited by 3
  9. 2025On the Interplay between Graph Structure and Learning Algorithms in Graph Neural Networkscited by 2
  10. 2023A Model-Agnostic Graph Neural Network for Integrating Local and Global Informationcited by 1
  11. 2025Conv4Rec: A 1-by-1 Convolutional AutoEncoder for User Profiling through Joint Analysis of Implicit and Explicit Feedbackscited by 1
  12. 2026Topology-Aware PAC-Bayesian Generalization Analysis for Graph Neural Networkscited by 1
5 more
  1. 2021Learning on Random Balls is Sufficient for Estimating (Some) Graph Parameterscited by 0
  2. 2021SStaGCN: Simplified stacking based graph convolutional networkscited by 0
  3. 2025Exact Generalisation Error Exposes Benchmarks Skew Graph Neural Networks Success (or Failure)cited by 0
  4. 2026Rethinking Generalization in Graph Neural Networks: A Structural Complexity Perspectivecited by 0
  5. 2026PAC-Bayesian Adversarially Robust Generalization for Message Passing Graph Neural Networks: A Sensitivity Analysiscited by 0