# On Vanishing Gradients, Over-Smoothing, and Over-Squashing in GNNs: Bridging Recurrent and Graph Learning

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

## Key facts

- Cited by 43 papers in the map (data through 14 Oct 2026).
- Builds on 83 of its 114 references that are in the map.
- First posted on arXiv 15 Feb 2025.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Mamba: Linear-Time Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2312.00752/) (2023)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Ordinary Differential Equations](https://mlsanity.com/paper/1806.07366/) (2018)
- [Efficiently Modeling Long Sequences with Structured State Spaces](https://mlsanity.com/paper/2111.00396/) (2021)
- [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)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [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)
- [Exact solutions to the nonlinear dynamics of learning in deep linear neural networks](https://mlsanity.com/paper/1312.6120/) (2013)
- [Recipe for a General, Powerful, Scalable Graph Transformer](https://mlsanity.com/paper/2205.12454/) (2022)
- [A Generalization of Transformer Networks to Graphs](https://mlsanity.com/paper/2012.09699/) (2020)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [DeepGCNs: Can GCNs Go as Deep as CNNs?](https://mlsanity.com/paper/1904.03751/) (2019)
- [Masked Label Prediction: Unified Message Passing Model for Semi-Supervised Classification](https://mlsanity.com/paper/2009.03509/) (2020)
- [Understanding over-squashing and bottlenecks on graphs via curvature](https://mlsanity.com/paper/2111.14522/) (2021)
- [Rethinking Graph Transformers with Spectral Attention](https://mlsanity.com/paper/2106.03893/) (2021)
- [Diffusion Improves Graph Learning](https://mlsanity.com/paper/1911.05485/) (2019)
- [Resurrecting Recurrent Neural Networks for Long Sequences](https://mlsanity.com/paper/2303.06349/) (2023)
- [Hyperbolic Graph Convolutional Neural Networks](https://mlsanity.com/paper/1910.12933/) (2019)
- [Residual Gated Graph ConvNets](https://mlsanity.com/paper/1711.07553/) (2017)
- [A critical look at the evaluation of GNNs under heterophily: Are we really making progress?](https://mlsanity.com/paper/2302.11640/) (2023)
- [xLSTM: Extended Long Short-Term Memory](https://mlsanity.com/paper/2405.04517/) (2024)
- [Unitary Evolution Recurrent Neural Networks](https://mlsanity.com/paper/1511.06464/) (2015)
- [Long Range Graph Benchmark](https://mlsanity.com/paper/2206.08164/) (2022)
- [Exponential expressivity in deep neural networks through transient chaos](https://mlsanity.com/paper/1606.05340/) (2016)

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

- [Why do LLMs attend to the first token?](https://mlsanity.com/paper/2504.02732/) (2025)
- [Attention Sinks and Compression Valleys in LLMs are Two Sides of the Same Coin](https://mlsanity.com/paper/2510.06477/) (2025)
- [A Mechanistic Analysis of Looped Reasoning Language Models](https://mlsanity.com/paper/2604.11791/) (2026)
- [Long-Context Generalization with Sparse Attention](https://mlsanity.com/paper/2506.16640/) (2025)
- [Towards Quantifying Long-Range Interactions in Graph Machine Learning: a Large Graph Dataset and a Measurement](https://mlsanity.com/paper/2503.09008/) (2025)
- [Oversmoothing, Oversquashing, Heterophily, Long-Range, and more: Demystifying Common Beliefs in Graph Machine Learning](https://mlsanity.com/paper/2505.15547/) (2025)
- [Return of ChebNet: Understanding and Improving an Overlooked GNN on Long Range Tasks](https://mlsanity.com/paper/2506.07624/) (2025)
- [On Measuring Long-Range Interactions in Graph Neural Networks](https://mlsanity.com/paper/2506.05971/) (2025)
- [Message-Passing State-Space Models: Improving Graph Learning with Modern Sequence Modeling](https://mlsanity.com/paper/2505.18728/) (2025)
- [Can You Hear Me Now? A Benchmark for Long-Range Graph Propagation](https://mlsanity.com/paper/2512.17762/) (2025)
- [Deeper with Riemannian Geometry: Overcoming Oversmoothing and Oversquashing for Graph Foundation Models](https://mlsanity.com/paper/2510.17457/) (2025)
- [Improving Long-Range Interactions in Graph Neural Simulators via Hamiltonian Dynamics](https://mlsanity.com/paper/2511.08185/) (2025)
- [Backward Oversmoothing: why is it hard to train deep Graph Neural Networks?](https://mlsanity.com/paper/2505.16736/) (2025)
- [The Oversmoothing Fallacy: A Misguided Narrative in GNN Research](https://mlsanity.com/paper/2506.04653/) (2025)
- [AdaSplash-2: Faster Differentiable Sparse Attention](https://mlsanity.com/paper/2604.15180/) (2026)
- [Early-Exit Graph Neural Networks](https://mlsanity.com/paper/2505.18088/) (2025)
- [pLSTM: parallelizable Linear Source Transition Mark networks](https://mlsanity.com/paper/2506.11997/) (2025)
- [Stochastic Parroting in Temporal Attention -- Regulating the Diagonal Sink](https://mlsanity.com/paper/2602.10956/) (2026)
- [Beyond ReLU: Bifurcation, Oversmoothing, and Topological Priors](https://mlsanity.com/paper/2602.15634/) (2026)
- [Learning Multi-Agent Coordination via Sheaf-ADMM](https://mlsanity.com/paper/2605.31005/) (2026)
- [Directed Acyclic Graph Convolutional Networks](https://mlsanity.com/paper/2506.12218/) (2025)
- [TANGO: Graph Neural Dynamics via Learned Energy and Tangential Flows](https://mlsanity.com/paper/2508.05070/) (2025)
- [gLSTM: Mitigating Over-Squashing by Increasing Storage Capacity](https://mlsanity.com/paper/2510.08450/) (2025)
- [Neuronal Group Communication for Efficient Neural representation](https://mlsanity.com/paper/2510.16851/) (2025)
- [Analysis of Dirichlet Energies as Over-smoothing Measures](https://mlsanity.com/paper/2512.09890/) (2025)
- [A General Neural Backbone for Mixed-Integer Linear Optimization via Dual Attention](https://mlsanity.com/paper/2601.04509/) (2026)
- [Effective Resistance Rewiring: A Simple Topological Correction for Over-Squashing](https://mlsanity.com/paper/2603.11944/) (2026)
- [From Message-Passing to Linearized Graph Sequence Models](https://mlsanity.com/paper/2605.12358/) (2026)
- [Quantitative Error Feedback for Quantization Noise Reduction of Filtering over Graphs](https://mlsanity.com/paper/2506.01404/) (2025)
- [Chi-Geometry: A Library for Benchmarking Chirality Prediction of GNNs](https://mlsanity.com/paper/2508.09097/) (2025)

## Abstract (arXiv)

Graph Neural Networks (GNNs) are models that leverage the graph structure to transmit information between nodes, typically through the message-passing operation. While widely successful, this approach is well known to suffer from the over-smoothing and over-squashing phenomena, which result in representational collapse as the number of layers increases and insensitivity to the information contained at distant and poorly connected nodes, respectively. In this paper, we present a unified view of these problems through the lens of vanishing gradients, using ideas from linear control theory for our analysis. We propose an interpretation of GNNs as recurrent models and empirically demonstrate that a simple state-space formulation of a GNN effectively alleviates over-smoothing and over-squashing at no extra trainable parameter cost. Further, we show theoretically and empirically that (i) GNNs are by design prone to extreme gradient vanishing even after a few layers; (ii) Over-smoothing is directly related to the mechanism causing vanishing gradients; (iii) Over-squashing is most easily alleviated by a combination of graph rewiring and vanishing gradient mitigation. We believe our work will help bridge the gap between the recurrent and graph neural network literature and will unlock the design of new deep and performant GNNs.