Spectral Graph Pruning Against Over-Squashing and Over-Smoothing

Authors: adarsh  jamadandi
celia  rubio-madrigal
rebekka  burkholz
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-11 10:39:39

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.

Main paper: 
 introduction: 
 Graphs are ubiquitous data structures that can model data from diverse fields ranging from chemistry (Reiser et 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-passing 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 a 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., 2021a,b; Bevilacqua et al., 2022) , all tackling a variety of problems in various 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., 2019) , over-smoothing (Li et al., 2019; NT & Maehara, 2019; Oono & Suzuki, 2020; Zhou et al., 2021) , and over-squashing (Alon & Yahav, 2021; Topping et al., 2022) .The phenomenon of over-squashing, first studied heuristically by Alon & Yahav (2021) and later theoretically formalized by Topping et al. (2022) , is caused by the presence of structural bottlenecks in 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 is to oversquashing. Recent work has explored rewiring the input graph to address these bottlenecks (Topping et al., 2022; Arnaiz-Rodríguez 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 over-smoothing (Keriven, 2022) . Instead, we propose to leverage the Braess paradox (Braess, 1968; Eldan et al., 2017) that posits certain edge deletions can maximize the spectral gap. We propose to approximate the spectral change in a computationally efficient manner by leveraging Matrix Perturbation Theory (Stewart & Sun, 1990) . Our proposed framework allows us to jointly address the problem of over-squashing, by increasing the spectral gap, and over-smoothing, 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 on 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.1. Inspired by the Braess phenomenon, we prove that, contrary to common assumptions, oversmoothing 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. Similarly, our algorithm can also be utilized to add edges in a joint framework. We compare this approach with a novel graph rewiring scheme based on Eldan'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 generalization 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., 2021) that takes additional node features and labels into account. This highlights the feasibility of finding winning subgraphs at initialization. 
related work: 
 Over-squashing. Alon & Yahav (2021) ; Topping et al. (2022) 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 is graph rewiring. This task aims to modify the edge structure of the graph either by adding or deleting edges. Gasteiger et al. (2019) propose to add edges according to graph diffusion kernel, such as personalized PageRank, to rely less on messages from only one-hop neighbors, thus alleviating over-squashing. Topping 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, Deac et al. (2022) show that negatively curved edges might be inevitable for building scalable GNNs without bottlenecks and advocate the use of Expander graphs for message passing. Arnaiz-Rodríguez et al. (2022) introduces two new 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. Karhadkar 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 is 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 over-smoothing (Li et al., 2019; Oono & Suzuki, 2020; NT & Maehara, 2019; Zhou et al., 2021; Rusch et al., 2023a) , 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., 2023) , 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, we 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 a computationally efficient approach to achieve this with spectral rewiring. In contrast to our proposal, curvature based methods (Nguyen et al., 2023; Giraldo et al., 2023) do not scale well to large graphs. For instance, Nguyen et 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 neighborhood 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, either in terms of their node distribution (Eden et al., 2018) or graph spectrum (Adhikari et al., 2017) . Zheng et al. (2020) ; Li et al. (2020) 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 et al., 2021; Hui et al., 2023) , prunes the model weights in addition to the adjacency matrix. The resulting winning graph lottery ticket (GLT) can match or 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 et al., 2022; Burkholz, 2022b,a) , our insights inspired by the Braess paradox add a complementary lens to our understanding of how generalization can be improved, namely by reducing over-squashing 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., 2022; Hoang et al., 2023) . We highlight that the spectral gap can also be employed as a 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) .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 no 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 (e.g., independence assumptions, noiseless settings, model well-specification, 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 a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairness. • 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 acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
theoretical insights into spectral rewiring: 
 To prove our claim that over-smoothing and over-squashing can both be alleviated jointly, we provide a minimal example as illustrated in Figure 1 . Utilizing the Braess paradox, we 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 L G , where G = (V, E). The Laplacian of the graph is L = D -A, where A is the adjacency matrix and D the diagonal degree matrix. The symmetric normalized graph Laplacian is defined asL G = D -1/2 LD -1/2 . Let {λ 0 < λ 1 < λ 2 , ...λ n } be the eigenvalues of L G arranged in ascending order and let λ 1 (L G ) be the first non-zero eigenvalue of the normalized graph Laplacian, which is also called the spectral gap of the graph. For a 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 (1971) (λ 1 ≈ 0.2829) 0 1 6 7 2 3 4 5 P rune (λ1 ⇈) Add (λ1 ⇈) Add (λ1 ⇊) G - (λ 1 ≈ 0.2929) 0 1 6 7 2 3 4 5 G + (λ 1 ≈ 0.3545) 0 1 6 7 2 3 4 5 G + (λ 1 ≈ 0.2713) 0 1 6 7 2 3 4 5Figure 1 : Braess' paradox. We derive a simple example where deleting an edge from G to obtain G - yields a higher spectral gap. Alternatively, we add a 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 a counter-intuitive result for road networks: even if all travelers behave selfishly, the removal of a road can still improve each of their individual travel times. That is, there is a violation of monotonicity in the traffic flow with respect to the number of edges of a network. For instance, Chung & Young (2010) has shown that Braess' paradox occurs with high probability in Erdős-Rényi random graphs, and Chung et al. (2012) have confirmed it for a 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 et 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 a sufficient condition that guarantees a spectral gap increase in response to a 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 λ 1 (L G ) the eigenvalue corresponding to the spectral gap. Let {u, v} / ∈ V be two vertices that are not connected by an edge. Denote Ĝ = (V, Ê), the new graph obtained after adding an edge between {u, v}, i.e., Ê := E ∪ {u, v}. Denote with P f := ⟨f, f0 ⟩ the projection of f onto the top eigenvector of Ĝ. Define g (u, v, L G ) :=-P 2 f λ 1 (L G ) -2(1 -λ 1 (L G )) √ d u + 1 - √ d u √ d u + 1 f 2 u + √ d v + 1 - √ d v √ d v + 1 f 2 v + 2f u f v √ d u + 1 √ d v + 1 . If g (u, v, L G ) > 0, then λ 1 (L G ) > λ 1 (L Ĝ ).As a showcase example of the Braess phenomenon, let us analyze the behaviour of the spectral gap in terms of an edge perturbation on the ring graph of n nodes R n . We consider the ring R 8 as G -, the deletion of an edge from graph G in Figure 1 . Proposition 3.2. The spectral gap of G increases with the deletion of edge {0, 3}, i.e., λ 1 (L G -) > λ 1 (L G ). It also increases with the addition of edge {0, 5} or decreases with the addition of edge {4, 7}, i.e., λ1 (L G + ) > λ 1 (L G ) and λ 1 (L G + ) < λ 1 (L G ).We leverage Eldan's Lemma 3.1 in Appendix A.1 and apply the spectral graph proxies in our 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 a trade-off between over-smoothing and over-squashing. Methods by Giraldo et al. (2023) ; 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, we . 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 to 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 a linear ridge regression (LRR) setup with mean squared error (MSE) as the loss. We assign two classes to nodes according to their color in Figure 1 , and one-dimensional features that are drawn independently from normal distributions N (1, 1) and N (-1, 1), respectively. Figure 2 (a) compares how our exemplary graphs (see Figure 1 ) 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 over-squashing 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 PROXYDELETE, 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 D.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-smoothing. Instead of deleting an edge, we could also add an edge arriving at G + , which would lead to a higher spectral gap than the edge deletion. Yet, it adds an edge between nodes with different labels and therefore leads to over-smoothing. 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 + or 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 G + .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.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? • The experimental setting should be presented in the core of the paper to a 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. 
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 in Table 14 . The other approach based on Eldan's Lemma is also analyzed, as it provides theoretical guarantees for edge deletions. However, it does not scale well to larger graphs.Greedy approach to 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 a single edge iteratively. In every iteration, we rank candidate edges according to a proxy of the spectral gap change that would be induced by the considered rewiring operation, as described next.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 as a criterion to rank edges requires a formula to efficiently estimate it for one edge flip. For this we resort to Matrix Perturbation Theory (Stewart & Sun, 1990; von Luxburg, 2007) to capture the change in eigenvalues and eigenvectors approximately. Our update scheme is similar to the proposal by Bojchevski & Günnemann (2019) in the context of adversarial flips. The change in the eigenvalue and eigenvector for a single edge flip (u, v) is given byEQUATIONwhere λ is the initial eigenvalue; {f u , f v } are entries of the leading eigenvector, ∆w u,v = 1 if we add an edge and ∆w u,v = -1 if we delete an edge. Note that this proxy is only used to rank edges efficiently. After adding/deleting the top M edges (where M = 1 in our experiments), we update the eigenvector and the spectral gap by performing a 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 Lanczos Method (Lehoucq et al., 1998) , with our current estimate of the leading eigenvector.Both our resulting algorithms, PROXYDELETE for deleting edges and PROXYADD for adding edges, are detailed in Appendix C.O (N • (|E| + s(G)))where N is the number of edges to delete, and s(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(G) = O(|E|). 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 O(1) proxy measure to score candidate edges, we are able to improve the overall runtime complexity from the original O (N • |E| • s(G)). Furthermore, even though this does not impact the asymptotic complexity, deleting edges instead of adding them makes every iteration run on a 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 as the edge deletion algorithm. The key distinction is that the ranking is conducted on the complement of the graph'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.Lemma 3.1 states a sufficient condition for the Braess paradox. It naturally defines a 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 Figure 3 : We instantiate a 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 criterion based edge methods. algorithms, as each scoring operation needs access to the leading eigenvector of the perturbed graph with an added or deleted edge. In case of edge deletions, we also need to approximate the spectral gap similar to our Proxy algorithms. As the involved projection P f is a dot product of eigenvectors, it requires O(|V|) operations. Even though this algorithm does not scale well to 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 C.To check whether the proposed edge modification algorithms are indeed effective in the spectral gap expansion, we conduct experiments on an Erdös-Rényi (ER) graph with (|V|, |E|) = (30, 58) in Figure 3 . 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(|E|) computations. For our small synthetic test bed, we 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 3(a) ) and deletions (Figure 3(b) ), we observe that the Proxy method outlined in Algorithm 1 usually leads to a better spectral expansion approximation. In addition, we report the spectral gaps that different methods obtain on real world data in Table 16 in the Appendix, which highlights that our proposals are consistently most effective in increasing the spectral gap. 
long range graph benchmark: 
 The Long Range Graph Benchmark (LRGB) was introduced by Dwivedi et al. (2023) specifically to create a test bed for over-squashing. 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 1 . 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: 1) PascalVOC-SP -Semantic image segmentation as a node classification task operating on superpixel graphs. 2) Peptides-func -Peptides modeled as molecular graphs. The task is graph classification. 3) Peptides-struct -Peptides modeled as molecular graphs.The task is to predict various molecular properties, hence a graph regression task.The top performance is highlighted in bold. Evidently, our proposed rewiring methods outperform DRew (Gutteridge et al., 2023) and FoSR (Karhadkar et al., 2023) on PascalVOC and Peptides-struct, 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.2) for adding edges, since FoSR (Karhadkar et al., 2023) was primarily tested on this task.Node classification on large heterophilic datasets. Platonov et al. (2023) point out that most progress on heterophilic datasets is 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, we also test our proposed algorithms on 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 Platonov et al. (2023) ; the datasets are divided into 50/25/25 split for train/test/validation respectively. The test accuracy is reported as an 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 PROXYDELETE in Tables 2,3,4. The top performance is highlighted in bold. Evidently, for increasing depth, even though the GNN performance should degrade because of over-smoothing, we achieve a significant boost in accuracy compared to baselines, which we attribute to the fact that our methods delete inter-class edges -thus slowing down detrimental smoothing. Pruning for graph lottery tickets. In Sections §3 and §5, 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) ?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., 2021) , prunes connections in the adjacency matrix and model weights that are deemed less important for a prediction task. Note that UGS relies on information that is obtained in 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 a pitfall we would want to avoid (Hui et al., 2023) , yet resorting to expensive train-prune-rewind 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 et 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 et 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 a 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 a 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 an iterative manner. Our results are presented in Table 18 , where we compare IMP based UGS (Chen et al., 2021) with our methods for different graph and weight sparsity levels. Note that, even though our method does not take any feature information into account and prunes purely based on the graph structure, our results are comparable. For datasets like Pubmed, we even slightly outperform the baseline. Table 5 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) .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 a 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 a graph exploiting the Braess paradox. By providing a minimal example, we prove that this way it is possible to address oversquashing 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 a computationally efficient graph rewiring framework, which also induces a competitive approach to prune graphs for lottery tickets at initialization. 
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, confidence 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. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 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 error rates). 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 a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader Impacts Question: Does the paper discuss both potential positive societal 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.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: No such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 a best faith effort.12. Licenses for existing assets Question: 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?Answer: [Yes] Justification: All codes and datasets used are properly attributed.Guidelines:• The answer NA means that the paper does not use 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 a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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. 
 
 Appendix: A.1 Proof of Proposition 3.2 Spectral analysis for general n.For all n, the (normalized) Laplacian matrix of R n is 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 L(R n ) is r n = 1, -1 2 , 0, . . . , 0, -1 2 . All circulant matrices satisfy that their eigenvectors are made up of powers of the nth-roots 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λ 1 = n-1 k=0 r n (k) • e -i2π k n = 1 - 1 2 e -i2π 1 n + e -i2π -1 n = 1 -cos 2π n .As stated before, one possible set of eigenvectors isω j (k) = exp i 2πjk n .Because their conjugates and their linear combinations are also eigenvectors, we can get real eigenvectors asx j (k) = ωj (k)-ω-j (k) 2i= sin 2πjk n . Alternatively, we can get y j (k) = ωj (k)+ω-j (k) 2= cos 2πjk n . We only need to focus on the (pair of) eigenvectors for j = 1. Note that they are orthogonal to each other. Because they are both eigenvectors with the same eigenvalue λ 1 , all linear combinations of them will also be eigenvectors with eigenvalue λ 1 . This multiplicity lets us choose any of these vectors to fulfill Eldan's criterion. A limitation of our algorithm is that, in cases of multiplicity, we can only choose one of them, potentially giving that edge a disadvantage -the Lemma holds as long as there exists one that fulfills it, but not necessarily the one we have chosen.The norms of x 1 and y 1 are n 2 . Therefore, the norm of any linear combination of them is ∥µx 1 + νy 1 ∥ = n 2 µ 2 + ν 2 . We denote the normalized linear combination of x 1 and y 1 asf (µ,ν) 1 = √ 2(µx 1 + νy 1 ) n(µ 2 + ν 2 )Our choice will be µ = 3, ν = 1, i.e., f(3,1) 1 = (3x1+y1) √ 5n . Elements of the criterion for general n. As per Eldan et al. (2017) , the first eigenvector of the new graph's normalized Laplacian is f0 = D 1 2 1/ di . In our case:f0 (k) = √ 3 √ 2(n+1) if k ∈ {u, v},and√ 2 √ 2(n+1)if k / ∈ {u, v}. With it we calculate the projection, dependent on the eigenvector f 1 :P f1 = n-1 k=0 f 1 (k) f0 (k) = n-1 k=0, k̸ =u,v √ 2 2(n + 1) f 1 (k) + √ 3 2(n + 1) (f 1 (u) + f 1 (v)) = √ 3 - √ 2 2(n + 1) (f 1 (u) + f 1 (v)) .We also have, for all n, u and v, that√ du+1- √ du √ du+1 = √ dv+1- √ dv √ dv+1 = √ 3- √ 2 √ 3 = 1 -2 3 .We can update the criterion with these considerations:g(u, v, R n ) = = -P 2 f1 λ 1 -2(1 -λ 1 ) √ d u + 1 - √ d u √ d u + 1 f 1 (u) 2 + √ d v + 1 - √ d v √ d v + 1 f 1 (v) 2 + 2f 1 (u)f 1 (v) √ d u + 1 √ d v + 1 = - √ 3 - √ 2 2(n + 1) 2 1 -cos 2π n (f 1 (u) + f 1 (v)) 2 -2 cos 2π n 1 - 2 3 f 1 (u) 2 + f 1 (v) 2 + 2f 1 (u)f 1 (v) 3 . Case n = 8, (u, v) = 3}. We choose f 1 := f (3,1) 1 = (3x1+y1) √ 40 . We have f 1 (0) = 1 2 √ 10 and f 1 (3) = 1 2 √ 5 . Then: (f 1 (u) + f 1 (v)) 2 = 1 2 √ 10 + 1 2 √ 5 2 = 3 + 2 √ 2 40 f 1 (u) 2 + f 1 (v) 2 = 1 2 √ 10 2 + 1 2 √ 5 2 = 3 40 f 1 (u)f 1 (v) = 1 2 √ 10 1 2 √ 5 = √ 2 40Finally, Eldan's criterion for n = 8, (u, v) = {0, 3}, and our choice off 1 is g(0, 3, R 8 ) = = - √ 3 - √ 2 √ 18 2 1 -cos π 4 (f 1 (u) + f 1 (v)) 2 -2 cos π 4 1 - 2 3 f 1 (u) 2 + f 1 (v) 2 + 2f 1 (u)f 1 (v) 3 = - √ 3 - √ 2 √ 18 2 1 - √ 2 2 3 + 2 √ 2 40 - √ 2 1 - 2 3 3 40 + 2 3 √ 2 40 ≈ -0.0002395 -0.0194635 + 0.0235702 ≈ 0.0038672 > 0.In Table 6 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 ∆PROXYADD -estimating the spectral gap's difference when that edge is added. Meanwhile, ∆PROXYDELETE is calculated from the denser graph and tries to estimate the spectral gap of the pruned one.When g(u, v, •) > 0, it theoretically guarantees that ∆λ 1 < 0, 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: ∆PROXYADD is negative because the edge should not be added, and ∆PROXYDELETE is positive because the edge should be pruned.Note that, because of the aforementioned multiplicity of the ring's eigenvectors, if we choose another f 1 for the first row, Eldan's criterion might not be satisfied. For example, using the eigenvectors given by the library function np.linalg.eigh, the criterion yields a 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 are again accurately descriptive of reality: ∆PROXYADD is positive and ∆PROXYDELETE is negative. A.2 Proof of Propositions 3.3 and 3.4We choose one-dimensional features to follow normal distributions dependent on their class: X i ∼ N (1, 1) for class (+), and X i ∼ N (-1, 1) for class (-). After one round of mean aggregation, class (+) nodes with two intra-class neighbors will still have an 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 X 2 , which have one neighbor of each class, will have a lower expected value:The smaller its expected mean is, the more it deviates from the original mean, and the less informative it gets. In Table 7 we show the expected values of each configuration dependent on the neighbors' classes as they appear on 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 one round of mean aggregation. 7 . We arbitrarily choose orange nodes to be the negative class. After one round of mean aggregation on each of 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 we intended to prove, they tend towards non-informative zero for both classes as the number of edges increases, and they follow the same order as the smoothing rate curves plotted in Figure 2 (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 G + and G + . Proposition 3.4 is proved because the values from G + are more informative/further apart than the values from G + .A + + + 1+1+1 3 = 1 B + + - 1+1-1 3 = 1 3 C + + - + 1+1+1-1 4 = 1 2 D - - + + 1+1-1-1 4 = 0 E - - + + + 1+1+1-1-1 5 = 1 5 B A A B -B -A -A -B (a) G -neighboring conf. B A C B -B -C -A -B (b) G neighboring conf. B A E B -B -C -A -D (c) G + neighboring conf. B C C B -B -C -C -B (d) G + neighboring conf.In Figure 5 we show how different configuration of labels for our example graphs affect their smoothing rate tests. In particular, we 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 a first modification (Figure 5(c )), we rotate the labels so that edge {0, 3} is now intra-class; this makes edge {4, 7} from G + intra-class, too. It is reflected in its smoothing rate plot in two main ways. First, the distance between graph G -and G 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 has the smallest spectral gap, so the configuration of labels and the graph structure work towards the same goal.Table 8 : Neighboring configurations for each graph, and their average value after a round of mean aggregation.G - G G + G + X 6 B: 1 3 B: 1 3 B: 1 3 B: 1 3 X 7 A: 1 A: 1 A: 1 C: 1 2 X 0 A: 1 C: 1 2 E: 1 5 C: 1 2 X 1 B: 1 3 B: 1 3 B: 1 3 B: 1 3 Average: 2+ 2 3 4 ≈ 0.667 1+ 2 3 + 1 2 4=≈ 0.542 As a second modification (Figure 5 (e)), 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, now on par with the base graph. We consider this phenomenon to be directly related to its lower spectral gap. Another relevant aspect of this graph is 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 is another instance of both mitigating over-smoothing and over-squashing.1+ 2 3 + 1 5 4 =≈ 0.467 2 3 + 2 2 4 =≈ 0.417 X 2 -B: -1 3 -B: -1 3 -B: -1 3 -B: -1 3 X 3 -A: -1 -C: -1 2 -C: -1 2 -C: -1 2 X 4 -A: -1 -A: -1 -A: -1 -C: -1 2 X 5 -B: -1 3 -B: -1 3 -D: 0 -B: -1 3 Average: - 2+ 2 3 4 ≈ -0.667 - 1+ 2 3 + 1 2 4 ≈ -0.542 - 1+ 1 3 + 1 2 4 ≈ -0.458 -Lastly (Figure 5 (g)), we propose a configuration that is actively counterproductive to the structure of the 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 a worse structure for the right kind of information to flow, and worse to avoid getting dissipated in this particular case. This unveils the ultimate limitation of not taking into account the task in a rewiring method, which is a trade-off to assume.Require:Graph G = (V, E), num. edges to prune N , spectral gap λ 1 (L G ), top eigenvector f of G. repeat for edges(u, v) ∈ E do Consider Ĝ = G \ (u, v).{Note that the denser graph is the original G, so we require approximations of f and λ 1 (L Ĝ ) from the sparser Ĝ.} Estimate eigenvector f from f based on the power iteration method. Estimate corresponding eigenvalue λ 1 (L Ĝ ) based on Eq. ( 1). Compute projectionP 2 f = ⟨ f , f 0 ⟩. Compute Eldan's criterion g(u, v, L Ĝ ).end for Find the edge that maximizes the criterion:(u -, v -) = argmax (u,v)∈E g(u, v, L Ĝ ) Ê = Ê \ (u -, v -). Update degrees d u -= d u --1, d v -= d v --1Update eigenvectors and eigenvalues of G accordingly. until N edges deleted. Output : Sparse graph Ĝ = (V, Ê).In section §3 we have demonstrated the possibility of addressing both over-squashing and oversmoothing 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 we delete edges using our PROXYDELETE method, the rate of smoothing is slowed down. It is also evident that our pruning method is more effective in heterophilous graph settings. This is likely due to 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 9 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 is 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 7 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, it cannot improve the Dirichlet energy like specialised methods (Zhou et al., 2021; Roth & Liebig, 2023; Rusch et al., 2023b) .In a recent work by Azabou et 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 a similar effect just by pruning edges instead of introducing additional nodes.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 on Chameleon, 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. Squirrel, Actor and the WebKB datasets consisting of Cornell, Wisconsin and Texas. Our baselines include GCN (Kipf & Welling, 2017) without any modifications to the original graph, DIGL by Gasteiger et al. (2019) , SDRF by Topping et al. (2022) , and FoSR by Karhadkar et al. (2023) . We adopt the public implementations available and tune the hyperparameters to improve the performance if possible. Our results are presented in Table 10 . We compare GCN with no edge modifications, GCN+DIGL, GCN+SDRF, GCN+FoSR, GCN+RandomDelete, GCN+ELDANDELETE where we delete the edges, GCN+ELDANADD where we add the edges according to 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 et 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 on Cora, Citeseer and Pubmed, which are homophilic. Yet, GCN+PROXYADD is more effective in increasing the spectral gap (see Table 16 ). 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.We conduct experiments on graph classification with a GCN (Kipf & Welling, 2017) and R-GCN (Battaglia et al., 2018) backbone to demonstrate the effectiveness of our proposed rewiring algorithms. Our experimental setting is the same as 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 our results with FoSR by Karhadkar et al. (2023) . For the IMDB-BINARY, REDDIT-BINARY and COLLAB datasets there are no node features available and have to be created. For fair comparison we run FoSR on these datasets. For ENZYMES 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 our proposed algorithms are effective in increasing the generalization performance even for graph classification tasks. In Table 13 we compare FoSR (Karhadkar et al., 2023) and our proposed methods that use Eldan's criterion for adding edges and the PROXYADD method with a Relational-GCN backbone on 9 datasets.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. 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 to 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 of 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 = 1 leads to better spectral gap improvement, M = 10 is also a valid updating period which induces enough spectral gap change while simultaneously bringing down the runtime (also presented in Table 14 ) 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 PROXYDELETE with different M updates on Cora and Texas datasets to modify 50 and 20 edges respectively. This is shown in Figure 8 . Although a 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 et 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) . In Table 18 , we present the results for Pruning at 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 et 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 ELDANDELETE-UGS and PROXYDELETE attain comparable performance to UGS. On Pubmed for different graph sparsity levels we outperform UGS. Meanwhile, our method fails to identify winning 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 3 runs. Except for Pubmed which could only be averaged over 2 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.We instantiate a 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 et al. (2023) . We use a 60/20/20 split for training/testing/validation respectively for all datasets. We perform extensive hyperparameter tuning on the validation set and finally report test accuracy averaged over 10 splits of the data (Chen et 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 a 4-layered GCN and R-GCN versions. For the larger heterophilic datasets, we use the experimental setup given by the authors (Platonov et al., 2023) . We set the learning rate to {3e -3, 3e -4}, dropout to 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 as averaged over 10 random splits run for 1000 steps. Skip connections and normalization (Ba et al., 2016) 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 in 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 as long as it is clear that these goals are not attained by the paper.. In general, if a (class (+)) node has p same-class neighbors and q different-class neighbors, their representation after an aggregation round will follow a normal distribution N ( 1+p-q 1+p+q , 1 1+p+q ). 


Decision: 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.

Reviews: review: paper_summary: paper_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
strength_weakness: strength_weakness: 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. 

2. 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:
    - The inspiration is drawn based on the contrived example.
    - 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.
    - Spectral gap expansion is then shown in Erdos-Renyi graphs in Section 4.3.

These 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.

3. 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?

4. 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.


References

1. Oono and Suzuki. Graph neural networks exponentially lose expressive power for node classification.

2. Wu etl al. Demystifying Oversmoothing in Attention-Based Graph Neural Networks.
questions: 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
via the spectral gap increase." Could you clarify?

2. 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.

3. Any justification why for spectral expansion, the proxy method does better than Eldan criterion in Section 4.3?

4. How would the method compare to random edge-dropping baselines such as DropEdge [1] in the literature?

5. 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.

References

[1] Rong et al. DropEdge: Towards Deep Graph Convolutional Networks on Node Classification.
limitations: limitations: n/a
paper_summary: paper_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.
strength_weakness: strength_weakness: 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?

2.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?

3.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"?

4.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].

5.Some typos, ‘basline’ in L187, etc.

 
[1] Khang Nguyen, et al. “Revisiting Over-smoothing and Over-squashing Using Ollivier-Ricci Curvature” ICML 2023.
questions: questions: See weaknesses.
limitations: limitations: The authors have addressed the limitations and potential societal impact.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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. 

The condition in lemma 3.1 is a bit too specific Can you give some intuition as to what we should interpret from it?
questions: 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: limitations: none exist
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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")

- 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.
questions: 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.

- for graph lottery, are the "-UGS" versions of the algorithm differents ? It is never clearly explained.
limitations: limitations: See above

Comments: title: Thank you
comment: I thank the authors for their answers, which address most of my questions. I still find the lottery tickets to be a bit tangential and the ``paradox'' to be a bit ``on-the-nose'' for something as studied as spectral gap maximization, but admit that this is an interesting work that draws interesting connections with GNN literature. I will keep my score as is, but tentatively recommend acceptance.
I would like to thank the authors for their detailed response. The rebuttal has addressed my major concerns. One minor thing is that I still think the ring example given is quite specific and the intuition there might not generalize to real graphs. Despite this weakness on theoretical side, the authors have shown the effectiveness of the idea in practice. I will increase my score to 5.
Thank you for the rebuttal. As my original scoring is optimistic, I retain my scoring for this paper.
We thank the reviewer for their timely and highly constructive response. We highly appreciate the interesting discussion.

Just to avoid a potential misunderstanding, we would like to highlight that only our propositions are limited to the ring example. In addition, we have provided numerical evidence on real world graphs (e.g. Figure 2) and ER graphs in Figure 3. Our algorithms and insights apply to any real world graph.

Re Q1: We agree that the full spectral approach could lead to better learning. To understand the intricacies, we would probably also have to consider the full learning dynamics.
Re W1, W2, ok, fair enough if the purpose is to give a small example to break a common misconception. It does limit the broader applicability a bit, and maybe some efforts should be made there, e.g. find some random graph examples where this is true numerically. 

Re Q1: I think this strikes the heart of the difference between optimizing and learning. I agree the optimization convergence rate depends most dominantly on one eigenvalue, but if that is the focus of training, it could lead to some weird biases in the resulting model; it seems a fuller spectral approach could lead to better learning.  However, how one approaches this is probably still an open question, and I admittedly have no idea how to actually do anything like that. 

Overall, I am happy with the responses and will keep my score.