# A Non-Asymptotic Analysis of Oversmoothing in Graph Neural Networks

arXiv: https://arxiv.org/abs/2212.10701 · HTML: https://mlsanity.com/paper/2212.10701/

## Key facts

- Cited by 49 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 47 references that are in the map.
- First posted on arXiv 21 Dec 2022.

## Builds on (most cited first, 30 of 32)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [Representation Learning on Graphs with Jumping Knowledge Networks](https://mlsanity.com/paper/1806.03536/) (2018)
- [Simple and Deep Graph Convolutional Networks](https://mlsanity.com/paper/2007.02133/) (2020)
- [Gated Graph Sequence Neural Networks](https://mlsanity.com/paper/1511.05493/) (2015)
- [Convolutional Networks on Graphs for Learning Molecular Fingerprints](https://mlsanity.com/paper/1509.09292/) (2015)
- [Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological View](https://mlsanity.com/paper/1909.03211/) (2019)
- [DeepGCNs: Can GCNs Go as Deep as CNNs?](https://mlsanity.com/paper/1904.03751/) (2019)
- [Interaction Networks for Learning about Objects, Relations and Physics](https://mlsanity.com/paper/1612.00222/) (2016)
- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [PairNorm: Tackling Oversmoothing in GNNs](https://mlsanity.com/paper/1909.12223/) (2019)
- [Combining Label Propagation and Simple Models Out-performs Graph Neural Networks](https://mlsanity.com/paper/2010.13993/) (2020)
- [Is Homophily a Necessity for Graph Neural Networks?](https://mlsanity.com/paper/2106.06134/) (2021)
- [Contextual Stochastic Block Models](https://mlsanity.com/paper/1807.09596/) (2018)
- [Not too little, not too much: a theoretical analysis of graph (over)smoothing](https://mlsanity.com/paper/2205.12156/) (2022)
- [Unifying Graph Convolutional Neural Networks and Label Propagation](https://mlsanity.com/paper/2002.06755/) (2020)
- [Non-Local Graph Neural Networks](https://mlsanity.com/paper/2005.14612/) (2020)
- [Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalization](https://mlsanity.com/paper/2102.06966/) (2021)
- [Tackling Over-Smoothing for General Graph Convolutional Networks](https://mlsanity.com/paper/2008.09864/) (2020)
- [Width Provably Matters in Optimization for Deep Linear Neural Networks](https://mlsanity.com/paper/1901.08572/) (2019)
- [Graph Attention Retrospective](https://mlsanity.com/paper/2202.13060/) (2022)

## Built on by (most cited first, 30 of 49)

- [Demystifying Oversmoothing in Attention-Based Graph Neural Networks](https://mlsanity.com/paper/2305.16102/) (2023)
- [A Fractional Graph Laplacian Approach to Oversmoothing](https://mlsanity.com/paper/2305.13084/) (2023)
- [Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All?](https://mlsanity.com/paper/2306.01323/) (2023)
- [Sheaf Hypergraph Networks](https://mlsanity.com/paper/2309.17116/) (2023)
- [Residual Connections and Normalization Can Provably Prevent Oversmoothing in GNNs](https://mlsanity.com/paper/2406.02997/) (2024)
- [Towards Deep Attention in Graph Neural Networks: Problems and Remedies](https://mlsanity.com/paper/2306.02376/) (2023)
- [Over-Squashing in Graph Neural Networks: A Comprehensive survey](https://mlsanity.com/paper/2308.15568/) (2023)
- [Exposition on over-squashing problem on GNNs: Current Methods, Benchmarks and Challenges](https://mlsanity.com/paper/2311.07073/) (2023)
- [A Neural Collapse Perspective on Feature Evolution in Graph Neural Networks](https://mlsanity.com/paper/2307.01951/) (2023)
- [Oversmoothing, Oversquashing, Heterophily, Long-Range, and more: Demystifying Common Beliefs in Graph Machine Learning](https://mlsanity.com/paper/2505.15547/) (2025)
- [Understanding and Mitigating Bottlenecks of State Space Models through the Lens of Recency and Over-smoothing](https://mlsanity.com/paper/2501.00658/) (2024)
- [Understanding Heterophily for Graph Neural Networks](https://mlsanity.com/paper/2401.09125/) (2024)
- [Optimal Inference in Contextual Stochastic Block Models](https://mlsanity.com/paper/2306.07948/) (2023)
- [Joint Graph Rewiring and Feature Denoising via Spectral Resonance](https://mlsanity.com/paper/2408.07191/) (2024)
- [Graph Convolutions Enrich the Self-Attention in Transformers!](https://mlsanity.com/paper/2312.04234/) (2023)
- [Feature Distribution on Graph Topology Mediates the Effect of Graph Convolution: Homophily Perspective](https://mlsanity.com/paper/2402.04621/) (2024)
- [Sign is Not a Remedy: Multiset-to-Multiset Message Passing for Learning on Heterophilic Graphs](https://mlsanity.com/paper/2405.20652/) (2024)
- [Centered Self-Attention Layers](https://mlsanity.com/paper/2306.01610/) (2023)
- [Graph Neural Networks Do Not Always Oversmooth](https://mlsanity.com/paper/2406.02269/) (2024)
- [Residual connections provably mitigate oversmoothing in graph neural networks](https://mlsanity.com/paper/2501.00762/) (2025)
- [Query-Aware Flow Diffusion for Graph-Based RAG with Retrieval Guarantees](https://mlsanity.com/paper/2605.18775/) (2026)
- [Are We Measuring Oversmoothing in Graph Neural Networks Correctly?](https://mlsanity.com/paper/2502.04591/) (2025)
- [Principles for Initialization and Architecture Selection in Graph Neural Networks with ReLU Activations](https://mlsanity.com/paper/2306.11668/) (2023)
- [Taming Gradient Oversmoothing and Expansion in Graph Neural Networks](https://mlsanity.com/paper/2410.04824/) (2024)
- [Improving Graph Neural Networks by Learning Continuous Edge Directions](https://mlsanity.com/paper/2410.14109/) (2024)
- [The Oversmoothing Fallacy: A Misguided Narrative in GNN Research](https://mlsanity.com/paper/2506.04653/) (2025)
- [Analysis of Corrected Graph Convolutions](https://mlsanity.com/paper/2405.13987/) (2024)
- [Graph Attention is Not Always Beneficial: A Theoretical Analysis of Graph Attention Mechanisms via Contextual Stochastic Block Models](https://mlsanity.com/paper/2412.15496/) (2024)
- [Resolving Oversmoothing with Opinion Dissensus](https://mlsanity.com/paper/2501.19089/) (2025)
- [A Signed Graph Approach to Understanding and Mitigating Oversmoothing in GNNs](https://mlsanity.com/paper/2502.11394/) (2025)

## Abstract (arXiv)

Oversmoothing is a central challenge of building more powerful Graph Neural Networks (GNNs). While previous works have only demonstrated that oversmoothing is inevitable when the number of graph convolutions tends to infinity, in this paper, we precisely characterize the mechanism behind the phenomenon via a non-asymptotic analysis. Specifically, we distinguish between two different effects when applying graph convolutions -- an undesirable mixing effect that homogenizes node representations in different classes, and a desirable denoising effect that homogenizes node representations in the same class. By quantifying these two effects on random graphs sampled from the Contextual Stochastic Block Model (CSBM), we show that oversmoothing happens once the mixing effect starts to dominate the denoising effect, and the number of layers required for this transition is O(log N/log (log N)) for sufficiently dense graphs with N nodes. We also extend our analysis to study the effects of Personalized PageRank (PPR), or equivalently, the effects of initial residual connections on oversmoothing. Our results suggest that while PPR mitigates oversmoothing at deeper layers, PPR-based architectures still achieve their best performance at a shallow depth and are outperformed by the graph convolution approach on certain graphs. Finally, we support our theoretical results with numerical experiments, which further suggest that the oversmoothing phenomenon observed in practice can be magnified by the difficulty of optimizing deep GNN models.