# Residual Connections and Normalization Can Provably Prevent Oversmoothing in GNNs

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

## Key facts

- Cited by 34 papers in the map (data through 14 Oct 2026).
- Builds on 48 of its 59 references that are in the map.
- First posted on arXiv 5 Jun 2024.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://mlsanity.com/paper/1502.03167/) (2015)
- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Layer Normalization](https://mlsanity.com/paper/1607.06450/) (2016)
- [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)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Modeling Relational Data with Graph Convolutional Networks](https://mlsanity.com/paper/1703.06103/) (2017)
- [Instance Normalization: The Missing Ingredient for Fast Stylization](https://mlsanity.com/paper/1607.08022/) (2016)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [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)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Simple and Deep Graph Convolutional Networks](https://mlsanity.com/paper/2007.02133/) (2020)
- [Geom-GCN: Geometric Graph Convolutional Networks](https://mlsanity.com/paper/2002.05287/) (2020)
- [Convolutional Networks on Graphs for Learning Molecular Fingerprints](https://mlsanity.com/paper/1509.09292/) (2015)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Benchmarking Graph Neural Networks](https://mlsanity.com/paper/2003.00982/) (2020)
- [Interaction Networks for Learning about Objects, Relations and Physics](https://mlsanity.com/paper/1612.00222/) (2016)
- [Graph Neural Networks in Recommender Systems: A Survey](https://mlsanity.com/paper/2011.02260/) (2020)
- [Attention is Not All You Need: Pure Attention Loses Rank Doubly Exponentially with Depth](https://mlsanity.com/paper/2103.03404/) (2021)
- [Graph Neural Networks with Learnable Structural and Positional Representations](https://mlsanity.com/paper/2110.07875/) (2021)
- [PairNorm: Tackling Oversmoothing in GNNs](https://mlsanity.com/paper/1909.12223/) (2019)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [A Note on Over-Smoothing for Graph Neural Networks](https://mlsanity.com/paper/2006.13318/) (2020)

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

- [Dynamic metastability in the self-attention model](https://mlsanity.com/paper/2410.06833/) (2024)
- [On Vanishing Gradients, Over-Smoothing, and Over-Squashing in GNNs: Bridging Recurrent and Graph Learning](https://mlsanity.com/paper/2502.10818/) (2025)
- [Measure-to-measure interpolation using Transformers](https://mlsanity.com/paper/2411.04551/) (2024)
- [Multistability of Self-Attention Dynamics in Transformers](https://mlsanity.com/paper/2511.11553/) (2025)
- [Residual connections provably mitigate oversmoothing in graph neural networks](https://mlsanity.com/paper/2501.00762/) (2025)
- [Deeper with Riemannian Geometry: Overcoming Oversmoothing and Oversquashing for Graph Foundation Models](https://mlsanity.com/paper/2510.17457/) (2025)
- [Preventing Representational Rank Collapse in MPNNs by Splitting the Computational Graph](https://mlsanity.com/paper/2409.11504/) (2024)
- [Are We Measuring Oversmoothing in Graph Neural Networks Correctly?](https://mlsanity.com/paper/2502.04591/) (2025)
- [On the Convergence of Gradient Descent on Learning Transformers with Residual Connections](https://mlsanity.com/paper/2506.05249/) (2025)
- [On the Necessity of Learnable Sheaf Laplacians](https://mlsanity.com/paper/2603.05395/) (2026)
- [Simplifying the Theory on Over-Smoothing](https://mlsanity.com/paper/2407.11876/) (2024)
- [A Signed Graph Approach to Understanding and Mitigating Oversmoothing in GNNs](https://mlsanity.com/paper/2502.11394/) (2025)
- [Early-Exit Graph Neural Networks](https://mlsanity.com/paper/2505.18088/) (2025)
- [Position: Don't be Afraid of Over-Smoothing And Over-Squashing](https://mlsanity.com/paper/2601.07419/) (2026)
- [Beyond ReLU: Bifurcation, Oversmoothing, and Topological Priors](https://mlsanity.com/paper/2602.15634/) (2026)
- [Convergence of Gradient Descent for General Neural Network Architectures Beyond the NTK Regime](https://mlsanity.com/paper/2606.23364/) (2026)
- [Data Uniformity Improves Training Efficiency and More, with a Convergence Framework Beyond the NTK Regime](https://mlsanity.com/paper/2506.24120/) (2025)
- [GEDAN: Learning the Edit Costs for Graph Edit Distance](https://mlsanity.com/paper/2508.03111/) (2025)
- [Agent Harness Distillation: Inference-Time Harness Extraction and Exploitation in Autonomous Multi-Agent Systems](https://mlsanity.com/paper/2607.28147/) (2026)
- [Bridging Computational Social Science and Deep Learning: Cultural Dissemination-Inspired Graph Neural Networks](https://mlsanity.com/paper/2509.19084/) (2025)
- [Model Metamers Reveal Invariances in Graph Neural Networks](https://mlsanity.com/paper/2510.17378/) (2025)
- [Solving Oversmoothing in GNNs via Nonlocal Message Passing: Algebraic Smoothing and Depth Scalability](https://mlsanity.com/paper/2512.08475/) (2025)
- [CLARGA: Multimodal Graph Representation Learning over Arbitrary Sets of Modalities](https://mlsanity.com/paper/2512.11901/) (2025)
- [ParaFormer: A Generalized PageRank Graph Transformer for Graph Representation Learning](https://mlsanity.com/paper/2512.14619/) (2025)
- [Graph Learning Should Move Beyond Restrictive Views of Spectral and Message-Passing GNNs](https://mlsanity.com/paper/2602.10031/) (2026)
- [Local Message-Passing for Discrete Graph Generation](https://mlsanity.com/paper/2603.08825/) (2026)
- [GOMA: Toward Structure-Driven Multimodal Alignment from a Graph Signal Smoothing Perspective](https://mlsanity.com/paper/2605.15723/) (2026)
- [Analogies between Transformer Layers and Power Method](https://mlsanity.com/paper/2605.25619/) (2026)
- [Learning Graphs through Continuous Information Entropy Fields](https://mlsanity.com/paper/2606.22895/) (2026)
- [A Spectral Theory of Normalized Corrected GNN Propagation](https://mlsanity.com/paper/2606.23572/) (2026)

## Abstract (arXiv)

Residual connections and normalization layers have become standard design choices for graph neural networks (GNNs), and were proposed as solutions to the mitigate the oversmoothing problem in GNNs. However, how exactly these methods help alleviate the oversmoothing problem from a theoretical perspective is not well understood. In this work, we provide a formal and precise characterization of (linearized) GNNs with residual connections and normalization layers. We establish that (a) for residual connections, the incorporation of the initial features at each layer can prevent the signal from becoming too smooth, and determines the subspace of possible node representations; (b) batch normalization prevents a complete collapse of the output embedding space to a one-dimensional subspace through the individual rescaling of each column of the feature matrix. This results in the convergence of node representations to the top-k eigenspace of the message-passing operator; (c) moreover, we show that the centering step of a normalization layer -- which can be understood as a projection -- alters the graph signal in message-passing in such a way that relevant information can become harder to extract. We therefore introduce a novel, principled normalization layer called GraphNormv2 in which the centering step is learned such that it does not distort the original graph signal in an undesirable way. Experimental results confirm the effectiveness of our method.