# Exposition on over-squashing problem on GNNs: Current Methods, Benchmarks and Challenges

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- Builds on 72 of its 134 references that are in the map.
- First posted on arXiv 13 Nov 2023.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [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)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Modeling Relational Data with Graph Convolutional Networks](https://mlsanity.com/paper/1703.06103/) (2017)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Representation Learning on Graphs with Jumping Knowledge Networks](https://mlsanity.com/paper/1806.03536/) (2018)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Recipe for a General, Powerful, Scalable Graph Transformer](https://mlsanity.com/paper/2205.12454/) (2022)
- [Benchmarking Graph Neural Networks](https://mlsanity.com/paper/2003.00982/) (2020)
- [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)
- [Hypergraph Neural Networks](https://mlsanity.com/paper/1809.09401/) (2018)
- [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)
- [Hyperbolic Graph Convolutional Neural Networks](https://mlsanity.com/paper/1910.12933/) (2019)
- [Explainability in Graph Neural Networks: A Taxonomic Survey](https://mlsanity.com/paper/2012.15445/) (2020)
- [Long Range Graph Benchmark](https://mlsanity.com/paper/2206.08164/) (2022)
- [GRAND: Graph Neural Diffusion](https://mlsanity.com/paper/2106.10934/) (2021)
- [A Note on Over-Smoothing for Graph Neural Networks](https://mlsanity.com/paper/2006.13318/) (2020)
- [A Survey on Oversmoothing in Graph Neural Networks](https://mlsanity.com/paper/2303.10993/) (2023)
- [Weisfeiler and Lehman Go Cellular: CW Networks](https://mlsanity.com/paper/2106.12575/) (2021)
- [NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification](https://mlsanity.com/paper/2306.08385/) (2023)
- [Structure-Aware Transformer for Graph Representation Learning](https://mlsanity.com/paper/2202.03036/) (2022)
- [Self-Supervised Learning of Graph Neural Networks: A Unified Review](https://mlsanity.com/paper/2102.10757/) (2021)

## Built on by (most cited first, 22 of 22)

- [On Vanishing Gradients, Over-Smoothing, and Over-Squashing in GNNs: Bridging Recurrent and Graph Learning](https://mlsanity.com/paper/2502.10818/) (2025)
- [On Oversquashing in Graph Neural Networks Through the Lens of Dynamical Systems](https://mlsanity.com/paper/2405.01009/) (2024)
- [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)
- [PANDA: Expanded Width-Aware Message Passing Beyond Rewiring](https://mlsanity.com/paper/2406.03671/) (2024)
- [Design Your Own Universe: A Physics-Informed Agnostic Method for Enhancing Graph Neural Networks](https://mlsanity.com/paper/2401.14580/) (2024)
- [PIORF: Physics-Informed Ollivier-Ricci Flow for Long-Range Interactions in Mesh Graph Neural Networks](https://mlsanity.com/paper/2504.04052/) (2025)
- [Improving Long-Range Interactions in Graph Neural Simulators via Hamiltonian Dynamics](https://mlsanity.com/paper/2511.08185/) (2025)
- [Foundations and Frontiers of Graph Learning Theory](https://mlsanity.com/paper/2407.03125/) (2024)
- [When Graph Neural Networks Meet Dynamic Mode Decomposition](https://mlsanity.com/paper/2410.05593/) (2024)
- [Implicit Hypergraph Neural Networks: A Stable Framework for Higher-Order Relational Learning with Provable Guarantees](https://mlsanity.com/paper/2508.09427/) (2025)
- [Are Graph Transformers Necessary? Efficient Long-Range Message Passing with Fractal Nodes in MPNNs](https://mlsanity.com/paper/2511.13010/) (2025)
- [Demystifying Topological Message-Passing with Relational Structures: A Case Study on Oversquashing in Simplicial Message-Passing](https://mlsanity.com/paper/2506.06582/) (2025)
- [Diffusing to the Top: Boost Graph Neural Networks with Minimal Hyperparameter Tuning](https://mlsanity.com/paper/2410.05697/) (2024)
- [TANGO: Graph Neural Dynamics via Learned Energy and Tangential Flows](https://mlsanity.com/paper/2508.05070/) (2025)
- [Graph Homophily Booster: Rethinking the Role of Discrete Features on Heterophilic Graphs](https://mlsanity.com/paper/2509.12530/) (2025)
- [Adaptive Graph Rewiring to Mitigate Over-Squashing in Mesh-Based GNNs for Fluid Dynamics Simulations](https://mlsanity.com/paper/2511.12709/) (2025)
- [Graph homophily booster: Reimagining the role of discrete features in heterophilic graph learning](https://mlsanity.com/paper/2602.07256/) (2026)
- [Information propagation dynamics in Deep Graph Networks](https://mlsanity.com/paper/2410.10464/) (2024)
- [Graph Pseudotime Analysis and Neural Stochastic Differential Equations for Analyzing Retinal Degeneration Dynamics and Beyond](https://mlsanity.com/paper/2502.06126/) (2025)
- [Schreier-Coset Graph Propagation](https://mlsanity.com/paper/2505.10392/) (2025)
- [S3GNN: Efficient Global Mixing and Local Message Passing for Long-Range Graph Learning](https://mlsanity.com/paper/2605.23467/) (2026)

## Abstract (arXiv)

Graph-based message-passing neural networks (MPNNs) have achieved remarkable success in both node and graph-level learning tasks. However, several identified problems, including over-smoothing (OSM), limited expressive power, and over-squashing (OSQ), still limit the performance of MPNNs. In particular, OSQ serves as the latest identified problem, where MPNNs gradually lose their learning accuracy when long-range dependencies between graph nodes are required. In this work, we provide an exposition on the OSQ problem by summarizing different formulations of OSQ from current literature, as well as the three different categories of approaches for addressing the OSQ problem. In addition, we also discuss the alignment between OSQ and expressive power and the trade-off between OSQ and OSM. Furthermore, we summarize the empirical methods leveraged from existing works to verify the efficiency of OSQ mitigation approaches, with illustrations of their computational complexities. Lastly, we list some open questions that are of interest for further exploration of the OSQ problem along with potential directions from the best of our knowledge.