mlsanityData to 7 Oct 2026

Asymptotic generalization error of a single-layer graph convolutional network

arXiv 2402.03818 ↗First posted 6 Feb 2024cs.LG cond-mat.dis-nncited by 3

Not on the map. Why?

Abstract (arXiv)

While graph convolutional networks show great practical promises, the theoretical understanding of their generalization properties as a function of the number of samples is still in its infancy compared to the more broadly studied case of supervised fully connected neural networks. In this article, we predict the performances of a single-layer graph convolutional network (GCN) trained on data produced by attributed stochastic block models (SBMs) in the high-dimensional limit. Previously, only ridge regression on contextual-SBM (CSBM) has been considered in Shi et al. 2022; we generalize the analysis to arbitrary convex loss and regularization for the CSBM and add the analysis for another data model, the neural-prior SBM. We also study the high signal-to-noise ratio limit, detail the convergence rates of the GCN and show that, while consistent, it does not reach the Bayes-optimal rate for any of the considered cases.

Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 26 of its 35 references that are in the map. First posted on arXiv 6 Feb 2024.

Builds on

26 of 35 references.

References · 26

  1. 2017Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithmscited by 4,283
  2. 2019Simplifying Graph Convolutional Networkscited by 1,470
  3. 2019Surprises in High-Dimensional Ridgeless Least Squares Interpolationcited by 508
  4. 2019The generalization error of random features regression: Precise asymptotics and double descent curvecited by 410
  5. 2018Contextual Stochastic Block Modelscited by 134
  6. 2017Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Modelscited by 115
  7. 2018A modern maximum-likelihood theory for high-dimensional logistic regressioncited by 79
  8. 2021Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalizationcited by 70
  9. 2020The role of regularization in classification of high-dimensional noisy Gaussian mixturecited by 63
  10. 2021On Provable Benefits of Depth in Training Graph Convolutional Networkscited by 58
  11. 2020Generalization error in high-dimensional perceptrons: Approaching Bayes error with convex optimizationcited by 51
  12. 2021Learning Theory Can (Sometimes) Explain Generalisation in Graph Neural Networkscited by 51
14 more
  1. 2023Bayes-optimal Learning of Deep Random Networks of Extensive-widthcited by 41
  2. 2023Towards Understanding the Generalization of Graph Neural Networkscited by 41
  3. 2021p-Laplacian Based Graph Neural Networkscited by 39
  4. 2023Generalization in Graph Neural Networks: Improved PAC-Bayesian Bounds on Graph Diffusioncited by 39
  5. 2022EvenNet: Ignoring Odd-Hop Neighbors Improves Robustness of Graph Neural Networkscited by 26
  6. 2020Contextual Stochastic Block Model: Sharp Thresholds and Contiguitycited by 22
  7. 2019The spiked matrix model with generative priorscited by 20
  8. 2022Homophily modulates double descent generalization in graph convolution networkscited by 13
  9. 2023Optimality of Message-Passing Architectures for Sparse Graphscited by 13
  10. 2016Covariate Regularized Community Detection in Sparse Graphscited by 12
  11. 2023Optimal Inference in Contextual Stochastic Block Modelscited by 11
  12. 2023Is Solving Graph Neural Tangent Kernel Equivalent to Training Graph Neural Network?cited by 8
  13. 2023Neural-prior stochastic block modelcited by 4
  14. 2023Bayes optimal learning in high-dimensional linear regression with network side informationcited by 2

Built on by

Cited by year

Citing papers per year: 2024: 1; 2025: 2.

3 papers.

  1. 2025Statistical physics analysis of graph neural networks: Approaching optimality in the contextual stochastic block modelcited by 2
  2. 2024Optimal Exact Recovery in Semi-Supervised Learning: A Study of Spectral Methods and Graph Convolutional Networkscited by 0
  3. 2025PLATONT: Learning a Platonic Representation for Unified Network Tomographycited by 0