Is Rewiring Actually Helpful in Graph Neural Networks?
Graph neural networks compute node representations by performing multiple
message-passing steps that consist in local aggregations of node features.
Having deep models that can leverage longer-range interactions between nodes is
hindered by the issues of over-smoothing and over-squashing. In particular, the
latter is attributed to the graph topology which guides the message-passing,
causing a node representation to become insensitive to information contained at
distant nodes. Many graph rewiring methods have been proposed to remedy or
mitigate this problem. However, properly evaluating the benefits of these
methods is made difficult by the coupling of over-squashing with other issues
strictly related to model training, such as vanishing gradients. Therefore, we
propose an evaluation setting based on message-passing models that do not
require training to compute node and graph representations. We perform a
systematic experimental comparison on real-world node and graph classification
tasks, showing that rewiring the underlying graph rarely does confer a
practical benefit for message-passing.
Domenico Tortorella, Alessio Micheli
# Is Rewiring Actually Helpful in

###### Abstract

Graph neural networks compute node representations by performing multiple message-passing steps that consist in local aggregations of node features. Having deep models that can leverage longer-range interactions between nodes is hindered by the issues of over-smoothing and over-squashing. In particular, the latter is attributed to the graph topology which guides the message-passing, causing a node representation to become insensitive to information contained at distant nodes. Many graph rewiring methods have been proposed to remedy or mitigate this problem. However, properly evaluating the benefits of these methods is made difficult by the coupling of over-squashing with other issues strictly related to model training, such as vanishing gradients. Therefore, we propose an evaluation setting based on message-passing models that do not require training to compute node and graph representations. We perform a systematic experimental comparison on real-world node and graph classification tasks, showing that rewiring the underlying graph rarely does confer a practical benefit for message-passing.

## 1 Introduction

Neural models for graphs [6; 59], commonly called _graph neural networks_ (GNNs), have been successfully applied in many real-world tasks, such as identifying categories of users in social networks or classifying molecules. GNNs typically operate in the _message-passing_ paradigm, that is by exchanging information between nearby nodes according to the graph structure. Messages are computed from the neighbor node features, then aggregated by a permutation-invariant function to provide node representations. With multiple message-passing steps, GNNs are able to learn a hierarchy of representations that capture interactions between increasingly distant nodes. This is accomplished either via multiple iterations of the same parameterized message-passing function [44; 15], or by a deep network of message-passing layers with different learnable parameters [34; 13; 5; 25]. The need for sufficiently deep graph networks arises for tasks that require the discovery of long-range dependencies between nodes, otherwise the model incurs in _under-reaching_[3]. As deep learning on graph progressed, several challenges preventing the computation of effective node representations have emerged. Among those, _over-squashing_ is inherently connected to the inductive bias at the base of GNNs: the problem of encoding an exponentially growing receptive field [34] in a fixed-size node embedding dimension [3]. As simply increasing the width of node representations does not remove the underlying issues caused by the graph topology [12], this has motivated a growing number of methods that alter (i.e. _rewire_) the original graph as a pre-processing to improve message-passing. In this paper, we attempt to meet the need for an _empirical approach_ to assess the benefits of graph rewiring methods. Indeed, altering the input data without taking into account the specific learning task can possibly lead to the loss of critical information. Since the quality of node representations computed on rewired graphs is evaluated according to the accuracy in downstream learning tasks, the
use of end-to-end trained models does not allow to decouple the effects caused by graph topology on message-passing from the problems inherently connected to training in deep neural networks. Indeed, while it has been proven that gradient vanishing prevails on over-squashing when the number of message-passing steps is much larger than the range of node interactions needed to solve the task, it still unclear how the two issues interact with each other or what happens in intermediate regimes [12]. Furthermore, GNN models that completely or partially avoid learning representations via training have exhibited performances close to or above common end-to-end trained ones [17; 18; 35; 24], in particular when compared to previous results for rewiring methods applied to trained GNNs [54]. Therefore, as opposed to previous literature, we propose to use message-passing models that compute node representations _without training_, either by being parameter-free [58] or by following the reservoir computing paradigm [15], where parameters are just randomly initialized under certain constraints. Crucially, the issues that graph rewiring methods aim to address are connected with the inductive bias of GNNs [8], that is to the message-passing _per se_, whether is done in the forward or backward pass. This will allow us to assess the actual benefits of graph rewiring on several node and graph classification tasks.

The rest of this paper is structured as follows. In Sec. 2 we present a brief survey of the rewiring methods that will be evaluated in our experiments. In Sec. 3 we introduce SGC and GESN, the two training-free message-passing models adopted in our experimental framework. The datasets and results of our experiments will be discussed in Sec. 4, drawing final conclusions in Sec. 5.

## 2 Graph rewiring methods

Let \(\mathcal{G}(\mathcal{V},\mathcal{E})\) be a graph with nodes \(v\in\mathcal{V}\) and edges \((u,v)\in\mathcal{E}\), each node having associated input features \(\mathbf{x}_{v}\in\mathbb{R}^{X}\). We denote by \(\mathcal{N}_{v}\) the set of neighbors of node \(v\) with cardinality (i.e. degree) \(d_{v}\), and respectively by \(\mathbf{A}\), \(\mathbf{D}\), \(\mathbf{L}\) the graph adjacency, degree and Laplacian matrices. We also define the symmetric normalized adjacency \(\mathbf{A}_{\text{sym}}=\mathbf{D}^{-\frac{1}{2}}\mathbf{A}\mathbf{D}^{- \frac{1}{2}}\), the random-walk normalized adjacency \(\mathbf{A}_{\text{rw}}=\mathbf{A}\mathbf{D}^{-1}\), and the mean-aggregation normalized adjacency \(\mathbf{A}_{\text{mean}}=\mathbf{D}^{-1}\mathbf{A}\), along with the respective normalized Laplacians \(\mathbf{L}_{\text{sym}}\), \(\mathbf{L}_{\text{rw}}\), \(\mathbf{L}_{\text{mean}}\), and the self-loop augmented \(\hat{\mathbf{A}}=\mathbf{A}+\mathbf{I}\). Finally, we denote by \(\mathbf{A}^{+}\) the pseudo-inverse of matrix \(\mathbf{A}\). Throughout the paper we assume the graphs to be undirected.

A graph neural network (GNN) computes node representations \(\mathbf{h}_{v}\in\mathbb{R}^{H}\) via a deep neural network of \(L\) message-passing layers. Each layer \(k=1,...,L\) computes a new node representation \(\mathbf{h}_{v}^{(k)}\) by performing a permutation-invariant aggregation of messages computed from the previous layer representations of neighbor nodes \(\mathbf{h}_{u}^{(k-1)}\). Without much loss of generality, we assume the message-passing layers to have the form

\[\mathbf{h}_{v}^{(k)}=\phi_{k}\left(\sum_{u\in\mathcal{V}}M_{vu}\,\psi_{k} \left(\mathbf{h}_{u}^{(k-1)}\right)\right),\quad\mathbf{h}_{v}^{(0)}=\mathbf{ x}_{v}, \tag{1}\]

where local neighbors of \(v\) are implicitly defined as nodes \(u\) such that \(M_{vu}\neq 0\). By \(\mathbf{M}\) we denote the message-passing matrix, which is a graph shift operator. Such operator that can be e.g. either the adjacency \(\mathbf{A}\), the Laplacian \(\mathbf{L}\), or one of their normalizations. In this case, the aggregations are performed on graph neighborhoods \(\mathcal{N}_{v}\). Message-passing layers can thus represent the relationships induced by graph connectivity in an efficient manner by leveraging the graph structure sparsity. To capture long-range dependencies between nodes, GNNs must perform at least as many message-passing steps (i.e., have as many layers) as the distance between node pairs to not incur in under-reaching [3]. However, building deep GNNs presents an inherent challenge. As depth increases, the receptive field of nodes [34] grows exponentially, thus requiring more information to be encoded in the same fixed-size vectors. This problem is called over-squashing [3]. Topping et al. [52] have investigated this phenomenon via the analysis of node representations sensitivity to input features. Assuming there exist an \(L\)-path from node \(u\) to node \(v\), the sensitivity of \(\mathbf{h}_{v}^{(L)}\) to input features \(\mathbf{x}_{u}\) is upper bounded by

\[\left\|\frac{\partial\mathbf{h}_{v}^{(L)}}{\partial\mathbf{x}_{u}}\right\|\ \leq\ \underset{\underset{\text{Lipschitz constants}}{ \underbrace{k=1}}}{\prod}\|\phi_{k}\|\|\psi_{k}\|\underset{\text{graph topology}}{\underbrace{\left(\mathbf{M}^{L}\right)_{vu}}}. \tag{2}\]
Over-squashing arises when the derivative in (2) becomes too small, indicating that the representation of node \(v\) is mostly insensitive to the information initially present at node \(u\). While increasing the layer Lipschitz constants or the dimension \(H\) can mitigate the issue [54, 12], this may come at the expense of model generalization [32]. Therefore, different methods have been proposed to alter the graph topology in a more favorable way to message-passing. In this paper we focus on graph rewiring methods which change the initial graph--or equivalently, the message-passing matrix \(\mathbf{M}\)--as a pre-processing step, as opposed to e.g. the implicit rewiring done by attention mechanisms [55].

Diffusion processesGraph diffusion was originally proposed as a way of aggregating nodes beyond the immediate \(1\)-hop neighborhood [26], thus allowing a single message-passing layer to directly consider information from more distant nodes. The generalized graph diffusion matrix is computed by the power series \(\sum_{m=0}^{\infty}\theta_{m}\mathbf{A}^{m}\), where the choice of coefficients \(\theta_{m}\) defines the particular diffusion process and \(\mathbf{A}\) can be replaced by any other transition matrix. Two examples of graph diffusion are the heat kernel [27] with \(\theta_{m}^{\text{Heat}}=e^{-t}\frac{1}{m!},t>0\), and personalized PageRank [40] with \(\theta_{m}^{\text{ PageRank}}=\alpha(1-\alpha)^{m},0<\alpha<1\), which correspond respectively to the message-passing matrices

\[\mathbf{M}_{\text{Heat}}=e^{-t\mathbf{A}}\quad\text{and}\quad\mathbf{M}_{ \text{PageRank}}=\alpha(1-(1-\alpha)\mathbf{A})^{+}. \tag{3}\]

Diffusion-based rewiring was proposed exclusively for node-level tasks.

Local bottlenecksIn their analysis of over-squashing, Topping et al. [52] have linked its causes to _bottlenecks_ in the graph topology that happen where the graph structure locally resembles a tree. Intuitively, for a tree the receptive field grows exponentially in the branching factor, while at the other opposite a complete graph has a constant receptive field. To provide a metric to quantify this local behavior, they have proposed the balanced Forman curvature, defined as

\[\text{Ric}_{uv}=\underbrace{\frac{2}{d_{u}}+\frac{2}{d_{v}}}_{\text{tree-likeness}}-2 +2\underbrace{\frac{\sharp^{\triangle}_{uv}}{\max\{d_{u},d_{v}\}}+\frac{ \sharp^{\triangle}_{uv}}{\min\{d_{u},d_{v}\}}}_{\text{local similarity to a complete graph}}+\underbrace{\frac{\sharp^{\square}_{uv}+\sharp^{\square}_{vv}}{ \star^{\max}_{uv}}}_{\text{grid-likeness}}, \tag{4}\]

where \(\sharp^{\triangle}_{uv}\) is the number of triangles on the edge \((u,v)\), \(\sharp^{\square}_{uv}\) is the number of neighbors of \(u\) forming a \(4\)-cycle based on the edge \((u,v)\) without diagonals inside, and \(\gamma^{\max}_{uv}\) is a normalization factor. For a graph having only positively curved edges (i.e. \(\text{Ric}_{uv}>0\) for all \((u,v)\)) it has been proved that the receptive field grows at most polynomially [52]. Therefore, rewiring algorithms that aim at increasing the graph curvature have been proposed. SDRF [52] iteratively samples an edge \((u,v)\) proportionally to how negatively curved it is, then adds the new edge \((u^{\prime},v^{\prime})\) able to provide the largest increase of \(\text{Ric}_{uv}\). (The algorithm optionally removes the most positively curved edges to avoid growing the graph excessively.)

Global bottlenecksThe edge curvature defined in equation (4) is not the only way to measure the presence of bottlenecks in the graph topology. A more _global_ metric is the Cheeger constant \(\mathfrak{h}_{\mathcal{G}}\), which quantifies the minimum fraction of edges that need to be removed in order to make the graph disconnected. A small \(\mathfrak{h}_{\mathcal{G}}\) thus indicates that few edges act as a bridge between two otherwise disconnected communities. However, computing the Cheeger constant is an NP-hard problem, so the lower bound given by the spectral gap \(\lambda_{1}\) (i.e. the smallest positive Laplacian eigenvalue) is used as a proxy measure in practice: \(\mathfrak{h}_{\mathcal{G}}\geq\frac{1}{2}\lambda_{1}\)[36]. GRLEF [7] proposes to improve a graph spectral gap by working exclusively _locally_ via the triangle counts \(\sharp^{\triangle}_{uv}\), which are cheaper to compute as they require just neighborhood information. The algorithm iteratively samples an edge \((u,v)\) proportionally to the inverse of triangle count, that is from an area of the graph that is locally far away from being fully-connected. Then it chooses the pair of edges \((u,u^{\prime}),(v,v^{\prime})\) to flip into \((u,v^{\prime}),(v,u^{\prime})\) which provides the smallest net change in triangle count. This behavior can be interpreted as mitigating a very low local curvature (as suggested by the small term \(\sharp^{\triangle}_{uv}\) in \(\text{Ric}_{uv}\)) at the expense of a reduction in curvature of more positively curved neighboring edges. Banerjee et al. [7] supported the approach of their rewiring algorithm by empirically finding a correspondence between triangle count decrease and spectral gap increase.

Expander propagationThere is a class of graphs that avoid global bottlenecks by construction: expander graphs are simultaneously sparse and highly connected [23]. Additionally, expander families
of graphs are characterized by an uniform lower bound on the Cheeger constant [2], and for uniform maximal node degree their diameter is also logarithmic in the number of nodes [37; 1]. Deac et al. [11] have thus proposed to interleave the message propagation on the original graph with message-passing on an expander graph to provide for information propagation over bottlenecks. The expander graphs adopted for EGP [11] are derived from the Cayley graphs of finite groups \(\mathrm{SL}(2,\mathbb{Z}_{n})\), which are \(4\)-regular and thus guarantee sparsity. Interestingly, these graphs have all negatively curved edges with \(\mathsf{Ric}_{uv}=-\frac{1}{2}\). In our experiments we will thus use the message-passing matrix \(\mathbf{M}_{\mathrm{EGP}}=\mathbf{A}_{\mathrm{Cay}}\,\mathbf{A}\), where \(\mathbf{A}_{\mathrm{Cay}}\) is the adjacency matrix of said Cayley graphs.

Effective resistanceEffective resistance [14] provides an additional way to measure bottlenecks in graph topology. The resistance \(\mathsf{Res}_{uv}\) between two nodes is proportional to the commute time \(\mathsf{Com}_{uv}\), which is the number of expected steps for a random walk to go back and forth between nodes \(u,v\). 1 An high resistance between two nodes is an indication of the difficulty for messages to pass from node \(u\) to node \(v\). Black et al. [9] proved a sensitivity bound similar to (2) relating high effective resistance \(\mathsf{Res}_{vu}\) between pairs of nodes to a reduced sensitivity of the representations \(\mathbf{h}_{v}^{(L)}\) to input features \(\mathbf{x}_{u}\). Furthermore, effective resistance is inversely related to the square of the Cheeger constant by the inequality \(\max_{(u,v)\in\mathcal{E}}\mathsf{Res}_{uv}\leq\frac{1}{b_{0}^{2}}\)[4]. Arnaiz-Rodriguez et al. [4] have proposed a layer for learning effective resistance to re-weight the original graph adjacency (hence 'DiffWire') in the perspective of sampling a spectrally similar but sparser graph which preserves the graph structural information [47]. The additional intuitive effect is to enlarge the relative capacity of high resistance edges, which correspond to bridges over more densely connected communities. In our experiments we implement the DiffWire approach by computing the effective resistance in exact form by \(\mathsf{Res}_{uv}=(\mathbf{1}_{u}-\mathbf{1}_{v})^{\top}\mathbf{L}^{+}(\mathbf{ 1}_{u}-\mathbf{1}_{v})\) with \(\mathbf{1}_{u}\) the indicator vector of node \(u\). The resulting message-passing matrix therefore is \(\mathbf{M}_{\mathrm{DiffWire}}=\mathsf{Res}\odot\mathbf{A}\), where '\(\odot\)' denotes the elementwise product.

Footnote 1: Precisely, \(\mathsf{Res}_{uv}=\frac{1}{\sum_{v\in\mathcal{V}}d_{v}}\mathsf{Com}_{uv}\).

## 3 Training-free graph neural networks

Since graph rewiring methods work as a pre-processing step on the input graph, the choice of GNN model is crucial to assess their benefits in downstream task accuracy. So far, only end-to-end trained models have been used, such as GCN [25] in [52]. This approach does not allow to consider the effects of over-squashing independently from the other issues that can affect training in message-passing models, such as gradient vanishing. By learning node and graph representations jointly with the task prediction readout, the experimental results become inextricably linked to how training is conducted. Therefore, we propose to apply GNNs that compute node and graph representation _without training_ in our experimental setting for assessing the actual contributions of graph rewiring. Indeed, rewiring methods aim to address issues connected with the model bias itself, that is local aggregation of messages computed from node structural neighbors, independently from whether message-passing is done in the forward or backward pass. Isolating the inductive bias of a model from

Figure 1: The two different model architectures of SGC [58] and GESN [15].
training is not completely unprecedented, as it was previously employed for the analysis of recurrent neural networks [51, 50, 16]. For our experiments we adopt two training-free models with different architectural biases, SGC [58] and GESN [15]. In particular, the latter has achieved performances in line with or better than widely adopted end-to-end trained GNNs in node classification tasks [35], also significantly improving upon previous results that include rewiring as graph pre-processing [54]. This may suggest that the training process itself can pose serious challenges.

As an example of how end-to-end training can egregiously fail, in Tab. 1 we report the accuracy of some common GNN models (GCN [25], GraphSAGE [22], GAT [55]) on two node classification tasks. Platonov et al. [42] have observed that both Squirrel and Chameleon present a large number of duplicated nodes--i.e., nodes sharing same local structure and features, resulting in a training-test leakage. Nevertheless, the accuracy of end-to-end trained models is significantly worse than the two training-free GNNs, and is actually much closer to a graph-agnostic baseline (MLP). This is an additional motivation for our choice of excluding end-to-end trained GNNs in our rewiring evaluation framework and rely on the models presented below.

SgcA straightforward way to compute node representations without the need for training is to replace the functions \(\phi_{k},\psi_{k}\) in (1) with the identity, thus removing altogether parameters in layers. Such approach was previously proposed by [58] as a simplification of graph convolution by removing non-linearities, hence the name SGC. This model therefore is reduced to pure message-passing (Fig. 0(a)), with node representations computed after \(L\) message-passing steps as

\[\mathbf{h}^{(L)}=\mathbf{M}^{L}\,\mathbf{x}. \tag{5}\]

Notice that this model was proposed exclusively for node-level tasks [58].

GesnA different approach for training-free models is to follow the reservoir computing (RC) paradigm [39, 31, 56], where input representations (or embeddings) are computed by a dynamical system with randomly initialized parameters. Combining the recursive embedding approach of [44] with RC, Graph Echo State Networks [15] compute node representations by iterating up to \(L\) times the same message-passing function

\[\mathbf{h}^{(k)}_{v}=\tanh\left(\mathbf{W}_{\text{in}}\,\mathbf{x}_{v}+\sum_{ u\in\mathcal{V}}M_{uv}\hat{\mathbf{W}}\,\mathbf{h}^{(k-1)}_{u}+\mathbf{b} \right),\quad\mathbf{h}^{(0)}_{v}=\mathbf{0}, \tag{6}\]

where \(\mathbf{W}_{\text{in}}\in\mathbb{R}^{H\times X}\), \(\mathbf{b}\in\mathbb{R}^{H}\) and \(\hat{\mathbf{W}}\in\mathbb{R}^{H\times H}\) are respectively the input-to-reservoir, bias, and recurrent weights for a reservoir with \(H\) units. This can be interpreted as a form of parameter sharing between message-passing layers (Fig. 0(b)). Notice also that equation (6) slightly departs from (1) due to the presence of input skip connections. All reservoir weights are randomly initialized, with \(\mathbf{W}_{\text{in}}\) rescaled to accommodate the input features range, and \(\hat{\mathbf{W}}\) rescaled to control the Lipschitz constant of (6). For \(\|\hat{\mathbf{W}}\|\ \|\mathbf{M}\|<1\) the message-passing function is contractive [53], that is the iterations of (6) converge to a fixed point \(\mathbf{h}^{(\infty)}\) as \(L\to\infty\). While this regime has been shown to be optimal for graph-level tasks, node-level tasks instead benefit from a non-contractive initialization \(\|\hat{\mathbf{W}}\|\ \|\mathbf{M}\|>1\), as the upper bound on input sensitivity (2) intuitively suggests. In the non-contractive regime, a choice of \(L\) larger then the graph diameter is sufficient to ensure effective node representations [35].

To produce graph representations for graph-level tasks, we apply a parameter-free global pooling operation, such as sum or mean pooling, to the final node representations:

\[\mathbf{h}^{\text{\tiny{SUM}}}_{\mathcal{G}}=\sum_{v\in\mathcal{V}}\mathbf{ h}^{(L)}_{v},\quad\mathbf{h}^{\text{\tiny{MEAN}}}_{\mathcal{G}}=\tfrac{1}{| \mathcal{V}|}\sum_{v\in\mathcal{V}}\mathbf{h}^{(L)}_{v}. \tag{7}\]

ReadoutTo solve a downstream node (or graph) classification task, there still remains the need to train a predictor. For this purpose, we use a linear readout layer \(\mathbf{y}_{v}=\mathbf{W}_{\text{out}}\,\mathbf{h}^{(L)}_{v}+\mathbf{b}_{\text {out}}\), where the

\begin{table}
\begin{tabular}{l c c} \hline \hline  & **Squirrel** & **Chameleon** \\ \hline MLP [62] & \(29.68\pm 1.81\) & \(46.36\pm 2.52\) \\ \hline GCN [62] & \(36.89\pm 1.34\) & \(59.82\pm 2.58\) \\ SAGE [62] & \(41.61\pm 0.74\) & \(58.73\pm 1.68\) \\ GAT [62] & \(30.62\pm 2.11\) & \(54.69\pm 1.95\) \\ \hline GCN [42] & \(39.06\pm 1.52\) & \(50.18\pm 3.29\) \\ SAGE [42] & \(35.83\pm 1.32\) & \(50.18\pm 1.78\) \\ GAT [42] & \(32.21\pm 1.63\) & \(45.02\pm 1.75\) \\ \hline SGC & \(72.88\pm 1.20\) & \(76.16\pm 1.87\) \\ GESN [35] & \(73.56\pm 1.62\) & \(77.05\pm 1.24\) \\ \hline \hline \end{tabular}
\end{table}
Table 1: Examples of underfitting in common end-to-end trained models on node classification (experimental setting of [41]).
weights \(\mathbf{W}_{\mathrm{out}}\in\mathbb{R}^{C\times H},\mathbf{b}_{\mathrm{out}}\in \mathbb{R}^{C}\) are trained by ridge regression on one-hot encodings of target classes \(y_{v}\in 1,...,C\). This can be achieved efficiently in closed-form even on large data [61], thus removing also from the readout any issue connected to back-propagation learning.

## 4 Experiments and discussion

We evaluate the graph rewiring methods of Sec. 2 jointly with the training-free GNNs presented in the previous section on several real-world classification tasks, many of whom were also adopted in previous rewiring literature [52; 4]. The aim of our experimental approach is to provide a tool for examining the effects of rewiring from a different perspective than previously pursued in literature, thanks to decoupling the inductive bias of GNNs from the training process.

DatasetsFor node classification tasks, we adopt six graphs of up to \(20{,}000\) nodes. Cora [33], CiteSeer [20], PubMed [45] are paper citation networks, where input node features are bag-of-words representations of paper content, and the target is the research topic. Film [49] is a network induced by co-occurrences of actors in the same Wikipedia page, grouped into five categories [41]. TwitchDE [43; 30] is a social network of German garcer accounts from Twitch classified into suitable for work or adult profiles. Tolokers [29; 42] is a collaboration network of users extracted from the crowdsourcing platform Toloka, where the task is to determine whether an user is active or not (since the two classes are unbalanced, the evaluation metric in this case is area under the ROC curve instead of accuracy). The first three are homophilous node classification tasks, while the other three tasks present low homophily. For graph classification we adopt six tasks from the TUDataset collection [38]. NCI-1, NCI-109 [57; 46] are molecules to be classified as cancerogenous or not, where node input features are one-hot encodings of atom type, and edges correspond to chemical bounds. Reddit-B, Reddit-5K, Reddit-12K [60] are interaction networks between users in Reddit discussion threads, and the classification task is to identify the type of sub-reddit the discussions belong to. Collab [28; 60] is a collection of ego-networks belonging to three different scientific collaboration fields. Both Reddit tasks and Collab have no node input features. In all tasks we have consciously avoided adding structural input features to the graph nodes, such as node degrees or positional encodings [48]. Relevant dataset statistics are reported in Tab. 2.

Experimental settingFor all classification tasks we have generated with class stratification \(5\)-fold selection/test splits with inner validation holdout, thus resulting in 60:20:20 training/validation/test set ratios. Both GNN and rewiring algorithm parameters are jointly selected on each validation fold. For SGC, we select the number of message-passing iterations \(L\in[1,15]\) and the type of

\begin{table}
\begin{tabular}{l r r r r r r} \hline \hline  & **Cora** & **CiteSeer** & **PubMed** & **Film** & **TwitchDE** & **Tolokers** \\ \hline nodes & \(2{,}708\) & \(3{,}327\) & \(19{,}717\) & \(7{,}600\) & \(9{,}498\) & \(11{,}758\) \\ edges & \(10{,}556\) & \(9{,}104\) & \(88{,}648\) & \(53{,}504\) & \(153{,}138\) & \(519{,}000\) \\ average degree & \(3.90\) & \(2.74\) & \(4.50\) & \(7.03\) & \(16.14\) & \(88.28\) \\ diameter & \(19\) & \(28\) & \(18\) & \(12\) & \(7\) & \(11\) \\ node features & \(1{,}433\) & \(3{,}703\) & \(500\) & \(932\) & \(2{,}514\) & \(10\) \\ classes & \(7\) & \(6\) & \(3\) & \(5\) & \(2\) & \(2\) \\ edge homophily & \(0.81\) & \(0.74\) & \(0.80\) & \(0.22\) & \(0.63\) & \(0.59\) \\ \hline \hline \multicolumn{7}{c}{Graph Classification} \\ \hline  & **NCI-1** & **NCI-109** & **Reddit-B** & **Reddit-5K** & **Reddit-12K** & **Collab** \\ \hline graphs & \(4{,}110\) & \(4{,}127\) & \(2{,}000\) & \(4{,}999\) & \(11{,}929\) & \(5{,}000\) \\ average nodes & \(30\) & \(30\) & \(430\) & \(509\) & \(391\) & \(75\) \\ average edges & \(32\) & \(32\) & \(498\) & \(595\) & \(457\) & \(2{,}458\) \\ average degree & \(2.16\) & \(2.16\) & \(2.34\) & \(2.25\) & \(2.28\) & \(37{,}37\) \\ average diameter & \(13{,}33\) & \(13{,}13{,}\) & \(9.72\) & \(11{,}96\) & \(10{,}91\) & \(1.86\) \\ node features & \(37\) & \(38\) & \(0\) & \(0\) & \(0\) & \(0\) \\ classes & \(2\) & \(2\) & \(2\) & \(5\) & \(11\) & \(3\) \\ \hline \hline \end{tabular}
\end{table}
Table 2: Dataset statistics.
message-passing matrix (adjacency, Laplacian, or one of their normalizations, with or without the addition of self-loops). For GESN, we select the reservoir size (i.e. node representation dimension) \(H\in[2^{4},2^{12}]\), the input scaling factor in \([0,1]\), and the Lipschitz constant. For the latter, we actually follow the reservoir computing practice of selecting the spectral radius \(\rho(\hat{\mathbf{W}})\) instead of the spectral norm \(\|\hat{\mathbf{W}}\|\), as the radius is a lower bound on the norm [21] and it is cheaper to compute [19]. We select \(\rho(\hat{\mathbf{W}})\in[0.1/\rho(\mathbf{M}),30/\rho(\mathbf{M})]\), while the number of message-passing iterations is fixed at \(L=30\), which is comfortably larger than graph diameters in our datasets [35]. For graph-level tasks we also select the pooling function from the two defined in (7). As for graph rewiring algorithms, we select \(t\in[0.1,5]\) for heat diffusion, and \(\alpha\in[0.01,0.99]\) for PageRank diffusion. We run SDRF and GRLEF for a number of iterations corresponding to up to \(20\%\) of the graph edges, without performing edge removal in the former. Finally, the regularization for the closed-form ridge regression to train the readout classifier is selected in \([10^{-5},10^{3}]\).

ResultsWe report the results of our experiments in Tab. 3-5. The baseline accuracy corresponds to the model applied on the original graph without any rewiring. We highlight better or worse accuracy with respect to the baseline when statistically significant (\(p<0.05\)), denoting no improvements otherwise. The experiments were executed on an NVIDIA A100 with 40GB of GPU RAM. For reference, a single complete model selection for GESN excluding rewiring took up to \(3.5\) hours. 'OOR' in Tab. 3-4 indicates that SDRF exceeded the limit of 10 days of computation for Tolokers.

On node classification tasks the only rewiring methods able to achieve some significant improvements over the baseline both for SGC and GESN are the diffusion-based heat and PageRank rewiring. This improvement is present both on high and low homophily graphs, that is respectively PubMed and Film.

\begin{table}
\begin{tabular}{l c c c c c c} \hline \hline  & **Cora** & **CiteSeer** & **PubMed** & **Film** & **TwitchDE** & **Tolokers** \\ \hline Baseline & \(87.70\pm 1.34\) & \(75.84\pm 0.93\) & \(89.53\pm 0.49\) & \(35.23\pm 0.70\) & \(68.62\pm 1.04\) & \(84.40\pm 1.02\) \\ \cline{2-7} Heat & \(87.86\pm 1.50\) & \(75.34\pm 0.88\) & \(89.22\pm 0.33\) & \(36.87\pm 1.05\) & \(68.26\pm 0.30\) & \(84.20\pm 1.17\) \\ PageRank & \(87.50\pm 1.30\) & \(75.20\pm 1.32\) & \(89.19\pm 0.42\) & \(35.91\pm 1.06\) & \(67.88\pm 0.49\) & \(82.63\pm 1.18\) \\ SDRF & \(86.60\pm 1.56\) & \(74.84\pm 1.66\) & \(89.20\pm 0.40\) & \(34.92\pm 0.55\) & \(68.54\pm 0.80\) & OOR \\ GRLEF & \(86.06\pm 1.56\) & \(74.74\pm 1.73\) & \(89.11\pm 0.74\) & \(35.05\pm 0.87\) & \(67.66\pm 0.70\) & \(82.64\pm 1.19\) \\ EGP & \(86.95\pm 2.51\) & \(74.62\pm 1.85\) & \(89.50\pm 0.42\) & \(35.06\pm 0.78\) & \(68.68\pm 0.98\) & \(84.50\pm 1.02\) \\ DiffWire & \(86.51\pm 1.74\) & \(74.03\pm 2.20\) & \(88.81\pm 0.49\) & \(35.01\pm 0.74\) & \(68.15\pm 0.33\) & \(84.77\pm 0.95\) \\ \hline \hline \end{tabular}
\end{table}
Table 4: Node classification with GESN.

\begin{table}
\begin{tabular}{l c c c c c c} \hline \hline  & **NCI-1** & **NCI-109** & **Reddit-B** & **Reddit-5K** & **Reddit-12K** & **Collab** \\ \hline Baseline & \(78.09\pm 1.64\) & \(77.56\pm 0.83\) & \(87.23\pm 1.38\) & \(53.86\pm 1.49\) & \(44.02\pm 0.54\) & \(72.49\pm 0.77\) \\ \cline{2-7} SDRF & \(73.39\pm 0.63\) & \(72.35\pm 1.46\) & \(87.02\pm 1.30\) & \(53.84\pm 1.55\) & \(44.07\pm 0.47\) & \(71.25\pm 1.09\) \\ GRLEF & \(73.74\pm 1.40\) & \(71.76\pm 1.31\) & \(85.89\pm 2.02\) & \(53.17\pm 1.26\) & \(42.94\pm 1.23\) & \(72.23\pm 0.86\) \\ EGP & \(78.31\pm 1.63\) & \(77.49\pm 0.65\) & \(87.28\pm 1.29\) & \(53.78\pm 1.34\) & \(44.08\pm 0.48\) & \(72.17\pm 0.87\) \\ DiffWire & \(78.14\pm 1.61\) & \(77.48\pm 0.65\) & \(84.54\pm 2.44\) & \(53.58\pm 0.72\) & \(41.37\pm 0.68\) & \(66.31\pm 0.76\) \\ \hline \hline \end{tabular}
\end{table}
Table 5: Graph classification with GESN.
This comes as a surprise, since these methods were dismissed in previous literature [52]. We may conjecture that by acting as low-pass filters on the graph spectra [26], diffusion methods can improve the spectral gap \(\lambda_{1}\) (i.e. the smallest positive Laplacian eigenvalue) in certain graphs, possibly resulting in a rewired graph with a larger Cheeger constant since \(\mathfrak{h}_{G}\geq\frac{\lambda_{1}}{2}\)[36]. The other rewiring methods do not provide significant improvements in accuracy, both on node and graph classification tasks. Actually, they can cause a significant degradation of accuracy. To investigate the effects of rewiring algorithms that explicitly act on local bottlenecks of graph topology, we analyze the distribution of edge curvature before and after rewiring (Fig. 1(a)). Notice that the overall curvature distribution is not improved; in particular, the one of SDRF appears to become even more skewed towards negatively curved edges. This is confirmed by observing the differences between initial and final edge curvature in the scatter plots of Fig. 1(b), where the predominant number of edges appears in red below the diagonal, denoting than edge curvature has actually become more negative instead of improving. This behavior can be explained by recalling that the algorithm acts _greedily_ on _local_ curvature information, without accounting for the effects on _global_ graph curvature when deciding where to add supporting edges [12]. As previously stated in Sec. 2, the spectral gap is a proxy measure of global graph bottlenecks. In Fig. 3 we analyze the effects of the two local rewiring algorithms SDRF and GRLEF on this global property. While a more positive curvature should also improve the spectral gap since \(\lambda_{1}\geq\min_{(u,v)\in\mathcal{E}}\text{Ric}_{uv}\)[52], the failure of SDRF in generally increasing edge curvature results in an unchanged \(\lambda_{1}\). On the other end, GRLEF is in some cases able to provide some increase in the spectral gap. However, this does not necessarily translates into an improvement of node classification accuracy, as the results on TwitchDE and Tolokers show. EGP seems to have little effect on accuracy both on graph and node classification tasks in general. As for DiffWire, the significant degradation of accuracy on Collab and Reddit-12K could be attributed to a magnification of spurious edges between network communities. While the scope of our empirical approach is to validate the effectiveness of graph rewiring purely on message-passing, to put the results of our experiments into perspective we recall that the addition of training to a message-passing model on the rewired graph has shown no improvements over training-free baselines [54]. As for a comparison with end-to-end trained GNNs, we refer to the results of rewiring algorithms in the respective original papers.

LimitationsSince our experimental framework is based on training-free GNNs, we have necessarily left out models that learn the graph structure jointly with node representations, or that perform an implicit rewiring via attention mechanisms. We may also have left out from our evaluation rewiring

Figure 3: Effects of SDRF and GRLEF on spectral gaps \(\lambda_{1}\).

Figure 2: Effects of SDRF and GRLEF on graph curvature Ric for Cora.