Locality-Aware Graph Rewiring in GNNs
Authors: Federico Barbero
Ameya Velingker
Amin Saberi
Michael M. Bronstein
Francesco Di Giovanni
Venue: ICLR 2024 poster (2024)
Keywords: Graph Neural Networks
Message Passing Neural Networks
Over-squashing
Graph Rewiring
Primary area: learning on graphs and other geometries & topologies

Abstract: Graph Neural Networks (GNNs) are popular models for machine learning on graphs that typically follow the message-passing paradigm, whereby the feature of a node is updated recursively upon aggregating information over its neighbors. While exchanging messages over the input graph endows GNNs with a strong inductive bias, it can also make GNNs susceptible to over-squashing, thereby preventing them from capturing long-range interactions in the given graph. To rectify this issue, graph rewiring techniques have been proposed as a means of improving information flow by altering the graph connectivity. In this work, we identify three desiderata for graph-rewiring: (i) reduce over-squashing, (ii) respect the locality of the graph, and 
(iii) preserve the sparsity of the graph. We highlight fundamental trade-offs that occur between spatial and spectral rewiring techniques; while the former often satisfy (i) and (ii) but not (iii), the latter generally satisfy (i) and (iii) at the expense of (ii). We propose a novel rewiring framework that satisfies all of (i)--(iii) through a locality-aware sequence of rewiring operations. We then discuss a specific instance of such rewiring framework and 
validate its effectiveness on several real-world benchmarks, showing that it either matches or significantly outperforms existing rewiring approaches.

Published as a conference paper at ICLR 2024
LOCALITY-AWARE GRAPH REWIRING IN GNNS
Federico Barbero'; Ameya Velingker", Amin Saberi', Michael Bronstein', Francesco Di Giovanni'
Michael 'University of Oxford, Department of Computer Science
Google Research
SStanford University, Department of Management Science and Engineering
ABSTRACT
Graph Neural Networks (GNNs) are popular models for machine learning on graphs that typically follow the message- paassing paradigm, whereby the feature of a node is updated recursively upon aggregating information over its neighbors. While exchanging messages over the input graph endows GNNs with a strong inductive bias, it can also make GNNs susceptible over-squashing, thereby preventing them from capturing long-range interactions in the given graph. To rectify this issue, graph rewiring techniques have been proposed as a means of improving information flow by altering the graph connectivity. In this work, we identify three desiderata for graph-rewiring: (i) reduce over wver-squshhin, (ii) respect the locality of the graph, and (iii) preserve the sparsity of the graph. We highlight fundamental trade-offs that occur between spatial and spectral rewiring techniques; while the former often satisfy (i) and (ii) but not (iii), the latter generally satisfy (i) and (iii) at the expense of (ii). We propose a novel rewiring framework that satisfies all of (i)-(ii) through locality
sequence of rewiring operations. We then discuss a specific instance of such rewiring framework and validate its effectiveness on several real-world benchmarks, showing that it either matches significantly outperforms existing rewiring approaches.
INTRODUCTION
Graph Neural Networks (GNNs) (Sperduti, 1993; Goller & Kuchler, 1996; Gori et al., 2005; Scarselli et al., 2008; Bruna et al., 2014; Defferrard et al., 2016) are widely popular types of neural networks operating over graphs. The majority of GNN architectures act by locally propagating information across adjacent nodes of the graph and are referred to as Message Passing Neural Networks (MPNNs) (Gilmer al., 2017). Since MPNNs aggregate messages over the neighbors of each node recursively at each layer, a sufficient number of layers is required for distant nodes to interact through message passing (Barceló et al., 2019). In general, this could lead to an explosion of information that needs to be summarized into fixed-size vectors, when the receptive field of node grows too quickly due to the underlying graph topology. This phenomenon is known as over-squashing (Alon & Yahav, 2021), and it has been proved to be heavily related to topological properties of the input graph such as curvature (Topping et al., 2022) and effective resistance (Black et al., 2023; Di Giovanni et al., 2023).
Since over-squa is a limitation of the message-passing passing paradigm that originates in the topology of the input-graph a solution to these problems is graph rewiring (Topping et al., 2022), in which one alters the connectivity of the graph to favor the propagation of information among poorly connected nodes. Spatial rewiring techniques often connect each node to any other node in its k-hop (Brüel- Gabrielsson et al., 2022: Abboud et al., 2022), or in the extreme case operate over fully-connected graph weighted by attention such as for Graph-Transformer (Kreuzer et al., 2021; Mialon et al., 2021; Ying et al., 2021; Rampasek et al., 2022). Spectral rewiring techniques instead aim to improve the connectivity of the graph by optimizing for graph-theoren quantities related to its expansion properties such as the spectral gap, commute time, or effective resistance (Arnaiz-Rodríguee et al., 2022; Karhadkar et al., 2022; Black et al., 2023).
While graph rewiring a promising direction, it also introduces a fundamental trade-off between the preservation of the original topology and the "friendliness' of the graph to message passing. Spatial rewiring techniques partly preserve the graph-distance information (i.e. its 'locality)) by
"Coresponddnnce Dcdericobbrberoor ac.k...c.k

---

Published as a conference paper at ICLR 2024
SPECTRAL
SPATIAL
LASER
Figure 1: Difference between spectral (left), spatial (middle), and LASER (right) rewirings in green with respect to the blue node of reference. Spectral rewirings are sparse and connect distant nodes. Spatial rewirings able retain local inductive biases the cost of sparsity. LASER remains both local and sparse by optimizing over the edges to be added.
only adding edges within a certain radius or by relying on positional information. However, these methods often result in a dense computational graph that increases memory complexity and cause issues such as over- smoothig (Nt & Maehara, 2019; Oono & Suzuki, 2020; Rusch & Mishra, 2020; Di Giovanni al., 2022). Conversely, spectral rewiring approaches add fewer edges according to some optimization criterion and hence better preserve the sparsity of the input graph. However, these methods 'maximally' destroy the locality induced by the graph since they typically insert very 'long' edges among distant nodes (see Figure 1). The following natural question then arises: Can we design a general graph rewiring framework that leverages the inductive bias of spatial methods but more edge-efficient way characteristic of spectral methods?
Contributions and outline. In this work, we address the above question by proposing general framework for graph-rewiring that improves the connectivity, while preserving locality and sparsity:
In Section 3 we review existing rewiring approaches and classify them as either spatial or spectral, highlighting their limitations. We then provide general list of desiderata for rewiring that amounts to (i) reducing over-squashnn squashius,nn and preserving both (ii) the graph-locality and (iii) its sparsity.
In Section 4 we introduce a paradigm for rewiring that depends on arbitrary connectivity and locality measures. We argue that in order to satisfy (i) (iii) above, a single rewiring is not enough, and instead propose sequential rewiring, where multiple graph snapshots are considered. Building on Karhadkar al. (2022), we also draw an important equivalence between graph-rewiring on one side, and multi-relational GNNs and temporal-GNNi on the other.
In Section 5 we present specific instance of the aforementioned paradigm termed Locality SEquential Rewiring (LASER). Our framework leverages the distance similarly spatial rewiring while also guaranteeing the efficiency of spectral techniques by sampling edges to add according to equivariant, optimal conditions. We show that LASER reduces over-squashing and better preserves the locality of the graph compared spectral rewiring techniques.
In Section 6 we validate LASER on different tasks, attaining performance that is on par or superior existing rewiring techniques. In particular, we present extensive ablation studies to support our claim that LASER is more efficient than spatial methods while being better at preserving graph-distance information in comparison to spectral approaches.
BACKGROUND
Preliminaries on graphs. Let EV,E) an undirected graph with n nodes V and edges E, which are encoded by the non-zero entries of the adjacency matrix A 8= Let D be the diagonal degree matrix such that D d,. We recall that the normalized graph Laplacian 11/2 A)D-AA 1/2 is a symmetric positive semi-definite operator with eigenvalues 0 An < 5 -1 We assume that is connected, that X; > 0 and refer to it as the spectral gap. From the Cheeger inequality, follows that a larger x generally means better connectivity of We finally recall that a random walk on G is a Markov chain on V with transition matrix D 11 A and that the commute time CT is defined the expected number of steps required for random walk to commute between
D-112/()
G. We denote by de (u, v) the shortest path distance between the nodes
2

---

Published as a conference paper at ICLR 2024
two nodes. Note that the commute time (1 u) between two nodes and u is proportional to their effective resistance R(u, u) (Chandra et al., 1996) as (U u) = 2|E|R(e, u).
The message-passingg paradigm. We consider the case where each node has a feature x.: R is common to stack the node features into a matrix x E Rnxd consistently with the ordering of A. GNNs are functions defined on the featured graph that can output node, edge, graph-level values. The most common family of GNN architectures are Message Passing Neural Networks (MPNN), which compute latent node representations by stacking T layers of the form:
x = up (+) (x!!-1) (x (u, u) E EH)),
(I)
for = L..= T, where (+) is some cettuuttttoniiivvrinnn aggregation function, while up(*) updates the node's current state with aggregated messages from its neighbors.
Over-squashing and long-range interactions. While the message-passing paradigm usually constitutes a strong inductive bias, it is problematic for capturing long-range interactions due to phenomenon known as over-squashing. Given two nodes u, at distance de(u, v) = 7, an MPNN will require T 2 r layers to exchange messages between them. When the receptive fields of the nodes expand too quickly (due to volume growth properties characteristic of many real-world scale free graphs), the MPNN needs to aggregate large number of messages into fixed-size vectors, leading to some corruption of the information (Alon & Yahav, 2021). This effect on the propagation of information has been related the Jacobian of node features decaying exponentially with (Topping et al., 2022). More recently, it was shown that the Jacobian is affected by topological properties such as effective resistance (Black et al., 2023; Di Giovanni al., 2023).
3 EXISTING GRAPH- APPROACHES AND THEIR LIMITATIONS
The main principle behind graph rewiring in GNNs is to decouple the input graph G from the computational one. Namely, rewiring consists of applying an operation to (V,E). thereby producing new graph RG) = (V, R(E)) on the same vertices but with altered connectivity. We begin by generalizing the MPNN formalism to account for the rewiring operation R as follows:
(1) : (v, (4x!--); 0 (x!! aG
E E (c) (1x(
(v, u) E R(E))))
(2)
where a node feature is now updated based on information collected over the input graph G and the rewired one RG)), through (potentially) independent aggregation maps. Many rewiring- -aaed GNN models simply exchange messages over RG), i.e., they take ag = 0. The idea of rewiring the graph implicit to many GNNs, from using Cayley graphs (Deac et al., 2022), to virtual nodes (Cai et al., 2023) and cellular complexes (Bodnar et al., 2021). Other works have studied the implications of directly changing the connectivity of the graph to de-noise it (Klicpera et al., 2019), or to explore multi-hop aggregations (Abu-El Abu-El-Haija -aija et al., 2019; Ma et al., 2020; Wang et al., 2020; Nikolentzos et al., 2020). Ever since oqur-squa was identified as an issue in MPNNs (Alon & Yahav, 2021), several novel rewiring approaches have been proposed mitigate this phenomenon.
Related work on spatial rewiring. Most spatial rewiring models attempt to alleviate wer-squashing by adding direct connections between a node and every other node within a certain distance (Brüel- Gabrielsson et al., 2022; Abboud et al., 2022) - with (dense) Graph Transformers being the extreme case (Ying et al., 2021; Mialon et al., 2021; Kreuzer et al., 2021; Rampasek al., 2022). These frameworks follow equation 2, where ag and ( are learned independently, or the former is zero while the second implements attention over a dense graph. Spatial rewiring reduces over-squashing by creating new paths in the graph, thus decreasing its diameter or pairwise effective resistances between nodes. The rewired graph still preserves some information afforded by the original topology in the form of distance-awer aware aggregations in multi-hop GNNs, or positional encoding in Graph- Transformers. A drawback of this approach, however, is that we end up compromising the sparsity of the graph, thereby impacting efficiency. Thus, natural question is whether some of these new connections introduced by spatial rewiring methods may be removed without affecting the improved connectiviry.
We also mention spatial rewiring methods based on improving the curvature of G by only adding edges among nodes distance most two (Topping et al., 2022; Nguyen et al., 2022). Accordingly,
3

---

Published as a conference paper at ICLR 2024
these models may fail significantly improve the effective resistance of the graph unless large number of local edges is added.
Related work spectral rewiring methods. A different class of ap- proaches consist of rewiring the graph based on a global spectral quantity rather than using spatial distance. Two prototypical measures that have been explored this regard are spectral gap (Karhadkar et al., 2022) and effective resistance Aamaiz-Rodrígie been shown that node is mostly insensitive to information contained at nodes that have high effective resistance (Black et al., 2023; Di Giovanni et al., 2023); accordingly, spectral rewiring approaches alleviate over-squashing by reducing the effective resistance. Moreover, they achieve that adding only a few edges by optimally increasing the chosen measure of connectivity, hence maintaining the sparsity level of the input graph. However, the edges that are added in the graph typically end up connecting very distant nodes (since the distance between two nodes is at least as large as their effective resistance), hence rapidly diminishing the role of locality provided by distance on the original graph.
Table I: Properties of different types of rewirings.
Property
Spatial
Spectral
LASER
Reduce over-squashing
/
Preserve locality
X
/
Preserve sparsity
et al., 2022; Banerjee et al., 2022; Black et al., 2023). It has recently
An ideal rewiring approach. Given a graph G, an ideal rewiring map R should satisfy the following desiderata: (i) Reduce over-squashing: R. increases the overall connectivity of G G- according to some topological measure - in order to alleviate over-squashing; (ii) Preserve locality: R preserves some inductive bias afforded by G. c.g., nodes that are "distant" should be kept separate from nodes that are closer in the GNN architecture; (iii) Preserve sparsity: R. approximately preserves the sparsity of G, ideally adding a number of edges linear in the number of nodes. While condition (i) represents the main rationale for rewiring the input graph, criteria (ii) and (iii) guarantee that the rewiring is efficient and do not allow the role played by the structural information in the input graph to degrade too much. As discussed above and summarized in Table 1, spatial methods typically satisfy only (i) and (ii), but not (iii), while spectral- methods meet (i) and (iii) but fail (ii).
Main idea. Our main contribution is a novel paradigm for graph rewiring that satisfies criteria (i)- leveraging key principle: instead of considering single rewired graph RRG). we use a sequence of rewired graphs (Re(G) such that for smaller f, the new edges added in (G) are more 'local' (with respect to the input graph G) and sampled based on optimizing a connectivity measure.
A GENERAL PARADIGM: DYNAMIC REWIRING WITH LOCAL CONSTRAINTS
In this Section, we discuss a general graph-rewiring paradigm that can enhance any MPNN and satisfies the criteria (i)-(ii) described above. Given a graph G, consider a trajectory of rewiring operations Re, starting at Go G. of the form:
R.
G1 R2
Ri
G Go
GL.
(3)
Since we think of Gy the input graph evolved along dynamical process for l iterations, we refer to G as the E-snapshot. For the sake of simplicity, we assume R, = R, though it is straightforward to extend the discussion below the more general case. In order to account for the multiple snapshots, we modify the layer form in equation 2 as follows:
x (t) = (0)
x (t, (a (fx(--)) (v, E B. o
(4)
Below we describe a rewiring paradigm based on an arbitrary connectivity measure p.: V x - R and locality measure V x - R.. The measure μ can be any lopological quantity that captures how easily different pairs of nodes can communicate in graph, while the measure y is any quantity that penalizes interactions among nodes that are 'distant' according to some metric on the input graph. In nutshell, our choice of R samples edges add according to the constraint v, prioritizing those that maximally benefit the measure μ. By keeping this generality, we provide a universal approach to do graph-rewiring that can be of interest independently of the specific choices of μ and
4

---

Published as a conference paper at ICLR 2024
Improving connectivity while preserving locality. The first property we demand of the rewiring sequence is that for all nodes U, u, we have JG,,,1 (u. u) 2 fA,, (v, u) and that for some nodes, the inequality is strict. If connect all pairs of nodes with low pı-valu, however, we might end up adding non-local edges across distant nodes, hence quickly corrupting the locality of G. To avoid this, constrain each rewiring by requiring the measure
take values in certain range Ig [0, oo):
an edge (v, u) appears in the f-snapshot (for 1 S l < L) according to the following rule:
(u,u) E E if (HG.(1, u) < e and VG., (v, E Ie) or (v, u) E Ex-1-
(5)
To make the rewiring more efficient, the connectivity and locality measures are computed once over the input graph Go. Since the edges to be added connect nodes with low y-values, the rewiring makes the graphs G. friendlier to gressage-passing as I grows. Moreover, by taking increasing ranges of values for the intervals It, we make sure that new edges connect distant nodes, as specified by v. only at later snapshots. Sequential rewiring allows us to interpolate between the given graph and one with better connectivity, creating intermediate snapshots that progressively add non-local edges. By accounting for all the snapshots G2 in equation 2, the GNN can access both the input graph, and more connected ones, at a much finer level than 'instantancous' rewirings, defined next.
Instantancous vs sequential rewiring. As discussed in Section 3, existing rewiring techniques particularly those of the spectral type- - often consider the simpler trajectory Go + R(Go) == G₁ ("instantaneous rewiring"). The main drawback of this approach is that in order to improve the connectivity in a single snapshot, the rewiring map R is bound to either violate the locality constraint v, by adding edges between very distant nodes, compromise the graph-sparsity by adding large volume of (local) edges. In fact, if that were not the case, we would still be severely affected by over-squashing. Conversely, sequential rewiring allows smoother evolution from the input graph Go to configuration Gr, which is more robust to over-squashing, so that we can more ceasly preserve the inductive bias afforded by the topology via local constraints under equation 5.
An equivalent perspective: multi-relational GNNs. In Karhadkar et al. (2022) the notion of relational rewiring was introduced for spectral methods. We expand upon this idea, by noticing that the general, sequential rewiring paradigm described above can be instantiated as family of multi-relational GNNs (Battaglia al., 2018; Barcelo et al., 2022). To this aim, consider a slightly more specific instance of equation 4, which extends common MPNN frameworks:
(t)
up (x
Σ dF (8) (x(1-1) !))
(6)
(v.a)EE,
where w/ are learnable message functions depending on both the layer t and the snapshot f. It suffices now to note that each edge set E,, originated from the rewiring sequence, can be given its own relation, so that equation 6 is indeed equivalent to the multi-relation GNN framework of Battaglia et al. (2018). In fact, since we consider rewiring operations that only add edges to improve the connectivity, we can rearrange the terms and rename the update and message-fune funcction maps, so that we aggregate over existing edges once, and separately over the newly added edges i.e. the set Eg \. Ez-1- Namely, we can rewrite equation 6 as
(1) up
x 1t)
Σ (O,
(x!
(t- 1)
(t-1)) 11)
+
Σ
(10 (x0(xx) 1x,--,,,x-01)) 1)) (7)
1=1
(E,w)EE/
Accordingly, we see how our choice of sequential rewiring can be interpreted as an extension of relational rewiring in Karhadkar et al. (2022), where L 1. Differently from Karhadkar et al. (2022), the multiple relations f 2 1 allow us to add connections over the graph among increasingly less local nodes, meaning that the edge-type i now associated to notion of locality specified by the choice of the constraint v(v, u) E It. We finally observe that the connection between graph-rewiring and relational GNNs is not surprising once we think of the sequence of rewiring in equation 3 as snapshots of temporal dynamics over the graph connectivity. Differently from the setting of temporal GNNs (Rossi et al., 2020) though, here the evolution of the connectivity over time is guided by our rewiring procedure rather than by intrinsic law on the data. In fact, Gao & Ribeiro (2022) studied the equivalence between temporal GNNs and static multi nultiorelational GNNs, which further motivate the analogy discussed above.
5

---

Published as a conference paper at ICLR 2024
5 LOCALITY-AWARE SEQUENTIAL REWIRING: THE LASER FRAMEWORK
We consider an instance of the outlined sequential rewiring paradigm, giving rise to the LASER framework used in our experiments. We show that LASER (i) mitigates over-squashing, (ii) preserves the inductive bias provided by the shortest-walk distance on better than spectral approaches, while (iii) being sparser than spatial-rewiring methods.
The choice of locality. We choose v to be the shortest-walk distance dG. In particular, if in equation 5 we choose intervals Iz 5,+1, then at the E-snapshot G. we only add edges among nodes at distance exactly & + 1. Our constraints prevent distant nodes from interacting at earlier snapshots and allows the GNN to learn message functions the in equation 7 for each hop level E. If we choose Eg E to be the set of all edges connecting nodes whose distance is exactly E + 1, then equation 7 equivalent to the L-hop MPNN class studied in Feng et al. (2022). This way though, we generally lose the sparsity of G and increase the risk of over- wver-smoothing Accordingly, we propose to only add edges that satisfy the locality constraint and have connectivity measure 'small' so that their addition is optimal for reducing over-squashing.
The choice of the connectivity measure μ.. Although edge curvature or effective resistance R are related to over-squashing (Topping et al., 2022: Black et al., 2023; Di Giovanni et al., 2023), computing these metrics incur high complexity - O ([E]daas)) for the curvature and (n²)) for R.
Because of that, we propose more efficient connectivity measure:
( u)= := (A Vuu A
(8)
Because of the self-loops, the entry (A*) you equals the number of walks from v to of length at most k. Once we fix a value k. if pu:(;; u) is large, then the two nodes v, u have multiple alternative routes to exchange information (up to scale k) and would usually have small effective resistance. In particular, according to Di Giovanni et al. (2023, Theorem 4. I), we know that the number of walks among two nodes is proxy for how sensitive pair of nodes is to over-squashing.
LASER focus. We can now describe our framework. Given a node v and snapshot G2, we consider the set of nodes at distance exactly f+1 1 from v. which we denote by NN++1() We introduce a global parameter E (0, 1] and add edges (with relation type E as per equation 7) among v and the fraction of nodes in Ne+1 (v) with the lowest connectivity score if this fraction is smaller than one, then we round it to one. This way, we end up adding only a percentage p of the edges that a normal multi- -hop GNNs would have, but we do so by prioritizing those edges that improve the connectivity measure the most. To simplify the notations, we let N (w) C CN441 (v), be the p-fraction of nodes at distance E++ from v, where Pe in equation 8 takes on the lowest values. We express the uppatee of LASER as
L
(1) = (!) x 11-1)
Σ (O,N)EE
(t) (x(1-1 (11 wo (x!
Σ
1/ (x((xx
(x((-)))xx!--))
x ))
(9)
E=1 KENP (t)
We note that when p == O, equation (9) reduces to a standard MPNN on the input graph, while for p = 1 we recover multi-relational L-hop MPNNs (Feng et al., 2022). Although the framework encompasses different choices of the message-functionn the, in the following we focus the LASER-GCY variant, whose update equation is reported in Appendix (Section A).
We now show that the LASER framework satisfies the criteria (i)-(ii) introduced in Section 3. Let ((r) (v. u) == /0x!0) be the Jacobian of features after layers of GCN on G, and similarly we let j(r (v. u) be the Jacobian of features after r layers of LASER-GCH in equation 10. In the following, we take the expectation with respect to the Bernoulli variable ReLU" which is assumed to have probability of success p for all paths in the computational graph as in Xu et al. (2018); Di Giovanni et al. (2023). We recall that given E V and 1 S l < L, di,t enters equation 10.
Proposition 5.1. Let v, u E V with de (c(v, (U, u) = r, and assume that there exists a single path of length r connecting and u. Assume that LASER adds an edge between and some node belonging to the path of length r connecting e to u, with de (v()) = E < r. Then for all m S r, we have
(d
[ (v. w)ll
[[ (v, u)]ll-
Vdr,
6

---

Published as a conference paper at ICLR 2024
The result is not surprising and shows that in general, the LASER- rewiring improve the Jacobian sensitivity significantly and hence alleviates squsshuu,,,, satisfying desideratum (i). Next, we validate that the effects of the local constraints when compared to unconstrained, global spectral methods. Below, we let DE be the matrix of pairwise distances associated with the graph G, i.e. (DG)vu da u). We propose to investigate iDG DR(G)) r. where || ||r is the Frohenius norm and R(G) is either baseline spectral rewiring, our -faae--ra..ork. We treat this quantity as a proxy for how well a rewiring framework is able to preserve the inductive bias given by the input graph. In fact, for many graphs (including molecular-type with small average degree), spectral rewirings incur a larger Frobenius deviation even if they add fewer edges, since these edges typically connect very distant nodes in the graph. To this aim, we show a setting where LASER preserves more of the locality inductive bias than spectral- based methods provided we choose the factor P small enough. Below, we know to be a worst-case scenario for over-squashine squashing considering that the commute time scales cubically in the number of nodes. Put differently, the graph below represents a prototypical case of "bottleneck" encountered when information has to travel from the end of the chain to the clique.
focus on a case that, according to Di Giovanni et al. (2023); Black al. (2023),
Proposition 5.2. Let G be 'lollipop' graph composed of a chain of length L attached to a clique of size nt sufficiently large. Consider a spectral rewiring R which adds an edge between nodes with the highest effective resistance. We can choose the factor p E (0, 1) as a function of so that LASER with single snapshot, on average, adds number of edges that guarantees:
D|D - F 2 || - DLASER |FF-
We refer to the Appendix (Section A) for explicit characterization on how large needs to be depending on L and the proofs of the statements stated above. Finally, as desired in (iii), we observe that compared to dense multi-hop GNNs, LASER is more efficient since it only adds a fraction p of edges for each node u and each orbit-level (w). In fact, for many sparse graphs (such as molecular ones) the model ends up adding number of edges proportional to the number of nodes (see Section C.2 in the Appendix for a discussion and ablations).
EXPERIMENTS
In this section, we validate our claims on range of tasks and benchmarks. Beyond comparing the performance of LASER to existing baselines, we run ablations to address the following important questions: (1) Does LASER improve the graph's connectivity? (2) Does LASER preserve locality information better than spectral rewiring approaches? (3) What is the impact of the fraction of edges sampled? (4) What if we sample edges to be added from N (v) randomly, rather than optimally according to μ in equation 8? (5) Is LASER scalable to large graphs? In the Appendix (Section C). we provide a density comparison between LASER and Multi-Hop GNNs, discuss our tie-breaking procedure that guarantees cquivariance in expectation and further improves performance, provide an ablation using different underlying MPNNs, and discuss additional motivation for the need for locality. We also provide, in Section D, more thorough scalability analysis.
Benchmarks. We evaluate on the Long Range Graph Benchmark (LRGB) (Dwivedi et al., 2022)
Table 2: Results for the Peptides-func, and PCQM-Contact datasets. Performances are Average Precision (AP) (higher is better), Mean Absolute Error (MAE) (lower is better), and Mean Reciprocal Rank (MRR) (higher is better), respectively.
soptides-strunn
and TUDatasets (Morris et al., 2020). In the experiments, we fix the underlying model GCN, but provide ablations with differ- ent popular MPNNs in the Ap- pendix (Section C.3). For spatial curvature-bart based rewirings, we com- pare against SDRF (Topping et al., 2022) and BORF (Nguyen et al., 2023). For spectral techniques, we compare against FOSR (Karhadkar al., 2022), spectral gap rewiring technique, and GTR (Black et al., 2023), an effective resistance rewiring technique. We also compare to DiffWire
Rewiring
Pept i deddde---fnm
Papt des-sst
PCOM-Contact.
Test AP f
Test MAE J
Test MRR
None
0.5930--0.0023
0.3496
1.3234-0.0000
SDRF
0,5947110.00 0035
0.3404-10.000
0.324920.0006
GTR
0.5075++0.0029
0,3618=40.0011
0.0007-0.0022
FOSR
0.5947:+0.0027
0.3078:10.008
0.2783-0.0008
BORF
0.6012:10.0311
0.337410.0011
TIMBOUT
LASER
0.6440+:0.0010
0.0049
0.3275-0.001
al., 2022), a differentiable rewiring technique.
7

---

Published as a conference paper at ICLR 2024
Based on Karhadkar et al. (2022) and the parallelism we draw between rewiring and multi-relational GNNs, for all techniques, we report results tuned over both a 'standard' and relational (Schlichtkrull et al., 2018) model for the baselines, where we assign original and rewired edges distinct relational types. In particular, R-GCN in these cases is then a special instance of equation 2. For additional details on the tasks and
we refer to the Appendix (Section B).
LRGB. We consider the Peptides (15535 graphs) and PCQM-Conten (529 434 graphs) datatsets, from the Long Range Graph Benchmark (LRGB). There are two tasks associated with Peptides, peptide function classification task Pept seeciide--ur and peptide structure regres- sion task Peptides struct. PCOM-Contact predict pairs of distant nodes that will be adjacent in 3D space. We replicate the experimental settings from Dwivedi et al. (2022), with 5-layer MPNN for each of the rewirings as the underlying model. We choose the hidden dimension in order to respect the 500k parameter budget. In Table 2, we report the performance on the three tasks. LASER convincingly outperforms all baselines on the three tasks, while the other rewiring baselines frequently perform worse than the standard GCN model. On PCOM-Contase act, the rewiring time for BORF surpasses the 60 hour limit enforced by Dwivedi et al. (2020) our hardware, so we assign it a TIMEOUT score.
a link-prediction task, in which the goal is to
TUDatasets. We evaluate LASER on the REDDIT-BINARY, IMDE-BINARY, MUTAG, ENZ PROTEINS, and COLLAB tasks from TUDatasets, which were chosen by Karhadkar et al. (2022) under the claim that they require long-range interactions. We evaluate on 25 random splits, fixing the hidden dimension for all models to 64 and the number of layers 4, as in Karhadkar et al. (2022). We avoid the use of dropout and use Batch Norm (Ioffe & Szegedy, 2015). We refer to the Appendix (Section B.2) for further details on the drawbacks of these tasks. Table 3 shows the results on the aforementioned benchmarks. LASER most consistently achieves the best classification accuracy, attaining the highest mean rank.
and a discussion on some
Table 3: Accuracy + std over 25 random splits for the datasets and rewirings. Colors highlight First, Second, and Third; we report the mean rank achieved on the valid runs OOM is Out of Memory.
Rewiring
REDDIT-D
IMDB- BINARY
NUIAG
ENZYMBG
PROTEING
COLLAB
Mcan Rank
None
81.000=2.777
1,9990-:1.990
74.737:55955
28.733=55.2 297
2.200
68 68.960:2222844
1,83
DiflWire 00M
59.000+13.847
80,421:1..777
28.533=#4.475
72.7141:2.946
65.440::-2.177
4,83
GTR
25.700::2.786
52.560-144 104
78.632:16.201
26.333::5.821
72.303-14..558
68.024:1:..29
4.67
SDRF
81.420=2.7785
$8.290-::.201
74.526=55.355
30.567:26.188 188
68.714:b42255
70.222::2.571
4,50
POSR
2.99999
60.40011..885
75 895-17.211
28, 28.600-55.253
71.643-33.428
10.848:13.488
3.67
BORF
84.920
60.8204338877
81.684 964
30.50026.593
68.111144112
0OM
3.60
LASER
85.458:228827
64.333-3.229
82.204:6.7228
34.33326:936
74.381
70.923::2.338
1.37
Ablation studies. In the following, we choose FOSR as a typical spectral rewiring approach, while taking LASER with p 1 as instance of a dense, multi-hop GNN (i.e. classical spatial rewiring). For the purpose of these ablations, we conduct experiments on the Pept investigating questions (1) and (2), namely, how well LASER improves connectivity while respecting locality. To this end, we increment the number of snapshots from 2 to given densities p p= 0.1 and p 1 for LASER and instead vary the number of edge additions of FOSR spanning the values 10, 20, 50, and 100. To assess the connectivity, we report the mean total effective resistance - which is a good proxy for over-squashing (Black al., 2023; Di Giovanni et al., 2023) while for the locality, we evaluate the norm of the difference between the original graph distance matrix and that of the rewired graph ||DG - DRoGY || as per Proposition 5.2. Figure 2 shows the results of this ablation. We validate that the sparse LASER framework decreases the mean total effective resistance consistently over increasing snapshots as well as other rewiring techniques. Moreover, we find that LASER with p = 0.1 is better than dense spatial methods and especially surpasses spectral approaches at preserving information contained in the distance matrix.
dataset. We start by
Next, we investigate question (3), i.e. the impact of the fraction & of edges being sampled, by
Table 4: Comparison between LASER and random sampling, with L 3 and p 0.1.
increasing the number of snapshots from 2 to 5
and varying the density ranging 0.1, 0.25, 0.5,
Model Pept Funne-ureffe Peptides-sttuct 4
and 1, with results reported in Figure 3. The
Random
0.4796=0.0067
0.338240.0019
majority of the performance gains are obtained throuhh a sparse rewiring, as even with p = 0.1
LASER
0.6014-0.0020
0.3119
8

---

Published as a conference paper at ICLR 2024
Total Effectivs Resistance
Graph Distance
Peptidoo--unc
Poptides-struct
0.60
0.30
250K
Total Ellecie Bosstanes
0.35
200K-
Gooh Detance
3.5K
0.00
0.34
150K
3.CK
0.64
0.33
0:57
100K
2.5K
0.31
50K
2.0K
0K
7/10
3,20
4,50
5/100
1.5K
3,70
4/50
5/100
0.58
0.1
0.25
0.5
0.10
0.50
1.00
Snapahorau ip of Rowined Edgex
Denaty
Rowiingg Methods
Namber of Snapehuts
LASER p
LASER
FOSR
Bassine
Figure 2: Total effective resistance and graph distance, as measured by the Frobenius norm, when varying the number of snapshots from 2 to and from 0.1 to
Figure 3: Performance on the Pept ides tasks when varying the number of snapshots from 2 to and p from 0.1 to 1. The baseline indicates a standard GCN model.
the performance is greatly increased over the baseline. The additional density in the orbits does seem to help with performance, but this comes at the cost of density.
Finally, we address question (4), by evaluating how sampling edges uniformly over the nodes at distance & ++1 given density p. compares our choice of prioritizing edges with lowest connectivity score jt as per equation 8. We report the results in Table 4. We see that LASER greatly outperforms the random rewiring, verifying our claim that guiding the rewiring through l is more sound approach.
Scalability. The operations required to compute and in LASER are designed to be efficiently implemented on modern hardware accelerators, mostly relying on matrix multiplication. Furthermore, the rewiring operation is done once and stored for future runs. The p factor can be tuned to calibrate the density of the rewiring, giving further control on the training efficiency. LASER does not seem to significantly impact the run-time compared to the standard baseline models and we found through synthetic benchmarking experiment that our implementation of LASER is able to rewire graphs with 100k nodes and million edges in 2 hours. This is in contrast to FOSR and SDRF that failed finish the computation within 24 hours. We report large number of benchmarking experiments, alongside a theoretical complexity analysis in the Appendix (Section D).
7 CONCLUSION
In this work, we have identified shortcomings of rewiring techniques and argued that a rewiring must: (i) improve connectivity, (ii) respect locality, and (iii) preserve sparsity. Unlike current spectral and spatial rewirings that compromise some of these properties, we have outlined a general rewiring paradigm that meets criteria (i) (iii) by interpolating between the input graph and a better connected one via locally constrained sequential rewiring. We have then proposed a specific instance this paradigm - LASER and verified, both theoretically and empirically, that it satisfies (i)-(iii).
Limitations and Future Work. In this paper, we considered simple instance of the general rewiring paradigm outlined in Section 4, but we believe that an interesting research direction would be explore alternative choices for both the connectivity and locality measures, ideally incorporating features in a differentiable pipeline similar to Arnaiz-Rodrigues et al. (2022). Furthermore, the identification between graph-rewiring on the one hand, and multi-relational GNNs and temporal- GNNs on the other, could lead to interesting connections between the two settings, both theoretically (e.g., what is the expressive power a certain rewiring policy?) and practically, where techniques working in one case could be effortlessly transferred to the other. Finally, we highlight that, as customary in rewiring approaches, it is always hard to pinpoint with certainty the reason for any performance improvement, including whether such improvement can be truly credited to ouur-iiua and long-range interactions. We have tried to address this point through multiple ablations studies.

---

Published as a conference paper at ICLR 2024
8 ACKNOWLEDGEMENTS
FdG, FB, and MB are partially supported by the EPSRC Turing AT World-Leading Research Fellow- ship No. EP/X040062/1. We would like to thank Google Cloud for kindly providing computational resources for this work.
REFERENCES
Ralph Abboud, Radoslav Dimitrov, and Ismail Ilkan Ceylan. Shortest path networks for graph property prediction. In The First Learning on Graphs Conference, 2022. URL https:// openreview net wtrufoormmii weruumiddm@aaiiwauus
Sami Abu-EI-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg. and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In international conference machine learning. pp. 21-29. PMLR, 2019.
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations, 2021.
Adrián Almaiz-Rodriguee Ahmed Begga, Francisco Escolano, and Nuria Oliver. DiffWire: Inductive Graph Rewiring via the Lovász Bound. In The First Learning on Graphs Conference, 2022. URL
https: / /ttpppppeevvieeeeeeeeeeeeeeeeeee net /ptff/fff// ?
Pradeep Kr Banerjee, Kedar Karhadkar, Yu Guang Wang, Uri Alon, and Guido Montúfar. Over- squashing in gnns through the lens of information contraction and graph expansion. In Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 1-8. IEEE, 2022.
Pablo Barceló, Egor V Kostylev, Mikael Monet, Jorge Pérez, Juan Reutter, and Juan Pablo Silva. The logical expressiveness of graph neural networks. In International Conference on Learning Representations, 2019.
Pablo Barcelo, Mikhail Galkin, Christopher Morris, and Miguel Romero Orth. Weisfeiler and leman go relational. In The First Learning on Graphs Conference, 2022. URL https:: net/ / forum? wediidwwwwi___ IYhh TYhh6pqi.........
Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. 2018
Mitchell Black, Zhengehao Wan, Amir Nayyeri, and Yusu Wang. Understanding oversquashing in gnns through the lens of effective resistance. In International Conference Machine Learning, pp. 2528-2282222 2247. PMLR, 2023.
Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yuguang Wang, Pietro Lio, Guido F Montufar, and Michael Bronstein. Weisfeiler and lehman go cellular: Cw networks. In Advances in Neural Information Processing Systems, volume 34, pp. 2625-2640, 2021.
Rickard Brbii-Gan,,,lsson, Mikhail Yurochkin, and Justin Solomon. Rewiring with positional encodings for graph neural networks. arXiv preprint arX1v:2201.12674. 2022.
Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. In International Conference on Learning Representations, 2014.
Chen Cai, Truong Son Hy, Rose Yu, and Yusu Wang. On the connection between mpnn and graph transformer. arXiv preprint arXiv:2301. 11956, 2023.
Ashok Chandra, Prabhakar Raghavan, Walter Ruzzo, Roman Smolensky, and Prasoon Tiwari. The electrical resistance of graph captures its commute and cover times. computational complexity, 6 (4):312-340, 1996.
Andreea Deac, Mare Lackenby, and Petar Veličković. Expander graph propagation. In The First Learning on Graphs Conference, 2022.
10

---

Published as a conference paper at ICLR 2024
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks graphs with fast localized spectral filtering. In Advances in neural information processing systems, volume 2016.
Francesco Di Giovanni, James Rowbottom, Benjamin P Chamberlain, Thomas Markovich, and Michael M Bronstein. Graph neural networks as gradient flows. arXiv preprint arXiv:2206.1099 2022.
Francesco Di Giovanni, Lorenzo Giusti, Federico Barbero, Giulia Luise, Pietro Lio, and Michael Bronstein. On over-squashing in message passing neural networks: The impact width, depth, and topology. arXiv preprint arXiv:2302.02941 2023.
Vijay Prakash Dwivedi, Chaitanya K. Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. abs/2003.00982, 2020.
Vijay Prakash Dwivedi, Ladislav Rampášek, Michael Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. Long range graph benchmark. Advances in Neural Information Processing Systems, 35:22326-22340, 2022.
Jiarui Feng, Yixin Chen, Fuhai Li, Anindya Sarkar, and Muhan Zhang. How powerful are k-hop message passing graph neural networks. 2022.
Jianfei Gao and Bruno Ribeiro. On the equivalence between temporal and static equivariant graph representations. In International Conference on Machine Learning, pp. 7052-7076. PMLR, 2022.
Justin Gilmer, Samuel Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International Conference Machine Learning, pp. 1263-1272. PMLR, 2017
Christoph Goller and Andreas Kuchler. Learning task desk-dependent distributed representations by backpropagation through structure. In Proceedings of International Conference on Neural Networks (ICNN'96), volume 1, pp. 347-352. IEEE, 1996.
Marco Gori, Gabriele Monfardini, and Franco Scarselli. A new model for learning in graph domains. In Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005., volume pp. 729-734. IEEE, 2005.
W. L. Hamilton, R. Ying. and J. Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, pp. 1025-1035, 2017.
S. loffe and C. Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference on machine learning, pp. 448-456. PMLR, 2015.
Kedar Karhadkar, Pradeep Kr Banerjee, and Guido Montúfar. Fosr: First-order spectral rewiring for addressing oversquashing in gnns. arXiv preprini arXiv:2210.117900, 2022.
D. Kingma and J. Ba. Adam: A method for stochastic optimization. 2015.
Thomas N. Kipf and Max Welling. Semi-Supervised Classification with Graph Convolutional
Networks. In International Conference Learning Representations, 2017.
Johannes Klicpera, Stefan Weissenberger, and Stephan Günnemann. Diffusion improves graph learning. Advances in Neural Information Processing Systems, 2019. 2019.
Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourneau, and Prudencio Tossou. Re- thinking graph transformers with spectral attention. In Advances in Neural Information Processing Systems, volume 34, pp. 21618 22669,, 2021.
Zheng Ma, Junyu Xuan, Yu Guang Wang, Ming Li, and Pictro Liò. Path integral based convolution and pooling for graph neural networks. In Advances in Neural Information Processing Systems, volume 33, pp. 16421-16433 2020.
Grégoire Mialon, Dexiong Chen. Margot Selosse, and Julien Mairal. Graphit: Encoding graph structure in transformers. CoRR, abs/2106.05667, 2021.

---

Published as a conference paper at ICLR 2024
Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. 0bs/2007.08663. 2020. URL httts::/arxiv..oot
abs /200000663...
Khang Nguyen, Tan Nguyen, Nhat Ho, Khuong Nguyen, Hieu Nong, and Vinh Nguyen. Re- visiting over-smoothing and over-squashing using ollivier's ricci curvature. arXiv preprint arXiv:2211.15779, 2022.
Khang Nguyen, Nong Minh Hieu, Vinh Duc Nguyen. Nhat Ho, Stanley Osher, and Tan Minh Nguyen. Revisiting smootsngg and over-squashing using ollivier-ricci curvature. In International Conference on Machine Learning, pp. 25956925979. PMLR, 2023.
Giannis Nikolentzos, George Dasoulas, and Michalis Vazirgiannis. k-hop graph neural networks. Neural Networks, 550:195-205, 2020.
Hoang Nt and Takanori Maehara. Revisiting graph neural networks: All we have is low-pass filters. 2019.
arXiv preprint
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In International Conference on Learning Representations, 2020.
Ladislav Rampasek, Mikhail Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Do- minique Beaini. Recipe for general, powerful, scalable graph transformer. In Advances in Neural Information Processing Systems, 2022.
Emanuele Rossi, Ben Chamberlain, Fabrizio Frasca, Davide Eynard, Federico Monti, and Michael Bronstein. Temporal graph networks for deep learning dynamic graphs. arXiv:2006. 10637, 2020.
T Konstantin Rusch and Siddhartha Mishra. Coupled oscillatory recurrent neural network (cornn): An accurate and (gradient) stable architecture for learning long time dependencies. arXiv preprint arXiv:2010.00951, 2020.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1):61-80, 2008
Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In The Semantic Web: 15th International Conference, ESWC 2018, Heraklion, Crete, Greece, June 3-7, 2018, Proceedings 15, pp. 593-607. Springer, 2018
Alessandro Sperduti. Encoding labeled graphs by labeling raam. In Advances Neural Information Processing Systems, volume 6, 1993.
Jan Tönshoff, Martin Ritzert, Eran Rosenbluth, and Martin Grohe Where did the gap go? reassessing the long-range graph benchmark. arXiv preprint (xXix2330900066) 2023.
Jake Topping, Francesco Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. In International Conference on Learning Representations, 2022.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
Guangtao Wang, Rex Ying, Jing Huang, and Jure Leskovec. Multi-hop attention graph neural network. arXiv preprint arXiv:2009. 143.:33209..423,,,. 2020.
K. Xu, W. Hu, J. Leskovee, and Jegelka. How powerful are graph neural networks? In International Conference Learning Representations, 2019.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International Conference Machine Learning, pp. 5453-5462. PMLR, 2018.
12

---

Published as a conference paper at ICLR 2024
Chengxuan Ying. Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie- Yan Liu. Do transformers really perform badly for graph representation? In Advances in Neural Information Processing Systems, volume 34, pp. 28877-28888, 2021.
13

---

Published as a conference paper at ICLR 2024
A ADDITIONAL DETAILS ON THEORY AND FRAMEWORK
In this Section, we report additional considcrations about our framework and provide proofs for the theoretical results stated in Section 5.
First, we report the variant of GCN-LASER to make things more concrete:
ReLU
E
(1)
Σ Σ
x2 (10)
vd.du
{=1 (0) Viuieduue
(ENG())U(O)
where W for 0 < S L, are learnable weight matrices, while di,e is equal to the degree induced by the distance matrix associated with the value f, for each node i E V. We base most of our evaluation on the model in equation 10.
Proposition A.1. Let u, E V with dc(u, u) =r, and assume that there exists single path of length r connecting and Assume that LASER adds an edge between and some node belonging to the path of length connecting u to u, with dc(v. = E < r. Finally, assume for simplicity that all products of weight matrices have unit norm. Then for all m S r, we have
(dmia)²
| (v, (v, w)ll 2 Vdn, 1dja-1
EEJ (m)) (v, u)]l
Proof. We first that extending the result to arbitrary weight matrices is trivial, since one would just obtain an extra factor in the lower bound of the form w"- (//4++//ww]]))) /(=""" depending on the spectral bounds (i.e. singular values bounds) of the weight matrices entering LASER -GCN and GCN, respectively.
Following the assumptions, we can argue precisely as Xu al. (2018) and Di Giovanni et al. (2023, Section 5) and write the Jacobian of node features after m layers of GCN (Kipf & Welling, 2017) as
(m) (1, (v, = P II W (k) (À Jous
k=1
where Á A= D 1/2 is the symmetrically normalized adjacency matrix. In particular, can then estimate the norm of the Jacobian matrix simply by:
[ (u, will = pll II
w (8) ((A))))))))) p(AA))
k=1
where we have used our simplifying assumption on the norm of the weights. In particular, since de (v, u) r, if m I r then the term above vanishes which satisfies the lower bound in the claim. Let us then consider the case m = r. We can write the unique path of length r connecting e and u as a tuple (v, ui...., Up- u), so that
| [ (m)) (v, w)]l =
Vd.d
d
s=1
Similarly, given our LASER -GCN framework in equation 10 and the assumptions, we can bound the norm of the expected Jacobian
[a (1) (v, x)]ll
pll
II 1=
w W (1) (A
pl ((Ar-1)og(A" (Am-))))
Dou.
where (Ae) 1/ dd.ed as defined in equation 10 if de (i, l and zero otherwise. If now take the ratio of the two expected values, we can bound them from below as
[E w)ll (A--1)e;
(Ám-1)
(dmin))
E (e x)]l
Vdo,e-dd,e-1
Vd.
where we have used that by assumption there must exist only one path length m E from j to u, which has same degrees (d.).
14

---

Published as a conference paper at ICLR 2024
Proposition A.2. Let G be a 'lollipop' graph composed of a chain of length L attached to clique of size nt sufficientty large. Consider a spectral rewiring R which adds an edge between nodes with the highest effective resistance. We can choose the factor p (0, 1) as a function of L so that LASER with single snapshot, on average, adds a number of edges that guarantees:
|IDG - DR(G))le 2 1|D6 DLASER FF-
Proof. Let denote the end node of the chain by while is the node belonging to both the chain and the clique, and u be any node in the interior of the clique. It is known that the commute time between and scales cubically in the total number of nodes (Chandra et al., 1996), so algorithm aimed at minimizing the effective resistance will add an edge between v and a point in the interior of the clique which we rename without loss of generality. Accordingly, the distance between and any point in the interior has changed by at least (L + 1) 2. Besides, the distance between and has changed by L We can then derive the lower bound:
IID - -RIGG)lL 2 V(n I)(L (L-
Let us now consider the case of LASER with a single snapshot. We want to choose p sufficiently small so to avoid adding too many edges. In order to do that, let us focus on the chain. Any node in the chain with the exception of the one before 2, which we call z' (which has the whole clique in its 2-hop), has 2-hop neighbourhood of size at most 2. Accordingly, given number of edges A we wish be adding, if we choose
k
2T.
it means that our algorithm, on average, will only add l edges over the chain. To avoid vacuous cases, consider & 2 Accordingly, the pairwise distance between any couple of nodes along the chain is changed by at most k. For what concerns the clique instead, let us take the worst-case scenario where is connected to any node the clique. Then, the distance between any node in the clique and any node in the chain has changed by (I: + 1). If put all together, we have shown that
DDc - DLASER |F VIRR2 nL(k + 1)2.
Therefore, the bound we have claimed holds if and only if
L 22 + nL(k + 1)² S (n () - 1)2 + (I. 10-22 2
(11)
One can now manipulate the inequality and find that the bound is satisfied as long as
2
21 21
n Z 1 - k2) - 3/, 2kL +
and note that the denominator is always positive if k² < <L/4 and L 2 8. Accordingly, we conclude that if
L/4
1
L.
2VL
and L > 8 our claim holds. In particular, LASER will have added k (0, VL/2) edges in total.
B EXPERIMENTAL DETAILS
Reproducibility statement. We release our code on the following URL https::///// pettps://githue thub. com/Fedzbar/ laaerrrlaeerree rewerrreeeeeeeeeeeee under the MIT license. For the additional baselines, we bor- rowed the implementations provided by the respective authors. We slightly amended the implementa- tion of GTR as it would encounter run-time errors when attempting to invert singular matrices on certain graphs.
payper-parameters For the LRGB experiments, we use the same hyper-parameters and configura- tions provided by Dwivedi et al. (2020), respecting a 500k parameter budget in all the experiments. We lightly manually tune the number of snapshots with values L {2, 4, 5} and the density with values [1/10, 1/4, 1/2) for LASER. For FOSR, SDRF, and GTR we search the number of iterations from (5, 20, 40), similarly to their respective works. For BORF, the rewiring is much
15

---

Published as a conference paper at ICLR 2024
more expensive, especially these 'larger' datasets, fix the number of iterations to 1. We point out that with the implementation provided by the authors, BORF would exceed the 60 hours limit imposed by Dwivedi et al. (2022) on our hardware for PCOM-Contact and for this reason assigned it a TIMEOUT value.
For the TUDatasets experiments, we use ADAM (Kingma & Ba, 2015) with default settings and use the ReduceLROme Lateau scheduler with a patience of 20, a starting learning rate of 0.001, decay factor of 1/2, and minimum learning rate of 10-5, We apply Batch Norm (loffe & Szegedy, 2015), use ReLU as an activation function, and fix the hidden dimension to 64. We do not use dropout, avoid using a node encoder and use a weak (linear) decoder to more accurately compare the various rewiring methods. We lightly manually tune the number of snapshots with values I. {2, 3) and the density with values (1/10, 1/4, 1/2] for LASER For FOSR, SDRF, and GTR we search the number of iterations from (5. 20, 40), similarly to their respective works. For BORF, we sweep over (1, 3) iterations. For DifTWire, we search between a normalized or Laplacian derivative and set the number of centers to 5.
For both LRGB and the TUDatasets the additional baseline models are also further tuned using either a relational or non-relational GCN. For instance, in the main text we group the results of FOSR and R-FOSR together for clarity. In general, we found relational models to perform better than the non-relational counter-parts Such result is consistent with results reported by other rewiring works.
Hardware. Experiments were ran on machines with 4x NVIDIA Tesla T4 (16GB) GPU, 16 core Intel(R) Xeon(R) CPU (2.00GHz), and 40 GB of RAM, hosted the Google Cloud Platform (GCP). For the PWCM-Contaaeeooooo experiments we increased the RAM to 80GB and the CPU cores to 30.
B. DATASETS
and PCOM-Contact tasks from the Long Range Graph Benehmark (LRGB) (Dwivedi et al., 2022). Peptides-fung (15 535 graphs) is a graph classification task in which the goal is to predict the peptide function out of 10 classes. The performance measured Average Precision (AP). Pept reptides
LRGB We consider the Pept deptides-strutt, Pept
(15
graphs) is a graph regression task in which the goal is to predict 3D properties of the peptides with the performance being measured in Mean Absolute Error (MAB). CCQM-Contact (529 434 graphs) is link- meeeppreiition task in which the goal is to predict pairs of distant nodes (when considering graph distance) that are instead close in 3D space. In our experiments, we follow closely the experimental evaluation in Dwivedi al. (2022), we fix the number of layers 5 and fix the hidden dimension as such to respect the 500k parameter budget. For Peptides ides we use a 70% 15% /15% train/test/split, we use a 90%/5%/51
while for PCQM-Cont
split. We train for 500 epochs on Pept des
and for 200 on Tönshoff et al. (2023) have shown that there are better syper-paramett configurations than the ones used by Dwivedi et al. (2022) for the LRGB tasks that significantly improve the performance of certain baselines.
We would like to also point out that in work concurrent to ours,
TUDatasets We consider the REDDIT -CC--BIN BINARY (2 (2000 graphs), IMDB-BINANE BINARY (1000 graphs), MUTAG (188 graphs) YMES (600 graphs), PROTEINS (1 113 graphs), and COLLAB (5 000 graphs) tasks from TUDatasets (Moris et al., 2020). These datasets were chosen by Karhadkar et al. (2022), under the claim that they require long-ran range interactions. We train for 100 epochs over 25 random seeds with a 80% 10% 100 train/val/test split. We fix the number of layers to 4 and the hidden dimension to 64 as Karhadkar et al. (2022). However, unlike Karhadkar et al. (2022), we apply Batch Norm and set dropout to 0% instead of 50%. We also avoid using multi-layered encoders and decoders, in order to more faithfully compare the performance of the rewiring techniques. The reported performance is accuracy + standard deviation a. We note that Karhadkar al. (2022) report an uncertainty value a /NN with N being the number of folds. As they set N 100, they effectively report mean to/ 2g/10, 10. We instead report simply the standard deviation a as we deemed this to be more commonly used within the community.
16

---

Published as a conference paper at ICLR 2024
B.2 DISCUSSION ON THE TUDATASETS
In Table 3, we show an evaluation of LASER on the REDDIT-BINARY, IMDB-BINARY, MUTAG, ENZYMES, PROTEINS, and COLLAB tasks from the TUDatasets, which were chosen by Karhadkar at. (2022) under the claim that they require long-range interactions. We evaluate on a 80%/10%/10 train/val/test split on 25 random splits. We fix the hidden dimension for all models to 64 and the number of layers to 4 as in Karhadkar et al. (2022), but set dropout rate to 0% instead of 50% deem this more appropriate. The goal of the evaluation to compare the rewiring techniques directly, while the high dropout may complicate more direct evaluation. We train for 100 epochs. For these experiments, we fix the underlying MPNN to GCN.
We point that the datasets chosen in the evaluation of Karhadkar al. (2022) have characteristics that may be deemed problematic. First, many of the datasets contain few graphs. For instance, MUTAG contains 188 graphs, meaning that only 18 graphs are part of the test set. Further, REDDIT -BBBIRYYY IMDB- WNDD-BINARY, and COLLAB do not have node features and are augmented with constant feature vectors. Consequently, is not immediately clear how much long-range interactions play role in these tasks, or in fact, how to even define wer-squashing on graphs without (meaningful) features. For these reasons, we believe the LRGB tasks be more indicative of the benefits of graph-rewiring to mitigate over-squashing.
Furthermore, the standard deviation of the reported accuracy relatively large on some of the benchmarks, especially on the smaller MUTAG and ENZYMES tasks. While we report directly the standard deviation in our uncertainty quantification, Karhadkar et al. (2022) instead report a / V with N being the number of folds. In Karhadkar et al. (2022) they set N = 100, meaning that effectively they report the standard deviation divided by a factor of 10. The high uncertainty in these datasets can be also seen in the results from Karhadkar et al. (2022). In particular, an accuracy of 68.3% on MUTAG is reported using GCN without rewiring, while accuracy of 49.9% is reported on MUTAG with an R-GCN without rewiring. However, the two models should achieve similar accuracy, as the R-GCN without rewiring is equivalent to standard GCN model as there no further edge types in MUTAG.
For these reasons, we believe that while the results of LASER the TUDatasets are strong and beat the other baselines, any evaluation done on these tasks should be considered with a degree of caution as the high standard deviation and quality issues of the chosen tasks leave the results possibly less conclusive. Regardless, we retain such an evaluation in our work for completeness of comparison with the benchmarks used by Karhadkar et al. (2022).
C ADDITIONAL RESULTS
In this Section, provide additional results and ablations. In Section C.I, we discuss the orbit sampling procedure that makes LASER permutation-oquivarinn in expectation. In Section C.2, we provide a density comparison between LASER and multi-hop GNNs (p = 1). In Section C.3, we show that LASER is able to work well over range of popular MPNNs. Finally, in Section C.4, we give further motivation for the need for locality.
C.I PERMUTATION- FERMUTATION--QUIVVRIAANT EQUIVARIANCE OF LASER.
When selecting the edges that need to be rewired given the connectivity measure μ., care needs to be given when handling the tie-breaks order to remain permutation-equivarinn Assume we have to select A nodes from partially ordered set of size n >> ki given reference node v. Further assume that nodes from k' + 1 < k to p > & have equivalent connectivity measure, i.e. we are given a sequence of nodes U1, ..... Un such that:
(V, S ... S u(u, uw) ulo, 4k41) = ... u(),up) ...
S.. Sp(u,
We start by selecting the first k nodes ui...., dy as they are the ones with lowest connectivity measure. Next, we have to select the remaining k - k' nodes from ug++1..... up- If we naively conuutation-quivvriaan issues as we would be
select the nodes ..., Ug we would encounter relying on arbitrary ordering of the nodes. Instead, in LASER sample uniformly the remaining
17

---

Published as a conference paper at ICLR 2024
Table 5: Performance on the Peptides tasks given a LASER implementation that is not permutation -etiiiariiniiviiianttt (choosing top & based on and tie- are chosen based on node id) and one that equivariant (through sampling uniformly from the tie-breaks). Bold denotes best.
Rewiring
Pept: fun
Peptides-struct: +
LASER Not Equivariant
0.6385=100048
0.3162+000032
LASER
0.6447:10.0033
0.3151#0.0006
Table 6: Mean added edges per graph given a LASER rewiring with density of 0.1 and p = 1 on the Pept ides dataset.
Density
2 Snapshots
3 Snapshots
4 Snapshots
5 Snapshots
LASER P 0.1
148.9
296.5
442.4
587.2
LASER =
205.8
434.7
691.6
986.1
1'' from the nodes + ......P that have equivalent connectivity measure, assuring permutation- equivariance in expectation. Table 5 shows that the permutation-equivatt better than the naive implementation of simply selecting the first & nodes sorted with respect to μ. In practice this shuffling can be implemented efficiently by sampling random vector NN(0, ol), with a very small and then adding this to the vector of connectivity measures, i... fi = f + x. When is small enough, this has the effect of uniformly breaking the tie-breaks, without breaking the absolute order of the connectivity measures.
implementation performs
C.2 DENSITY ABLATION.
Table 6 reports the mean added edges per graph (counting undirected edges only once) given 0.1 and p = on the ides graphs. We note that regardless of p. we always add minimum of 1 edge per node orbit. Given that the (molecular) graphs in peptides are very sparse graphs with an average of 151 nodes and 307 edges, the table highlights worst-case scenario for LASER as the orbits grow relatively slowly. Having said this, the number of added edges grows at significantly lower rate given p 0.1. This showcases the use of p control the density of the graphs. The minimum number of node rewirings added being set to is design choice and this can also be further tuned to control the density, desired.
C.3 PERFORMANCE WITH DIFFERENT UNDERLYING MPNNS
We run experiments to evaluate the performance of LASER operating over different MPNNs. We evaluate on popular MPNN models: Graph Convolution Networks (GCNs) (Kipf & Welling, 2017), Graph Isomorphism Networks (GINs) (Xu et al., 2019), GAT Veličković et al. (2018), and GraphSAGE (SAGE) Hamilton al. (2017). Table 7 shows the results Pept desiddes-fie func and septides-oe strccttruct obtained by varying the underlying MPNN. We see that LASER improves the bascline MPNN performance consistently reaching best or near best performance. This is the case for FOSR and SDRF that often end up harming the performance of the baseline MPNN, even when using a relational model. This experiment provides evidence supporting the fact LASER able to function well regardless of the underlying convolution being considered.
C.4 MOTIVATING LOCALITY
In this section, motivate the desire for rewiring technique respect the locality of the graph. Preserving locality is natural inductive bias to have whenever we assume that the graph-structure associated with the data is aligned with the downstream task. For instance, molecular systems observe long-range interactions that decay with the distance, in the form of Coulomb electrostatic forces. This behaviour also naturally appears in social networks, transaction networks, more generally in
18

---

Published as a conference paper at ICLR 2024
Table 7: Results for Peptides- func and serrridessstine Performances are Average
Precision (AP) (higher is better) and Mean Absolute Error (MAE) (lower is better), respectively. Results in bold denote the best result for each MPNN.
Peptides- fune Peptides
Model
Test AP f
Test MAE
GCN
0,5930=0.00023 0.4629
0.3496100.00 3
GCN-FOSR-R
0.3078 0.06
GCN-SDRF-R
0.5851
0.3404=0.000
GCN-LASER
0.6440=0.0010
0.3043
GIN
0.5799#0.0006
0.3493
GIN-FOSR-R
0.486410.0054
0.2966=:0.0024
GIN-SDRE-R
0.6031
0.3394+t0.0011
GIN-LASER
0..089
0.0078+0000066
GAT
0.5800=000001
0.3506:+0.0011
GAT-FOSR-R
0.00044
0.3074+00.002
GAT-SDRE-R
0.5756:10.0037
0.3422:10.0000
GAT-LASER
0.6271#0.0052
0.2971+0.0037
SAGE
0.3480+00.000
BAGE-FOSS-R
0,4678
0.2086
SAGE-SDRE-R 0.5892:10.0000
0.000
SAGE-LASER
0.6464+0.0032
0.3004+0.0032
physical systems, in which interactions that nearby are more likely be important for given task. Accordingly, given a budget of edges to be added, it is sensible to prioritise adding connections between nodes that are closer.
Through a spectral rewiring, one is able to efficiently improve the information flow, but this often greatly modifies the information given by the topology the graph, as shown in Figure This may be beneficial in tasks in which mixing all information quickly is important, but GNNs usually do not operate under such conditions. In fact, in tasks which locality 'should' be preserved, spectral rewirings tend to perform poorly, as shown in Table 2. Furthermore, it is unclear to what extent spectral graph-rewsrings are able to deal with generalization to variying graph sizes. For instance, spectral rewiring very large peptide chain will connect the most distant parts of the peptide, drastically reducing spatial quantities such as diameter. Instead, on a small molecule this change in topology would be comparably much more tame. On the other hand, local rewiring techniques naturally generalize to different graph sizes as the mechanism via which they alter the topology is much more consistent, being a local procedure.
Figure 4 further motivates the need for locality in LASER and supports the claim that locality is the main source of improvement, rather than the more expressive architecture capable of handling sequence of snapshots. In the experiment, we compare LASER to version of FOSR in which each snapshot contains 10 rewirings. We observe that for LASER larger quantity of snapshots seems to benefit the performance. Instead, with FOSR there is a slight degrade in performance. Regardless, even with a growing number of snapshots, FOSR not able compete with LASER This supports the claim that even within our snapshot framework, it is important for the snapshots to remain local, rather than acting globally as done in FOSR.
D SCALABILITY AND IMPLEMENTATION
In this section, provide theoretical and practical insights the scalability of LASER to large graphs. We start by providing a theoretical complexity analysis, followed by benchmarking pre- hardware.
processing and training times for the various rewiring techniques under comparison We find that the LASER rewiring procedure is able to scale to synthetically generated graphs with 100k nodes and million edges. We further find that the densification due to the rewiring does not
19

---

Published as a conference paper at ICLR 2024
Snapshots with Local and Global Rewirings
0.66
Local (LASER)
Global (FOSR)
0.64
0.62
0.60
0.58
2
Snapshots
Figure 4: Average Precision (AP) on Pept peptiids--unde obtained by varying the number of snapshots for LASER and FOSR, respecting the 500k parameter budget. For LASER, fix p 0.1. For FOSR, each snapshot contains 10 iterations.
significantly impact the total training and inference time when compared to the underlying MPNN without rewirings on real-world tasks.
D.1 COMPLEXITY ANALYSIS
The computations LASER during the pre-processing time are achieved in two steps: (1) the connectivity measure μ and locality measure are computed for the graph G and (2) μ is used to guide the rewiring of the edges given the density factor p and constrained by the locality measure v. Algorithm describes the computation done in step (1) and Algorithm 2 the computation in step (2).
Algorithm Fast μr, Computation
Input: Adjacency matrix A, Number of snapshots L., Connectivity radius C 8
Output: Locality matrix D, Connectivity matrix M
D+ A
2: Acurr + A
3: Anezt A
4: for = 2, do do
5:
Acurr +- clip( AcurT)
6:
Anert clip( Aneat
7:
D+D D r( (Annet Acurr)
Adds nodes at distance r to D. Setup next iteration.
8:
Agurr Anezt
9:
Anext Anezt
10:
end for
11:
M + AC
return D,M
While the implementation depends on the choices for f and in step (1), our specific choices are particularly efficient. Both of our measures can be in fact computed with matrix multiplication and other simple matrix operations that are highly efficient on modern hardware. For square matrices of size n, we set the cost of matrix multiplication to (n)3) in our analysis for simplicity although there are more efficient procedures for this operation. In particular the computational complexity assuming the number of snapshots L to be sufficiently small which is the case in practice of μ and v is (n?)) with n being the number of nodes considered, while the memory complexity is O(n?). We further note that while computing effective resistance also has theoretical complexity of (n it involves (pseudo-)ie jivverting the graph Laplacian which in practice has significant prefactor when compared to matrix multiplication and often runs into numerical stability issues.
20

---

Published as a conference paper at ICLR 2024
The computations in Algorithm 2 are similarly efficient and easily parallelizable the computation for each node independent. We find that the computational complexity is O(n²) as each node-wise wise calculation is (n)) and there are such operations. Overall, the entire procedure of LASER therefore has a cost of (nn"), with the primary overhead heing the cost of taking matrix powers of the adjacency matrix A. In these calculations are absorbing the costs due the number of snapshots L as prefactor, which is reasonable assumption as L is constant, small, and independent of n. As shown in the benchmarking experiments, in practice the cubic cost shows very strong scalability as the operations required in our computations are highly optimized on modern hardware accelerators and software libraries.
Algorithm 2 LASER rewiring for locality value r
Input: Graph G, Locality matrix D, Connectivity matrix M. Locality value Density p Output: Rewired edges E, for locality
1: E, < empty()
2: for node in do
3:
Doode; Mnode
D mode, =], M M[ooee :]
4:
Mnode &- Mnodel D Dode r]
> Consider only the nodes at locality value r. Edges to add are the fraction p of the orbit size.
5: k ==round(A (p) Mnodel)
6:
Euode &- getNew/ddeesRnndd@@iivviaaan Modd: k)
7: E. E.ddddEggesEE.
8: end for
9: return E,
D.2 REAL-WORLD GRAPHS SCALING
In Table 8, we show rewiring pre-processing and training times on PCQM-Contact and pre- processing times PascalVOC-S3 datasets from LRGB. PCQM-Contact has more than 500k graphs with an average node degree of = 30 per graph. We find that the rewiring and inference times between FOSR, SDRF, and LASER are very similar. Pasca VOC-SP is dataset with & 11k graphs, but with a considerably larger average node degree of R 480. We find that LASER still extremely efficient, especially when compared SDRF, with FOSR being the fastest. We further remark that the FOSR and SDRF implementations rely on custom CUDA kernel implementations with Numba accelerate the computations. We specifically avoided such optimizations in order to preserve the clarity of the implementation and found the performance of LASER to be efficient enough without such optimizations regardless. We envision that a custom CUDA kernel implementation of LASER could be used for further speedups.
In Table 9, we show the training time impact of the various rewiring techniques with SAGE as the underlying MPNN on the Pept des d task. We find that the rewiring techniques overall add small overhead to the SAGE implementation. In particular, LASER with L = 1 has the same training time of FOSR and SDRF but achieves significantly higher performance.
Table 8: Rewiring and Training+Inference times for the CCQM-Contact and PascalVOC-SH datasets.
Dataset
FOSR
SDRF
LASER
PCQM Training+Inference Time (GIN)
11h 47m
11h 51m
12h 21m
PCQM Rewiring Time
5m 20s
5m 36s
4m 15s
PascalVOC-SP Rewiring Time
4m 3s
31m 30s
9m 6s
D.3 SYNTHETIC SCALING EXPERIMENT
To further benchmark the scalability of the rewiring time, we construct an Ardos-Renyl synthetic benchmark with nodes and Bernoulli probability p 10/n, iee in expectation In these synthetic experiments, we benchmark on a machine with 44 cores and 600GB of RAM. Setting 10k (meaning 100k edges), LASER (p 0.5, 1) takes I Iss while FOSR and
have 10n edges.
21

---

Published as a conference paper at ICLR 2024
Table 9: Run-time on Peptides func with different rewirings and SAGE. For FOSR and SDRF
we set the number of iterations to 40 and for LASER we set 0.5. L denotes the number of rewirings.
Model
Training Time
Rewiring Time
Parameters
Test t
SAGE
46m 26s
N/A
0
482k
0.5971
FASE-FOSR-R
55m 51s
35s
1
494k
0.4678=0.0066
SAGE-SDRF-R
54m 52s
21s
1
494k
0.5892:#0.0040
SAGE-LASER
54m 50s
33s
1
494k
0.6442:10.022
SAGE-LASER
4m 28s
42s
3
495k
0.644444000032
SDRF with 0.001n 100 iterations take 45s and 5m 48s respectively. On 100k (meaning million edges), LASER completes the computation in 2h 16m, while FOSR and SDRF do not terminate after more than 24 hours of computation. We emphasize that these graphs much larger than what graph rewiring techniques are designed for, yet LASER still able to handle them with success due its efficient design.
Overall, in these synthetic experiments, we found that LASER is able to scale to very large graphs and with reasonable run-time modest hardware. Scaling to larger graphs with millions of nodes would likely require some further form of sampling, with this being a common practice used to scale GNNs very large graphs (Hamilton et al., 2017).
22


Reviews:
[{"review_id": "QEITLg4Les", "reviewer": "Reviewer_EJ4V", "summary": "This paper proposed a sequential rewiring method, LASER, that improves connectivity, and preserves locality in the original graph, and theoretically alleviates the over-squashing problem. Empirical experiments show that LASER outperforms the baselines on some LRGB and TUDatasets.", "questions": "On the top of page 3, what does the notation 2|E|R(v, u) stand for?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper gives a good summarization of spectral and spatial rewiring methods.\n- The anti-over-squashing and sparsity motivation of the paper makes sense.\n- The sequential rewiring idea is pretty good so that edges are not added at once but more carefully selected.\n- The connection between sequential rewiring and multi-relational GNN is novel\n- The writing is good and clear.", "weaknesses": "- The paper does not explain why adding distant edges is not a good choice. In other words, why must we respect the locality and inductive bias of the given graph? Therefore, the paper does not fully convince me of their significance, although the sparsity motivation is good, the method is novel, and the experimental results seem good.\n- The paper selects some spectral rewiring baselines but does not compare with DRew [1] and SP-MPNN [2] in the experiments, which also attend multi-hop neighbors in their message passing scheme and should be considered as spatial rewiring baselines. On LRGB datasets, DRew seems even better.\n- As this is a rewiring approach, it does not seem to make sense to do experiments with PCQM-Contact, which is an edge prediction task\n- The choice of connectivity measure in equation (8) is not efficient. The matrix multiplication would also be O(N^3). If the matrices are sparse, then the complexity would be at least O(N^2 * d_max).\n\n[1] Gutteridge, Benjamin, Xiaowen Dong, Michael M. Bronstein, and Francesco Di Giovanni. \"Drew: Dynamically rewired message passing with delay.\" In International Conference on Machine Learning, pp. 12252-12267. PMLR, 2023.\n\n[2] Abboud, Ralph, Radoslav Dimitrov, and Ismail Ilkan Ceylan. \"Shortest path networks for graph property prediction.\" In Learning on Graphs Conference, pp. 5-1. PMLR, 2022.", "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": "", "extra_scores": {}}, {"review_id": "2vFvALUdIE", "reviewer": "Reviewer_RVSP", "summary": "This paper explores the concept of graph rewiring, which involves altering graph connectivity to improve information flow. Three essential objectives for graph rewiring are identified: (i) reducing over-squashing, (ii) preserving the graph's local structure, and (iii) maintaining its sparsity. \n\nThe authors highlight that there is a trade-off between two primary techniques in graph rewiring: spatial and spectral methods. They argue that spatial methods tend to address over-squashing and local structure but may not preserve sparsity, while spectral methods generally handle over-squashing and sparsity but might not maintain local properties. \n\nTo tackle these trade-offs, the paper introduces a novel rewiring framework. This framework employs a sequence of operations that are sensitive to the graph's local characteristics, aiming to simultaneously meet all three objectives: reducing over-squashing, respecting the graph's locality, and preserving its sparsity. Furthermore, the paper discusses a specific instance of this proposed framework and evaluates its performance on real-world benchmarks.", "questions": "* Why do you say that spectral methods are not local, since most of them combine long-range information (by bypassing the bottleneck) and initial neighborhood? For instance, Arnaiz-Rodríguez et al. combine the CT model (long-range) with MPNN with the initial adj.\n\n* Is there any study of the parameter k? For instance, what happens for large k values? How does it affect the relationship between the distance of nodes of the same cluster (locally) and nodes of different clusters (globally)?\n\n* Can there be any attention mechanism between the snapshots, attending to those snapshots that contribute more to the representation of the graph, as they do in multiple papers where they explore different adj  (Abu-El-Haija et al., 2019; or FSGNN (Improving Graph Neural Networks with Simple Architecture Design)?", "limitations": "", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The authors gave a nice taxonomy of rewiring methods and the issues that they suffer from", "weaknesses": "* In the paper they constantly cite spectral methods such as Arnaiz-Rodríguez et al., Black et al., 2023 and transformer-based methods such as Kreuzer et al., 2021; Mialon et al., 2021; Ying et al., 2021; Rampasek et al., 2022. But in the tables, there is no comparison with these methods.\n\n* The results are very poor, especially when it comes to the task of graph classification, where the method is not able to outperform the few selected models.", "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": "", "extra_scores": {}}, {"review_id": "Cro2Vk7scA", "reviewer": "Reviewer_KgxZ", "summary": "This paper presents a framework for graph rewiring. Specifically, the paper suggests having two competing metric - one for oversquashing and one for distance to the original graph that should be balanced. The paper presents a specific instantiation of the framework and present numerical experiments to show the benefit of the framework.", "questions": "See weaknesses", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "**Originality**\n\nThe framework presented in the paper is new. However, the idea of preserving the original graph structure is not new, further as the authors themselves state the idea of using relational GNNs is not new either. Though they do have an original extension of the framework. \n\n**Quality**\n\nPlease see weaknesses. \n\n**Clarity**\n\nThe paper is well written and places itself very well in the context of prior work. This I think is the papers biggest strength. The framework is clearly presented. However, the paper's clarity degrades in Section 5. For example Proposition 5.2 is not clear and there is no formal statement or proof anywhere in the paper. \n\n**Significance**\n\nThe paper's method does seem to perform better than SDRF and FOSR. However, I have certain concerns about the experiments, highlighted in the weakness section.", "weaknesses": "I think there a few weaknesses. Part of my concern with the paper is that as detailed in point 2a, there are now many different rewiring techniques. However, I do not think we understand oversquashing yet. Hence for me new papers in the area either need to a thorough comparison with prior work to show empirical improvement. Or contributes to understanding oversquashing and I think this paper, unfortunately, does not do either. \n\n1) One big weakness is Proposition 5.2. The statement in the paper is informal and incomplete. However, the paper does not have a formal statement or a proof. This is a big concern. For example, for the informal statement $\\mathcal{G} = \\emptyset$ vacuously gives us the result. However, that version is meaningless. Hence a formal statement is needed. There is space in the paper for this discussion, the first few pages are quite repetitive. \n\nI see that page 14 has something that is called a proof. But without a formal statement the notion of proof does not make sense to me. And there is no formal statement. A.2 is thought of to be formal statement but it refers to a lower bound in 5.2 which is not clear. \n\n2) I have a few concerns about the experiments. \n\n    a) First, I think the paper compares against very few prior works. The paper does a good job of citing many prior works in the area but then only compares against two of them. The paper should compare against most of the following or explain why it is not relevant to do so: GTR (Black et al. 2023), BORF (Nguyen et al. 2023), DRew (Gutteridge et al 2023), DIGL (Gasteiger et al 2019), Expander propagation (Deac et al 2022), DiffWire (Arnaiz Rodriguez et al 2022). The paper even cites Brüel-Gabrielsson et al., 2022; Abboud et al., 2022, and  Banerjee et al., 2022 as further works with rewiring techniques. \n\n   b) I also have some concerns with the experiments that are present. First, as the paper notes the network from FOSR is the case that $L=1$. However, for the method proposed in the paper, the paper uses $L \\in \\{2,3,4,5\\}$. Since for each $\\ell \\le L$ we have a different weight matrix, this implies that the networks for LASER are bigger than the networks used for FOSR and SDRF. This is an inequity that could account for the improved performance. \n\n   c) Hyperparameter tuning. The paper mentions that they tune $L$ and $\\rho$ for their method. However, they do not perform any hyper parameter tuning for the comparison methods (SDRF and FOSR). They fix the number of edges to be 40. This is another thing that could account for the inequity between the methods. It is also not mentioned what number is reported, I am assuming that the experiments trained models for each of the hyperparameters, picked the setting with the best validation performance and then reported the test error, however it would good if this were explicitly mentioned (since Figure 3 reports the metrics on the test data for all hyperparameters). \n\n3) I think the fairer version for the experiments would be to sequentially rewire the datasets with FOSR and SDRF such for each $1 \\le \\ell \\le L$ all sets $E_\\ell$ have the same size. I think this would help determine if part of the reason for increased performance is the rewiring or the new GNN architecture.  \n\nThe next couple of concerns are more minor. \n\n4) In terms of the context for the work, I think the following could be clarified. The notion of oversquashing in Alan and Yahav 2021, and the other papers Topping et al 2022, Black et al., 2023; Di Giovanni et al., 2023 are subtly but in my opinion importantly different. Alon and Yahav 2021, is a more information theoretic issue that is highlighted. Vectors of a certain size can not aggregate too much information. However, the issue in Topping et al 2022, Black et al., 2023; Di Giovanni et al., 2023 is more about optimization rather than information theory. These papers talk about how the Jacobian has a small norm. Hence while both phenomena can be labelled as oversquahing I do think they are different and should be treated as such. \n\n5) The paper measures the \"information\" provided by the graph structure as preserving locality. Specifically, they say ``while the measure $\\nu$ is any quantity that penalizes interactions among nodes that are ‘distant’ according to some metric on the input graph.'' However, local structure of the graph and the information stored in the graph are not the same thing.", "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": "", "extra_scores": {}}, {"review_id": "O7SX7X43OC", "reviewer": "Reviewer_XEwE", "summary": "This paper focuses on graph rewiring, a technique used to reduce the over-squashing problem in GNNs. It analyzes three desiderata for graph-rewiring, pointing out that previous methods fail to satisfy all of them. Based on this, the authors propose a novel rewiring framework that satisfies all three desiderata, considering locality by a sequential process. Finally, they validate the method on various real-world benchmarks.", "questions": "1. The paper used the number of walks for the connectivity measure $\\mu$. According to the preliminaries in section 2, it seems that the connectivity measure is an unnormalized adjacency matrix. However, in the theorem 4.1 of the citated paper (Di Giovanni et al., 2023), the number of walks are divided by power of minimum node degree. Following this, doesn’t the adjacency matrix should be normalized using the node degree?\n2. For the necessity of sequential rewiring, authors claimed that instantaneous rewiring easily violates either locality or sparsity constraint. In Figure 3, authors conducted an ablation study on the number of snapshots. Is there any comparison with an instantaneous rewiring, i.e., snapshot being 1?\n3. The connectivity and locality measures are only computed once over input graph to make the rewiring process efficient. However, it seems that these measure might change after some sequential steps of graph rewiring. For example, the shortest-walk distance between two nodes might get smaller after some graph rewiring steps, leading to another graph rewiring rather than the authors intended. Is it just that the performance gap of computing measures once and at each rewiring step did not differ much?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. The paper clearly points out that previous graph rewiring fails to satisfy three aspects, and suggests a new method satisfying all aspects.\n2. The paper is overall well written and structured.\n3. The theoretical analysis provides an explanation on why the suggest method works well.", "weaknesses": "1. The background for preserving sparsity seems to be weaker compared to the background for preserving locality, where the authors give effective resistance as example for preserving locality. It would be more persuasive if the authors gave an experiment result or paper for the question, “some of these new connections introduced by spatial rewiring methods may be removed with affecting the improved connectivity.”\n2. Authors have used “effective resistance” throughout the paper to support their claim. However, the paper does not have any comparison with the graph rewiring method that uses effective resistance$^{[1]}$.\n\n[1] Black et al., Understanding oversquashing in gnns through the lens of effective resistance, ICML 2023", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)