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

2025/06/19 by Liang, Langzhang, Bu, Fanchen, Song, Zixing +3
Computer Science · Neuroscience · #Advanced Graph Neural Networks #FOS: Computer and information sciences #Functional Brain Connectivity Studies #Graph Theory and Algorithms #Machine Learning (cs.LG)

paper · pdf · doi:10.48550/arxiv.2506.16110

openalex publication_date 2025/06/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

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 over-squashing. To reduce such bottlenecks, graph 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., spectral 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 spectrum-preserving graph sparsification, 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.

Citations

• Sign is Not a Remedy: Multiset-to-Multiset Message Passing for Learning on Heterophilic Graphs
• Spectral Graph Pruning Against Over-Squashing and Over-Smoothing
• Higher-Order Expander Graph Propagation
• Probabilistically Rewired Message-Passing Neural Networks
• Locality-Aware Graph-Rewiring in GNNs
• Cooperative Graph Neural Networks
• Mitigating Over-Smoothing and Over-Squashing using Augmentations of Forman-Ricci Curvature
• Understanding Oversquashing in GNNs through the Lens of Effective Resistance
• On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology
• Leave Graphs Alone: Addressing Over-Squashing without Rewiring
• Revisiting Over-smoothing and Over-squashing Using Ollivier-Ricci Curvature
• FoSR: First-order spectral rewiring for addressing oversquashing in GNNs
• Revisiting Heterophily For Graph Neural Networks
• Expander Graph Propagation
• ResNorm: Tackling Long-tailed Degree Distribution Issue in Graph Neural Networks via Normalization
• Understanding over-squashing and bottlenecks on graphs via curvature
• Local Algorithms for Estimating Effective Resistance
• Rethinking Graph Transformers with Spectral Attention
• Learning to Drop: Robust Graph Neural Network via Topological Denoising
• Simple and Deep Graph Convolutional Networks
• On the Bottleneck of Graph Neural Networks and its Practical Implications
• Geom-GCN: Geometric Graph Convolutional Networks
• Multi-scale Attributed Node Embedding
• Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological View
• How Powerful are Graph Neural Networks?
• Graph networks as learnable physics engines for inference and control
• Relational inductive biases, deep learning, and graph networks
• Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning
• Graph Attention Networks
• Neural Message Passing for Quantum Chemistry
• Semi-Supervised Classification with Graph Convolutional Networks
• Revisiting Semi-Supervised Learning with Graph Embeddings
• The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains
• Approaching optimality for solving SDD systems
• Spectral Sparsification of Graphs
• Graph Sparsification by Effective Resistances
• Random Walks and Electric Networks
• The Graph Neural Network Model

Related

• Spectral Graph Pruning Against Over-Squashing and Over-Smoothing
• FoSR: First-order spectral rewiring for addressing oversquashing in GNNs
• Leave Graphs Alone: Addressing Over-Squashing without Rewiring
• Spectral Neural Graph Sparsification
• Schreier-Coset Graph Rewiring