# Not too little, not too much: a theoretical analysis of graph (over)smoothing

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

## Key facts

- Cited by 106 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 66 references that are in the map.
- First posted on arXiv 24 May 2022.

## Builds on (most cited first, 27 of 27)

- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [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)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges](https://mlsanity.com/paper/2104.13478/) (2021)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [Geometric deep learning: going beyond Euclidean data](https://mlsanity.com/paper/1611.08097/) (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)
- [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)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [PairNorm: Tackling Oversmoothing in GNNs](https://mlsanity.com/paper/1909.12223/) (2019)
- [Molecular Graph Convolutions: Moving Beyond Fingerprints](https://mlsanity.com/paper/1603.00856/) (2016)
- [Neural Sheaf Diffusion: A Topological Perspective on Heterophily and Oversmoothing in GNNs](https://mlsanity.com/paper/2202.04579/) (2022)
- [Graph Neural Networks with Heterophily](https://mlsanity.com/paper/2009.13566/) (2020)
- [What graph neural networks cannot learn: depth vs width](https://mlsanity.com/paper/1907.03199/) (2019)
- [Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networks](https://mlsanity.com/paper/2102.06462/) (2021)
- [Knowledge-aware Graph Neural Networks with Label Smoothness Regularization for Recommender Systems](https://mlsanity.com/paper/1905.04413/) (2019)
- [Transferability of Spectral Graph Convolutional Neural Networks](https://mlsanity.com/paper/1907.12972/) (2019)
- [Convergence and Stability of Graph Convolutional Networks on Large Random Graphs](https://mlsanity.com/paper/2006.01868/) (2020)
- [Tackling Over-Smoothing for General Graph Convolutional Networks](https://mlsanity.com/paper/2008.09864/) (2020)
- [Policy-GNN: Aggregation Optimization for Graph Neural Networks](https://mlsanity.com/paper/2006.15097/) (2020)
- [Random walks and diffusion on networks](https://mlsanity.com/paper/1612.03281/) (2016)
- [On the Universality of Graph Neural Networks on Large Random Graphs](https://mlsanity.com/paper/2105.13099/) (2021)
- [On Node Features for Graph Neural Networks](https://mlsanity.com/paper/1911.08795/) (2019)

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

- [A Survey on Oversmoothing in Graph Neural Networks](https://mlsanity.com/paper/2303.10993/) (2023)
- [Why do LLMs attend to the first token?](https://mlsanity.com/paper/2504.02732/) (2025)
- [A Non-Asymptotic Analysis of Oversmoothing in Graph Neural Networks](https://mlsanity.com/paper/2212.10701/) (2022)
- [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)
- [Generalized Graph Prompt: Toward a Unification of Pre-Training and Downstream Tasks on Graphs](https://mlsanity.com/paper/2311.15317/) (2023)
- [Residual Connections and Normalization Can Provably Prevent Oversmoothing in GNNs](https://mlsanity.com/paper/2406.02997/) (2024)
- [Spectral Graph Pruning Against Over-Squashing and Over-Smoothing](https://mlsanity.com/paper/2404.04612/) (2024)
- [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)
- [Rank Collapse Causes Over-Smoothing and Over-Correlation in Graph Neural Networks](https://mlsanity.com/paper/2308.16800/) (2023)
- [Subgraph Pooling: Tackling Negative Transfer on Graphs](https://mlsanity.com/paper/2402.08907/) (2024)
- [Generalization Bounds for Message Passing Networks on Mixture of Graphons](https://mlsanity.com/paper/2404.03473/) (2024)
- [Unsupervised Optimal Power Flow Using Graph Neural Networks](https://mlsanity.com/paper/2210.09277/) (2022)
- [Homophily modulates double descent generalization in graph convolution networks](https://mlsanity.com/paper/2212.13069/) (2022)
- [Optimality of Message-Passing Architectures for Sparse Graphs](https://mlsanity.com/paper/2305.10391/) (2023)
- [Half-Hop: A graph upsampling approach for slowing down message passing](https://mlsanity.com/paper/2308.09198/) (2023)
- [What Can We Learn from State Space Models for Machine Learning on Graphs?](https://mlsanity.com/paper/2406.05815/) (2024)
- [Contrasformer: A Brain Network Contrastive Transformer for Neurodegenerative Condition Identification](https://mlsanity.com/paper/2409.10944/) (2024)
- [Question-guided Knowledge Graph Re-scoring and Injection for Knowledge Graph Question Answering](https://mlsanity.com/paper/2410.01401/) (2024)
- [GNNs Getting ComFy: Community and Feature Similarity Guided Rewiring](https://mlsanity.com/paper/2502.04891/) (2025)
- [What functions can Graph Neural Networks compute on random graphs? The role of Positional Encoding](https://mlsanity.com/paper/2305.14814/) (2023)
- [Graph Convolutions Enrich the Self-Attention in Transformers!](https://mlsanity.com/paper/2312.04234/) (2023)
- [Convergence of Message Passing Graph Neural Networks with Generic Aggregation On Large Random Graphs](https://mlsanity.com/paper/2304.11140/) (2023)
- [Graph Coarsening with Message-Passing Guarantees](https://mlsanity.com/paper/2405.18127/) (2024)
- [Analysis of Convolutions, Non-linearity and Depth in Graph Neural Networks using Neural Tangent Kernel](https://mlsanity.com/paper/2210.09809/) (2022)
- [Networked Inequality: Preferential Attachment Bias in Graph Neural Network Link Prediction](https://mlsanity.com/paper/2309.17417/) (2023)
- [Sign is Not a Remedy: Multiset-to-Multiset Message Passing for Learning on Heterophilic Graphs](https://mlsanity.com/paper/2405.20652/) (2024)
- [Towards Adaptive Neighborhood for Advancing Temporal Interaction Graph Modeling](https://mlsanity.com/paper/2406.11891/) (2024)
- [Unitary convolutions for learning on graphs and groups](https://mlsanity.com/paper/2410.05499/) (2024)

## Abstract (arXiv)

We analyze graph smoothing with mean aggregation, where each node successively receives the average of the features of its neighbors. Indeed, it has quickly been observed that Graph Neural Networks (GNNs), which generally follow some variant of Message-Passing (MP) with repeated aggregation, may be subject to the oversmoothing phenomenon: by performing too many rounds of MP, the node features tend to converge to a non-informative limit. In the case of mean aggregation, for connected graphs, the node features become constant across the whole graph. At the other end of the spectrum, it is intuitively obvious that some MP rounds are necessary, but existing analyses do not exhibit both phenomena at once: beneficial ``finite'' smoothing and oversmoothing in the limit. In this paper, we consider simplified linear GNNs, and rigorously analyze two examples for which a finite number of mean aggregation steps provably improves the learning performance, before oversmoothing kicks in. We consider a latent space random graph model, where node features are partial observations of the latent variables and the graph contains pairwise relationships between them. We show that graph smoothing restores some of the lost information, up to a certain point, by two phenomenon: graph smoothing shrinks non-principal directions in the data faster than principal ones, which is useful for regression, and shrinks nodes within communities faster than they collapse together, which improves classification.