Spectral Graph Pruning Against Over-Squashing and Over-Smoothing
Authors: Adarsh Jamadandi
Celia Rubio-Madrigal
Rebekka Burkholz
Venue: NeurIPS 2024 poster (2024)
Keywords: graph neural networks
rewiring
spectral gap optimization
over-smoothing
over-squashing
lottery tickets
Primary area: graph_neural_networks
TL;DR: By deleting edges of a graph that maximize the spectral gap, we jointly address over-smoothing and over-squashing in GNNs.

Abstract: Message Passing Graph Neural Networks are known to suffer from two problems that are sometimes believed to be diametrically opposed: over-squashing and over-smoothing. The former results from topological bottlenecks that hamper the information flow from distant nodes and are mitigated by spectral gap maximization, primarily, by means of edge additions. However, such additions often promote over-smoothing that renders nodes of different classes less distinguishable. Inspired by the Braess phenomenon, we argue that deleting edges can address over-squashing and over-smoothing simultaneously. This insight explains how edge deletions can improve generalization, thus connecting spectral gap optimization to a seemingly disconnected objective of reducing computational resources by pruning graphs for lottery tickets. To this end, we propose a computationally effective spectral gap optimization framework to add or delete edges and demonstrate its effectiveness on the long range graph benchmark and on larger heterophilous datasets.

Spectral Graph Pruning Against Over-Squashing and Over-Smoothing
Adarsh Jamadandi*1.2 1.2 adarsh. jan@gmai com
Celia Rubio-Madrigal" celia.
Rebekka Burkholz? burkholz@cispa.dd de
Universität des Saarlandes CISPA Helmholtz Center for Information Security
Abstract
Message Passing Graph Neural Networks are known to suffer from two problems that are sometimes believed to be diametrically opposed: over-squashing and over-smoothing. The former results from topological bottlenecks that hamper the information flow from distant nodes and are mitigated by spectral gap maximization, primarily, by means of edge additions. However, such additions often promote over- smoothing that renders nodes of different classes less distinguishable. Inspired by the Braess phenomenon, we argue that deleting edges can address over-squashing and over-smoothing simultaneously. This insight explains how edge deletions can improve generalization, thus connecting spectral gap optimization to a seemingly disconnected objective of reducing computational resources by pruming graphs for lottery tickets. To this end, we propose a computationally effective spectral gap optimization framework to add or delete edges and demonstrate its effectivenesss on the long range graph benchmark and on larger heterophilous datasets.
Introduction
Graphs are ubiquitous data structures that can model data from diverse fields ranging from chemistry
(Reiser al. 2022), biology (Bongini et al. 2023) to even high-energy physics (Shlomi et al. 2021).
This has led to the development of deep learning techniques for graphs, commonly referred to as
Graph Neural Networks (GNNs)). The most popular GNNs follow the message-passinnn paassgggs paradigm (Gori et al.. 2005) Scarselli et al. 2009 Gilmer et al. 2017)] Bronstein et al. [2021), where arbitrary differentiable functions, parameterized by neural networks, are used to diffuse information on the graph, consequently learning graph-level representation. This representation can then be used for various downstream tasks like node classification, link prediction, and graph classification. Different types of GNNs (Kipf & Welling 2017, Hamilton et al., 2017 Veličković et al.] 2018 Xu et al.) 2019 Bodnar et al. 202 b domains have been proposed with varied degree of success. Despite their widespread use, GNNs have a number of inherent problems. These include limited expressivity, (Leman 1968 Morris et al.
Bevilacqua et al. (022), all tackling a variety of problems in various
2019), over-smoothing (Li et al. [209 NT & Maeharal 2019 Oono & Suzuki 2020 Zhou et al.
2021 and over-squashing (Alon & Yahav 2021 Topping et al. 2022).
The phenomenon of wer-sqqashing, first studied heuristically by Alon & Yahav (201 and later
theoretically formalized by Topppig al. (022), is caused by the presence of structural bottlenecks in
Equal contribution.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

the graph. These bottlenecks can be attributed to the first non-zero eigenvalue of the normalized graph Laplacian, also known as the spectral gap. The smaller the gap, the more susceptible a graph over-
squashing. Recent work has explored rewiring the input graph to address these bottlenecks (Topping)
iet al. 2022 Arnaiz-Rodriguer et al., 2022 Giraldo et al., 2023 Nguyen et al. 2023 Karhadkar et al.
2023), but suggest there has to be a trade-off between over-squashing and ovor-smoothing (Keriven 2022). Instead, we propose to leverage the Braess paradox (Braess) 1968) Eldan et al. 2017) that
maximize the spectral gap. We propose to approximate the spectral change in computationally efficient manner by leveraging Matrix Perturbation Theory (Stewart & jointly address the problem of over-squashing, by increasing the spectral gap, and over- smothing, by slowing down the rate of smoothing. We find that our method is especially effective in heterophilic graph settings, where we delete edges between nodes of different labels, thus preventing unnecessary aggregation. We empirically show that our proposed method outperforms other graph rewiring methods node classification and graph classification tasks. We also show that spectral gap based edge deletions can help identify graph lottery tickets (GLTs) (Frankle & Carbin 2019). that is, sparse sub-networks that can match the performance of dense networks.
posits certain edge deletions
Sun 1990). Our proposed framework allows
1.1 Contributions
1. Inspired by the Braess phenomenon, we prove that, contrary to common assumptions, over- smoothing and over-squashing are not necessarily diametrically opposed. By deriving a minimal example, we show that both can be mitigated by spectral based edge deletions.
2. Leveraging matrix perturbation theory, we propose a Greedy graph pruning algorithm (PROXyDELETE) that maximizes the spectral gap in a computationally efficient way. Sim- ilarly, our algorithm can also be utilized to add edges in a joint framework. We compare this approach with novel graph rewiring scheme based on Eldan's 's criterion (Eldan et al.) 2017) that provides guarantees for edge deletions and a stopping criterion for pruning, but is computationally less efficient.
3. Our results connect literature on three seemingly disconnected topics: over-smoothing, over-squashing, and graph lottery tickets, which explain observed improvements in gener- alization performance by graph pruning. Utilizing this insight, we demonstrate that graph sparsification based on our proxy spectral gap update can perform better than or on par with a contemporary baseline (Chen et al. 202T) that takes additional node features and labels into account. This highlights the reasibility of finding winning subgraphs at initialization.
2 Related work
Topping et al. (0022) have observed that over-squashing where information from distant nodes are not propagated due to topological bottlenecks in the graph. hampers the performance of GNNs. A promising line of work that attempts to alleviate this issue graph rewiring. This task aims to modify the edge structure of the graph either by adding or deleting edges. Gasteiger et al. (0119) propose to add edges according to graph diffusion kernel, such as personalized PageRank, rely less on messages from only one-hop neighbors, thus alleviating over-squashing. TToppig et al.) (2022) propose Stochastic Discrete Ricci Flow (SDRF) to rewire the graph based on curvature. Banerjee et al.] (2022) resort to measuring the spectral expansion with respect to the number of rewired edges and propose a random edge flip algorithm that transforms the given input graph into an Expander graph. Contrarily, [Decc et al. (2022) show that negatively curved edges might be inevitable for building scalable GNNs without bottlenecks and advocate the et al. (2022) introduces two new
Over-squashing, Alon & Yahav (2021) ;:
use of Expander graphs for message passing. intermediate layers called CT-LAYER and GAP-LAYER, which can be interspersed between GNN layers. The layers perform edge re-weighting (which minimizes the gap) and introduce additional parameters. Karbadkar et al. (2023) propose FoSR, a graph rewiring algorithm that sequentially adds edges to maximize the first-order approximation of the spectral gap. A recent work by Black et al. (2023) explores the idea of characterizing over-squashing through the lens of effective resistance (Chandra et al. 1996). Giovanni et al. (2023) provide a comprehensive account of over-squashing and studies the interplay of depth, width and the topology of the graph.
Over-smoothing. It a known fact that increasing network depth (He et al., 2016) often leads to better performance in the case of deep neural networks. However, naively stacking GNN layers often seems

---

to harm generalization. And one of the reasons is smoothing (Li et al. 2019; Oono & Suzuki 2020; NT& Maehara 2019 Zhou et al., 202T: Rusch et al., (023a), where repeated aggregation
leads to node features, in particular nodes with different labels, becoming indistinguishable. Current graph rewiring strategies, such as FoSR (Karhadkar et al., (023), which rely on iteratively adding edges based on spectral expansion, may help mitigate over-squashing but also increase the smoothing induced by message passing. Curvature based methods such as Nguyen et al. (2023); Giraldo et al.) (2023) aim to optimize the degree of smoothing by graph rewiring. as they assume that over-smoothing is the result of too much information propagation, while over-squashing is caused by too little. Within this framework, they assume that edge deletions always reduce the spectral gap. In contrast, show and exploit that some deletions can also increase it, Furthermore, we rely on a different, well established concept of over-smoothing (Keriven 2022) that also takes node features into account and is therefore not diametrically opposed to over-squashing. As we show, over-smoothing and over-squashing can be mitigated jointly. Moreover, we propose computationally efficient approach to achieve this with spectral rewiring. In contrast to our proposal, curvature based methods (Nguyen) et al. 2023 Giraldo et al. (202) do not scale well to large graphs. For instance, [Ngueen al. (2023) propose a batch Ollivier- Ricci (BORF) curvature based rewiring approach to add and delete edges, which solves optimal transport problems and runs in cubic time.
Graph sparsification and lottery tickets. Most GNNs perform recursive aggregations of neighbor- hood information. This operation becomes computationally expensive when the graphs are large and dense. A possible solution for this is to extract a subset of the graph which is representative of the dense graph, cither in terms of their node distribution (Eden et al. 2018) or graph spectrum (Adhikari ett al. 2017). ZZeng et al. 2020); Li et al. (202)) formulate graph sparsification as an optimization problem by resorting to learning surrogates and ADMM respectively. With the primary aim to reduce the computational resource requirements of GNNs, a line of work that transfers the lottery ticket hypothesis (LTH) by Frankle & Carbin (2019) to GNNs (Chen al. 202 I Hui et al. 2023), prunes the model weights in addition to the adjacency matrix. The resulting winning graph lottery ticket (GLT) can match surpass the performance of the original dense model. While our theoretical
understanding of GLTs is primarily centered around their existence (Ferbach et al.] 2022 Burkholz
al. 2022; [Burkholz] 2022b a). our insights inspired by the Braess paradox add a complementarg lens to our understanding of how generalization can be improved, namely by reducing over- wer-squahhing
and over-smoothing with graph pruning. So far, the spectral gap has only been employed to maintain a sufficient degree of connectivity of bipartite graphs that are associated with classic feed-forward neural network architectures (Pal et al., [0022] Hoang et al.] 2023). We highlight that the spectral gap can also be employed as pruning at initialization technique (Frankle et al., 2021) that does not take node features into account and can achieve computational resource savings while reducing the generalization error, which is in line with observations for random pruning of CNNs (Gadhikar et al.
2023 Gadhikar & Burkholz 2024).
3 Theoretical insights into spectral rewiring
To prove our claim that over-smoothing and over-squashing can both be alleviated jointly, we provide minimal example illustrated in Figure 1 Utilizing the Braess paradox, achieve this by the deletion of an edge. In contrast, an edge addition that addresses over-squashing still causes over-smoothing, yet less drastically than another edge addition that worsens over-squashing.
Reducing over-squashing via the spectral gap. From a spectral perspective, bottlenecks, which hamper the information flow by over-squashing, can be characterized by the spectral gap of the (symmetric) normalized graph Laplacian Cg. where g = (V,E). The Laplacian of the graph is L= - A, where A is the adjacency matrix and D the diagonal degree matrix. The symmetric normalized graph Laplacian is defined as Lg = D 1/2 1 LD--DD-- 1/2, Let (Ao < λ₁ < A2....n } be the eigenvalues of LG arranged in ascending order and let (Cc) be the first non-zero eigenvalue of the normalized graph Laplacian, which is also called the spectral gap of the graph. For graph where distant network components are connected only by a few bridging edges, all the information has to be propagated via these edges. The information flow through edges is encoded by the Cheeger [aS] 1171 constant li = minscv min(Val(S) V where as {u, v) u E S U E V' and Vol(S) = Eues du. being d, the degree of the node u. The spectral gap is bounded by the Cheeger
h2 incquality 2hg > A1 2.
which motivates it as measure of over-squashing
3

---

g (A) (8299
g (A) 0.3545)
Add
(A M
Prine
Add
[Ax 11)
G (A Rs 0.2929)
(A1 0.2713)
Figure 1: Braess' paradox. We derive simple example where deleting an edge from 9 to obtain G yields a higher spectral gap. Alternatively, we add single edge to the base graph to either increase (G*) or to decrease (G+) the spectral gap. The relationship between the four graphs is highlighted by arrows when an edge is added/deleted.
Braess' paradox. Braess 1968) found counter-intuitive result for road networks: even if all travelers behave seltishly, the removal of road can still improve each of their individual travel times. That is, there is violation of monotonicity in the traffic flow with respect to the number of edges of a network. For instance, instance,Chuung & Young (2010) has shown that Braess' paradox occurs with high probability in Erdös-Rényí random graphs, and Chung et (2012) have confirmed it for large class of Expander graphs. The paradox can be analogously applied to related graph properties such as the spectral gap of the normalized Laplacian. [Eldan al. (2017) have studied how the spectral gap of a random graph changes after edge additions or deletions, proving a strictly positive occurrence of the paradox for typical instances of ER graphs. This result inspires us to develop an algorithm for rewiring a graph by specifically eliminating edges that increase this quantity, which we can expect to carry out with high confidence in real-world graphs. Their Lemma 3.2 (when reversed) states sufficient condition that guarantees a spectral gap increase in response to deletion of an edge.
Lemma 3.1. Eldan et al. (2017: Let G = (V,E) be a finite graph, with f denoting the eigenvector and X (Lg) the eigenvalue corresponding the spectral gap. Let (u,v) & V be two vertices that are not connected by an edge. Denote & (V. E), the new graph obtained after adding an edge between {u, v), ie.. & = E (u, Denote with Py = fo) the projection of f onto the top eigenvector of G. Define (u, Lg)
Vd, +1 vdu+1- vdh Pa Vd. +1 - vdu (3 Vdu +1
2fufe
-P}Xi(Lg) 2(1 (L())
Vdl +1
Vdn - 1d +
If 9 (u. v, Lg) then (1 > (C
As showcase example of the Braess phenomenon, let analyze the behaviour of the spectral gap in terms of an edge perturbation on the ring graph n nodes Ry, We consider the ring Rs as G the deletion of an edge from graph G in Figure I
Proposition 3.2. The spectral gap of increases with the deletion of edge (0, 3), i.e. X1 (Co-)) )) A1 (Cg). It also increases with the addition of edge (0.5) or decreases with the addition of edge (4, 7), i.e., Ai(Lg)) >> X1 (LG) and Xı (Lgg)) < X1 (L.).
We leverage Eldan's Lemma 3.1 in Appendix A.I and apply the spectral graph proxies in derivations starting from an explicit spectral analysis of the ring graph. While these derivations demonstrate that we can reduce over-squashing (i.e., increase the spectral gap) by edge deletions, we show next that edge deletions can also alleviate over-smoothing.
Slowing detrimental over-smoothing. For GNNs with mean aggregation, increasing the spectral gap usually promotes smoothing and thus leads to higher node feature similarity. Equating a high node feature similarity with over-smoothing would thus imply trade-off between over-smoothing and over-squashing. Methods by Giraldo et al. (2023); y; Nguyen et al. (2023) seek to find the right amount of smoothing by adding edges to increase the gap and deleting edges to decrease it. Contrarily,

---

0.3
020
MSE
015
MSE
Original
FoSR
G+
ProxyAdd
0.5
G
Prley
000
Order of smoothing
Order of smoothing
(a) Smoothing test for graphs in Figure
(b) Smoothing test for the Texas dataset.
Figure 2: We plot the MSE vs order of smoothing for our four synthetic graphs ((a) and for a real heterophilic dataset with the result of different rewiring algorithms to it: FoSR (Karhadkar al. 2023) and PROXYADD for adding (200 edges), and our PROXYDELETY for deleting edges (5 edges) (2(b) We find that deleting edges helps reduce over-smoothing, while still mitigating over-squashing via the spectral gap increase.
argue that deleting edges can also increase the gap while adding edges could decrease it, as our previous analysis demonstrates. Thus, both edge deletions and additions allow to control which node features are aggregated, while mitigating over-squashing. Such node features are central a more nuanced concept of over-smoothing that acknowledges that increasing the similarity of nodes that share the same label, while keeping nodes with different labels distinguishable, aids the learning task.
To measure over-smoothing, we adopt the Linear GNN test bed proposed by Keriven (2022), which uses linear ridge regression (LRR) setup with mean squared error (MSE) the loss. We assign two classes to nodes according to their color in Figure I. and one-dimensional features that are drawn independently from normal distributions (1, 1) and ()11, respectively. Figure 2(a) compares how our exemplary graphs (see Figure D influence over-smoothing in this setting. While adding edges can accelerate the rate of smoothing, pruning strikingly aids in reducing over-smoothing and still reduces weusshua by increasing the spectral gap. Note that the real world heterophilic graph example shows a similar trend and highlights the utility of the spectral pruning algorithm PROXYDELFFE which we describe in the next section, over edge additions by the strong baseline FOSR. Additional real world examples along with cosine distance between nodes of different labels before and after spectral pruning and plots for Dirichlet energy can be found in Appendix [
In the following, we discuss and analyze rigorously the reasons for this finding. Consider again the ring graph G- which has an inter-class edge pruned from our base graph G; this avoids a problematic aggregation step and in this way mitigates over- -mooohinn Instead of deleting an edge, we could also add an edge arriving at g which would lead to higher spectral gap than the edge deletion. Yet, it adds an edge between nodes with different labels and therefore leads to ver-smotthing. We also prove this relationship rigorously for one step of mean aggregation.
Proposition 3.3. As more edges are added (from G to G. or from G to G+ G+), the average value over same-class node representations after a mean aggregation round becomes less informative.
The proof is presented in Appendix A.2 We argue that similar situations arise particularly in heterophilic learning tasks, where spectral gap optimization would frequently delete inter-class edges but also add inter-class edges. Thus, mostly edge deletions can mitigate over-squashing and over-smoothing simultaneously.
Clearly, this argument relies on the specific distribution of labels. Other scenarios are analyzed in Appendix B to also highlight potential limitations of spectral rewiring that does not take node labels into account.
Following this argument, however, we could ask if the learning task only depends on the label distribution. The following proposition highlights why spectral gap optimization is justified beyond label distribution considerations.
Proposition 3.4. After one round of mean aggregation, the node features of g+ are more informative compared to ++.
5

---

Note that G+ decreases the spectral gap, while G+ increases it relative to g. However, the label configuration of G+ seems more advantageous because, for the changed nodes, the number of neighbors of the same class label remains in the majority in contrast to g+. Still, the spectral gap increase seems to aid the learning task compared to the spectral gap decrease.
4 Braess-inspired graph rewiring
We introduce two algorithmic approaches to perform spectral rewiring. Our main proposal is computationally more efficient and more effective in spectral gap approximation than baselines, as we also showcase Table The other approach based on Eldan's Lemma is also analyzed, as provides theoretical guarantees for edge deletions. However, it does not scale well to larger graphs.
Greedy approach modify edges. Evaluating all potential subsets of edges that we could add or delete is computationally infeasible due to the combinatorially exploding number of possible candidates. Therefore, we resort to a Greedy approach, in which we add or delete single edge iteratively. In every iteration, we rank candidate edges according to proxy of the spectral gap change that would be induced by the considered rewiring operation, as described next.
4.1 Graph rewiring with Proxy spectral gap updates
Update of eigenvalues and eigenvectors. Calculating the eigenvalues for every normalized graph Laplacian obtained by the inclusion or exclusion of a single edge would be a highly costly method. The ability to use the spectral gap directly estimate it for one edge flip. For this we resort to Matrix Perturbation Theory (Stewart & Sun 1990] von Luxburg 2007) capture the change in cigenvalues and eigenvectors approximately. Our update schemne is similar to the proposal by Bojchevski & Günnemann (2019) in the context of adversarial flips. The change in the eigenvalue and eigenvector for single edge flip (u, v) is given by
criterion to rank edges requires formula to efficiently
A A + Aw., fa)² X(P f?))
where A is the initial eigenvalue; (Sa are entries of the leading eigenvector, AWw. = 1 if we add edge and Awa.e = 1 if we delete an edge. Note that this proxy is only used rank edges efficiently. After adding/deleting the top M edges (where M = 1 in our experiments), we update the cigenvector and the spectral gap by performing few steps of power iteration. To this end, we initialize the function eigsh of the scipy sparse library in Python, which is based on the Implicitly Restarted Lanezos Method (Lehoucq et al. 1998), with our current estimate of the leading eigenvector. Both our resulting algorithms, PROXYDELET for deleting edges and PROXYADD for adding edges, are detailed in Appendix(C
Time Complexity of PROXYDELETE. The algorithm runs in O (N ([8)+ +())) where N is the number of edges delete, and (G)) denotes the complexity of the algorithm that updates the leading eigenvector and eigenvalue at the end of every iteration. In our setting, this requires a constant number of power method iterations, which is of complexity s()) O( Note that, because we choose to only delete one edge, the ranking does not need to be sorted to obtain its maximum. By having an (L) proxy measure to score candidate edges, we are able to improve the overall runtime complexity from the original O (N - |E] s.)).. Furthermore, even though this does not impact the asymptotic complexity, deleting edges instead of adding them makes every iteration run on gradually smaller graph, which can further induce computational savings for the downstream task.
Time Complexity of PROXYADD. The run time analysis consists of the same elements the edge deletion algorithm. The key distinction is that the ranking is conducted on the complement of the graph's 's edges, &. Since the set of missing edges is usually larger than the existing edges in real world settings, to save computational overhead, it is possible to only sample a constant amount of edges. See Section F for empirical runtimes.
4.2 Graph rewiring with Eldan's criterion
Lemma 3.1 states a sufficient condition for the Braess paradox. It naturally defines scoring function of edges to rank them according to their potential to maximize the spectral gap based on the function g. However, the computation of this ranking is significantly more expensive than other considered

---

SpectralGapp
Spectral Cap
GreedyFull-Ads PR-Add Eldarvidd
GreedyFull-Deiete
PR-Delete
30
Iterations
Tterations
(a) Edge additions to improve spectral gap expansion.
(b) Edge deletions to improve spectral gap expansion.
Figure 3: We instantiate toy ER graph with 30 nodes and 58 edges. We compare FoSR (Karhadkar et al. 2023), our proxy spectral gap based methods, and our Eldan's 's criterion based edge methods.
Table 1: Results on Long Range Graph Benchmark datasets.
PascalVOC-SP
Peptides- Peptides-Func (Test AP 7)
Peptides- Struct (Test MAE
Method
(Test Fl f)
Baseline-GCN
0.1268+0.00 0066
0.5930=0.000 0022
0.3496=0.000
DRew+GCN
0.1848+0.0107
0.699620.0076
0.2781
FOSR+GCN
0.215740.0055
0.652620.0014 0014
0.2499+0.0006
ProxyAd+-GCN
0,2213+:.0011
0.6789=0.0002
0.2465=0.0004
ProxyDelet++GCN
0.2170#0.0015
0.6908=0.0007
0.2470=00.0800
algorithms, as each scoring operation needs access to the leading eigenvector of the perturbed graph with added or deleted edge. In of edge deletions, we also need to approximate the spectral gap similar to our Proxy algorithms. As the involved projection Py is a dot product of eigenvectors, requires ((VV) operations. Even though this algorithm does not scale well large graphs without focusing on a small random subset of candidate edges, we still consider it as baseline, as it defines a more conservative criterion to assess when we should stop deleting edges. The precise algorithms are stated in Appendix
4.3
Approximation quality
To check whether the proposed edge modification algorithms indeed effective in the spectral gap expansion, we conduct experiments on an Erdös-Rényi (ER) graph with ([V], (30,58 in Figure Our ideal baseline that scores each candidate with the correct spectral gap change would usually be computationally too expensive, because each edge scoring requires O(EE) computations. For our small synthetic test bed, still compute it to assess the approximation quality of the proposed algorithms, and of the competitive baseline FoSR (Karhadkar et al.) 2023). For both edge additions (Figure ({))p and deletions (Figure ((b)). we observe that the Proxy method outlined in Algorithm I usuaaly leads to better spectral expansion approximation. In addition, we report the spectral gaps that different methods obtain on real world data in Table [6]in the Appendix, which highlights that our proposals are consistently most effective in increasing the spectral gap.
5
Experiments
5.1 Long Range Graph Benchmark
The Long Range Graph Benchmark (LRGB) was introduced by Dwivedi et al. (2023) create a test bed for squushqus We compare our proposed PROXYADD and PROXYDELETE methods with DRew (Gutteridge et al. 2023), a recently proposed strong baseline for addressing over-squashing using a GCN as our backbone architecture in Table We adopt the experimental setting of Tönshoff et al. (2023), we adopt DRew baseline results from the original paper. We evaluate on the following datasets and tasks: PaSSalVOC-SP... Semantic image segmentation as node classification task operating superpixel graphs. 2) Peptides-func Peptides modeled molecular
specifically to
7

---

Table 2: Node classification on Loman-Empinn dataset.
Layans
GCN
70.30 73
70 33
GCN+FV6R
73.0041
77.54H9.74
20
GAT
00.05a51
Stell T0
GAT
11.1340
100
12st No Mest
GAT-PionyGap
50
96.07 46
20
GCN
Shal
GCN Hldan
100
15.39 Dgg
100
10
OCNI Panyy
20
78.31
20
TH. 1Pet
10
GAT
GKI-FaSIL
100
$1.3741
10
100
87.19988.5
20
10
GEN-
100
20
50
77 05
20
TIS 1YSHEET 71
20
GAT
GAT+FoSR
80/6441
(eles 12
100
96.79u0.01
90
86 70140.50
20
GATsPrayGap
10
36 7540566
20
1560.51
70
Table 3: Node classification on Amazon Ratings.
Table 4: Node classification on Minesweeper.
Michal
#FdyynAdtel
4FdgooAddiall
Accenacy
#idgodeicssd
Tox
Layas
OCN
47. 21200si1:3 35
20200.033
10
OCN
88.55 57 0.54
58 57. 0.64
10
OUN-FISR
20.08840 (2106-077 75
10
GUN-FoRR 50
90.15 55
10
OCN-Falan
48.71-8899 99
100
58, 15
10
OCN+Eldaa
100
90.11.20.5 50
50
39 4920600
10
OCN+PrasyGap
10
40.72:0:41
50
49.75110446
10
OCN-ProxyCip
20
89 39.5M-99.50
20
39.57411.09
10
GAT
03.00120.54
93. 33.00211.64
10
GAT4R-5R
51.361062
GAT+R-SR
100
GAT-Bldon
50
GAT-Bllan
93.224055
GAp
09.06e0
100
$1,7240.30
CKN
2T- 59
ST.TTR 39
20
OCN
317-1110
20
GUN-
100
49:5728
20
100
13.86200555
20
GCN+EMdan
0266660.22 31
20
76
30
OCN+Fidan
CCp
500
49.5810.59
OCN+PruxyEap
39.4620.50
47.31200.46
GAT+FoSR
03.56.0004
GAT-Hlaan
51,40s0.55
20
51.64:1.44
GAT-Ellan
10
91.92-0:44
20
95.48:1164
20
GAT
47.53s8
20
$1.6920.46
20
GAT-ProxyGap
20
94.9988.7
20
94 64.440055
20
graphs. The task is graph classification. 3) Peptides-struct Peptides modeled as molecular graphs. The task is predict various molecular properties, hence graph regression task.
The top performance highlighted in bold. Evidently, our proposed rewiring methods outperform DRew (Gutteridge al. 2023) and FoSR (Karhadkar et al. 2023) on PascalVOC and Peptides-struce
and achieves comparable performance on Peptides-func.
In addition, Table 10 in the appendix compares different rewiring strategies for node classification on other commonly used datasets and graph classification ( E.22 for adding edges, since FoSR
(Karhadkar et al. 2023) was primarily tested this task.
Node classification large heterophilic datasets. Platonov et al. (2023) point out that most progress on heterophilic datasets unreliable since many of the used datasets have drawbacks, including duplicate nodes in Chameleon and Squirrel datasets, which lead to train-test data leakage. The sizes of the small graph sizes also lead to high variance in the obtained accuracies. Consequently, also test proposed algorithms
3/5 of their newly introduced larger datasets and use GCN (Kipf & Welling 2017) and GAT (Veličković et al.) 2018) as our backbone architectures. As a higher depth potentially increases over-smoothing, we also analyze how our methods fares with varied number of layers. To that end, we adopt the code base and experimental setup of Platonooy al. (202);; the datasets are divided into 50/25/25 split for train/tes//validation respectively. The test accuracy is reported as average over 10 runs. To facilitate training deeper models, skip connections and layer normalization are employed. We compare FoSR (Karhadkar et al., 2023) and our proposals based on the Eldan criterion as well as PROXYADD and PROXYDELET in Tables 3
The top performance highlighted in bold. Evidently, for increasing depth, even though the GNN performance should degrade because of over-smoothing, we achieve significant boost in accuracy compared to baselines, which we attribute to the fact that our methods delete inter-class edges -tus slowing down detrimental smoothing.
8

---

Table 5: Pruning for lottery tickets comparing UGS ELDANDELETE pruning and our PROXY- DELETE pruning. We report Graph Sparsity (GS), Weight Sparsity (WS), and Accuracy (Acc).
Method
Cora
Citeseer
Pubmed
Metrics
GS
WS
GS
WS
Ace
UGS
79,85%
97.86%
68.46+1 89
78. 18.10%
97.50%
66.50=0060
68.67%
94.52%
76.90= 1.83
ELDANDELCTO-UGS
79. 70%
97.31%
68, 73+0.01
77.84%
96.78%
64.60=0.00
70.11%
93.17%
78.00=0.42
PROXYDELETE-UGS
78.81%
97.24%
69.2620.63
77.50%
95.83%
65.4340.60
78.81%
97.24%
75.25=0.25
we have shown that graph pruning can improve generalization, mitigate over-squashing and also help slow down the rate of smoothing. Can we also use our insights to find lottery tickets (Frankle & Carbin 2019)
Pruning for graph lottery tickets. In Sections $ and $
To what degree is graph pruning feature data dependent? The first extension of the Lottery Ticket Hypothesis to GNNs, called Unified Graph Sparsification (UGS) (Chen et al.] (021), prunes connections in the adjacency matrix and model weights that are deemed less important for prediction task. Note that UGS relies on information that obtained computationally intensive prune-train cycles that take into account the data and the associated masks. In the context of GNNs, the input graph plays a central role in determining a model's performance at a downstream task. Naively pruning the adjacency matrix without characterizing what constitutes important edges is pitfall we would want to avoid (Hui et al. 2023), yet resorting to expensive train- pwrpp-rruueennnee cycles to identify importance is also undesirable. This brings forth the questions: To what extent does the pruning criterion need to depend on the data? Is it possible to formulate a data/feature agnostic pruning criterion that optimizes a more general underlying principle to find lottery tickets? Morcos al. (2019) and Chen et al. (2020) show, in the context of computer vision and natural language processing respectively, that lottery tickets can have universal properties that can even provably (Burkholz et al. 2022) transfer to related tasks.
Lottery tickets that rely on the spectral gap. However, even specialized structures need to maintain and promote information flow through their connections. This fact has inspired works like Pal ct al. (2022); Hoang et al. (2023) to analyze how well lottery ticket pruning algorithms maintain the Ramanujan graph property of bipartite graphs, which is intrinsically related to the Cheeger constant and thus the spectral gap. They have further shown that rejecting pruning steps that would destroy proxy of this property can positively impact the training process.
In the context of GNNs, we show that we can base the graph pruning decision even entirely on the spectral gap. but rely on a computationally cheaper approach to obtain proxy. By replacing the magnitude pruning criterion for the graph with the Eldan criterion and PROXYDELETE to prune edges, in principle, we can avoid the need for additional data features and labels. This has the advantage that we could also prune the graph at initialization and thus benefit from the computational savings from the start. We use our proposed methods to prune the graph at initialization to the requisite sparsity level and then feed it to the GNN where the weights are pruned in iterative manner. Our results are presented in Table 18 where we compare IMP based UGS (Chen et al., (02T) with our methods for different graph and weight sparsity levels. Note that, even though not take any feature information into account and prunes purely based on the graph structure, our results comparable. For datasets like Pubmed, we even slightly outperform the baseline. Table shows results for jointly pruning the graph and parameter weights, which leads to better results due to potential positive effects of overparameterization on training (Gadhikar & Burkholz 2024).
method does
Stopping criterion. The advantage of using spectral gap based pruning (especially the Eldan criterion) is patent: It helps identify problematic edges that cause information bottlenecks and provides a framework to prune those edges. Unlike UGS, our proposed framework also has the advantage that we can couple the overall pruning scheme with stopping criterion that follows naturally from our setup. We stop pruning the input graph when no available edges satisfy our criterion anymore.
Conclusion
Our work connects two seemingly distinct branches of the literature on GNNs: rewiring graphs to mitigate over-squashing and pruning graphs for lottery tickets to save computational resources.

---

Contributing to the first branch, we highlight that, contrary to the standard rewiring practice, not only adding but also pruning edges can increase the spectral gap of graph exploiting the Braess paradox. By providing minimal example, we prove that this way it is possible to address over- squashing and over-smoothing simultaneously. Experiments on large-scale heterophilic graphs confirm the practical utility of this insight. Contributing to the second branch, these results explain how pruning graphs moderately can improve the generalization performance of GNNs, in particular for heterophilic learning tasks. To utilize these insights, we have proposed computationally efficient graph rewiring framework, which also induces a competitive approach to prune graphs for lottery tickets at initialization.
Acknowledgments and Disclosure of Funding
We gratefully acknowledge funding from the European Research Council (ERC) under the Horizon Europe Framework Programme (HORIZON) for proposal number 101116395 SPARSE-ML.
References
Adhikari, B., Zhang, Y., Bharadwaj. A., and Prakash, B. A. Condensing temporal networks using propagation. In SDM, pp. 417-425. SIAM, 2017. ISBN 978-1-61 197-497-3.
Alon, U. and Yahav, E. On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations, 2021. URL https://openreviex: net/ forun/id=1800PhDN
Amaiz-Rodriguez A., Begga, A., Escolano, F., and Oliver, N. Diffwire: Inductive graph rewiring via the lovász bound, 2022. URL https::t/axxtiiii org/ abs/aabs....///////////////// 07369
Azabou, M., Ganesh, V., Thakoor, S., Lin, C.-H., Sathidevi, L., Liu, R., Valko, M., Veličković, P.. and Dyer, E. Half-hop: A graph upsampling approach for slowing down message passing. In International Conference on Machine Learning. 08 2023.
Ba. J. L., Kiros, J. R., and Hinton, G. E. Layer normalization. 2016. URL https:t//rxxiii org/ abs/1607 06450
Banerjee, P. K., Karhadkar, K., Wang, Y. G., Alon, U., and Montúfar, G. Oversquashing in gnns through the lens of information contraction and graph expansion. In 2022 58th Annual Allerton Conference on Communicctionn Control, and Computing (Allerton), pp. 1-8. IEEE Press, 2022. doi: 10.1 (1000//AAllett0/9997200029990090
URL https://doi. org 10. 1109/
A1lerton49937 2022. 9929363
Battaglia, P. W., Hamrick, J. B.. Bapst, V., Sanchez- A., Zambaldi, V., Malinowski, M., Tacchetti, A., Raposo, D., Santoro, A., Faulkner, R., et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv: 01261, 2018.
Bevilacqua, B., Frasca, F., Lim, D., Srinivasan, B., Cai, C., Balamurugan, G., Bronstein, M. M., and Maron, H. Equivariant subgraph aggregation networks. In International Conference on Learning Representations, 2022. URL BRLL/htps:://// /ttttp::///peeneviiess wttp://wweeeeeeeeeeruurrriedeee. www.:/eeeo/tiiiiie http://orouunidddddooreeetaatt.
Black, M., Wan, Z., Nayyeri, A., and Wang, Y. Understanding oversquashing gnns through the lens of effective resistance. In Proceedings of the 40th International Conference on Machine Learning, ICML'23, JMLR.org, 2023.
Bodnar, C., Frasca, F., Otter, N., Wang, Y. G., Liò, P., Montufar, G., and Bronstein, M. M. We- isfeiler and lehman go cellular: CW networks. In Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.), ), Advances in Neural Information Processing Systems, 2021a. URL https::/opeerevier wwt. wwt.:/oruun..diww/c.....co
Bodnar, C., Frasca, F., Wang. Y. G., Otter, N., Montufar, G., Liò, P., and Bronstein, M. Weisfeiler and lehman go topological: Message passing simplicial networks. In /CLR 202/ Workshop Geometrical and Topological Representation Learning, 2021b. URI, httpt:ttt///// |Rt./attps://ppereeee /ppprevieeeeeeeeeeeeeeee net het/forum?id-R220 22w66 03w6z
10

---

Bojchevski, A. and Günnemann, S. Adversarial attacks on node embeddings via graph poisoning, In Proceedings of the 36th International Conference on Machine Learning. ICML, Proceedings of Machine Learning Research. PMLR, 2019.
Bongini, P., Pancino, N., Scarselli, F., and Bianchini, M. Biognn: How graph neural networks can solve biological problems. In Artificial Intelligence and Machine Learning for Healthcare, pp- 211-231. Springer, 2023.
Braess, D. Über ein paradoxon aus der verkchrsplanung. Unternehmennfforcchunn, 12:258-268, 1968.
Bronstein, M. M., Bruna, J., Cohen, T., and Velickovic, P. Geometric deep learning: Grids, groups. graphs, geodesics, and gauges. CoRR, (tix/1104.1378,, 2021. (tRthttts:/// /tttts:///atii.....//////// http:/:.///xvvvo//////// abs/ 2104.13478
Burkholz, R. Convolutional and residual networks provably contain lottery tickets. In International Conference on Machine Learning, 2022a.
Burkholz, R. Most activation functions can win the lottery without excessive depth. Advances in Neural Information Processing Systems, 2022b.
Burkholz, R., Laha, N., Mukherjee, R., and Gotovos, A. On the existence of universal lottery tickets. In International Conference on Learning Representations, 2022.
Chandra, A. K., Raghavan, P., Ruzzo, W. L., Smolensky, R., and Tiwari, P. The electrical resistance of a graph captures its commute and cover times. compulational complexity, 6(4):312-340, 1996. doi: 10. 10.1007/BF01277085.
URL.https: http:///.o.....0........000 1tt.:////1011000////000077555
Cheeger, J. A Lower Bound for the Smallest Eigenvalue of the Laplacian, pp. 195-200. Princeton University Press, Princeton, 1971. ISBN 97814008693 doi:
URL battps://dof: org/ 10. 1515/977844086932--003
Chen, J., Ma. T., and Xiao, C. FastGCN: Fast learning with graph convolutional networks via importance sampling. In International Conference on Learning Representations, 2018. URL https://openreviek
Chen, T. Frankle, J., Chang, S., Liu, S., Zhang, Y., Wang, Z.. and Carbin, M. The lottery ticket hypothesis for pre-trained bert networks. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS '20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 9781713829546.
Chen, T., Sui, Y., Chen, X., Zhang, A., and Wang, Z. A unified lottery ticket hypothesis for graph neural networks. International Conference on Machine Learning, 2021.
Chung, F. and Young, J. Braess's paradox large sparse graphs. In Internet and Network Economics. Springer Berlin Heidelberg, 2010.
Chung, F,, Young, S. J., and Zhao, W. Braess's paradox in expanders. Random Structures & Algorithms, 41(4):451-465 2012. doi: https://doi.or//10. http://.....r./1...000//aa.2aa URL https /ooliielibraayy www.wwwwwwwweeeee...
com httm///ai/abs/1..00//raaaa 20457
Deac, A., Lackenby, M., and Veličković, P. Expander graph propagation. In The First Learning on Graphs Conference, 2022. URL http:p::://peerreeeeeeneeeeeeeee
Dwivedi, V. P., Rampášek, L., Galkin, M., Parviz, A., Wolf, G., Luu, A. T., and Beaini, D. Long range graph benchmark, 2023.
Eden, T., Jain, S., Pinar, A., Ron, D., and Seshadhri, C. Provable and practical approximations for the degree distribution using sublinear graph samples. In Proceedings of the 2018 World Wide Web Conference, WWW '18, pp. 449-458, Republic and Canton of Geneva, CHE, 2018. International World Wide Web Conferences Steering Committee. ISBN 9781450356398. doi: 10.1145/3178876.311 1167666111611.... URL SttLhhtp:://// //bpps://doi..oo http:///toooog///./.// 10....1115331887777 1115//11178766..11111
Eldan, R., Rácz, M. Z., and Schramm, T. Braess's paradox for the spectral gap in random graphs and delocalization of cigenvectors. Random Structures & Algorithms, 50, 2017.

---

Ferbach, D., Tsirigotis, C., Gidel, G., and Avishek, B. A general framework for proving the equivariant strong lottery ticket hypothesis, 2022.
Frankle, J. and Carbin, M. The lottery ticket hypothesis: Finding sparse, trainable neural networks
In International Conference on Learning Representations, 2019. URL https://openreviirr net/forum?id 13--dR3FF-
Frankle, J., Dziugaite, G. K., Roy, D., and Carbin, M. Pruning neural networks initialization: Why are we missing the mark? In International Conference on Learning Representations, 2021.
Gadhikar, A. H. and Burkholz, R. Masks, signs, and learning rate rewinding. In International Conference on Learning Representations, 2024.
Gadhikar, A. H., Mukherjee, S., and Burkholz, R. Why random pruning is all need to start sparse. In International Conference on Machine Learning, 2023.
Gasteiger, J., Weißenberger. S., and Günnemann, S. Diffusion improves graph learning. In Conference Neural Information Processing Systems (NeurIPS), 2019.
Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., and Dahl, G. E. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning Volume 70, ICML' 17, pp. 1263-1272. JMLR.org. 2017.
Giovanni, F. D., Giusti, L., Barbero, F., Luise, G., Lio', P., and Bronstein, M. On over-squashing in message passing neural networks: The impact of width, depth, and topology, 2023.
Giraldo. H., Skianis, K., Bouwmans, T., and Malliaros, F. D. On the trade-off between over- smoothing and over-squashing in deep graph neural networks. In Proceedings of the 32nd ACM International Conference on Information and Knowledge Management, CIKM '23, pp. 566-5 576, New York, NY, USA, 2023. Association for Computing Machinery. ISBN 9798400701245. doi: 10.1145/3583780.3661
URL htttt/ttt////ooo wtgg//////00 001111115/337880 36149977
Gori, M., Monfardini, G., and Scarselli, new model for learning in graph domains. Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005., volume 2, pp. 729-734 vol. 2, 2005. doi: 10. 1109/ICNN.2000. 1555549942..
Gray, M. Toeplitz and Circulant Matrices: Review. Foundations and Trends in Communications and Information Theory, 2(3):155-233 239, 2005. doi: 10.1561/0 10110/00000000066..
Gutteridge, B., Dong, X., Bronstein, M. M., and Di Giovanni, F. DRew: Dynamically rewired message passing with delay. In International Conference on Machine Learning, pp. 12252-12267. PMLR, 2023.
Hamilton, W. L.,, Ying, Z., and Leskovec, J. Inductive Representation Learning on Large Graphs. In NIPS, pp. 1024-1034, 2017.
He, K., Zhang, X., Ren. S., and Sun, J. Deep residual learning for image recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp- 770-778, 2016. doi: 10.1 10.1109/CVPR.2016.999
Hoang, D. N., Liu, S., Marculescu, R., and Wang. Z. Revisiting Pruning At Initialization Through The Lens of Ramanujan Graph. In The Eleventh International Conference on Learning Representations, 2023. htttp::
Hui, B., Yan, D., Ma, X., and Ku, W.S. Rethinking graph lottery tickets: Graph sparsity matters. In The Eleventh International Conference on Learning Representations, 2023. URL https fftrrumm?ddffjuuuQqp
//openreview.
Karhadkar, K., Banerjee, P. K., and Montufar, G. FoSR: First-order spectral rewiring for addressing oversquashing in GNNs. In The Eleventh International Conference on Learning Representations, 2023. URL /ttttree//ppenreiiiee nett:
Keriven, N. Not too little, not too much: theoretical analysis of graph (over)smoothing. In
The First Learning on Graphs Conference, 2022. http:/ppp/e/opeeeevveeeeeeee/e/e KQNsbAm.Jugg
12

---

Kipf, T. N. and Welling, M. Semi Semi-Supervised Classification with Graph Convolutional Networks, In ICLR, 2017.
Lehoucq, R. B., Sorensen, D. C., and Yang, C. ARPACK Users' Guide: Solution of Large Scale Eigenvalue Problems by Implicitly Restaried Arnoldi Methods. SIAM, 1998.
Leman, A. The reduction of a graph to canonical form and the algebra which appears therein. 1968.
Li, G., Müller, M., Thabet, A., and Ghanem, B. Deepgens: Can gens go as deep cnns? In The IEEE International Conference on Computer Vision (ICCV), 2019.
Li, J., Zhang, T., Tian, H., Jin, S., Fardad, M., and Zafarani, R. Sgen: A graph sparsifier based graph convolutional networks. In Advances in Knowledge Discovery and Data Mining: 24th Pacific-Asia Conference, PAKDD 2020, Singapore, May 11-14, 2020, Proceedings, Part I, pp. 275 287, Berlin, Heidelberg, 2020. Springer- Verlag. ISBN 978 178-3-030-47425-- doi: 10. 10.1007/ 978-3- 3-030-044224-333 __22. httpstts: org/ 10. 00000//778-20 000-----000--442--3131
McCallum, A. K. Nigam, K., Rennie, J., and Seymore, K. Automating the construction of internet portals with machine learning. Information Retrieval, 3(2):127-163, 2000. doi: 10.1023/A:
100995381 14988. Utt
org/ 10. 1023/ A: 10009///11099958144488
Morcos, A. S., Yu, H., Paganini, M., and Tian, Y. One ticket to win them all: generalizing lottery ticket initializations across datasets and optimizers. Curran Associates Inc., Red Hook, NY, USA, 2019.
Morris, C., Ritzert, M., Fey, M., Hamilton, W. L., Lenssen, J. E.,, Rattan, G., and Grohe, M. Weisfeiler and leman go neural: Higher-order graph neural networks. Proceedings of the AAAI Conference on Artificial Intelligence, 23(01):4602 4609. Jul. 2019. doi: 10. v3319/0....33001.3333333 https://ojs aaai org/ index.
URL
Namata, G., London, B., Getoor, L.,, and Huang, B. Query-driven active surveying for collective classification. 2012.
Nguyen, K., Nong. H., Nguyen, V., Ho, N., Osher, S., and Nguyen, T. Revisiting over-smoothing and over-squashing using ollivier-ricci curvature, 2023.
NT, H. and Machara, T. Revisiting graph neural networks: All we have is low-pass filters. ArXiv, abs/1905 1ass1990509550 2019.
Oono, K. and Suzuki, T. Graph neural networks exponentially lose expressive power for node classification. In International Conference on Learning Representations, 2020.
Pal, B., Biswas, A., Kolay, S., Mitra, P., and Basu, B. A study on the ramanujan graph property of winning lottery tickets. In Chaudhuri, K., Jegelka, S., Song. L., Szepesvari, C., Niu, G., and Sabato, S. (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 11116-17201, PMLR, 17-23 Jul 2022. mlr wwwpsp/www/ppaalslppppp
URL htttps://proceedingg
html
Platonov, O., Kuznedelev, D., Diskin, M., Babenko, A., and Prokhorenkova, I., A critical look at evaluation of gnns under heterophily: Are we really making progress? In The Eleventh International Conference Learning Representations, 2023,
Reiser, P., Neubert, M., Eberhard, A., Torresi, L., Zhou. C., Shao, C.. Metni, H., van Hoesel, C.. Schopmans, H., Sommer, T., and Friederich, P. Graph neural networks for materials science and chemistry. Communications Materials, 3(1):93, 2022. doi: 10. 10.1038/543246--2-000311 URL hhttps://do orooooo//// 10. 1038/ (4338//43246-10 00315-6
Roth, A. and Liebig. T. Rank collapse causes over-smoothing and over-correlation in graph neural networks. In The Second Learning on Graphs Conference, 2023. URL htl.hhttps://pperrev/
met./forumiid-aaDDddmm
Rusch, T. K., Bronstein, M. M., and Mishra, A survey on oversmoothing in graph neural networks, 2023a.
13

---

Rusch, T. K., Chamberlain, B. P., Mahoney, M. W., Bronstein, M. M., and Mishra, S. Gradient gating for deep multi-rate learning on graphs. The Eleventh International Conference on Learning Representations, 2023b. http://ppp..pppperrrrre////////r
Salez, J. Sparse expanders have negative curvature. Geometric and Functional Analysis, 32(6): 1486-1513, September 2022. ISSN 1420-8970. doi: 10.1007/500039900--00668888 URL
http://dx. wwtp org 10. 10070000000300 020-0033---220000000 00618-3
Scarselli, F., Gori, M., Tsoi, A. C.,, Hagenbuchner, M., and Monfardini, G. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61-80, 2009, doi: 10. 109/TNN,,,00 2005605.
Sen, P., Namata, G., Bilgic, M., Getoor, L.,, Galligher, B., and Eliassi-Rad, T. Collective classification in network data. Al Magazine, 29(3):93, Sep. 2008. doi: 10.
v2913.2157. URL
https://ofe aaai org/ index. php/ almagaazinee/rrtiilee///ee////
Shlomi, J., Battaglia, P., and Vlimant, J.-R. Graph neural networks in particle physics. Machine
Learning: Science and Technology, 2(2)02 jan 2021. doi: 00.1088/2632-21555abb9999 URL
https://doi. org/ 10. 00011008/2338 2153/abbf9a.
Stewart, G. and Sun, J. Matrix Perturbation Theory. Computer Science and Scientific Computing. Elsevier Science, 1990. ISBN 9780126702309, https:/tt////o wow.ooooo..ooole...ooooooooooooo de/books?id-
178PAQAAMAΑJ
Topping, J., Giovanni, F. D., Chamberlain, B. P., Dong, X., and Bronstein, M. M. Understanding over-squashing and bottlenecks on graphs via curvature. International Conference on Learning Representations, 2022. URL http:: //pperevi/oenreiiex
Tönshoff, J., Ritzert, M., Rosenbluth, E., and Grohe, M. Where did the gap go? reassessing the long-range graph benchmark, 2023.
Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., and Bengio, Y. Graph Attention Networks. In ICLR, 2018.
von Luxburg. U. A tutorial on spectral clustering. Statistics and Computing, 17(4):395 2007. doi: 10. 12210077/11222--077-3333--- URL URL.ittgs//aaa..oo//00000////// http:////.....001111220000000000
Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How powerful are graph neural networks? In International Conference on Learning Representations, 2019. URL httpss://openreriew.nt net/ forum?id=ry/ei id-mm//1-rrGG661mmmm
Zheng, C., Zong, B., Cheng, W., Song, D., J., Yu, W., Chen, H., and Wang, W. Robust graph representation learning via neural sparsification. III, H. D. and Singh, A. (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 11458-11468, PMLR, 13-18 Jul 2020. URL httttssss//pcceeeiinng mlr. wwwpprss/viii. vvlssvv11i 19tpz///eegn.......
Zhou, K., Huang, X., Zha, D., Chen, R., Li, L., Choi, S.-H.. and Hu, X. Dirichlet energy constrained learning for deep graph neural networks. Advances in neural information processing systems, 2021.
14

---

A Proofs
A.1 Proof of Proposition 3.2
Spectral analysis for general
For all n, the (normalized) Laplacian matrix of R, circulant: all rows consist of the same elements, and each row is shifted to the right with respect to the previous one. The first row of ((R,) is All circulant matrices satisfy that their eigenvectors are made up of powers of the nottr of unity, and that its eigenvalues are the DFT of the matrix's first row (Gray 2005). With this we easily obtain that its spectral gap is
In = (1, - 2. 0,....,,, 0, -2)-
A
Σ [k(k) k=0
22
1 ( 2
e 2n +e 12t =1 m
1 COS
2π
Because their conjugates and their linear combinations are also eigenvectors, we can get real eigenvectors as ry (k) (y(k) -((k) sin 2rjk Alternatively, we can get yj (k) (w) (k) 2i
As stated before, one possible set of eigenvectors wy(kk = exp (2mjh n
cos 2rjk
2
We only need to focus on the (pair of) eigenvectors for j = Note that they are orthogonal to each other. Because they are both eigenvectors with the same eigenvalue λ2. all linear combinations of them will also be eigenvectors with eigenvalue A This multiplicity lets us choose any of these vectors to fulfill Eldan's 's criterion. limitation of our algorithm is that, in cases of multiplicity, can only choose one of them, potentially giving that edge disadvantage the Lemma holds as long as there exists one that fulfills it, but not necessarily the one we have chosen.
The norms of I1 and y1 are - Therefore, the norm of any linear combination of them is
|| vy || v 3 V 12 + U², We denote the normalized linear combination of and y1
flam)) V2(uz1 + vv)) V Vn(n² + v2)
Our choice will be f1 == 3, v = 1, i.e. fl (3.1)
+3)
v5n
Elements of the criterion for general n. As per Eldan et al. (017). the first cigenvector of the new
graph's normalized Laplacian is fo 1 Σ dr. In case: fo(k)
/3 if i E {u,
V2(=+1)
if lo & {u, oJ. With it we calculate the projection, dependent on the eigenvector fi: and 2(++1)
V2
V3
P/ = Σ (Kk) = Σ
fi(k) +
(fi(u) + fi())
2 1)
2 + 1)
k=0
k= kuu,
V3 - V2
22 (fi(u)+ +i())
We also have, for all n, a and v, that +d VI vd,+1
Y3-V2
/ We can
vd,+1
v3
update the criterion with these considerations: g(u, v, Rm)
Vdl +I VI Vdn fi(2)² + Vdy + dd
2fi(u)f(v))
=-P A1 - 2(1 -11
1((1)2)
Vd, +1
Vd. +1
Vd, + +ld, +1
V3 V2 ) 22(n ( +1)
( (1-cos (2xT) (²x)) (f(())+((())
1m
2 V 3
(fi(u)2 + f(())) 21((()
cos
n
15

---

Case n 8, (u, v) (0.3).
We choose /1 = s(a.1)
[3z1 +v1l
We have f1(0)
2vT0 and
<40
f1(3) = 1
203 Then:
1
2
3
2/2
2V10
2v5
40
1
3
(fi(1) A(19))
TV
2/5
1
V2
fi(u)((())
2v10 10 2/5
40
Finally, Eldan's 's criterion for 8, (u, v) 33, and our choice of fi g R,)
V3 v3-12 v2
(1- cos
cos
7
m
(fi (fi + fi(v)) - 2 cos
1
1
2
(fi(u)++ + fi(w)
V18
2
2f (f)
V3 (33 V2
V2
2
2
3
2
1
V2
1
+
3
V18
2
40
3
40
3
40
0.0000299 0.0194635 + 0.0235702 0.0038672 O.
In Table we check Eldan's criterion computationally for all examples; we also check whether both our proxy estimates truthfully indicate the sign of the real spectral gap difference. Eldan's criterion g(u, v, .) is calculated from the sparser graph's ' spectral properties, as well as APROXYADD essimatinng the spectral gap's difference when that edge is added. Mcanwhile, APROXYDELETE is calculated from the denser graph and tries to estimate the spectral gap of the pruned one.
When g(u, .) > O, it theoretically guarantees that Ad1 < O, i.e., that the addition of said edge is NOT desired. This holds in our table for the first and third rows, where the addition of each edge lowers the spectral gap. Our proxy values reflect it in both directions: APROXYADD is negative because the edge should not be added, and DELETE is positive because the edge should be pruned.
Note that, because of the aforementioned multiplicity of the ring's eigenvectors, if we choose another fi for the first row, Eldan's 's criterion might not be satisfied. For example, using the eigenvectors given by the library function np.linalg.ett eigh. the criterion yields value of -0.005904.
The second row shows an example of an edge that is desirable to be added. In this case, it is guaranteed that Eldan's criterion is negative. Our proxy values again accurately descriptive of reality: A ARROXYADD is positive and ÁPROXYDELETE negative.
Table 6: Computationally calculated criteria for the toy graph examples.
Sparser graph
Denser graph
{u.0} v)
Eldan's g(u, v..)
ARROXYDELETE
APROXYADD
A
{0,3]
0.003867
0.027992
-0.017678
-0.01002
g+
{0,5)
-0.146246
-0.064550
0.415994
0.071632
g+
{4,7)
0.004952
0.032403
-0.024739
-0.011584
A.2 Proof of Propositions
3.3 and 3.4
We choose oneddmmensi features to follow normal distributions dependent on their class: X, (11 1) for class (+), and X, ~ (- for class (-). After one round of mean aggregation, class (+) nodes with two intra-class neighbors will still have expected mean value of 1, because they will aggregate three features that follow the same distribution: from themselves and the two neighbors. However, nodes like X2, which have neighbor of each class, will have lower expected value: 2-1 = 3- In general, if (class (+)) node has p same-class neighbors and different-claat neighbors, 3
their representation after aggregation round will follow normal distribution / (itptt 1#1-g).
16

---

The smaller its expected mean is, the more it deviates from the original mean, and the less informative it gets. Table we show the expected values of each configuration dependent on the neighbors' classes as they appear our four considered graphs. The class (-) configurations are omitted because they are the same as the ones shown but with the opposite sign.
Table 7: Expected mean values of each neighboring configuration after round of mean aggregation.
Name
Neighboring configuration
Expected Mean
A
B
C
141+1-1
2
D
1+1-1-1 0
E
1+1+1-1-1
B
G neighboring conf. (b) neighboring conf. (c) g neighboring conf.
(d) g neighhoring conf.
Figure 4: Neighhoring configurations each of the four graphs from Figure T
Now we consider again the four graphs from Figure]] T In Figure we specify which nodes have which configuration from the set A, B, C, D, E) named in Table We arbitrarily choose orange nodes to be the negative class. After one round mean aggregation on each them, we can estimate the amount of class information remaining on the two classes by averaging the corresponding node representations of each node per class -that is, we average the four expected means for purple nodes and the four expected means for orange nodes. We calculate these values in Table 8 As intended to prove, they tend towards non-informative zero for both classes as the number of edges increases, and they follow the same order the smoothing rate curves plotted in Figure ((a) Proposition 3.3 is proved because values tend to zero -so both classes' averages get closer together- from G to G, and from G to both + and ++ Proposition 3.4 is proved because the values from G are more informative/further apart than the values from G+.
B How other label configurations affect the rings' smoothing rates
In Figure 5 we show how different configuration of labels for our example graphs affect their smoothing rate tests. In particular, will analyze the result when added edges are intra-class instead of inter-class, as well as when the label distribution actively goes against the graph structure.
As first modification (Figure 5(c) rotate the labels so that edge {0, 3} is now intra-class; this makes edge (4, 7} from 9 intra-class, too. It is reflected in its smoothing rate plot in two main ways. First, the distance between graph g and is not as wide, because the extra intra-edge in G does not cause as much smoothing as the inter-class edge from the original configuration does. Second, graph G is now the least smoothed. This might be because the two edges aid in isolating the flow of information between the two, very distinct classes; note that this graph also the smallest spectral gap, so the configuration of labels and the graph structure work towards the same goal.
17

---

Table 8: Neighboring configurations for each graph, and their average value after a round of mean aggregation.
Node
G
G
G
G
X6
B:
B: 3
3
3
X7
A: 1
A:
A:
C:
Xo
A:
C:
E:
C:
X1
B:
B:
B:
B: 3
2+3
143+
143+3
3+3
Average:
0.667
0.542
0.467
0.417
4
X2
-B:
-B:
-B:
-B:
X3
-A: -1
-C:
-C:
-C:
X1
-A:
-A:
-A: -1
-C:
X5
-B:
-B:
-D: 0
-B:
2+
1+ ~ 0.458
1 R 0.417
Average:
0.667
R 0.542
MAS
Order smoothing
Order of smoothing
(a) Original conf. (#1)
(b) Smoothing rate (#1)
(c) Conf. (#2)
(d) Smoothing rate (#2)
MSB
Order of smoothing
Order of smoothing
(e) Conf. (#3)
(f) Smoothing rate (#3)
(g) Conf. (44)
(h) Smoothing rate (#4)
Figure 5: Different configurations of labels/features for the example graphs of Figure as well as
their respective smoothing rate akin Figure [[a) Figure5(a)iis [ the original configuration, for direct comparison. Figure rotates the labels and achieves more intra-class edges. Figure 5(e)
achieves the same amount of intra-class edges but separates nodes with the same labels. Figure 5(g alternates between classes and is a worse configuration to learn.
As a second modification (Figure5(() we alternate classes two by two nodes at a time. This makes (0,3) and (4, 7} intra-class again, so it is directly comparable to the previous disposition. However, the edges in G are not dividing the two classes so distinctively. This makes its smoothing occur more quickly than before, directly related its lower spectral gap. Another relevant aspect of this graph that, still, the pruned graph G smooths less than G. even when the pruned edge is intra-class, and even if the spectral gap has increased; it another instance of both mitigating over-smoo and over-squashing.
par with the base graph. We consider this phenomenon to be
we propose configuration that is actively counterproductive to the structure of ring, by alternating nodes of different classes one by one. As much as the spectral gap increases with the deletion of edge (0,3), the ring G is worse structure for the right kind of information to flow, and worse to avoid getting dissipated this particular case. This unveils the ultimate limitation of not taking into account the task in rewiring method, which is trade-off to assume.
Lastly (Figure 5(g
18

---

C
Algorithms
Here include the corresponding algorithms: PROXYDELETE T PROXYADD ELDANADD
33, and ELDANDELETE (4.
Algorithm Proxy Spectral Gap based Greedy Graph Sparsification (PROXYDELETE)
Require: Graph G (V, num. edges prune N, spectral gap (C()) second eigenvector f. repeat
for (u,v) E & do
Consider 9 = 9 (u, v).
Calculate proxy value for the spectral gap of & based on Eq. (1
\1(Cg) = \1(g)) - ((fu fo)² X1 (Lg) (f + f.))
end for
Find the edge that maximizes the proxy: (u",0)) = argmax X1 X1 (Lz).
(u.N)Eε
Update graph edges:
(u ,0)
Update degrees: d = d, 1, du-
Update eigenvectors and eigenvalues G accordingly. until N edges deleted.
Output : Sparse graph G EV,8).
Algorithm 2 Proxy Spectral Gap based Greedy Graph Addition (PROXYADD)
Require: Graph G (V, E"), num, edges to add N, spectral gap A1 (CC). second eigenvector of G.
repeat
for (u, u) E & do
Consider G U (u,
Calculate proxy value for the spectral gap of ف based on Eq. (1)
Xi(Cg) R (CG) + ((fu f.)² >1 (S + fe)
end for
Find the edge that maximizes the proxy: (ut, bttt argmax X (Cg).
(a.e)E
Update graph edges: & = E (u+, v*).
Update degrees: du+ = du+ + 1, dut +
Update eigenvectors and eigenvalues of G accordingly. until N edges added.
Output : Denser graph 9 = EV,
Algorithm 3 Eldan based Greedy Graph Addition (ELDANADD)
Require: Graph G (V, E), num. edges to add N, spectral gap Y1 (Cg), top eigenvector G.
repeat
for edges (u, v) E & do
Consider 9 = G U (u, v).
Compute projection P3 = (f. fo).
Compute Eldan's 's criterion g(u, Lg).
end for Find the edge that minimizes the criterion: (ut, ut)
argmax -g(u,v Lz). (u.vee
E Euttt v+). Update degrees d d,,t + + 1, dhy +
Update eigenvectors and eigenvalues of G accordingly. until N edges added.
Output Denser graph 9 EV,
19

---

Algorithm 4 Eldan based Greedy Graph Sparsification (BLDANDELETE)
Require: Graph 9 (V,E), num. edges to prune N, spectral gap À (Cg), top eigenvector f of g.
repeat
for edges u. 1) E & do
Consider = G \ (u, v).
(Note that the denser graph is the original G, so we require approximations of and X (Lg)
from the sparser G.]
Estimate eigenvector / from f based on the power iteration method.
Estimate corresponding eigenvalue A1 (fig) based on Eq. T
Compute projection Pj- = fo).
Compute Eldan's 's criterion g(u, v, fg).
end for Find the edge that maximizes the criterion: (u,, , argmax ((,, v, Lg)
(u,0)EE
E (wT,e"). Update degrees du- = du- - 1, 1, dv- Update eigenvectors and eigenvalues of G accordingly. until edges deleted.
Output Sparse graph ف = (V,8).
D Spectral pruning can slow down the rate of smoothing
In section we have demonstrated the possibility of addressing both over-squashing and over- smoothing via spectral gap based pruning in a simple toy graph setting. Below we present the results on real-world graphs, where spectral pruning can help slow down the rate of smoothing. We adopt the same Linear GNN setup (Keriven 2022). In Figure 6 we present two homophilic datasets (Cora and Citeseer) and two heterophilic graphs (Texas and Chameleon). For each of these experiments we add edges using FoSR (Karhadkar et al. 2023) and PROXYADD and delete edges using our proposed PROXYDELETE method. FOSR, which optimizes the spectral gap by adding edges, aids in mitigating over-squashing but inevitably leads to accelerating the smoothing rate. Conversely, if delete edges using our PROXYDELETE method, the rate of smoothing slowed down. is also evident that our pruning method is more effective in heterophilous graph settings. This is likely due the deletion of edges between nodes with different labels, thus preventing detrimental smoothing. We substantiate this by measuring the distance between nodes that have different labels, which should stay distinguishable. That is, our method deletes edges between nodes of different labels thus preventing unnecessary aggregation. We report the cosine distance for heterophilic graphs in Table before training, after training on the original graph, and after training on the pruned graph. From the table it is clear that pruning edges increases the distance between nodes of different labels. Another popular metric in the literature to measure over-smoothing Dirichlet energy, which can only measure the degree of smoothing, but not whether it is helpful for a learning task. To keep up with the trend, we plot the Dirichlet energy vs. Layers (Roth & Liebig. 2023) in Figure [on Cora and Texas. It is clear from the figure that our method slows down the decay of Dirichlet energy. Note that, since our method works purely on the graph topology. cannot improve the Dirichlet energy like specialised methods (Zhou et al. 2021 Roth & Liebig 2023
Rusch et al. 2023b).
In recent work by Azabou al. (2023), the authors also show similar experiments by introducing additional nodes to slow down the rate of message passing and thus slowing down the rate of smoothing. We achieve similar effect just by pruning edges instead of introducing additional nodes.
E
Additional results
E.1
Node classification.
We perform semi-supervised node classification on the following datasets: Cora McCallum et al.) 2000), Citeseer (Sen et al. 2008) and Pubmed (Namata et al. 2012). We report results Chamelcon,
20

---

24
Original
20
Original
FoSR
FoSR
MSE
ProxyAdd
MSB
ProxyAdd
ProxyDelete
ProxyDelete
100
3.
27
12
Order of smoothing
Order of smoothing
(a) Cora dataset with 200 edges added (FoSR, PROXYADD) and 20 deleted (PROXYDELETE),
(b) Citeseer dataset with 200 edges added (FoSR, PROXYADD) and 100 deleted (PROXYDELETE).
26
Original
FoSR
MSE
Original
MSE
ProxyDelete
ProxyAdd
FoSR
ProxyAdd
ProxyDelete
Order of smoothing
Order of smoothing
(c) Texas dataset with 200 edges added (FoSR, PROXYAdD) and deleted (PROXYDELETE).
(d) Chameleon dataset with 200 edges added (FoSR, PROXYAdD) and 250 deleted (PROXYDELFTE).
Figure 6: We show on real-world graphs that spectral pruning can not only mitigate over-squashing by improving the spectral gap but also slows down the rate of smoothing, thus effectively preventing over-smoothing as well.
Table 9: Cosine distance between nodes of different labels before and after deleting edges using PROXYDELETE.
After Training (OriginaGGraph)
After Training (PrunedGraph)
Before Training
Dataset
Comell
0.72
0.87
0.83
Wisconsin
0.72
0.77
0.86
Texas
0.68
0.62
0.80
Chameleon
0.99
0.91
0.96
Squirrel 0.98
0.82
0.89
Actor
0.83
0.95
0.99
Squirrel, Actor and the WebKB datasets consisting of Comelll Wisconsin and Texas. Our baselines include GCN (Kipf & Welling, (017) without any modifications to the original graph, DIGL by Gasteiger et al. (2019), SDRF by Topping al. (2022), and FoSR by Karhadkar al. (203)). We adopt the public implementations available and tune the hyperparameters to improve the performance if possible. Our results presented in Table TO We compare GCN with edge modifications, GCN+DIGL, GCN+SDRF, GCN+FoSR, GCN+RandomDellct. GCN+ELDANDELPE delete the edges, GCN+ELDANADD where we add the edges according the criterion from Lemma 3.1 and PROXYADD and PROXYDELETE which use Equation (1) to optimize the spectral gap directly, The results for GCN+BORF (Nguyen al. 2023) are taken from the paper directly, hence NA for some datasets. The top performance is highlighted in bold. GCN+FoSR outperforms all methods more effective in increasing the spectral gap (see Table I6]. On the remaining six datasets, our proposed methods both with edge deletions and additions outperform FoSR and SDRF, while outperforming all other baselines on all datasets. For training details and hyperparameters, please refer to the Appendix 19
where we
on Cora, Citeseer and Pubmed, which are homophilic. Yet. GCN+PROXYADD
E.2 Graph classification with GCN and R-GCN
We conduct experiments on graph classification with GCN (Kipf & Welling 2017 and R-GCN (Battaglia et al. 2018) backbone to demonstrate the effectiveness of our proposed rewiring algorithms.
21

---

121 PPogestraa
Dirichlet energy
Dirichlet ennrgy
18-
1374
12"
1274
12:
Layers
Layers
(a) Cora dataset with 50 edges
(b) Texas dataset with 50 edges added (FoSR) and 100 deleted (PROXYDELETE).
added (FoSR) and 50 deleted
(PROXYDELETE).
Figure 7: We measure the Dirichlet energy and plot it for increasing depth a homophilic dataset, Cora and a heterophilic dataset, Texas. For increasing depth, we can see PROXYDELMAX slows the decay of Dirichlet energy.
Table 10: We compare the performance of GCN augmented with different graph rewiring methods on node classification.
Methed
H
Palamed
Caneel 'N 0.1227
Wisconsin
0.177
Tesas
0.2167
Chameleon 14 0.2474
Squinel
0,2174
87.22s0:40
77.
53.5241.55
50.40111
GUN&DIGLL
83.31:0.79
73 29e11.1
57.3566.46
26.
39.95
OCN+SIDRE
07.5420.88
78.43411
58.7843.22
60.2544.777
31.67a1).36
41.30a1.36
38.9820.46
DCN4FiSR
91.44-0.39
82.13+0.31
91,4940.10
46
13.50-1.75
38.0+00.1
46.64-0.63
73+0.67
GON+ELDANDEELET
87.00.0.16
78.0810055
87.3320.07
65.1361.50
67.841145
70.53+1.23
43.6210.11
$2.5120.55
48 8910.40
GUN-ELBANN ALD
88 88.38-0.12
79:45 +0.37
87.17551
69.05e1.50
64.08+1 /63
57. 1illle1111 13
48.0 59
51.6621).45
89.10=0:70
78.92211.54
$7.52211
60.5421.43
67:75+1.64
74.21+1.25
54,30g0.30 59
43. (3.5521).33
DCN-PROONYDLLTTE
87.51-0.81
78 68 +0.55
87. 39+00001 11
66 1.67
66 16+
72: 36-161111 35
43. 5..5220.2
55.88+0.77 70
48 90+00
GCN- BEN-DAADONDEELETE
87 87.30s0.31
78, 78.34400.38
$7.1520.16
63.9742.50
61. 61.71+2.73
63.9745.41
29.5720).4
46.0721100
40.6 40.6320044
GON+BORF
87 $7.50e0.20
73 73.808801.30
NA
50.80ee1.13
50 30.30000.30
49.40be1.20
NA
61.50e0040
NA
Our experimental setting is the same that of FoSR by Karhadkar et al. (2023), with the difference being we tune our hyperparameters on 10 random splits instead of 100. The final test accuracy is averaged over 5 random splits of data. We compare results with FoSR by Karhadkar et al. (2023). For the IMDB-BINARY BINARY, REDDIT-BINARY and COLLAB datasets there are no node features available and have to be created. For fair comparison and MUTAG the results are taken from the values reported in the paper. The results are reported in Table 11 and 12 From the tables it is clear that proposed algorithms are effective in increasing the generalization performance even for graph classification tasks.
FoSR on these datasets. For ENZYMES
Table 11: Graph classification with GCN comparing FOSR, ELDANADD and PROXYADD.
Method
ENZYMES
MUTAG
INDB-BINARY
REDDIT-BINARY
COLLAB
PROTEINS
GCN+FoSR
25.06+0.50
80.0020.80
68.8024
80.01=0.02
80.30+0.00
73.42 = 0.41
GCN+ELDANADD
26.36+0.01
82. 16+0033
75.8420.01 75.00=0.02
81.03+0.02
81.82+0.97
70.53+0.86 86
GON-PROXYADD
27.39:0.01
85.00=0.00
78.20=0.01
79.52+0.01
76.53+0.02
Table 12: Graph classification with R-GCN comparing FOSR, ELDANADD and PROXYADD.
Method
ENZYMES
MUTAGG
IMDB-BINARY
REDDIT-BINARY
COLLAB
PROTEINS
R-GCN+FOSR
35.63+0.58
84.45+0.77 77
70.
80.01+0.02 79.76=0.17
78.0440.8
73.79+0.35
R-DDN-DDD
30.55=0.16
85.80+0.20
76.32:0.07
80.6940.01
72.01+0.04
P.GN-ADDOYYADD
33.1242.74
78.0=5.51
73 73.9622.25
87.93=0.61
80.22+1.13
73.3242.78
E.3
Node classification using Relational-GCN
In Table 13 we compare FoSR (Karhadkar al. 2023) and our proposed methods that use Eldan's
criterion for adding edges and the PROXYADD method with Relational GCCn backbone on 9 datasets.
22

---

We adopt the experimental setup and code base of (Karhadkar et al. 2023), with the exception of averaging over 10 random splits of data instead of 100.
Table 13: Node classification using Relational -CCns comparing FOSR, Eldan's criterion and PROX- YADD.
Mechod
Cora
Citeseer
Pubreed
Cornell
Wisconsin
Texus
Actor
Chameleon
Squirel
R-GCN+FoSR
87.2820.67
73.81
68.6110.28
71 6L62222.8 88
76.0715
75. 25.4013.777 77 36.1920.49
39 19.8312.700 70
34.80u
R-GON-ELDANARD
87 37.38=1.00 .03
73.7261.15
88. S850 20
73.7866.30
77.45+3.19
78.37a2.75
34.75z00.40
43.20e:1.2
33.79:081
ROCCNPROXYADD
87,42=0.01
75.82:0.09
89.17 0.42
70.0010.20
77.45x0.40
75.6740.10
35,0520.35
42.58&1.20
33.03&1.40
F Update period, empirical runtimes and spectral gap comparisons
In $4.1 we have discussed the time complexity analysis of our proposed algorithms. Recall, that our algorithm has a hyperparameter M, the number of edges delete after ranking the edges using our proxy. For edge additions, the candidate edges that can be added are large, thus we can resort to sampling a constant set of edges to speed up the process. All of our experiments in $5 were conducted with M 1. However, it is possible to further reduce the overall runtimes by tuning the value M, that is, how many edges we can modify before we have to recalculate the proxy to rank the edges again. This is shown in Table 15] where we compare our algorithms with M = 1 and .M = 10, for 50 edge modifications. It is clear that although M leads to better spectral gap improvement, M 10 is also valid updating period which induces enough spectral gap change while simultaneously bringing down the runtime (also presented in Table [4] considerably, especially for large graphs. To further evaluate the trade-off between the update period and its effect on GNN test accuracy, we use PROXYADD and DELETDELETE with different M updates on Cora and Texas datasets modify 50 and 20 edges respectively. This is shown in Figure 8 Although more frequent update points to better test accuracy. update periods with (5, 10) also yield competitive results. Thus reinforcing the fact that our proposed methods can be computationally efficient and can help in improving the generalization. In Table 16 we report the spectral gap changes induced by FoSR (Karhadkar al. 2023), our proposed Eldan criterion based addition and deletions and also the Proxy versions of addition and deletions. In Table 17 we provide the runtimes for large heterophilic datasets (Platonov et al. 2023).
Test Accuracy
FR: Delete
PRuAad
Test Accuracy
PR Rdd PR-Deeete
4615-
6625
Update Period
Update Period
(a) Test accuracy for Cora with M {1. 5, 10, 25} update periods, We ad- d/delete 50 edges.
(b) Test accuracy for Texas with M {1, 5, 10, 20} update periods. We ad- d/delete 20 edges.
Figure 8: We investigate the trade-off between how frequently we need to update the ranking criterion vs. the test accuracy for GCN on Cora and Texas for node classification.
Table 14: Runtimes for 50 edge modifications in seconds.
Method
Cora
Citeseer
Chamelcon
Squirrel
FoSR
4.69
5.33
5.04
19.48
SDRF
19.63
173.92
17.93
155.95
PROXYADD
4.30
3.13
1.15
9.12
PROXYDELETE
1.18
0.86
1.46
7.26
23

---

Table 15: Empirical runtime (RT) comparisons with different update periods for the criterion for 50
edges. We also report the spectral gap before (SG.B) and after rewiring (SG.A).
Method
Cora
Citeseer
Chameleon
Squirel
Measures
SG.B
SG.A
RT
SG.B
5G.A
RT
SG.B
5G.A
RT
SG.B
SG.A
RT
PROXYADD (M=1)
0.004788
0.0240
41.82
0.0015
0.012
27.70
0.0063
0.018
9.24
0.051
0.069
75.89
PROXYDELETE (M=1)
12.82
5.47
0.0063
0.0064
7.51
0.053
PROXYADD (M=10)
0.004788
0.018
4.30
0.0015
0.0067
3.13
0.0063
0.0160
1.15
0.051
0.058
9.12
PROXYDELETE (M=10)
1.04
0.0063
0.0527
Table 16: We compare the spectral gap improvements of different rewiring methods for 50 edge modifications. From the table it is evident that our proposed PROXYADD and PROXYDELETE methods improve the spectral gap much better than FoSR.
Method
Cora
Citeseer
Chameleon
Squirrel
Spectral Gap Changes
SG. Before
SG. After
SG. Before
SG. After
SG. Before
SG. After
SG. Before
SG. Afler
FoSR
0,0047
0.0099
0.0015
0.0027
0.0063
0.0085
0,051
0.052
PROXYADD
0.0047
0.024
0.0015
0.012
0.0063
0.018
0.051
0.069
DELETE
0.0047
0.0059
0.0015
0.0018
0.0063
0.0064
0.051
0.053
ELDANADD
0.0047
0.0047
0.0015
0.0039
0.0063
0.0085
0.051
0.052
ELDANDELETE
0.0047
0.0074
0.0015
0.0099
0.0063
0.0059
0,051
0.053
Table 17: Spectral gap changes and empirical runtimes for Large Heterophilic Datasets.
Dataset
SG. Before
#Edges
SG. Afler
AddingTine Time
#FdgesDeleted
SG. After
PruningTime
Roman Empire
3.6842e-01 07
7.5931e-07
124,34
3.6875e
Amazon Ratings
0.000104825
10
0.000230704
380.62
50
0.000104840
62.69
Minesweeper
0.000376141
0.000375844
164.44
20
0.000376141
15.5
G Pruning at initialization for graph lottery tickets
In Table 18
present the results for Pruning Initialization for finding graph lottery tickets. We first prune the input graph to the required sparsity level and then the weights are iteratively pruned by magnitude similar to the approach proposed by (Chen al. 2021). From the table it is clear that, at least for moderate graph sparsity (GS) levels for Cora dataset, that is around GS = 18.75%. our proposed
UGG UGS and PROXT attain comparable performance UGS. On Pubmed for different graph sparsity levels we outperform UGS. Meanwhile, our method fails to identify winming tickets for Citeseer. We use the public implementation by the authors (Chen et al.. 2021) for all our lottery ticket experiments. For all experiments we report the test accuracy on node classification averaged over runs. Except for Pubmed which could only be averaged over runs.
Table 18:
We perform pruning at initialization to find graph lottery tickets. We compare UGS with our proposed methods for varying graph sparsity (GS) and weight sparsity (WS) levels.
Cora - -el--G((1185555) WS(89.88%)
Citeseer )
Pubmed - (1)1190019):56883333999
Method
Acccuracy
Method
Accuracy
Method
Accuracy
UGS
79.54
LGS
72.20=0.60
UGS
77.75+1.04 .04
ELdan-UGS
79. 19.1000.07
Eldan-UGS
68. 15..5.0.65
Eldan-UGS
79.80=0.00
ProxyDelete-UGS
78.66+0.73
PROXYDELETE-UUS
69.76=0.65
ProxyDelete-UGS
78.20=0.20
Cora GS(57.59%) WS(98.31%)
Citeseer- 155
Pubmed CS156.47%)
UGS
72.65+0.55
UGS
68.7020.25
UGS
76.80=0.0
ELd
72.40=0.40
Eldan-UGS
66.55=0.15
Eldan-UGA
77.70=0.08
ProxyDelete-
70.49+0.27
PROXYDELETE-UGS
1.79
ProxyDelete UGS
77.80+0.00
Cora GII--GS(77811) WS(98.239))
Citeseer- GS182269%)
Pubmed - GSS811009)):W5((77.00
UGS
68.65+0.95
UGS
66.05=0.45
UGS
76.25=0.45
Eldan-UGS
67,20+0.1 10
Eldan-UGS
62.60+0.60
Eldan-UGS
72.80=0.00
ProxyDelete-UGGS
64.4620.47
PROXYDELETE-UUG
61.19:0.29
ProxyDelete-UGG
74.70=0.00
24

---

H Training details and hyperparameters
We instantiate 2-layered GCN (Kipf & Welling 2017) for semi-supervised node classification, the Planetoid datasets (Cora, Citeseer and Pubmed) are available as pytorch geometric datasets. For the WebKB datasets we use the updated ones given by Platonov al. (2023). We a 60/20/20 split for training/essting/aliidaoo respectively for all datasets. We perform extensive hyperparameter tuning the validation and finally report test accuracy averaged over 10 splits of the data (Chen al.) 2018). We use the largest connected component wherever available. The same experimental settings hold for other baselines DIGL. SDRF and FoSR. For node classification using R-GCNs, we also use a 3 layered GCN, this is highlighted in Table 20 with other hyperparameters. For graph classification, we use the same experimental setup as (Karhadkar et al. 2023), we use 4-layered GCN and R-GCN versions. For the larger heterophilic datasets, we use the experimental setup given by the authors (Platonov al. 2023). We set the learning rate to {3e 3, 3e 4), dropout 0.32, and the hidden dimension size to 512. For GATs, the attention heads are set to 8. The datasets are split into 50%/25%/25% for train, test and validation respectively. We tune our edge modification algorithms on the validation set. The final test accuracy is reported averaged over 10 random splits run for 1000 steps. Skip connections and normalization (Ba et al. (0T6) is used to facilitate training deeper models. We PyTorch Geometric and DGL library for experiments, All experiments done on V V100 GPUs. Our code httph: //tt:////g is available.
Table 19: Hyperparameters for GCN+our proposed rewiring algorithms.
Dataset
LR
HiddenDimension
Dropout
ELDANADD
ELDANDELETE
PROXYADD
PROXYDELETE
Cora
0.01
32
0.3130296
20
100
Citeseer
0.01
0.4130296
20
Pubmed
0.01
128
0.3130296
50
100
20
50
Comell
0.001
128
0.4130296
100
5
50
20
Wisconsin
0.001
128
0.5130296
5
10
Texas
0.001
0.4130296
Actor
0.001
128
0.2130296
100
10
25
500
Chamelcon
0.001
128
0,2130296
100
50
50
200
Squirrel
0.001
128
0.5130296
100
1000
Table 20: Hyperparameters for R-GCN+PROXYADD on node classification
Dataset
I.R
Layers
HiddenDimension
Dropout
PROXYAdD
0.01
0.3130296
50
Citeseer
0.01
0.3130296
Pubmed
0.01
0.4130296
100
Cornell
0.001
128
0.3130296
Wisconsin
0.001
128
0.3130296
25
Texas
0.01
128
0.3130296
20
Actor
0.001
128
0,5130296
25
Chameleon
0.001
128
0.4130296
100
Squirrel
0.001
128
0.3130296
Table 21: Hyperparameters for graph classifica- tion with ACddEldanAdd
Table 22: Hyperparameters for graph classifica- tion with GCN PROXYADD
Danaset
1.R
Dropout
Hidden Dimension
EldanAd
Dotneet
I.R
Doepout
Hidden Dimension
ProxyAdd
ENZYMES
0.001
0.21 30796
32
20
ENZYMES
0.001
0.2130796
52
201
MUTAG
30296
MUTAG
0.3130206
IMDB-BINARY
0.3130296
REDDIT BINARY
0.001
0.2130296
REDDIT BINARY
0.001
0.2130296
COLLAB
0.001
0.21
32
10
COLLAB
0.001
0.21
52
10
PROTEINS
0.001
0,3130296
PROTEINS
0.001
0,3130296
25

---

Table 23: Hyperparameters for SDRF
Dotaset
LR
Dropout
Hidden
SDRF
C+
Cora
0.01
0.3130296
32
100
163
0.95
Citeseer
0.01
0.2130296
32
84
180
0.22
Pubmed
0.01
0.4130296
128
166
115
1443
Comell
0.001
0.21 30296
128
126
145
0.83
Wisconsin
0.001
0,2130296
128
89
1.64
Texas
0.001
0.2130296
128
136
7.95
0.01
0,4130296
128
3249
7.91
Chameleon
0.01
30296
128
2441
252
2.84
Squirrel
0.01
0.2130296
128
1396
Table 24: Hyperparameters for FoSR.
Table 25: Hyperparameters for DIGL.
Dataset
LR
Dropout
Hidden Dimension
FrSR
Dotaset
LR
Dropout
Hidden Dimension
Cora
0.01
0,5130296
128
50
Cora
0.01
0.41
32
0,0773
128
Citescer
0.01
0,3130296
128
Citeseer
Pubmed
0.01
80296
128
50
Pubmed
0.01
0.41
128
0.1
128
Cornell
0.001
0,2130296
128
100
Comell
0.001
0.41
128
0,1795
Wisconsin
0.001
0.21 30296
128
100
Wisconsin
0.001
0.31
128
0.1246
0,4130296
Texas
0.001
0.41
128
0,0206
32
Actor
0.01
30296
128
100
Actor
0.01
0,21
128
0,0656
0.4130296
Chameleon
0.41
128
0.0244
Squimel
0.01
0,2130296
128
100
Squirrel
0.01
0.41
128
0,0395
32
Table 26:
Hyperparameters for graph classifica- tion with R R-GCN+EldanAdd
Table 27: Hyperparameters for graph classifica- tion with R-GCN PROXYADD
Hidden Dimenssio
Dropout
EldanAd
Dropout
ProxyAdd
ENZYMES
0.001
D.21 30796
ENZYMES
0.001
0.21 20296
10
MUTAG
0.001
0.3130296
64
40
MUTAG
0.001
0.3130256
52
10
IMDB-BINARY BINARY
0.001
0,3130296
IMDB- BINB-B
0.001
0.3130296
0.2130296
0.2130296
COLLAB
0.01
0.1130296
COLLAB
0.01
0.1130296
PROTEINS
0.01
30296
32
05
PROTEINS
0.01
0,4130296
10
26

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We provide both theoretical and experimental proof to substantiate claims made in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discuss computational efficiency of our proposed algorithms and its approximation quality.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
27

---

Answer: [Yes]
Justification: Informal proofs provided in the main paper. Formal proofs provided in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proof' in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: We provide all the hyperparameters and our code base to reproduce the results reported in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
28

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes)
Justification:
We provide the code base with the instructions reproduce our results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ "cippscc/puullc//uuu /otee//guuddde/eeoSuuubbmiibii ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
Yes in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
We provide confidence intervals for all the experiments conducted.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Discussed as part of the training details in the appendix.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httpp//s//.aaapp..ooooooo/////aa
Answer: [Yes]
Justification: [NA]
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work deals mainly with understanding the constituent factors affecting the generalization performance of graph neural networks. Although GNNs themselves have broad range of applications, our method itself doesn't have societal impact as such.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
30

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: No such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All codes and datasets used properly attributed.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
31

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: No new assets released.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
No crowdsourcing or human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Not applicable.
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
32


Reviews:
[{"review_id": "GPsYBbJLoS", "reviewer": "Reviewer_p1uY", "summary": "Inspired by the Braess phenomenon, the paper proposes a Greedy graph pruning algorithm (PROXYDELETE) that maximizes the spectral gap in a computationally efficient way to simultaneously address over-smoothing and over-squashing of GNNs. The paper then verifies the empirical effectiveness of the method on long-range and heterophilic graph tasks, and pruning graphs for lottery tickets", "questions": "1. I don't see how the findings in Section 3 suggests that \"deleting edges can address over-squashing and over-smoothing simultaneously.\" For example, from Fig 2, how could one conclude that \"deleting edges helps reduce over-smoothing, while still mitigating over-squashing\nvia the spectral gap increase.\" Could you clarify?\n\n2. For clarification, does Lemma 3.1 from Eldan el al. 2017 applies only to Erdos-Renyi graphs or general graphs? As in line 2017 it says that their study is for random graphs.\n\n3. Any justification why for spectral expansion, the proxy method does better than Eldan criterion in Section 4.3?\n\n4. How would the method compare to random edge-dropping baselines such as DropEdge [1] in the literature?\n\n5. I think it would be good to include the real run time of the method as a plus in the main text, as I think this is a main advantage of the method.\n\nReferences\n\n[1] Rong et al. DropEdge: Towards Deep Graph Convolutional Networks on Node Classification.", "limitations": "n/a", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. The paper is clearly written and easy to follow.\n2. Evaluation is done on a diverse set of tasks (long range, heterophilic, GLT), showing the empirical effectiveness of the method to certain extent.\n3. The method is more principally designed than the common random edge dropping baselines in the literature.\n4. The method seems to be efficient in real time.", "weaknesses": "1. The theoretical analysis (proposition 3.2-3.4) in Section 3, while it is interesting given the historical context of the Braess’ paradox, is completely based on a specific contrived example in Figure 1. How much the result derived from this example can generalize to general graphs, even a class of general graphs is unclear. \n\n2. The experimental setups are not consistent throughout the paper. The discrepancies that make the claims in the paper seem not reliable in the sense that they might overfit the specific examples:\n    - The inspiration is drawn based on the contrived example.\n    - To show that the increase in spectral gap can help with the linear ridge regression task, the heterophilic dataset Texas is used; however, there is no clue that the method indeed leads to spectral gap expansion there, nor spectral gap expansion indeed leads to improvement on that data, even we suppose that the method led to spectral gap expansion there.\n    - Spectral gap expansion is then shown in Erdos-Renyi graphs in Section 4.3.\n\nThese three graphs are three specific graphs (contrived example, Texas and ER graphs). How they are connected to each other and fit together is unclear to me.\n\n3. While the authors show that their Proxy method is better at spectral expansion than Eldan criterion in Section 4.3 on ER graphs, Eldan criterion seems to on par or even outperform Proxy in many setups across all tasks considered in Table 1-5. Wouldn't this contradict the main idea of the paper that \"spectral expansion\" leads to better performance?\n\n4. I think the paper can be better positioned, too. I don't quite see how the current literature put over-smoothing and over-squashing \"diametrically opposed\". My understanding is that the over-smoothing theory also have a direct spectral connection. For example, see [1] and [2] for the bounds derived for GCNs and attention-based GNNs respectively, which is directly related to the spectral gap of the graph.\n\n\nReferences\n\n1. Oono and Suzuki. Graph neural networks exponentially lose expressive power for node classification.\n\n2. Wu etl al. Demystifying Oversmoothing in Attention-Based Graph Neural Networks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer p1uY for the constructive feedback provided and valuable insights. We include answers for each of the points raised. Tables are located in the document on the global response.\n* W1. Our theoretical investigations have the purpose of providing a counterexample for the common hypothesis that over-smoothing and over-squashing have to be traded off against each other. It further provides an intuition when the Braess phenomenon can be exploited to alleviate these two problems simultaneously. In experiments, we show that this is a very common phenomenon and can be exploited in all studied real-world graphs. This demonstrates that our insights are clearly application relevant.\n* W2. Our experimental setup is consistent, as the relevant information is available for all datasets. The ring serves as existence proof -for which we obtain provable evidence regarding the spectral gap, over-smoothing, etc.- and, as a simple example, provides an intuition of how both over-squashing and over-smoothing can be mitigated simultaneously -since the current consensus is to view them as a trade-off [3]. For the linear ridge regression setup we have also included analyses for Cora, Citeseer (homophilic), Chameleon and Texas (heterophilic) in Figure 6 of the appendix. The ER graphs merely show that our proposed algorithms indeed lead to spectral gap optimization. In Table 16 and 17 we also present the spectral gap values before and after rewiring for Cora, Citeseer, Chameleon, Squirrel, Roman Empire, Amazon ratings and Minesweeper. As an overview, in the attachment (T1) we report a table of spectral gap changes for ProxyDelete, ProxyAdd, and FoSR on all datasets. The number of deletions varies depending on the size and type of dataset, yet note that the spectral gap is successfully increased (in all cases but Pubmed on deletions).\n* W3. To increase the spectral gap for improved GNN performance has been previously proposed in the over-squashing literature [2,3,4]. Our contribution is to point out that, by deleting edges, one can also achieve this goal, while reducing the over-smoothing rate. Note that spectral gap optimization is a label independent rewiring strategy. As our ring example (and the no free lunch theorem) suggest, no rewiring strategy can be universally optimal. For specific label distributions, Eldan’s criterion can therefore outperform ProxyGap. Yet, as it is similarly based on the Braess paradox, it has the same advantage of simultaneously addressing over-squashing and over-smoothing in principle. \n* W4/Q1. Some theory on over-smoothing draws on an analogy to random walks [3], where the spectral gap controls the convergence speed to the steady state and thus the rate of smoothing. According to this view, one would need to determine the right amount of smoothing: if it is too high, over-smoothing should occur; if it is too little, over-squashing hinders good GNN performance. In contrast, we follow the narrative of [6] that over-smoothing refers to unwanted neighborhood aggregation, which also depends on other aspects (like heterophily structure) and is directly deduced from GNN generalization performance. In our work we have described how this depends on features and node labels, which explains why our proposed method is particularly effective in heterophilic settings. Moreover, we have shown several and diverse real-world datasets where our method (1) reduces the rate of smoothing according to the testbed of [6] (Figures 2, 6), and (2) increases the spectral gap by deleting edges that fulfill the Braess paradox. If over-smoothing and over-squashing were exclusively defined by the graph’s spectrum, both problems could not be decoupled, as has been the current assumption in graph rewiring literature [2,3,5]. We believe that these are relevant theoretical (as well as practical) insights that add a novel perspective to the discussion of graph rewiring.\n* Q2. It is a general condition for finite graphs. As they state in their section 1.3 (Approach): “We first obtain a general sufficient condition [...]  See Lemma 3.2 for details. Next, we specialize this general condition to Erdos-Rényi random graphs…”. We use their Lemma 3.2.\n* Q3. Eldan gives a sufficient condition or a guarantee that the paradox occurs when deleting the specified edge, but it does not give a direct measurement of the magnitude with which the spectral gap increases. This is why the quantity is generally more conservative than the proxy value.\n* Q4. DropEdge [1] proposes to drop a random percentage of edges of the graph during training, which acts as a graph augmentation technique, and they have access to the entire graph during their whole training procedure. Our method however is a pre-processing technique which actually sparsifies the input graph. During optimization the GNN model consumes a sparser, more incomplete version of the graph, thus making these two methods not directly comparable. We believe it to be more comparable to deleting edges randomly as a pre-processing step. We have nonetheless included both in the attachment (T2,3).\n* Q5. We appreciate the suggestion, and we also agree that efficiency is a big advantage of our method -which we included in Table 14. We would be happy to move it to the main text given sufficient space.\n\nReferences:\n* [1] Rong et al. DropEdge: Towards deep graph convolutional networks on node classification. ICLR 2020\n* [2] Karhadkar et al. FoSR: First-order spectral rewiring for addressing oversquashing in GNNs. ICLR 2023\n* [3] Giraldo et al. On the Trade-off between Over-smoothing and Over-squashing in Deep Graph Neural Networks. ACM CIKM 2023\n* [4] Banerjee et al. Oversquashing in GNNs through the lens of information contraction and graph expansion. AACCCC 2022\n* [5] Nguyen et al. Revisiting over-smoothing and over-squashing using Ollivier-Ricci curvature. ICML 2023\n* [6] Keriven, N. Not too little, not too much: a theoretical analysis of graph (over)smoothing. NeurIPS 2022", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "kQVXddRmyx", "reviewer": "Reviewer_1tmm", "summary": "The paper addresses the issue of over-squashing and over-smoothing in Message Passing Graph Neural Networks (MPNNs). It proposes a novel spectral gap optimization framework with rewiring, inspired by the Braess phenomenon, to mitigate both over-squashing and over-smoothing. The method is computationally efficient and is shown to improve generalization on various benchmarks.", "questions": "See weaknesses.", "limitations": "The authors have addressed the limitations and potential societal impact.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1.The idea that “certain edge deletions can maximize the spectral gap” is interesting and makes sense. The proposed framework is described in sufficient detail and easy to follow.\n\n2.The paper is well-written and easy to read.\n\n3.The experimental section involves a wide variety of datasets, providing a comprehensive evaluation of the method's performance.", "weaknesses": "1.How universally do the conditions for the inequality mentioned in Eldan's Lemma hold for graph datasets commonly used in the GNN field? Can the authors provide a theoretical or experimental analysis?\n\n2.Why are the results in Sec 4.3 inconsistent between the ER toy graph and other graph datasets? On the ER graph, adding edges leads to a continuous increase in the spectral gap, while deleting edges leads to an initial increase followed by a decrease. However, in common datasets such as Cora, adding edges seems to decrease the spectral gap, while deleting edges increases the spectral gap. Is there a misunderstanding on my part?\n\n3.Does the viewpoint of this paper, \"deleting edges to mitigate over-squashing,\" conflict with some previous rewiring methods that suggest \"adding edges to mitigate overfitting\"?\n\n4.Why were different baselines chosen for different experiments? For example, DRew was selected for Long Range Graph Benchmark datasets while FoSR was chosen for large heterophilic datasets. What are the insights behind these choices? Additionally, some rewiring methods were not selected as baselines, such as BORF [1].\n\n5.Some typos, ‘basline’ in L187, etc.\n\n \n[1] Khang Nguyen, et al. “Revisiting Over-smoothing and Over-squashing Using Ollivier-Ricci Curvature” ICML 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer 1tmm for the constructive feedback provided and valuable insights. We include answers for each of the points raised. Tables are located in the document on the global response.\n* W1. The criterion states that if the quantity $g$ is positive, then the Braess paradox occurs. In all of the datasets for which we have tested our EldanDelete method, we have found edges that satisfy this criterion, and we have been able to increase the spectral gap by deleting those edges. The criterion is not necessary for the Braess paradox to occur, and the Braess paradox is not necessarily found in all graphs, but we have been able to apply it to all real-world graphs we have tested -for at least one edge, and most times for many. In the attachment (T3) we include how many edges we can delete iteratively such that all have positive $g$ for the set of heterophilic graphs.\n* W2. The ER graph is a toy example to show that our proposed algorithms indeed help in spectral gap maximization. In Figure 3a, we add edges to the ER graph to show that our proposed EldanAdd and ProxyAdd lead to spectral gap improvements. In Figure 3b we use ProxyDelete and EldanDelete to show that we can delete edges and still increase the spectral gap. However, there might not be many edges that satisfy the criterion, and from a point onward, further deletions will eventually decrease the gap. This is no problem, since we only want to modify a small number of edges without changing the original degree distribution of the graph. For real-world graphs such as Cora, we present in Tables 16 and 17 the increase in spectral gap for both additions and deletions. We also present the values for ProxyDelete, ProxyAdd, and FoSR for other datasets in the attachment (T1). Concluding, our edge rewiring decisions always increase the spectral gap (unless we aim for more extreme graph sparsification when we aim for the smallest decrease that is possible).  \n* W3. Our proposed method is not in conflict with the previous literature but complements it. Current consensus for mitigating over-squashing suggests rewiring the graph as a possible solution. Our proposed method aligns with this motivation; more specifically, we show that deleting edges for spectral gap maximization can help mitigate both over-squashing as well as slow down the rate of detrimental over-smoothing, which challenges the commonly held assumption that both of these phenomena are a trade-off. Adding edges is still a powerful tool to solve problems in GNNs related to connectivity and generalization. However, in our work we highlight the advantage of edge deletions (which could also be combined with edge additions), as they could fight over-smoothing in addition to over-squashing.\n* W4. We believe FoSR to be the most comparable method to our own, as it is also a preprocessing spectral rewiring method. Therefore, we included it in all main comparisons. The Long Range Graph Benchmark datasets are conceived as a test to assess if proposed methods can indeed tackle over-squashing, for which we compare with the method that has been proposed for these particular tasks. We appreciate the suggestion to compare it to other rewiring methods. We report the results for FoSR on Long Range Benchmark datasets and also include BORF on other commonly used datasets (as obtained by the authors) in the attachment (T5,6).\n* W5. We thank the reviewer for noticing the typos which we will correct in a revision.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "I2H1566LgD", "reviewer": "Reviewer_1jBY", "summary": "This paper investigates the connection between oversmoothing/oversquashing, spectral gap optimization via edge deletions and additions, and the lottery ticket hypothesis. Specifically, they propose that sparsifying a graph can indeed improve its response to oversmoothing / oversquashing. Some theoretical studies is done over rings, and empirical results are given that show promising results in practice.", "questions": "Is it obvious that increasing the spectral graph is always good for message passing? First, the smallest nonzero eigenvalue only discusses the first partition, but if the task is multiclass classification, or regression, then the next smallest eigenvalues should also play a role. More generally, it seems that relying too much on Cheeger's inequality isn't precisely telling the whole picture; do you have thoughts as to whether a larger part of the spectrum might be used in this analysis?", "limitations": "none exist", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I thought this paper was really interesting, and takes an ambitious step to try to tie these topics together. Given that connecting foundational graph theoretical concepts with message passing in machine learning is still tenuous, I think the discussion in this paper is interesting and novel.", "weaknesses": "I think depending too much on rings is a bit too idiosyncratic; there's no reason to assume that most graphs in practice are ring-like, and the circulant structure is too specific. That being said, the numerical results are done over more general classes of graphs and still seem promising, so the general intuition is probably correct. \n\nThe condition in lemma 3.1 is a bit too specific Can you give some intuition as to what we should interpret from it?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer 1jBY for the constructive feedback provided and valuable insights. We include answers for each of the points raised. \n* W1. The ring graph has the specific purpose of providing a counterexample for the hypothesis that oversmoothing and oversquashing have to be traded-off against each other, which appears in previous analyses of the over-squashing literature [Karhadkar, Giraldo, Banerjee]. It also provides an intuition to the reader as to when the Braess phenomenon can be exploited to alleviate these two problems simultaneously. Our experiments on real-world graphs indeed demonstrate that our theoretical insights can be exploited and carried over into practice.\n* W2. [Eldan] gives a concise explanation of their lemma in mathematical terms in their section 1.3: “Given a general graph G, and another graph G+ obtained from G by adding a single edge, consider the second eigenvector v2 of the normalized Laplacian LG, and let v’2 be the projection of v2 away from the top eigenvector of LG+. If v’2 has a smaller Rayleigh quotient in G+ than in G, then the spectral gap decreases. This event can be explicitly expressed using v2, λ2(LG), and the degrees of vertices in G [...].” In the context of graph rewiring, it offers us a conservative criterion that even provides a guarantee that an edge deletion will lead to a spectral gap increase. We use the stated quantity to rank which edges to delete.\n* Q1. Controlling the full spectrum during rewiring is a very interesting idea. However, when one analyzes graphs with respect to random walks, the dominant factor in their convergence is the first eigenvalue. Smaller eigenvalues might play a role if the corresponding eigen directions are pronounced in the initial conditions. We consider this somewhat unlikely during general message passing. A different kind of problem would be to study the condition number of the graph; that is, the ratio between smallest and largest eigenvalue. In terms of how hard the learning problem is, the condition number could be important in a future analysis. However, this analysis would probably address trainability more rather than oversquashing or oversmoothing.\n\nReferences:\n* [Karhadkar] Karhadkar et al. FoSR: First-order spectral rewiring for addressing oversquashing in GNNs. ICLR 2023.\n* [Giraldo] Giraldo et al. On the Trade-off between Over-smoothing and Over-squashing in Deep Graph Neural Networks. ACM CIKM 2023.\n* [Banerjee] Banerjee et al. Oversquashing in GNNs through the lens of information contraction and graph expansion. In 2022 58th Annual Allerton Conference on Communication, Control, and Computing (Allerton).\n* [Eldan] Eldan et al. Braess's paradox for the spectral gap in random graphs and delocalization of eigenvectors. Random Struct. Algorithms 2015.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "rDhpZHpez1", "reviewer": "Reviewer_MxtA", "summary": "In this paper, the authors propose several variations of a graph pruning/rewiring algorithm, based either on an approximate maximization of the spectral gap, or on a more complex criterion based on Eldan's proof that deleting edges can counter-intuitively lead to an increasing spectral gap (which has been linked to the so-called Braess' paradox). They claim that, by maximizing the spectral gap, their algorithm fights over-squashing, while deleting edges naturally leads to combatting oversmoothing at the same time. They prove these properties on a toy example ring graph. They then show improvements when training GNNs on pruned graphs, mostly on heterophilic graphs, and also gives connections with the recent trend of finding \"lottery tickets\" in graphs.", "questions": "- Although the algorithm seems technically novel, the idea of maximizing the spectral gap has been extensively explored in various processes on graphs, and indeed in the vast literature of graph sparsification. Is there a connection between your approach and previous approaches for sparsifying graphs, see eg \"Spectral sparsification of graphs: theory and algorithms\" by Batson et al.\n\n- for graph lottery, are the \"-UGS\" versions of the algorithm differents ? It is never clearly explained.", "limitations": "See above", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- the paper creates connections between different literatures, all important in their own rights\n- the paper is well-written and articulated\n- the experiments are quite complete, with additional results in appendix", "weaknesses": "- some \"connections\" claimed by the authors appear quite tenuous or unclear, eg the graph \"lottery tickets\" seems a bit unnecessary and not really motivated (experiments are indeed interesting, but I would not say that playing with the spectral gap, a very natural and extensively studied idea, \"creates a connection with graph lottery tickets\")\n\n- my main comment is that, although the spectral gap is indeed used as a proxy for over-squashing, this is often motivated by Cheeger's inequality (as described by the authors), as the Cheeger's constant is admitted to be the \"real\" measure of oversquashing. However, unlike the spectral gap, it is easy to show that Cheeger's constant is *always decreasing with edges deletion*. Hence the claim that there may be a \"paradox\" that leads to reducing both over-squashing and oversmoothing at the same time should be quite toned down in my opinion.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer MxtA for the constructive feedback provided and valuable insights. We include answers for each of the points raised. \n\n* W1. We believe the idea of graph lottery tickets is an interesting application since we propose a graph sparsification method. Recent works [Pal, Hoang] suggest the importance of preserving the spectral properties (Ramanujan graph property) during finding lottery tickets and our proposed approach complements this line of work (L325 in our paper).\n\n* W2. We agree and would be happy to add a more nuanced discussion in a revision. Our position is that quantifying the phenomenon of over-squashing is an active area of research [DiGiovanni], and, while various metrics have been proposed, the spectral gap has an intuitive explanation in terms of random walks. It is also reasonable to think that any good over-squashing definition would exhibit a parallel Braess phenomenon in effect. Furthermore, our results on the Long Range Graph Benchmark [Dwivedi] (Table 1 of our paper and also Table 5 in the attachment where we have also added FoSR [Karhadkar] as a new baseline) suggest that our rewiring strategy are able to mitigate over-squashing. \n\n* Q1. We would like to thank the reviewer for bringing this interesting work to our attention. Our goal in the paper is to obtain a sparse representation of the graph by deleting edges that maximize the spectral gap in an efficient way. The methods mentioned in [Batson] point to finding sparse representations of graphs that preserve the spectral properties of the original graph, which we would be happy to mention in a revision.\n\n* Q2. For finding graph lottery tickets we use the algorithms provided by UGS [Chen] with a notable difference: we adopt a spectral gap based pruning for the input graph but use the original iterative magnitude pruning (IMP) for the network weights, while UGS uses iterative magnitude pruning for both the input graph and the network weights.\n\nReferences:\n* [Pal] Pal. et al. A study on the ramanujan graph property of winning lottery tickets. ICML 2022.\n* [Hoang] Hoang et al. Revisiting pruning at initialization through the lens of Ramanujan graph. ICLR 2023\n* [Batson] Batson et al. Spectral sparsification of graphs: theory and algorithms. Comms ACM. 2013.\n* [Chen] Chen et al. A Unified Lottery Ticket Hypothesis for Graph Neural Networks. ICML. 2021\n* [DiGiovanni] Di Giovanni et al. How does over-squashing affect the power of GNNs? TMLR 2024.\n* [Gutteridge] Gutteridge. et al . DRew: Dynamically rewired message passing with delay, ICML 2023.\n* [Dwivedi] Dwivedi. et al. Long range graph benchmark, NeurIPS 2022.\n* [Karhadkar] Karhadkar et al. FoSR: First-order spectral rewiring for addressing oversquashing in GNNs. ICLR 2023.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:
We sincerely thank all reviewers for their feedback. We appreciate the overall positive reception of our work and are glad that its novelty, clarity, and thoroughness have been recognized. Below, we summarize our key contributions and address the added material in the attached document:

* Our work challenges the common hypothesis that over-smoothing and over-squashing must be traded off against each other in graph rewiring. We demonstrate how the Braess paradox can be exploited to alleviate both problems simultaneously through strategic edge deletions.
* We follow the narrative of [6] that over-smoothing refers to unwanted neighborhood aggregation, which depends on features and node labels. This explains our method's effectiveness in heterophilic settings.
* Our theory for the ring graph provides an existence proof that over-smoothing and over-squashing can be optimized jointly and provides insights into the basic mechanism that explains the performance gains by our proposed rewiring methods. We have extended our analyses to real-world graphs (Cora, Citeseer, Chameleon, Texas, etc.) to demonstrate its practical applicability.
* We propose efficient algorithms for spectral gap optimization, which have been shown to be effective across various graph types and tasks.

To address specific requests and provide further clarity, we have included the following additional analyses in the attachment:

* T1: Table of spectral gap changes for ProxyDelete, FoSR, ProxyAdd and EldanDelete on all datasets
* T2, T3: Comparison with random edge deletion and DropEdge
* T4: Number of edges that satisfy the Eldan criterion
* T5, T6: Results for FoSR on Long Range Benchmark datasets, and BORF on commonly used datasets

We believe that our insights and our proposed practical algorithms are timely and of high interest to the community. In particular, our contribution exploits an overlooked piece in the puzzle of how to improve the performance of graph neural networks and/or their computational efficiency by graph rewiring.

Meta-review: The article proposes a graph pruning algorithm that maximises the spectral gap in a computationally efficient way to address oversquashing and oversmoothing in GNNs. It observes that, by deleting edges, one can increase the spectral gap, while reducing the oversmoothing rate. 

Reviewers find that the paper is clearly written and easy to follow, that the evaluation uses a diverse set of tasks, and the method appears to be efficient. They regarded it as a weakness that the theoretical analysis was based on a specific example and thus unclear how it would generalize, the experimental setups not always consistent, and connections to the lottery ticket hypothesis not sufficiently motivated. The rebuttal addressed several of the main concerns, prompting some to increase the score and others to maintain their positive score. 
At the end of the discussion period, all reviewers recommended weak accept. 

I conclude that the article provides a well presented and meaningful advance on a topic of interest and therefore recommend accept. The authors are asked to implement the promised revisions in the final version of the article.
Decision: Accept (poster)