Statistical physics analysis of graph neural networks: Approaching optimality in the contextual stochastic block model
Not on the map. Why?
Abstract (arXiv)
Graph neural networks (GNNs) are designed to process data associated with graphs. They are finding an increasing range of applications; however, as with other modern machine learning techniques, their theoretical understanding is limited. GNNs can encounter difficulties in gathering information from nodes that are far apart by iterated aggregation steps. This situation is partly caused by so-called oversmoothing; and overcoming it is one of the practically motivated challenges. We consider the situation where information is aggregated by multiple steps of convolution, leading to graph convolutional networks (GCNs). We analyze the generalization performance of a basic GCN, trained for node classification on data generated by the contextual stochastic block model. We predict its asymptotic performance by deriving the free energy of the problem, using the replica method, in the high-dimensional limit. Calling depth the number of convolutional steps, we show the importance of going to large depth to approach the Bayes-optimality. We detail how the architecture of the GCN has to scale with the depth to avoid oversmoothing. The resulting large depth limit can be close to the Bayes-optimality and leads to a continuous GCN. Technically, we tackle this continuous limit via an approach that resembles dynamical mean-field theory (DMFT) with constraints at the initial and final times. An expansion around large regularization allows us to solve the corresponding equations for the performance of the deep GCN. This promising tool may contribute to the analysis of further deep neural networks.
Key facts. Cited by 2 papers in the map (data through 13 Oct 2026). Builds on 40 of its 54 references that are in the map. First posted on arXiv 3 Mar 2025.
Builds on
40 of 54 references.
References · 40
- 2015Deep Residual Learning for Image Recognitioncited by 51,950
- 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,318
- 2018Neural Ordinary Differential Equationscited by 3,750
- 2019Simplifying Graph Convolutional Networkscited by 1,474
- 2018Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learningcited by 1,099
- 2018Pitfalls of Graph Neural Network Evaluationcited by 1,003
- 2020Learning to Simulate Complex Physics with Graph Networkscited by 873
- 2020Simple and Deep Graph Convolutional Networkscited by 857
- 2019DeepGCNs: Can GCNs Go as Deep as CNNs?cited by 527
- 2019The generalization error of random features regression: Precise asymptotics and double descent curvecited by 411
- 2021Combinatorial optimization and reasoning with graph neural networkscited by 267
- 2019Graph Neural Ordinary Differential Equationscited by 154
28 more
- 2018Contextual Stochastic Block Modelscited by 134
- 2021Learning curves of generic features maps for realistic datasets with a teacher-student modelcited by 126
- 2019Continuous Graph Neural Networkscited by 114
- 2022Not too little, not too much: a theoretical analysis of graph (over)smoothingcited by 106
- 2021Graph Representation Learning in Biomedicinecited by 80
- 2021Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalizationcited by 70
- 2020The role of regularization in classification of high-dimensional noisy Gaussian mixturecited by 63
- 2021On Provable Benefits of Depth in Training Graph Convolutional Networkscited by 58
- 2021Optimization of Graph Neural Networks: Implicit Acceleration by Skip Connections and More Depthcited by 55
- 2020Generalization error in high-dimensional perceptrons: Approaching Bayes error with convex optimizationcited by 51
- 2021Learning Theory Can (Sometimes) Explain Generalisation in Graph Neural Networkscited by 51
- 2023Bayes-optimal Learning of Deep Random Networks of Extensive-widthcited by 41
- 2023Towards Understanding the Generalization of Graph Neural Networkscited by 41
- 2021p-Laplacian Based Graph Neural Networkscited by 39
- 2023Generalization in Graph Neural Networks: Improved PAC-Bayesian Bounds on Graph Diffusioncited by 39
- 2022Do Residual Neural Networks discretize Neural Ordinary Differential Equations?cited by 27
- 2022EvenNet: Ignoring Odd-Hop Neighbors Improves Robustness of Graph Neural Networkscited by 26
- 2023From Continuous Dynamics to Graph Neural Networks: Neural Diffusion and Beyondcited by 26
- 2020Contextual Stochastic Block Model: Sharp Thresholds and Contiguitycited by 22
- 2022Graph Neural Networks for Moleculescited by 21
- 2023Generalization bounds for neural ordinary differential equations and deep residual networkscited by 21
- 2016Column Networks for Collective Classificationcited by 17
- 2022Homophily modulates double descent generalization in graph convolution networkscited by 13
- 2023Optimality of Message-Passing Architectures for Sparse Graphscited by 13
- 2016Covariate Regularized Community Detection in Sparse Graphscited by 12
- 2023Optimal Inference in Contextual Stochastic Block Modelscited by 11
- 2023Neural-prior stochastic block modelcited by 4
- 2024Asymptotic generalization error of a single-layer graph convolutional networkcited by 3
Built on by
Citing papers per year: 2025: 1; 2026: 1.
2 papers.