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

Langzhang Liang, Fanchen Bu, Zixing Song, Zenglin Xu, Shirui Pan, Kijung Shin · 2025

Read Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification by Langzhang Liang, Fanchen Bu, Zixing Song, Zenglin Xu, Shirui Pan, Kijung Shin (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-16110.txt.

Introduction

Graph neural networks learn by passing notes between linked points, but distant points often fail to hear each other. Langzhang Liang and co-authors attack that flaw, called over-squashing, in a 2025 paper. Bottlenecks in the graph squeeze too much information through too few links.

Common fixes add links, which costs compute time and can blur each point's own signal. Their method instead thins the graph in a way that keeps its core vibration pattern, the spectrum, nearly intact. The thinned graph connects better while staying sparse. Tests beat strong rival methods on labeling accuracy and on holding the spectrum of the graph, which shows rewiring need not erase what made the graph itself.

Catalog record

CREATORLangzhang Liang, Fanchen Bu, Zixing Song, Zenglin Xu, Shirui Pan, Kijung Shin
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE66 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-16110

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification Langzhang Liang, Fanchen Bu, Zixing Song, Zenglin Xu, Shirui Pan, Kijung Shin 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. 1 Introduction and Related Works Graphs are a fundamental data structure for representing complex relational systems, where nodes signify entities and edges represent interactions ( Harary 1969 ; Diestel 2012 ; Shuman et al. 2013 ) . Their capacity to capture both structural and relational information makes them valuable across diverse fields, including social networks, biological systems, and recommendation engines ( Battaglia et al. 2018 ; Sanchez-Gonzalez et al. 2018 ; Gilmer et al. 2017 ; van den Berg et al. 2017 ; Koh et al. 2024 ) . Graph Neural Networks (GNNs) are a specialized class of neural networks developed to process graph-structured data by utilizing both node features and edge-based structural information ( Scarselli et al. 2009 ; Kipf & Welling 2017 ; Velickovic et al. 2018 ) . GNNs iteratively update each node’s representation by aggregating information from its neighbors ( Gilmer et al. 2017 ) . Recently, the problem of over-squashing in GNNs has gained attention. Over-squashing occurs when information from distant nodes is forced through graph structural bottlenecks, causing message distortion during aggregation ( Alon & Yahav 2021 ) . This issue worsens in deeper networks as the receptive field grows, making it difficult to encode large amounts of information into a fixed-size vector. Consequently, over-squashing limits GNNs’ ability to capture long-range dependencies, degenerating performance on tasks that need global context. Figure 1: Overview of the proposed densification-sparsification rewiring (DSR) framework. The framework starts by densifying the input graph through an inverse spectral sparsification process, which aims to alleviate structural bottlenecks while preserving spectral properties. Following this, sparsification is applied to the densified graph (referred to as the latent graph) to generate an output graph. This output graph not only exhibits improved connectivity, as measured by effective resistance, but also retains similar spectral properties and maintains the same edge density as the original input graph. Many efforts to address over-squashing have focused on graph rewiring techniques. These methods modify the edge set of input graph (original graph)—either by adding or reconfiguring edges—to create an output graph that enhances connectivity and enables more effective message passing in sparse or bottlenecked areas. The rewired output graph is then used for downstream tasks, such as node classification and graph classification. Despite advancements, existing graph-rewiring methods have two notable limitations. First, they often substantially modify the edge set and fail to preserve graph structural integrity, especially the Laplacian spectrum. For instance, Delaunay graph-based rewiring ( Attali et al. 2024 ) offers benefits such as reduced graph diameter and lower effective resistance. However, it constructs graphs solely based on node features, completely disregarding the original graph topology. Similarly, graph transformers ( Ying et al. 2021 ; Kreuzer et al. 2021 ) essentially rely on fully connected graphs, while expander graph-based rewiring methods ( Deac et al. 2022 ; Christie & He 2023 ) may even introduce entirely new node sets, diverging significantly from the structure of the input graph. It is important to preserve graph spectrum during rewiring, since many learning tasks, such as clustering and semi-supervised learning on graphs, rely on spectral properties to ensure accurate results. Second, these methods often introduce many additional edges to enhance connectivity, which increases the computational cost of learning on the rewired output graph. Moreover, a denser output graph increases the risk of over-smoothing, where information from neighboring nodes becomes excessively blended, undermining the ability to maintain distinct node features ( Li et al. 2018 ; Chen et al. 2020a ; Liang et al. 2023b ) . To address these challenges, we propose GOKU , a graph rewiring method designed to address over-squashing in GNNs. Specifically, given an input graph G , the objective is to generate an output graph G_{o} with improved connectivity by increasing a few of the smallest eigenvalues of its Laplacian, while preserving sparsity and ensuring the remaining eigenvalues stay close to those of G . This balance allows G_{o} to improve message-passing capabilities without deviating significantly from the spectrum of the original graph, which reflects the graph’s essential characteristics. This is inspired by spectral sparsification techniques that allow graphs with different edge sets to maintain spectral similarity. GOKU operates in two phases: (1; densification) it first densifies the input graph G by solving an inverse graph sparsification problem, creating a densified latent graph with improved connectivity; (2; sparsification) it then applies a spectral sparsification algorithm to reduce edge set size, producing a sparse output graph G_{o} for downstream classification tasks. This densification-sparsification paradigm is illustrated using an example graph in Figure 1 . Contributions. Our main contributions are as follows: • We propose a novel densification-sparsification rewiring (DSR) paradigm for mitigating over-squashing (Sec. 3 ). To our knowledge, DSR is the first rewiring paradigm that simultaneously (1) enhances connectivity for effective message passing, (2) maintains graph sparsity for computational efficiency, and (3) explicitly preserves the graph spectrum for structural fidelity. • We present a novel method GOKU, a practical and effective instance of the proposed DSR paradigm (Sec. 4 ). With efficient algorithmic designs, GOKU operates in nearly linear time with respect to both nodes and edges. • We conduct extensive experiments (Sec. 5 ). GOKU achieves better downstream performance than existing methods in both node and graph classification tasks on 10 datasets, while effectively balancing improving connectivity and preserving graph spectrum. Related works and their limitations. Numerous methods have been proposed to mitigate over-squashing in GNNs. Many approaches focus on modifying the graph structure through rewiring. For instance, First-order Spectral Rewiring (FoSR) ( Karhadkar et al. 2023 ) improves the first-order approximation of the spectral gap by adding edges. Curvature-based methods ( Topping et al. 2022 ; Nguyen et al. 2023 ) optimize connectivity by adding and removing edges based on geometric principles. ProxyGap ( Jamadandi et al. 2024 ) employs both edge deletions and additions to optimize the spectral gap, based on the Braess paradox ( Braess 1968 ) . Expander graph-based rewiring ( Deac et al. 2022 ) maintains a small diameter using Cayley graphs, which may even have a different node set from the original graph. More recently, methods like Probabilistically Rewired Message-Passing Neural Networks

Read the complete text