The Effectiveness of Curvature-Based Rewiring and the Role of Hyperparameters in GNNs Revisited

## Abstract

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, 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 improvements.

## 1 Introduction

Machine learning on graph data, and more specifically Graph Neural Networks (GNNs), has undergone rapid development over the past few years. Both in terms of architecture variations (Wu et al., ; Kipf & Welling, ; Veličković et al., ; Hamilton et al., ) as theoretical understanding (Xu et al., ; Bronstein et al., ; Bodnar et al., , ). 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., ; Wu et al., ). The basis of the message passing paradigm of GNNs (Gilmer et al., ) rests on the idea of information diffusion
where messages, namely the node’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 a node, i.e., the number of nodes it can receive information from, depends on the number of layers of the GNN. A low number of layers can cause under-reaching (Sun et al., ) where required information does not reach the nodes. On the other hand, if a node’s receptive field is too large, this can lead to oversmoothing (Li et al., ; Oono & Suzuki, ), where node representations are homogenised due to subsequent message passing.

Recently, a lot of attention has been drawn to the problem of oversquashing (Alon & Yahav, ) where structural properties of the graph called bottlenecks cause a loss of information as the messages passing through get too compressed. Research efforts have therefore focused on understanding this phenomenon (Di Giovanni et al., ; Black et al., ) as well as on ways to alleviate it. The most pragmatic approach consists of rewiring, i.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 curvatures on graphs can be used to detect the location of bottlenecks, allowing for the development of algorithmic rewiring methods such as Stochastic Discrete Ricci Flow (Topping et al., ). While this point of view was presented first in (Topping et al., ), other definitions of curvatures such as Jost and Liu Curvature (Giraldo et al., ; Jost & Liu, ) or Augmented Forman Curvature (Fesser & Weber, ) have been proposed as alternative measures (Bober et al., ). Despite that fact that work on synthetic datasets (Di Giovanni et al., ; Black et al., ) does indicate the occurrence of oversquashing, we here nuance these results on benchmark datasets and reevaluate the performance gains of curvature-based rewiring.

#### Contribution

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 Tortorella & Micheli () which evaluates rewiring performances on training-free GNNs and shows that rewiring rarely confers a practical benefit for message-passing 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 to real-world datasets. Additionally, we explain the occurrence of the 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., ). 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.

#### Outline

In section 2 we introduce the theoretical relation between curvature and bottlenecks in graphs. Section 3 experimentally verifies this condition in standard datasets, where we find that most rewired edges are not necessarily responsible for oversquashing. With this nuanced perspective on the theory underlying the rewiring algorithm, we evaluate the performance gains possible due to rewiring in section 4. When comparing performances of all curvature definitions with the performance obtained when implementing no rewiring at 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=(\mathbb{V},\mathbb{E})$ identified by a set $\mathbb{V}$ of nodes, which are described by a feature vector $\mathbf{x}_{i}\in\mathbb{R}^{n_{0}}$ with $i\in\mathbb{V}$, and a set of edges $\mathbb{E}\subset\mathbb{V}\times\mathbb{V}$. The adjacency matrix, which describes the connection of the graph, is denoted by A.

#### Graph Neural Networks

Given the graph $G$ as described as above, we write $\mathbf{h}^{(l)}_{i}$ the representation of node $i$ at layer $l$, where $\mathbf{h}^{0}_{i}=\mathbf{x_{i}}$. Given layer dependent, differentiable functions $\phi^{l}:\mathbb{R}^{n_{l}}\times\mathbb{R}^{n^{\prime}_{l}}\rightarrow\mathbb
{R}^{n_{l+1}}$ and $\psi^{l}:\mathbb{R}^{n_{l}}\times\mathbb{R}^{n_{l}}\rightarrow\mathbb{R}^{n^{
\prime}_{l}}$, we write the message passing function as

$$ $\mathbf{h}_{i}^{(l+1)}=\phi^{l}\bigg{(}\mathbf{h}_{i}^{(l)},\sum_{j=1}^{n}\hat {\textbf{A}}_{ij}\psi^{l}\left(\mathbf{h}_{i}^{(l)},\mathbf{h}_{j}^{(l)}\right )\bigg{)}\,.$ (1) $$

Here, $\hat{\textbf{A}}$ denotes the normalised augmented adjacency matrix, i.e. the adjacency matrix A is augmented by self-loops $\tilde{\textbf{A}}=\textbf{A}+\textbf{I}$ and then normalised by $\tilde{\textbf{D}}=\textbf{D}+\textbf{I}$, where D denotes the diagonal degree matrix. More precisely, we have $\hat{\textbf{A}}=\tilde{\textbf{D}}^{-\frac{1}{2}}\cdot\tilde{\textbf{A}}\cdot
\tilde{\textbf{D}}^{-\frac{1}{2}}$.

### 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-cycles 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 in 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\sim j$. We denote by $d_{i}$ the degree of node $i$ and by $d_{j}$ the degree of node $j$. The common neighbours of node $i$ and node $j$ are denoted by $\sharp_{\triangle}(i,j)$. They correspond to the triangles located at edge $i\sim j$. The neighbours of $i$ (resp. $j$) that form a four-cycle based at $i\sim j$ without diagonals inside are denoted by $\sharp_{\square}^{i}$ (resp. $\sharp_{\square}^{j}$) and the maximum number of four-cycles without diagonals inside that share a common node is denoted by $\gamma_{max}$. We denote by $x\vee y\doteq\mathrm{max}(x,\>y)$ (resp. $x\wedge y\doteq\mathrm{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., ) and variations thereof:

- •
Balanced Forman Curvature: For an edge $i\sim j$ we have $BFc(i,j)=0$ if $\min(d_{i},d_{j})=1$ and otherwise
$BFc(i,j)=\frac{2}{d_{i}}+\frac{2}{d_{j}}-2+2\frac{|\sharp_{\triangle}(i,j)|}{d
_{i}\vee d_{j}}+\frac{|\sharp_{\triangle}(i,j)|}{d_{i}\wedge d_{j}}+\frac{
\left(|\sharp_{\square}^{i}|+|\sharp_{\square}^{j}|\right)}{\gamma_{max}(d_{i}
\vee d_{j})}\,.$
(2)
- •
Balanced Forman Curvature (without four-cycles): Determining the number of four-cycles without diagonals inside is a 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\sim j$ we have $BFc_{3}(i,j)=0$ if $\min(d_{i},d_{j})=1$ and otherwise
$\displaystyle BFc_{3}(i,j)=\frac{2}{d_{i}}+\frac{2}{d_{j}}-2+2\frac{|\sharp_{
\triangle}(i,j)|}{d_{i}\vee d_{j}}+\frac{|\sharp_{\triangle}(i,j)|}{d_{i}
\wedge d_{j}}\,.$
(3)
- •
Modified Balanced Forman Curvature: The original code implementation provided in Topping et al. () 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 $i\sim j$ we have $BFc_{mod}(i,j)=0$ if $\min(d_{i},d_{j})=1$ and otherwise
$\displaystyle BFc_{mod}=\frac{2}{d_{i}}+\frac{2}{d_{j}}-2+2\frac{|\sharp_{
\triangle}(i,j)|}{d_{i}\vee d_{j}}+\frac{|\sharp_{\triangle}(i,j)|}{d_{i}
\wedge d_{j}}+\mathcal{O}\left(|\sharp_{\square}^{i}|+|\sharp_{\square}^{j}|
\right)\,.$
(4)

Secondly, we consider JLc (Jost and Liu) Curvature(Jost & Liu, ). For an edge $i\sim j$ we have, with $s_{+}\doteq\max(s,0)$,

$$ $\displaystyle JLc(i,j)=-\left(1-\frac{1}{d_{i}}-\frac{1}{d_{j}}-\frac{|\sharp_ {\triangle}(i,j)|}{d_{i}\wedge d_{j}}\right)_{+}-\left(1-\frac{1}{d_{i}}-\frac {1}{d_{j}}-\frac{|\sharp_{\triangle}(i,j)|}{d_{i}\vee d_{j}}\right)_{+}+\frac{ |\sharp_{\triangle}(i,j)|}{d_{i}\vee d_{j}}\,.$ (5) $$

Finally, we consider the Augmented Forman Curvature used for rewiring in (Fesser & Weber, ). Originally, the Forman curvature was introduced in (Forman, ) as a discrete analogue of the Ricci curvature that aims to mimic the Bochner–Weitzenböck 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 at most consist of one lower-dimensional cell). It was then adapted to graphs (Sreejith et al., ) and augmented to also include two dimensional cells such as triangles (Weber et al., ; Samal et al., ). The Augmented Forman curvature comes in two variants.

- •
A variant where we consider only three-cycle contributions to the curvature. For an edge $i\sim j$ we have
$\mathcal{AF}_{3}(i,j)=4-d_{i}-d_{j}+3|\sharp_{\triangle}(i,j)|\,.$
(6)
- •
A variant where we also consider the four-cycle contributions to this curvature. It is important to note that, unlike the Balanced Forman curvature, the term $\square(i,j)$ in $\mathcal{AF}_{4}$—as uniquely used in (Fesser & Weber, )—counts all four-cycles located at a given edge $i\sim j$ without obstructions on diagonals inside. For an edge $i\sim j$ we have
$\displaystyle\mathcal{AF}_{4}(i,j)=4-d_{i}-d_{j}+3|\sharp_{\triangle}(i,j)|+2
\square(i,j)\,.$
(7)

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 A. 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 undirected graph is given by the Cheeger constant. Small values indicate that the graph can be decomposed into two distinct sets of nodes with only a few edges between those sets. Therefore, the Cheeger constant is only non-zero for connected graphs. Due to 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 et al., )) that diffusion-based methods (Gasteiger et al., ) are limited in their ability to increase the Cheeger constant. In (Di Giovanni et al., ), the symmetric Jacobian obstruction between two 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 of the Cheeger constant (Corollary 5.6 in (Di Giovanni et al., )).

There have also been attempts to rewire based on a targeted increase of the spectral gap (Karhadkar et al., ). 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, ), a bound on connections between the neighborhoods of nodes $i$ and $j$ is derived based on $\mathcal{AF}_{4}-\mathcal{AF}_{4}^{\text{min}}$ (Proposition 3.4 in (Fesser & Weber, )). However, this bound is in general not very strict and rather heuristic. In (Nguyen et al., ), it is shown edges $i\sim j$ with an Ollivier (Ricci) Curvature $\kappa(i,j)$ close to the minimum value of $-2$ cause oversquashing (Propostion 4.4 and Theorem 4.5 in (Nguyen et al., )). From (Topping et al., ) we know that $\kappa(i,j)\geq BFc(i,j)$, and through the distribution of $BFc$ in Appendix A we can see that most edges are far away from the lower limit of $-2$ of $BFc$ (and therefore also $\kappa(i,j))$. This will play an important role in the next section.

The fundamental result connecting edges with a very negative Balanced Forman curvature to oversquashing is given in Topping et al. (), 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 4 above gives a reason to rewire the graph around negatively curved edges (adding triangles or four-cycles which give a positive contribution) as it increases the $\delta$ and therefore softens the bound in  equation 8. In (Topping et al., ), the set $Q_{j}$ is explicitly constructed as the neighbours of $j$ that correspond to tree-like structure around the edge $i\sim j$ and the Balanced Forman curvature gives us control over the information flow to these neighbours from node $i$ along the edge $i\sim j$. The idea of the proof is to bound the left-hand side of  equation 8 by second powers of the augmented normalised adjacency matrix $(\hat{\textbf{A}}_{ik})^{2}$ and then to control these contributions with knowledge about the three- and four-cycles located at edge $i\sim j$ derived from the $\delta$ bound. However, the question arises if the edges selected to be rewired during pre-processing 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 4 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, we 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-passing paradigm (Gilmer et al., ) 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 -smoothing 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 to improve scalability (Hamilton et al., ), by considering multiple hops during message propagation (Abu-El-Haija et al., , ; Zhu et al., ) or by changing the definition of a neighbour. This can be done either using shortest path distances (Abboud et al., ) or defining importance-based neighbourhoods using random walks (Ying et al., ). 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., ), by exchanging the adjacency matrix with a sparsified version of the generalised graph diffusion matrix $\mathbf{S}$, by defining a new weighted and directed graph (Gasteiger et al., ), or by propagating messages along a personalised PageRank (Gasteiger et al., ).

In this paper, we focus on graph-rewiring techniques as follows: Given a graph $G=(\mathbb{V},\mathbb{E})$, we construct a new graph $G^{\prime}=(\mathbb{V},\mathbb{E}^{\prime})$ for message-passing. The set $E^{\prime}$ is constructed based on the discrete curvature measures discussed in the previous section. We treat rewiring as a pre-processing task, similar to methods like SDRF (Topping et al., ), BORF (Nguyen et al., ), FoSR (Karhadkar et al., ), LASER (Barbero et al., ), G-RLEF or $\nu$DReW (Gutteridge et al., ).

## 3 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., ) 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 $\tau$, 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.

Looking at the condition from Theorem 4, we now experimentally check if the edges in standard GNN benchmark datasets satisfy the necessary condition 2, which identifies the edge as an ‘oversquashing’ edge. The number of edges to be rewired is chosen from the hyperparameters given in (Topping et al., ). For each edge selected to be rewired (which is the most negative edge) we compute the upper threshold $\delta_{max}(i,j)=BFc(i,j)+2$. For each of these edges, we then verify if this $\delta_{max}$ determined by the curvature is compatible with the condition

$$ $\delta<\frac{1}{\sqrt{(d_{i}\vee d_{j}})}~{}\text{ \& }~{}\delta<\frac{1}{ \gamma_{max}}~{}~{}\text{(Condition 2)}$ (9) $$

which allows the theorem to identify the edge as a bottleneck in the derivation. From our results in Table 1, we see that these conditions on $\delta$ 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<\delta<1/\sqrt{(d_{i}\vee d_{j})}$ is solely used to guarantee that $\delta\leq 1/\sharp_{\triangle}$, and it is this condition that is subsequently used in the proof. In the second column of Table 1, we display the number of edges that satisfy the actual modified condition required.

$$ $\delta\leq\frac{1}{\sharp_{\triangle}}~{}\text{ \& }~{}\delta<\frac{1}{\gamma_ {max}}~{}~{}\text{(Condition 2b)}\,.$ (10) $$

Since this bound is looser, we see that more selected edges satisfy the condition 2b, especially when looking at the citation graphs. However, these numbers imply that a part of the edges selected do not satisfy the conditions for Theorem 4, limiting their interpretation as bottlenecks during message passing.

Figure: Figure 1: A 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 $\delta>1/\sharp_{\triangle}$ (if the edge is situated above the dotted line) or $\delta>1/\gamma_{max}$ (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 the dotted line and $\delta<1/\gamma_{max}$. The color code of the edges indicates at which step of the rewiring process (in %) the edge is selected. Dotted line shows $y=1/\sharp_{\triangle}$ corresponding to the upper limit in condition 2b.
Refer to caption: x1.png

Figure 1 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 to the $\gamma_{max}$ upper limit (as shown by the edges below the dotted line). The figure shows as well that edges that do satisfy the condition are sometimes close to the upper bound of $1/\sharp_{\triangle}$. This again reduces their interpretation as bottlenecks, as the $\delta$ 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 a saturation-type effect.

**Table 1: When an edge is selected by the SDRF algorithm, we verify if this edge satisfies condition 2 of Theorem 4 (Eq. equation 9). Additionally, we check if the edge satisfies a softer, but sufficient, version of condition 2 (Eq. equation 10)**
| Dataset | Edges rewired | Cond. 2 (%) | Cond. 2b (%) |
| --- | --- | --- | --- |
| Texas | $89$ | $0~{}(0\%)$ | $6~{}(6.7\%)$ |
| Cornell | $126$ | $0~{}(0\%)$ | $15~{}(11.90\%)$ |
| Wisconsin | $136$ | $0~{}(0\%)$ | $11~{}(8.09\%)$ |
| Chameleon | $2441$ | $4~{}(0.16\%)$ | $141~{}(5.78\%)$ |
| Actor | $1000$ | $11~{}(1.1\%)$ | $237~{}(23.70\%)$ |
| Squirrel | $787$ | $0~{}(0\%)$ | $34~{}(4.32\%)$ |
| Cora | $100$ | $0~{}(0\%)$ | $68~{}(68.0\%)$ |
| Citeseer | $84$ | $0~{}(0\%)$ | $24~{}(28.57\%)$ |
| Pubmed | $166$ | $25~{}(15.06\%)$ | $116~{}(69.88\%)$ |
| MUTAG | $3497$ | $0~{}(0\%)$ | $1228~{}(35.16\%)$ |
| PROTEINS | $50936$ | $0~{}(0\%)$ | $~{}5944(11.67\%)$ |

## 4 Hyperparameter dependency of rewiring

Graph rewiring algorithms depend on quite some hyperparameters. The first category consists of training and GNNs hyperparameters: learning rate, hidden depth, hidden dimension, weight decay, and dropout. Additionally, there are 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 $\tau$, 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 a parameter sweep over different benchmark graph datasets to evaluate curvature-based graph rewiring with different curvature notions.

#### Experimental setup

To analyse the impact of different curvatures we ran node-classification tasks. For the node classification tasks we used 9 datasets to evaluate the different curvature notions: Texas, Cornell and Wisconsin from WebKB (), Chameleon and Squirrel (Rozemberczki et al., ), Actor (Tang et al., ), Cora (McCallum et al., ), Citeseer (Sen et al., ) and Pubmed (Namata et al., ). For graph classification we used MUTAG and PROTEINS (Morris et al., ). For each dataset we only use the largest connected component, extracted with the algorithm provided in [https://github.com/jctops/understanding-oversquashing](https://github.com/jctops/understanding-oversquashing). While this implementation does not strictly adhere to the mathematical definition of connected components for directed graphs (it returns neither the strong nor weak component), it was chosen to maintain consistency in 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: $\{1,2,3\}$, layer width: $\{16,32,64,128\}$, dropout: $[0.0001,0.5555]$, weight decay: $[0.0001,0.9999]$, $C^{+}$: $[0.2,21.2]$, $\tau$: $[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 et al., ). We perform a random-grid search with 800 iterations for all datasets. Our evaluations follows (Gasteiger et al., ). Each dataset is split into a development set and a test set with a fixed seed. The development set is then split 100 times into a validation and training set using the same seeds as in (Topping et al., ). Each hyperparameter configuration is then trained and evaluated on each of the 100 training-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 on the validation set. We use a GCN (Kipf & Welling, ) for all datasets together with the Adam optimizer (Kingma & Ba, ).

#### Curvature notions

The question now arises as to what the role is of different curvature measures when rewiring graphs. For each dataset, we used each discrete curvature notion on graphs discussed in section 2 to rewire the graph in order to assess possible SDRF as extensively as possible.

#### Results

Figure 2 show the smoothed distributions (kernel density estimates), together with boxenplots, 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 Table 2. To assess the robustness of the distributions we analysed how well the distribution saturates with an 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.

**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 0.**
|  | Texas | Cornell | Wisconsin | Chameleon | Cora | Citeseer |
| --- | --- | --- | --- | --- | --- | --- |
| None | $59.95\pm 1.15$ | $53.66\pm 0.14$ | $54.92\pm 0.51$ | $40.76\pm 3.52$ | $58.83\pm 16.36$ | $58.14\pm 7.33$ |
| $BFc$ | $59.26\pm 0.00$ | $53.61\pm 0.28$ | $54.06\pm 0.01$ | $34.58\pm 3.19$ | $28.39\pm 17.24$ | $35.99\pm 13.82$ |
| $BFc_{3}$ | $59.26\pm 0.00$ | $53.59\pm 0.12$ | $54.06\pm 0.01$ | $30.93\pm 0.10$ | $21.86\pm 08.75$ | $30.35\pm 12.03$ |
| $BFc_{mod}$ | $59.26\pm 0.00$ | $53.68\pm 0.43$ | $54.91\pm 1.72$ | $31.60\pm 2.04$ | $27.73\pm 13.08$ | $44.16\pm 12.46$ |
| $JLc$ | $59.26\pm 0.00$ | $53.57\pm 0.01$ | $54.06\pm 0.02$ | $30.91\pm 0.02$ | $26.83\pm 13.82$ | $42.48\pm 7.83$ |
| $AFc_{3}$ | $59.58\pm 0.52$ | $54.20\pm 1.57$ | $56.37\pm 1.60$ | $36.93\pm 5.14$ | $59.25\pm 14.83$ | $60.11\pm 6.30$ |
| $AFc_{4}$ | $59.79\pm 0.54$ | $53.63\pm 0.10$ | $54.60\pm 0.80$ | $31.20\pm 0.62$ | $58.68\pm 16.10$ | $61.67\pm 5.43$ |

A first observation is that no curvature measure consistently shifts the distribution of the mean test 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$ 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-computational intensive curvature measures ($BFc_{3}$ and $AFc_{3}$) in comparison with their more intensive variant ($BFc$ and $AFc_{4}$).

It 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 in the graph by allowing communication between nodes that shouldn’t. Secondly, when comparing the results from Table 1 with the distribution of $BFc$ in Figure 2, we see that the datasets with more edges that satisfy condition 2b do not perform better than other.

Figure: 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 we also show the smoothed distribution using kernel density estimates from the seaborn package.
Refer to caption: x2.png

## 5 Conclusion

In our work, we have taken a 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 oversquashing 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-passing 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 is 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 of a GNN. There is an inherent trade-off between reducing oversquashing and enhancing oversmoothing (Nguyen et al., ; Fesser & Weber, ). 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 in this paper, despite meeting theoretical bounds better than other datasets (see Table 1), 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, ). This dependency is measured by the homophily (Pei et al., ), 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 1, 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 hyperparameter configuration rather than a structural shift in the performance, as illustrated by the distribution of performance in Figure 2. We argue that future rewiring methods should take into consideration the dependency of their method on hyperparameters, both GNN and rewiring, when evaluating their performance.

#### 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., ), which is the most natural method for curvature-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, $\delta\cdot|\#_{\triangle}|\leq 1$, could potentially be replaced by a more general bound, $\delta\cdot|\#_{\triangle}|\leq R$ with $R>1$, as alluded to in Remark 15 of (Topping et al., ). 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 can 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.

## Appendix A Curvature distributions

Figure: Figure 3: Distribution of curvatures for dataset Texas
Refer to caption: x3.png

Figure: Figure 4: Distribution of curvatures for dataset Cornell
Refer to caption: x4.png

Figure: Figure 5: Distribution of curvatures for dataset Wisconsin
Refer to caption: x5.png

Figure: Figure 6: Distribution of curvatures for dataset Chameleon
Refer to caption: x6.png

Figure: Figure 7: Distribution of curvatures for dataset Cora
Refer to caption: x7.png

Figure: Figure 8: Distribution of curvatures for dataset Citeseer
Refer to caption: x8.png

Figure: Figure 9: Distribution of curvatures for dataset Pubmed
Refer to caption: x9.png

Figure: Figure 10: Distribution of curvatures for dataset Actor
Refer to caption: x10.png

Figure: Figure 11: Distribution of curvatures for dataset Squirrel
Refer to caption: x11.png

## Appendix B On the implementation of the Balanced Forman curvature

Figure: Figure 12: Sample graph provided in Figure. 3 in Topping et al. ()
Refer to caption: x12.png

During the setup of our experiment, we noticed that the implementation of the Balanced Forman curvature provided by the authors of Topping et al. () under [https://github.com/jctops/understanding-oversquashing](https://github.com/jctops/understanding-oversquashing) does not match the theoretical definition presented in their paper (Definition 1 in Topping et al. ()). More precisely, the issue for a given edge $i\sim j$ evolves around the terms corresponding to the four-cycle contributions, i.e. $|\sharp_{\square}^{i}|,\>|\sharp_{\square}^{j}|$ and $\gamma_{max}$. The degree $d_{i}$ and $d_{j}$ of the involved nodes and the number of triangles $|\sharp_{\triangle}(i,j)|$ are calculated correctly. However, even for the sample graph provided in Figure. 3 in Topping et al. () (Figure 12 here) the publicly available implementation produces demonstrably wrong results. The four-cycle contribution is computed as illustrated in the code below with $\mathrm{sharp}_{ij}=|\sharp_{\square}^{i}|+|\sharp_{\square}^{j}|$, $\mathrm{lambda}_{ij}=\gamma_{\max}$.

If we consider the edge $0\sim 1$ of the sample graph in Figure 12 and using the definition of the Balanced Forman curvature, Eq. equation 2 we find $BFc(0,1)=0.10$. In contrast, when using the publicly available code we find $BFc(0,1)=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 $S_{1}(i)$ and $S_{1}(j)$ of the involved nodes) provided in Definition 1 in Topping et al. (). These are

- 1.
$\sharp\Delta(i,j):=S_{1}(i)\cap S_{1}(j)$ are the triangles based at $i\sim j$.
- 2.
$\sharp_{\square}^{i}(i,j):=\left\{k\in S_{1}(i)\backslash S_{1}(j),k\neq j:
\exists w\in\left(S_{1}(k)\cap S_{1}(j)\right)\backslash S_{1}(i)\right\}$ are the neighbours of $i$ forming a 4-cycle based at the edge $i\sim j$ without diagonals inside.
- 3.
$\gamma_{\max}(i,j)$ is the maximal number of four-cycles based at $i\sim j$ traversing a common node

Additionally, we used Remark 10 from Topping et al. () to calculate the four-cycle contribution and in particular $\gamma_{max}$. Our CUDA implementation of BFc was then controlled with the Networkx implementation. Both our implementations are available in our code.

Figure: Listing 1: Code snippet from Topping et al. () to compute the 4-cycle contribution of the BFc

## Appendix C Datasets

If the dataset connected disconnected components we report the statistics for the largest connected component selected. The homophily index $\mathcal{H}(G)$ defined by Pei et al. () is defined as

$$ $\displaystyle\mathcal{H}(G)=\frac{1}{|\mathbb{V}|}\sum_{v\in\mathbb{V}}\frac{ \text{ Number of }v\text{ 's neighbors who have the same label as }v}{\text{ Number of }v\text{ 's neighbors }}\,.$ (11) $$

|  | Texas | Cornell | Wisconsin | Chameleon | Squirrel | Actor | Cora | Citeseer | Pubmed |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| $\mathcal{H}(G)$ | 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 | 5 | 5 | 5 | 7 | 6 | 3 |
| Directed? | Yes | Yes | Yes | Yes | Yes | Yes | No | No | No |

## Appendix 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 |
| --- | --- | --- | --- | --- | --- |
| 2 x Nvidia A100 | 40 Gb | 2x 16-core AMD EPYC | 256 Gb | 2 TB SSD | EDR-IB |
| 2 x Nvidia Tesla P100 | 16 Gb | 2x 12-core INTEL E5-2650v4 | 256 Gb | 2 TB HDD | 10 Gbps |

## Appendix E Saturation analysis of distributions

Figure: Figure 13: Saturation analysis for datasets Texas and Cornell (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 $x\%$ of the total hyperparameter iterations. (f., g.) Mean and standard deviation when including $x\%$ of the total iterations.
Refer to caption: x13.png

Figure: 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 $x\%$ of the total hyperparameter iterations. (f., g.) Mean and standard deviation when including $x\%$ of the total iterations.
Refer to caption: x14.png

Figure: Figure 15: Saturation analysis for datasets Squirrel and Actor (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 $x\%$ of the total hyperparameter iterations. (f., g.) Mean and standard deviation when including $x\%$ of the total iterations.
Refer to caption: x15.png

Figure: 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. (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.
Refer to caption: x16.png

Figure: 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 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.
Refer to caption: x17.png

## Peer Reviews

confidence: 4
contribution: 3
initial_rating: 5
presentation: 3
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.

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

3) 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.
soundness: 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.

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

3) The paper is clearly motivated and generally well written. The visualisations are helpful to aid understanding.
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.
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).

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

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 2
questions: No further questions beyond weaknesses
soundness: 3
strengths: 1. This paper reveals an important issue in the evaluation of graph rewiring techniques, especially for curvature-based graph rewiring.
2. The theoretical analysis is thorough and solid.
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
weaknesses: 1. The analysis and empirical study are specific to the curvature-based method (Topping et al., 2021).
2. 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.
3. 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. 









------- 
- 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_.
- Bresson, X., & Laurent, T. (2018). Residual Gated Graph ConvNets. In _arXiv:1711.07553_.
- Hamilton, W., Ying, Z., & Leskovec, J. (2017). Inductive Representation Learning on Large Graphs. _Adv. Neural Inf. Process. Syst._, _30_. 
- Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., & Bengio, Y. (2018). Graph Attention Networks. _Proc. Int. Conf. Learn. Represent._

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 2
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.
2. For Other questions please see Weaknesses.
soundness: 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.
2. 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.
3. The paper proves its point through a large number of experiments, which show that the existing methods are ineffective in solving the problem.
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.
weaknesses: 1. The author merely presents a problem, not a solution to it.  The work lacks sufficient integrity.
2. 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.
3. 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.

Overall, I found this paper a very theoretically solid work. I would like to reconsider my score if my concerns could be addressed.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 2
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.
soundness: 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.
- 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.
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.

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

[1] Fesser, Lukas, and Melanie Weber. "Effective Structural Encodings via Local Curvature Profiles." The Twelfth International Conference on Learning Representations.

[2] Dwivedi, Vijay Prakash, et al. "Long range graph benchmark." Advances in Neural Information Processing Systems 35 (2022): 22326-22340.

Meta-review: Oversquashing has been one of the central challenges in Graph Neural Networks (GNNs). This phenomenon has been demonstrated in synthetic datasets. In the paper, the authors reassess the potential of curvature-based rewiring to enhance the performance of GNNs on real-world datasets. The study investigates the practical application of these techniques, particularly their effectiveness in mitigating the challenges of oversquashing phenomenon in complex and real-world scenarios.

Most of the reviewers agree that the theoretical analyses in the paper are thorough and clear, including a detailed explanation of the bottleneck conditions of curvature rewiring. The experiments are extensive, detailed and convincing, which support the theoretical findings. The presentation of the paper is also clear and easy to follow.

While there was a concern that the paper presents new insights into curvature-based rewiring, rather than proposing a new solution, model, or method, most of the reviewers and I believe that these new insights are useful for the community. As a consequence, I recommend accepting the paper.

The authors are encouraged to incorporate the feedbacks and comments of the reviewers into the revision of their paper.

Decision: Accept (Poster)