mlsanityData to 14 Oct 2026

A Non-Asymptotic Analysis of Oversmoothing in Graph Neural Networks

arXiv 2212.10701 ↗First posted 21 Dec 2022cs.LG cs.SI stat.MLcited by 49

Not on the map. Why?

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.

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

32 of 47 references.

References · 32

  1. 2015Deep Residual Learning for Image Recognitioncited by 52,096
  2. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,305
  3. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  4. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  5. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,919
  6. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,434
  7. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,089
  8. 2013Spectral Networks and Locally Connected Networks on Graphscited by 1,102
  9. 2018Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learningcited by 1,102
  10. 2018Predict then Propagate: Graph Neural Networks meet Personalized PageRankcited by 993
  11. 2016Revisiting Semi-Supervised Learning with Graph Embeddingscited by 976
  12. 2018Representation Learning on Graphs with Jumping Knowledge Networkscited by 877
20 more
  1. 2020Simple and Deep Graph Convolutional Networkscited by 860
  2. 2015Gated Graph Sequence Neural Networkscited by 796
  3. 2015Convolutional Networks on Graphs for Learning Molecular Fingerprintscited by 754
  4. 2019Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological Viewcited by 545
  5. 2019DeepGCNs: Can GCNs Go as Deep as CNNs?cited by 527
  6. 2016Interaction Networks for Learning about Objects, Relations and Physicscited by 509
  7. 2017Community Detection and Stochastic Block Modelscited by 319
  8. 2019PairNorm: Tackling Oversmoothing in GNNscited by 297
  9. 2020Combining Label Propagation and Simple Models Out-performs Graph Neural Networkscited by 202
  10. 2021Is Homophily a Necessity for Graph Neural Networks?cited by 182
  11. 2018Contextual Stochastic Block Modelscited by 134
  12. 2022Not too little, not too much: a theoretical analysis of graph (over)smoothingcited by 106
  13. 2020Unifying Graph Convolutional Neural Networks and Label Propagationcited by 98
  14. 2020Non-Local Graph Neural Networkscited by 91
  15. 2021Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalizationcited by 70
  16. 2020Tackling Over-Smoothing for General Graph Convolutional Networkscited by 66
  17. 2019Width Provably Matters in Optimization for Deep Linear Neural Networkscited by 52
  18. 2022Graph Attention Retrospectivecited by 24
  19. 2018Exponential Convergence Time of Gradient Descent for One-Dimensional Deep Linear Neural Networkscited by 22
  20. 2022Understanding Non-linearity in Graph Neural Networks from the Bayesian-Inference Perspectivecited by 19

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 14; 2024: 18; 2025: 10; 2026: 7.

49 papers.

Sort:

By area:

  1. 2023Demystifying Oversmoothing in Attention-Based Graph Neural Networkscited by 49
  2. 2023A Fractional Graph Laplacian Approach to Oversmoothingcited by 45
  3. 2023Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All?cited by 41
  4. 2023Sheaf Hypergraph Networkscited by 34
  5. 2024Residual Connections and Normalization Can Provably Prevent Oversmoothing in GNNscited by 34
  6. 2023Towards Deep Attention in Graph Neural Networks: Problems and Remediescited by 24
  7. 2023Over-Squashing in Graph Neural Networks: A Comprehensive surveycited by 23
  8. 2023Exposition on over-squashing problem on GNNs: Current Methods, Benchmarks and Challengescited by 22
  9. 2023A Neural Collapse Perspective on Feature Evolution in Graph Neural Networkscited by 19
  10. 2025Oversmoothing, Oversquashing, Heterophily, Long-Range, and more: Demystifying Common Beliefs in Graph Machine Learningcited by 19
  11. 2024Understanding and Mitigating Bottlenecks of State Space Models through the Lens of Recency and Over-smoothingcited by 18
  12. 2024Understanding Heterophily for Graph Neural Networkscited by 15
37 more
  1. 2023Optimal Inference in Contextual Stochastic Block Modelscited by 12
  2. 2024Joint Graph Rewiring and Feature Denoising via Spectral Resonancecited by 12
  3. 2023Graph Convolutions Enrich the Self-Attention in Transformers!cited by 11
  4. 2024Feature Distribution on Graph Topology Mediates the Effect of Graph Convolution: Homophily Perspectivecited by 9
  5. 2024Sign is Not a Remedy: Multiset-to-Multiset Message Passing for Learning on Heterophilic Graphscited by 8
  6. 2023Centered Self-Attention Layerscited by 7
  7. 2024Graph Neural Networks Do Not Always Oversmoothcited by 7
  8. 2025Residual connections provably mitigate oversmoothing in graph neural networkscited by 7
  9. 2026Query-Aware Flow Diffusion for Graph-Based RAG with Retrieval Guaranteescited by 7
  10. 2025Are We Measuring Oversmoothing in Graph Neural Networks Correctly?cited by 6
  11. 2023Principles for Initialization and Architecture Selection in Graph Neural Networks with ReLU Activationscited by 3
  12. 2024Taming Gradient Oversmoothing and Expansion in Graph Neural Networkscited by 3
  13. 2024Improving Graph Neural Networks by Learning Continuous Edge Directionscited by 3
  14. 2025The Oversmoothing Fallacy: A Misguided Narrative in GNN Researchcited by 3
  15. 2024Analysis of Corrected Graph Convolutionscited by 2
  16. 2024Graph Attention is Not Always Beneficial: A Theoretical Analysis of Graph Attention Mechanisms via Contextual Stochastic Block Modelscited by 2
  17. 2025Resolving Oversmoothing with Opinion Dissensuscited by 2
  18. 2025A Signed Graph Approach to Understanding and Mitigating Oversmoothing in GNNscited by 2
  19. 2025AGTCNet: A Graph-Temporal Approach for Principled Motor Imagery EEG Classificationcited by 2
  20. 2026Gaussian Process Limit Reveals Structural Benefits of Graph Transformerscited by 2
  21. 2023Degree-based stratification of nodes in Graph Neural Networkscited by 1
  22. 2024On provable privacy vulnerabilities of graph representationscited by 1
  23. 2024Sharp Bounds for Poly-GNNs and the Effect of Graph Noisecited by 1
  24. 2024Mixture of Scope Experts at Test: Generalizing Deeper Graph Neural Networks with Shallow Variantscited by 1
  25. 2024RL-SPH: Learning to Achieve Feasible Solutions for Integer Linear Programscited by 1
  26. 2023Understanding Community Bias Amplification in Graph Representation Learningcited by 0
  27. 2024Rethinking the Graph Polynomial Filter via Positive and Negative Coupling Analysiscited by 0
  28. 2024Learning to Control the Smoothness of Graph Convolutional Network Featurescited by 0
  29. 2024Optimal Exact Recovery in Semi-Supervised Learning: A Study of Spectral Methods and Graph Convolutional Networkscited by 0
  30. 2025Chordless Structure: A Pathway to Simple and Expressive GNNscited by 0
  31. 2025Exact Generalisation Error Exposes Benchmarks Skew Graph Neural Networks Success (or Failure)cited by 0
  32. 2025Domain-Decomposed Graph Neural Network Surrogate Modeling for Ice Sheetscited by 0
  33. 2026Coden: Efficient Temporal Graph Neural Networks for Continuous Predictioncited by 0
  34. 2026Transductive Generalization via Optimal Transport and Its Application to Graph Node Classificationcited by 0
  35. 2026Latent-Hysteresis Graph ODEs: Modeling Coupled Topology-Feature Evolution via Continuous Phase Transitionscited by 0
  36. 2026The Value of Depth in Message Passing on Sparse Graphs: A Kesten-Stigum Dichotomycited by 0
  37. 2026Exploring Oversmoothing with Householder Matricescited by 0