The Effectiveness of Curvature-Based Rewiring and the Role of Hyperparameters in GNNs Revisited
Authors: Floriano Tori
Vincent Holst
Vincent Ginis
Venue: ICLR 2025 Poster (2025)
Keywords: Geometric deep learning
Graph Neural Networks
Graph Rewiring
Curvature
Primary area: learning on graphs and other geometries & topologies
TL;DR: Our research challenges the effectiveness of curvature-based rewiring methods, revealing their dependence on hyperparameter tuning and questioning their applicability to real-world datasets.

Abstract: Message passing is the dominant paradigm in Graph Neural Networks (GNNs). The efficiency of message passing, however, can be limited by the topology of the graph. This happens when information is lost during propagation due to being oversquashed when travelling through bottlenecks. To remedy this, recent efforts have focused on graph rewiring techniques, which disconnect the input graph originating from the data and the computational graph, on which message passing is performed. A prominent approach for this is to use discrete graph curvature measures, of which several variants have been proposed, to identify and rewire around bottlenecks, facilitating information propagation. While oversquashing has been demonstrated in synthetic datasets, in this work we reevaluate the performance gains that curvature-based rewiring brings to real-world datasets. We show that in these datasets, edges selected during the rewiring process are not in line with theoretical criteria identifying bottlenecks. This implies they do not necessarily oversquash information during message passing. Subsequently, we demonstrate that SOTA accuracies on these datasets are outliers originating from sweeps of hyperparameters—both the ones for training and dedicated ones related to the rewiring algorithm—instead of consistent performance gains. In conclusion, our analysis nuances the effectiveness of curvature-based rewiring in real-world datasets and brings a new perspective on the methods to evaluate GNN accuracy improvements.

Published as a conference paper at ICLR 2025
THE EFFECTIVENESS OF CURVATURE-BASED REWIRING AND THE ROLE OF HYPERPARAMETERS IN GNNS REVISITED
Floriano Tori
Vincent Holst
Vincent Ginis
Data Analytics Laboratory Vrije Universiteit Brussel F Florianc. Tori evri@vub...r be
Data Analytics Laboratory
Data Analytics Laboratory
Vrije Universiteit Brussel Vincent. Tworeee Holst @ @vub.be be
Vrije Universiteit Brussel
SEAS, Harvard University
Vincent. Gini www.siiub..nn...mmmmmmmmmu be
ABSTRACT
Message passing is the dominant paradigm in Graph Neural Networks (GNNs). The efficiency of it, however, can be limited by the topology of the graph. This happens when information is lost during propagation due to being oversquashed when travelling through bottlenecks. To remedy this, recent efforts have focused on graph rewiring techniques, which disconnect the input graph originating from the data and the computational graph, on which message passing is performed. A prominent approach for this is to use discrete graph curvature measures, of which several variants have been proposed, to identify and rewire around bottlenecks, fa- cilitating information propagation. While oversquashing has been demonstrated synthetic datasets, in this work we reevaluate the performance gains that curvature- based rewiring brings to real-world datasets. We show that these datasets, edges selected during the rewiring process are not in line with theoretical criteria iden- tifying bottlenecks. This implies they do not necessarily oversquash information during message passing. Subsequently, we demonstrate that SOTA accuracies on these datasets are outliers originating from sweeps of hyperparameters- both the ones for training and dedicated ones related to the rewiring consistent performance gains. In conclusion, our analysis nuances the effectiveness of curvature-bane based rewiring in real-world datasets and brings a new perspective the methods to evaluate GNN improvements.
innsttd of
INTRODUCTION
Machine learning graph data, and more specifically Graph Neural Networks (GNNs), has dergone rapid development over the past few years. Both in terms of architecture variations (Wul al., 2019 Kipf & Welling 2016: VVeičković al. 2018 (ammlton et al. 2017) as theoretical understanding (Xu et al. 2018 Bronstein et al.) 2021 Bodnar et al. 2021a b). Due to their large flexibility GNNs have been applied in a variety of domains, from physical sciences to knowledge graphs or social sciences (Zhou et al. 2020 Wu et al. 202T). The basis of the message passing paradigm of GNNs (Gilmer et al.) 2017 rests on the idea of information diffusion where messages, namely the node's s feature vector, are propagated along the edges of the graph to their neighbours.
This approach to GNNs has been shown to be very successful, as it combines topological information (the graph) and specific node information (feature vectors) for predictions. However, this paradigm can also suffer from drawbacks. The receptive field of node, i.e., the number of nodes can receive information from, depends the number of layers of the GNN. A low number of layers can cause under-reaching (Sun et al. 2022) where required information does not reach the nodes. On the other hand, if node's 's receptive field too large, this can lead oversmoothing (Li al.) 2018 Oono & Suzuki 2019). where node representations are homogenised due to subsequent message passing.
Recently, lot of attention has been drawn to the problem of oversquashing (Alon & Yahav 2021) where structural properties of the graph called bottlenecks cause loss of information as the messages passing through get too compressed. Research efforts have therefore focused understanding this

---

Published as a conference paper at ICLR 2025
phenomenon (Di Giovanni et al. 2023 Black et al. 2023) well ways to alleviate it. The most pragmatic approach consists of rewiring, L.e,, a targeted addition or removal of edges, to reduce the bottlenecks in the graph.
In this work, we investigate the role of graph rewiring to improve performance on node classification tasks. Discrete notions of eurvatures graphs can be used to detect the location of bottlenecks, allowing for the development algorithmic rewiring methods such as Stochastic Discrete Ricci Flow
(Topping al. 2021). While this point of view was presented first (Topping al. [022] other
definitions of curvatures such as Jost and Liu Curvature (Giraldo et al. [023] Jost & Liu 2014) or
Augmented Forman Curvature (Fesser& & Weber 2023) have been proposed as alternative measures
(Bober et al., (202)). Despite that fact that work on synthetic datasets (Di Giovanni et al., 2023
Black et al. 2023) does indicate the occurrence of oversquashing, we here nuance these results on
benchmark datasets and reevaluate the performance gains of curvature-bane -assee rewiring.
The goal of our paper is to analyse the effectiveness of curvature based rewiring to improve performances in non-synthetic graph datasets. This is in line with Tortorell & Micheli (2023) which evaluates rewiring performances on training-free GNNs and shows that rewiring rarely confers practical benefit for pessagg-passiigg in those cases. Our work shows that this is the case in general GNNs and offers an explanation: the theoretical motivation for rewiring is not satisfied in most cases when applied real-world datasets. Additionally, SOTA results when rewiring by analysing the role of hyperparameter sweeps. We find that these results can be attributed to hyperparameter tuning outliers, as has also been found in other GNN performance gains (Tönshoff et al.) 2024). Our work thus calls into question the effectiveness of rewiring for graph datasets and creates a starting point for further investigations on how to evaluate (GNN) improvements and how to bridge theory and experiment beyond synthetic datasets.
Contribution
explain the occurrence of the
Outline In section 2 we introduce the theoretical relation between curvature and bottlenecks in graphs. Section OxctiionSexperimmettte experimentally verifies this condition in standard datasets, where find that most rewired edges are not necessarily responsible for oversquashing. With this nuanced perspective on the theory underlying the rewiring algorithm, evaluate the performance gains possible due to rewiring in section[4] 4 When comparing performances of all curvature definitions with the performance obtained when implementing no rewiring all, we find no consistent (at the level of distributions) improvements over the different datasets.
2
GRAPHS, OVERSQUASHING AND CURVATURE
2.1 PRELIMINARIES
Graphs We consider an undirected graph G (V, identified by a set of nodes, which are described by feature vector E R with i E V, and set of edges E C V x V. The adjacency matrix, which describes the connection of the graph, is denoted by A.
(1) the representation Graph Neural Networks Given the graph G as described as above, we write h of node layer where h, X1. Given layer dependent, differentiable functions o' Rn RR R and v R
x R Rdd, we write the message passing function as
h (++1)
d' h
(h.". (n.).n()))
(I)
j=1
Here, Á denotes the normalised augmented adjacency matrix, i.c. the adjacency matrix A is augmented by self-loops Á A + and then normalised by D D I, where D denotes the diagonal degree matrix. More precisely, we have Á D
A.D
2

---

Published as a conference paper at ICLR 2025
2.2 DISCRETE CURVATURE NOTIONS ON GRAPHS
The main idea behind applying discrete curvature notions to detect local bottlenecks in graphs stems from differential geometry. Here, it is well known that the Ricci curvature describes whether two geodesics which start close to each other, either diverge (negative curvature), stay parallel (zero curvature) or converge (positive converge). Prominent examples are the hyperbolic space (negative curvature), Euclidean space (zero curvature) and the sphere (positive curvature). The graph analogues for these spaces are trees, four-eycles and triangles. Discrete curvature notions in essence capture the occurrence of such structures around a given edge. Intuitively, negatively curved edges exhibit more tree-like structures their local neighbourhoods and are thus prone to oversquash information.
Discrete curvature notions for graphs Curvature notions on graphs depend on topological aspects of the graph with the needed ingredients being the following, For a simple, undirected graph we consider an edge i ~ j. We denote by d: the degree of node i and by dj the degree of node j. The common neighbours of node i and node are denoted by i4 (). They correspond to the triangles located at edge j. The neighbours of i (resp. j) that form a four-cycle based i ~ without diagonals inside are denoted by $ (resp. + and the maximum number of four-cycles without diagonals inside that share common node denoted by Tmaz We denote by x V y - max(æ, y) (resp. x A y = min(x, y)) the maximum (resp. minimum) of two real numbers. In this paper we analyse three main branches of discrete curvatures, with variations within.
First, we consider Balanced Forman Curvature (BFc) (Topping et al. 2021) and variations thereof:
Balanced Forman Curvature: For an edge i ~ we have BFe(i. = if min(d;, (d), = 1 and otherwise
( + |+
BFe(i.j)
2 - -
2 dj -
FA (i,
(t. A Ymaz (dg V dj)
(2)
d;
d, Vjj
Balanced Forman Curvature (without four-cycles): Determining the number of four-cycles without diagonals inside is costly computational effort, especially for dense graphs. We therefore analyse the rewiring performance of BFc without these four-cycles to evaluate the need of more intensive computations. For an edge i ~ j we have (F,)( 0 if min (d,, d,) = 1 and otherwise
2 di dj
2
(1. de V dj
+ (A(
BFca(i,j)
2
(3)
d, A dj
Modified Balanced Forman Curvature: The original code implementation provided in Topping al.] (202T) contained an error in the counting of four-cycles (See Appendix B for more details). We therefore implement this version as well for comparison. For an edge j we have BF BFomoddi, (i,j) 0 if min(d;, dj) = 1 and otherwise
2 2 d,
14 (i.)) (+.() d4 Vd
O (I + 1151+
BFCmod
+
d
d4 ^ Ad
Secondly, consider JLc (Jost and Liu) Jorvature(Jost & Liu 2014). For edge ~ Lj we have, with 5 max(s, 0),
JLcli,j) = (1 d d
1
1 (1. de A d2
(1.5 - -(1 d: d d, V.V.. d2
(1,
d, V dj
(5)
Finally, we consider the Augmented Forman Curvature used for rewiring in (Fesser & Weber 2023).
Originally, the Forman curvature was introduced in (Forman] (003) as a discrete analogue of the Ricci curvature that aims to mimic the -eitnerr-WWtzzbböökk decomposition of the Riemannian Laplace operator for quasiconvex cell complexes (compact regular CW complexes which are quasiconvex, i.e. the boundary of two cells can most consist of one lower-dimensional cell). It then adapted to graphs (Sreejith et al. 2016) and augmented to also include two dimensional cells such as triangles (Weber et al. 2018 Samal al. 2018). The Augmented Forman curvature comes in two variants.
3

---

Published as a conference paper at ICLR 2025
A variant where consider only three-cycle contributions to the curvature. For edge ~ j we have
AF AF,(1,)) d 311
A variant where we also consider the four-cycle contributions to this curvature. is important to note that, unlike the Balanced Forman curvature, the term [i. )) in AF4-as uniquely used in (Fesser & Weber, 2023) counts all four-cycles located at a given edge i ~ without obstructions on diagonals inside. For an edge ~ j we have
AFa(i,
d. dj t (f, (i,))
For all datasets we consider in this paper (see section 3 we computed the curvature distributions of the edges for all different definitions above. These can be found in Appendix [ From these distributions, we note the similar behaviour of BFc (and variants thereof) and JLc.
Curvature and oversquashing One global measure to identify potential bottlenecks in an undi- rected graph is given by the Cheeger constant. Small values indicate that the graph can be decomposed into two distinct sets of nodes with only few edges between those sets. Therefore, the Cheeger constant only non-zero for connected graphs. Due the well-known Cheeger inequality, the Cheeger constant can be approximated by the spectral gap. i.e. the first non-zero eigenvalue of the normalised Graph Laplacian. The latter has a lower computational cost. Both notions have been linked to oversquashing. It has been shown (Theorem 6 in (Topping al. 202T)) that diffusion-based methods (Gasteiger al. 2019) are limited in their ability to increase the Cheeger constant. In (Di Giovanni al. (023). the symmetric Jacobian obstruction between nodes is introduced as a measure of how well information can be exchanged between those nodes. Here, higher values indicate worse information flow and it is shown that the symmetric Jacobian obstruction is bounded by the inverse the Cheeger constant (Corollary 5.6 in (Di Giovanni et al. 2023)
There have also been attempts rewire based on targeted increase of the spectral gap (Karhadkar et al., (022). However, global measures such as the spectral gap do not convey information about the location of local bottlenecks and thus do not necessarily help to alleviate oversquashing. Here, discrete curvature measures have, allegedly, given us a local and computable metric to estimate this effect based on the graph topology itself. In (Fesser & Weber 2023). a bound on connections between the neighborhoods of nodes and j derived based on AF AFTii (Proposition 3.4 in (Fesser& & Weber )023)). However, this bound is in general not very strict and rather heuristic. In (Nguyen et al.] 2023). is shown edges ~ j with an Ollivier (Ricci) Curvature k(i, j) close to the minimum value of -2 cause oversquashing (Propostion 4.4 and Theorem 4.5 in (Nguyen et al.) 2023)). From (Topping et al. 2021) we know that x(i,,) Z BF j), and through the distribution of BFc in Appendix A we can see that most edges are far away from the lower limit of - of FFc (and therefore also k j)), This will play an important role in the next section.
The fundamental result connecting edges with a very negative Balanced Forman curvature to over- squashing is given in Topping al. (202I), where theorem 4 identifies negatively curved edges as sources of distorted information for a large set of nodes in the local neighbourhood of the given edge.
Theorem (Topping al. 2021)
Consider a MPNN as in Equation] Let ~ with d; S dj and assume that: the depth of the MPNN.
1. V S a and / < 3 with
2. There exists 8 such that 5
Pmaz for which Ric(i,j) -2+5
v (d.vdd))
Then there exists Qj S2) satisfying [Q, and for 0 50 s L-2 have
Oh (lo+2)
1
Σ
< (a.3)88
(8)
Q
Oh
REQ;
4

---

Published as a conference paper at ICLR 2025
Theorem 4 above gives reason to rewire the graph around negatively curved edges (adding triangles or four-cycles which give a positive contribution) as it increases the ó and therefore softens the bound in equation g In (Topping al. 202I), the set Qj is explicitly constructed as the neighbours of j that correspond to tree-like structure around the edge i ~ j and the Balanced Forman curvature gives us control over the information flow these neighbours from node i along the edge ~ j. The idea of the proof is to bound the left-hand side of equation byy second powers of the augmented normalised adjacency matrix (Axx)² and then to control these contributions with knowledge about the three- and four-cycles located at edge i j derived from the 8 bound. However, the question arises if the edges selected to be rewired during prepreeesssig indeed satisfy the conditions (specifically condition 2) of the theorem.
In the next sections, we will explore graph rewiring based on curvature measures in two ways. First, we look at how well Theorem can be applied to benchmark datasets by seeing if edges selected during rewiring are contributing to the bottleneck. Specifically, we look at whether these edges satisfy condition 2. In the second phase, we take a closer look at the performances that different curvature measures deliver. Instead of reporting one-off accuracies originating from parameter sweeps, take a look at the distribution of accuracies obtained when sweeping parameters.
2.3 GRAPH CURVATURE AND REWIRING
Graph rewiring In its core idea, graph rewiring techniques encompass recent efforts to decouple the input (true) graph from the graph used for computational tasks. The original message- pessagg-passingg paradigm (Gilmer et al. 2017) for GNNs used the input graph itself. By decoupling this input graph from the graph on which the computations are performed, which can take many forms, one can find alleviations for the oversquashing and -moothing problem mentioned in the previous section.
One can first look at ways to modify the message passing algorithm on the original graph, for example by sampling only certain nodes improve scalability (Hamilton et al. (2017), by considering multiple hops during message propagation (Abu-El-Haija et al. 2019] 2020 Zhu et al. 2020) or by changing the definition of a neighbour. This can be done either using shortest path distances (Abboud et al.
2022) or defining importance-basee neighbourhoods using random walks (Ying et al.) 2018).. A more drastic approach consists of changing the graph itself used for propagation, for example by pre-computing unsupervised node embeddings and using neighbourhoods defined by geometric relationships in the resulting latent space for the propagation (Pei et al.) 2019), by exchanging the adjacency matrix with a sparsified version of the generalised graph diffusion matrix S. by defining a new weighted and directed graph (Gasteiger et al. 2019), or by propagating messages along a personalised PageRank (Gasteiger al.) 2018).
In this paper, we focus on graph-rewiring techniques as follows: Given a graph G = (V,E), we
=(V, IE') for gressage-passing The set E" is constructed based on the discrete curvature measures discussed in the previous section. We treat rewiring as a pre- pre-processing
construct a new graph G' = -V,
task, similar to methods like SDRF (Topping al. 2021). BORF (Nguyen et al. 2023 FoSR
(Karhadkar et al. 2022). LASER (Barbero et al. 2023). G-RLEF or vDReW (Gutteridge et al. 2023
BENCHMARK DATASETS HAVE A LACK OF SUFFICIENTLY NEGATIVELY CURVED EDGES
In our experiments, we make exclusive use of the Stochastic Discrete Ricci Flow (SDRF) (Topping et al. 2021) algorithm for rewiring, which works in two steps. First, it selects the most negatively curved edge based on the curvature measure. Around this edge, all edges that can lead to three- cycles and four-cycles are considered, and for each candidate edge, the potential improvement of the curvature is computed. The edge to be added is then selected in a stochastic way, regulated by the temperature parameter T, where the probability is determined by the improvement the edge brings to the curvature of the original edge. Finally, SDRF also allows, at each iteration, the removal of (very) positively curved edges, determined by the threshold curvature value C+. Although different algorithms have been proposed, we only work with SDRF due to the simplicity of its approach, allowing us to look at the impact of the added edges more clearly.
5

---

Published as a conference paper at ICLR 2025
Looking at the condition from Theorem 4, now experimentally check if the edges in standard GNN benchmark datasets satisfy the necessary condition 2, which identifies the edge as an overssuashhig edge. The number of edges to be rewired is chosen from the hyperparameters given in (Topping) et al.) 2021). For each edge selected to he rewired (which is the most negative edge) we compute the upper threshold 8maz j) BFc j) + 2. For each of these edges, we then verify if this 8maz determined by the curvature is compatible with the condition
8<
V(d.dd) & 8
(Condition 2)
Tmar
which allows the theorem to identify the edge as a bottleneck in the derivation. From our results in Table [ we see that these conditions on ō are seldom satisfied by the graphs in the datasets. However, upon examining the derivation of the theorem, we find that the degree-based condition is too stringent. The inequality 0 < 5 < 1/v(d; V dj) is solely used to guarantee that 8 < 1/ža. and it is this condition that is subsequently used in the proof. In the second column of Table I we display the number of edges that satisfy the actual modified condition required.
& < $
(Condition 2b).
(10)
Ymaa
Since this bound is looser, we see that more selected edges satisfy the condition 2b, especially when look- ing at the citation graphs. However, these numbers imply that a part of the edges selected do not satisfy the con- ditions for Theorem 4, limiting their interpretation bottlenecks during message passing. Figure T shows in which step of SDRF (in % based on maximum number of iterations) the edges that do not satisfy condition 2b are selected to be rewired. Finally, we also note that edges do not satisfy condition 2b due to the three-cycle condition, as well as due the "maa upper limit (as shown by the edges below the dotted line). The figure shows as well that edges that do sat- isfy the condition are sometimes close to the upper bound of 1/4o. This again reduces their interpretation bottlenecks, the 8 bound on the Jacobian of the features is therefore looser. This temporal information for both types of edges tells us that this phenomenon occurs both at the beginning and the end, indicating that this is not saturation-tyl effect.
Table I: When an edge is selected by the SDRF algorithm, verify if this edge satisfies condition of Theorem (Eq, equation 9) Additionally, we check if the edge satisfies softer, but sufficient, version of condition 2 (Eq. equation [T)
Dataset
Edges rewired
Cond. 2 (%)
Cond. 2b (%)
Texas
89
0 (0%)
6 (6.7%)
Cornell
126
(0%)
15 (11.90%)
Wisconsin
136
(0%)
11 (8.09%)
Chameleon
2441
(0.16%)
141 (5.78%)
Actor
1000
11 (1.1%)
237 (23.70%
Squirrel
787
(0%)
34 (4.32%)
Cora
100
(0%)
68 (68.0%)
Citeseer
84
(0%)
24 (28.57%)
Pubmed
166
25 (15.06%)
116 (69.88%)
MUTAG
3497
(0%)
1228 16%)
PROTEINS
50936
(0%)
(14.
4 HYPERPARAMETER DEPENDENCY OF REWIRING
Graph rewiring algorithms depend quite some hyperparameters. The first category consists of training and GNNs hyperparameters: learning rate, hidden depth, hidden dimension, weight decay, and dropout. Additionally, there also the rewiring hyperparameters, which in the case of the SDRF algorithm are: max iterations (i.e. number of edges around which is rewired), temperature r, and threshold curvature C- While hyperparameter tuning is an important aspect of optimising models, we argue here that results in accuracy should not be the main judge for a new technique's performance, but one should consider the overall improvement over a wide array of hyperparameters. In this experiment, we perform parameter sweep over different benchmark graph datasets to evaluate curvature- based graph rewiring with different curvature notions.

---

Published as a conference paper at ICLR 2025
1.7 x 10"
Exx5
Comell
Wisconsin
Chamelcon
S
80
10-1
Squarrel
60
Deue
3.5 10
16 Puboped
12
MUTAG
PROTEINS
Once
10
2
D
2
0
Fa
b.
1.5 100
Texas
Camall
Wisconsin
Chameleon
Gove
6x 10-1
Squiraal
0
Actor
Cora
Cleeearr
60
Öyse
8
40
3.5 10-1
Gizu
f
20
109
Fd.
F6.
F6
Figure 1: visualisation of the edges selected during the SDRF rewiring algorithm. a, The panels show the edges that do not satisfy condition 2b, both due to 5 > 1/ta (if the edge is situated above the dotted line) 8 1/imaz (if the edge is situated below the dotted line). b, The panels show the opposite, namely the edges that satisfy condition 2b. This means that the edge is situated below edges indicates at which step of the rewiring
dotted line and 8 < 1 1/maaz- The color code process (in %) the edge is selected. Dotted line shows y 1/$2 corresponding to the upper limit in condition 2b.
Experimental setup To analyse the impact of different curvatures we ran modecclasiification tasks. For the node classification tasks used 9 datasets evaluate the different curvature notions: Texas, Cornell and Wisconsin from WebKB (University). Chameleon and Squirrel (Rozemberczki et al.) 2009). Cora (McCallum al. 2000), Citeseer (Sen 2008) and Pubmed Naamaaa et al. 2012). For graph classification we used MUTAG and PROTEINS (Morris et al. 2020). For each dataset only use the largest connected component, extracted with the algorithm provided in htt //tptt:////ttbb com jct//ccttssssso wotoos/unndzzee www.drstandiing-oon
2021), Actor (Tang
squashing While this implementation does not strictly adhere the mathematical definition of connected components for directed graphs (it returns neither the strong nor weak component), it was chosen to maintain consistency the number of nodes and edges, thus facilitating a fair comparison with other studies. Directed graphs were subsequently transformed to undirected.
Our hyperparameter grid is defined as: learning rate: [0.0001, 0.5555], number of layers: 2,,2,3) 3). layer width: {16, 32, 64, 128). dropout: [0.0001, 10001,0..50 0.5555), weight decay: [0.0001, 0.9999], C+: [0.2, 21.2]. r: [1, 500] and the max number of iterations is dataset dependent, where we take the lower and upper boundary to be 20% above and below the reported best hyperparameters from (Topping jet al. 202T). We perform a random-grid search with 800 iterations for datasets. Our evaluations follows (Gasteiger al. 2019). Each dataset is split into development set and test set with fixed
7

---

Published as a conference paper at ICLR 2025
seed. The development set is then split 100 times into validation and training set using the same seeds as in (Topping et al., (021). Each hyperparameter configuration then trained and evaluated validation sets. The reported accuracy is then the mean test accuracy over the 100 validation sets. We train the networks with early stopping, where the patience is 100 epochs of no improvement the validation set. We use GCN (Kipf & Welling 2016) for all datasets together with the Adam optimizer (Kingma & Ba (2114).
on each of the 100 traniin-validation
Curvature notions when rewiring graphs. For each dataset, we used each discrete curvature notion on graphs discussed in section rewire the graph in order assess possible SDRF as extensively as possible.
The question now arises as what the role is of different curvature measures
Results Figure 2 show the smoothed distributions (kernel density estimates), together with box-
enplots, of the average accuracy obtained per dataset for each rewiring measure. Additionally, we also look at the top 10% of the reported accuracies given by hyperparameters, which is presented in T To assess the robustness of the distributions we analysed how well the distribution saturates with increasing number of added iterations. We look at the evolution of the mean and standard deviation as iterations are added, as well as the Wasserstein distance metric between two distributions which include progressively more iterations. We performed this analysis for all datasets and show it in Appendix [E] From these results, we see that our sample of iterations is not unrepresentative of the expected performances and that the obtained distributions saturate, indicating that further runs would not majorly impact the performance distribution.
A first observation is that curvature measure consistently shifts the distribution of the accuracy away from the None distribution (meaning no rewiring) over all datasets. On some datasets, such as Cornell, Wisconsin or Actor we do notice that AFc based rewiring does provide better performance. However, these curvature definitions do not do this consistently for the other low homophily datasets such as Texas, Squirrel or Chameleon. We also see this behaviour when looking at the average of the top 10% results, where AFc c based rewiring does perform better than other variants but with a larger standard deviation. The improvement, taking into account the spread of the distributions is therefore not significant with respect to no rewiring. We can also note the similar performance of less-coe cosputatttaai intensive curvature measures (BFcs and AF Fey) in comparison with their more intensive variant Fc and AFc)).
test
Table 2: For each dataset we take the top 10% results from the hyperparameter sweeps and compute the average mean test accuracy obtained together with the standard deviation. For some datasets, the top 10% showed almost no variability which resulted in a standard deviation of (almost) 0.
Texas
Coreel
Wisconsin
Chamelcon
Cora
Citeseer
None
59.95 + 1.15
53.66
0.14
54.92 + 0.51
40.76 + 3.52
58.83 t 16.36
58.14 + 7.33
BFe
59.26 : 0.00
53.61
0.28
54.06 + 0.01
34.58 3.19
28.39 + 17.24
35.99 13.82
BFeg
59.26 = 0.00
53.59
0.12
54.06 + 0.01
30.93 0.10
21.86 08.75
30.35 12.03
Bmoo
59.26 = 0.00
53.68
0.43
54.91
1.72
31.60 2.04
27.73 13.08
44.16 12.46
JLc
59.26 + 0.00
53.57
0.01
54.06
+ 0.02
30.91
0.02
26.83 + 13.82
42.18 7.83
AFes
59.58 : 0.52
54.20
1.57
56.37
+ 1.60
36.93 1 5.14
59.25 + 14.83
60.11 + 6.30
AFcs
59.79 + 0.54
0.10 53.63
54.60 + 0.80
31.20 + 0.62
58.68 + 16.10
61.67 + 5.43
Pubmed
Actor
Squirre
MUTAG
PROTEINS
None
41.99 12.58
27.73 1 0.02
36.73
55.34 3.67
61.45 1.49
BFc
39.67 8.30
54.38 1.00
61.36 2 1.23
BFeg
40.97 #
27.73 0.02
0.56
54.45
2.25
61.16
BFemod
41.23 : 11.30
27.73
0.85
54.36 2.32
61.20
JLC
39.47 8.97
27.73
0..2
2.86
6.370
AFc3
42.74 + 12.91
28.00 + 0.93
1..8
54.63 2.91
61.22+000 0.45
AFca
41.40 + 12.65
28.14 + 1.02
35.64+1.40
64.54+2.0
61.27 + 1.02
is also interesting to note that rewiring can also negatively impacted the performance of a dataset, as seen by the larger spread for the citation networks. This could be due to rewiring non-suitable edges which introduces noise the graph by allowing the communication between nodes that should not. Secondly, when comparing the results from [T the distribution of BFc in Figure 2 we can see that the datasets with more edges that satisfy condition 2b do not perform better than other (e.g. Pubmed).
8

---

Published as a conference paper at ICLR 2025
Texas
Cornell
Wisconsin
Chameleon
Density
10
BFC
BFcg
Bod
DD
1000
JLc
AFc3
40
AFc4
Om
0000
None
00
0.4
0.2
0.4
0.6
0.2
0.4
0.6
0.3
0.5
Squirrel
Actor
Cora
Citeseer
Density
10a
10a
10a
BFC
KOOD
BFc3
COOD
EWOO
FFo
100
JLc
000000
OCB
3000
300
AFc3
OCDOD
AFc4
3TD OO
0
None
0.3
0.25
0.30
0.5
0.0
0.5
Density
10a
Pubmed
Density
10a
MUTAG
PROTEINS
10a
10
10
BFC
0
3000
BFO
6600
CG
BFcs
BFc:
OCGD
0
BFo
000
BFo
400
C+
JLc
3000
JLc
4 CD
AFc;
AFc;
CED
AFc4
1
AFc4
04
None
None
O00D
CB
0.4
0.8
0.7
0.7
Figure 2: Distribution of mean test accuracy over the sweep of hyperparameters for the different curvature measures and node-classification datasets used. We show boxenplots which first identify the median, then extend boxes outward, each covering half of the remaining data on which outliers (circles) are identifiable. For each dataset also show the smoothed distribution using kernel density estimates from the seaborn package.

---

Published as a conference paper at ICLR 2025
5 CONCLUSION
In our work, we have taken closer look at the effectiveness of graph-rewiring on (large-scale) graph datasets which are commonly used for benchmarking. Our results show that the conditions for over- squashing based on theorems proposed from the literature are not always met when considering these datasets. This implies that the edges selected during rewire do not necessarily cause oversquashing during message- g and that severe bottlenecks are in fact not present in these datasets. Although one might interpret oversquashing as a continuous phenomenon, these results suggest that it limited to specific graph topologies.
While graph rewiring can alleviate structural properties of graphs that cause information bottlenecks, thereby mitigating oversquashing. it also interacts intricately with other factors that influence the performance a GNN. There is an inherent trade-off between reducing oversquashing and enhancing oversmoothing Nguyen et al.] 2023 Fesser & Weber 2023). Additionally, rewiring can introduce noise, allowing nodes to access information they shouldn 't while improving overall information flow.
Moreover, enabling long-range interactions between nodes is only necessary for tasks that depend on those interactions. This explains why citation networks this paper, despite meeting theoretical bounds better than other datasets (see Table [], do not show performance improvements with rewiring. This is in line with previous research indicating that these tasks do not rely on long-range interactions (Alon & Yahav 2021). This dependency is measured by the homophily (Pei al. 2019), and Appendix C shows that citation networks have the highest homophily among the benchmark datasets, further strengthening this observation. For the other datasets, the low homophily indicates the necessity of long-range interactions, aligning with the observation that many edges fail to meet theoretical conditions, as shown in Table and therefore explaining the lack of performance gains for these datasets.
Our analysis is further substantiated by examining the role of hyperparameter sweeping when benchmarking curvature-based graph rewiring methods. We found that most performance gain is due to finding an optimal lyperparameter configuration rather than a structural shift in the performance, as illustrated by the distribution of performance in Figure 2 should take into consideration the dependency of their method on hyperparameters, both GNN and rewiring, when evaluating their performance.
We argue that future rewiring methods
Limitations and future work The results presented in this manuscript suggest several directions for future investigation while also facing some limitations. While the distributions shown above might be influenced by the hyperparameter grid used in our random search, focusing on the top 10% of results demonstrates that this influence is likely minimal. Our analysis tested the results for the SDRF algorithm from (Topping et al. (022), which is the most natural method for survature-based graph rewiring. It would be interesting to extend this investigation to other rewiring algorithms to validate similar claims. The theoretical analysis of the SDRF bounds indicates that the current bound,
|# | S 1, could potentially be replaced by a more general bound, ò | I S R with R > 1, as alluded to in Remark 15 of (Topping et al., 2021). However, this adjustment would further weaken the theoretical bounds established in Theorem 4. The curvature distributions provided in the appendix reveal that the edges are not negatively curved enough to create bottlenecks. Future work could involve developing real-world benchmark datasets that do suffer from bottlenecks to test whether the robust performance gains observed in synthetic data be replicated. Moreover, exploring the possibility of Theorem-aware rewiring, which involves only rewiring edges that meet theoretical conditions, could be beneficial. This approach should be tested on datasets that genuinely suffer from severe information bottlenecks, as indicated earlier.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENT
The resources and services used in this work were provided by the VSC (Flemish Supercomputer Center), funded by the Research Foundation Flanders (FWO) and the Flemish Government. Work at VUB was partially supported by the Research Foundation Flanders under Grants No. G032822N and No. GOK9322N.
REFERENCES
Ralph Abboud, Radoslav Dimitrov, and Ismail Ilkan Ceylan. Shortest path networks for graph property prediction. In Learning on Graphs Conference, pp. 5-1. PMLR, 2022.
Sami Abu-El-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 on machine learning. pp. 21-29. PMLR, 2019.
Sami Abu-EI-Haije Amol Kapoor, Bryan Perozzi, and Joonseok Lee. N-gen: Multi-scale graph convolution for semi-supervised node classification. Ryan P. Adams and Vibhav Gogate (eds.), Proceedings of The 35th Uncertainty in Artificial Intelligence Conference, volume 115 of Proceedings of Machine Learning Research, pp. 841-851. PMLR, 22-25 Jul 2020.
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations, 2021. URL https://opeerrviiee
net/ forum ?id= 80CPhOCVH2
Federico Barbero, Ameya Velingker, Amin Saberi, Michael M Bronstein, and Francesco Di Giovanni. Locality-aware graph rewiring in gnns. In The Twelfth International Conference on Learning Representations, 2023.
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- PMLR, 2023.
Jakub Bober, Anthea Monod, Emil Saucan, and Kevin N Webster. Rewiring networks for graph neural network training using discrete geometry. In International Conference on Complex Networks and Their Applications, pp. 226..36. Springer, 2023.
Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yuguang Wang, Pietro Lio, Guido F Montufar, and Michael Bronstein. Weisfeiler and lehman go cellular: Cw networks. Advances in neural information processing systems, 34:2625-2644 2021a.
Cristian Bodnar, Fabrizio Frasca, Yuguang Wang, Nina Otter, Guido F Montufar, Pietro Lio, and Michael Bronstein. Weisfeiler and lehman go topological: Message passing simplicial networks. In International Conference on Machine Learning, pp. 1036-003. PMLR, 2021b.
Michael M Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. arXiv preprint arXiv:2104. 13478, 2021.
Francesco Di Giovanni, Lorenzo Giusti, Federico Barbero, Giulia Luise, Pietro Lio, and Michael M Bronstein. On over-squashing in message passing neural networks: The impact of width, depth, and topology. International Conference on Machine Learning, pp.
PMLR, 2023.
Lukas Fesser and Mclanie Weber. Mitigating over-s moothhng and over-squashing using augmentations of forman-ricci curvature. In The Second Learning Graphs Conference, 2023.
Forman. Bochner's method for cell complexes and combinatorial ricci curvature. Discrete & Computational Geometry, 29:323-374, 2003.
Johannes Gasteiger, Aleksandar Bojchevski. and Stephan Günnemann. Predict then propagate:
Graph neural networks meet personalized pagerank. International Conference on Learning Representations, 2018.
11

---

Published as a conference paper at ICLR 2025
Johannes Gasteiger, Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph learning. Advances in neural information processing systems. 32, 2019.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pp- 1263-1272. PMLR, 2017.
Jhony H. Giraldo, Konstantinos Skianis, Thierry Bouwmans, and Fragkiskos D. Malliaros. On the trade-off between over- wwerssmoghing and over over-squa in deep graph neural networks. In Proceed- ings of the 32nd ACM International Conference on Information and Knowledge Management. CIKM '23, pp. 566-576, New York, NY, USA, 2023. Association for Computing Machinery. ISBN 9798400701245.
Benjamin Gutteridge, 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.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Jürgen Jost and Shiping Liu. Ollivier's ss ricci curvature, local clustering and curvature-dimension inequalities on graphs. Discrete & Computational Geomelry, 5 51(2):000-32, 2014.
Kedar Karhadkar, Pradeep Kr Banerjee, and Guido Montufar. Fosr: First-order spectral rewiring for addressing oversquashing gnns. In The Eleventh International Conference on Learning Representations, 2022.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6908 2014.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2016.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 3: 3:127-163, 2000.
Christopher Morris, Nils M Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. arXiv preprint arXiv:2007.08663, 2020.
Galileo Namata, Ben London, Lise Getoor, Bert Huang, and U Edu. Query-driver active surveying for collective classification. In 10th international workshop on mining and learning with graphs, volume 8, pp. 1, 2012.
Khang Nguyen, Nong Minh Hieu, Vinh Duc Nguyen, Nhat Ho, Stanley Osher, and Tan Minh Nguyen. Revisiting smor-smog and over-squashing using ollivier-ricci curvature. In International Conference on Machine Learning, pp. 25956-25979. PMLR, 2023.
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification, In International Conference on Learning Representations, 2019.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. In International Conference on Learning Representations, 2019.
Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Newworks, 9())cnabb14, 2021.
Areejit Samal, RP Sreejith, Jiao Gu, Shiping Liu, Emil Saucan, and Jürgen Jost. Comparative analysis of two discretizations of ricci curvature for complex networks. Scientific reports, 8(1):8650, 2018.
12

---

Published as a conference paper at ICLR 2025
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Iitassi-Rad. Collective classification in network data. Al magazine, 29(3):93 93, 2008.
RP Sreejith, Karthikeyan Mohanraj. Jürgen Jost, Emil Saucan, and Areejit Samal. Forman curvature for complex networks. Journal of Statistical Mechanics: Theory and Experiment, 2016(6):063206, 2016.
Qingyun Sun, Jianxin Li, Haonan Yuan, Xingcheng Fu, Hao Peng, Cheng Ji, Qian Li, and Philip S Yu. Position-awan structure learning for graph and over-squashing. In Proceedings of the 31 ACM International Conference Information & Knowledge Management, pp. 1848-1857, 2022.
by relieving under-reaching
Jie Tang, Jimeng Sun, Chi Wang, and Zi Yang. Social influence analysis in large-scale networks. In Knowledge Discovery and Data Mining, 2009. URL /api semanticscholaa.
org/CorpusID: 4931144
Jan Tönshoff, Martin Ritzert, Eran Rosenbluth, and Martin Grohe Where did the gap go? reassessing the long-range graph benchmark. Transactions on Machine Learning Research, 2024.
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, 2021.
Domenico Tortorella and Alessio Micheli. Is rewiring actually helpful in graph neural networks? arXiv preprint arXiv:2305. 2023.
Cameggi Mellon University. Webkb.
http::/www. cmu. www.leddudaafseeeee at///f///// cs. cmu. edu/
pzoject/theo-1//wet /ww.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
Melanie Weber, Emil Saucan, and Jürgen Jost. Coarse geometry of evolving networks. Journal of complex networks, 6(5):706-732, 2018.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Sim- plifying graph convolutional networks. In International conference on machine learning, pp- 6861-6877 PMLR, 2019.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 32(1):4-24 2021. doi: 10. (0.1109/TNNIS, w.t......02228888..
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? In International Conference on Learning Representations, 2018.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & daía mining, pp. 974-983, 2018.
Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang. Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applications. Al open, 1: 1:57-81, 2020.
Jiong Zhu. Yujun Yan. Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in neural information processing systems, 33:7793-7804, 2020.
13

---

Published as a conference paper at ICLR 2025
A
CURVATURE DISTRIBUTIONS
Texas
200
25
0
100
-1
2
-2
0
5
-
5
-2
Density
0.5
0.0
40
20
100
60
40
20
100
40
20
BFc
BFC3
BFCmod
JLc
AFCa
AFca
Figure 3: Distribution of curvatures for dataset Texas
Cornell
200
1
2
2
1
1
2
2
0
5
2
5
Density
0.5
0.0
-2
11
2
40
20
-100
-80
-60
-40
-20
-100
-80
-60
-40
-20
BFC3
BFCmod
JLc
AFC3
AFCa
Figure 4: Distribution of curvatures for dataset Cornell
14

---

Published as a conference paper at ICLR 2025
Wisconsin
50
100
-2
-1
-2
-1
-2
-1
-2
-1
-2
-2
0
5
-2
5
-2
Density
0.5
0.0
-2
-1
2
5
20
10
-100
60
400
-20
-100
-80
-60
-20
BFc
BFC3
BFCmod
JLc
AFC3
AFC4
Figure 5: Distribution of curvatures for dataset Wisconsin
Chameleon
1000
500
2
-1
-2
-1
-2
-2
-2
Density
0
1
2
3
200
-100
-50
50
2000
4000
6000
8000
BFc
BFCa
BFCmod
JLc
AFCa
AFCa
Figure 6: Distribution of curvatures for dataset Chameleon
15

---

Published as a conference paper at ICLR 2025
Cora
500
500
- -1
-2
-1
-1
-2
-1
-2
5
-2 0
5
-2 0
5
-2
Density
0.5
0.0
-2
-1
500
0
-100
-80
60
-40
-0
-100
-80
-60
40
-20
BFc
BFc3
BFCmod
JLc
AFC3
AFC4
Figure 7: Distribution of curvatures for dataset Cora
Citeseer
250
500
-
-1
2
-1
2
-1
-2
0
-2
Density
0.5
1
2
-100
-80
-60
-40
-20
-100
-80
-60
-40
-20
BFc
BFca
BFCmod
JLc
AFCa
AFCa
Figure 8: Distribution of curvatures for dataset Citeseer
16

---

Published as a conference paper at ICLR 2025
Pubmed
5000
5000
0
0
-2
5
-2
-2
-2
Density
1
-2
-1
0
1
2000
1000
0
100
80
40
20
100
80
60
40
20
BFc
BFC3
BFCmod
JLc
AFC3
AFCa
Figure 9: Distribution of curvatures for dataset Pubmed
Actor
5000
4000
0
2000
2
1
0
-2
0
5
-2
0
5
-2
5
-2
Density
0
-2
2
3
5
1000
500
0
-100
-80
-60
-40
-20
-100
-80
-60
-40
-20
0
BFc
BFC3
BFC
JLc
AFC3
AFCa
Figure 10: Distribution of curvatures for dataset Actor
17

---

Published as a conference paper at ICLR 2025
Squirrel
2500
-2
-1
-2 -1
-2
-1
-2
-1
-2
-2 0
5
-2
5
-2
Density
0.5
0.0
-2
-1
1
400
200
m0
0
1100
60
40
-20
-100
-80
-60
-20
BFc
BFC3
BFCmod
JLc
AFC3
AFC4
Figure 11: Distribution of curvatures for dataset Squirrel
B ON THE IMPLEMENTATION OF THE BALANCED FORMAN CURVATURE
During the setup of our experiment, we noticed that the implementation the Balanced Forman eurvature provided by the authors of Topping al. (202T) under //6 qå thub. com/ cct /wtp/unndsssseeeee wandinngggnno oeroovurruuuhhhhoo does match the theoretical definition presented in their paper (Definition I in Topping et al. ()021)). More precisely, the issue for a given edge ~ evolves around the terms corresponding to the four-cycle contributions, i.c. |+ | and Imaz. The degree d, and d, of the involved nodes and the number of triangles (i, are calculated correctly. However, even for the sample graph provided Figure. 3 in Topping et al. (202T) (Figure 12 here) the publicly available implementation produces demonstrably wrong results. The four-cycle contribution computed illustrated in the code below with sharp.y lambda;; 7max-
https:
Figure Sample graph provided in Figure. 3 in Topping et al.) (2021)
12:
| 1-
If consider the edge 0 1 of the sample graph in Figure 12 and using the definition of the Balanced Forman curvature, Eq. equation 2 we find BFc(0, 0.10. In contrast, when using the publicly available code we find BF
0.08.
To control that our computation of BFc was correct we implemented with the NetworkX library the set- theoretical definition (evolving around the 1-hop neighbourhoods (i) and (j) of the involved nodes) provided in Definition in Topping et al. 2021). These are
1. AA = (1) n (() are the triangles based at i ~ j-
2. # (i.)) == {k E (1) k + j: Eo E (K) n Si() (5) are the neighbours
i forming 4-cycle based the edge ~ j without diagonals inside.
3. mmax (i. ( is the maximal number of four-cycles based at i ~ traversing a common node
Additionally, we used Remark 10 from Topping et al. (202 to calculate the four-cycle contribution and in particular 7man- Our CUDA implementation of BFc then controlled with the Networkx implementation. Both our implementations are available in our code.
18

---

Published as a conference paper at ICLR 2025
Listing 1: Code snippet from Topping et al. (2021) compute the 4-cycle contribution of the BFc
// 4-cycle contribution for k in range (N)
TMP A[k, j] (A2 k]-Ali, k]) A[i, 51
if TMP
sharp_it ij +=
it TMP lambda ij:
lambda_i] - TMP
TMP AlI, k] (A2 [k, 5k-Alk, j1} ACI, 51
is TMP > 0:
sharp ij += if TMP lambda ij: lambda_is _ij TMP
cli, 31 = (12 / d_ax) + (2 / d_min) - 2 + (2 / d_ax + 1 dmin) A2lL, 11, il A[1, 11
if lambda_is _jj 0:
c(i, il +- sharp_ij / max lambda_ig _ij)
C DATASETS
If the dataset connected disconnected components report the statistics for the largest connected component selected. The homophily index H(G) defined by Pei et al. (2019) defined as
Number of 's neighbors who have the same label Number of 's neighbors
H(G)=
(11)
V
DEV
Texas
Comell
Wisconsin
Chamelcon
Squirrel
Actor
Cora
Citeseer
Pubmed
H())
0.06
0.11
0.16
0.25
0.24
0.22
0.83
0.72
0.79
Nodes
135
140
184
832
2186
4388
2485
2120
19717
Edges
251
219
1703
12355
65224
21907
5069
3679
44324
Features
1703
1703
1703
2323
2089
931
1433
3703
500
Classes
5
5
5
6
Directed?
Yes
Yes
Yes
Yes
Yes
Yes
No
No
No
D HARDWARE SPECIFICATIONS
Our experiments were performed on a HPC server with nodes containing the following components:
GPUs per node
GPU memory
processors per node
CPU memory
local disk
network
Nvidia A100
16-core EPYC
256 Gh
TB SSD
EDR-IB
2 x Nvidia Tesla P100
16 Gb
2x 12-core INTEL E5-2650v4
256 Gb
TB HDD
10 Gbps
19

---

Published as a conference paper at ICLR 2025
E SATURATION ANALYSIS OF DISTRIBUTIONS
Texas
Cornell
Density
10
33%
(66%)
100%)
10a
33%
(6%%)
100%)
10a
10a
0.4
0.4
0.6
0.25
0.50
0.25
0.50
0.25
0.50
Mean Test Accuracy
Mean Test Accuracy
0y 1000
10
10
10"4
10-
0.575
#x
0.550
0.500
0.050
0.050
0.025
0.025
100
20
Iterations included
Iterationn included (x)
Figure 13: Saturation analysis for datasets Texas and Cornell (a.-d.) Distribution the obtained mean test accuracy when including 33%, 66%, and 100% of the total hyperparameters runs. (e.) Evolution of the Wasserstein distance between two subsequent distributions that include x% of the total hyperparameter iterations. (f., g.) Mean and standard deviation when including x % of the total iterations.
Wisconsin
Chameleon
Density
33%
66%)
(100%)
10²
8.
(33%)
b.
(66%)
c. (100%)
10
10
10a
0.25
0.50
0.25
0.50
0.25
0.50
0.3
0.4
0.5
0.3 0.4
0.5
0.3 0.4
Accuracy
Mean Test Accuracy
bx 3. (x)
10-2
10-2
10-3
10-4
10-4
0.33
0.500
0.32
0.475
0.31
0.075
9.
0.05
0.050
0.025
20
40
60
80
100
0
20
40
60
80
100
% of [terations included (x)
% of iterations included (x)
Figure 14: Saturation analysis for datasets Wisconsin and Chameleon (a.-d.) Distribution of the obtained mean test accuracy when including 33%, 66%, and 100% of the total hyperparameters runs. (e.) Evolution of the Wasserstein distance between two subsequent distributions that include 2% of the total hyperparameter iterations. (f., g.) Mean and standard deviation when including x% of the total iterations.
20

---

Published as a conference paper at ICLR 2025
Squirrel
Actor
Density
10'
(33%)
(66%)
(100%)
10a
(33%)
(66%)
(100%)
20a
10a
10a
100
0
M
0.350.40
0.276.300 3250..5.
Mean Test Accuracy
Mean Test Accuracy
Wi 1,(x)
10-3
10
10-5
0.350
0.277
0.345
0.276
0.005
0.01
0.00
0.000
20
40
60
80
100
20 40
80
100
of Iterations included
Iterations included (x)
Figure 15: Saturation analysis for datasets Squirrel and Actor (a.-.)) Distribution of the obtained mean test accuracy when including 33%, 66%. and 100% of the total hyperparameters runs. (e.) Evolution of the Wasserstein distance between two subsequent distributions that include x% of the total hyperparameter iterations. (f., g.) Mean and standard deviation when including x% of the total iterations.
Pubmed
(33%)
(66%)
(100%)
Density
10a
10a
0.250.500.750.
00..2555...5..2220 500.75
Mean Test Accuracy
10-2
w,tx
10-3
10-4
0.36
Ux
0.05
0.00
20
40
60
100
Iterations included
Figure 16: Saturation analysis for dataset Pubmed (a.-d.) Distribution of the obtained mean test accuracy when including 33%, 66%, and 100% of the total hyperparameters runs. (c.) Evolution of the Wasserstein distance between two subsequent distributions that include x% of the total hyperparameter iterations. (f., g.) Mean and standard deviation when including 2% of the total iterations.
21

---

Published as a conference paper at ICLR 2025
MUTAG
PROTEINS
Density
107
(33%%)
(66%)
(100%)
10a
16%%)
100%)
100
10a
0.6
0.7
0.7
1.550.00.65
0.7
0.6
Mean Test Accuracy
Mean Test Accuracy
0x 1,000)
10:2
10
10-3
10-4
10-4
0.55
0.595
0.015
0.025
0.000
0.010
100
20
Iterations included
iterations included (x)
Figure 17: Saturation analysis for datasets MUTAG and PROTEINS (a.-d.) Distribution of the obtained mean test accuracy when including 33%, 66%, and 100% of the total hyperparameters (e.) Evolution of the Wasserstein distance between two subsequent distributions that include x% of the total hyperparameter iterations. (f., g.) Mean and standard deviation when including x% of the total iterations.
22


Reviews:
[{"review_id": "jHUmwME3p8", "reviewer": "Reviewer_VNfT", "summary": "This paper investigates the effectiveness of curvature-based rewiring in mitigating bottlenecks in graph machine learning tasks. It argues that the theoretical conditions for edges being considered as bottlenecks are not necessarily satisfied for edges being modified in practice. It further argues that the superior performance of some existing methods is likely due to hyperparameter selection rather than systematic improvement.", "questions": "1) It is unclear whether any dataset in Table 1 would possess bottlenecks that hinder (in particular long-range) interactions that might be necessary for the task (in some sense this is also a limitation of the experiments in Topping et al. 2022), which is one of the main reasons why curvature-based rewiring was proposed in the first place. Therefore the analyses presented in this paper are, albeit interesting and pointing towards the right direction, not entirely surprising. This has been briefly discussed in Section 5, but it might be helpful if the authors can conduct experiments on datasets are may possess long-range interactions, for example the ones described in Dwivedi et al. (https://arxiv.org/abs/2206.08164). Note that the suitability of these datasets are themselves under active debate (see https://arxiv.org/abs/2309.00367), nevertheless they might be more appropriate than the datasets chosen in the paper.\n\n2) The experiments are mostly based on a single rewiring technique and a single GNN model, i.e., the GCN. While this is reasonable starting point, for a more comprehensive evaluation and conclusive evidence, more rewiring methods and GNN models (e.g., GraphSage, ChebNet, or GIN) should be tested. I appreciate the former is recognised as a limitation of the current work, but it makes it less clear how generalisable the findings are.\n\n3) I don’t think homophily is the only factor that determines the long-rangeness of the task. It should depend on the graph topology (e.g., diameter), node features, and the nature of the task as well. Although this is not necessarily the focus of the paper, discussion about this can be made more precise.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1) The paper takes a careful look at some of the curvature-based methods proposed in the literature and examines whether theoretical conditions match empirical practice. From this perspective, the paper represents a move towards the right direction in evaluation of graph machine learning methods.\n\n2) Detailed description of experimental setup provides helpful guideline for future research in terms of conducting rigorous empirical evaluation. The argument on hyperparameter selection is interesting and points to the importance of a probabilistic view in performance evaluation.\n\n3) The paper is clearly motivated and generally well written. The visualisations are helpful to aid understanding.", "weaknesses": "1) As discussed in the paper briefly, I don’t feel the datasets being tested are the most appropriate ones (see Questions below). This makes the findings less surprising and not entirely convincing (although in fairness this is probably a limitation of previous methods as well).\n\n2) Given that this is a paper on empirical validation, experiments should perhaps be done on more than one rewriting method and one single GNN model.", "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": "C4A1Sg7JPN", "reviewer": "Reviewer_dc59", "summary": "This paper revisits the effectiveness of curvature-based graph rewiring techniques on real-world datasets. The authors reveal that the identified bottlenecked edges are not in line with theoretical criteria identifying bottlenecks, which thus do not necessarily oversquash the information. Furthermore, the authors demonstrate that the improved accuracies of rewiring techniques on these datasets are outliers originating from sweeps of hyperparameters—both the ones for training and dedicated ones related to the rewiring algorithm—instead of consistent performance gains. They further nuances the effectiveness of curvature-based rewiring in real-world datasets and bring a new perspective on the methods to evaluate GNN improvements", "questions": "No further questions beyond weaknesses", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. This paper reveals an important issue in the evaluation of graph rewiring techniques, especially for curvature-based graph rewiring.\n2. The theoretical analysis is thorough and solid.", "weaknesses": "1. The analysis and empirical study are specific to the curvature-based method (Topping et al., 2021).\n2. As the over-squashing issue is highly related to the long-range dependency, the work doesn't include the long-range graph benchmark (Dwivedi et al., 2022), which a bit weakens the study and analysis.\n3. The analysis is only on GCN (Kipf & Welling, 2016). It will be more comprehensive to include other widely used MPNNs, e.g., GraphSAGE (Hamilton et al., 2017), GatedGCN (Bresson & Laurent, 2018), GAT (Veličković et al., 2018). This can help better understand the impact of MPNNs on the performance of graph rewiring techniques. \n\n\n\n\n\n\n\n\n\n------- \n- Dwivedi, V. P., Rampášek, L., Galkin, M., Parviz, A., Wolf, G., Luu, A. T., & Beaini, D. (2022). Long Range Graph Benchmark. _Adv. Neural Inf. Process. Syst. Track Datasets Benchmarks_.\n- Bresson, X., & Laurent, T. (2018). Residual Gated Graph ConvNets. In _arXiv:1711.07553_.\n- Hamilton, W., Ying, Z., & Leskovec, J. (2017). Inductive Representation Learning on Large Graphs. _Adv. Neural Inf. Process. Syst._, _30_. \n- Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., & Bengio, Y. (2018). Graph Attention Networks. _Proc. Int. Conf. Learn. Represent._", "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": "Kw701IOaR9", "reviewer": "Reviewer_UNSN", "summary": "This paper reconsiders the effect of rewiring according to curvature on GNN effects. Through a large number of experiments, it points out that the rewiring does not meet the identification criteria of the message-passing bottleneck in the figure, and the effect is not significantly improved under a large number of hyperparameter attempts.", "questions": "1. Can the author provide a comparison of experimental results without using edges? (an MLP with the same number of layers) In general, in a node classification task, node characteristics play a crucial role in the classification effect, often sometimes the role of edges is not obvious.\n2. For Other questions please see Weaknesses.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. This article gives a very detailed introduction to curvature rewiring, which is very helpful for readers who are new to the field to understand the work.\n2. This paper explains the bottleneck conditions of curvature rewiring from the theoretical point of view and verifies the effect of various methods through experiments, which is very convincing.\n3. The paper proves its point through a large number of experiments, which show that the existing methods are ineffective in solving the problem.", "weaknesses": "1. The author merely presents a problem, not a solution to it.  The work lacks sufficient integrity.\n2. There are some problems with the selection of datasets. For example, MUTAG and PROTEIN, which are themselves molecules and proteins, have biochemical implications. Therefore, performance may not be significantly improved after rewiring. For different areas of graph data, we need to be more profound.\n3. The baseline of the experiment needs to be increased. In the task of node classification, the importance of node characteristics is very important. Therefore, the authors need to add an MLP as a baseline. If you can't explain the effectiveness of the edge in this task, then you can't fully explain the problem of rewiring.\n\nOverall, I found this paper a very theoretically solid work. I would like to reconsider my score if my concerns could be addressed.", "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": "Tc7Wqw4qmS", "reviewer": "Reviewer_GwmN", "summary": "The paper revisits the effectiveness of curvature-based rewiring in Graph Neural Networks, focusing on its role in alleviating the over-squashing problem. In GNNs, message passing can suffer from information bottlenecks, where messages get compressed, leading to worse downstream performance. Curvature-based rewiring, which involves modifying the graph’s structure to improve information flow, has been proposed as a solution. This paper reevaluates its performance on real-world datasets.\n\nThe authors find that in real-world scenarios, the edges selected during the rewiring process do not align with theoretical predictions about bottlenecks, suggesting that the over-squashing issue may not be as prevalent in these datasets. Furthermore, the paper argues that state-of-the-art results from curvature-based rewiring often stem from hyperparameter tuning rather than consistent performance improvements. The study questions the practical benefits of curvature-based rewiring for GNNs and calls for a more nuanced evaluation of GNN improvements.", "questions": "Could the authors explain why they focus on the theoretical results related to SDRF and not the ones related to BORF, another curvature-based method? Their theoretical results seem less restrictive than what’s presented in the SDRF paper, so I'm wondering what an analogue of Table 1 could look like in this context.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- Clear motivation: The paper has a clear motivation to revisit and critically evaluate the effectiveness of curvature-based rewiring in Graph Neural Networks, and to specifically test whether the theoretical justifications for these methods are genuinely applicable to real-world datasets.\n- Extensive experiments: The authors conduct a thorough experimental analysis, testing various curvature measures and examining their effects on node and graph classification tasks. They scrutinize both the theoretical underpinnings and the practical outcomes of rewiring, demonstrating that the edges selected by the rewiring process do not always correspond to bottleneck points. Additionally, they show that state-of-the-art performance is often a result of hyperparameter tuning rather than inherent benefits from rewiring.", "weaknesses": "- Presentation: pages 8 and 9 could benefit from some reorganization, for example by better integrating table 2 and figure 2 into the text. Table 2 could also benefit from the best-performing setting being highlighted. I also find Figure 3 hard to read: perhaps it would be better to split the figure in two, i.e. have one figure with the curvature distributions and one with the mean test accuracies.\n- More nuanced discussion: while this may be a minor point, I would suggest that the authors include a sentence or two about the role of curvature in graph machine learning more broadly in their discussion section, for example by referring to [1]. While I welcome that the paper pushes back against curvature-based rewiring and consider it good science, this does not mean that curvature is generally not useful for GNNs.\n- Long-range datasets: again a minor point, but additional graph-level datasets would further strengthen the paper's message. The authors could, for example, look at Peptides-func and Peptides-struct in the LRGB datasets [2].\n\n[1] Fesser, Lukas, and Melanie Weber. \"Effective Structural Encodings via Local Curvature Profiles.\" The Twelfth International Conference on Learning Representations.\n\n[2] Dwivedi, Vijay Prakash, et al. \"Long range graph benchmark.\" Advances in Neural Information Processing Systems 35 (2022): 22326-22340.", "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)