# Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 53 references that are in the map.
- First posted on arXiv 19 Jun 2025.

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

- [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)
- [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)
- [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)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [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)
- [Rethinking Graph Transformers with Spectral Attention](https://mlsanity.com/paper/2106.03893/) (2021)
- [Graph networks as learnable physics engines for inference and control](https://mlsanity.com/paper/1806.01242/) (2018)
- [Revisiting Heterophily For Graph Neural Networks](https://mlsanity.com/paper/2210.07606/) (2022)
- [On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology](https://mlsanity.com/paper/2302.02941/) (2023)
- [Learning to Drop: Robust Graph Neural Network via Topological Denoising](https://mlsanity.com/paper/2011.07057/) (2020)
- [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)
- [Cooperative Graph Neural Networks](https://mlsanity.com/paper/2310.01267/) (2023)
- [Probabilistically Rewired Message-Passing Neural Networks](https://mlsanity.com/paper/2310.02156/) (2023)
- [Spectral Graph Pruning Against Over-Squashing and Over-Smoothing](https://mlsanity.com/paper/2404.04612/) (2024)
- [ResNorm: Tackling Long-tailed Degree Distribution Issue in Graph Neural Networks via Normalization](https://mlsanity.com/paper/2206.08181/) (2022)
- [Leave Graphs Alone: Addressing Over-Squashing without Rewiring](https://mlsanity.com/paper/2212.06538/) (2022)
- [Sign is Not a Remedy: Multiset-to-Multiset Message Passing for Learning on Heterophilic Graphs](https://mlsanity.com/paper/2405.20652/) (2024)

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

- [Asynchronous Message Passing for Addressing Oversquashing in Graph Neural Networks](https://mlsanity.com/paper/2509.06777/) (2025)
- [Cross-attentive Cohesive Subgraph Embedding to Mitigate Oversquashing in GNNs](https://mlsanity.com/paper/2603.27529/) (2026)
- [Graph Rewiring in GNNs to Mitigate Over-Squashing and Over-Smoothing: A Survey](https://mlsanity.com/paper/2605.00951/) (2026)
- [MLGIB: Multi-Label Graph Information Bottleneck for Expressive and Robust Message Passing](https://mlsanity.com/paper/2605.13126/) (2026)
- [Spectral Flow Certificates for Depth-Aware Long-Range Propagation in Graph Neural Networks](https://mlsanity.com/paper/2607.21607/) (2026)
- [Pair-Centric Graph Rewiring for Over-Squashing via Optimal Transport-Guided Communication Alignment](https://mlsanity.com/paper/2608.10619/) (2026)
- [Finite-Time Node Separation in Recurrent Graph Neural Networks with Persistent Gaussian Perturbations](https://mlsanity.com/paper/2609.13920/) (2026)
- [Mitigating Over-squashing without Rewiring: A Sheaf Effective Resistance Perspective](https://mlsanity.com/paper/2610.04157/) (2026)

## Abstract (arXiv)

The message-passing paradigm of Graph Neural Networks often struggles with exchanging information across distant nodes typically due to structural bottlenecks in certain graph regions, a limitation known as textitover-squashing. To reduce such bottlenecks, textitgraph rewiring, which modifies graph topology, has been widely used. However, existing graph rewiring techniques often overlook the need to preserve critical properties of the original graph, e.g., textitspectral properties. Moreover, many approaches rely on increasing edge count to improve connectivity, which introduces significant computational overhead and exacerbates the risk of over-smoothing. In this paper, we propose a novel graph rewiring method that leverages textitspectrum-preserving graph textitsparsification, for mitigating over-squashing. Our method generates graphs with enhanced connectivity while maintaining sparsity and largely preserving the original graph spectrum, effectively balancing structural bottleneck reduction and graph property preservation. Experimental results validate the effectiveness of our approach, demonstrating its superiority over strong baseline methods in classification accuracy and retention of the Laplacian spectrum.