# Oversquashing in GNNs through the lens of information contraction and graph expansion

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

## Key facts

- Cited by 53 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 62 references that are in the map.
- First posted on arXiv 6 Aug 2022.

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

- [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)
- [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)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Representation Learning on Graphs with Jumping Knowledge Networks](https://mlsanity.com/paper/1806.03536/) (2018)
- [DropEdge: Towards Deep Graph Convolutional Networks on Node Classification](https://mlsanity.com/paper/1907.10903/) (2019)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [Understanding over-squashing and bottlenecks on graphs via curvature](https://mlsanity.com/paper/2111.14522/) (2021)
- [Diffusion Improves Graph Learning](https://mlsanity.com/paper/1911.05485/) (2019)
- [Long Range Graph Benchmark](https://mlsanity.com/paper/2206.08164/) (2022)
- [Generalization and Representational Limits of Graph Neural Networks](https://mlsanity.com/paper/2002.06157/) (2020)
- [Discriminative Embeddings of Latent Variable Models for Structured Data](https://mlsanity.com/paper/1603.05629/) (2016)
- [DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networks](https://mlsanity.com/paper/2111.06283/) (2021)
- [Expanders via Local Edge Flips](https://mlsanity.com/paper/1510.07768/) (2015)
- [The flip Markov chain for connected regular graphs](https://mlsanity.com/paper/1701.03856/) (2017)

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

- [On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology](https://mlsanity.com/paper/2302.02941/) (2023)
- [FoSR: First-order spectral rewiring for addressing oversquashing in GNNs](https://mlsanity.com/paper/2210.11790/) (2022)
- [Revisiting Over-smoothing and Over-squashing Using Ollivier-Ricci Curvature](https://mlsanity.com/paper/2211.15779/) (2022)
- [Understanding Oversquashing in GNNs through the Lens of Effective Resistance](https://mlsanity.com/paper/2302.06835/) (2023)
- [Expander Graph Propagation](https://mlsanity.com/paper/2210.02997/) (2022)
- [Locality-Aware Graph-Rewiring in GNNs](https://mlsanity.com/paper/2310.01668/) (2023)
- [Mitigating Over-Smoothing and Over-Squashing using Augmentations of Forman-Ricci Curvature](https://mlsanity.com/paper/2309.09384/) (2023)
- [Probabilistically Rewired Message-Passing Neural Networks](https://mlsanity.com/paper/2310.02156/) (2023)
- [Adaptive Message Passing: A General Framework to Mitigate Oversmoothing, Oversquashing, and Underreaching](https://mlsanity.com/paper/2312.16560/) (2023)
- [Spectral Graph Pruning Against Over-Squashing and Over-Smoothing](https://mlsanity.com/paper/2404.04612/) (2024)
- [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)
- [Neurosymbolic AI for Reasoning over Knowledge Graphs: A Survey](https://mlsanity.com/paper/2302.07200/) (2023)
- [Cayley Graph Propagation](https://mlsanity.com/paper/2410.03424/) (2024)
- [Oversmoothing, Oversquashing, Heterophily, Long-Range, and more: Demystifying Common Beliefs in Graph Machine Learning](https://mlsanity.com/paper/2505.15547/) (2025)
- [Probabilistic Graph Rewiring via Virtual Nodes](https://mlsanity.com/paper/2405.17311/) (2024)
- [GNNs Getting ComFy: Community and Feature Similarity Guided Rewiring](https://mlsanity.com/paper/2502.04891/) (2025)
- [On the Ability of Graph Neural Networks to Model Interactions Between Vertices](https://mlsanity.com/paper/2211.16494/) (2022)
- [Joint Graph Rewiring and Feature Denoising via Spectral Resonance](https://mlsanity.com/paper/2408.07191/) (2024)
- [PANDA: Expanded Width-Aware Message Passing Beyond Rewiring](https://mlsanity.com/paper/2406.03671/) (2024)
- [Graph Rewiring in GNNs to Mitigate Over-Squashing and Over-Smoothing: A Survey](https://mlsanity.com/paper/2411.17429/) (2024)
- [Deeper with Riemannian Geometry: Overcoming Oversmoothing and Oversquashing for Graph Foundation Models](https://mlsanity.com/paper/2510.17457/) (2025)
- [The Graph Lottery Ticket Hypothesis: Finding Sparse, Informative Graph Structure](https://mlsanity.com/paper/2312.04762/) (2023)
- [Design Your Own Universe: A Physics-Informed Agnostic Method for Enhancing Graph Neural Networks](https://mlsanity.com/paper/2401.14580/) (2024)
- [Deep Equilibrium Algorithmic Reasoning](https://mlsanity.com/paper/2410.15059/) (2024)
- [PIORF: Physics-Informed Ollivier-Ricci Flow for Long-Range Interactions in Mesh Graph Neural Networks](https://mlsanity.com/paper/2504.04052/) (2025)
- [Graph Unitary Message Passing](https://mlsanity.com/paper/2403.11199/) (2024)
- [Structural Group Unfairness: Measurement and Mitigation by means of the Effective Resistance](https://mlsanity.com/paper/2305.03223/) (2023)
- [Higher-Order Expander Graph Propagation](https://mlsanity.com/paper/2311.07966/) (2023)
- [Dynamic Triangulation-Based Graph Rewiring for Graph Neural Networks](https://mlsanity.com/paper/2508.19071/) (2025)

## Abstract (arXiv)

The quality of signal propagation in message-passing graph neural networks (GNNs) strongly influences their expressivity as has been observed in recent works. In particular, for prediction tasks relying on long-range interactions, recursive aggregation of node features can lead to an undesired phenomenon called "oversquashing". We present a framework for analyzing oversquashing based on information contraction. Our analysis is guided by a model of reliable computation due to von Neumann that lends a new insight into oversquashing as signal quenching in noisy computation graphs. Building on this, we propose a graph rewiring algorithm aimed at alleviating oversquashing. Our algorithm employs a random local edge flip primitive motivated by an expander graph construction. We compare the spectral expansion properties of our algorithm with that of an existing curvature-based non-local rewiring strategy. Synthetic experiments show that while our algorithm in general has a slower rate of expansion, it is overall computationally cheaper, preserves the node degrees exactly and never disconnects the graph.