FoSR: First-order spectral rewiring for addressing oversquashing in GNNs
Authors: Kedar Karhadkar
Pradeep Kr. Banerjee
Guido Montufar
Venue: ICLR 2023 poster (2023)
Keywords: oversquashing
oversmoothing
graph rewiring
graph neural networks
GNN
relational GNN
spectral expansion

Abstract: Graph neural networks (GNNs) are able to leverage the structure of graph data by passing messages along the edges of the graph. While this allows GNNs to learn features depending on the graph structure, for certain graph topologies it leads to inefficient information propagation and a problem known as oversquashing. This has recently been linked with the curvature and spectral gap of the graph. On the other hand, adding edges to the message-passing graph can lead to increasingly similar node representations and a problem known as oversmoothing. We propose a computationally efficient algorithm that prevents oversquashing by systematically adding edges to the graph based on spectral expansion. We combine this with a relational architecture, which lets the GNN preserve the original graph structure and provably prevents oversmoothing. We find experimentally that our algorithm outperforms existing graph rewiring methods in several graph classification tasks.

Published as a conference paper at ICLR 2023
FOSR: FIRST-ORDER SPECTRAL REWIRING FOR ADDRESSING OVERSQUASHING IN GNNS
Kedar Karhadkar
Pradeep Kr. Banerjee
Guido Montúfar UCLA & MPI MiS
UCLA kedar@math. wamaath.ccll... edu
MPI MiS
pradeepêmis. mpg. de
contufar@matioe uucl ucla. edu
ABSTRACT
Graph neural networks (GNNs) are able to leverage the structure of graph data by passing messages along the edges of the graph. While this allows GNNs to learn features depending on the graph structure, for certain graph topologies it leads to inefficient information propagation and problem known as oversquashing. This has recently been linked with the curvature and spectral gap of the graph. On the other hand, adding edges to the message- paasggggaaiinggggggg graph can lead to increasingly similar node representations and a problem known oversmoothing. We propose a computationally efficient algorithm that prevents oversquashing by systematically adding edges the graph based on spectral expansion. We combine this with relational architecture, which lets the GNN preserve the original graph structure and provably prevents oversmoothing. We find experimentally that our algorithm outperforms existing graph rewiring methods in several graph classification tasks.
INTRODUCTION
Graph neural networks (GNNs) (Gori et al., 2005; Scarselli al., 2008) a broad class of models which process graph-structured data by passing messages between nodes of the graph. Due to the versatility of graphs, GNNs have been applied variety of domains, such as chemistry, social networks, knowledge graphs, and recommendation systems (Zhou et al., 2020; Wu et al., 2020). GNNs broadly follow message- paaugiin framework, meaning that each layer of the GNN aggregates the representations of a node and its neighbors, and transforms these features into new representation for that node. The aggregation function used by the GNN layer is taken to be locally permutation- invariant, since the ordering of the neighbors of node is arbitrary, and its specific form is a key component of the GNN architecture; varying it gives rise to several common GNN variants (Kipf and Welling, 2017; Veličković et al., 2018; Li et al., 2015; Hamilton et al., 2017; Xu et al., 2019). The output of a GNN can be used for tasks such as graph classification or node classification.
Although GNNs are successful in computing dependencies between nodes of graph, they have been found to suffer from a limited capacity to capture long-range interactions. For fixed graph, this is caused by variety of problems depending the number of layers in the GNN. Since graph convolutions are local operations, a GNN with small number of layers can only provide a node with information from nodes close to itself. For GNN with layers, the receptive field of node (the set of nodes it receives messages from) is exactly the ball of radius about the node. For small values of I, this results in "underreaching" and directly limits which functions the GNN can represent. On a related note, the functions representable by GNNs with I layers are limited to those computable by I steps of the Weisfeiler-Lehmaal (WL) graph isomorphism test (Morris et al., 2019; Xu al., 2019; Barceló et al., 2020). On the other hand, increasing the number of layers leads to its own set of problems. In contrast to other architectures that benefit from the expressivity of deeper networks, GNNs experience decrease in accuracy the number of layers increases (Li et al., 2018; Chen et al., 2020). This phenomenon has partly been attributed to "oversmoothing" where repeated graph convolutions eventually render node features indistinguishable (Li et al., 2018; Oono and Suzuki, 2020; Cai and Wang, 2020; Zhao and Akoglu, 2020; Rong et al., 2020; Di Giovanni et al., 2022).
Separate from oversmoothing is the problem of "oversquashing" first pointed out by Alon and Yahav (2021). As the number of layers of a GNN increases, information from (potentially) exponentially- growing receptive fields need be concurrently propagated at each message-passing step. This leads

---

Published as a conference paper at ICLR 2023
to bottleneck that causes oversquashing, when an exponential amount of information is squashed into fixed-size node vectors (Alon and Yahav, 2021). Consequently, for prediction tasks relying on mange interactions, the GNN can fail. Oversquashing usually occurs when there are enough layers the GNN to reach any node (the receptive fields are large enough), but few enough that the GNN cannot process all of the necessary relations between nodes. Hence, for fixed graph, the problems of underreaching, oversquashing, and oversmoothing occur in three different regimes, depending on the number of layers of the GNN.
A common approach to addressing oversquashing to rewire the input graph. making changes to its edges so that it has fewer structural bottlenecks. A simple approach to rewiring to make the last layer of the GNN fully adjacent, allowing all nodes to interact with one another (Alon and Yahav, 2021). Alternatively, one make changes edges of the input graph, feeding the modified graph into all layers of the GNN (Topping al., 2022: Banerjee et al., 2022). The latter approaches can viewed optimizing the spectral gap of the input graph for alleviating structural bottlenecks and improving the overall quality of signal propagation across nodes (see Figure 1).
FoSR
SDRF
Input graph
G-RLEF
0.75
accurtty (S))
Speztral gno
80
0.50
G-RLET
0.25
k0-
SDRF
FOSR
0.00
20
160
150
Iterations
While these rewiring methods improve the connec- tivity of the graph, there are drawbacks to making too many modifications the input. The most obvi- ous problem is that we are losing out on topological information about the original graph. If the structure of the original graph is indeed relevant, adding and removing edges diminishes that benefit to the task. Another issue arises from the smoothing effects of adding edges: If we add too many edges to the in- put graph, an ordinary GCN will suffer from over- smoothing (Li et al., 2018). 8). In other words, if we use this natural approach rewiring, we experience trade-off' between oversquashing and oversmoothing, This observation, which does not seem have been pointed out in earlier works, is the main motivation for the approach that we develop in this work.
Figure Top: Schematic showing different rewiring methods, FoSR (ours), SDRF (Top- ping et al., 2022), and G-RLEF (Banerjee et al., 2022) for alleviating structural bottlenecks in the input graph. Our method adds new edges that are labeled differently from the existing ones so that the GNN can distinguish them in training. Bottom: Normalized spectral gap and training accuracy as functions of the num- ber of rewiring iterations for learning task modeled on the NEIGHBORS problem for a path-of-cliques input (for details, see Ap- pendix 1.1.1).
1.1 MAIN CONTRIBUTIONS
This paper presents a new framework for rewiring a graph to reduce oversquashing in GNNs while preventing oversmoothing. Here are our main contributions:
We introduce a framework for graph rewiring which can be used with any rewiring method that sequentially adds edges. contrast to previous approaches that only modify the input graph (e.g.. Topping et al., 2022; Banerjee et al., 2022: Bober et al.. 2022), our solution gives special labels to the added edges. We then use a relational GNN on this new graph, with the relations corresponding to whether the edge was originally in the input graph or added during the rewiring. This allows us to preserve the input graph topology while using the new edges to improve its connectivity. In Theorem 3 we show that this approach also prevents oversmoothing.
We introduce spectral gap of the graph input to the GNN (Algorithm 1). This algorithm computes the first-order change in the spectral gap from adding each edge, and then adds the edge which maximizes this (Theorem 4 and Proposition 5).
rewiring method, FoSR (First-order Spectral Rewiring) aimed at optimizing the
We empirically demonstrate that the proposed method results in faster spectral expansion (a marker of reduced oversquashing) and improved test accuracy against several baselines several graph
2

---

Published as a conference paper at ICLR 2023
classification tasks (see Table 1). Experiments demonstrate that the relational structure preserving the original input graph significantly boosts test accuracy.
1.2
RELATED WORKS
Past approaches to reducing oversquashing have hinged upon choosing a measure of oversquashing. and modifying the edges of the graph to minimize it. Topping et al. (2022) argue that negatively curved edges are responsible for oversquashing drawing on curvature notions from Forman (2003) and Ollivier (2009). They introduce rewiring method known stochastic discrete Ricci Flow (SDRF), which aims to increase the balanced Forman curvature of negatively curved edges by adding new edges. Bober al. (2022) extend this line of investigation by considering the same type of rewiring but using different notions of discrete curvature. Banerjee et al. (2022) approach oversquashing from an tehoomation-thcoeretic viewpoint, measuring in terms of the spectral gap of the graph and demonstrate empirically that this can increase accuracy for certain graph classification tasks. They propose rewiring algorithm greedy random local edge flip (G-RLEF) motivated by an expander graph construction employing an effective resistance (Lyons and Peres, 2017) based edge sampling strategy. The work of Alon and Yahav (2021) first pointing at oversquashing also introduced an approach to rewiring, where they made the last GNN layer an expander the complete graph that allows every pair of nodes to connect to each other. They also experimented with making the last layer partially adjacent (randomly including any potential edge). This can be thought of form of spectral expansion in the final layer since random graphs have high spectral gap (Friedman, 1991). In contrast these works, our method gives practical way of achieving the largest possible increase in the spectral graph with the smallest possible modification of the input graph and in fact preserving the input graph topology via relational structure.
Although not as closely related, we find it worthwhile also pointing at following works in this general context. Prior the diagnosis of the oversquashing problem, Klicpera al. (2019) used graph diffusion to rewire the input graph, improving long-range connectivity for the GNN. Rewiring can also be performed while training a GNN, Amaiz-Roddiguee et al. (2022) use first-order spectral methods to define a loss function depending on the adjacency matrix, allowing a GNN to learn a rewiring that alleviates oversquashing We should mention that aside from rewiring the input graph, some works pursue different approaches to solve oversquashing, such as creating positional embeddings for the nodes or edges inspired by the transformer architecture (Vaswani et al., 2017). The most direct generalization of this approach to graphs is using Laplacian embeddings (Kreuzer et al., 2021; Dwivedi and Bresson, 2020). -abrielGabrielsson et al. (2022) combine this with adding neighbors to encode the edges which are the result of multiple hops.
2 PRELIMINARIES
2.1 BACKGROUND ON SPECTRAL GRAPH THEORY
Let G RV) be an undirected graph with node set V, |V| = n. edge set E, |8] m, and relation set R. The set R. is finite set of relation types, and elements (u, v,r) E & consist of a pair of nodes u, u E V together with an associated relation type r E R. When the relation type of an edge is not relevant, we will simply write (u, e) for an edge. For each E V we define N(v) to consist of all neighbors of v, that is all u E V such that there exists an edge (u, v) E E. For each r E R and E V. we define Mr (v) to consist of all neighbors of of relation type r. The degree d, of node V E V is the number of neighbors of e. We define the adjacency matrix A = A()) by Aij = 1 if (i,j) E, and A. = 0 otherwise. Let D D(G) denote the diagonal matrix of degrees given by D# d,. The normalized Laplacian L = L()) is defined as L
D- 1/2 AD-1/2, We will often add self-loops (edges (i, i) for E V) to the graphs we consider, so we define augmented versions of the above matrices corresponding to graphs with self self-loops added. If G is graph without self-loops, we define its augmented adjacency matrix À == I + A, its augmented degree matrix D = I D. and its augmented Laplacian L = D 1/2 AD
We denote the eigenvalues of the normalized Laplacian L by 0 = A S A2 S ... < An < 2.
Let 1 denote the constant function which assumes the value on each node. Then 1 is an eigenfunction of I with eigenvalue O. The spectral gap of G is Xa A1 A2 We say that g has
3

---

Published as a conference paper at ICLR 2023
good spectral expansion if it has large spectral gap. In Appendix A, review the relation between the spectral gap and a related measure graph expansion, the Cheeger constant.
2.2 BACKGROUND ON RELATIONAL GNNS
The framework propose fundamentally relies on relational GNNs (R-GNNs) (Battaglia al., 201 8), so we review their formulation here. We define general R-GNN layer by
h Φu (1/50) EPER EnEN,,0) U2 (K) ,110 .110
where the Verr R Rd - R 1 message-passiing functions, and the Φx R + R are update functions. The Φg and lhk.r can either be fixed mappings or learned during training. All GNN layer types consider will be special cases of this general R-GNN layer. We recover classical (non-relational) GNN when there is only one relation, (R] =
As special case of R-GNNs, R-GCN layers are defined by the update
hg (k+1) o (W (() + ETER EvEN.(U)
1 W
where is nonlinear activation, Cu.u is normalization factor, and W(A), W relation- specific learned linear maps, One can interpret the Whe term as adding self-loops to the original graph, and encoding these self-loops as their own relation. We often take ReLU, and Ca. v(1+ + d.)(1 + d.).
Other specializations of R-GNNs include graph convolutional networks (GCNs) (Kipf and Welling, 2017), defined by
hgg (k+1) =o(( ==EEEN(())UL) _ _ (k)
C...
and graph isomorphism networks (GINs) (Xu et al., 2019), defined by
h
(k+1) MLP (EnENtoJEO)) (1
3 RELATIONAL REWIRING OF GNNS
We introduce a graph rewiring framework to improve connectivity while retaining the original graph via a relational structure, which demonstrably allows us also control the rate of smoothing. The rate of smoothing measures the similarity of neighboring node features in the GNN output graph. Adding separate weights for the rewired edges allows the network more flexibility in learning an appropriate rate of smoothing. Our main result in this section, Theorem 3 makes this precise.
3.1 RELATIONAL REWIRING
We incorporate relations into our architecture in the following way. Suppose that we rewire & (V,&1 E1) by adding edges, yielding a rewired graph G (V, & U&). We equip G' with relational structure by assigning each edge in & the edge type 1, and each edge in &g the edge type 2. For example, in an R-GCN, this relational structure would result in the following layer form:
A (1+1) = (() -(G,
_ Lw((1))) l1 + E((,,)E 1
(k) (k)
The original layer (before relational rewiring) would include only the first two terms. A rewired graph with relational structure would add the third term but the weights w-(4) ((())
relational structure serves to provide the GNN with more flexibility, since it remembers both the original structure of the graph and the rewired structure. In the worst case scenario, if we add too many edges, the GNN may counterbalance this by setting most of the weights wr( to be focusing its attention the original graph. In more realistic scenario, the GNN can the original edge
weights (*) to compute important structural features of the graph, and the weights w simply to transmit information along the graph. Since the weights assigned to the original and rewired edges are separate, their purposes can be served in parallel without sacrificing the topology of the graph. Finally, this R-GCN model allows us better regulate the rate of smoothing we demonstrate next.
4

---

Published as a conference paper at ICLR 2023
3.2 RATE OF SMOOTHING FOR R-GCN WITH REWIRING
In this section, we analyze the smoothing effects of repeatedly applying R-GCN layers with rewiring. Here, we consider R-GCN layers yp Rexp RRx of the form
x(x) xX ETER D 1-1
where θ, 0 E RPXP are weight matrices, A, is the adjacency matrix of the r-th relation, and D is the matrix degrees of G. For a vanilla GCN without relations or residual connections, one problem with rewiring the graph that adding too many edges will result in oversmoothing (Di Giovanni et al., 2022). Indeed, adding edges to a graph will by definition increase its Cheeger constant. For input graphs with high spectral gap (and hence high Cheeger constant). a GCN will produce similar representations for each node (Xu et al., 2018; Oono and Suzuki, 2020). As an extreme case, if we replace the graph with a complete graph, the GCN layer will assign each node the same representation. We will show that R- R-GCNs are robust to this effect, allowing us to add edges without the adverse side effect of oversmoothing.
Definition 1. Let G be connected graph with adjaceney matrix A and normalized Laplacian L. For i E V, let d, denote the degree of node Given a scalar field f E IR", its Dirichlet energy with respect is defined as
2
= And
Li Vd.
- Vdz
= F
For vector field X E R we define
(()) = 1.2 2 Engi Aij
Xit Vdl
X, vdz
LX).
The Dirichlet energy of unit-norm function on the nodes of graph is measure of how "non- smooth" it (Chung and Graham, 1997). The Dirichlet energy a function f small when fi/ Vdz close in value to f / dd for all edges (i.j). In the case where & is d-regular (all nodes have degree d), this reduces to the familiar notion of adjacent nodes having representations close in value. Hence, we make the following definition:
Definition Let & be graph and yp R=*x- Raxp be mapping. We define the rate of smoothing of yp with respect to G as
((p(X))/8()) 1/2
/SUPX ( 1 (x)(
RSc(p)) =1
The numerator of the fraction above indicates the rate of decay (or expansion) of the Dirichlet energy upon applying sp. We take supremum over X to find the largest possible relative change in energy upon applying sp. We would also like our notion of the rate smoothing to be scale-invariant; multiplying oo by scalar should not change its rate of smoothing. To impose scale-invariance, divide by a factor in the denominator which captures how much &p scales up the entries X. By defining the the rate of smoothing as ratio of two norms, we can estimate them separately which gives us a good theoretical handle of smoothing. Note that if to is linear,
sup 6 (x(())
1/2
RSc(p):=1 :-
sup| X||= [X
since I and & quadratic forms. The following theorem shows that R-GCN layers are flexible in their ability to choose an appropriate rate of smoothing for graph:
Theorem 3. Let G1 (V, E1) be a graph and G2 (V, E2) be a rewiring of Gr. Consider an R-GCN layer yp defined as in (1), with relations = E,, Ez. Then for any X E [0, (2())) there exist values of θ, O1,
,,,0 O2 for which yp smooths with rate RS with respect to G2.
Proof. The map tp is given by
p(X;0, 1,0,0,,00 X x 1 + 12 -
5

---

Published as a conference paper at ICLR 2023
where A = A1 + A2 is the adjacency matrix of G2. Here D is the degree matrix of G2. Fix a [0, and take 1₁ = 2 = al and è = a.I. Then
(x) = (1 a
1 = a1- + aD a001/---2 1/2x -x)))xx
where L is the normalized Laplacian of G2. We will show that sp smooths with rate (L) Let = UEU be an orthogonal diagonalization of L. Let Ai...., An be the eigenvalues of L in ascending order and recall that 0 X I 2 for all with \1 O. We have
((((X)) = Tr(x* - aL) x) = Tr(x* -
ad: (X:) X),)) M:11 Ai1A(1 -F) = Eis
(a) $
( x),)² -
(1- (1-a)2)² TrX"" =1 o
(1-a)))08)))
with equality in (a) when (U X) = for + Hence,
((x(X) = (1 -cce2))
sup 6(X)#0 8(X)
(2)
Next, we compute
= =
- (b)
= -1-01-al
(U)))))) |UX = [|
with equality in (b) when (UX)i, = for * Hence
(x)
sup X=0
||
Combining (2) and (3) yields RS(p)) ad2 ad2(L). Since this holds for any [0, 1]. the result follows.
In Appendix B.3, we empirically demonstrate that R-GNNs achieve lower Dirichlet energy than GNNs.
4 FOSR: FIRST ORDER SPECTRAL REWIRING
In order to the R-GCN framework, need to make choice of rewiring algorithm that is capable of adding edges without removing any. We propose a first-order spectral rewiring algorithm (FoSR) with the goal of improving graph connectivity. The rate of spectral expansion, i.e., the rate which the spectral gap improves as a function of the rewiring iterations is one the key determinants of oversquashing (Banerjee al., 2022; Deac al., 2022). Compared existing approaches such as SDRF (Topping et al., 2022) and G-RLEF (Banerjee et al., 2022), the proposed algorithm has a faster rate of spectral expansion. See Figure for an illustration.
Our algorithm FoSR follows a similar philosophy as Chan and Akoglu (2016) optimizing the spectral gap of the input graph by sequentially adding edges such that the rate of spectral expansion is maximized. At each step, we wish to add the edge that maximizes the spectral gap of the resulting graph. However, computing the spectral gap for each edge addition is expensive as it requires to compute eigenvalues for O(n²) different matrices. Instead of computing this quantity directly, we use a first-order approximation the spectral gap based on matrix perturbation theory. The following theorem determines the first-order change of the eigenvalues of perturbed symmetric matrix:
Theorem 4. For symmetric matrices M E guxn with distinct eigenvalues, the i-th largest eigenvalue A; satisfies
V MAA(M) = I
where I; denotes the (normalized) eigenvector for the i-th largest eigenvalue of M.

---

Published as a conference paper at ICLR 2023
We provide a proof in Appendix C. Stated differently, the previous theorem allows make the linear approximation (M + 6M) 22 + Th Tr(VA - X2 + (8M)a2
(4)
Let us apply the approximation (4) to the spectrum of a graph G. We wish to sequentially add an edge (u, 2) in way that maximizes the spectral gap of the resulting graph. Equivalently, the second-largest eigenvalue of D- AD 1/2 should be minimized, since this matrix is equal to Using Theorem 4 for the matrix D- AD-1/2, we obtain the following result.
Proposition 5. The first-order change in X2 >2 1/2 1/222/ from adding the edge (u, v) is
dd
1)
vd. (v+22-11)
+ 2A2
(5)
VI+
where x denotes the second eigenvector of D ADD and Iı denotes the w-th entry of z.
We provide a proof in Appendix C. We choose to minimize the first term in (5)
2x,
((1 + d.) dd)
since this is simpler and cheaper to compute. To why this approximation is reasonable, note v
that (vTFZ)//4Z)) (d,, as du, d, - oo, while VI+-. ~ d So if the degrees of the nodes are sufficiently large and comparable in size, the first term in (5) dominates. Again, our decision optimize the first term is chosen for computational reasons. In Appendix B.2, we show that FoSR has significantly smaller computation overhead compared to SDRF on real and synthetic datasets. Further, we show in Appendix B. 1.2 that FoSR has much faster rate of spectral expansion compared to SDRF Finally in Appendix B.4, discuss the approximation error of FoSR.
For each iteration that it runs, FoSR computes an approximation the second eigenvector æ E R" of D-1/2 A- AD 1/2 and chooses an edge (u, v) which minimizes (6). To produce an initial approximation of x, we use power iteration (rather than computing full eigendecomposition) Let d E R" denote the vector of degrees of G. Let Vd denote the entry-wise square root of d, i.e., with components vd, Recall that vd is the first eigenvector of D AD 1/2, Since x is the second eigenvector of D D-1/2AD A/-1//11// 11/2, we may approximate it by repeatedly applying D 0-1/2AD D-/2 112 and then subtracting the component the direction of the first eigenvector. This map is given by
(x, vd Vd.
I D 1/2 1/2
2m
After applying this map, normalize back to unit vector, + | FoSR operates by repeatedly via power iteration.
alternating between adding an edge and computing new approximation Importantly, our algorithm avoids computing full cigendecomposiiionn of & by only approximating its second eigenvector. We compute increasingly accurate estimates of this eigenvector using power iteration. The steps of our method are outlined in Algorithm 1.
Algorithm 1 FoSR: First-order Spectral Rewiring
Input: E), iteration count l; initial number of power iterations Output: Rewired graph g' = (V,E")
1: Initialize x E Rn arbitrarily
2: for -= 1, ... do
I x+ D- 1/2 1/2 (2.vd) Vd 2m
3:
Approximate second eigenvector before rewiring
4:
x+ |
5: end for
6:
for i -= =1, do
7:
Add edge (i,j) which minimizes ((++d) (1+d))
8:
I D- 1/2
(x.vd)
P Power iteration to update second eigenvector
9:
I x+ 1
10: end for
7

---

Published as a conference paper at ICLR 2023
The number of edge additions k and the initial number of power iterations are hyperparameters. The number of power iterations r only needs to be chosen large enough to produce an initial approximation of the cigenvector æ. In practice, choice of iteration count k is problem-specific, and can be chosen to be such that the spectral gap increases sufficiently. We tried multiple configurations of k when training models.
found that taking r between 5 and 10 is sufficient. The proper
Computational complexity Taking advantage of the sparsity of G, FoSR requires ((m) floating. point operations for each power iteration and O(n") operations for each edge added. The Onn") operations come from searching over all node pairs (i, for the minimal value of y:Uj. where y: = / V + d:- This results in a cost of Okn)²). When the graph is sparse, we can often compute the minimal value of yeyy in a faster way. We can choose = arg ming yk and j = arg max, yh if ming Ms < 0 and the (i,j) chosen in this way is not already an edge. Indeed, the probability of (i.j) not already being an edge higher if G is sparse, In this case, the edge addition only takes can relax the minimization by choosing
arg min; yk and j = arg (5) Y& when min; yk I O. We can use a similar relaxation when min; yk > 0; take i == arg ming yh and = arg min Uk- If we use the above relaxations, the total cost is (km))
(m) operations. More generally,
5 EXPERIMENTS
We compare our rewiring methods to existing ones to demonstrate the efficacy of relational rewiring as well rewiring informed by spectral expansion several graph classification tasks.
Datasets We consider graph classification tasks REDDIT-BINARY ENZYMES, PROTEINS, COLLAB from the TUDataset (Morris al., 2020) where the topology of the graphs in relation to the task has been identified to require long-rang interactions. While certain node classification tasks have also been considered in previous works, these have been found to be tractable with nearest neighbor information (Brockschmidt, 2020).
MUTAG,
Compared methods We focus on approaches that preprocess the input graph by adding edges. Diffusion Improves Graph Learning (DIGL) (Klicpera et al., 2019) is liffusson-based rewiring scheme that computes a kernel evaluation of the adjacency matrix, followed by sparsification. SDRF (Topping et al., 2022) surgically rewires graph by adding edges to support other edges with low curvature, which are locations of bottlenecks. For SDRF, we include results for both the original method (configured to only add edges), and our relational method (again only add edges, and include the added edges with their own relation). Fully adjacent layers (Alon and Yahav, 2021) rewire the graph by adding all possible edges, setting & (V x V) \ Eg We include results for rewiring only the last layer (last layer FA) and rewiring every layer (every layer FA).
Experimental details We test each rewiring algorithm on an R-GCN (Schlichtkrull et al., 2018), with the relations varying depending on the rewiring method. For rewirings which do not explicitly assign relations to edges, we use two relations: one for the default edge type, and one for self-loops. In other words, simply use the rewired graph and add residual connections to the architecture. For each task, we use the same GNN architecture for all rewiring methods to illustrate how the choice of rewiring affects test performance. That is, we hold the number of layers, hidden dimension, and dropout probability constant across all rewiring methods for a given dataset. The hyperparameter values are reported in Appendix D.I. However, for each dataset, we separately tune all hyperparamters specific to the rewiring method (such as the number of iterations for FoSR and SDRF). We train all models with an Adam optimizer with learning rate of 10- and scheduler which reduces the learning rate by a factor of 10 after 10 epochs with no improvement in validation loss. For FoSR and SDRF, we only tuned the number of rewiring iterations. For DIGI. (Klicpera et al., 2019), we tuned the sparsification threshold (e) and teleport probability (a).
For optimizing hyperparamters and evaluating each configuration, we first select test set consisting of 10 percent of the graphs and development set consisting of the other 90 percent of the graphs. We determine accuracies of each configuration using 100 random train/validation splits of the development set consisting of 80 and 10 percent of the graphs, respectively. When training the GNNs, we use a stopping patience of 100 epochs based on the validation loss. We evaluate each hyperparameter configuration using the validation accuracy, so the test set is only used once to
8

---

Published as a conference paper at ICLR 2023
generate results for the best hyperparamter configurations. For the test results, record 95 percent confidence intervals for the hyperparameters with the best validation accuracy using the 100 runs.
Results Table shows the results of our experiments on various GNN layer types. Shown the test accuracy. For each rewiring method, using relational GNN type improves classification accuracy. The boost in accuracy from using an R-GNN is greatest for the rewiring methods which surgically add edges (FoSR and SDRF). Out of all of the rewiring methods, FoSR typically achieves the best classification accuracy when relational rewiring is used. When relational rewiring is not used, FoSR still outperforms DIGL and SDRF for most datasets. We note that +FA is sometimes competitive, but this is highly dependent on the GNN architecture. In particular, it does not perform well for GCNs and R-GCNs. Our results are also very competitive against results reported for the DiffWire methods by Amaiz-Roorigun et al. (2022, Table 1), although they use different type of architecture that is not directly comparable to preprocessing methods like ours or SDRF which sequentially add edges.
Table I:
Results of rewiring methods for GCN and GIN comparing standard and relational. The best results in each setting are highlighted bold font and best across settings are highlighted red.
GCN
Rewiring
REDDIT-BINARY
IMDB-BINARY
MUTAG
ENZYMES
PROTEINS
COLLAB
None
68, 252 + 1.098
49.770
0.817
72.150 + 2.442 27.607 = 1.164 70.982 + 0. 33.784 + 0.488
Last layer FA
68.485 = 0.945
48.980
0.945
70.050 + 2.027
26.407 = 1.204
71.018 + 0.963
33.320 + 0.435
Every layer FA
48.490 1: 1.044
48.170
0.801
70.450 1: 1.960
18.333 1 1.038
60.036 1 0.925
51.798 1 0.419
DIGL
19,980 = 0.680
49.910 + 0.811
71.350 + 2.391
27.517 # 1.053
70.607 + 0.731
15.530 + 0.291
SDRF
68.620 + 0.851
49. 100
0,904
71.050 + 1.872
28.367
+ 1.174
70.920
+ 0.792
33. 448 + 0.472
FoSR
70.330 + 0.727
49.660 0.864 80.000 + 1.574 25.067
0.994
73.420
0.811
33.836 0.584
R-GCN
Rowiring
REDDIT-BINARY
IMDB-BINARY
MUTAG
ENZYMES
PROTEINS
COLLAB
49.850 1. 0.653
50.012 0.917
69.250
2.085
25.600 1 1.186 69.518 1 0.725
33.602
1.047
Last layer FA
19.800 + 0.626
30.650
0.964
70.550
1.810 28.233
1.138
69.527
+ 0.815
31.732
1.194
Every layer FA
49.950 : 0.593
30.500
0.891
70.500
1.836
33.400 : 1.142
71.670
+ 0.882
33.616
0.978
DIGL
49.995 + 0.619
49.670
0.843
73.400
+ 2:007
28.283
: 1.213
08.
: 0.851
16.926 + 1.441
SDRF
58.620 1 0.647
53.640
1.043
72.300
1: 2.215
33.483
1 1.245
69.107
1 0.759
67.990
1 0.386
FOSR
76.590 1 0.531
64.050 1 1.123
84.450 1 1.517 35.633 1 1.151
73.795
1 0.692
70.650 1 0.482
GIN
Rewiring
REDDIT-BINARY
IMDB-BINARY
MUTAG
ENZYMES
PROTEINS
COLLAR
None
86.785
1.056
70.180
0.992
77.700
3.602
33.800 1.115
70.804 1 0.827 72.092 + 0.384
Last layer FA
90.220
0.4750
70.910
0. 0.788
83.450 + 1.742
47.400
1.387
72.304
0.660
75.056 0.406
Every layer
50.360 1: 0.648
49.160
0.870
72.550
3.016
28.383
1.052
70.375 1 0.910
32.894
0.390
DIGL.
76.035 1: 0.774
64.390
0.907
79.700
2.150
35.717
1
70.759
1 0.774
54.504
0.410
SDRF
86.410 = 0,590
69. 19.720
1.152
78
2.803
35.817
+ 1.094
69.813
+ 0.792
72.958
0.119
FOSR
87.350 + 0.398
71.210 + 0.919
78.000
2.217
29.200 + 1.376 75.107
0.817
73.278 0.416
R-GIN
Rewiring
REDDIT-BINARY
IMDB BINARY
MUTAG
ENZYMES
PROTEINS
COLLAB
None
87.965 1: 0.564
68.889
0.872
83.050 1 1.439 39.017 1 1.166 70.500 1 0.809 75.544 1 0.323
Last layer FA
89.995 1 0.647
69.710
1.025
80.600 +: 1.639
48.183 1: 1.401
70.304 1 0.844
75.434 1: 0.491
Every layer FA
36.855 + 0.943
71.480
0.876
83.050 + 1.518
54.950 + 1.331
71.045 + 0.909
75.432 + 0.475
DIGI.
74.425
0.723
63.930
0.947
81.450 1: 1.488
37.600
1.198
71.312 0.757
54.714
0.416 0.416
SDRF
86.825
0.523
70.210
0.806
82.700
1.782
39.583
1.333
70.696
+ 0.815
76.480
0.388
FOSR
0.416
71.810 1
+ 45.550
1.258
74.670
0.692
78.806
0.451
6 CONCLUSIONS
We proposed an efficient graph rewiring method for preventing oversquashing based on iterative first-order maximization of the spectral gap. Further, we identified a shortcoming of existing rewiring approaches that can cause oversmoothing and propose a relational rewiring method to overcome this with theoretical guarantees. Experiments on several graph classification benchmarks demonstrate that the proposed methods can significantly improve the performance of GNNs. In future work it will be interesting to study the effects of oversmoothing and oversquashing in relation to training dynamics and investigate rewiring strategies that aid training.

---

Published as a conference paper at ICLR 2023
Reproducibility Statement The computer implementation of the proposed methods along with scripts to re-run our experiments are made publicly available on https: htt///gitthl com/ kedar2/FoSR. The experimental settings are described in detail in Section 5 and Appendix D.I, which also details the compute infrastructure and selected hyperparameter values.
ACKNOWLEDGMENTS
This project has been supported by NSF CAREER Grant DMS-2145630, ERC Starting Grant 757983, DFG SPP 2298 (FoDL) Grant 464109215. This work is partly supported by BMBF in DAAD project 57616814 (SECAI).
REFERENCES
N. Alon and V. D. Milman. Eigenvalues, expanders and superconcentrators. In 25th Annual Symposium Foundations of Computer Science (FOCS), pages 320-322, 1984.
U. Alon and Yahav. On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations, 2021.
A. Emaiz-Rodríguee A. Begga, F. Escolano, and N. Oliver. DiffWire: Inductive graph rewiring via the Lovász bound. arXiv preprint 2rXiv:2206.07369 2022.
P. K. Banerjee, K. Karhadkar, Y. G. Wang, U. Alon, and G. Montúfar. Oversquashing in GNNs through the lens of information contraction and graph expansion. arXiv preprint vrXiv:2208.03// 2022. 58th Annual Allerton Conference on Communication, Control, and Computing.
P. Barceló, E. Kostylev, M. Monet, J. Pérez, J. Reutter, and J.-P. Silva. The logical expressiveness of graph neural networks. In International Conference on Learning Representations, 2020.
P. W. Battaglia, J. B. Hamrick, V. Bapst, A. Sanchez-Gonzalez, V. Zambaldi, M. Malinowski, A. Tacchetti, D. Raposo, A. Santoro, R. Faulkner, al. Relational inductive biases, deep learning, and graph networks. arXiv preprint 1oXivv/806.0111
2018.
J. Bober, A. Monod, E. Saucan, and K. N. Webster. Rewiring networks for graph neural network training using discrete geometry, 2022. URL httpsttppp.... / arxiv. wtt.:o////b////.00000/00
M. Brockschmidt. GNN-film: Graph neural networks with feature-wise linear modulation. In International Conference Machine Learning, pages 1144-1152, PMLR, 2020.
R. Brbbec-Gar,, M. Yurochkin, and J. Solomon. Rewiring with positional encodings for graph neural networks, 2022. URL https: wwwaaiivvvorr.. wrg. abs/2200 12674.
C. Cai and Y. Wang- A note on over-smoothing for graph neural networks. arXiv preprint arXiv:2006. 13318, 2020.
H. Chan and L. Akoglu. Optimizing network robustness by edge rewiring: a general framework. Data Mining and Knowledge Discovery,
2016.
Cheeger. A lower bound for the smallest eigenvalue of the Laplacian. Problems in Analysis, 625 (195-199):110) 1970.
D. Chen, Y. Lin, W. Li, P. Li. J. Zhou, and X. Sun. Measuring and relieving the over-smoothing problem for graph neural networks from the topological view. In Proceedings of the AAAI Conference Artificial Intelligence, volume 34, pages 3438 3445,, 2020.
R. Chung and F. Graham. Spectral graph theory. Number 92. American Mathematical Society, 1997.
A. Deac, M. Lackenby, and P. Veličković. Expander graph propagation. arXiv preprint arXiv:2210.02997, 2022.
Di Giovanni. Rowbottom, B. P. Chamberlain, T. Markovich, and M. M. Bronstein. Graph neural networks gradient flows. arXiv preprint arXiv:2206. 10999,, 2022.
10

---

Published as a conference paper at ICLR 2023
V. Dwivedi and X. Bresson. A generalization of transformer networks to graphs. arXiv preprint Wwxiv:2012.09699 2020. AAAI 2021 Workshop on Deep Learning on Graphs: Methods and Applications (DLG-AAAI 2021).
M. Fey and E. Lenssen. Fast graph representation learning with Pytorch Geometric. In ICLR Workshop Representation Learning Graphs and Manifolds, 2019.
R. Forman. Bochner's method for cell complexes and combinatorial Ricci curvature. Discrete and Computational Geometry, 2933):32--374, 2003.
Friedman, On the second eigenvalue and random walks in random d-regular graphs. Combinatorica, 11(4):331-362 1991.
M. R. Garey, D. S. Johnson, and L. Stockmeyer. Some simplified NP-complete problems. In Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, pages 47-63, 1974.
M. Gori, G. Monfardini, and F. Scarselli. A new model for learning in graph domains. In IEEE International Joint Conference on Neural Networks, volume 2, pages 729-734, 2005.
W. Hamilton, Z. Ying, and J. Leskovec. Inductive representation learning large graphs. Advances in Neural Information processing Systems, 30: 1024-10344 2017.
C. R. Harris, K. J. Millman, J. Van Der Walt, R. Gommers, P. Virtanen, D. Couraaeau,, E. Wieser, Taylor, S. Berg, N. Smith, et al. Array programming with NumPy. Nature, 585(7825):357-362, 2020.
D. Hunter. Matplotlib: 2D graphics environment. Computing Science Engineering, 9(03): 90-95, 2007.
V. Kaibel. On the expansion of graphs of 0/1-polytopes. In The sharpest cut: The impact of Manfred Padberg and his work, pages 199-216, 2004.
N. Kipf and M. Welling, Semi-supervised classification with graph convolutional networks. In International Conference Learning Representations, 2017.
J. Klicpera, S. Weißenherger, and S. Günnemann. Diffusion improves graph learning. Advances in Neural Information processing Systems, 33, 2019.
D. Kreuzer, D. Beaini, W. Hamilton, V. Létournea, and P. Tossou. Rethinking graph transformers with spectral attention. Advances in Neural Information Processing Systems, 34:21618-21629 2021.
Leighton and S. Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. Journal of the ACM, 46(6):777-83) 1999.
D. A. Levin and Y. Peres. Markov chains and mixing times, volume 107. American Mathematical Society, 2017.
Q. Li, Z. Han, and X.-M. Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
Y. Li. D. Tarlow, M. Brockschmidt, and R. Zemel. Gated graph sequence neural networks. arXiv preprint arXiv: I.5493, 2015.
R. Lyons and Y. Peres. Probability on and networks, volume 42. Cambridge University Press, 2017.
B. Mohar. Isoperimetric numbers of graphs. Journal combinatorial theory, Series B, 47(3): 274-291, 1989.
C. Morris, M. Ritzert, M. Fey, W. Hamilton, J. E. Lenssen, G. Rattan, and M. Grohe. Weisfeiler and Leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI conference artificial intelligence, volume 33, pages
2019.

---

Published as a conference paper at ICLR 2023
C. Morris, N. M. Kriege, F. Bause, K. Kersting, P. Mutzel, and M. Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. In ICML 2020 Workshop on Graph Representation Learning and Beyond (GRL+ 2020), 2020. URL htattp:/epprits.... www..c...vvvi......... 6469/.
Y. Ollivier. Ricci curvature of Markov chains on metric spaces. Journal of Functional Analysis, 256 (3)8810-866 2009.
K. Oono and Suzuki. Graph neural networks exponentially lose expressive power for node classification. In International Conference on Learning Representations, 2020.
A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein,
L. Antiga, et al. Pytorch: An imperative style, high-performant deep learning library. Advances in Neural Information Processing Systems, 32, 2019.
Y. Rong, W. Huang. T. Xu, and Huang. Dropedge: Towards deep graph convolutional networks on node classification. In International Conference on Learning Representations, 2020.
F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61-80, 2008
M. Schlichtkrull, N. Kipf, P. Bloem, R. v. Berg, Titov, and M. Welling, Modeling relational data with graph convolutional networks. In European Semantic Web Conference, pages 593 607. Springer, 2018.
G. Stewart and J. Sun. Matrix Perturbation Theory. Computer Science and Scientific Computing. Elsevier Science, 1990.
Topping, D. Giovanni, B. P. Chamberlain, X. Dong, and M. M. Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. In International Conference on Learning Representations, 2022.
A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, t. Kaiser, and I. Polosukhin. Attention is all you need. Advances in Neural Information Processing Systems, 30, 2017.
Veličković. G. Cucurull, A. Casanova, A. Romero, P. Lio, and Y. Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and S. Y. Philip. A comprehensive survey graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 32(1):4-24, 2020.
K. Xu, Li, Y. Tian, T. Sonobe, K.-i. Kawarabayashi, and S. Jegelka. Representation learning on graphs with jumping knowledge networks. In Proceedings of the 35th International Conference Machine Learning (ICML), pages 5453-5462, 2018.
K. Xu, W. Hu, J. Leskovec, and S. Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019.
L. Zhao and L. Akoglu. Pairnorm: Tackling oversmoothing in gnns. In International Conference on Learning Representations, 2020.
J. Zhou, G. Cui, S. Hu, 7. Zhang, C. Yang, 7. Liu, L. Wang, C. Li, and M. Sun. Graph neural networks: review of methods and applications. Al Open, 1:57-81, 2020.
12

---

Published as a conference paper at ICLR 2023
APPENDIX
A SPECTRAL GAP AND CHEEGER CONSTANT
A.1 QUANTIPYING STRUCTURAL BOTTLENECKS VIA THE CHEEGER CONSTANT
Since traditional GNNs use the input graph to propagate neural messages, structural characteristics of the input graph play crucial role in the quality of signal propagation across nodes. Our method is motivated from the key idea that structural bottlenecks in the input graph lead to information oversquashing GNNs. classic measure of "bottlenecked-ness" of graph is the Cheeger constant (Chung and Graham, 1997)
[as)
MG))
== min E+SCV min (v S, vol
where vol boundary of S V. This definition considers the number of edges connecting two complementary subsets of nodes and their volume as measured by the sum of the degrees of the nodes, and then takes the minimum of this value over all possible non-trivial bipartitions of the graph.
S S and as = {uu, v):
S E S, (u. E } is the edge
Note that 0 S (g) < 1 for all S C V. G is connected if and only if h(g) > 0.
Intuitively, when h(g) is large, & has no structural bottlenecks in the sense that every part of g is connected to the rest of it by large fraction of its edges.
large (9) implies that there low probability of being trapped in a small subset of the nodes and consequently, simple random walk over the nodes of g is rapidly mixing (Levin and Peres, 2017).
Well-connected graphs such the complete graph over nodes, Kn, has high Cheeger constant, while easily- eesily-disoonnected graphs have low Cheeger constant. An example of the latter is the dumbbell graph K,, K,,K, comprising of two cliques joined by bridge (see Figure 1), which has Cheeger constant of 1/(1 + n(n - 1)).
A.2 BOUNDING THE CHEEGER CONSTANT VIA THE SPECTRAL GAP
In general, computing the exact value of h()) in practice is known to be hard problem; see, e.g.. Leighton and Rao (1999); Garey et al. (1974); Mohar (1989); Kaibel (2004). Nonetheless, it is possible bound the Cheeger constant from below and from above in terms of the spectral gap as we explain next. Recall from Section 2.1 that the spectral gap of a graph is the difference d2 A1 between the first two eigenvalues of the Laplacian (in increasing order), whereby Å 0.
The discrete Cheeger inequality (Cheeger, 1970; Alon and Milman, 1984) shows that the spectral gap of 9 provides an estimate of its Cheeger constant:
A2
M9) S 22
(8)
To intuitively understand this inequality, we can consider the variational formulation of the spectral gap (Chung and Graham, 1997):
A inf LL xTx
LDD
We can write the numerator above
Lx
Dj
Vdl
d
(D,))E
Let be a subset of the nodes. We may encode S as a "zero-one vector", writing x; = Vdl if and x; = Off i & S. This gives us
a La Σ (u,)sas las).
(WE)
13

---

Published as a conference paper at ICLR 2023
That is, we encode terms from h(g) into the expression for X2 if use this variational formulation.
The discrete Cheeger inequality tells us that the spectral gap is bounded away from zero if and only if h()) is bounded away from zero. G is connected and only if X2 > O. Since the spectral gap can be computed efficiently, we use it as measure of graph bottlenecked-ness in lieu of the Cheeger constant.
B SPECTRAL GAP AND OVERSQUASHING
In this section, we provide some more intuition behind our idea of optimizing the spectral gap of the input graph for alleviating structural bottlenecks and improving the overall quality of information propagation across nodes.
The rate of spectral expansion, i.c., the rate at which the spectral gap improves as a function of the rewiring iterations is one of the key determinants of oversquashing (Banerjee et al., 2022), and a faster rate is one the main features of our new algorithm. We show that FoSR has a faster rate spectral expansion compared to existing curvature- -bsed methods such SDRF (Topping al., 2022) for both the synthetic benchmark NEIGHBORSMATCH (Alon and Yahav, 2021) (Appendix B.1.1) and the TUDataset (Morris et al., 2020) (Appendix B.1.2).
In Appendix B.2, we show that optimizing only the first-order change in the spectral gap gives FoSR significant computational advantage over SDRF In Appendix B.3, empirically explore the trade-off between oversquashing and oversmoothing as function of the number of rewiring iterations. Finally in Appendix B.4, we discuss the approximation error of FoSR.
B.I COMPARING THE RATE OF SPECTRAL EXPANSION FOR FOSR AND SDRF
B.1.1 THE NEIGHBBRSMAATCH PROBLEM (DETAILS FIGURE
Alon and Yahav (2021) introduced the synthetic benchmark NEIGHBORS test the impact of oversquashing in GNNs. Given an input graph G, suppose that wish predict the label for node T; see Figure (()). The correct label is the label the green node that has the same number of blue neighbors as T. For the example in Figure 2(a), the answer is B which happens reside at the opposite end of the graph. A correct prediction of the label for this example will require a number of GNN layers / that equal the diameter of the graph. With increasing however, each message-passing layer, information from exponentially-groviin receptive fields need to be concurrently propagated. This leads to oversquashing and the GNN fails to propagate long-range signals and fit the training dataset perfectly.
S
T
Figure 2: Learning task modeled the NEIGHBORSMATCH problem.
We consider a learning task modeled on the NEIGHBORSMAACH problem. Given an input graph G. a target node T. and subset S of the nodes of G, assign each node in S different random [S] -idmessioonl one-hot vector encoding the number of blue neighbors. Likewise, we represent the label of T as random |8| dim-dnmnsi one-hot vector and the goal is to predict the node T E S with
14

---

Published as a conference paper at ICLR 2023
the same label T. We take the imput G to be path-of-cliques, which comprises of three cliques each of size 10 connected in a path by two edges; see Figure 2(b). The set S consists of the first nodes in clique-1, and the target T is the last node of clique-3. The range of the interaction, i... the maximum distance between and a node in S is 5. We trained graph attention network (Veličković al., 2018) with 6 layers each of width 64 on training dataset comprising of 10000 copies of G, where each copy has different mapping matching the target.
Figure 1 (bottom) shows the evolution of the normalized spectral gap and training accuracy function of the number of rewiring iterations for three algorithms: our FoSR, SDRF (Topping et al., 2022), and G-RLEF (Banerjee et al., 2022). SDRF is motivated from the idea that negatively curved edges lead to oversquashing. The notion of curvature, which can be construed as a "local" Cheeger constant, plays a key role in the SDRF rewiring process. SDRF cycles between adding a supporting edge around negatively curved edge and removing a redundant positively-curver edge; see Figure (top). Since the addition and removal of edges are done independently of each other, SDRF can potentially disconnect a connected input graph. G-RLEF, on the other hand, seeks improve the "global" Cheeger constant (G) sampling edges according to inverse triangle counts (a proxy for curvature) and using local edge flip mechanism that the input graph is never disconnected. In our experiments, we configured SDRF to only add edges. For all three algorithms, we observe that both the normalized spectral gap and training accuracy increase monotonically in the number of rewiring steps until they saturate at around 150 iterations. The rate of spectral expansion i.e., the rate at which the spectral gap improves function of the rewiring iterations is the fastest for FoSR.
B.1.2 THE TUDATASET
Figure shows the normalized spectral gap as a function of the number of rewiring iterations for FoSR and SDRF on the TUDataset (Morris et al., 2020). Again, we observe that FoSR has much faster rate of spectral expansion compared to that of the SDRF (Topping et al., 2022).
REDDIT-BINARY
INDE-BINARY
MUTAG
SDRF
0.6
SDRF
0.7
SDRF
0.175
RiSA
0.150
0.7
0.125
0.6
0.4
0.3
0.07%
0.4
0.1
20
20
30
10
20
30
0
10
20 benaioos
30
Benotions
FNZYMES
COLLAR
SDAF
500F
SDRP
0.4
Fa5Al
FreRt
0.500
Fosill
Spectraign 580
0.1
Spectral Q60
0.475
0.3
0.2
0.2
0.425
0.000
0.1
10
0.175
10
herstions
Rorations
korations
Figure 3:
Normalized spectral gap as a function of the number of rewiring iterations for FoSR and SDRF on the TUDataset graphs (Morris et al., 2020). We record the average spectral gap across all graphs in the dataset for each iteration count.
B.2 COMPARISON OF THE COMPUTATION TIME FOR FOSR AND SDRF
Our First-order Spectral Rewiring (FoSR) method computes the first-order change in the spectral gap from adding each edge, and then adds the edge which maximizes this. Optimizing only the first-order change gives our method significant computational advantage over competing curvature- -aased based methods like the SDRF (Topping et al., 2022). Figure 4 and Table 2 show the computation time of FoSR and SDRF for synthetic dataset consisting of Frdös-Rényi graphs, and the TUDataset graphs
15

---

Published as a conference paper at ICLR 2023
Rewiring Erdés-Rényl (FoSR)
Rewiring Erdós-Rényl (SDRF)
Runtime (5)
30
4-
Runtime
20
2-
10-
2000
6000 8000
10000
2000
4000
6000
8000
10000
Number nodes
Number nodes
Figure 4: Compute time of FoSR and SDRF for Erdös-Rényi graphs. For graph with nodes, we add an edge (i.j) with probability p 5log
(Morris et al., 2020) respectively. We observe that the run times for FoSR are almost an order of magnitude lower than that of SDRF
Table 2: Runtime to rewire every graph for 10 iterations (in seconds).
Architecture REDDIT-BINARY IMDB-BINARY MUTAG ENZYMES PROTEINS COLLAB
FOSR
37.4167
0.0924058
0.0146499
0,0622702
0,1677542
4,58400
SDRF
193.432
5.28793
0.407810
2.38515
5.51248 610.542
B.3 TRADE-OFF BETWEEN OVERSQUASHING AND OVERSMOOTHING AS A FUNCTION OF REWIRING ITERATIONS
Table 3 shows that the relational architecture indeed helps to reduce oversmoothing, since the relational rewiring leads higher Dirichlet energies. Here the Dirichlet energy is measured as an average over all graphs in the dataset after training, summed over 100 runs.
Relational GNNs evidently help to reduce oversmoothing. However, the tradeoff between oversquash- ing and oversmoothing still exists. Recall that input graphs with small spectral gaps are prone to oversquashing, whereas inputs with large spectral gaps are prone to oversmoothing (see Section 3.2). We use R-GNNs to alleviate oversmoothing, but there is still optimal number of edges to add, beyond which performance declines. Figure 5 shows that the performance for R-GCNs peaks at around 25 iterations, which is reflected in both the test accuracy and Dirichlet energy of the final layer.
B.4 DISCUSSION ON THE APPROXIMATION ERROR OF FOSR
When rewiring graph using FOSR, the objective at each iteration is to add the edge which maximally increases the spectral gap. Since FoSR makes this calculation using first-order approximation of the spectral gap, there is some enror incurred between the estimated spectral gap and the actual spectral gap. This error is caused by two factors. The first is the error from using the first-order change of the spectral gap instead of the actual change. The second error accrues from using the dominant term of the first-order change instead of the first-order change. We record each of these three quantities (actual change, first-order change, FoSR approximated change) for graphs in the ENZYMES dataset (Morris al., 2020) in Figure 6. We see that the actual change is well-correlated with the approximations, and that the approximations are well-correlated with each other.
While FoSR accumulates some error from the actual change in the spectral gap, interested in how this affects its ability to choose good edges for rewiring. Hence, is natural to ask how FoSR compares to a greedy algorithm which computes the spectral gap exactly. We test the
primarily
16

---

Published as a conference paper at ICLR 2023
Table 3: Dirichlet energy of the final layer for TUDataset graphs after training. The relational architectures tend to provide higher energy, which indicates that they are less prone to oversmoothing.
GCN
Rewiring REDDIT-BINARY IMDB BINARY
MUTAG
ENZYMES
PROTEINS
COLLAB
None
0.6188 = 0.0676 0.0018 0.0001 0.0622 = 0.0046 0.0954 + 0.0026 0.0470 # 0.0008 0.0026 + 0.0001
DIGL
0.0002 1 0.0000 0.0005 0.0001 0.0303 1 0.0032 0.0392 0.0007 0.0398 1. 0.0010 0.0001 1. 0.0000
SDRF
0.6110 0.0584 0.0013 .000001 0. 0.0504 0.0041 0.0927 0.0023
0.0468 0.0007 0.0023 0.0001
FoSR
0.6017 0.0497 0.0020 0.0001 0.0579 0.0021 0.08441 0.0023 0.0699 0.0013 0.0030 0.0005
R-GCN
Rewiring
MUTAG
PROTEINS
None
0.8077 1: 0.0007 0.0607 0.0001 0.0966 1 0.0040 0.1214 0.0024 0.1161 1. 0.0043 0.0904 0.0001
DIGL
0.0425 1. 0.0000 0.0309 0.0000 0.0918 1 0.0046 0.0894 0.0015 0.0979 1. 0.0045 0.0041 0.0000
SDRE
1.8160 # 0.0161 0.0613 + 0.0061 0.1575 # 0.0101 0.2111 + 0.0069 0.1235 # 0.0017 0.8306 + 0.0475
FOSR
1.3733 + 0.0203 1.3040 + 0.0705 0.5345 + 0.0201 0.3206 + 0.0088 0.4308 # 0.0337 0.8139 + 0.0382
GIN
Rewiring REDDIT-BINARY IMDB BINARY
MUTAG
ENZYMES
PROTEINS
COLLAB
Nome
1.1215 1. 0.0379 0.0816 0.0093 0.1287 1. 0.0053 0.1064 0.0018 0.0853 1 0.0034 0.1128 0.0074
DIGL
0.1080 0.0103 0.0517 0.0061 0.0442 1 0.0052 0.0675 0.0011 0.0679 1. 0.0029 0.0067 0.0011
SDRF
1.0996 0.0392 0.0691 0.0092 0.1126 0.0011 0.1005
0.0783 0.0027 0.1164 0.0075
+: 0.0522 0.0916
+:
+: 0.0058 0.1271
R-GIN
Rewiring
MUTAG
PROTEINS
None
1.2972 1 0.0336 0.2625 0.0235 0.4140 1 0.0142 0.1825 1. 0.0039 0.3021 1. 0.0286 0.3293 0.0244
DIGL
0.3265 + 0.0271 0.0591 + 0.0075 0.0772 # 0.0052 0.1319 + 0.0021 0.2534 # 0.0168 0.0175 + 0.0016
SDRE
1.5525 + 0 0.0260 0.1031 + 0.0051 0.2754 + 0.0102 0.1768 + 0.0027 0.2373 # 0.0141 0.2695 + 0.0153
FoSR
0.8037 + 0.0227 1818 + 0.0125 0.2901 + 0.0063 1.000 + 0.0010
0.1393 + 0.0051
0.2414 + 0.0129
1.4
FcSR
SDRF
1.2
Test accuracy
58
Energy
56
0.8
FoSR
54
0.6
0.4
52
0.2
50
0.0
0
25
50
75
100
125
150
0
25
50
75
100
125
150
Iterations
Iterations
Figure 5: Trade-off between oversquashing and oversmoothing as function of rewiring iterations for R-GCN on the IMDB-BINARY graph classification task. Left: Test accuracy as a function rewiring iterations. Right: Dirichlet energy of the final layer as a function of rewiring iterations. The performance for R-GCNs peaks at around 25 iterations, which is reflected in both the test accuracy and Dirichlet energy.
performance of FoSR on synthetic dumbbell graph, consisting of two cliques of size 50, connected via path of length 3. The results are shown in Figure 7. We see that the spectral evolution of FoSR indistinguishable from that the greedy method, indicating that approximation is strong and that the two methods choose similar edges.
17

---

Published as a conference paper at ICLR 2023
0.550
0.150
0156
0.125
0.125
0.12
Ristoterr change
Makual chargge
0.05
0.075
0.055
0.050
0.000
0.00
0.000
-0.028.
-0.01
-0.00
approximated change spectral gap
change spectral gmp
approximated change gop
Figure 6: Change in the spectral gap, first-order change, and the FoSR approximated change for rewired graphs. The changes are recorded for each graph in the ENZYMES dataset after 1 rewiring iteration.
Rewiring dumbbell graph
FoSR
Greedy
0.06
Spectral
0.04
0.00
20
40
60
80
100
lterations
Figure 7: Evolution of the spectral gap of a dumbbell graph under rewiring, evaluated at every iteration count between and 100. The performance FoSR is nearly identical method which selects edges to add via exact computation of eigenvalues.
18

---

Published as a conference paper at ICLR 2023
C DETAILS ON SECTION 4
Proof of T'heorem 4. We refer to Stewart and Sun (1990, Theorem 2.3) for a proof that X a continuously differentiable function and a computation of its gradient for general classes of matrices. We provide calculation for our case here.
Fix symmetric matrix Mg R and let M, UEU-I be an orthonormal diagonalization of Mo with the diagonal entries of Σ sorted in descending order. Fix j. k E [nx. Let Е denote the
matrix whose (j, k) entry is and remaining entries are O. Define curve y R - R=x" by
(() = Mo + tU -U,,,UU
Then
= -
X, 8i.jde,
(10)
where 81g is equal to if j and 0 otherwise. The final equality follows since the i-th diagonal entry of is Ao and adding an off-diagonal entry does not change its eigenvalues. For sufficiently small the order of the eigenvalues does not change. By the chain rule,
d (t()t)) = (dA,) M. (...)...((0)) (f(0)).
dt d=
By equation (10), the left-hand side of the above equation is equal to ōi, So
5 (dd:) (+(0)) (dA:) Mo (UFg,
By the definition of the gradient,
Tr(U T = (dd:) (U (UFF,.uU))) = di = Tr(Fi, Fg..)
Rewriting the left-hand side of the above equation gives us
TrU (M)) TTG,,
Since this holds for all j, k E [n]] and the Ej,t span R this implies that
U VA, = Ei,
VA,(MM) = U U
VAN(MM) ITJT
as desired.
Proof of Proposition 5. Let A be the adjacency matrix of a graph G, and let AN be the normalized adjacency matrix. Let be an eigenvector of AN with eigenvalue X. Suppose that we add an edge (u, v) to G. Let 8AN denote the entry-wise change in the normalized adjacency matrix from adding the edge (u, v). If # and # v. then
(8AN Dij 0.
If i of and v, then
(BAN) = Aij Vit, (I+ Voh) )
1
If Tri-u u and j A v, then
(8AN)is = Aij ( 1
Vdz VI+ van
If i = and v, then
(8AN)s = (1 V1+ vd,)
19

---

Published as a conference paper at ICLR 2023
By Theorem the first-order change in (2(AN) is given by
x² (
Σ
(6AN)ssaaay + ΣE
(6A
(6A))aaaaa + ΣE
(ŌAN Majaeee + ΣE (6AAN)eaaa
1=v
Σ Σ
(dAN)saa
E
Σ
(ÓAN))JUTY + E
E
(6AN)s)aia)
1 =
$4a,0 j=v
iz suu.
LuZo
Auj
1
(VT+ + da)) (v (v)+
Vdj
+I+
Van
Aug
(V1+ + dv)(++1++++ de)
ddz
dh
vdg
AquTTTu
Atviit Vdd
1
Vid
+h+
Viu
Vily)
iFuvv
2r
+ +2 +2Σ
1
(VI daa) (VI+ dn)
Vdl
VI+ du
vdl
itu
Aluitttu
1
+
Vd
di+du
Vdu
-11
Vdh
(V1 du))
dw)
V1+
isfu
Vdn
+2 Σ (AN)iu
+I
2I
-1
Vol
E(AN)
V1+ d... +11+dd) +d))
VT+ de
vdu VI+ de
+ 2 Σ (AN)iu
Since x is an eigenvector of Ay with eigenvalue X, we may write the above expression as
20 (V1 ( + 2Xx3
Vd
-1) 2Xx2
Vdn
1):
Vi+d
VT+
Applying this equality to the second eigenvector of Ay yields the result.
D DETAILS ON THE EXPERIMENTS FROM SECTION
The computer implementation of the proposed methods along with scripts to re-run our experiments are made publicly available on https: /appoy/o/nn 4open. science/ss F--FFFSRRSEE In the following list details on hyperparameters, libraries, and the compute infrastructure we used in these experiments.
D.I MYEERSSRAMETERS
Table 4: Common hyperparameters
Dropout
0.5
Number of layers
Hidden dimension
64
Learning
10-3
Stopping patience
epochs
20

---

Published as a conference paper at ICLR 2023
Table 5: Rewiring iteration counts for FoSR and SDRE
FoSR
Architecture REDDIT-BINARY IMDB-BINARY MUTAG ENZYMES PROTEINS COLLAB
GCN
40
20
GCN
40
40
5
GIN
20
10
R-GIN
40
20
5
40
20
10
SDRF
Archilecture REDDIT-BINARY IMDB BINARY MUTAG ENZYMES PROTEINS COLLAB
GCN
20
5
5
40
GCN
40
20
GIN
5
20
R-GIN
Table 6: DIGL hyperparameters.
Teleport probability (a)
Architecture MEDDIT-BINAR IMDB BINARY MUTAG ENZYMES PROTEINS COLLAB
0.05
0.15
0.05
0.15
0.15
0.15
R-GIN
0.05
0.15
0.05
0.05
0.05
0.05
Sparsification threshold
Architecture REDDIT-BINARY IMDB BINARY MUTAG ENZYMES PROTEINS COLLAR
GCN
10
10
10
10
10-4
10
R-GCN
10
10
10
10
10
GIN
10-3
10-1
10-1
10-3
10-3
10-1
R-GIN
10-3
10"
10-3
10-
10-4
10-3
D.2 COMPUTER INFRASTRUCTURE AND LIBRARIES
In this section, we provide details of our implementation. All the experiments were implemented in Python using PyTorch (Paszke al., 2019), NumPy (Harris et al., 2020), PyG (PyTorch Geometric) (Fey and Lenssen, 2019), with plots created using Matplotlib (Hunter, 2007). PyTorch, PyG and NumPy are made available under the BSD license, and Matplotlib under the PSF license.
We conducted all our experiments on local server with 2x 22- 2-CCore/44-Thhe Intel Xeon Scalable Gold 6152 processor 12.1/3.7 GHz) and 8x NVIDIA GeForee RTX 2080 graphics card (11 GB, GDDR6).
21


Reviews:
[{"review_id": "tlBvZoPgP8", "reviewer": "Reviewer_j5dr", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "The work addresses the issue of oversquashing in GNN in proposing a new approach of rewiring graphs so as to improve the spectral gap of the graph (as it has been studied that spectral gap is a key feature in preventing oversquashing). The proposed rewiring algorithm comes from a study of perturbation of the Fiedler vector  and spectral gaps when adding one edge. The methods is conceptually simple and relevant and some numerical results show its performance.", "summary_of_the_review": "My recommandations is for marginal accept, because it is a sound work on an existing issue, even if the work is in part incremental.\n\n\nUpdate after revision: I increase the score to 8: Accept.", "strength_and_weaknesses": "Strength:\n\n1- The idea and derivation of the first order spectral rewiring is very well explained in Section 4 (even if it relies on known tools or algorithms, the idea is, for me, new in this context).\n\n2- The resulting method shows improvements in effeiciency as compared to contenders, and the numerical experiments are extensice enough to assess that.\n\n3- Globally the article is clear and it's a nice read, without any superfluous elements.\n\nWeaknesses\n\n1- The issue addressed, navigating the trade-off between oversquashing and oversmoothing, exists yet I am not certain it is a major one and several works have already discussed and addressed the issue. The contribution is, on this side, incremental.\n\n2- The algorithm relies on approximate (perturbation-based + power-method eigenvectors computation + approximation of argmin (y_i y_j) which appear to work yet are not really controled or checked. What would happen with difference choices of k, r and of the argmin method ? Are the results robust ? What would be the choice of r if k has to be increase ?\n\n3- there don't appear to gave results comparing the computation time to methods from contenders. Also, parameters (as in D.1) could be varied a little bit, at least to check robustness against ther variation.  \n\n Minor questions :\n\n- results on ENZYMES appear to be low as compared to what I have seen in other works; Why that ?\n\n-   the number of digits in the numerical results (5 digits on percentages) appear to be high. Is it really trustable ? Even with 100 runs, I wold expect less precision of the accuracy results.\n\n- the datasets are rather small size (in average number of nodes and/or number of graphs). Given the  dicussion about computational complexity and the approximations leveraged in the method, I would have expected results on larger datasets as well.\n\n- I don't think that Appendix A is useful (I think that expected readers are familiar with that).\n\n- Figure 1 should be larger so as to be more readable. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Vx3_gbaddm", "reviewer": "Reviewer_T9j4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "The authors propose a graph rewiring method, which aims to tackle the oversquashing problem in GNN literature. The proposed method greedily adds edges for maximizing the spectral gap of the graph sequentially. The authors also propose the use of relational GNNs to preserve the original graph topological information. The experimental results show that the proposed method achieves better test accuracy on graph classification tasks compared to several recently proposed rewiring methods.", "summary_of_the_review": "The authors attempt to tackle the oversquashing problem and propose a new rewiring method and the use of relational GNN. Their proposed method aims to add edges that maximize the spectral gap. My major concern about the paper is its motivation, where the complete graph can simply resolve the oversquashing problem and the original graph information can be preserved by the use of relational GNN. The experimental results only demonstrate the better test accuracy of the proposed method on graph classification tasks, where some simple baseline and transformer-based methods are ignored. Also, the comparison of the time efficiency is not presented. Hence, I believe the paper needs some revision before publishing.\n\n====================post rebuttal===========================\n\nI thank the response by the authors. Most of my concerns are well-addressed but one still remains (please see my response below). Nevertheless, based on the merits of the current paper, I raise my rating from 5 to 6. ", "strength_and_weaknesses": "## Strengths\n\n- Proposing the use of relational GNN to preserve the original graph topological information is reasonable.\n\n- The proposed edge-adding method, FoSR (First-order Spectral Rewiring), can maximize the spectral gap in a greedy but effective way.\n\n- The experimental results on the graph classification task demonstrate the superior performance of the proposed method in terms of test accuracy.\n\n- The experiment setting is rigorous. The code seems to be well-documented.\n\n## Weaknesses\n\n- The criterion of maximizing the spectral gap for adding edges seems not well-motivated.\n\n- The experiment results do not support or validate the theoretical analysis and claims. Also, the efficiency (i.e. time complexity) of FoSR is not reported and compared with baseline methods.\n\n- Some naive baselines (i.e. fully connected graph at the last layer) and transformer-based methods are only mentioned but not included in the experiments.\n\n## Detail comments\n\nI have mixed feelings about this work. On one hand, I like the idea of leveraging relational GNNs to preserve the original graph information is great for graph rewiring-based methods. I also love how rigorous the authors prepared their experiments and make their code well-documented (at least specifying the environment).\n\nOn the other hand, I have several concerns about the paper. I explain all the listed weaknesses below.\n\n### The criterion of maximizing the spectral gap for adding edges seems not well-motivated. \n\nAs the authors mentioned in the Section 3, once we introduce relational GNNs, we will not suffer from losing the original topological information (i.e. $\\mathcal{E}_1$). As also mentioned by the authors, using a complete graph can maximally resolve the oversquashing issue, albeit it comes with the cost of losing original topological information. However, this is not a problem when we consider relational GNNs. Hence, should not we simply choose $\\mathcal{E}_2 = \\mathcal{E}/\\mathcal{E}_1$? I do not get the motivation why we need a special design of $\\mathcal{E}_2$ for solving the oversquashing problem theoretically.\n\nNote that the naive approach abovementioned has an obvious drawback, which is its scalability on large graphs similar to the transformer-based method. However, given the fact that the authors only consider graph classification tasks, I feel like there is no need for the proposed FoSR method. Maybe I miss something, please correct me if I do. If not, I would suggest the authors test these rewiring methods on node classification tasks, where the graph can be huge.\n\n### The experiment results do not fully support or validate the theoretical analysis and claims. Also, the efficiency (i.e. time complexity) of FoSR is not reported and compared with baseline methods.\n\nI notice that the authors demonstrate that their method indeed achieves a higher spectral gap compared to the baselines in Figure 1. I wonder if the authors also report similar results for their main experiments? Note that this is quite important, as the authors claim in the introduction that the spectral gap is a measure of the oversquashing effect.\n\nAlso, one major contribution of the paper is their first-order approximation formalism, which makes the FoSR algorithm much faster in theory. However, I wonder how the running time of FoSR compared to the other baselines. Does FoSR win in both test accuracy and time complexity? If not, what does the trade-off look like?\n\n### Some naïve baselines (i.e. fully connected graph at the last layer) and transformer-based methods are only mentioned but not included in the experiments.\n\nOne major drawback of the experiments is the selection of baseline methods. As mentioned by the authors in the introduction, some naive methods can resolve the oversquashing problem. For example, leveraging a complete graph in the last layer of the GNN. The other naive baseline would be the one that I proposed earlier, which simply chooses $\\mathcal{E}_2 = \\mathcal{E}/\\mathcal{E}_1$ for relational GNN. Finally, note that the transformer-based methods will not suffer from oversquashing and perform pretty well on graph classification tasks recently. I wonder how the proposed methods compare to transformer-based methods. Do we still need these rewiring techniques for graph classification? As I mentioned earlier, if the authors want to prevent comparison with transformer-based methods or methods leveraging complete graphs, they should conduct experiments on node classification tasks with large graphs.\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "KSJzzdxco0", "reviewer": "Reviewer_2pg5", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper deals with oversquashing in GNNs, that is, when information flows between nodes (receptive field large enough), but is too compressed (squashed) into the (finite) features to be correctly exploited for prediction (because number of neighbors grows exponentially with radius of receptive field).\n\nThe paper has 2 contributions: \n\n- First a key idea, which is that in a rewiring procedure, one can label the added edges differently from the original ones, so that the GNN knows they are \"fake edges\", only here to help propagate information.\n\n- Second, based on spectral gap/graph Laplacian mathematical arguments, they propose a new rewiring algorithm. The rewiring algorithm is inspired from the arguments, but does not guarantee the best rewiring (largest increase in spectral gap) at each step: instead it is approximate, so as to be reasonably cheap (computationally).\n\nBoth these contributions are backed by experiments, comparing with 2 other rewiring methods.", "summary_of_the_review": "The paper is overall good, and if the ideas presented are indeed new, should be published. The 2 contributions seem to be directly applicable, and yet are avenues for future work (improved architectures that well exploit the added edges with new label, and other approximations or schemes for adding edges, in the spirit of increasing the spectral gap).\n\nTechnically and empirically, contributions are somewhat new, in that the rewiring and the way to process are indeed new, but the very idea of rewiring, and the very idea of fighting oversquashing, are not themselves new.", "strength_and_weaknesses": "Weaknesses: \n\n- Section 3 is hard to read, and contains some general theorems in which the proof is in a sense \"disappointing\" (theorem  3): the weight matrices \\Theta used in the proof are trivial (proportional to identity)\n- The experiments are described a bit too succinctly, making it hard to infer exactly how experiments were performed (more details later in the review).\n\nStrengths:\n- the two contributions seem to be genuinely good ideas, with practical added value: the special label for added edges seems to indeed improve accuracy. \n- The rewiring algorithm is not too expensive (actually seems pretty cheap, under some conditions), and also clearly works well (better than the two previous method it's compared to).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "5bwYoxqc9tR", "reviewer": "Reviewer_42Gr", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper investigates the oversquashing phenomenon in Graph Neural Networks from the perspective of graph rewiring methods. The purpose of graph rewiring is to alleviate structural bottlenecks and facilitate the flow of information between more distant nodes. The contribution of the paper is twofold: 1) for any graph rewiring approach, a relational GNN implementation is proposed, which is able to make use of the augmented edge set without forsaking the information contained in the graph topology; 2) First-Order Spectral Rewiring is proposed as an efficient rewiring mechanism, which provides a principled way for selecting edges by maximizing the change (up to first-order approximation) in the spectral gap. In support of 1), a theoretical result is provided, which seems to hint that the proposed R-GNN formalism might be able to make use of the augmented index set without exacerbating a related phenomenon called oversmoothing. Experimental results demonstrate the benefit of both proposed techniques compared to non-relational GNNs and alternative rewiring methods.", "summary_of_the_review": "The paper investigates oversquashing and oversmoothing. It communicates the ideas particularly well. The proposed techniques (R-GNN and FoSR) are novel and original. Some theory is provided to motivate the R-GNN with some open questions at the moment. Experiments demonstrate the benefit of the both techniques with interesting results compared to alternative rewiring approaches and non-relational GNN. Discussion of trade-offs and some theoretical questions would help strengthen the message. As mentioned above, I am looking forward to the authors' rebuttal regarding my questions, which may affect the final rating (in both ways).", "strength_and_weaknesses": "### The paper has several strengths:\n- It is remarkably well-written and the exposition is very clear.\n- The proposed techniques are elegant and innovative, but mostly nontrivial.\n- Theoretical results hint at the benefits of the approach.\n- Detailed experiments demonstrate the benefit of both techniques, individually and also when combined.\n\n### Notable weaknesses:\nOverall, there are some missing points in the discussion which make me a bit unsure about this paper on a second read. Depending on how these points are addressed, I can be incentivized to modify my rating in either direction.\n\n- Missing discussion about spectral gap maximization.\n\nThe paper does a good job at conveying the core ideas from related work without overloading the reader. One thing I was missing is an overview of previous results for why graph rewiring via spectral gap maximization is a worthwhile approach for alleviating oversquashing. Since this seems to be the foundation on which the corresponding FoSR algorithm is built, I think it would go far if there was an intuitive overview of the core idea. \n\n- Theorem 3 does not tell the whole story.\n\nTheorem 3 seems to be a useful result regarding the flexibility of R-GNN. However, I have some doubts whether it tells the full story. Specifically, when the weight matrices $\\Theta_1$ and $\\Theta_2$ are reduced towards zero, the rate of smoothing reduces as the contribution from the direct and indirect neighbours decrease. In the corner case of $\\Theta_1 = \\Theta_2 = 0$, only the self-loops remain with the R-GNN becoming a node-wise linear transformation, and this setting also clearly achieves minimal oversmoothing. However, the structural information is lost in this case as well. In this way, Theorem 3 does not tell the whole story because somehow we are trying to maintain propagation along the important edges while maintaining a low rate of smoothing. It seems there is a missing component here to really guarantee the strength of these R-GNNs in practice. It would be interesting to know more about how this interaction happens with the graph rewiring approach utilized.\n\n- Experiments do not report investigation regarding the realized spectral gap and associated trade-offs.\n\nThe experiments demonstrate improved downstream performance after applying the proposed rewiring approach. On the other hand, no investigation of robustness is carried out in terms of the realized spectral gap itself. I would be curious about the following comparison for the compared rewiring methods: number of rewiring iterations - realized spectral gap - downstream performance. In this case, other model hyperparameters could be treated as fixed. This also connects to the previous point, as it looks like simply maximizing the spectral gap is not sufficient (otherwise we could just choose a larger number of rewirings). Although the R-GNN can learn to reduce oversmoothing, it seems like it's main method for doing so is to effectively eliminate the newly introduced connections, hence making the R-GNN more similar to classic GNN. It seems like we are still somehow trying to balance both phenomenons (oversmoothing and oversquashing) with some added flexibility. For example, how this trade-off happens with respect to the rewiring steps could be investigated and explained in more detail empirically.\n\n- Robustness of FoSR approximation is unexplored.\n\nDuring the derivation of FoSR, several involved calculations are carried out where the spectral gap is approximated (first the order-1 Taylor expansion, and then an asymptotic argument to discard some of the terms from the maximand). Consequently, as with most approximations, there is some error incurred. At the moment, there is no intuition about when (just from the point of view of spectral gap maximization) this rewiring approach is expected to work well, or if it could fail in certain cases. Some discussion would be interesting here.\n\n- Motivation of tools utilized for oversmoothing analysis.\n\nSection 3 first sets the foundation for the theoretical analysis by introducing a carefully chosen set of tools. I found the associated references to be somewhat scarce. The Dirichlet energy associated with the graph is referenced, but I did not see references for the associated rate of smoothing \"metric\". Is this something that the authors propose themselves, or was this used in previous works? In the former case, I think it would be worthwhile to provide a more detailed justification about why this is a good quantity to measure oversmoothing.\n\n\nPOST-REBUTTAL: Rating increased to 8 in view of significant improvements.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster