Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification
Authors: Langzhang Liang
Fanchen Bu
Zixing Song
Zenglin Xu
Shirui Pan
Kijung Shin
Venue: ICML 2025 poster (2025)
Keywords: Graph Neural Ntworks
Over-squashing
Graph sparsification
Primary area: deep_learning->graph_neural_networks
TL;DR: We propose a novel approach to mitigate over-squashing which generates rewired graphs that can preserve the spectra of the original graphs while improving connectivity.

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 spectral graph sparsification for mitigating over-squashing. Specifically, 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.

Mitigating Over-Squashing in Graph Neural Networks by Spectrun-Preserving Sparsification
Langzhang Liang'
Fanchen Bu Zixing Song?
Zenglin Xu 45 Shirui Pan Kijung Shin 12
Abstract
edges represent interactions (Harary, 1969; Diestel, 2012; Shuman et al., 2013). Their capacity to capture both struc- tural and relational information makes them valuable across diverse fields, including social networks, biological sys- tems, and recommendation engines (Battaglia et al., 2018; Sanchez- Grohheez- al., 2018; Gilmer et al., 2017: van den Berg et al., 2017; Koh al., 2024). Graph Neural Networks (GNNs) are specialized class of neural networks developed to process graph-structured data by utilizing both node fea- tures 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 al., 2017).
The message-passinn paradigm of Graph Neu- ral Networks often struggles with exchanging in- formation 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 orig- inal graph, e.g., spectral properties. Moreover, many approaches rely on increasing edge count to improve connectivity, which introduces sig- nificant computational overhead and exacerbates the risk of over-smoothing. In this paper, we pro- pose a novel graph rewiring method that leverages ppectrum-preservigg graph sparsification, for mit- igating over-squashin. Our method generates graphs with enhanced connectivity while main- taining sparsity and largely preserving the original graph spectrum, effectively balancing structural bottleneck reduction and graph property preserva- tion. Experimental results validate the effective- ness of our approach, demonstrating its superior- ity over strong baseline methods in classification accuracy and retention of the Laplacian spectrum.
Recently, the problem of over-squashing in GNNs has gained attention. Over-squashing occurs when informa- tion from distant nodes is forced through graph structural bottlenecks, causing message distortion during aggregation (Alon & Yahav, 2021). This issue worsens in deeper net- works as the receptive field grows, making difficult to encode large amounts of information into fixed-size vector. Consequently, over-squashing limits GNNs' ability cap- ture Long-range dependencies, degenerating performance on tasks that need global context.
Many efforts to address over-squashing have focused on graph rewiring techniques. These methods modify the edge set of input graph (original either by adding or reconfiguring edges-to create an output graph that en- hances connectivity and enables more effective message passing in sparse or bottlenecked areas. The rewired out- put graph is then used for downstream tasks, such as node classification and graph classification.
1. Introduction and Related Works
Graphs are a fundamental data structure for representing complex relational systems, where nodes signify entities and
Despite advancements, existing graph-rewiring methods have two notable limitations. First, they often substan- tially modify the edge set and fail to preserve graph struc- tural integrity, especially the Laplacian spectrum. For in- stance, Delaunay graph-based rewiring (Attali et al., 2024) offers benefits such as reduced graph dianeter and lower effective resistance. However, it constructs graphs solely based on node features, completely disregarding the orig- inal graph topology. Similarly, graph transformers (Ying et al., 2021; Kreuzer et al., 2021) essentially rely on fully connected graphs, while expander graph-based rewiring
'Kim Jaechul Graduate School of Artificial Intelligence, KAIST, Scoul, Republic of Korea "School of Electrical Engineer- ing, KAIST, Daejcon, Republic of Korea 'Department of Engi- neering, University of Cambridge, Cambridge, United Kingdom "Attificill Intelligence Innovation and Incubation Institute, Fudan University, Shanghai. China Thiina'Shame 'Shanghai Academy of Artificial Intel- ligence for Science, Shanghai, China "School of Information and Communication Technology, Griffith University, Gold Coast, Aus- tralia. Correspondence to: Kijung Shin <kijungs kaist.ac.kr>.
Proceedings of the 4dnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preservnng Sparsification
Input graph G
Densification
Latent graph G2
Sparsification
Output graph G,
Laplacian spectrum comparison
Input
Output
- Latent
(1) Objectives:
(1) Objectives:
To mitigate bottlenecka preserve spectral properties
To reduce edge denaity
-To preserve spectral properties
Bottleneck
Eigen
(2) Method:
(2) Methoct
Inverse spectral
Spectral spersification (egg, Section 4.2)
spersification
(eg, Section 4.1)
New
edges
Stadstic::
Statistics:
Statistics:
Edge count:
Edge count
EEgg count:
1
2
3
4
5
6
7
8
9
10
refesttive (ER) between a.d
ER v:0.
ERR betweenu and v.5
Order
Figure I: Overview of the proposed ceaifffcaaioossppsssfiititii 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 outpul 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.
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 pre- serve 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.
Contributions.
Our main contributions are as follows:
We propose novel ceasification-pparssftttlll rewiring (DSR) paradigm for mitigating over-squashing (Sec. 3). To our knowledge, DSR is the first rewiring paradigm that simultancously (1) enhances connectivity for effective message passing, (2) maintains graph sparsity for computational efficiency, and (3) explicitly preserves the graph spectrum for structural fidelity.
Second, these methods often introduce many additional edges enhance connectivity, which increases the com- putational cost of learning on the rewired output graph. Moreover, denser output graph increases the risk of over- smoothing, where information from neighboring nodes be- comes excessively blended, undermining the ability to main- tain distinct node features (Li et al., 2018; Chen et al., 2020a; Liang et al., 2023b).
We present novel method GOKU, practical and ef- fective 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 connec- tivity and preserving graph spectrum.
To address these challenges, 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, with improved connectivity by increasing a few of the smallest eigenvalues of its Lapla- cian, while preserving sparsity and ensuring the remaining eigenvalues stay close to those of G. This balance allows Go 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 two phases: (1; densification) it first densifies the input graph G by solving an inverse graph sparsification problem, creating densified latent graph with improved connectivity; (2; sparsification) it then applies spectral sparsification algorithm to reduce edge set size, producing sparse output graph G, for downstream classification tasks. paradigm is illustrated us- ing an example graph in Figure 1.
Related works and their limitations. Numerous methods have been proposed to mitigate over-squashing in GNNs. Many approaches focus on modifying the graph struc- ture 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- 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 op- timize the spectral gap, based on the Braess paradox (Braess, 1968). Expander graph-based rewiring (Deac et al., 2022) maintains 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 (Qian et al., 2024) explore proba- bilistic approaches to rewiring. Black et al. (2023) propose
This
2

---

Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification
minimizing total effective resistance reduce bottlenecks. Attali al. (2024) construct new graphs based on node fea- tures, completely discarding the original topology. Other methods address over-squashing without altering the origi- nal graph topology. Giovanni et al. (2023) investigates the impact of model width, depth, and topology. (Tortorella & Micheli, 2022) and PANDA (Choi et al., 2024) propose alter- peessagepasssing
Task
Dataset
Same Class
Different Class
IMDB
0.59
0.21
Mutag
0.58
0.23
Graph
Proteins
0.13
0.05
Enzymes
0.05
0.03
Cora 0.2817
0.0736
Node
Citeseer 0.0013
0.0001
native message- passing mechanisms, with PANDA focusing on expanded width-awan message passing. Cooperative Graph Neural Networks (Finkelshtein et al., 2024) also in- troduce learned cooperative mechanisms in message passing that can help alleviate information bottlenecks.
Pubmed 0.3383
0.1121
Table 1: Average spectral similarity between graphs and nodes within the same class and across different classes. For the graph- level (IMDB, Mutag, Proteins, Enzymes), similarity is computed based on eigenvalue distributions using the fastdtw algorithm (as they have different numbers of nodes). For the node level (Cora, Citeseer, Pubmed), similarity is measured as the average cosine similarity between node feature vectors derived from eigenvectors.
While these approaches improve connectivity, they often substantially change the topology, overlooking the signif- icance of retaining the graph structure. To address this limitation, Locaeety-aware rewiring (Barbero al., 2024) has been recently proposed to restrict new connections to k- hop neighbors, avoiding arbitrary long-range modifications. However, there still remains a lack of methods that explicitly integrate spectrum preservation- a key aspect that captures essential graph structural properties- into mitigating over- squashing. To bridge this gap, this paper introduces novel approach leveraging spectral sparsification methods, which produce sparsified graphs that explicitly maintain spectral similarity to the original graph. Our code is available at
on these intrinsic graph and node characteristics. For graph classification, graphs belonging to the same class tend to exhibit more similar eigenvalue distributions than graphs from different classes. For node classification, nodes from the same class exhibit higher average cosine similarity in their eigenvector- bassdd feature representations compared nodes from different classes (using components from the first 128 eigenvectors, resulting in 228-dimensions feature vector per node). The results supporting these observations for both tasks are summarized in Table 1.
Spectral gap and effective resistance. The spectral gap (or algebraic connectivity) of a graph (Chung, 1997; Fiedler, 1973) is the second-smallest (i.e., smallest non-zero) eigen- value X2 of its Laplacian matrix.' A small spectral gap implies many structural bottlenecks, i.c., poor connectivity. The effective resistance (ER) Ru,e (Doyle & Snell, 1984) between nodes u and U, quantifies the difficulty of flow between the two nodes: Ru, = - -e,) L+ (e, ex); where eu and eg are indicator vectors for and v, and + is the Moore-Penrose pseudoinverse of the Laplacian L. A lower Ru, indicates more alternative short paths between u and v, implying (u, v) is well-connected.
2. Preliminaries and Background
2.1. Preliminaries on Graphs
Graph and notation. We define basic notations used in this paper. Let G (V, E, w) be an undirected weighted graph, where V is the node set with n =VV, E is the edge set with m = FF and w: E + R+ assigns positive weights to edges. Note that unweighted graphs are treated as special cases of weighted graphs with all weights being one. Nodes have a feature matrix X E gaxd The weighted adjacency matrix A E Raxx has As = Wiy if (Mi, 1;){ E F,, otherwise Aij = O. The degree matrix D is diagonal with
Graph Neural Networks (GNNs). update node representations iteratively by ag- gregating information from neighboring nodes: N = U, (1) Mr (n ((h. (t-1) I (()))))))) where Mi and U, are the message and update functions at layer 1, and h.")) are the node embedding of at layer L. For graph classification, we use a readout function ú = R
GNNs
DH =E As,. and the Laplacian matrix is L D A. For node classification, the label matrix Y E f0, 1]mxe encodes node label assignments across classes. For graph classification, the dataset comprises {(Gt, 3:) where each graph G; = (Vi, E.) is labeled yo-
Graph spectrum. The graph spectrum of a graph is the set of eigenvalues \ = 0 < X2 S ... < X, of its Laplacian L. It is a "fingerprint" that encodes topological charac- teristics, e.g., node centrality, community structure, and clustering coefficient (Chung, 1997). Since spectral prop- erties are invariant to graph isomorphisms, they provide robust framework for comparing and analyzing graphs. Preserving spectral similarity is essential for tasks relying
to aggregate all node embeddings.
'We define spectral gap following, e.g., Karhadkar et al. (2023), while it can be alternatively defined as the difference between the two largest cigenvalues of the adjacency matrix.
3

---

Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification
2.2. Graph Sparsification
-A General Framework
Graph Sparsification (Benezúr & Karger, 1996; Spielman & Srivastava, 2008; Spielman & Teng, 2011) is family of techniques aimed at approximating graph G with sparse graph H, ensuring that H is an efficient computa- tional proxy for G while minimizing approximation errors.
In this section, we introduce a novel Densification- Sparsification Rewiring (DSR) paradigm to mitigate over- squashing in GNNs, consisting of two sequential modules: graph densification and graph sparsification. We denote the input graph (original graph) as G. the intermediate graph after densification (referred to as the latent graph) as G₁, the final output graph after sparsification as Go. i.c. G densificcation
Spectral sparsification. Among these techniques, spectral sparsification produces a sparsifier of the original graph whose Laplacian quadratic form closely approximates that of the original graph across all real vector inputs.
Gj sparsification
G.. Below, we first explain the motivations behind these two steps, and then discuss their details. This section introduces the general paradigm. while Section 4 presents concrete instance of DSR.
Definition 2.1 (Spectrally Similar Graphs). Let G = (V, E,w) w) and H = (V. Ei,, wH) be undirected weighted graphs. We say H is (1 + e)-spectrally similar to G for an approximation error parameter c E (0, 1), denoted by H 1 G, if the Laplacian matrices Lø and L (of H and G respectively) satisfy the following inequality for all x E R":
3.1. Motivations
Our core idea is to view the input graph G = (V, F.) as spectral sparsifier of unknown latent graph G2 (V, Et) that has good connectivity, and we aim to reconstruct Gr. In this view, the structural bottlenecks observed in G' arise due to the omission of certain critical edges during the sparsification process from G₁ to G. By reconstructing G1, we aim to recover these "missing edges", which can help mitigate over-squashing and improve the overall graph structure. How can we identify those "missing edges" and reconstruct Gj from the "sparsified" graph G?
Densification.
(I- LX S S LHI S (1 + c)x La.
(1)
LL Remark 2.2. The definition of x² Læ
E(uNjeg (x - x2)² intrinsically connects to various topological characteristics of the graph. For instance, by choosing I to be an indicator vector for a set of nodes S S V. i.e., Tu 1 if u S and v., 0 if & S. the quadratic form x T Læ becomes the weight of the graph cut separating S from its complement S. denoted cut(S, That is, x Lr= = cut(S, S). Similarly, other choices of x can reveal connections to node degrees or relationships between cigenvalues. This comprehensive measure allows us assess the similarity of graphs based on their fundamental structural properties.
This question defines the densification (or inverse sparsi- fication) problem: given graph G, we aim to reconstruct the latent graph Gj such that G, is the most likely (as in Maximum Likelihood Estimation) latent graph from which spectral sparsification algorithm produces G. Since G is a spectral sparsifier of Gt, Gi is expected effectively preserve the spectrum of G while improving connectivity.
Definition 2.3 (Spectral Sparsifier). Let G = (V, F, w) and
To reintroduce missing edges crucial for increasing connec- tivity, we consider the inverse process of unimportance- based spectral sparsification (USS). In USS, crucial edges tend to be removed, while less crucial edges tend to remain. Therefore, if G is the result of applying USS Gj, the "remaining edges" in G are less crucial, while the "missing edges" that are in G3 but not in G are supposed to be crucial for connectivity, which we aim to recover.
H = (V, wH) be undirected weighted graphs. H is called a sparsifier of G if Eµ C E. If a sparsifier H is also (1 + e)-spectrally similar to G. we say H is a (1 = c)- spectral sparsifier of G.
A common approach to sparsification (i.e., constructing sparsifier) involves repeating the following process for rounds: (1) sampling an edge e; E E with replacement according to a probability distribution (ee and (2) in- crementing its weight by "Ks,, This process ensures that spe;
Sparsification. A drawback of densification is the in- creased computational complexity due to added edges in Gj. To balance connectivity and efficiency, we apply importance-based spectral sparsification (ISS) to G pruning edges that are less critical for connectivity. As result, the output G, almost retains Gi's 's connectivity level while preserving the sparsity and spectrum of G, making it an ideal proxy for downstream tasks on G.
the expected weight of each edge in the sparsified graph See W.-
H matches its original weight in G, since qp.- ope Consequently, the total edge weight is also preserved in ex- pectation. Different sparsification methods primarily differ in their choice of (p=). Our rewiring paradigm builds upon this sparsification framework, which we introduce in the following section.
Combination.
When we combine the two steps, both G and G, are spectral sparsifiers of G,. Therefore, the
3. DSR: Proposed Rewiring Paradigm
4

---

Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification
spectrum is explicitly preserved from G Go:
Algorithm 1 USS Algorithm
1: Input: Graph G. = (V. Ed, wa) and sampling count q
Go ite R GR G. 1he
(1+t)² G Go ~ G.
2: Output: Graph G2 (V, F.,, Wss)
3: Compute the Fielder vector f (the eigenvector corre- sponding to the second-smallest eigenvalue X2 of Lapla- cian) and node degrees deg(u)'s
At the same time, by (1) recovering edges that are crucial for connectivity in densification and (2) removing edges that are less crucial in sparsification, we maintain sparsity and enhance the connectivity from G to Go-
4: Initialize (e) < 0, Ve E Ed
5: for i to g do
Sample an edge e; = (u, v) E Fa with replacement, (
3.2. Detailed Descriptions
with probability Pe x ( [fu-ful
7: Increment the weight: (x(e)) + wa(es) + wa(e:)
Densification. The graph densification problem is formu- lated as Maximum Likelihood Estimation (MLE) problem.
Pef
8: end for
9: Return G. = (V, w.) by collecting the sampled edges and their weights: E, = {e E Ea : w.(e) > 0}
Definition 3.1 (Graph Densification Problem). Given (V, E, w) and a spectral sparsification algorithm o6-) that outputs (1 + e)-spectral sparsifier (see Def. 2.1), the densification problem aims to find a latent graph G2 (V, E,, wi) to maximize the likelihood of G being the result of applying (b)) to Gj. Formally,
higher Pe values to edges that are more crucial. We can sim- ilarly set Pe proportional to the topological significance of e: Pe.. x Topological significance of e, and the "topological significance" in USS and ISS can be defined differently. We will provide detailed algorithmic choices in our practical instance of sparsification in Section 4.2.
G = argmax
Ga= CZ=(VEEUE P(O(Ga)= = G)
(2)
lte subject to ENE'= 0, Gd
2 G.
Comparison to existing methods. Our method differs from existing approaches in several ways. First, it explicitly preserves spectrum through (inverse) spectral sparsification. Second, it integrates both densification and sparsification. While prior works (Topping et al., 2022; Nguyen et al., 2023; Fesser & Weber, 2023; Jamadandi al., 2024) also modify edges mitigate over-smoothing enhance connectivity, our approach guarantees that the final sparsified graph never exceeds the original graph's 's density. Third, rather than deterministically selecting edges based on predefined con- nectivity metrics, our method employs a probabilistic edge modification strategy. Finally, leveraging graph spectral properties, the number of added edges |E') derived from a well-established theoretical result (see Theorem 4.1) rather than being a heuristically chosen value.
Here, E is the edge set of the observed sparsifier G, and E' the set of "missing edges" removed during sparsification.
Unimportance--assed spectral sparsification (USS). As mentioned in Section 3.1, in USS, edges that are crucial for connectivity tend to be removed, while less crucial edges tend to remain. Therefore, the distribution Pe for sampling edges (see Section 2.2) in (-)) should give higher pe. val- ues to edges that are less crucial for connectivity. A natural approach is to set Pe inversely proportional to the topolog- ical significance of e: Pe.o X Yopological signinicance e where "topological significance" can be quantified using edge im- portance metrics, e.g., effective resistance or edge between- ness. We will provide detailed algorithmic choices in our practical instance of densification in Section 4.1.
4. GOKU: Proposed Method -A Practical Instance of DSR
Sparsification. In graph sparsification, we use another spectral sparsification algorithm e-() that outputs a (1 =1=)-- c)- spectral sparsifier, to selectively retain edges with high topo- logical significance in the latent graph Gj. By doing so, we reduce structural complexity, preserve the graph spectrum, and maintain the enhanced connectivity in Gr.
In this section, we present a practical instance of the AesitiiationnSpaasificaaia Rewiring (DSR) paradigm, termed GOKU (Graph rewiring to tackle Over-squashing by Keeping graph spectra throUgh spectral sparsification). Implementing the DSR paradigm requires designing USS and ISS algorithms and solving the MLE problem in Eq. (2).
Importance-based spectral sparsification (ISS). As men- tioned in Section 3.1, in ISS (which is the opposite of USS), edges that are crucial for connectivity tend to re- main. Therefore, the distribution Pe.ş in vi(-) should give
4.1. Graph Densification: USS and the MLE Problem
For graph densification, we design an algorithm for the USS method, and propose an efficient procedure to construct the latent graph for the MLE problem in Eq. (2).
'The existence of such o(-) is guaranteed by existing results. For example, Benczúr & Karger (1996) and Spielman & Srivas- tava (2008) proposed algorithms sparsifier with On log n//e") edges for any graph.
construct (1 + e)-spectral
USS instance. The USS method should assign low prob-
5

---

Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification
abilities Pe edges crucial for maintaining connectivity. We design Algorithm 1 as USS method, which prefer- entially retains edges with a high value of deg(a) +deg()))) -vl
to simplify calculation, we approximate P(()(Ga) =G) as:
P(o(Ga)= =))
where fu and fo are components of the Fiedler vector (the eigenvector associated with the second-smallest eigenvalue A2 of Laplacian; see Section 2.1).
II (P(( ((Ga))) "h
II (P((' & ((Ga)))
C'EE'
II (1 (1-e) pe) CEF
II ((1 - ))))))))) d'E
(3)
Why does a lower value of deg(() indicate higher significance for connectivity? The intuition is: large If.. fol suggests weak connectivity between u and v, and small degrees imply they are weakly connected to the remaining part of the graph. Removing such edges creates bottlenecks, making them critical for preserving graph connectivity.
I.f-ff1
where w = EEEB / is the average edge weight, and recall Es = E". In Eq. (3), we simplify the formula by (1) assuming edge independence, and (2) using edge weights directly as power exponents (or equivalently, linear weights in the log probability). Since we assume uniform edge weights in G2, we omit wy in the formula.
Algorithm 1 provably produces spectral sparsifiers.
With the above simplifications and approximations, now, optimization over Ga is equivalent to optimization over the "missing edges" E', i.e., we aim to find E" argmax [I - (1 - pe) Ie'' ((1 Pe )") Below, we discuss the detailed procedure to find such E².
Theorem 4.1 (USS Gives Spectral Sparsifiers). Lei Ga = (V, Ea, wa) and G, = Ev, Wa) be the input and out- put of Algorithm 1, with Laplacian L and L,, respectively. For any x R", define
k((x) Pesa Caall where
||aa]2
Pmin = Ea Ea Pe, and C E ER
x(VI denotes the signed incidence matrix of Ga. For any E 1), if
First, we select an approximation error parameter E (0, 1). set I as the leading eigenvector (the eigenvector associated with the largest eigenvalue X₂2) of the Laplacian of G, and compute the corresponding condition number λ x(x) (see Theorem 4. We use the leading eigenvector since we aim to improve the small eigenvalues (c.g., the spectral gap X2; see Section 2.1) which are closely related to structural bottlenecks, while preserving the large eigenvalues. The choice of e ensures that a sufficient number of new edges can be added E", specifically requiring |E"| = |E - [E] to exceed a predefined threshold a. Next, we set q y= 2,2 log 8, and determine |Ei] such that when sampling q raadom edges with replacement from E,, the subgraph contains exactly [E] distinct edges in expectation. Further details on this process are provided in Appendix E.
q2 1 22 log 8, then with probability at least 3/4,
(1- Lx S aF Lx S (1+c)x
Proof. Proof is deferred to Appendix D.
x²
Solve the MLE by inverse sparsification. We now solve the MLE problem in Eq. (2) using Algorithm I as the USS method, i.c., o(-) in Section 3.2. We treat the input graph G as the observed sparsifier, representing the output of Algorithm 1, and aim to find the latent graph Gj as the most likely input to Algorithm that would produce G.
Second, after determining |Ej (and thus [E'D, the task re- duces to maximizing the objective function in Eq, (3) by choosing |E'| edges from the complement set Ecomp = {u, u) u,v E V) \ F,, with ((EeT)) possible combina- tions, which is still intractable. To improve efficiency, we focus on edges between "promising nodes" through two steps: (1) Candidate set construction: Identify the 2j nodes with the largest absolute Fiedler values and the 2j nodes with the smallest degrees, where j is the smallest integer such that (2) > E'I. This gives (2) RJ E") edge combinations. Pairs between such nodes are likely to have a small value of deg(w)++dggu)++1 and thus are crucial for con- [-=
However, solving this MLE problem presents several chal- lenges. First, the search space of possible G 's is intractable, as it includes all supergraphs of G' and all possible edge weight assignments. Second, even for given Ga, comput- ing the exact probability P()(Ga) G) is difficult.
To address these challenges, we introduce a practical proce- dure with simplifications and approximations to efficiently obtain the latent graph G = (V, Et, wt). For the first chal- lenge, to reduce search space, we assume uniform edge weights in G2, i.e., w2 (e,) wn wy(eg) for any 61, e2 E E,, fo- cusing on optimizing the edge set. For the second challenge,
nectivity. (2) Random selection: Assign each edge in the candidate set probability c. proportional to the value of the objective function Eq. (3) assuming is inserted into G. We then sample E'| edges from the candidate set at once based on the distribution {ce} and construct G3 by including these edges. Finally, we re-scale the edge weights in G2 so that
Faac edge (u, v) E Eg is represented by two rows: one with Ck = Ckju 11, and zeros elsewhere; and another with Ckyu = -1, Ckyy = 1, and zeros elsewhere.
6

---

Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification
each edge in Ej has weight |E]/|E) ensuring that G and G have the same total edge weight, as the total edge weight is typical preserved in sparsification (see Section 2.2). See Appendix B for more details.
the approximation error. We use the technique by Koutis et al. (2014). The approximation error affects the bound by constant factor, altering the bound in Theorem 4.2 to (1 + (1 + 8)e). We fix ó = 0.1 throughout our experiments.
Time complexity. The time complexity of GOKU has two main components: graph densification and graph spar- sification. Denote |E] = m and [V] n. In graph densification, generating approximately 16| candidate edges and computing their scores requires ((EE)()) In graph sparsification, approximating the ER for all edges (llgol
4.2. Graph Sparsification: ISS
After deriving G1, we sparsify it using importance-based spectral sparsification (ISS) to obtain the output graph G.- We propose to use effective resistance (ER) to measure edge significance in ISS (see Sec. 2.1 for the definition of ER).
incurs O
and the ISS sampling step adds
ISS instance. We adapt a well-known ER-based spar- sification (Spielman & Srivastava, 2008), but further in- corporate node features. Specifically, each edge (u, is sampled with probability Pe x (1 + R.) where
8
O ni llogn
Combining these, the overall time complex-
ity is: O(IE' (m) + O (m-poly(log m)
+ O
2 log 12
S. = (1 + #x))/2 E [o, 1] is the normalized co- sine similarity between original node features, and R. is the edge's ER. Heterophily describes a type of graph where connections predominantly occur between dissimilar nodes. This characteristic has been recognized as a significant chal- lenge for effectively training GNNs across various stud- ies(Zhu et al., 2020; Luan et al., 2022; Liang et al., 2023a; 2024). This prioritizes edges with high ER and feature sim- ilarity, thus retaining edges crucial to connectivity while filtering noisy edges with dissimilar node features (as in topological denoising; see, e.g., Luo et al. (2021)). We sample edges until 3| distinct edges are selected, where
O(LE" (1] + (m) where Ô omits polylogarithmic fac- tors. The Fiedler and leading vectors can be approximated in linear time, dominated by the other terms.
5. Experiments
In this section, we evaluate the proposed method GOKU across various tasks, benchmarking its performance against state-of-the-art methods for node and graph classification. Our analysis is guided by the following research questions:
RQ1: Performance. How does GOKU compare to lead- ing methods in node/graph classification tasks?
0.5 B < 1, to ensure sparsity (specifically, G, is not denser than G). Due to the nature of the sparsification pro-
RQ2: Spectrum preservation. How well does GOKU
cess (see Section 2.2). Go has the same total edge weight as G1 in expectation. Recall in USS, the total edge weight of Gj matches that of G. Therefore, Go also matches the total edge weight of G. The ISS algorithm is similar to Alg. 1, except for the probability distribution {pe). For pseudocodes of our ISS instance and the GOKU method, please refer to Appendix B. Similar to USS, our instance of ISS also provably produces spectral sparsifiers.
preserve the graph spectrum?
RQ3: Ablation study. What are the contributions of densification and sparsification to GOKU's effectiveness? RQ4: Structural impact and efficiency of GOKU. How does GOKU improve the structure (homophily and con- nectivity) of graphs and how efficient GOKU?
Datasets. We evaluate our method on 10 widely used datasets for node/graph classification. For node classifica- tion, we use Cora, Citeseer (Yang et al., 2016), Texas, Cor- nell, Wisconsin (Pei et al., 2020), and Chameleon (Rozem- berezki et al., 2021), including both homophilic and het- erophilic datasets. For graph classification, we use Enzymes, Imdb, Mutag, and Proteins from TUDataset (Morris et al., 2019). Dataset statistics summarized in Appendix A.
Theorem 4.2 (ISS Gives Spectral Sparsifiers). Let Ga (V, Ea, wa) and G = Ee, w.) be the input and output of Algorithm 2, with Laplacian and T., respectively. For any c E (0, 1), there exists 9 = O(nlog ) such that
Vx E RR, (1 (1- Lax S xT sLx S (1 + La,
Experimental details. We compare the proposed method GOKU with no graph rewiring (i.e., NONE) and six state- of-the-art rewiring methods: SDRF (Topping et al., 2022), FOSR (Karhadkar et al., 2023), BORF (Nguyen et al., 2023), GTR (Black et al., 2023), Delaunay Rewiring (DR) (At- tali et al., 2024), and LASER (Barbero et al., 2024).
holds with high probability.
Proof. Proof is deferred to Appendix D.2.
4.3. Complexity Analysis
Each method preprocesses graphs before evaluation with
Approximating ER. Computing ER exactly is compu- tationally intensive, but there are efficient approximation methods in sublinear Omm poly(logn/88)) time (Koutis et al., 2014; Peng et al., 2021), where 0 < 8 < 1 is
7

---

Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification
Method
Cora
Citeseer
Texas
Cornell
Wisconsin
Chameleon
Enzymes
Imdb
Mutag
Proteins
AR
NONE
86.7
+2
44,2+15
41
44.6=14
a9.2+
15.5
49
68.8
70.6=10
6.60
SDRF
863
72.6403
43.9
42.2
46.2+12
59
26.1
49.
70.5
21.4208
5.70
FOSR
85.9
72.3+03
46.0+16
40.2+16
48.3=13
59
27.4+1.1
49.6
75.6+17
72.3
4.80
BORF
87.
73.8+02
49,4+12
50.8+11
50.3=09
61.5+00
24.7+1.0
50.1
75
71.0=0x
3.40
DR
78.4+12
69.5+
67.8+25
17.8+19
62.8+21
58.6+08
47.0+07
80.1
72.2+08
4.55
GTR
07
+2.4
45
10.8
4..
57.6
27.4
10
78.9
72.4=12
3.90
LASER
86.9+11
72.6+06
45.9+26
42.7+26
46,0=26
43
27.6+1.3
50.3
18.8+16
71.8+16
4.20
GOKU
86.8+a3
73.6+02
72.4+22
69.4+2.1
68.8 1.4
63.2+04
27.6+12
49.8+
81.0+20
71.9
1.90
Table 2: Performance of different methods for both node and graph classification datasets using GCN as the model. The best and runner-up
results are highlighted in yellow and green, respectively. The average ranking (AR) reflects the mean position of each method across all
datasets. +: DR requires graphs to have at least 3 nodes, but some graphs from Enzymes have only 2 nodes.
Method
Cora
Citeseer
Texas
Cornell
Wisconsin
Chameleon
Enzymes
Imdb
Mutag
Proteins
AR
NONE
12
19.3+
46.4+45
40.2+48
42,1
56.6+08
33,5+1a
67.7
76.1+31
69.5+14
6.20
SDRF
77.2
59.9.12
44.5+39
38.2
43.1
18.1
32
69.4+14
79.5
71.4.08
5.80
FOSR
78.2+u8
61.4
43.7+411
39.4+38
43.
59.3+
28
70.6+13
75
73.7
5.00
BORF
77.6+09
60.8+02
49.9+34
39.9+39
46.7
59.2+0.
31.4+15
70.5+13
18.2+16
71.9+13
4.40
DR
66.6
20.8
57.3
20.
50.1
60.2
64.8
74.5
74.3
4.44
GTR
18
62.6
49.5
39.4
44.2
57.1
28.4
70.1
78.5
73.3
4.40
LASER
79.1
66.5
46.5+45
44.5+38
46.1 +46
59.8+2.
35.3
68.6+12
76.1+24
72.1 707
3.40
GOKU
2..
6..
60.2
49.5.35
57.6
1..
33.8
71.3
78.4
a3.9
1.80
Table 3: Performance of different methods for both node and graph classification datasets using GIN as the model.
Method
Mutag
Imdb
Proteins
Chameleon
Cora
edges are sampled.
GOKU-D
78.0=18
72.0 48.2+
62.7 .07
86.4
Performance results. Table and Table 3 summarize the results for GOKU and baselines using GCN and GIN as backbone models, respectively (see Appendix C for the re- sults using GCNII). GOKU achieves superior performance across both node and graph classification tasks when using GCN as the backbone model, especially in the node clas- sification task for heterophilic graphs (such as Texas, Cor- nell, and Wisconsin). Similarly, with GIN as the backbone, GOKU maintains its strong performance, outperforming baselines in most datasets. Overall, GOKU consistently outperforms other methods, demonstrating its effectiveness across diverse tasks and graph types.
GOKU-S 16
70.1 48
62.9
86.4
GOKU
21.0=20
197
71.9
63.2204
86.8 0.3
Table 4: Ablation study, GOKU-D and GOKU-S correspond to densification and sparsification only.
a GCN (Kipf& & Welling, 2017), GIN (Xu et al., 2019), and GCNII (Chen et al., 2020b) (refer to Appendix C). Fol- lowing Nguyen et al. (2023), we prioritize fairness and comprehensiveness over maximizing performance on indi- vidual datasets, applying fixed GNN hyperparameters (e.g.. learning rate le- -3 3, hidden dimension 64, 4 layers) across all methods. Hyperparameters for rewiring methods are tuned individually. The configuration that yields the best validation performance is selected and tested. Results are averaged over 100 random trials with both the mean test accuracy and the 95% confidence interval reported.
Visualization of graph spectra. We visualize the spec- tra of randomly selected graphs from the Mutag and Pro- teins datasets before and after rewiring using GTR, DR, and GOKU, For a fair comparison, 10 edges are added to Mutag and 50 the other datasets (a 10 or a 50 for GOKU). For LASER, we set p 0.15 and maximum hop k 3 to add a similar number of edges. As shown in Figure 2, GTR and DR cause significant eigenvalue deviations, while GOKU best preserves the spectra of the original graphs, even outperforming LASER. This highlights GOKU's abil- ity to maintain spectral fidelity.
Hyperparameters of GOKU. We fix the spectrum approx- imation error 0.1, which determines the value of q q= 5e. log 8 (see Theorem 4.1). For the ER approximation algorithm (Koutis et al., 2014), we set 8 = 0.1. Two hyper- parameters are fine-tuned based on the validation set: (1; densification) E (5. 10, 15, 20, 25, 30): If the number of edges added during densification computed with the initial e = 0.1, is less than a, we iteratively increase e until this threshold is exceeded. (2; sparsification) /3 E [0.5, 1.0] This parameter scales the size of the output graph G. rela- tive to the input graph G, such that |E,| E. During the sparsification phase, we keep sampling until G E distinct
Ablation study. We provide ablation study in Table 4. The results demonstrate that both densification and spar- sification contribute to the effectiveness of GOKU. While GOKU-D (densification only) enhances connectivity more significantly than GOKU, this does not always translate to better performance for downstream tasks. Excessive connec- tivity can lead to issues such as over-smoothing or disrupting the underlying community structures. On the other hand,
* (EmENtr)
Whe Ao (())
$p MLP()) ((++)) h0 + +vE N()) Wae h()
8

---

Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification
Dataset
# Edges
Homo. (bef.)
Homo. (aft.)
Time (sec)
20 edges
245 edges
8035 2 edges
S S-High
20
0,8333
0.9167
0,086
Orginal Rewired
Ori Rewired
Original Rewired
S-Low
20
0,4000
0,4123
0.072
Hlgh Homoo
M-High
245
0.7459
0.7764
0.42
M-Low
245
0.3452
0.3822
0.36
150
L-HHigh
80352
0.7558
0.7822
65.26
I.-Low
80352
0.3854
0.4325
72.24
2.0 0.000
5,022
0.24
01066 0.000
Table 5: (1) Homophily levels before and after applying the GOKU
Low Homa.
Original Pawired
Original
Rendiea
450
rewiring method, and (2) the average running time (10 runs) for
300
GOKU rewiring across graphs of varying scales.
Mutag Elgenvalue Distribtton Compartson
Proteins Eigenvalue Distribution Comparison
0.000 2,012 0424 Duss 0,345
Eigemralue faagilude
Elgernelue Mongg Hoggritude
Figure 3: Effective resistance (ER) distribution node pairs in graphs with varying scales and homophily levels before and after rewiring. Smaller ER values suggest better connectivity.
which aligns with the theoretical time complexity in Section 4.3.
Eigenvalue
Elgenvalue
GOKU
GTR
LASER
Figure 2: Graph spectra of Mutag and Proteins before and after rewiring. See more examples in Appendix F.2.
6. Conclusions and Limitations
GOKU-S (sparsification only) alone fails to achieve sig- nificant improvements in connectivity. This underscores the importance of combining both components to strike balance between connectivity and density.
In this paper, we propose GOKU, novel graph rewiring method for addressing over-squashing in GNNs through the censification-ssariffffe
paradigm. Building on spectral sparsification, we formulate and solve an inverse sparsifi- cation problem to enhance graph connectivity while pre- serving spectral properties, followed by a sparsification step for maintaining sparsity. Extensive experiments show that GOKU outperforms existing methods in node and graph classification tasks, while effectively balancing connectivity improvement and spectral retention. Our code is available at
Homophily level, effective resistance, and running time. We generate graphs at varying scales (20, 200, and 2000 nodes) with different homophily levels (high and low) using the Stochastic Block Model (SBM) to investigate the impact of GOKU. Specifically, we compare homophily levels and effective resistance distributions before and after the GOKU rewiring technique is applied each graph. In addition, measure the rumning time of GOKU across diffferent graph sizes to evaluate its computational efficiency as the graph scale increases. For the experiment, we fix a = 0.1|E] and 3 = 1.0, meaning that during densification, we add 0.1 edges, and the density the rewired graphs remains the same as that of the original graphs.
Limitations. Spectrum preservation for unweighted graphs with different edge sizes is inherently challenging, so spectral sparsification typically relies on weighted graphs, where edge weights may cause additional complexities for GNNs. This is not a major concern in practice for most GNN models, where edge weights can be naturally incorporated.
The homophily values of the original and rewired graphs are given in Table 5, Note that GOKU consistently improves homophily levels" across differ- ent graph scales and homophily levels. This improve- ment is due to the consideration node features during sparsification, which helps preserve intra-community edges.
Homophily:
Effective resistance: After applying GOKU, the ef- fective resistances between node pairs significantly decrease, as shown in the distributions in Figure 3. This reduction indicates improvements both local and global connectivity in the rewired graphs.
Running time:
The running time of GOKU scales liar-linearly with the graph size, shown in Table 5,
"Homophily level defined

---

Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preservnng Sparsification
Impact Statement
Chen, M., Wei, Z., Huang, Z., Ding, B., and Li, Y. Simple and deep graph convolutional networks. In ICML, 2020b.
This paper presents work whose goal to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which feel must be specifically highlighted here.
Choi, J., Park, S., Wi, H., Cho, S., and Park, N. PANDA: expanded width-aware message passing beyond rewiring. ICML, 2024.
Christie, T. and He, Y. Higher- expander graph propa- gation. CoRR, abs/2311. 1.07966, 2023.
Acknowledgements
We thank the anonymous reviewers for their constructive feedback. This work was partly supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No. RS-2024-00406985), This
Chung, F. R. Spectral graph theory. CBMS Regional Con- ference Series in Mathematics, 1997.
Deac, A., Lackenby, M., and Velickovic, P. Expander graph propagation. In LoG, 2022.
work was partly supported by Institute of Information &
Communications Technology Planning & Evaluation (IITP) grant funded by the Korea government (MSIT) (No. 2022-0- 00871 / 2022-22211112,71,, Development of AT Autonomy and Knowledge Enhancement for AI Agent Collaboration) (No. R8-2024--00438633, DB2A:: Foundations and Software for Comprehensive Deep Representation Learn- ing and Prediction on Entire Relational Databases) (No. RS-2019-11190075, Artificial Intelligence Graduate School Program (KAIST)).
Diestel, R. Graph Theory, 4th Edition, volume 173 of
Graduate texts in mathematics. Springer, 2012.
Doyle, P. G. and Snell, J. L. Random walks and electric networks. 1984.
Fesser, I.. and Weber, M. Mitigating over-smoothing and over-squashing using augmentations of forman-ricei cur- vature. In LoG, 2023.
References
Fiedler, M. Algebraic connectivity of graphs. In Czechoslo- vak Mathematical Journal, volume 23, pp. 298-305, 1973.
Alon, U. and Yahav, E. On the bottleneck of graph neural networks and its practical implications. In ICI.R, 2021.
Finkelshtein, B., Huang, X., Bronstein, M. M., and Ccylan, i. Cooperative graph neural networks. In ICML, 2024.
Attali, H., Buscaldi, D., and Pernelle, N. Delaunay graph: Addressing over-squashing and over-smoothing using de- launay triangulation. In ICML, 2024.
Gilmer, J., Schoenholz, S. S., Riley, F., Vinyals, O., and Dahl, E. Neural message passing for quantum chem- istry. In ICML, 2017.
Barbero, F., Velingker, A., Saberi, A., Bronstein, M. M., and Giovanni, F. D. Locality- graph rewiring in gnns. In ICLR, 2024.
Giovanni, F. D., Giusti, L., Barbero, F., Luise, G., Lio, P., and Bronstein, M. M. On over-squashing in message passing neural networks: The impact of width, depth, and topology. ICMI, 2023.
Battaglia, P. W., Hamrick, J. B., Bapst, V., Sanchez- Gonzalez, A., Zambaldi, V., Malinowski, M., Tacchetti, A., Raposo, D., Santoro, A., Faulkner, R., Gulcehre, C., Menick, H., Pascanu, R., Botvinick, M., Vinyals, O., and Li. Y. Relational inductive biases, deep learning, and graph networks. Nature, 575:515-518, 2018.
Harary, F. Graph Theory. Addison Addison-Wesley. Wesley, 1969.
Jamadandi, A., Rubio-Madrigal, C., and Burkholz, R. Spectral graph pruning against over-squashing and over- smoothing. CoRR,
Benczúr, A. A. and Karger, D. R. Approximating s-t mini- mum cuts in Ō(n2) time. In STOC, 1996.
2024.
Karhadkar, K., Banerjee, P. K., and Montúfar, G. Fosr: First- order spectral rewiring for addressing oversquashing in gnns. ICLR, 2023.
Black, M., Wan, Z., Nayyeri, A., and Wang, Understand- ing oversquashing in gnns through the lens of effective resistance. In ICML,0023
Braess, D. Über ein paradoxon aus der verkehrsplanung. Unterneimeensfosccunng, 12(1):258-2666 1968.
Kipf, N. and Welling, M. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
Chen, D., Lin, Y., Li, W., Li, P., Zhou, J., and Sun, X. Measuring and relieving the smoothhng problem for graph neural networks from the topological view. In AAAI, 2020a.
Koh, H. Y., Nguyen, A. T. N., Pan, S., May. L. T. and Webb, G. I. Physicochemical graph neural network for learning protein-ligand interaction fingerprints from sequence data. Nat. Mac. Intell., 2024.
10

---

Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification
Koutis, I., Miller, G. L., and Peng, R. Approaching optimal- ity for solving SDD linear systems. SIAM Comput., 43 (1):337-354, 2014.
Rozemberczki, B., Allen, C., and Sarkar, R. Multi-scale attributed node embedding. J. Complex Networks, 9(2), 2021.
Kreuzer, D., Beaini, D., Hamilton, W. L., Létourneau, V., and Tossou, P. Rethinking graph transformers with spec- tral attention. In NeurlPS, 2021.
Sanchez-Gonzalee A., Heess, N., Springenberg, J. T., Merel, Riedmiller, M., Hadsell, R., and Battaglia, P. W. Graph networks learnable physics engines for infer- ence and control. In NeurIPS, 2018.
Langley, P. Crafting papers on machine learning. In ICML, pp. 1207-1216, 2000.
Scarselli, F., Gori, M., Tsoi, A. C.,, Hagenbuchner, M., and Monfardini, G. The graph neural network model. IEEE Trans. Neural Networks, 20(1):61-80, 2009.
Li, Q., Han, Z., and Wu, X.-M. Deeper insights into graph convolutional networks for semi-supervised learning. In AAAL, 2018.
Shuman, D. I., Narang, S. K., Frossard, P., Ortega, A., and Vandergheynst, P. The emerging field of signal process- ing on graphs: Extending sigh-dimensional data anal- ysis networks and other irregular domains. CoRR, abs/1307.5665. 2013.
Liang, L., Hu, X., Xu, Z., Song, Z., and King, I. Predicting global label relationship matrix for graph neural networks under heterophily. NeurIPS, 2023a.
Spielman, D. A. and Srivastava, N. Graph sparsification by effective resistances. In STOC, 2008.
Liang, L., Xu, Z., Song, Z., King, I., Qi, Y., and Ye, J. Tackling long-tailed tailed distribution issue in graph neural net- works via normalization. IFEE Transactions on Knowl- edge and Data Engineering, 3665):2213-2223, 2023b.
Spielman, D. A. and Teng, S. Spectral sparsification of graphs. SIAM J. Comput., 40(4):981-1055, 2011.
Liang, L., Kim, S., Shin, K., Xu, Z., Pan, S., and Qi, Y. Sign is not remedy: Multiset-to -uuliset message passing for learning heterophilic graphs. ICML, 2024.
Topping, J., Giovanni, F. D., Chamberlain, B. P., Dong, X., and Bronstein, M. M. Understanding over-squashing and bottlenecks on graphs via curvature. In ICLR, 2022.
Luan, S., Hua, C., Lu, Q., Zhu, J., Zhao, M., Zhang, S., Chang, X.-W., and Precup, D. Revisiting heterophily for graph neural networks. NeurlPS, 2022.
Tortorella, D. and Micheli, A. Leave graphs alone: Addressing over-squashing without rewiring. CoRR, abs/2212.06538. 2022.
Luo, D., Cheng, W., Yu, W., Zong. B.. Ni, J., Chen, H., and Zhang, X. Learning to drop: Robust graph neural network via topological denoising. In WSDM, 2021.
van den Berg, R., Kipf, N., and Welling, M. Graph convolutional matrix completion. In RecSys, 2017.
Velickovic, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., and Bengio, Y. Graph attention networks. In ICLR, 2018.
Morris, C., Ritzert, M., Fey, M., Hamilton, W. L., Lenssen, F., Rattan, G., and Grohe, M. Weisfeiler and leman go neural: Higher-order graph neural networks. In NeurlPS, 2019.
Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How powerful are graph neural networks? In ICLR, 2019.
Nguyen, K. Hieu, N. M.. Nguyen, V. D., Ho. N., Osher, S. J., and Nguyen, T. M. Revisiting over-smoothing and over-squ using ollivier-ricci curvature. ICML, 2023.
Yang. Z., Cohen, W. W. and Salakhutdinov, Revisiting semi-supervised learning with graph embeddings. In ICML, 2016.
Ying, C., Cai. T., Luo. S., Zheng, S., Ke, G., He, D., Shen, Y., and Liu, T. Do transformers really perform badly for graph representation? In NeurIPS, 2021.
Pei, H., Wei, B., Chang, K. C., Lei, Y., and Yang, B. Geom- gen: Geometric graph convolutional networks. In ICLR, 2020.
Zhu, J., Yan, Y., Zhao, L., Heimann, M., Akoglu, L., and Koutra, D. Beyond homophily in graph neural networks: Current limitations and effective designs. NeurIPS, 2020.
Peng, P., Lopatta, D., Yoshida, Y., and Goranci, G. Local algorithms for estimating effective resistance. In KDD, 2021.
Qian, C., Manolache, A., Ahmed, K., Zeng, Z., den Broeck, G. V., Niepert, M., and Morris, C. Probabilistically rewired message-passing neural networks. In ICLR, 2024.

---

Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification
Algorithm 2 ISS Algorithm
Input: Graph G; (V, E) and sampling count
2: Output: Output graph G. (V, Fie)
3: Approximate ER Re and compute original node feature cosine similarity S.
1+c0x (a.
E
[0, 1] for each edge
2
F..
4: for to q do
5: Randomly select edge with probability Pe. (1 R. with replacement
6: Increment the edge weight by 1_ for each sampling
P.y
7: end for
8: Construct the output graph G. (V, E.) by including the sampled edges with their accumulated weights
A. Dataset
summary of the statisties for all datasets used is presented in Table 6 and Table7.
Cornell
Texas
Wisconsin
Cora
Citeseer
Chameleon
#Nodes
140
135
184
2485
2120
832
#Edges
219
251
362
5069
3679
12355
#Features
1703
1703
1703
1433
3703
2323
#Classes
5
5
5
7
6
5
Directed Graph?
YRS
YES
YES
NO
NO
YES
Table 6: Summary statistics of node classification datascts.
ENZYMES
IMDB
MUTAG
PROTEINS
Basic Info. of Graphs
Nodes (Min-Max)
2-126
12-136
10-28
4-620
Edges (Min-Max)
2-298
52-2498
20-66
10-2098
Avg # of Nodes
32.63
19.77
17.93
39.06
Avg # of Edges
124.27
193.06
39.58
145.63
Classification Info.
# of Graphs
600
1000
188
1113
# of Classes
6
2
2
2
Directed Graphs?
NO
NO
NO
NO
Table 7: Summary statistics of graph classification datasets.
B. The GOKU Algorithm Pseudocode
We provide the pseudocodes for the ISS sparsification and GOKU Algorithm and Algorithm 3, respectively.
C. Results with GCNII
We conduct additional experiments using several of the strongest baselines from Table 2 and Table 3, alongside four benchmark datasets: Mutag, Proteins, Cora, and Corell. In these experiments, we use the powerful GNN model, GCNII (Chen et al., 2020b), as the backbone. The results from these experiments provide valuable insights into the relative strengths of the baseline models and the GCNII backbone. The results in the Table demonstrate the performance of four methods (DR, GTR, LASER, GOKU) on five datasets (Mutag, Proteins, Cora, Cornell, Wisconsin) using GCNII GOKU consistently achieves the best near-best performance across most datasets.
12

---

Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification
Algorithm 3 GOKU, Graph Densification and Sparsification Algorithm
Input: Input graph G (V,
2: Output: Output graph G. = (V, F..)
3: (Densification: Add k Edges G}
x 4: Compute q = 22 log 8 using the leading eigenvector and 6; estimate |Pa as Appendix E and set Frrl - |F]
5: Identify 2j nodes with the largest absolute Fiedler values and 2j nodes with the smallest degrees.
6: Form candidate edges between these nodes, size (*))
7: Initialize S 0 (set of selected edges)
8: Initialize r = 0 (sampling counter)
9: while size of < k do
10: Randomly select an edge e from the candidate set based on probability proportional to its contribution to the
objective function (3).
if then Add to S.
12:
13: end if
14: Increment edge weight of by
L Pr
15:
Increment r by 1.
16:
end while
17:
Construct latent graph G: = (V, = E S by including edges in with their accumulated weights; scale edge weights in by | scale edge weights S by 1/r.
(Sparsification: Reduce Ej to Eo}
19: for each edge Eg do
20:
Approximate effective resistance R. with approximation error = 0.1 using the technique proposed by Koutis et al. (2014).
21: end for
22: for iori=1 to q do
23: Randomly sample edges with probability p. (1 Re, where S. and R. denote feature similarity and effective
resistance of edge e, respectively.
24:
Increment edge weights by 1 for each sample. paq
25:
end for
26:
Construct sparsified graph G. = EV) by including the sampled edges with their accumulated weights.
Method
Mutag
Proteins
Cora
Cornell
Wisconsin
AR
DR
81.6
72.1
78.8
67.9
70.5
2.6
GTR
79.0
72.5
86.8
59.2
62.7 #3.7
3.4
LASER
80.3
73.0
88.1 1.3
60.8
60.1 +3.
2.6
GOKU
81.8
73.9 109
87.2
69.4
68.8 1.6
1.4
Table 8: Results on five datasets with GCNII. The best and runner-up results are highlighted in yellow and green, respectively. The average ranking (AR) reflects the mean position of each method across all datasets.
D. Proof
D.1. Proof of Theorem 4.1
Proof. We aim to show that the Laplacian L of the sparsified graph G, approximates the Laplacian L of the original graph G in the spectral norm, i.e.,
(1- L (1 e)
with high probability. Our approach is based on Chernoff bounds and variance control in the sampling process.
Setup. Consider a graph G = (V, E) with n nodes and m edges. For each edge e = (u, v) E E, the weight w. = 1. The Laplacian matrix e xn is defined as
D
13

---

Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification
where D is the degree matrix and A is the adjacency matrix. We sample q edges from E with replacement, where the probability of sampling an edge (u, v) is denoted by Pe, without specifying particular distribution for Pe, values. For each sampled edge, its contribution to the Laplacian is scaled by the inverse of its sampling probability. Let L be the Laplacian of the sparsified graph. Then,
B =1.
We aim control the spectral deviation between L and using a concentration bound.
Quadratic Form Decomposition. Let x E I= be an arbitrary vector. We analyze the quadratic form x Lzz which is sum of independent random variables:
Lx
X
where X; is the contribution of the i-th sampled edge to the quadratic form. More precisely, for each sampled edge = (u, v), we define:
X; -x=-- (zu xz)²
qpe
The random variables X; are independent and identically distributed, and the expectation of each X; is:
E[X;] - Lx 1 m q
4
where yr = Lx is the quadratic form of the original Laplacian.
Bounding the Range of X,, To apply concentration inequalities, we need to bound the range the random variables X,, The maximum possible value of X; occurs when the difference (z xx)) is maximal, i.e..
(In x ||C2||
EB
where C' E mmx" is the signed incidence matrix of the graph. Therefore, each X; is bounded as:
s X; S pPmin
|Crx|
where Pmin mineeE Pe represents the minimum sampling probability. Variance Bound. The variance of each X; is bounded as:
Var(X,) < E[X?] < |C22
q q2pii
Summing over all sampled edges, the total variance is:
9: 1|
Var Σ Xi = Var(X1) S
q p2p
Therefore, the standard deviation is:
||Cx| 12 9/2 /1/2pmin Pmin
<
Application of Hoeffding's Inequality. We now apply Hoeffding's 's inequality to bound the probability that the sum deviates
from its expectation:
9
211
IP
M (x. E(x.I)
>t < 2 eexp
E4 (b: a;)²
Substituting the bounds on X,, we get:
-2 min
P
Σ (X, E(X,))
>t < 2 exp
||xx
im
14

---

Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification
|| Pmo C
Conclusion. Let = eje and n
Then the probability becomes:
-2c
( - x." Lx > (u) S 2exp
1i2
Thus, by choosing 2 x²= 2.a
log 8, we ensure that
T Lx x= Las S Ex L
with probability at least 3/4, which completes the proof.
D.2. Proof of Theorem 4.2
Proof. This proof builds upon the techniques introduced by Spielman & Srivastava (2008).
Let C' E Rmxx be a signed incidence matrix defined such that Ce.v = 1 if is the head of edge e, Ce.v = -1 v is the tail of edge e, and Ce otherwise. Consequently, the Laplacian can be expressed as I= CT C. This allows us denote the Laplacian of the sparsifier as L = CT SC, where S is a diagonal matrix with Se,e = de., and Se represents the number of times edge is sampled.
Since G is connected graph, the multiplicity of the eigenvalue 0 is and we express the pseudoinverse of
uau
Using the pseudoinverse, the effective resistance between nodes and can be calculated follows:
Ruy = (Iu LL, Lo),
where the vector 1, an indicator vector, with the w-th element equal to 1 and all other elements equal to 0. Based on this definition, we can represent the effective resistance matrix as
= CL+CT,
where the diagonal entries are given by &e,e Rg. Next, we introduce the following lemma:
Lemma D.1. Let be probability distribution over r C Rd such that for all y E S2 y S v, and | (Pll S 1. Let 31 ................................ be independent and identically distributed samples drawn from p. Then
log
R
youl
Eyy"
< min
1)
9
where e is a constant.
We will apply the above lemma to E $$$ 4Φb1. Note that 4S$ can be expressed as
T
$$Φ
Σ
De E
Le
(4)
Pe
Pe
for drawn independently from the distribution follows:
ti with probability Pe- We compute the expectation of yリ as vp
Eyy" T
Σ
Pe _ $ $T
=-=-
(5)
Pe
15

---

Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification
The last step follows from the fact that & is projection matrix, which can be derived follows:
hh =
= LL* =L = +
(6)
The first equation uses the definition of = CT C, while the second equation follows from the fact that L Ei= u.u! which indicates that I,+ is identity the image of L=+, i.e., I.+ ITI++ I,+.
Next, to apply Lemma D.I, we calculate |[Eyy" ||2 and the upper bound of ||vll2. Since & is projection matrix, its eigenvalues are either 1 or 0. To determine the multiplicity of 1, consider vy E ii(('), there exists a vector r 1 ker(C) such that Ca = We have
by = CL+C Cz = CL+ = Cx = ys
which suggests that im(C) S (m( It is easy to see that im( im(CL+ C*) C im(C). We can conclude that iC) = imm()) ()).
Since a positive semidefinite matrix, we derive
T x² C 1Cx1
(8)
which implies that ker(L) ker(C) and iC) im(L). Given that G is connected, dim(L) dim(C) n 1. Combining this with im(C) im ()), we have dim( dim
1, so the multiplicity of is n 1. Hence, 1, which gives
know the norm ||Eyy" ll2 ||d112 1. tr( n - 1, and Ee R. ir(()
(1+ S.)
Rs
R.
Pe Ee (1 + Se'
S Ee 2p
(9)
2(n - 1)
We also have bound on the norm of y: |1 |e .2ll22 S By setting q 1662 log n/e², arrive
1 vPc
Vope = /2(n 1}. Now we are ready to apply Lemma D.I.
llo (ononnoogn22)2(0 1)
/2c
B1 a Σ
Eyw S c
(10)
16c2n log
4
Using Markov's inequality, we get
1054 +211 Se
(11)
with high probability. Hence, with high probability, we have $ 2 S c. This leads to the following equivalence: Since | 2 S c, that is to say
y DW 1)byl (1)obl <e
sup yERm
y"y
Now, consider the case Vx E IR ker(C), so Cx E Rm and Cx * 0. We have
xTC ("- Se
sup xER (C)
xTC
Recall that Vy E im(C), by (Eq. (7)), thus we can substitute 4Cx with Cx, leading to
x" CF (1-
x x" Lx
sup xER" (C)
Cx
sup x
x T
S.
XER"
Rearranging this inequality yields the desired result for & ker(C). For ker(C), is trivial since x =x= = x 0.
By the equivalence between |4 क S c and |x" 1'-xx"1A -xxxxxxx Lxd
< and using the inequality
Lx
V2
PP (11 (111 (1- (1 Tx 21
for q = 16c2n log n/e2, we conclude the proof.
16

---

Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification
Sensitivity Analysis
80
Performance
60
40
10, 8-0.5
a= B=1.0
a 25, B 0-5.5
2- B-1.0
Std of Accuracies
Cora
CiteSeer
Texas
Coreel
Wisconsin
Chameleon
Enzymes
Imdi
Mutag
Proteins
Figure 4: Hyperparameter sensitivity analysis on real-world datascts.
E. Determining Ei|
||Call |= where ||Cx||2 xT''a Læ depends the choice of æ. Here, we select the leading eigenvector of G'
Note that x. to calculate k, as our goal is to improve connectivity in the latent graph G₁, which requires significantly boosting the small eigenvalues. Using an eigenvector associated with the small eigenvalues of might make the small eigenvalues of G and G1 too similar, resulting in limited improvement connectivity.
< log 8, we estimate [Ei] by solving the following problem. Suppose we apply sparsification After calculating x and q = 227 on latent graph G2 by sampling q random edges with replacement, and observe |E) distinct edges in the sparsified graph. The question is: what is the expected value of Frrl the number of edges in the latent graph? To simplify this computation, assume uniform edge probability distribution. Specifically, let denote the expected value of Er]. Then, we have
| = x (1 11- (1 1 (1-1x111111
)-
(12)
Solving this equation yields k = r EE
F. Additional Experimental Results
F.1. Hyperparameter Sensitivity Analysis
Table 9 presents the results of a node classification task for sensitivity analysis of the hyperparameters a and B. For each node count (20, 200, and 2000 nodes) and homophily level (high and low), classification accuracy is evaluated across various combinations of a and 3. The analysis shows that the classification accuracy is relatively stable and not highly sensitive to variations in these hyperparameters:
Alpha (a):
For smaller graphs (e.g., 20 nodes), larger values of a (0.15|E)) are generally preferred, as more aggressive densification appears to improve classification performance in smaller networks.
For larger graphs (e.g., 200 and 2000 nodes), the classification accuracy remains consistent across values, with a slight tendency for smaller a (0.05) to perform better. This suggests that less aggressive densification is sufficient for improving the connectivity of larger networks.
Beta (3):
For high homophily, larger values of 3 (e.g., 1.0) are generally preferred, as they help preserve the community structure by retaining more edges during sparsification.
- For low homophily, smaller values of 3 (c.g., 0.5) tend to perform better, as sparser graphs better reduce noise introduced by inter-community edges.
17

---

Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification
Mutag
Cregrna Grupth
Oragrnal Gragr
CDKJ
GOKi
SURF LASER
SDRF
LASER
Densty
CIH
Densaty
GTR
Effecliv Resistance
Efeecive Resistance
Mutag
Proteins
1.0
GOKU
1.0
GOKU
0.8
0.8
-MNAA
LASER
LASER
0.6
0.0
0.4
0.2
0.2
0.0
10
15
26
30
35
Eigenvalue Index
Eigenvalue Index
Figure 5: Trade-off between preserving spectrum and reducing ER.
We also present hyperparameter sensitivity analysis results on real-world datasets in Figure 4. Overall, the results demonstrate that classification accuracy is not very sensitive to changes a and / values within reasonable ranges. This suggests that GOKU's performance remains stable across a wide variety of hyperparameter settings, and the method is robust to changes densification and sparsification levels.
F2. More Visualization Results
Figure 6, we present additional visualizations spectral distributions for randomly selected graphs from the Mutag, IMDB, and Proteins datasets. Across datasets, consistent pattern emerges: GOKU demonstrates the highest fidelity preserving the original graph spectra. This result underscores its effectiveness in striking balance between enhancing connectivity and maintaining the structural integrity of the graph. By preserving spectral properties more effectively than alternative methods, GOKU ensures that key graph characteristics remain intact while improving overall connectivity.
Additionally, we provide Figure 5 for the trade-off' between preserving spectrum and reducing ER.
18

---

Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification
Nodes Homophily Hyperparameters (a, .)
Classification Accuracy
( 1.0)
0.8765
(0.15 0.7)
0,8617
(0.15 0.5)
0,8541
(0.1 1.0)
0.8541
20 High
(0.1 0.7)
0,8392
(0.1 0.5)
0,8112
(0.05
0,8321
(0.05
0.8295
E
0.8189
(0.15 2 1.0)
0.5734
(0.15 0.7)
0.5630
(0.15 (.5) 0.5)
0.6334
(0.1 1.0)
0.5134
20 - Low
(0.1 0.7)
0,5231
(0.1
0,5975
(0.05 1.0)
0,4901
E
0,5156
(0.05 0.5)
0.5967
(0.15 1.0)
0.9173
(0.15 E 0.7)
0,8851
(0.15 0.5)
0.9540
(0.1 1.0)
0,9540
200 High
(0.1 F. 0.7)
0.9545
(0.1 0.5)
0,9632
(0.05 1.0)
0.8625
(0.05
0.8321
EI
0.7947
(0.15 1.0)
0.5850
(0.15 0.7)
0.5661
(0.15)
0.6153
(0.1 1.0)
0.5534
200 Loo
(0.1
0.5513
(0.1
0,6012
(0.05]E),110)
0.4715
(0.05
0,4898
(0.05 0.5)
0.5973
(0.15 1.0)
0.9207
(0.15)E)
0.8918
(0.15)El 0.5)
0,8781
(0.1
0,9127
2000 High
E0.1
0,8936
(0.1 0.5)
0.8625
(0.05
0.9202
(0.05
0.9282
F).
0.8987
(0.15]
0,5335
(0.15
0,5701
(0.15
0,5934
E0.1
0,5543
2000 Low
(0.1 0.7)
0,5921
(0.1 0.5)
0,5792
(0.05 E 1.0)
0.5213
(0.05 0.7)
0,5462
(0.05 E 0.5)
1.5814
Table Node classification results sensitivity analysis on hyperparameters (a 0.05 F|. 0. F., 0. and
0.5, 0,7, 1.0).
19

---

Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserinng Sparsification
Mutag
Imdb
Proteins
Eigenvalue Distribution Comparison
Eigenvalue Distribution Comparison
Eigenvalue Distribution Comparison
Eigenvalue Magnitude
Eigenvalue Magnitude
Eigenvalue Magnitude
Eigenvalve Index
Eigenvalue Index
Eigenvalue Index
Eigenvalue Magnitude
Eigenvalus Magnituds
Eigenvalue Magnitude
Eigenvalue Index
Eigenvalue Index
Eigenvalue Index
Elgenvalue Magnitude
Elgenvalue Magnituda
Elgenvalue Magnitude
Eigenvalue Index
Eigenvalue Index
Eigenvalue Index
Elgenvalue Magnitude
Elgenvalue Magnitude
Eigenvalue Magnitude
Eigenvalue Index
Eigenvalue Index
Eigenvalue Index
Eigenvalue Magnitude
Eigenvalue Magnitude
Eigenvalue Magnitude
Eigenvalue Index
Eigenvalue Index
Eigenvalue Index
None
GOKU
DR
GTR
LASER
Figure 6: More randomly selected graph spectra visualization results from Mutag, Imdb, and Proteins datasets.
20


Reviews:
[{"review_id": "DARIXEU8ss", "reviewer": "Reviewer_1faH", "summary": "This paper proposes a method to mitigate the over-squashing issue of GNNs while preserving the spectrum of the original graph. To this end, the authors propose a two-stage process of densification followed by sparsification, where both steps are discussed in detail. Experimental results demonstrate the competitiveness of the proposed method across a wide range of datasets against several baselines.\n\n**==Post-rebuttal update==** \n\nI would like to thank the authors for their final response which partially addressed my concerns. On acknowledging this and as an encouragement of the good work from them, I am raising my score to 3. However, I would strongly recommend the authors to further strengthen the motivation of spectrum preservation for future versions of the paper.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their time, effort, and constructive comments. Below are our responses.\n\n> ### **Comment 1**: Why $x^TLx$ as spectral similarity & advantages over degree distribution in SDRF\n\n**Summary**: Our approach defines similarity via the Laplacian quadratic form, aligning with the graph spectral sparsification literature and covering **broader structural properties** beyond degree distribution. \n\nConsider two graph $G$ and $\\\\tilde{G}$ with $(1-\\\\epsilon)x^TLx \\\\leq x^T\\\\tilde{L}x \\\\leq (1+\\\\epsilon)x^TLx$, we have:\n1. **Eigenvalue Similarity**: The relationship $(1 - \\\\epsilon) \\\\lambda _i \\\\leq \\\\tilde{\\\\lambda} _i \\\\leq (1 + \\\\epsilon) \\\\lambda _i$ holds[1].\n2. **Graph Cut Similarity**: The graph cut, $\\text{cut}(G, S) = \\\\sum W(u, v)$, where $u \\\\in S$, $v \\\\in V - S$, and $W(u, v)$ is edge weight. Since $x^T L x = \\\\sum W(u, v) (x(u) - x(v))$, setting $x$ as indicator (1 inside $S$, 0 outside) gives $(1 - \\\\epsilon)\\\\text{cut}(G, S) \\\\leq \\\\text{cut}(\\\\tilde{G}, S) \\\\leq (1 + \\\\epsilon)\\\\text{cut}(G, S)$.\n3. **Degree Distribution Similarity**: For node $u$, setting $x_u = 1$ and $x_v = 0$ for $v \\\\neq u$, we get $x^T L x = \\\\text{deg}(u)$. In other words, $(1-\\\\epsilon)\\\\text{deg}(G)(u) \\\\leq \\\\text{deg}(\\\\tilde{G})(u) \\\\leq (1+\\\\epsilon)\\\\text{deg}_G(u)$ for all $u \\\\in V$.\n4. **Eigenvector Similarity**: By matrix perturbation theory, the eigenvectors $v _i$ and $\\\\tilde{v} _i$ of $L$ and $\\\\tilde{L}$ are close, with $\\\\| v _i - \\\\tilde{v} _i \\\\|_2 \\\\leq \\\\frac{\\\\| L - \\\\tilde{L} \\\\|_2}{|\\\\lambda _i - \\\\tilde{\\\\lambda} _i|}$.\n\nSee SDRF visualization: https://anonymous.4open.science/r/Submission3560_Rebuttal_for_Reviewer_1faH/Fig.pdf\n\n> ### **Comment 2**: Literature review regarding SDRF.\n\nWe appreciate your valuable suggestions and will revise the paper to rephrase them more accurately. Thank you!\n1. **SDRF also considers edge deletion**: We will clarify it to avoid confusion. We acknowledge SDRF does involve both edge addition and deletion, as noted in our paper: \"Curvature-based methods (citing SDRF) optimize connectivity by adding and removing edges.\" A key difference is that **SDRF requires adding and removing nearly the same number of edges to preserve degree distribution**. In contrast, our method allows a large edge reduction while keeping spectral similarity using weighted edges.\n2. **Edge density and over-smoothing.** We agree that increased edge density does not necessarily lead to over-smoothing, as connection patterns also play a role.\n3. **Why stochastic manner to edit edges.** SDRF uses a stochastic mechanism to select edges for addition, and our method extends this by also randomly selecting edges for deletion. **We consider stochastic mechanism a means (not a goal)**. GOKU maintains spectral similarity even with a significant reduction in edge count ($0.5 \\\\leq \\\\beta \\\\leq 1$). This is made possible by spectral sparsification, which relies on stochastic sampling.\n\n> ### **Comment 3**: Spectrum and specific learning tasks & LASER performs well in some cases while not preserving spectrum well.\n\n1. We summarize the **average similarity of eigenvalue distributions** between graphs from the same and different classes below. We use the fastdtw algorithm to compute distance between vectors of different sizes, and sim = $1/(0.01 + dis)$. It shows that **graphs from the same class exhibit more similar spectra**. Preserving spectrum could help classification tasks. Additionally, $x^TLx$ captures important graph anomaly signal, which **helps anomaly detection** [2].\n2. Apart from spectrum, **others such as connectivity also matter**. While LASER distorts the spectrum more than GOKU, it also improves the spectral gap more. GOKU seeks to balance connectivity improvements with spectral similarity, as evidenced by the best overall performance.\n\n|  | Same class| Diff |\n| -- | --| --|\n| IMDB  | 0.59 | 0.21 |\n| MUTAG | 0.58| 0.23 |\n| PROTEINS | 0.13  | 0.05 |\n| ENZYMES | 0.05 | 0.03 |\n\n> ### **Comment 4**: Notations, $G$ and $G_d$ are confusing at times.\n\n$G_d$ is not an input to either the densification or sparsification processes, but a **candidate latent graph**. $G$ represents the input graph fed into the rewiring process. In densification, given $G$, we aim to find a latent graph $G_l$ that maximizes the probability as $G_l = \\\\arg \\\\max P(\\\\phi(G_d) = G)$, where $G$ is the actual input.\n\n> ### **Comment 5**: Why two-stage approach.\n\nThe two-stage approach is **simple and practical**: in densification, when adding edges (Eq. 3, $\\prod_{e \\\\in E} (1 - (1 - p_e)^q)^{w_e} \\\\prod_{e' \\\\in E'} ((1 - p_{e'})^q)^{\\\\bar{w}}$), we assume original edges $E$ are preserved, so we only need to find the $E'$ that maximizes the objective from the complement graph. However, allowing edge removal adds complexity, as we must also find an optimal subset from $E$ to delete.\n\n[1] Spectral sparsification of graphs: theory and algorithms.\n\n[2] Rethinking GNNs for Anomaly Detection.", "claims_and_evidence": "The authors claimed “..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..” - I wonder if the authors can elaborate on why learning tasks may benefit from preserving spectral properties, given this is a main motivation?\n\nThe authors claimed “..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 oversmoothing..” - first I think methods such as SDRF can actually maintain the edge density via the addition/deletion mechanism; second I also don’t think the single factor of increased edge density would necessarily lead to over-smoothing being more likely. Both should be carefully rephrased.\n\nThe authors claimed “..while these approaches improve connectivity, they often substantially change the topology, overlooking the significance of retaining the graph structure..” - again I don’t think SDRF change the graph topology substantially, actually it preserves the degree distribution pretty well (according to Fig.4 of that paper). \n\nThe authors claimed “..rather than deterministically selecting edges based on predefined connectivity metrics, our method employs a probabilistic edge modification strategy” - to my knowledge SDRF also involves a stochastic mechanism to select which edge to add.", "methods_and_evaluation_criteria": "In 3.2 the authors mentioned several advantages of the proposed framework over existing methods, which are however not very clear to me: \n- why do we necessarily want to preserve spectral properties? This needs to be discussed in more detail with respect to specific learning tasks. \n- why do we need to follow a two-stage approach of densification and sparsification? Can we not consider an optimisation problem that solves for an optimal graph topology at once? This needs to be better justified conceptually.\n- Why is it desirable to choose edges to modify in a stochastic manner? What’s the benefits of doing this over a deterministic method?\n\nThe authors defined being “spectrally similar” in Definition 2.1 as having similar Laplacian quadratic form, but I am not sure if this actually preserves the Laplacian eigenvalues? I would imagine something like the spectral distance (norm of difference of the two vectors corresponding to the two sets of Laplacian eigenvalues) would be more appropriate as a measure of similarity.", "theoretical_claims": "Theoretical claims seem correct to me.", "experimental_designs_or_analyses": "Can the authors explain why the performance of GOKU in Table 1 and 2 can be attributed to preserving spectral properties? \n\nActually, methods such as LASER can still perform quite well on some datasets (in Table 2) while distorting the spectrum more so than GOKU. Can the authors explain this more? \n\nWhy is SDRF not shown in Fig.2? As mentioned above, it can actually preserve the degree distribution (hence probably the spectrum) pretty well. If this is true, its average performance in Table 1 and 2 actually indicates preserving spectrum isn’t always contributing to better performance. Can the authors comment on this?", "relation_to_broader_scientific_literature": "The paper contributes to a growing literature of GNN methods developed to address the over-squashing issue. The main differences from and advantages over the existing methods are, however, not very clear to me. See [Methods And Evaluation Criteria] for more details.", "essential_references_not_discussed": "The references seem adequate to me.", "other_strengths_and_weaknesses": "Strengths: \n- the paper tackles a timely problem\n- the proposed framework is conceptually interesting\n- the paper is relatively well written and clear to follow\n\nWeaknesses:\n- the proposed framework can be better motivated and justified\n- certain claims are not accurate and should be rephrased\n- experimental results need more discussion in relation to core motivation\n\nPlease see detailed comments above.", "other_comments_or_suggestions": "The notations are confusing at times. For example, in some part of the paper the input graph is denoted as G while in other part denoted as G_d. Then expression such as \\phi(G_d)=G makes it even more confusing.", "questions_for_authors": "See above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wjLDFUVqJo", "reviewer": "Reviewer_geiv", "summary": "This paper introduces GOKU, a novel graph rewiring method that mitigates over-squashing in Graph Neural Networks through a two-phase densification-sparsification paradigm. The approach first identifies and adds critical missing edges to alleviate bottlenecks via inverse spectral sparsification, then selectively removes less important edges to maintain sparsity while preserving spectral properties. The results demonstrate that GOKU outperforms existing rewiring methods on multiple node and graph classification tasks.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their time, effort, and constructive comments. Below are our responses.\n\n> ### **Comment 1 (Claims And Evidence 2, Theoretical Claims 2&3)**: Lack of probability bounds, impact of feature similarity in Theorem 4.2 & feature similarity term in ISS (Algorithm2)\n\n- For $q= 32c^2n\\\\log n/\\\\epsilon^2$, the lower bound is $3/4$.  \n- Theorem 4.2 already accounts for feature similarity (**Eq. 9** in Appendix). \n- We don't prioritize feature similarity. For instance, given edges $a$ and $b$ with $S_a=1,R_a=0.5$ and $S_b=0.5,R_b=1$, we have sampling probabilities proportional to $(1+1)*0.5=1$ for $a$ and $(1+0.5)*1=1.5$ for $b$.\n\n> ### **Comment 2 (Claims And Evidence 1 & Experimental Designs 2)**: Time complexity\n- We discuss the time complexity of approximating ER in Sec. 4.3 as $\\\\mathcal{O}(m \\\\cdot \\\\text{poly}(\\\\log n)/\\\\delta^2)$, where $\\\\text{poly}(\\\\log n)$ is a polynomial in $\\\\log n$.  \n- If $|E'|$ is too large, $\\\\mathcal{O}(|E'| m)$ is not sublinear. However, this is not an issue in practice: in dense graphs, we don’t need large $|E'|$ to achieve good connectivity. In sparse graphs (small $m$), large $|E'|$ won’t significantly increase $|E'| m$. For Tables 1 and 2, we chose $|E'|$ from \\{5, 10, 15, 20, 25, 30\\}.\n\n> ### **Comment 3 (Weaknesses 2, Suggestions 1 & Claims And Evidence 3)**: Measurement of reduction in over-squashing & quantitative measurements of spectrum similarity\n* We measure the reduction in over-squashing by comparing **pairwise ER** between the original and rewired graphs in **Fig. 3**, which shows that ER values decrease post-rewiring. \n* Smaller ER $R_{u,v}$ leads to larger $\\\\left\\\\| \\\\frac{\\\\partial h_u^{(r)}}{\\\\partial x_v} \\\\right\\\\|$(Black, Mitchell, et al.) the same metric as in Di Giovanni et al. Smaller $R_{u,v}$ also implies more and shorter paths. \n\nSee visualization: https://anonymous.4open.science/r/Submission3560_Rebuttal_for_Reviewer_geiv/Fig.pdf\n\n> ### **Comment 4**: Not discussed references\n\nWe mainly focused on rewiring-based work in the submission. Thanks for providing these excellent references! We will discuss them in the revision.\n\n> ### **Q1**: $\\\\alpha$ and $\\\\beta$ search spaces\n  \nApologies for any confusion. The search spaces for $\\\\alpha$ and $\\\\beta$ in page 7 apply to Tables 1 and 2. \n- **$\\\\alpha$ in the Appendix**: Table 8 analyzes $\\\\alpha$ sensitivity, not GOKU vs. baselines. For the 2000-node, 80k-edge graphs, a small search space for $\\\\alpha$ (5 to 30) is too limited for capturing meaningful difference. We use $0.05|E|, 0.1|E|, 0.15|E|$ for this reason. \n- **$\\\\beta$ values**: For the main experiments, we use $\\\\{0.5, 0.6, 0.7, 0.8, 0.9, 1.0\\\\}$. For Table 8, we use $\\\\{0.5, 0.7,1.0\\\\}$ to avoid an overly large table while capturing key trends.\n\n> ### **Q2**: Sensitivity studies  \n\nWe summarize the average accuracy across $18 = 3 \\\\times 6$ settings in Table 8:  \n- $\\\\alpha = (0.05|E|, 0.1|E|, 0.15|E|)$: 0.705, 0.728, 0.731  \n- $\\\\beta = (0.5, 0.7, 1.0)$: 0.730, 0.717, 0.705  \nThe variances of the average accuracies are relatively small.\n\n> ### **Q3**: USS\n  \nUSS assigns **low probabilities to important edges**, often leading to their removal. However, we don't apply USS directly; instead, we reverse the process (densification) to reintroduce important edges, mitigating over-squashing.\n\n> ### **Q4**: Range of $\\\\beta$\n  \nTo ensure efficiency, we constrain $\\\\beta \\\\leq 1$ to avoid denser output graphs than input. We set $\\\\beta \\\\geq 0.5$ empirically to prevent overly sparse graphs and reduce the hyperparameter search space.\n\n> ### **Q5**: ER Approximation error $\\\\delta$\n \nThe error bound $1 \\\\pm (1+(\\\\delta))\\\\epsilon$ can be derived by scaling $p_e$ as in Eq. 9 of the Appendix. Our experiments show minimal performance drops for $\\\\delta = 0.4$ compared to Table 1($\\\\delta=0.1$).\n\n||Cora|Texas|Mutag|\n|-|-|-|-|\n| $\\\\delta=0.4$|↓0.3|↓0.5|↓1.2|\n| $\\\\delta=0.7$|↓0.6|↓1.2|↓2.6|\n| $\\\\delta=1.0$|↓0.4|↓2.8|↓2.4|\n\n> ### **Q6**: ER changes in Fig. 1\n  \nSparsification is not meant to further improve connectivity after densification. ER increases when edges are removed (Rayleigh Monotonicity). There is a trade-off: as discussed in **Page 8**, sparsification provides two benefits: reducing edge density and retaining spectral similarity. **Fig. 1** shows that sparsified graph has a more similar spectrum to the original graph.\n\n> ### **Q7 & Q8**: Newly added edges survival \n\nWhile sparsification may remove newly added edges, they are assigned higher sampling probabilities during sparsification as they are topologically important. We computed the survival rate using the three datasets mentioned above. Over 90% of these edges were retained after sparsification.\n\n> ### **Q9:** reversing the order of DSR\n\nWe have not explored reversing the order of densification and sparsification. If we apply sparsification first, we have to densify a weighted graph, which is more diffcult. We leave this interesting question for future work.", "claims_and_evidence": "1. The paper claims that GOKU has \"nearly linear time\" with respect to the number of nodes and edges. However, it lacks a thorough explanation of how the complexity of approximate Effective Resistance calculations affects the overall complexity.\n\n2. While the paper emphasizes spectrum preservation, the actual implementation appears to prioritize feature similarity in the sparsification process. This suggests the possibility that it optimizes other objectives (e.g., improved homophily) rather than purely preserving the spectrum.\n\n3. Although the paper emphasizes theoretical guarantees for spectrum preservation, the visualization of spectrum comparisons in Section F.2 provides only qualitative assessment without quantitative measurements (e.g., spectral similarity metrics).", "methods_and_evaluation_criteria": "The paper claims that GOKU outperforms existing methods on several datasets, which is well supported by extensive experimental results in Tables 1, 2, and 7.", "theoretical_claims": "1. In Section 4.1, the authors acknowledge the difficulties of MLE calculation and propose a simplified approach, but there's a lack of theoretical guarantees regarding how accurately this simplified approach solves the original MLE problem.\n\n2. Theorem 4.2 claims to guarantee spectral similarity with high probability, but doesn't present specific probability bounds (only expressed as \"with high probability\").\n\n3. In the ISS algorithm, the theoretically proposed probability distribution is modified by additionally considering feature similarity. It appears that the impact of this modification on the guarantees in Theorem 4.2 is not analyzed.", "experimental_designs_or_analyses": "1. Reporting that hyperparameters are not sensitive without providing sensitivity studies for alpha and beta lacks persuasiveness.\n\n2. The paper claims GOKU has \"nearly linear time\" with respect to nodes and edges, but doesn't explain in detail how the complexity of approximate Effective Resistance calculations affects the overall complexity. Particularly, can $\\mathcal{O}(|E'|m)$ be considered linear complexity when $|E'|$ is large?", "relation_to_broader_scientific_literature": "The DSR represents a conceptual shift in graph rewiring approaches:\n\n- Unlike previous methods that either only add edges (Karhadkar et al., 2023) or only modify existing ones (Barbero et al., 2024), DSR employs a two-phase process. This connects to optimization literature, where intermediate relaxations are used before refinement to final solutions.\n- The paper addresses the tension between connectivity enhancement and over-smoothing risk, similar to how ProxyGap (Jamadandi et al., 2024) leverages the Braess paradox to show that removing edges can sometimes improve connectivity. GOKU's approach aligns more with the recent LASER rewiring (Barbero et al., 2024), which also aims to maintain aspects of the original graph structure.", "essential_references_not_discussed": "PR-MPNN [1], which proposes a rewiring strategy that structures the graph according to downstream tasks and underlying data distribution, is missing. Studies that improve message passing methods without relying on rewiring are also omitted. For instance, there should be discussion of Co-GNN [2], which learns behavior when updating node features, or PANDA [3] and GESN [4], which aim to mitigate over-squashing according to model characteristics while avoiding rewiring methods.\n\n> [1] Qian, Chendi, et al. \"Probabilistically rewired message-passing neural networks.\" ICML 2024\n>\n> [2] Finkelshtein, Ben, et al. \"Cooperative Graph Neural Networks.\" ICML 2024.\n>\n> [3] Choi, Jeongwhan, et al. \"PANDA: Expanded Width-Aware Message Passing Beyond Rewiring.\" ICML 2024\n>\n> [4] Tortorella, Domenico, and Alessio Micheli. \"Leave Graphs Alone: Addressing Over-Squashing without Rewiring.\" The First Learning on Graphs Conference.", "other_strengths_and_weaknesses": "**Strengths**\n\n1. This paper introduces a paradigm that aims to solve over-squashing, maintain graph sparsity, and preserve spectral properties.\n\n2. The method proposed by the authors consistently demonstrates performance improvements, particularly on heterophilic graphs.\n\n**Weaknesses**\n\n1. GOKU has a disadvantage that, unlike other previous studies, sparsification and densitification must be performed separately.\n\n2. Despite being the primary motivation, this paper lacks direct measurements of over-squashing and instead relies on classification accuracy.\n\n3. The hyperparameter explanations for $\\alpha$ and $\\beta$ are inconsistent. Specifically, for $\\alpha$, it is described on page 7 as $\\alpha \\in \\{5, 10, 15, 20, 25, 30\\}$, but in the Appendix it appears to use 0.05, 0.1, 0.15. For $\\beta$, page 7 only considers 0.5 and 1.0, but the Appendix considers 0.5, 0.7, and 1.0.\n\n4. The authors explain the process of adding edges during the densification phase and then deleting edges during the sparsification phase, but authors do not provide specific analysis on how many of the newly added edges are retained or deleted, or by what criteria. Moreover, even in the experimental section of the paper, there is no analysis of the survival rate of newly added edges or their role in the final graph.", "other_comments_or_suggestions": "1. The paper states that it aims to solve the over-squashing problem, but the experimental evaluation mainly focuses on classification accuracy. There is a lack of direct measurement of how much over-squashing has actually been reduced. More appropriate evidence would be measuring signal propagation to distant neighbors (as in [5] and [3]) or providing theoretical bounds on over-squashing sensitivity.\n\n2. Could a more appropriate explanation be added for the ER change process from 1.5 → 0.3 → 0.5 in Fig 1? It would be helpful to better explain the intuition behind why it increases again from 0.3 to 0.5 after sparsification.\n\n3. It would be beneficial if the authors could analyze which newly added edges and which of those added edges ultimately remain after sparsification.\n\n> [5] Di Giovanni, Francesco, et al. \"On over-squashing in message passing neural networks: The impact of width, depth, and topology.\" ICML 2023.\n>\n> [3] Choi, Jeongwhan, et al. \"PANDA: Expanded Width-Aware Message Passing Beyond Rewiring.\" ICML 2024", "questions_for_authors": "1. For $\\alpha$, on page 7 it is described as $\\alpha \\in \\{5, 10, 15, 20, 25, 30\\}$, but in the Appendix it appears to use 0.05, 0.1, 0.15. For $\\beta$, page 7 only considers 0.5 and 1.0, but the Appendix considers 0.5, 0.7, and 1.0. Could you clarify these hyperparameter specifications?\n\n2. On page 16, you state that \"Overall, the results demonstrate that classification accuracy is not very sensitive to changes in $\\alpha$ and $\\beta$ values within reasonable ranges.\" Could you report sensitivity studies on alpha and beta with finer granularity to confirm they are truly not sensitive?\n\n3. On page 5, line 260, you state \"The USS method should assign low probabilities $p_e$ to edges crucial for maintaining connectivity.\" Shouldn't important edges be assigned high probabilities? Looking at Algorithm 1, it seems designed to assign low probabilities to them.\n\n4. Why is the range for $\\beta$ set as $0.5 < \\beta ≤ 1$? Is there a rationale for this specific range?\n\n5. You mention that setting $δ = 0.1$ results in an error of $(1 ± (1 + δ)ϵ)$. Could you analyze how this approximation error affects the overall algorithm performance?\n\n6. In Fig 1, the ER changes from 1.5 → 0.3 → 0.5. Why does it increase again from 0.3 to 0.5 after sparsification?\n\n7. The example in Fig 1 shows that newly added edges can be removed again by sparsification. Does this happen in your actual experiments?\n\n8. Could you analyze which newly added edges ultimately remain after the sparsification phase in your experiments?\n\n9. Have you tried experimenting with reversing the order of densification and sparsification?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nVKJsXE2uj", "reviewer": "Reviewer_yvpT", "summary": "This paper addresses the issue of over-squashing in Graph Neural Networks (GNNs) by introducing a novel approach called the **Densification-Sparsification Rewiring** framework, with a practical implementation termed **GOKU**. The main contribution of the paper is the proposal of a two-step rewiring process: \n\n1. Densification: This step applies an **unimportance-based sparsification** algorithm to solve an inverse spectral graph sparsification problem, aiming to improve graph connectivity.\n2. Sparsification: The second step uses an **importance-based sparsification** algorithm, ensuring the graph remains sparse but retains crucial connectivity. \n\nThe combination of these two steps allows GOKU to preserve both the graph’s spectral properties and density while improving overall connectivity, which helps mitigate the problem of over-squashing in GNNs.\n\nIn addition to the framework, the authors provide theoretical results that guarantee spectral preservation and include a time complexity analysis to demonstrate the efficiency of GOKU. The paper supports these contributions with extensive experiments on node and graph classification tasks, ablation studies, and visualizations of graph spectra. These experiments show that GOKU is a promising solution for better graph rewiring in GNNs.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their time, effort, and constructive comments. Here are our responses.\n\n### **Comment 1**: Choices of Spectral Sparsification Algorithms\n\nWe appreciate the reviewer’s interest in the choice of spectral sparsification algorithms. It is important to note that our approach is designed to be algorithm-agnostic, meaning it does not rely on any particular sparsification method. However, we acknowledge that different algorithms may offer distinct advantages, and we discuss two such algorithms here as representative examples. Other similar algorithms can also be considered within our framework.\n\n1. **Algorithm 1**: Algorithm 1 is designed to selectively increase the smaller eigenvalues while maintaining the larger ones. This is particularly important when the goal is to approximate the spectral properties of the graph. In **Theorem 4.1**, we show that for any vector $x$, the following inequality holds:\n   $$\n   (1 - \\\\epsilon) x^T L x \\\\leq x^T \\\\tilde{L} x \\\\leq (1 + \\\\epsilon) x^T L x\n   $$\n   This result is conditional on $\\\\kappa = \\\\kappa(x)$, which is a function of the eigenvector $x$. Specifically, we choose the leading eigenvector $x_l$ (corresponding to the largest eigenvalue) and derive the minimum required sampling count, $q \\\\geq \\\\frac{\\\\kappa(x_l)^2}{2\\\\epsilon^2} \\\\log 8$. This derivation focuses on ensuring that the larger eigenvalues are preserved, while the smaller eigenvalues are not explicitly accounted for in this process. \n\n2. **Algorithm 2**: This algorithm assigns higher probabilities to edges with larger effective resistance, which is aligned with our objective of preserving important edges during the sparsification process. We believe this approach is well-suited to maintain key structural properties of the graph. The algorithm presented in [1] is one such effective candidate for implementing Algorithm 2, but we note that other algorithms with similar principles could also be used within the framework of our method.\n\n---\n\n### **Comment 2**: Randomness in Sampling\n\n\nOur theorems explicitly account for the randomness in the sampling process by providing probability lower bounds for the properties of the sampled graphs. Specifically, once the sampling count $q$ exceeds a certain threshold, we show that the generated graphs exhibit the desired spectral properties with high probability. These theoretical results ensure that, despite the inherent randomness in the sampling, the method remains reliable and effective.\n\nTo further substantiate the reliability of our approach, we conducted extensive empirical validation. As shown in **Tables 1 and 2**, our results are based on the average of 100 independent runs with different random seeds. This approach allows us to assess the variability and consistency of our algorithm. The results demonstrate that the confidence intervals of our algorithm are comparable to those of deterministic methods, which reinforces the robustness of our approach despite the use of random sampling.\n\nWe believe that these empirical and theoretical analyses collectively validate the effectiveness of our algorithm, providing confidence in its consistency and reliability.\n\n---\n\nWe again thank the reviewer for the constructive feedback and valuable suggestions. Please do not hesitate to reach out if any further clarifications are needed.\n\n---\n### References \n[1] Spielman, Daniel A., and Shang-Hua Teng. \"Spectral sparsification of graphs.\" SIAM Journal on Computing 40.4 (2011): 981-1025.", "claims_and_evidence": "The claims are supported by experimental results and thorough analyses.", "methods_and_evaluation_criteria": "The proposed method appears effective in addressing the over-squashing problem while maintaining spectrum similarity between the original and rewired graphs. The authors used various datasets including on both node and graph classification to comprehensively evaluate the proposed method.I have roughly reviewed the proofs of the main theorems, and they appear to be sound.", "theoretical_claims": "I have roughly reviewed the proofs of the main theorems, and they appear to be sound.", "experimental_designs_or_analyses": "The paper evaluates the method from multiple perspectives, including performance, rewiring effects on graph structure, and efficiency, using both homophilic and heterophilic node classification datasets, as well as graph classification datasets. Especially, the classification experiments and spectral visualizations effectively demonstrate that the proposed method meets its goals of improving connectivity and preserving graph spectra.", "relation_to_broader_scientific_literature": "The proposed method offers a potential new paradigm for graph rewiring techniques, specifically addressing the over-squashing issue while preserving the spectral properties of the original graphs. This contribution builds on prior work by integrating spectral considerations into graph rewiring, an aspect that has not been fully explored in previous methods.", "essential_references_not_discussed": "Related works are adequately discussed in the paper, including literature on graph rewiring, graph scarification, and other relevant graph neural network studies.", "other_strengths_and_weaknesses": "***Strengths***\n\n- The originality of the method lies in its ability to integrate spectral preservation into the graph rewiring process, along with a novel design of inverse graph sparsification, which is both interesting and promising.\n- The experimental evaluation is comprehensive, utilizing both homophilic and heterophilic node classification datasets, as well as graph classification datasets, to thoroughly assess the method’s performance.\n- The paper is well-written and easy to follow.\n- Extensive experimental results validate the effectiveness of the proposed method in improving connectivity and preserving spectral properties.\n\n\n***Weaknesses***\n\n- The authors use two specific spectral sparsification algorithms (Algorithm 1 and Algorithm 2), but the reasons for selecting these particular algorithms are not sufficiently discussed. It would be helpful for the authors to explain why these algorithms were chosen over others. Can these algorithms be replaced with alternative spectral sparsification methods? \n\n- The GOKU method relies on random sampling, but the potential impact of this randomness on the quality and properties of the rewired graphs is not fully explored. A more detailed analysis of how random sampling may affect the consistency and reliability of the rewired graphs would strengthen the paper's conclusions.", "other_comments_or_suggestions": "N/A.", "questions_for_authors": "See weaknesses part.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "I7aWIjpKwe", "reviewer": "Reviewer_EEAT", "summary": "This papers proposes a method a rewiring technique for graph neural networks called GOKU. The goal of GOKU is to improve the connectivity of the graph (as measured by the effective resistance) while maintaining the structure of the graph (as measured by the Laplacian spectrum). GOKU takes a two step approach: first, it uses a heuristic to reverse a sparsification process that is more likely to remove edges important for connectivity (in other words, this reverse sparsification will add edges back to the graph that improve connectivity). Then, it performs a variant of spectral sparsification on this densified graph that also aims to keep edges between vertices with similar features. The authors empirically test the ability of GOKU to preserve the Laplacian spectrum while decreasing effective resistance. Finally, the authors test compare GOKU to other rewiring algorithms as a pre-procesing step for graph neural networks.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their time, effort, and constructive comments. Below are our responses.\n\n> ### **Comment 1**: Preserve all eigenvalues and the smallest eigenvalues are not increased in theoretical & experimental results\n\nOur method indeed increases the smallest eigenvalues. Here is a more detailed explanation:\n\n1. **Theoretical Results.** In Theorem 4.1, we show that $(1 - \\\\epsilon) x^T L x \\\\leq x^T \\\\tilde{L} x \\\\leq (1 + \\\\epsilon) x^T L x$ holds conditional on $\\\\kappa = \\\\kappa(x)$, **a function of the eigenvector $x$**. Specifically, we choose the leading eigenvector $x_l$ (with the largest eigenvalue), and derive the sampling count $q \\\\ge \\\\frac{\\\\kappa(x_l)^2}{2\\\\epsilon^2} \\\\log 8$. This derivation focuses on preserving the larger eigenvalues and does not account for the smallest eigenvalues.\n\n2. **Experimental Results.** Our experiments do show that the smallest eigenvalues are increased. However, due to the **large range** of eigenvalues, particularly the largest eigenvalue, observing this increment directly can be challenging. For instance, in Figure 2 (right), the spectral gap increases from nearly 0 to 0.5. Given that the largest eigenvalue is around 14, this makes the smallest eigenvalue changes **difficult to observe**. To make this clearer, we will include a zoom-in on the smallest eigenvalues for better visualization.\n\n---\n\n> ### **Comment 2:** How to reduce Effective Resistance (ER) While Preserving Eigenvalues\n\nNote that the total ER, $R_{\\\\text{tot}} = n \\\\sum_{i=2}^n \\\\frac{1}{\\\\lambda_i}$, is **sensitive to smallest eigenvalues**. For example, as shown in Figure 2 (right), the largest eigenvalue is approximately 14, contributing only $\\\\frac{1}{14}$ to $R_{\\\\text{tot}}$. On the other hand, the second smallest eigenvalue $\\\\lambda_2 = 0.05$ contributes significantly more ($\\\\frac{1}{\\\\lambda_2} = 20$). By increasing the smallest eigenvalue, for instance, to $\\\\lambda_2 = 0.5$, its contribution reduces to 2. Hence, by slightly increasing a few of the smallest eigenvalues, we can significantly reduce $R_{\\\\text{tot}}$, while maintaining a similar spectrum for others.\n\nSee visualization for this trade-off on a single graph: https://anonymous.4open.science/r/Submission3560_Rebuttal_for_Reviewer_EEAT/Fig.pdf\n\n---\n\n> ### **Comment 3:** Ablation Study on $S_e$\n\nWe provide the following clarifications for the impact of $S_e$:\n\n- **Impact of $S _e$:** The sampling probability is determined by $(1 + S_e)R_e$, where $S_e \\\\in [0,1]$ adds only a bias term to the factor 1, and $R _e$ remains the dominant factor. For example, consider two edges $a$ and $b$ with $S_a = 1$, $R_a = 0.5$ and $S _b = 0.5$, $R_b = 1$. We get: $(1+S_a)R_a = 2 \\\\times 0.5 = 1$ and $(1+S _b)R_b = 1.5 \\\\times 1 = 1.5$. Here, **$R_e$ plays a more significant role than $S_e$**. This is why our focus is on preserving the spectrum.\n\n- **Ablation Results:** We conduct an ablation study to analyze the role of $S_e$ in graph-level and node classification tasks across both homophily and heterophily datasets. We find that the utilization of **$S_e$ contributes less to performance** in graph-level and homophily tasks. On the other hand, Delaunay Rewiring, which disregards the original graph topology, still performs well in certain datasets. This is due to Delaunay triangulation’s inherent properties that ensure the graph remains well-connected, which is crucial for graph-level tasks.\n\nHere is the ablation study:\n\n|  | Mutag | Imdb  | Proteins | Chameleon | Cora  |\n|----|----|----|---|-----|---|\n| GOKU-Non$S_e$| 80.4  | **50.2** | 71.4     | 59.6      | 86.1  |\n| GOKU   | **81.0** | 49.8  | **71.9** | **63.2**  | **86.8** |\n\n---\n\n> ### **Comment 4**: Writing suggestions on adding a None row to Table 3, restating the theorems & Relational-GNN\n\nWe thank the reviewer for the valuable suggestions and feedback!\n\n1. We will explicitly mention that model used in Table 3 is the GCN models from Table 1. We also agree with adding a \"None\" row for clarity and restating the theorem statements in the appendix, which we believe will make it more reader-friendly. We will follow this suggestion in our future works as well. Thank you!\n2. We will clarify that methods such as FOSR, GTR, or LASER leverage Relational-GNN to preserve graph structure, whereas our method has the advantage that it doesn’t require the use of Relational-GNN to achieve this. This distinction will help readers better understand the literature and our contributions.\n\n> ### **Comment 5**: Theoretical guarantees for entire algorithm\n\nWe acknowledge that while the sparsification algorithm provides provable spectral sparsifiers, the reverse process (densification) does not have the same theoretical guarantees. It performs well empirically. The number of edges added during densification is **derived using Theorem 4.1 and the leading eigenvector** by $q \\\\ge \\\\frac{\\\\kappa(x_l)^2}{2\\\\epsilon^2} \\\\log 8$, rather than being chosen heuristically.", "claims_and_evidence": "The authors claim that GOKU is able to preserve the spectrum of the Laplacian. They argue this should be the case by constructing GOKU as a heuristic similar to an exact (but intractable) algorithm that would preserve the spectrum of the Laplacian. They demonstrate empirically comparing the spectrum of input graphs to those sparsified by GOKU. They also claim that GOKU will decrease the total resistance of nodes in the graph, which they demonstrate empirically. However, I am dubious of some of these claims; see Weaknesses. The authors claim that GOKU is an effective pre-processing step for graph neural networks, which they empirically verify by comparing it to other rewiring algorithms.", "methods_and_evaluation_criteria": "The authors propose GOKU as a pre-processing step for a graph neural network. They compare GOKU to other rewiring algorithms and show that GOKU achieved SOTA performance compared to other rewiring algorithms on a set of standard GNN benchmarks.", "theoretical_claims": "The authors prove that the two sparsification algorithms they consider are provably spectral sparsifiers. However, there are no guarantees for the unsparsification step, instead using on a heuristic for this step. Therefore, the entire algorithm GOKU has no theoretical guarantees of spectral sparsification.", "experimental_designs_or_analyses": "Mentioned above.", "relation_to_broader_scientific_literature": "This paper fits into a line of other works aimed at tackling over-squashing in graph neural networks by changing the topology of the graph. The technique in this paper seems most inspired by the work of (Karhadkar et al 2023) that aims to address oversquashing by increasing the spectral gap of the Laplacian, although the use of effective resistance as a measure for connectivity was proposed by (Black et al 2023, Di Giovanni et al 2023, 2024) who theoretically showed that over-squashing occurs between nodes of high effective resistance. In contrast to previous rewiring techniques, GOKU also aims to preserve the structure of the graph (as measured by the Laplacian spectrum), whereas other techniques focus on changing the graph to improve its connectivity. To maintain the spectrum of the graph, this paper relies on spectral sparsification techniques (Spielman and Srivistava, 2011).", "essential_references_not_discussed": "The paper makes a point that GOKU better preserves the spectrum of the graph than methods like FOSR, GTR, or LASER. However, I feel this somewhat misrepresents these methods. These papers recommend using these rewiring methods in conjunction with a relational GNN, which treats edges originally in the graph differently than those added during rewiring. (This could be true of the other rewiring methods as well, I am just most familiar with FOSR, GTR, and LASER.) Therefore, while I do think you can say that GOKU better preserves the structure of the graph than either of these methods, I think you should also mention that these methods aim to preserve the structure of the graph in a different way. (That said, you could argue that an advantage of using GOKU over these models is that you *don't* have to use a relational-GNN, which is a more complicated model with more parameters.)", "other_strengths_and_weaknesses": "# Strengths\n\nThe authors experimentally validate their claims that GOKU can preserve the Laplacian spectrum while decreasing effective resistance.\n\nThe authors have demonstrated the GOKU achieves SOTA performance as a pre-processing step for graph neural networks.\n\n# Weaknesses \n\nThere are a few inconsistencies in how this paper is presented in the introduction (see the Questions section below). Namely, the introduction presents the algorithm as both maintaining graph structure (in terms of the Laplacian spectrum) while improving connectivity (in terms of effective resistance), which is a contradiction as the effective resistances are a function of the Laplacian spectrum. (For example, the sum of effective resistance between all pairs of nodes is the trace of the pseudoinverse of the Laplacian; see e.g., (Ghost et al, 2006, Equation 15).)\n\nGhosh, A., Boyd, S., & Saberi, A. (2008). Minimizing effective resistance of a graph. SIAM review, 50(1), 37-66.", "other_comments_or_suggestions": "Table 3 should say which model is being used. I also suggesting adding a None row to Table 3. (I know it is technically listed in Table 1, but it would make it easier on the reader to include it in Table 3 as well.)\n\nI would recommend using the package thm-restate (or something similar) to copy the theorem statements of Theorem 4.1 and 4.2 to the appendix. This saves the reader from having to flip between the main text and the appendix when reading the proof of a theorem.", "questions_for_authors": "Would it be possible to do an ablation similar to Table 3 where you include/exclude the term $S_e$ from the probabilities in ISS step? Right now, it is not clear to me how much of the improvement in GOKU is due to preserving the spectrum vs. favoring edges with similar features. This feels relevant as the next best method is Delauney Rewiring, which as you note does not account for graph topology at all and only accounts for similarity of features.\n\nYou claim GOKU is both a spectral sparsifier while also reducing the effective resistance between most nodes. However, this seems to be a contradiction, as spectral sparsifiers preserve effective resistance. How is GOKU able to both preserve the spectrum of the graph while also reducing effective resistance? To this point, you show the effective resistance distribution (Figure 3) and eigenvalues of graphs (Figure 2) where GOKU was applied, but never for the same graph. Could you include both the effective resistance distribution and eigenvalues of a single graph so we could see the trade-off between these two?\n\nThe introduction of your paper says that the goal is to increase the smallest eigenvalues of the graph Laplacian while keeping the rest fixed. However, your theoretical results and your experiments both suggest that you preserve all eigenvalues. Why do you say you increase the smallest eigenvalues?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper introduces a spectrum-preserving graph sparsification approach to address over-squashing in GNNs. The paper has merits that the reviewers have highlighted. These include the methodological formalism and the good performance of the proposed approach, particularly when compared to existing pre-processing techniques. Nevertheless, the reviewers have also identified several limitations mainly related to the following points: (i) Motivation of simultaneously mitigating over-squashing while preserving the spectrum for node classification. This introduces a trade-off that hasn't been adequately discussed in the paper (and rebuttal). (ii) Tailoring experimental results to the main question of the paper. (iii) Besides, considering that the model acts in a pre-processing step, it's not evident how it compares to models that alleviate over-squashing while training the GNN. Considering that some of these points have been discussed in the response period, I'm in favor of accepting the paper. Please ensure that these comments are thoroughly addressed and incorporated into the manuscript.
Decision: Accept (poster)