# Leave Graphs Alone: Addressing Over-Squashing without Rewiring

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

## Key facts

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

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [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)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [Convolutional Networks on Graphs for Learning Molecular Fingerprints](https://mlsanity.com/paper/1509.09292/) (2015)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological View](https://mlsanity.com/paper/1909.03211/) (2019)
- [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)
- [Diffusion-Convolutional Neural Networks](https://mlsanity.com/paper/1511.02136/) (2015)
- [A Gentle Introduction to Deep Learning for Graphs](https://mlsanity.com/paper/1912.12693/) (2019)
- [Fast and Deep Graph Neural Networks](https://mlsanity.com/paper/1911.08941/) (2019)
- [Beyond Homophily with Graph Echo State Networks](https://mlsanity.com/paper/2210.15731/) (2022)

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

- [Adaptive Message Passing: A General Framework to Mitigate Oversmoothing, Oversquashing, and Underreaching](https://mlsanity.com/paper/2312.16560/) (2023)
- [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)
- [Oversmoothing, Oversquashing, Heterophily, Long-Range, and more: Demystifying Common Beliefs in Graph Machine Learning](https://mlsanity.com/paper/2505.15547/) (2025)
- [Correlation-aware Spatial-Temporal Graph Learning for Multivariate Time-series Anomaly Detection](https://mlsanity.com/paper/2307.08390/) (2023)
- [Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification](https://mlsanity.com/paper/2506.16110/) (2025)
- [Over-squashing in Spatiotemporal Graph Neural Networks](https://mlsanity.com/paper/2506.15507/) (2025)
- [Foundations and Frontiers of Graph Learning Theory](https://mlsanity.com/paper/2407.03125/) (2024)
- [An Empirical Evaluation of Rewiring Approaches in Graph Neural Networks](https://mlsanity.com/paper/2305.19717/) (2023)
- [Performance Heterogeneity in Graph Neural Networks: Lessons for Architecture Design and Preprocessing](https://mlsanity.com/paper/2503.00547/) (2025)
- [Conditional Shift-Robust Conformal Prediction for Graph Neural Network](https://mlsanity.com/paper/2405.11968/) (2024)
- [Adaptive Graph Rewiring to Mitigate Over-Squashing in Mesh-Based GNNs for Fluid Dynamics Simulations](https://mlsanity.com/paper/2511.12709/) (2025)
- [Probing Graph Neural Network Activation Patterns Through Graph Topology](https://mlsanity.com/paper/2602.21092/) (2026)
- [Reservoir-Based Graph Convolutional Networks](https://mlsanity.com/paper/2603.24131/) (2026)

## Abstract (arXiv)

Recent works have investigated the role of graph bottlenecks in preventing long-range information propagation in message-passing graph neural networks, causing the so-called `over-squashing' phenomenon. As a remedy, graph rewiring mechanisms have been proposed as preprocessing steps. Graph Echo State Networks (GESNs) are a reservoir computing model for graphs, where node embeddings are recursively computed by an untrained message-passing function. In this paper, we show that GESNs can achieve a significantly better accuracy on six heterophilic node classification tasks without altering the graph connectivity, thus suggesting a different route for addressing the over-squashing problem.