Analysis of Corrected Graph Convolutions
Not on the map. Why?
Abstract (arXiv)
Machine learning for node classification on graphs is a prominent area driven by applications such as recommendation systems. State-of-the-art models often use multiple graph convolutions on the data, as empirical evidence suggests they can enhance performance. However, it has been shown empirically and theoretically, that too many graph convolutions can degrade performance significantly, a phenomenon known as oversmoothing. In this paper, we provide a rigorous theoretical analysis, based on the two-class contextual stochastic block model (CSBM), of the performance of vanilla graph convolution from which we remove the principal eigenvector to avoid oversmoothing. We perform a spectral analysis for k rounds of corrected graph convolutions, and we provide results for partial and exact classification. For partial classification, we show that each round of convolution can reduce the misclassification error exponentially up to a saturation level, after which performance does not worsen. We also extend this analysis to the multi-class setting with features distributed according to a Gaussian mixture model. For exact classification, we show that the separability threshold can be improved exponentially up to O(logn/loglogn) corrected convolutions.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 34 of its 55 references that are in the map. First posted on arXiv 22 May 2024.
Builds on
34 of 55 references.
References · 34
- 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
- 2017Inductive Representation Learning on Large Graphscited by 6,284
- 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,085
- 2018Graph Convolutional Neural Networks for Web-Scale Recommender Systemscited by 1,133
- 2018Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learningcited by 1,099
- 2018Predict then Propagate: Graph Neural Networks meet Personalized PageRankcited by 987
- 2020Adaptive Universal Generalized PageRank Graph Neural Networkcited by 592
- 2019Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological Viewcited by 544
- 2016Interaction Networks for Learning about Objects, Relations and Physicscited by 503
- 2016Geometric deep learning on graphs and manifolds using mixture model CNNscited by 468
- 2017The Expressive Power of Neural Networks: A View from the Widthcited by 318
- 2019PairNorm: Tackling Oversmoothing in GNNscited by 297
22 more
- 2020SIGN: Scalable Inception Graph Neural Networkscited by 283
- 2023A Survey on Oversmoothing in Graph Neural Networkscited by 246
- 2020How Neural Networks Extrapolate: From Feedforward to Graph Neural Networkscited by 218
- 2021Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networkscited by 182
- 2021Is Homophily a Necessity for Graph Neural Networks?cited by 182
- 2022Graph neural networks for materials science and chemistrycited by 181
- 2019Anti-Money Laundering in Bitcoin: Experimenting with Graph Convolutional Networks for Financial Forensicscited by 158
- 2021Node Feature Extraction by Self-Supervised Multi-scale Neighborhood Predictioncited by 137
- 2018Contextual Stochastic Block Modelscited by 134
- 2021ETA Prediction with Graph Neural Networks in Google Mapscited by 130
- 2022Not too little, not too much: a theoretical analysis of graph (over)smoothingcited by 106
- 2021Is Heterophily A Real Nightmare For Graph Neural Networks To Do Node Classification?cited by 82
- 2021Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalizationcited by 70
- 2022Generalization Analysis of Message Passing Neural Networks on Large Random Graphscited by 58
- 2022A Non-Asymptotic Analysis of Oversmoothing in Graph Neural Networkscited by 49
- 2014Community Detection in Networks with Node Attributescited by 44
- 2019Stochastic Blockmodels meet Graph Neural Networkscited by 39
- 2022Graph Attention Retrospectivecited by 24
- 2022Effects of Graph Convolutions in Multi-layer Networkscited by 24
- 2020Contextual Stochastic Block Model: Sharp Thresholds and Contiguitycited by 22
- 2023Optimality of Message-Passing Architectures for Sparse Graphscited by 13
- 2023Improving Signed Propagation for Graph Neural Networks in Multi-Class Environmentscited by 2
Built on by
Citing papers per year: 2026: 2.
2 papers.