Effects of Dropout on Performance in Long-range Graph Learning Tasks
Authors: Jasraj Singh
Keyue Jiang
Brooks Paige
Laura Toni
Venue: NeurIPS 2025 poster ()
Keywords: Dropout
graph neural networks
long-range interactions
Primary area: deep_learning
TL;DR: We present the shortcomings of existing dropout-based methods in modeling long-range tasks.

Abstract: Message Passing Neural Networks (MPNNs) are a class of Graph Neural Networks (GNNs) that propagate information across the graph via local neighborhoods. The scheme gives rise to two key challenges: over-smoothing and over-squashing. While several Dropout-style algorithms, such as DropEdge and DropMessage, have successfully addressed over-smoothing, their impact on over-squashing remains largely unexplored. This represents a critical gap in the literature, as failure to mitigate over-squashing would make these methods unsuitable for long-range tasks – the intended use case of deep MPNNs. In this work, we study the aforementioned algorithms, and closely related edge-dropping algorithms – DropNode, DropAgg and DropGNN – in the context of over-squashing. We present theoretical results showing that DropEdge-variants reduce sensitivity between distant nodes, limiting their suitability for long-range tasks. To address this, we introduce DropSens, a sensitivity-aware variant of DropEdge, which is developed following the message-passing scheme of GCN. DropSens explicitly controls the proportion of information lost due to edge-dropping, thereby increasing sensitivity to distant nodes despite dropping the same number of edges. Our experiments on long-range synthetic and real-world datasets confirm the predicted limitations of existing edge-dropping and feature-dropping methods. Moreover, DropSens with GCN consistently outperforms graph rewiring techniques designed to mitigate over-squashing, suggesting that simple, targeted modifications can substantially improve a model’s ability to capture long-range interactions. Our conclusions highlight the need to re-evaluate and re-design existing methods for training deep GNNs, with a renewed focus on modelling long-range interactions. The code for reproducing the results in our this work is available at https://github.com/ignasa007/Dropout-Effects-GNNs.

Effects of Dropout on Performance in Long-range Graph Learning Tasks
Jasraj Singh'*
Keyue Jiangat Nanyang Technological University
Brooks Paige"
Laura Toni
University College London
Abstract
Message Passing Neural Networks (MPNNs) are class of Graph Neural Net- works (GNNs) that propagate information across the graph via local neigh- borhoods. The scheme gives rise to two key challenges: over-smoothing and over-squashing. While several Dropout-style algorithms, such DropEdge and DropMessage, have successfully addressed over-smoothing, their impact on over- squashing remains largely unexplored. This represents critical gap the lit- erature, as failure to mitigate over- squrssqu would make these methods unsuit- able for long-range tasks the intended use case of deep MPNNs. this work, we study the aforementioned algorithms,, and closely related edge-dropping algo- rithms - DropNode, DropAgg and DropGNN - the context of over-squashing. We present theoretical results showing that DropEdge-variamt ity between distant nodes, limiting their suitability for long-range tasks. To ad- dress this, we introduce DropSens, sensitivity is developed following the message-passingg scheme of GCN. DropSens explic- itly controls the proportion of information lost due to edge-dropping, thereby in- creasing sensitivity to distant nodes despite dropping the same number of edges. Our experiments on long-range synthetic and real- worldworld datasets confirm the pre- dicted limitations of existing edge-dropping and feature-dropping methods. More- over, DropSens with GCN consistently outperforms graph rewiring techniques designed to mitigate over-squashing, suggesting that simple, targeted modifica- tions can substantially improve a model's ability capture long-range interac- tions. Our conclusions highlight the need to re-evaluate and re-design existing methods for training deep GNNs, with renewed focus on modelling long-range interactions. The code for reproducing the results in our this work is available at Effeets-
reduce sensitiv-
variant of DropEdge. which
Introduction
Graph neural networks (GNNs) [51, 73] are powerful neural models developed for modelling graph-structured data, and have found applications in several real-world scenarios [29, 61, 84, 90- 94, 96, 101]. A popular class of GNNs, called message-passinn cursively process neighborhood information using message- -assiing layers. These layers are stacked to allow each node to aggregate information from increasingly larger neighborhoods, akin to how convolutional neural nelworks (CNNs) learn hierarchical features for images [48]. However, un- like image-based deep learning, where ultra-deep CNN architectures have led to performance breakthroughs [38, 80), shallow GNNs often outperform deeper models many graph learning
neural networks (MPNNs) [32], re-
Part of the work done master's student UCL. Primary supervisor: Correspondence Jasraj Singh <j <jasraj s1ngho01500@ma11.. com> and Keyue Jiang <keyue jiang. 180ucl uk>.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

tasks [99]. This is because deep GNNs suffer from unique issues like over-smoothing [65] and over-squashing [4], which makes training them notoriously difficult.
Over-smoothing refers to the problem of node representations becoming too similar as they are recursively processed. This is undesirable since it limits the GNN from effectively utilizing the information in the input features. The problem has garnered significant attention from the research community, resulting in a suite of algorithms designed to address it [72] (see Appendix A.1 for an overview of representative methods). Amongst these methods are a collection of random edge- dropping algorithms, including DropEdge [70], DropNode [23], DropAgg [43] and DropGNN [66]- which we will collectively refer to as DropEdge-variants
which act as prsssage-passing reducers. In addition, we have DropMessage [21], which performs Dropout [79] on the message matrices, instead of the feature matrices; we will collectively refer to these two methods as Dropout-variants since they are applied along the feature dimensions.
The other issue specific to GNNs is over-squashing. In certain graph structures, neighborhood size grows exponentially with distance from the source [12], causing information to be lost as passes through graph bottlenecks [4]. This limits MPNNs' ability to enable communication between distant nodes, which is crucial for good performance on long-range tasks [52]. To alleviate over-squashing, several graph-rewiring techniques have been proposed, which aim to improve graph connectivity by adding edges in a strategic manner [4. 8, 16, 44, 64] (see Appendix A.3 for an overview of representative methods).? In contrast, the DropEdge- Sropiee-varianns variants only remove edges, which should, in
principle, amplify over-squashing levels. The same can be intuitively argued about Dropout-varian variants.
Empirical evidence in support of methods designed for training deep GNNs has been majorly col- lected short-range tasks (see Appendix A.2 for a detailed discussion). That is, it simply suggests that these methods prevent loss of local information, but it remains inconclusive if they facilitate capturing long-range interactions (LRIs). Of course, on long-range tasks, deep GNNs are useless if they cannot capture LRIs. This is especially a concern for DropEdge-variants since evidence sug- gests that alleviating over-smoothing with graph rewiring could exacerbate over-squashing [34, 64).
Contributions. In this work, we precisely characterize the effects of random edge-dropping al- gorithms on over-squashing in MPNNs. By explicitly computing the expected sensirivity of the node representations to the node features [81] (inversely related to over-squashing) in a linear Graph Convolutional Network (GCN) [47], we show that these methods provably reduce the effective ceptive field of the model. Precisely speaking, the rate at which sensitivity between nodes decays is exponential w.r.t. the distance between them. We also extend the existing theoretical results on sensitivity in nonlinear MPNNs [8, 18, 86] to the random edge-dropping setting, concluding that these algorithms exacerbate the over-squashing problem. We use our analysis of GCNs design sensitivity-aware DropEdge-variant. named DropSens, that enjoys the representational expressivity of DropEdge without suffering from over-squashing, thereby demonstrating how algorithms can be readily adapted for long-range tasks.
We evaluated the DropEdge- and Dropout-variane on long- rang-range datasets using GCN, Graph Iso- morphism Network (GIN) [87] and Graph Attention Network (GAT) [83] architectures. Specifically, follow the setup in [33] with the SyntheticZIINC dataset, in [81] with real-world homophilic (corresponding to short-range tasks) and heterophilic (long-range tasks) node classification datasets, and in [8, 44] with graph classification datasets. Our results indicate that while the random dropping methods improve model performance in short-range tasks, they are often ineffective, and sometimes even detrimental, to long-range task performance. Finally, we present results for DropSens, which outperforms state-of-the-as classification and saah-classification tasks. These findings point to the importance of re-evaluating the methods used to train deep GNNs, especially in terms of how well they capture LRIs.
graph rewiring methods aimed at addressing over-squashing at node
2 Background
Consider a directed graph g = (V,ε), with V = [M]= (1...,,N) denoting the node set and
EC V x V the edge set; (j + i) E & if there's 's an edge from node j to node i. Let A E {0, 1) 1 denote its adjacency matrix, such that A,₃ = 1 if and only if (j - i) E &, and let D == diag (A1 w) denote the in-degree matrix. The geodesic distance, dg (j.)). from node j node is the length
Sometimes, along with removal of some edges preserve statistical properties of the original topology.

---

of the shortest path starting at node j and ending at node i. Accordingly, the Ł-hop neighborhood of a node i can be defined as the set of nodes that can reach it in exactly E' E No steps, (( (i) {j V: dg (j.z) = f}.
2.1 Graph Neural Networks
Graph Neural Networks (GNNs) operate inputs of the form (G, X), where G encodes the graph
topology and X E IR~*H()) collects the node features. Message-Passing Neural Networks (MPNNs) [32] are special class of GNNs which recursively aggregate information from the 1- hop neighborhood of each node using message-pante paaising layers. An L-layer MPNN is given as
!pd! () (2) (E-1), ,Ag' (1)
(z1 f00") : (JES((())))
AA [
(2.1)
MPNN, (9. = Out (f2!)
where (0)) = X. Agg denotes the aggregation fumctions, Upd the update functions, and Out the readout function. Since z(()) is function of the input features of nodes at most L-hops away from it, its receptive field is given by B(L) (i) == ( V dg (j, S I.).
For example, a GCN [47] updates node representations as the weighted sum of its neighbors' repre- sentations:
= = (AZ(
(2.2)
where is a point-wise nonlinearity, e.g. ReI.U, the propagation matrix, Á, is graph shift operator, i) E E or i = j. and (( E ( xx is a weight matrix. The original choice for À was the symmetrically
ie. Aij f if and only if (j +
x normalized adjacency matrix A = 1-2 AD [47], where Ā = A + In and D diag( A11 However, several influential works have also used the asymmetrically normalized adjacency, A asym D- Á [36, 50, 74].
1/2
2.2 DropEdge-variants
DropEdge [70] is random data augmentation technique that works by sampling a subgraph of the input graph in each layer, followed by the addition of self-loops, and uses that for message passing. Several variants of DropEdge have also been proposed, forming a family of random edge-dropping algorithms for tackling the over-smoothing problem. For example, DropNode [23] independently samples nodes and sets their features to 0, followed by rescaling to make the feature matrix unbi- ased. This is equivalent to setting the corresponding columns of the propagation matrix to O. In a similar vein, DropAgg [43] samples nodes that don't 't aggregate messages from their neighbors. This is equivalent to dropping the corresponding rows of the adjacency matrix. Combining these two approaches, DropGNN [66] samples nodes which neither propagate nor aggregate messages in given layer. These algorithms alleviate over- wer-smoothing by reducing the number of messages being propagated in the graph, thereby slowing down the convergence of node representations.
2.3 Dropout-variants
Dropout is a stochastic regularization technique which reduces over-fitting by randomly dropping features before each layer. It has been successful with various architectures, like CNNs [79] and transformers [82], and has also found applications in GNN training. DropMessage [21] is a variant of Dropout designed specifically for pessage-passing schemes it acts directly on the messages over each edge, instead of the node representations. This reduces the induced variance in the messages compared Dropout, DropEdge and DropNode, while the same time making the method more effective at alleviating over-smoothing and enabling the training of deep GNNs.
To keep things simple, will ignore edge features.
3

---

2.4 Over-squashing
Over-squashing refers the problem of information from exponentially growing neighborhoods [11] being squashed into finite-sized node representations [4]. [81] formally characterized over- squashing in terms of the Jacobian of the node-level representations w.r.t the input features: ||0,{-/ /0æ, |.- Accordingly, over-squashing can be understood as low sensitivity between distant nodes, i.e. small perturbations in a node's features don't effect other distant nodes' representations.
See Appendix for an extensive discussion of related works addressing the problems of over- smoothing and over-squashing, and unified treatment of the two.
3 Sensitivity Analysis
In this section, we perform a theoretical analysis of the expectation - w.r.t random edge masks of sensitivity of node representations. This will allow to predict how PropEdge-variants affect communication between nodes at various distances, which relevant for predicting their suitability towards learning LRIs.
Here, we present our analysis for linear GCNs, and treat more general nonlinear MPNN architectures in Appendix C.I. In this model, the final node representations can be summarised as
z
II A
XW E NxH
(3.1)
where W = I1 w E ( xH( Using the i..d. assumption on the distribution of edge
masks in each layer, (M()) ME the expected sensitivity of node to node be shown to be
(z! dz,
= E A
E
M
(3.2)
To keep things simple, will ignore the effect of DropEdge-variante the optimization trajectory. Accordingly, it is sufficient to study E[Å] in order predict their effect over-squashing. To maintain analytical tractability, we assume the use of an asymmetrically normalized adjacency matrix for message-passing A Á asym
Lemma 3.1. The expected propagation matrix under DropEdge (DE) is given as:
1 gdi+1
Pa = EDE
A
(1 (d: +1
(3.3)
P. EDE
[is] d; (1 9) (d: + 1)
1
- 9 g
where E [0, 1) is the dropping probability and (j i) E
See Appendix B.1 for proof, and similar treatment of DropNode, DropAgg and DropGNN. 1-Layer Linear GCNs. Vq E (0, 1) and nodes i, such that (j - i) E E, we have
d
1
Pu
d; +1
d, +1
(3.4)
1 Ps d
1 Ps
d +1
where the right-hand sides of the two incqualities are the corresponding entries in the propagation matrix of NoDrop model. Equations 3.3, 3.4, 16 and B.17 together imply the following result:
*We use P denote expected propagation matrix under asymmetric propagation rule. Ap- pendix D.2, use P to denote the expected propagation matrix under the symmetric propagation rule.

---

Influene Dietrinal Aol
0.0
doltA-0
deP.11
4.H.0 --
NeDrn
0.8
daP,3
Dripāage
Dropfgg
Drapders
Shortest Distance, dali,))
DropEdge Probabilit.
Shorest Distances
(a) Entries of p decay at exponential rate w.r.t. distance between nodes, and polynomial rate w.r.t. the DropEdgee probability.
(b) MC-approximation of influ- ence distribution in ReLUUGGNS.
Figure I: Empirical sensitivity analysis using the Cora dataset. The plot embedded in Figure lb shows the ratio of influence under DropSens that under DropEdge, at different distances.
Lemma 3.2. In I-layer linear GCN with Á Aasym, using DropEdge, DropAgg or DropGNN
1. increases the sensitivity of node's representations to its own input features, and
2. decreases the sensitivity to its neighbors' features.
L-layer Linear GCNs. Unfortunately, we cannot draw similar conclusions in L--aaer networks, for nodes at arbitrary distances. To see this, view P as the transition matrix of non-uniform random walk. This walk has higher self-transition (2 = j) probabilities than in a uniform augmented random walk (T = A q = 0), but lower inter-node (i # j) transition probabilities. Note that PL and T store the L-step transition probabilities in the corresponding walks. Then, since the paths connecting the nodes V and j B(L-1) (i) may involve self-loops, (P4);) may be lower or higher than (Th);g) Therefore, we cannot conclude how sensitivity between nodes separated by most /. hops changes. For nodes I--hops away, however, we can show that DropEdge always decreases the corresponding entry in pL, reducing the effective reachability of GCNs. Using Equations B.16 and 17, we can show the same for DropAgg and DropGNN, respectively.
Theorem 3.1. In an L-layer linear GCN with A Ausym using DropEdge. DropAgg or DropGNN decreases the sensitivity of node i V to another node j E S (i), thereby reducing its effective receptive field. Moreover, the sensitivity decreases with increasing dropping probability.
See Appendix B.2 for a precise quantitative statement and the proof.
Nodes at Arbitrary Distances. Although no general statement could be made about the change in sensitivity between nodes up to L hops away, we can analyze such pairs empirically. We compute the L-hop transition matrix P proportional to expected sensitivity linear GCNs under DropE- dge - for the Cora dataset, and average the entries after binning node pairs by the shortest distance between them. The results are shown Figure la. In the left subfigure, we observe that the expected sensitivity decays at an exponential rate with increasing distance between the corresponding nodes. In the middle subfigure, we observe that DropEdge increases the expected sensitivity between nodes close to each other (0-hop and 1-hop neighbors) in the original topology, but reduces it between nodes farther off. Similar conclusions can be made with the symmetrically normalized propagation matrix (see Appendix D.2). Note that the ever-squashing effects of DropAgg and DropGNN would, in theory, be even more severe, as suggested by Equations 16 and B.17.
Nonlinear MPNNs. While linear networks are useful in simplifying the theoretical analysis, they are often not practical. Appendix C.I, we treat the upper bounds sensitivity established in previous works, and extend them to the saapEde--vriintt Even still, although theoretical bounds offer valuable guarantees, they can be arbitrarily loose the absence eтror quantification, making their practical relevance unclear. To reliably conclude the empirical behaviour of DropEdge- and Dropout-variants we turn to Monte Carlo simulations with ReL.UGCNs:: see Appendix D. for description of the experiment setup. Figure 1b compares the influence of the source nodes [86] at different distances using a dropout probability of 0.5. We observe that while the effect of DropNode on the sensitivity profile as compared to the baseline NoDrop is relatively insignificant, models
5

---

using DropEdge, DropAgg and DropGNN have remarkably lower sensitivity to distant nodes, as predicted by our theory.
4 Sensitivity-Aware DropEdge
Lemma 3.1 tells us that DropEdge decreases the weight of cross-edges, (j + z), in the expected propagation matrix, i.e. the strength of message passing over these edges decreases. The fraction of information preserved over a cross-edge dependent only on the dropping probability and the target node's in-degree, d, We can directly control this quantity using per-edge dropping probability, 9i. dependent only on the receiving node's in-degree:
ÉDE [Ani] END Ai)
d2 +
1- 9 1:+1
-1
9i qi
d++1
(4.1)
di
(1 26) (d: +1)
di (1 qb)
where c is the fraction of information preserved, c.g. 95%, and ND refers to a NoDrop model. We can solve for q, and mask the incoming edges node accordingly; name this algorithm DropSens. In Appendix E.3, we present a Python implementation of the algorithm, as well as a computationally efficient approximation to Equation 4.1. In the plot embedded in Figure 1b, can observe that DropSens increases the influence of distant nodes, as compared to DropEdge.
Note that higher values of encourage lower q:, while lower values permit q to take higher values; see Figure 7a. Since this can result in abnormally high dropping probabilities, we clip the value of Øs in our experiments using another hyperparameter, Gmax; see details in Appendix F.2.
Challenges in Extending to GIN and GAT. DropSens has been specifically derived for GCN-style architectures, where the edge weights used in message aggregation are simple functions of node degree. Extending other architectures raises nontrivial challenges:
1. GIN uses constant edge weights, so the sensitivity of a node its neighbors simplifies to (1 2) ||W] for dropping probability Enforcing a fixed information preservation ratio e gives 7 = c, which equivalent to DropEdge. This limitation arises because GIN's neighbour-eeighing scheme is independent of the node degrees, making a principled variant of DropSens unnecessary.
2. GAT, in contrast, uses (cature-dependee attention weights that vary every layer and iteration. This means a DropSens-style approach would require recomputing edge masks in each iteration and each layer, compromising the simplicity aimed for. Moreover, the presence softmax attention makes the closed-form of sensitivity complicated.
5 Experiments
Our theoretical analysis indicates that random dropping may degrade the performance of GNNs in tasks that depend on capturing LRIs. In this section, we test this hypothesis by evaluating DropEdge- and Dropout-variants on both synthetic and real-world datasets. A complete description of the datasets provided in Appendix 1, and the experimental details are in Appendix E.2.
5.1 Synthetic Datasets
SyntheticZINC [33] a synthetic variant of the ZINC dataset [42], designed to study the effect of information mixing in graph learning. Node features are sparsely assigned, and the target requires non-linear mixing of two selected nodes' features, chosen based on their commute time [10]. We vary the mixing level and evaluate 11-layer GCN, ensuring sufficient message passing. For better readability, we only test DropEdge, Dropout and DropMessage - the three more popular methods used for training deep GNNs.
The results are presented in Figure where we can observe that the mean absolute error (MAE) increases with the commute time percentile used to select the node pairs, as was hypothesized and evidenced [33]. Additionally, we observe that both train and test performance decline when using dropout with probability as low as 0.2, and even more so with a higher probability of 0.5. These results provide strong evidence for the detrimental effects of dropout methods in modelling long- range interactions, supporting our theoretical analysis.

---

Test MAE
3.20
3.0
0d
Commute Time Percentile
Commute Time Percentile
NoDrop(O..)
DropEdge(0.21 DrupEdlge(0.5)
Dropout(0.2)
DropMessage(C.22
Dropout(0.5)
DrapMesaag:(0.5)
Figure Train and test MAE of 11 layer GCNs on the SyntheticZINC dataset, averaged over 10 initializations.
5.2 Real-world Datasets
To test the dropping methods on real- real-world datasets, we use the GCN, GIN [87] and GAT [83] architectures GCN and GIN satisfy the model assumptions made in all the theoretical results pre- sented Section 3, while GAT does not satisfy any of them, since the attention scores are computed as a function of all the node representations. Therefore, GCN, GIN and GAT together provide broad representation of different MPNN architectures. We present the results for GCN and GIN in the main text, since these models were used as baselines in majority of works on alleviating over-squahhing [4, 5, 8, 35, 44, 69, 81]; the results for GAT are reported in Table 7.
For each dataset-model model-dropout combination, we perform 20 independent runs to find the best performing dropout configuration; results are reported in Table 10. We then perform a t-test to assess whether dropout improves performance, using 50 samples from the NoDrop model (g 0) and 50 samples from the best performing dropout configuration." In this section, we report the p-values of the tests, and in Table 8, we report the effect sizes as Hedges' g statistic [39].
Node-classffication. Although determining whether a task requires modelling LRIs be chal- lenging, understanding the structure of the datasets can provide important insight. For example, homophilic datasets have local consistency in node labels, i.e. nodes closely connected each other have similar labels. On the other hand, in heterophilic datasets, nearby nodes often have dissimilar labels. Since DropEdge-variants increase the sensitivity of node's representations its immedi- ate neighbors, and reduce its sensitivity to distant nodes, we expect it to improve performance on homophilic datasets but harm performance on heterophilic ones; such setup was also used in [81]. In this work, we use Cora [58], CiteSeer [31] and PubMed [63]] as representatives of homophilic datasets [53, 100], and Squirrel, Chameleon and TwitchDE [71] represent heterophilic datasets [53]. The networks' statistics are presented in Table 4, where we can note the remarkably lower homophily measures of heterophilic datasets.
The results are presented in Table 1a. It is clear to see that dropout can significantly improve test per- formance on homophilic datasets with 31/54 57% cases performing better than the correspond- ing NoDrop baseline indicating that these methods are indeed beneficial in tackling short-range tasks. On the other hand, with the heterophilic datasets, the improvement is insignificant. Rather, in most (46/54 z 85%) cases, the best dropout configuration performs worse than the NoDrop base- line. This suggests that the dropping methods harm generalization in long- rangrange tasks by forcing models to overfit to short-range signals (see Appendix F.3 for supporting evidence).
Graph-classfficttinn. Several graph classification datasets have also been identified as long-range tasks, like the molecular networks datasets Mutag [17], Proteins [19] and Enzymes [9], and the social networks datasets Reddit, IMDb and Collab [89]. These datasets have also been used for evaluation in previous works on over-squashing, including [8, 44].
'The t-test assumes that both samples are drawn from normal distributions all Shapiro Wilk tests for non-normality of samples [76] failed at 90% confidence.

---

Table Difference in mean test accuracy (%) between the best performing configuration of each dropout method and the baseline NoDrop model. Cell colors represent p p-values from a t-test evaluating whether dropout improves performance: green indicates significance at 90% confidence, while red denotes insignificant results.
(a) Node classification tasks.
Homophilic Networks
Heterophilic Networks
GNN
Dropout
Cora
CiteSeer
PubMed
Chameleon
Squirrel
TwitchDE
DropEdge
+0.215
+0.515
-0.100
-1.711
00.34
-0.041
DropNode
+0.213
-0.302
0.082
-4.987
-1.307
-1.180
DropAgg
+0.092
+0.552
-0.429
15. 180
- -337788
-5.306
GCN
DropGNN
+0.372
+0.727
-0.194
-3.841
-1.451
-0.950
Dropout
+0.418
0.262
+1.111
-3.672
-1229
0.516
DropMessage
+0.140
+0,092
+0.820
-1,501
0.549
-0,270
DropEdge
5..370
11.991
-3.977
-7.814
-1.503
-0.724
DropNode
+3.983
+44.211
+1.260
-2655
-0.871
-0.426
DropAgg
-2.655
11.098
2.038
-7.233
-.973
-..28
GIN
DropGNN
0.929
10.150
-2.880
9.544
-5.118
0.057
Dropout
+4.771
+3.128
+2.311
-0.865
+1.062
-1.254
DropMessage
+5.661
+.2841
+22003
+-1.443
+-2.499
-1.919
(b) Graph classification tasks.
Molecular Networks
Social Networks
GNN
Dropout
Mutag
Proteins
Enzymes
Reddit
IMDb
Collab
DropEdge
-1.200
+0.482
-3.032
-6.280
+0.680
-3.353
DropNode
+0.000
+0.875
3.083
10.930
-0.20
4.511
DropAge
+1.100
0.286
5.424
17.450
+0.540
20.940
GCN
DropGNN
+2.600
+0.482
2.900
12.940
-1.180
-0.800
Dropout
-2.700
-0.089
4.485
-0.920
+-0.580
33.299
DropMessage
0.200
+0.393
-3.884
3.770
+3.420
-2.007
DropEdge
2.900
-..44
8.954
-0.430
-0.240
-0.558
DropNode
8.500
+0.536
-7.568
-1.500
+0.380
-0.125
DropAgg
+0,200
+0..443
-0.640
-1.660
-0.800
-0.988
GIN
DropGNN
33.700
-0.661
-11.745
-4.150
-2.740
-3.456
Dropout
+0.600
+0.661
-2.042
+0.390
+0.080
-0.383
DropMessage
+1.100
+1.536
-2.406
-0.130
+1.340
-1.506
The results shown in Table lb, where observe that dropout methods usually detrimental to model performance, often recording a non-positive effect (62/ Rs 61% cases). Notably, the p-values are lower compared to those recorded for heterophilic datasets in Table 1a, i.e. higher evidence for efficacy of dropping methods. We conjecture that over-squashing may have limited impact model performance in graph-level tasks since the aggregation module eventually mixes information from distant nodes for computing graph-level representations.
5.3 Evaluating DropSens
We start by comparing DropSens with DropEdge on real-world datasets from Section 5.2. illustrating how algorithms can be readily adapted for better suitability modelling LRIs. In Figure 3, we present the relative change in еттог rate (1 Acc) of DropSens w.r.t. DropEdge, with GCN as the base model. clear to observe uniform improvement in the performance on long-range tasks, suggesting that addressing over-squashing using DropSens can enhance the effectiveness of GCNs.
Finally, benchmark DropSens against state-of-the-art graph-rewiring techniques designed specif- ically to tackle over-squashing (see Appendix A.3 for their descriptions). We train a GCN on node classification tasks, following the setup in [81], and both GCN and GIN on graph classification tasks, following [8, 44]. The results with GCN are reported in Table 2, where we find that DropSens
We exclude Collab GAT due unsuccessful runs.

---

22.5
20.0
1.21
Relative Error Change geg
15.0
12.5
10.0
+1.50
22224
0.61
0.00
5.0
2.5
40.11
0.05
+0.31
0.26
0.0
Cora
Cite
PubMed
Chameleon
Squirrel
TwitchDE
Actor
Mutap
Proteins
Enzymea mizymes
Reddit
IMDb
Collab
Figure 3: Relative change in test-time performance GCN using DropSens, compared to the baseline DropEdge, on real-world datasets from Section 5.2. Text over each bar indicates the difference between mean performance of DropSens and DropEdge, and corresponding standard
Table 2: Performance of GCN with graph rewiring methods. First, second, and third best results are coloured.
(a) Node-classifiction tasks results for other methods taken from [81, Table 2).
Rewiring
Cora
CiteSeer
PubMed
Chameleon
Squirrel
Actor
None
81.89
72.31
78.16
41.33
30.32
23. 84
Undirected
42.02
35.53
21.45
+FA
81.65
70.47
79.48
42.67
36.86
24.14
DIGL (PPR)
83,21
73,29
78.84
42.02
33.22
24.77
DIGL + Undirected
42.68
32.48
25.45
SDRF
82.76
72.58
79.10
42.73
37.05
28.42
SDRF Undirected
44.46
37.67
28.35
DropSens
85.17
73.81
83.76
$3.45
39.72
22.89
(b) Graph-classification tasks results for other methods from [8. Table
Rewiring
Mutag
Proteins
Enzymes
Reddit
IMDb
Collab
None
72.15
70.98
27.67
68.26
49.77
33.78
Last FA
70.05
71.02
26.47
68.49
48.98
33.32
Every
70.45
60.04
18.33
48.49
48.17
51.80
DIGL
79.70
70.76
35.72
76.04
64.39
54.50
SDRF
71.05
70.92
28.37
68.62
49.40
33.45
FoSR
80.00
73.42
25.07
70.33
49.66
33.84
GTR
79.10
72.59
27.52
68.99
49.92
33.05
DropSens
75.30
73.27
28.42
80.16
49.34
64.16
outperforms other methods in node classification tasks, and performs competitively in graph classi- fication tasks. In addition to superior performance, another advantage of DropSens over the other methods is that it significantly reduces the number of messages being propagated, thereby tackling the problem of over-smoothing and increasing training speed.
The results with GIN are presented in Appendix G.4, where we observe that DropSens does not per- form competitively - unsurprising, since DropSens was specifically designed to work with GCN's message-passing scheme.
6 Conclusion
There exists an important gap in our understanding of several algorithms designed for training deep GNNs while their positive effects on model performance have been well-studied, making them popular choices for training deep GNNs, their evaluation has been limited to short-range tasks.

---

This is rooted in key assumption: that if deep GNN is trainable, it must also be capable of modelling LRIs. As result, potential adverse effects of these algorithms on capturing LRIs have been overlooked. Our results challenge this assumption we theoretically and empirically show that DropEdge- and Dropout-variants exacerbate the over-squashing problem in deep GNNs, and degrade performance on long-range tasks. This highlights the need for more comprehensive evaluation of common training practices for deep GNNs, with special emphasis on their capacity to capture LRIs. This is crucial for building confidence in their use beyond controlled benchmarks.
Limitations. While our theoretical analysis successfully predicts how DropEdge-variants variants affect test performance on short-range and long-ran rangge tasks, it is based on several simplifying assumptions on the message-pant -aasgge--pginggggg scheme. These assumptions, although standard in the literature, limit the generalizability of our conclusions to other architectures, including ResGCNs [51]. GATs [83], and Graph Transformers [85]. Additionally, an important limitation of DropSens is that it requires an architecture-speciie alteration to the edge-dropping strategy, which is not practical in general. As also mentioned Section 4, we did not intend to introduce DropSens as a benchmark, but rather to demonstrate how methods designed for alleviating over-smoothing can be readily adapted to simultaneously control over-squashing
Future Directions. Currently, real-world datasets are classified as short- or long-range tasks based on extensive model training [4] or weak proxy measures like node homophily [81]. Developing a reliable measure of information mixing in the ground ground-truth -ruth data could greatly benefit the research community. Such measure would enable more precise identification of short-, intermediate- and long-range tasks, improving evaluation and benchmarking. Another interesting direction is to in- vestigate the significance MPNNs enables some mixing of information from distant nodes. To the best of our knowledge, [33] the only work that directly addresses this question, offering strong theoretical insights. However, empirical validation of these effects remains limited.
over-squashin
graph-level tasks, where the aggregation module of
Acknowledgement
Keyue Jiang was supported by the UKRI Engineering and Physical Sciences Research Council (EP- SRC) Igrant number EP/R513 143/11. The authors would like to thank the anonymous reviewers for their helpful comments and insights.
References
[1] Zeyuan Allen-Zhu, Aditya Bhaskara, Silvio Lattanzi, Vahab Mirrokni, and Lorenzo Orec- chia. Expanders via local edge flips. In Proceedings of the Twenty-Sevent Annual ACM- SIAM Symposium on Discrete Algoritiums, SODA '16, pp. 259-269, USA, 2016. Society for Industrial and Applied Mathematics.
[2] N. Alon and V. D. Milman. A1, isoperimetric inequalities for graphs, and superconcentrators. Journal of Combinatorial Theory, Series B, 388(1))73-88, February 1985.
[3] Noga Alon. Eigenvalues and expanders. Combinatorica, ((2):33-9,, June 1986.
[4] Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations, 2021.
[5] Adrián Arnaiz Rodrizuz Ahmed Begga, Francisco Escolano, and Nuria M Oliver. Diffwire: Inductive graph rewiring via the lovász bound. In Bastian Rieck and Razvan Pascanu (eds.), Proceedings of the First Learning on Graphs Conference, volume 198 of Proceedings of Machine Learning Research, pp. 15:1-15:27. PMLR, 12 2022.
[6] Pradeep Kr. Banerjee, Kedar Karhadkar, Yu Guang Wang, Uri Alon, and Guido Montúfar. Oversquashing in gnns through the lens of information contraction and graph expansion. In 2022 58th Anmual Allerton Conference on Communication, Control, and Computing (Aller- ton), pp. 1-8. IEEE Press, 2022.
[7] Pablo Barceló, Egor V. Kostylev, Mikael Monet, Jorge Pérez, Juan Reutter, and Juan Pablo Silva. The logical expressiveness of graph neural networks. International Conference on Learning Representations, 2020.
10

---

[8] Mitchell Black, Zhengchao Wan, Amir Nayyeri, and Yusu Wang. Understanding oversquash- ing GNNs through the lens of effective resistance. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Proceed- ings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 2528- 2547. PMLR, 07 2023.
[9] Karsten M. Borgwardt, Cheng Soon Ong, Stefan Schönauer, S. V. N. Vishwanathan, Alex J. Smola, and Hans-Peter Kriegel. Protein function prediction via graph kernels. Bioinformatics, 21 [ 06 2005.
[10] Ashok K. Chandra, Prabhakar Raghavan, Walter L. Ruzzo, Roman Smolensky, and Prasoon Tiwari. The electrical resistance of a graph captures its commute and cover times. computa- tional complexity, 6:3 6:312-340, 1989.
[11] Jianfei Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with variance reduction. In International Conference on Machine Learning, pp. 941-949, 2018.
[12] Jie Chen, Tengfei Ma, and Cao Xiao. FastGCN: Fast learning with graph convolutional networks via importance sampling. In International Conference on Learning Representations, 2018.
[13] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 1725-1735. PMLR, 07 2020.
[14] Jacob Cohen. Statistical Power Analysis for the Behavioral Sciencesstical power analysis for the behavioral sciences. Lawrence Erlbaum Associates, Hillsdale. NJ, 2 edition, 1988.
[15] Colin Cooper, Martin Dyer, Catherine Greenhill, and Andrew Handley. The flip markov chain for connected regular graphs. Discrete Applied Mathematicx, 254:56-79, 2019.
[16] Andreea Deac, Mare Lackenby, and Petar Veličković. Expander graph propagation. In NeurlPS 2022 Workshop: New Frontiers in Graph Learning, 2022.
[17] Asim Kumar Debnath, Rosa L. Lopez de Compadre, Gargi Debnath, Alan J. Shusterman, and Corwin Hansch. Structure-activis relationship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity. Journal of Medicinal Chemistry, 34(2):786-797, Feb 1991.
[18] Francesco Di Giovanni, Lorenzo Giusti, Federico Barbero, Giulia Luise, Pietro Lio, and Michael M Bronstein. On over-squashing in message passing neural networks: The im- pact of width, depth, and topology. In International Conference on Machine Learning, pp. 7865-7885, PMLR, 2023.
[19] Paul D. Dobson and Andrew J. Doig. Distinguishing enzyme structures from non-enzymes without alignments. Journal of Molecular Biology, 330(4):771-783 2003.
[20] Vijay Prakash Dwivedi, Ladislav Rampášek, Mikhail Galkin, Ali Parviz, Guy Anh Luu, and Dominique Beaini. Long range graph benchmark. In Thirty-sixth Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2022.
Anh Tuan
[21] Taoran Fang. Zhiqing Xiao, Chumping Wang, Jiarong Xu, Xuan Yang. and Yang Yang. Dropmessage:
Unifying random dropping for graph neural networks. Proceedings of the AAAI Conference on Artificial Intelligence, 37(4):4267 Jun. 2023.
[22] Tomas Feder, Adam Guetz, Milena Mihail, and Amin Saberi. A local switch markov chain on given degree graphs with application in connectivity of peer-to-peer networks. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 06), pp. 69-76, 2006.
[23] Wenzheng Feng, Jie Zhang, Yuxiao Dong. Yu Han, Huanbo Luan, Qian Xu, Qiang Yang, Evgeny Kharlamov, and Jie Tang. Graph random neural networks for semi-supervised learn- ing on graphs. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances Neural Information Processing Systems, volume 33, pp. 22092-22103. Curran Associates, Inc., 2020.
11

---

[24] Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
[25] Rickard Brüel Gabrielsson, Mikhail Yurochkin, and Justin Solomon. Rewiring with positional encodings for graph neural networks. Transactions on Machine Learning Research, 2023.
[26] Yarin Gal and Zoubin Ghahramani. Bayesian convolutional neural networks with bernoulli approximate variational inference, 2016.
[27] Yarin Gal and Zoubin Ghahramani. Dropout as bayesian approximation: Representing model uncertainty in deep learning. Maria Florina Balcan and Kilian Q. Weinberger (eds.), Proceedings of The 33rd International Conference Machine Learning, volume 48 of Pro- ceedings of Machine Learning Research, pp. 1050-1059, New York, New York, USA, 06 2016. PMLR.
[28] Yarin Gal and Zoubin Ghahramani. A theoretically grounded application of dropout in current neural networks. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 29. Curran Associates, Inc., 2016.
[29] Hongyang Gao, Zhengyang Wang, and Shuiwang Ji. Large-scale learnable graph convo- lutional networks. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1416-1424. ACM, 2018.
[30] George Giakkoupis. Expanders via local edge flips in quasilinear time. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, pp. 64776, New York, NY, USA, 2022. Association for Computing Machinery.
[31] Lee Giles, Kurt D. Bollacker, and Steve Lawrence. Citeseer: an automatic citation indexing system. In Proceedings of the Third ACM Conference on Digital Libraries, DL '98, pp- 89-98, New York, NY, USA, 1998. Association for Computing Machinery.
[32] Justin Gilmer, Samuel Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Doina Precup and Yee Whye Tch (eds.), Proceedings of the 34th International Conference on Machine Learning, volume 70 of Pro- ceedings of Machine Learning Research, pp. 1263 1272. PMLR, 08 2017.
[33] Francesco Di Giovanni, T. Konstantin Rusch, Michael Bronstein, Andreea Deac, Mare Lack- enby, Siddhartha Mishra, and Petar Veličković. How does ver-sqqashing affect the power of GNNs? Transactions on Machine Learning Research, 2024.
[34] Jhony H. Giraldo, Konstantinos Skianis, Thierry Bouwmans, and Fragkiskos D. Malliaros. On the trade-off between wver-smoothing and over-squashing in deep graph neural networks. In Proceedings of the 32nd ACM International Conference on Information and Knowledge Management, CIKM '23, pp. 566-576, New York, NY, USA, 2023. Association for Comput- ing Machinery.
[35] Benjamin Gutteridge, Xiaowen Dong, Michael M Bronstein, and Francesco Di Giovanni. DRew: Dynamically rewired message passing with delay. In International Conference on Machine Learning, pp. 12252-12267. PMLR, 2023.
[36] Will Hamilton, Zhitao Ying. and Jure Leskovec. Inductive representation learning on large graphs. I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017
[37] Arman Hasanzadeh, Fhsan Hajiramezanali, Shahin Boluki, Mingyuan Zhou, Nick Duffield, Krishna Narayanan. and Xiaoning Qian. Bayesian graph neural networks with adaptive con- nection sampling, 2020.
[38] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 770-778, 2016.
12

---

[39] Larry V. Hedges. Distribution theory for glass's estimator of effect size and related estimators. Journal of Educational Statistics, 6(2):107-128, 2025/03/15/ 1981. Full publication date: Summer, 1981.
[40] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.0068) 2020.
[41] Lei Huang, Jie Qin, Yi Zhou, Fan Zhu, Li Liu, and Ling Shao. Normalization techniques in training dnns: Methodology, analysis and application, 2020.
[42] John J Irwin, Teague Sterling, Michael M Mysinger, Erin S Bolstad, and Ryan G Coleman. ZINC: a free tool to discover chemistry for biology. J Chem Inf Model, 5257):175--1768,
June 2012.
[43] Bo Jiang, Yong Chen, Beibei Wang, Haiyun Xu, and Bin Luo. Dropagg: Robust graph neural networks via drop aggregation. Neural Networks, 163:65-74, 2023.
[44] Kedar Karhadkar, Pradeep Kr. Banerjee, and Guido Montufar. FoSR: First-order spectral rewiring for addressing oversquashing in GNNs. In The Eleventh International Conference on Learning Representations, 2023.
[45] Kenji Kawaguchi. Deep learning without poor local minima. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 29. Curran Associates, Inc., 2016.
[46] Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Interna- tional Conference on Learning Representations (ICLR), San Diega, CA, USA, 2015.
[47] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017.
[48] Yann LeCun, Bernhard Boser, John Denker, Donnie Henderson, R. Howard, Wayne Hubbard, and Lawrence Jackel. Handwritten digit recognition with a pack-propagation network. In D. Touretzky (ed.), Advances in Neural Information Processing Systems, volume 2. Morgan- Kaufmann, 1989.
[49] Guohao Li, Matthias Müller, Ali Thabet, and Bernard Ghanem. Deepgens: Can gens go as deep as cnns? In 2019 IEEE/CVF International Conference on Computer Vision (ICCV), pp- 9266-9275, 2019.
[50] Qimai Li, Zhichao Han, and Xiao-ming Wu. Deeper insights into graph convolutional net- works for semi-supervised learning. Proceedings of the AAAI Conference on Artificial Intel- ligence, 32(1), 04 2018.
[51] Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard S. Zemel. Gated graph sequence neural networks. In Yoshua Bengio and Yann LeCun (eds.), 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016.
[52] Huidong Liang, Haitz Sáez de Ocáriz Borde, Baskaran Sripathmanathan, Michael Bronstein, and Xiaowen Dong. Towards quantifying long-range interactions in graph machine learning: a large graph dataset and measurement, 2025.
[53] Derek Lim, Xiuyu Li, Felix Hohne, and Ser-Nam Lim. New benchmarks for learning on non-homophilous graphs. arXiv preprint 4xX1v:2104.01404, 2021.
[54] Meng Liu, Hongyang Gao, and Shuiwang Ji. Towards deeper graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference Knowledge Discovery & Data Mining. ACM, 2020.
[55] Yang Liu, Chuan Zhou, Shirui Pan, Jia Wu, Zhao Li, Hongyang Chen, and Peng Zhang- Curvdrop: A ricci curvature based approach to prevent graph neural networks from over- smoothing and over-squashing. In Proceedings of the ACM Weh Conference 2023, WWw '23, pp. 221-230, New York, NY, USA, 2023. Association for Computing Machinery.
13

---

[56] L. Lovász. Random walks on graphs: A survey. Combinatorics, Paul Erdos is Eighty, 2(1): 1-46, 1993.
[57] Peter Mahlmann and Christian Schindelhauer. Peer-to-peer networks based on random trans- formations of connected regular undirected graphs. Proceedings of the Seventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '05, pp. 155-164, New York, NY, USA, 2005. Association for Computing Machinery.
[58] Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 3(2):127- 163, 07 2000.
[59] Péter Mernyei and Cătälina Cangea. Wiki-es: A wikipedia-based benchmark for graph neural networks, arXiv preprint arXiv:2007.02901, 2020.
[60] Aaron Meurer, Christopher P. Smith, Mateusz Paprocki, Ondřej Čertík, Sergey B. Kirpichev, Matthew Rocklin, AMiT Kumar, Sergiu Ivanov, Jason K. Moore, Sartaj Singh, Thilina Rath- nayake, Sean Vig, Brian E. Granger, Richard P. Muller, Francesco Bonazzi, Harsh Gupta, Shivam Vats, Fredrik Johansson, Fabian Pedregosa, Matthew Curry, Andy R. Terrel, Stěpán Roučka, Ashutosh Saboo, Isuru Fernando, Sumith Kulal, Robert Cimrman, and Anthony Sco- patz. Sympy: symbolic computing in python. PeerJ Computer Science, 3:e103, January 2017.
[61] Federico Monti. Michael Bronstein, and Xavier Bresson. Geometric matrix completion with recurrent multi-graph neural networks. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.). Advances in Neural Information Process- ing Systems, volume 30. Curran Associates, Inc., 2017.
[62] Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Mar- ion Neumann. Tudataset: A collection benchmark datasets for learning with graphs. In ICML 2020 Workshop on Graph Representation Learning and Beyond (GRL+ 2020), 2020.
[63] Galileo Mark Namata, Ben London, Lise Getoor, and Bert Huang. Query- active sur- veying for collective classification. In International Workshop on Mining and Learning with Graphs, Edinburgh, Scotland, 2012. MLG.
[64] Khang Nguyen, Hieu Nong. Vinh Nguyen, Nhat Ho, Stanley Osher, and Tan Nguyen. Revis- iting over-smoothing and over-squashing using ollivier-ricci curvature. In Proceedings of the 40th International Conference on Machine Learning, ICML'23. JMLR.org. 2023.
[65] Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In International Conference on Learning Representations, 2020.
[66] Pál András Papp. Karolis Martinkus, Lukas Faber, and Roger Wattenhofer. Dropgnn: Random dropouts increase the expressiveness of graph neural networks. M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neu- ral Information Processing Systems, volume 34, pp. 21997-22009, Curran Associates, Inc., 2021.
[67] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Yang, Zach Vetoto, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library, 2019.
[68] Hongbin Pei, Bingzhe Wei, Kevin Chen Chenn Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. In International Conference on Learning Repre- sentations, 2020.
[69] Chendi Qian, Andrei Manolache, Kareem Ahmed, Zhe Zeng, Guy Van den Broeck, Mathias Niepert, and Christopher Morris. Probabilistically rewired message-passing neural networks. In The Twelfth International Conference on Learning Representations, 2024.
14

---

[70] Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. In International Conference on Learning Reprexentations, 2020.
[71] Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-Scale Attributed Node Embed- ding. Journal of Complex Networks, 9(2,, 2021.
[72] T. Konstantin Rusch, Michael M. Bronstein, and Siddhartha Mishra. survey on oversmooth- ing in graph neural networks, 2023.
[73] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfar- dini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1)661-80, 2009.
[74] Michael Schlichtkrull, Thomas N. Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks, 2017.
[75] Ida Schomburg, Antje Chang, Christian Ebeling, Marion Gremse, Christian Heldt, Gregor Huhn, and Dietmar Schomburg. BRENDA, the enzyme database: updates and major new developments. Nucleic Acids Res, 32(Database issue):D431-3, January 2004.
[76] S. S. Shapiro and M. B. Wilk. An analysis of variance test for normality (complete samples). Biometrika, 52(3/4):591-61) 2025/03/12/ 1965. Full publication date: Dec., 1965.
[77] Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. Relational Representation Learning Workshop, NeurlPS 2018, 2018.
[78] Alistair Sinclair and Mark Jerrum. Approximate counting, uniform generation and rapidly mixing markov chains. Information and Computation, 82(1):93 133, 1989.
[79] Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdi- nov. Dropout: A simple way to prevent neural networks from overfitting. Journal of Machine Learning Research, 15(56))1929-199) 1958, 2014.
[80] Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Dumitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich. Going deeper with convolu- tions. In 2015 IEEE Conference Computer Vision and Pattern Recognition (CVPR), pp- 1-9, 2015.
[81] Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein. Understanding over-squashing and bottlenecks graphs via cur- vature. In International Conference on Learning Representations, 2022.
[82] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, E ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[83] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Repre- sentations, 2018
[84] Nikil Wale and George Karypis. Comparison of descriptor spaces for chemical compound retrieval and classification. In Sixth International Conference on Data Mining (ICDM'00) '06), pp. 678-689, 2006.
[85] Zhanghao Wu, Paras Jain, Matthew Wright, Azalia Mirhoseini, Joseph E Gonzalez, and Ion Stoica. Representing long-range context for graph neural networks with global attention. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
15

---

[86] Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 5453- 5462. PMLR, 07 2018.
[87] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks?, 2019.
[88] Han Xuanyuan, Tianxiang Zhao, and Dongsheng Luo. Shedding light on random dropping and oversmoothing, In NeurlPS 2023 Workshop: New Frontiers in Graph Learning. 2023.
[89] Pinar Yanardag and S. V.N. Vishwanathan. Deep graph kemels. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '15, pp. 1365-1374, New York, NY, USA, 2015. Association for Computing Machinery.
[90] Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD '18 pp. 974-983, New York, NY, USA, 2018. Association for Computing Machinery.
[91] Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, vol- ume 33, pp. 5812-5823. Curran Associates, Inc., 2020.
[92] Yuning You, Tianlong Chen, Zhangyang Wang, and Yang Shen. When does self-supervision help graph convolutional networks? In Hal Daumé III and Aarti Singh (eds.), Proceedings the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 10871-10880. PMLR, 07 2020.
[93] Yuning You, Tianlong Chen, Zhangyang Wang. and Yang Shen. L2-gen: Layer-wise and learned efficient training of graph convolutional networks. In 2020 IEEE/CVF Conference on Computer Vision and Puttern Recognition (CVPR), pp. 2124-2132, 2020.
[94] Yuning You, Tianlong Chen, Zhangyang Wang, and Yang Shen. Bringing your own view: Graph contrastive learning without prefabricated data augmentations. In Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining, WSDM '22 pp- 1300-1309 New York, NY, USA, 2022. Association for Computing Machinery.
[95] Lingxiao Zhao and Leman Akoglu. Paimorm: Tackling oversmoothing in gnns. In Interna- tional Conference on Learning Representations, 2020.
[96] Wenqing Zheng, Edward W Huang. Nikhil Rao, Sumeet Katariya, Zhangyang Wang, and Karthik Subbian. Cold brew: Distilling graph node representations with incomplete miss- ing neighborhoods. In International Conference on Learning Representations, 2022.
[97] Kaixiong Zhou, Xiao Huang, Yuening Li, Daochen Zha, Rui Chen, and Xia Hu. Towards deeper graph neural networks with differentiable group normalization. In Advances in neural information processing systems, 2020.
[98] Kaixiong Zhou, Xiao Huang, Daochen Zha, Rui Chen, Li Li, Soo-Hyun Choi, and Xia Hu. Dirichlet energy constrained learning for deep graph neural networks. Advances in neural information processing systems, 2021.
[99] Kuangqi Zhou, Yanfei Dong, Kaixin Wang, Wee Sun Lee, Bryan Hooi, Huan Xu, and Ji- ashi Feng. Understanding and resolving performance degradation in deep graph convolu- tional networks. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pp. 2728 2737, 2021.
16

---

[100] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 7793-7804. Curran Associates, Inc., 2020.
[101] Marinka Zitikk and Jure Leskovec. Predicting multicellular function through multi-layer tissue networks. Bioinformatics, 33(14):1190-119) 07 2017.
17

---

Appendix
Table of Contents
A Related Works
18
Methods for Alleviating Over-smoothing
A.2 Homophily Bias in Evaluation Techniques for Deep GNN
A.3 Methods for Alleviating Over-squashing
20
A.4 Towards Unified Treatment
21
Proofs
21
Expected Propagation Matrix under DropEdge variantss
21
B.2 Sensitivity in L-layer Linear GCNs
23
C Theoretical Extensions
24
C.I. Sensitivity in Nonlinear MPNNs
24
Test-time Monte-Carlo Dropout
25
D Empirical Sensitivity Analysis
25
D.1 MC-Approximation of Sensitivity in Nonlinear MPNNs
................................
26
D.2 Symmetrically Normalized Propagation Matrix
26
Upper Bound on Expected Sensitivity
................................
26
D.4 Closer Look DropSens
................................
27
E Experiments Details
27
E.1
Descriptions of the Datasets
27
Training Configurations
................................
29
E.3
DropSens Implementation
................................
30
F
Supplementary Experiments
31
F1
Test Accuracy versus DropEdge Probability
31
F2 Remark on Drop
................................
32
F3
Over-squashing Under-fitting?
................................
32
G Supplementary Experimental Results
33
G.1 Ranking Dropping Methods
33
G.2 Performance of GAT with Dropping Methods
33
G.3 Effect Size Statistical Tests
33
G.4 Performance of GIN with DropSens
34
G.5 Best-performing Dropping Probabilities.
35
Related Works
A.1 Methods for Alleviating Over-smoothing
popular choice for reducing over-smoothing in GNNs is regularize the model. Recall that DropEdge [70] implicitly regularizes the model by adding noise to it (Section 2.2). A similarly regularization effect is observed with the methods discussed in the main text DropNode [23], DropAgg [43], DropGNN [66], Dropout [79] and DropMessage [21]. Graph Drop Connect (GDC) [37] combines DropEdge and DropMessage together, resulting in a layer-wise sampling scheme that uses different subgraph for message-aggregation over each feature dimension. These meth- ods successfully addressed the over-smoothing problem, enabling the training of deep GNNs, and performed competitively several benchmarking datasets.
18

---

Table 3: Statistics of code-classitication datasets. Homophily measures as defined in [53].
Dataset
Nodes
Edges
Features
Classes
Homophily
Homophilic Networks
Reddit
232,965
114,615,892
602
41
0.653
OGBN-ArXiv 169,343
1,166,243
128
40
0,416
Coauthor-CS 18,33
163,788
6,805
15
0.755
Coauthor-Physies 34,493
495,924
8,415
5
0.847
Wiki-CS 11,701
216,123
300
10
0.568
Amazon-Computers 13,752
491,722
767
10
0.700
Amazon-Photo
7,650
238,162
745
0.772 8
Heterophilic Networks
Flickr
89,250
899,756
500
7
0.070
Cornell
183
298
1,703
5
0.031
Texas
183
325
1,703
5
0.001
Wisconsin
251
515
1,703
5
0.094
Another powerful form of implicit regularization is feature normalization, which has proven crucial in enhancing the performance and stability of several types of neural networks [41]. Exploiting the inductive bias in graph-structured data, normalization techniques like PairNorm [95]. Differen- tiable Group Normalization (DGN) [97] and NodeNorm [99] have been proposed to reduce over- smoothing in GNNs. On the other hand, Energetic Graph Neural Networks (EGNNs) [98] explicitly regularize the optimization by constraining the layer-wise Dirichlet energy predefined range.
In different vein, motivated by the success of residual networks (ResNets) [38] in computer vision, [49] proposed the use of residual connections to prevent the smoothing of representations. Residual connections successfully improved the performance of GCN on a range graph-learning tasks. [13] introduced GCN-II, which uses skip connections from the input all hidden layers. This layer wise propagation rule has allowed for training of ultra-deep networks architectures, like the Jumping Knowledge Network (JKNet) [86] and the Deep Adaptive GNN (DAGNN) [54), aggregate the representations from all layers, (z, (f) 1 ) before processing them through a readout layer.
to 64 layers. Some other
A.2 Homophily Bias in Evaluation of Techniques for Deep GNN
We examine the evaluation protocols commonly used for assessing methods aimed at alleviating over-smoothing in deep GNNs many of which are also widely adopted for training deep archi- tectures. Notably, we highlight a misalignment between the intended goal of these methods to improve the trainability of deep GNNs and their evaluation, which is often restricted to short- range tasks.
For example, DropEdge [70] was evaluated on Cora [58], CiteSeer [31], PubMed [63], and version of Reddit [36] distinct from the one used in our experiments. The first three exhibit high label ho- mophily (see Table 4) and are known to be better modelled by shallower networks [97]. Reddit also displays strong homophily, as can be seen in Table 3. Similarly, DropNode [23] was evaluated on Cora, CiteSeer, and PubMed; DropAgg [43] on Cora ML, CiteSeer, and OGBN-ArXiv [40], which has moderate homophily; DropMessage [70] was evaluated on Cora, SiteSeer, PubMed, OGBN- ArXiv, and Flickr, with only the latter having low homophily; GDC [37] was evaluated Cora, Cora ML and CiteSeer.
A similar trend can be observed in the evaluation of feature normalization techniques used to regular- ize GNNs. PairNorm [95] and DGN [97] were evaluated on Cora, CiteSeer, PubMed, and Coauthor- CS [77]; NodeNorm [99] on Cora, CiteSeer, PubMed, Coauthor-CS, Wiki-CS [59]. and Amazon- Photo [77]; and EGNNs [98] on Cora, PubMed, Sauthor-Physscee [77], and OGBN-ArXiv all of these datasets are highly homophilic.
19

---

A similar trend is observed in the evaluation of architectural modifications designed to enable deeper GNNss GCN-II [13] on Cora, CiteSeer, PubMed, and Chameleon; JKNet [86] on Cora, CiteSeer, and Reddit; and DAGNN [54] on Cora, CiteSeer, PubMed, Coauthor-CS, Coauthor-Physics Amazon- Computers [77], and Amazon- Paazon--Poto--- - many of these datasets are highly homophilic as well.
This pattern indicates that an overwhelming proportion of evaluations have been restricted to short- range, homophilic tasks, Such narrow focus risks overstating the general effectiveness of these methods and masking their potential limitations in long-range scenarios.
A few exceptions stand out. DropGNN [66], which was evaluated on graph-classificttion from the TUDataset [62]. aligning more closely with evaluations of rewiring methods targeting over- squashing [8, 44]. NodeNorm, while primarily evaluated on homophilic datasets, was also tested on three heterophilic graphs: Cornell, Texas, and Wisconsin [68]. GCN-II saw broader evalua- tion, including on several long-range tasks such Chameleon, Cornell, Texas, Wisconsin, and the Protein-Protein Interaction (PPI) networks [36]. Lastly, JKNet was also evaluated on the PPI net- works.
A.3 Methods for Alleviating Over-squashing
In this section, we will review some of the graph rewiring methods proposed to address the problem of over-squashing. Particularly, we wish emphasize a commonality among these methods edge addition is necessary. As reminder, graph rewiring refers to modifying the edge set of graph by adding and/or removing edges in systematic manner. In a special case, which includes many of the rewiring techniques we will discuss, the original topology is completely discarded, and only the rewired graph is used for message- paasage-passing.
Spatial rewiring methods use the topological relationships between the nodes in order to come up with a rewiring strategy. That is the graph rewiring is guided by the objective of optimizing some chosen topological properties. For instance, [4] introduced fully-adjacent (FA) layer, wherein mes- sages are passed between all nodes. GNNs using a FA layer in the final message-pand paaagggg step were shown to outperform the baselines on variety of long-range tasks, revealing the importance of in- formation exchange between far-offf nodes which standard message-passing cannot facilitate. [81] proposed a curvature- rewiring strategy, called the Stochastic Discrete Ricci Flow (SDRF), which aims to reduce the "bottleneckedness" of a graph by adding suitable edges, while simulta- neously removing edges in an effort to preserve the statistical properties of the original topology. [8] proposed the Greedy Total Resistance (GTR) technique, which optimizes the graph's 's total re- sistance by greedily adding edges to achieve the greatest improvement. One concern with graph rewiring methods is that unmoderated densification of the graph, e.g. using a fully connected graph for propagating messages, can result in loss of the inductive bias the topology provides, potentially leading to over-fitting, Accordingly, [35] propose a Dynamically Rewired (DRew) message--passing framework that gradually densifies the graph. Specifically, in given layer L, node aggregates mes- sages from its entire (-hop receptive field instead of just the immediate neighbors. This results in an improved communication over long distances while also retaining the inductive bias of the shortest distance between nodes.
Spectral methods, on the other hand, use the spectral properties of the matrices encoding the graph topology, e.g. the adjacency or the Laplacian matrix, to design rewiring algorithms. For example, [5] proposed a differentiable graph rewiring layer based on the Lovász bound [56, Corollary 3.3]. Similarly, [6] introduced the Random Local Edge Flip (RLEF) algorithm, which draws inspiration from the "Flip Markov Chain" [22, 57] sequence of such steps can convert connected graph into an expander graph a sparse graph with good connectivity (in terms of Cheeger's ''s constant) - with high probability [1, 15, 22, 30, 57], thereby enabling effective information propagation across the graph.
Some other rewiring techniques don't 't exactly classify as spatial or spectral methods. For instance, Probabilistically Rewired MPNN (PR-MPNN) [69] learns to probabilistically rewire graph, effec- tively mitigating under-reaching as well as over-squashing. Finally, [25] proposed connecting all nodes at most r-hops away, for some r E N, and introducing positional embeddings to allow for distance-aware aggregation of messages.
20

---

A.4 Towards a Unified Treatment
Several studies have shown that an inevitable trade-off exists between the problems of over- smoothing and over-squashing, meaning that optimizing for one will compromise the other. For instance, [64, 81] showed that negatively curved edges create bottlenecks in the graph resulting in over-squashing of information. On the other hand, [64, Proposition 4.3] showed that positively curved edges in a graph contribute towards the over-smoothing problem. To address this trade- off, they proposed Batch Ollivier-Ricci Flow (BORF), which adds new edges adjacent the neg- atively curved ones, and simultaneously removes positively curved ones. In similar vein, [34] demonstrated that the minimum number of message-passinn steps required to reach given level of over-smoothing is inversely related to the Cheeger's constant, hg. This again implies an inverse relationship between over-smoothing and over-squashing. To effectively alleviate the two issues together, they proposed the Stochastic Jost and Liu Curvature Rewiring (SJLR) algorithm, which adds edges that result in high improvement in the curvature of existing edges, while simultaneously removing those that have low curvature.
Despite the well-established trade-off between over-smoothing and over-squashing, some works have successfully tackled them together despite only adding or removing edges. One such work is [44], which proposed rewiring algorithm that adds edges to the graph but does not remove any. The First-order Spectral Rewiring (FoSR) algorithm computes, as the name suggests, first-order approximation to the spectral gap of the symmetric Laplacian matrix (L IN 1/3), and adds edges with the aim of maximizing it. Since the spectral gap directly relates to Cheeger's constant a measure of bottleneck-enness in the graph through Cheeger's inequality [2, 3, 78), this directly decreases the over-squashing levels. Moreover, [44, Figure 5] empirically demonstrated that addition of (up to a small number of) edges selected by FoSR can lower the Dirichlet energy of the representations, suggesting the method's potential simultane- ously tackle over-smoothing. Taking somewhat opposite approach, [55] adapted DropEdge to remove negatively curved edges sampled from a distribution proportional to edge curvatures. Their method, called CuryDrop, directly reduces over-squashin and, as side benefit of operating on sparser subgraph, also mitigates smoothng.
B Proofs
B.1 Expected Propagation Matrix under DropEdge-variants
Lemma. When using DropEdge, the expected propagation matrix is given as:
dr+t1
EDE (1)
(1 4) (d, +1)
[
1
EDE
1
(1 11-9) 9) (d, +
where (i E; P. otherwise.
Proof. Recall that under DropEdge, self-loop is added the graph after the edges are dropped, and then the normalization is performed. In other words, the self-loop is never dropped. Therefore, given the i.i.d. masks, mi...., Md: Bern (1 q), on incoming edges to node the total number of messages is given by
1
my = 1 1 M;
(B.1)
Am
21

---

where M2 ~ Binom (d,. 1 - q). Under asymmetric normalization (see Section 2.1), the expected
weight of the message along the self-loop is computed as follows:
EDE
Em wd
(B.2)
de
k=
mk
1
EM:
(B.3)
+ Mj
di
di
(1 1)t (1) ==)
(B.4)
k
1 k
k=n
d; + 1
(1 -1-6h 9) g)(+t1 (g) d
(B.5)
(1 ①) (de + 1)
k +
k=U
d,+1
d + 1)
k ) (1 - 9) * (q) d
(B.6)
(1 - 9) (d: + 1)
1- gdi+1
(B.7)
2) 1)
Similarly, if the Bernoulli mask corresponding to j + i is 1, then the total number of incoming messages node is given by
2 + m&
including one self-loop, which is never dropped, as noted earlier. On the other hand, the weight of the edge is simply 0 if the corresponding Bernoulli mask is O. Using the Law of Total Expectation, the expected weight of the edge j - i can be computed as follows:
EDE |
++ (1 - 4) E Emy...
1
(B.8)
2 X4 mR
d.-1
d3 1 ) (1 9)* (g) dh- 1
(1- 9)
(B.9)
k
2
k=
4:
(d: 1)!
(ke + 2)! (d: - 1 - k:)! (1 - 4) k+1 (4) dy) (k: + 1)
(B.10)
(d=-1) (1 - 9)th k-1 (q)d.-1- (k: - 1)
(B.11)
(k) +1 k)!
1
d++1
dc +1 ) (1 - 9)* (4) di (k= fe-11 1)
(B.12)
d. (d. + +1) (1-10 9)
k
2=2
[(d + 1) (1 9) 1 + c
(B.13)
d, (d: ()(1))1 g)
d, (1 EDE (
(B.14)
Analysis of DropEdgg-variants. We will similarly derive the expected propagation matrix for other random edge-dropping algorithms. First off, DropNode [23] samples nodes and drops corresponding columns from the aggregation matrix directly. followed by rescaling of its entries:
EDN
1 9
A
x (1 9) À = À
(B.
1-q
22

---

That is, the expected propagation matrix is the same as in a NoDrop model (g 0).
Nodes sampled by DropAgg [43] don't aggregate messages. Therefore, if Á A then the expected propagation matrix is given by
A + 1- 1 daq
BDA
EDE
A
di + d3 +
(B.16)
EDA
Aij]
(1 EDA
[
EDE
Ay)
Finally, DropGNN [66] samples nodes which neither propagate nor aggregate messages. From any node's perspective, if it is not sampled, then its aggregation weights are computed as for DropEdge:
1 - gd++1
EDG
Au
q + (1 q) LEDE
Asi
+
DEDA
Aa
di +
(B.17)
EDG
Aij
1 1 EDG di
Aui
EDA
[Ass
B.2 Sensitivity in L-layer Linear GCNs
Theorem. In an L-layer linear GCN with Á = A using DropEdge, DropAgg or DropGNN decreases the sensitivity of node V another node j E B(L) (i), thereby reducing its effective receptive field.
L II E... [Auene
E... (AL) is
Σ
] END (
(B.18)
(MO..... P {=1
where ND refers to a NoDrop model (q = =0), the placeholder can be replaced with one of the edge-dropping methods DE, DA or DG, and the corresponding entries of [A. can be plugged in from Equation 3.3, Equation 8.16 and Equation B.17, respectively. Moreover, the sensifivity monotonically decreases as the dropping probability is increased.
Proof. Recall that can be viewed as the transition matrix non-uniform random walk, such that Pue = (u + v). Intuitively, since there is no self-loop on any given L-length path connecting nodes and] (which are assumed to be L-hops away), the probability of each transition any path connecting these nodes is reduced. Therefore, so is the total probability of transitioning from i to in exactly L hops.
More formally, denote the set of paths connecting the two nodes by
Paths (j + i) {wu,, ... uy): uo jiuz (ue-1 - uz) E [4]
(B.19)
The (i, (entryy in the propagation matrix is given by
(p (Pb))s
Σ
II
P Pucue-
(B.20)
(24 (M Paathss t=1
Since there no self-loop on any of these paths,
pr.
Σ
II
dur (1- (1 q) (due + 11)
1
(B.21)
(uo Pathssf +8) Emm
L
Σ
II
(B.22)
due +
(MO.......) -8) +0)
The right hand side of the inequality is the (inj)-yntry in the th power the propagation matrix of NoDrop model. From Equation 1. and Equation 1.17, know that Equation B.22 is true for
23

---

DropAgg and DropGNN as well. We conclude the first part of the proof using Equation 3.2 the sensitivity of node to node j is propertional to (P)):-- Next, recall the geometric series for any q:
1+ ... + 9" 1 1-9 gatl
(B.23)
Each of the terms on the right are increasing in q. hence, all the P Parue-1 factors are decreasing in q. Similarly, EDA[A,) and Epc[A.y] decrease with increasing q. Using these results with Equa- tion B.20, we conclude the second part of the theorem.
C Theoretical Extensions
C.1 Sensitivity in Nonlinear MPNNs
While linear networks useful in simplifying the thcoretical analysis, they often not practical. In this subsection, we will consider the upper bounds on sensitivity established previous works, and extend them to the DropEdge setting.
ReLU GCNs. [86] considered the case of ReLU nonlinearity, so that the update rule is Z ReLU(AZ) (((), Additionally, it makes the simplifying assumption that each path in the computational graph active with fixed probability, e [45, Assumption Alp-m]. Accordingly, the sensitivity (in expectation) between any two nodes is given as
021-0 (2(1)) (L)
i 8=1
w
w (A4)
[
= =c1 (At),.
ERRLU
P
(C.1)
where (12) depends only on the depth L, and is independent of the choice of nodes i, V. Taking an expectation w.r.t. the random edge masks, we get
O214) (2)
|1 = clah)
1
II A ( )) =
MMM......MUU
ERELU
-
E
-c10
E
A
(C.2)
dxz
Using Theorem 3.1, conclude that in ReLU-GCN, DropEdge, DropAgg and DropGNN will reduce the expected sensitivity between nodes L-hops away. Empirical observations Figures la and 4 suggest that we may expect an increase in sensitivity neighboring nodes, but significant decrease in sensitivity to those farther away.
Source-only Message Functions. [8, Lemma 3.2] considers MPNNs with aggregation functions of the form
Agg (2(t-)) {2/ (t-1) :j e (ESss) (1)))
Σ
A Msg (4)
(z (2))
(C.3)
(E
and Upd and Msg functions with bounded gradients. In this case, the sensitivity between two nodes i,j can be bounded as
0z
(L)
L
(L)
A'
(C.4)
t=0
As before, we can use the independence of edge masks to get an upper bound on the expected sensitivity:
E M M(L)
0z(44)
C
(D)
E IN
II A
Σ
1)
c
Σ E A 4 (C.5)
dæ,
t=
24

---

Figure 5 shows the plot of the entries of Ei=o P (i.e. for DropEdge), as in the upper bound above, with Á Á We observe that the sensitivity between nearby nodes marginally increases, while that between distant nodes notably decreases (similar to Figure la), suggesting significant over- squashing. Similar observations can be made with A = Asym, and for other DropEdge-variamt
Source-and- -arrae- Message Functions. [81, Lemma 1] showed that if the aggregation function is instead given by
Agg 22 1
{ (6-1) :j E 8 E (0)) (j
Σ
Msg (8) (z! (x((-1) 22 1111)
(C.6)
(EB
then the sensitivity between nodes i and j E ((L) (i) can be bounded as
0z1-! (L)
S (1) (A*).
(C.7)
dx,
With random edge-dropping, this bound can be adapted as follows:
0z! (4) dæ,
L
E M MIL)
CB (1)
A
(C.8)
i5
which is similar to Equation C.2, only with different proportionality constant, that is anywa independent of the choice of nodes. Here, again, we invoke Theorem 3.1 to conclude that (B[A) (8(A)),, ") decreases monotonically with increasing DropEdge probability q. This implies that, in non-linear MPNN with Á A asym DropEdge lowers the sensitivity bound given above. Empirical results in Figure support the same conclusion for Á sm
C.2 Test-time Monte-Carlo Dropout
Up until now, we have focused on the expected sensitivity of the stochastic representations in models using DropEdge-varianss. This corresponds to their training-time behavior, wherein the activations are random. At test-time, the standard practice is to turn these methods off by setting = O. However, this raises the over-smoothing levels back up [88]. Another way of making predictions is to perform multiple stochastic forward passes, as during training, and then averaging the model outputs. This is similar to Monte-Carlo Dropout, which is an efficient way of ensemble averaging in MLPs [27], CNNs [26] and RNNs [28]. In addition to alleviating over-smoothing, this approach also outperforms the standard implementation in practical settings [88]. We can study the effect of random edge-dropping in this setting by examining the sensitivity of the expected representations:
022'0
E
=
E
dz,
(C.9)
In linear models, the order of the two operations -expectation and 1-norm - is irrelevant:
Oz (L)
02(44
= E A4
W
= E
AA
[il = E
(C.10)
0æ.
0z,
In general, the two quantities can be related using the convexity of norms and Jensen's 's inequality:
dz (T)
E Da.
<
E
s...
(C.I1)
Oz,
Therefore, the upper bound results in Appendix C.I 1 trivially extend to the MC-averaged representa- tions. Although tighter bounds may be derived for this setting, we leave that for future works.
D Empirical Sensitivity Analysis
In this section, we elaborate on the setup used for the empirical sensitivity analysis in Section 3. We also present some supplemental figures demonstrating the negative effects random edge-dropping. particularly focusing scenarios not covered by the theory.
25

---

(e (sljoomij 0
- 0.0
dg6,))
0.4 9
d.lk,) =
dali,) -4
doll.
Shartest Distance, da6.)
DropEdge Probability,
Figure 4: Entries of pe, averaged after binning node-pain sade-pairs by their shortest distance.
9- 0.2
0,16,p -0
dell,)) =2
d.ll.))
0.8
deli.)) 6
Shortest Distance, deli.)
DropEdge Probabilit. 9
Figure Entries 2 p averaged after binning node-pairs by their shortest distance.
D.1 MC-Approximation of Sensitivity in Nonlinear MPNNS
Given a target node from the Cora dataset [58], we computed the sensitivity of its representation to source nodes up L 6 hops away in ReLU-GCNs of width 32. The sensitivities ized to obtain influence scores [86]. This was repeated for 25 target nodes, and 25 model droopout samples were used for each of them. The source nodes were binned by the shortest distance from the corresponding target node, and the influence scores were averaged over each bin to obtain an average influence from nodes E-hops away.
normal-
D.2 Symmetrically Normalized Propagation Matrix
The results in Section 3 correspond the use of Å À asym for aggregating messages in each message passing step, only the in-degree of node i is used to compute the aggregation weights of the incoming messages. In practice, however, propagation matrix, À Ásym, which ensures that nodes with high out-degree do not dominate the information flow in the graph [47]. As in Equation 3.2, we looking for
more common use the symmetrically normalized
L
pL = =4=E0) MCO
II
( E=1
(D.1)
where P := EDE [Amm) While P analytically intractable, we can approximate it using Monte- Carlo sampling, Accordingly, use the Cora dataset, and sample 20 DropEdge masks compute approximation of P. and plot the entries of PL, did for PL in Figure la. The results are presented in Figure 4, which shows that while the sensitivity between nodes up to 3 hops away increased, that between nodes farther off significantly reduced, same in Figure la.
D.3 Upper Bound on Expected Sensitivity
[8] showed that the sensitivity between any two nodes in graph can be bounded using the sum of the powers of the propagation matrix. Appendix C.I, we extended this bound to random edge- dropping methods with independent edge masks sampled in each layer:
26

---

Influence Drop5ens/NoD1op
2.79
squirrel TwitchDE
CiteSeer
Influence, DropSens/DropEdd
PubMed
Actor
Chameleon
1:3
1.4
1.00
2.75
2.9
0.90
Shortest Distances
Shortest Distances
Figure 6: Average sensitivity under DropSens, normalized by average sensitivity under NoDrop (left) and DropEdge (right). We note that DropSens more sensitive to nearhy nodes (d S 2) than NoDrop, and more sensitive far off nodes (d 2 3) than DropEdge.
02(") dx,
E M ((4)
S (1)
Σ A
Although this bound does not have closed form, can again use the Cora network to study its entries. We plot the entries of Ei= P', corresponding to DropEdge, against the shortest distance between node-pairs. The results are presented in Figure 5. We observe an exponential decrease in the sensitivity bound the distance between nodes increases, suggesting that DropEdge is not suitable for capturing LRIs.
D.4 Closer Look DropSens
Lastly, we evaluate DropSens node-classification tasks, comparing its effects with NoDrop and DropEdge. In Figure 6, we compare sensitivity profiles of these methods. It is clear to observe that DropSens allows node representations to be more sensitive to distant nodes' (d 2 3) features, than DropEdge, thereby improving performance on heterophilic datasets. What is interesting is that for homophilic datasets, DropSens is more sensitive to nearby nodes (d 2 1) than DropEdge, allowing the model to effectively capture short-range interactions. Although is poorer at capturing short-range interactions for heterophilic datasets, DropSens improves NoDrop that front, similar to DropEdge
This set of experiments suggests that DropSens strikes perfect balance between NoDrop and DropEdge:
1. improves sensitivity to nearby nodes (d S 2), over NoDrop,
2. improves sensitivity to distant nodes (d 3), over DropEdge, and
3. mitigates over-fitting (by stochastic regularization) and over-smoothing (by reducing message-passing), just as DropEdge.
E Experiments Details
In this section, expand the details of the experiments in Section 5. All experiments on server equipped with an Intel(R) Xeon(R) E5-2620 v3 CPU, 62 GB of RAM, x NVIDIA GeForce GTX TITAN X GPU (12 GB VRAM each), and CUDA version 12.4.
E.1 Descriptions of the Datasets
Synthetic Datasets. The Synthetic7INCC dataset [33], as the name suggests, a synthetic dataset derived from the ZINC chemical dataset [42], with the dataset size constrained to 12K molecular
27

---

Table 4: Statistics of node classiftsstiiiiionnn datasets. Homophily measures from [53].
Dataset
Nodes
Edges
Features
Classes
Homophily
Homophilic Networks
Cora
2,708
10,556
1,433
7
0.766
CiteSeer
3,327
9,104
3,703
6
0.627
PubMed
19,717
88,648
500
0.664
Heterophilic Networks
Chameleon 2,277
36,051
2,325
5
0.062
Squirrel 5,201
216,933
2,089
5
0.025
Actor 7,600
29,926
931
5
0.01
TwitchDE
9,498
306,276
128
2
0.142
Table 5: Statistics of graph datasets.
Dataset
Graphs
Nodes
Edge
Features
Classes
Mutag
188
17.9
39.6
7
2
Proteins
1,113
39.1
145.6
3
2
Enzymes
600
32.6
124.3
3
6
Collab 5,000
74.5
4914.4
0
3
IMDb
1,000
19.8
193.1
0
2
Reddit
2,000
429.6
995.5
0
2
graphs [20]. Specifically,, given a molecular graph G. we set all its nodes' features to O, except for two nodes, and j # whose features are sampled as Tt L (0, 1). The graph-level target is computed as
tanh (z, + zz), i.c. learning the task requires a non-linear mixing between the features of nodes and j. These nodes are chosen to induce the desired level of underlying mixing- given E [0, 1]. the node-pair (i. j) is chosen such that the commute time [10] between them is the th quantile of the distribution of commute times over G. We analyze the effect of underlying mixing on model performance by varying a as 0.1, 0.2, 1.0. The MPNN is chosen to be an L-layer GCN with MAX-pooling readout, which encourages the model to learn the mixing by effectively passing messages [33, Theorem 3.2]. The model depth is set at L maxg [diam (G) /2] = 11 to ensure that the GCN does not suffer from under-reaching [4, 7].
code-classifiiation Tasks. Cora [58], CiteSeer [31] and PubMed [63] are citation networks - their nodes represent scientific publications and an edge between two nodes indicates that one of them has cited the other. The features of each publication are represented by binary vector, where each index indicates whether a specific word from a dictionary present or absent. Several studies have showed that these datasets have high homophily in node labels [53, 100] and that they are modelled much better by shallower networks than by deeper ones [97]. Chameleon and Squirrel [71] are networks of English Wikipedia web pages the respective topics, and the edges between web pages indicate links between them. The task to predict the average-monthly traffic on each of the web pages. The Actor dataset is induced from larger iln-director-actoo--iieee network [68]. It a network of film actors, with edges between those that occur on the same Wikipedia page, and node features are binary vectors denoting the presence of specific keywords in the corresponding Wikipedia entries. The task is to classify actors into five categories based on the content of their Wikipedia pages. Finally, TwitchDE [71] is a network of Twitch users in Germany, with the edges between them representing their mutual follower relationships. The node features are embeddings of the games played by the users, and the task is predict whether the users use explicit language.
Graph-classffication Tasks. Following [8, 44], we use the graph-classificttion datasets introduced in [62], which were hypothesized to be long-range tasks. On one hand we have the molecular datasets Mutag, Proteins and Enzymes, and on another we have the social networks Reddit- Reddit-Binary, IMDb Hibb-Binary and Collab. Their statistics are presented in Table 5.
28

---

Mutag [17] consists of nitroaromatic compounds, with the objective of predicting their mutagenicity, i.c the ability to cause genetic mutations, in cells in Salmonella typhimurium. Each compound is represented as graph, where nodes correspond to atoms, represented by their type using one-hot encoding, and edges denote the bonds between them. Proteins [9, 19] is collection of proteins classified as enzymes or not. The molecules are represented as graph of amino acids, with edges between those separated up to 6Å apart. The Enzymes [9, 75J dataset is represented similarly, and the task is to classify the proteins into one of 6 Enzyme Commission (EC) numbers system to classify enzymes based on the reactions they catalyze.
Collab [89] is a scientific collaboration dataset where each graph represents a researcher's ego net- work. Nodes correspond to researchers and their collaborators, with edges indicating co-authorship. Each network is labeled based on the researcher's 's field, which can be High Energy Physics, Con- densed Matter Physics, or Astrophysics. IMDb-Binary [89] is a movie collaboration dataset con- taining the ego-networks of 1,000 actors and actresses from IMDB. In each graph, nodes represent actors, with edges connecting those who have co-starred in the same film. Each graph is derived from either the Action genre or Romance. Finally, Reddit-Binary [89] comprises graphs represent- ing online discussions on Reddit, where nodes correspond to users and edges indicate interactions through comment responses. Each graph is labeled based on whether it originates from a Q&A or discussion- based subreddit.
For the molecular datasets, we use the node features supplied by PyG [24], but since they are un- available for the social networks, we set scalar features x; (1) for all nodes in these datasets, following [44].
E.2 Training Configurations
Dataset Splits. For the SyntheticZINC task, use the train-val-test splits provided in PyG. For the homophilic (citation) networks, we use the 'full' split [12), as provided in PyG, and for the heterophilic networks, we randomly sample 60% of the nodes for training, 16% for validation, and 24% for testing. On the other hand, for the graph classification tasks, we sample 80% of the graphs for training. and 10% each for validation and testing. following [8. 44].
Model Architecture. We standardize most of the hyperparameters across all experiments to isolate the effect of random dropping. Specifically, we use symmetric normalization of the adjacency ma- trix to compute the edge weights for GCN, and we set the number of attentions heads for GAT to in order to keep the computational load manageable, while at the same time harnessing the expres- siveness of the multi-headed self-attention mechanism. For the SyntheticZINC dataset, we fix the size of the hidden representations at 16, while we fix them 64 for all the real-world datasets. In all settings, a linear transformation is applied to the node features before message-passing passeeppssing...... Afterwards, bias term is added and then the ReI.U nonlinearity is applied. Finally, linear readout layer is used to compute the regressand (for regression tasks) or logits (for classification).
Dropping Probability. For the synthetic datasets, we experiment with NoDrop baseline, and DropEdge, Dropout and DropMessage, each with q = 0.2 and g = O.5. For the real-world datasets, the dropping probabilities are varied as q = 0.1, 0.2, ... 0.9, so to reliably find the best perform- ing configuration. We adopt the common practice of turning the dropping methods off at test-time (q 0), isolating the effects on optimization and generalization, which our theory does not address.
DropSens Configurations. For DropSens, we use 4 possible values for proportion of infor- mation preserved over corss-edges, = 0.5, 0.8, 0.9, 0.95. Since the dropping probability, gi increases with the in-degree of the target node, d, the proportion of all edges dropped could become very high, especially with small c. Therefore, we clip the value of q by 4 pos- sible choices, q. < 9max E {0.2, 0.3, 0.5, We exclude the following configurations: (c, Imax) E (0.55 0.2), (0.5, 0.3). (0.5, 0.5), (0.8, 0.2)). since they use the same dropping proba- bility (= )max) for each edge, and are therefore equivalent to DropEdge. In summary, we test with total of 12 configurations for DropSens to find the best one for each task.
Optimization Algorithm. The models are trained using the Adam optimizer [46]. On the Syn- theticZINC dataset, the models are trained with a learning rate of 2 x 10-3 and a weight decay of 1 x 10-4, for a total of 200 epochs. On the real-world datasets, we use a learning rate of 1 x 10-3 and no weight decay, following [8, 44]. Here, we cap the maximum number of epochs at 300. In
29

---

both cases, the learning rate is reduced by factor of X 10 if the validation loss fails to improve beyond relative threshold x 10 for 10 epochs, again following [8, 44].
Number of Independent Runs. We perform only 10 independent runs on the SyntheticZINCC dataset due its consistently low variance in performance, also observed by [33]. For real-world datasets, we conduct 20 runs to identify the best- best-performing dropping configurations. We then per- form one-sided I-test to assess whether dropout improves performance, using 90% confidence- level (a = 0.1) and targeting a statistical power of 0,9 (3 0.1). Under the assumption that the dropping method offers superior performance, detecting medium effect size of 0.5 [14] requires approximately 53 samples per group according to standard power analysis. We round this to 50, and accordingly perform 30 additional runs for the final comparison of the best best-performing dropping configuration with the NoDrop baseline.
E.3 DropSens Implementation
import warnings
import syпpy
fron sympy.abs import
import torch
fron torch.geonetric. utils inport degree, contains_ self loops
def drop_sens((
edge_index: Tensor,
float, nax_drop.prob: float None
nax dropppoo_po max_drop_prob.
# Assuming edge index does not have self loops contains_eelf_loop indge_inee);;
varnings.. warn ('Degree computation DropSens
absence'
of self self-1oops, but the index passed contains sone some.")
degrees degree (edg)..iedexx(())...
Mode indez in-degree
tarch (degraas) tolist()
array
napper torch. torch. ones (da [-1]+1) mapper [de] max_drop_prob
Node ie-reg dropping prob
for d_1 in da:
q_i #loat (syаpy Meyyapy.reall.aeeeeea real__roos (1-c)=d_i+(1-g
q=*(d_ [-2] # Folloxing Equation 4.1
4.1 else if dax_drop_prob: Because q nenontonic ert d, and de is sorted break
napper[d_1] = 9_1
in_dagreas = degrees [adge_index [1]]
Edge index -> in-dagrae of target node Edge index dropping probability
qa napper [in__egrees edge_nark <- adgo_ index edge_index(: edgo_nask]
(edge_ index size (1))
return edge index, edge_mast
Listing DropSens Implementation
In Listing present the DropSens implementation used in our experiments, relying mainly on SymPy [60].
Unfortunately, computing the roots of Equation 4.1 becomes slow when the in-degree d; is large a common scenario in large networks. This issue especially pronounced when the proportion of information preserved large, as the dropping threshold is only met higher value of d, To address this computational challenge, we propose an approximation:
0:
q.
d++1
c1 1 1+ c) d
qi
(E.1)
d
q:)
d,
4i
This approximation becomes increasingly accurate as increases since more information needs to be preserved, needs to be small, and hence, 9;
d.+1 - O.
30

---

Esacl Approximation
Edge Dropping Probvabilloyy
compattiinn time (C)
0.0
1e:6
1.4
0.83 Approximation
100
45
60
40
160
Mode in-degrea,
Aoda in-dagree,
(a) Edge-wiss wise dropping probabilities
(b) Compute time, averaged over 0.1
0.9
Figure 7: Edge-wise dropping probabilities under DropSens for varying values of c, along with the approxi- mation Equation E.1. Compute times measured using only execution thread.
DropSens in
DropSens Sampling
Computation Time
DropEdge Sampling
22
Cora
CitSeer
PubMed
Chameleon
Squirnl
TwitchDE
Actor
Mutag
Proteins
Enzymas
Reddit
IMDb
Collab
Figure 8: Initialization and sampling time of DropSens (c 0.8, 9max
0.5) compared to sampling time of
DropEdge, averaged over runs. graph classification tasks, edge masks are computed one go (instead of one mini-batch at time, in practice).
Figure 7a shows the DropSens probabilities for masking incoming messages based on the in-degree of the target nodes, along with the corresponding approximations. clear to see that the approx- imation gets increasingly more accurate for higher proportions of information preserved. Figure 7b shows that approximation several orders of magnitude cheaper than the exact computation, and also does not scale with the in-degree d,, expected."
Figure shows the initialization time of DropSens, and compares the sampling times DropSens and DropEdge. It is clear to see that DropSens sampling is more expensive than DropEdge, primarily because the edge-wise dropping probabilities need to be computed for new graphs," before sampling edge masks. Moreover, in our experiments, sampling consumed very small fraction of the total training time.
Supplementary Experiments
F1 Test Accuracy versus DropEdge Probability
In Section 3, we studied the effect of edge-dropping probability on sensitivity between nodes at different distances. However, this analysis may be insufficient to precisely predict the impact on model performance since DropEdge-varte significantly affect the optimization trajectory as well.
Note that this comparison only valid our SymPy-based implementation, and can significantly different for other implementations.
This step can be sped up for node-level tasks caching edge-wise dropping probabilities.
31

---

Chameleon
Squirrel
TwitchDE
Thet Accuraty
070
1.0
DropEdge Probability.c
DropEdge Propability. biy.
DropEdge Propeb lit.
Figure Dropping probability versus accuracy of DropEdge-GCN The theory the explains the contrasting trends as follows: random edge-dropping pushes models to fit to local information during training, which is suitable for short-range tasks, but harms test-time performance in long-range ones.
Chameleon
Squirrel
TwitchDE
lest Accuraty
4.44
DropNode Procability
DropNode Probability..
DrepNode Probebility. 9
+
L-6
+
Figure 10: Dropping probability versus test accuracy of DropNode- GCNN.
To learn more about the relationship between test-time performance and dropping probability, evaluate DropEdge-Grr GCNss on the heterophilic datasets; the results are shown in Figure 9. Clearly, on Chameleon, Squirrel and TwitchDE, the performance degrades with increasing dropping probability, as was suggested by Theorem 3.1 and Figure la. Surprisingly, the trends are significantly monotonic with GCNs of all depths, 2, 4, 6,8.
F.2 Remark DropNode
In Equation B.15, we noted that DropNode does not suffer from loss in sensitivity. However, those results were in expectation. Moreover, our analysis did not account for the effects on the learning trajectory. In practice, high DropNode probability would make it hard for information in the node features to reach distant nodes. This would prevent the model from learning to effectively combine information from large neighborhoods, harming generalization. In Figure 10, visualize the rela- tionship between test-time performance and DropNode probability. The performance monotonically decreases with increasing dropping probability, was observed with DropEdge.
F.3
Over-squashing or Under-fitting?
The results the previous subsection suggest that using random edge-dropping to regularize model training leads poor test-time performance. We hypothesize that this occurs because the mod- els struggle to propagate information over long distances, causing node representations to overfit local neighborhoods. However, confounding effect is at play: DropEdge variants reduce the generalization gap by preventing overfitting to the training set. If this regularization is too strong, the model could underfit, which could also explain the poor test-time performance on heterophilic datasets. This concern is particularly relevant because the heterophilic networks are much larger than homophilic ones (see Table 4), making them more prone to underfitting. investigate this, we plot the training accuracies of DropEdge- the results. It clear that the models do not underfit as the dropping probability increases. fact, somewhat unexpectedly, the training metrics improve. Together with the results in Figure 9, we con-
the heterophilic datasets; Figure 11 shows
32

---

Chameleon
Squirrel
TwitchDE
Train Accurary
6.70
6220
6.00
DropEdge Probabiiit..
DropEdge Propabiliy.co
DropEdge Prosab rit.ability.c
+
Figure 11: DropEdge probability versus training accuracy GCNs. The training performance improves with suggesting that the models are not underfitting. Instcad, the reason for poor test-time performance (Figure 9) that models are over-fitting short-range signals during training, resulting poor generalization.
clude that DropEdge-like methods are detrimental long-range tasks since they cause overfitting to short-range artifacts in the training data, resulting in poor generalization at test-time.
G Supplementary Experimental Results
G.1 Ranking Dropping Methods
In Table reported the mean improvement in test accuracy (%) of each dropout method the baseline NoDrop model, using the best-performing configuration for each. Table 6 presents the corresponding raw accuracies and ranks the methods accordingly. Notably, DropSens ranks first in 7 7/38 x 18% of datasetx combinations, and places within the top 3 in 21 21/38 z 55% cases, highlighting its consistent efficacy across a broad range of settings."
G.2 Performance of GAT with Dropping Methods
In Table 7, we present the results of experiments in Section 5.2, but with the GAT architecture. For node classification tasks, we see the same dichotomy in Table la, with dropping methods signifi- cantly improving performance on homophilic networks, while being detrimental to performance on heterophilic networks. On graph classification tasks, the dropping methods improve performance in 13/30 x 43% cases, but the improvement, if any, is not statistically significant (24/30 = 80% cases). Note that the GAT architecture was unable to learn the Collab dataset, Lee. the performance in all cases was as good as a random classifier's.
G.3 Effect Size in Statistical Tests
The reliance on p-values as measure of statistical significance has been widely criticized due to its limitations conveying the magnitude of an effect. Although low p-value indicates that an observed difference is unlikely to have occurred under the null hypothesis, it does not provide in- formation about the practical significance small to be meaningful in real-world applications, while non-significant result does not neces- sarily imply the absence of a meaningful effect, particularly when sample sizes are small. These concerns have led to increased emphasis effect size measures, which quantify the magnitude of differences independently of sample size.
the result. A statistically significant effect may be too
One widely used measure of effect size is Cohen's 's d statistic [14], which standardizes the difference between two group means by dividing by the pooled standard deviation:
52
d
(G.I)
8p
(nl
1) 5
(12 1)
8p
(G.2)
ni
+ 122
2
We exclude CollabxGAI due unsuccessful runs.
33

---

Table 6: Accuracy of dropping methods and their rankings.
GNN
Dataset
Nodrop
DropSens
DropEdge
DropNode
DropAge
DropGNN
Dropout
DropMessage
Cora
85.06
85-17
85.27
85.27
86.15
85.43
85.48
85.20
CiteSeer
73.39
73.81
73.90
73.09
73.94
74.11
73.13
73.48
PulMed
83.75
83.76
83.63
83.67
83.32
83.56
84.86
Chameloon
53.45
53.54
50.26
51.41
51.58
Squirrel
39.40
TwitchDE
68.26
67.97
67.06
GCN
Actor
22.54
22.89
22.80
22.08
23:15
22.71
22.25
Mulag
71.70
75.30
70.50
71.70
72.80
74,30
69.00
71.50
Proteins
71.29
73.27
71.77
72.16
71.00
71.77
71.20
71,68
Enzymes
31.39
28.42
28.36
25.31
26.97
28.49
26.91
27,81
Rodli
82.23
80.16
76.95
71.30
64.78
60.29
81.31
78.46
IMDb
48.58
49.34
49.36
48.26
49.12
47.40
49.16
$2.00
Collab
65.27
61.16
61.92
60.76
44.33
66.15
61.97
67.88
Cora
76.12
75.15
70:75
80.10
73.65
75.19
80.89
CiteSeer
61.78
53.54
66.82
PulMed
77.81
79.51
86.10
Chameloon
44,38
84:23
36.47
41.63
34.74
43.42
Squirrel
33,30
31.49
31.50
32.43
28.33
28.18
34.36
35.74
TwitchDE
63,48
65.37
64.20
63.90
02.55
63.42
64.73
65.40
Actar
20.24
20.30
22.56
20.16
23.18
20.74
20.27
20.22
Mutag
79,50
80.90
76.60
71.00
79.70
75.80
80.10
$0.60
Proceins
69.02
68.9
67.87
69.55
60.16
68.36
69.68
70.55
Enzymes
44.80
30.40
35.85
37.24
44.16
33.06
42.76
42,40
Reddit
89.72
90.32
89.29
88.22
88.10
85.57
90.11
$9.59
IMDb
60.96
67.50
60:72
69.16
67.22
70.04
Collab
70.68
72.91
72.48
70.01
73.85
Cura
84.47
80.03
CiteSeer
73:53
73.88
72.73
PulMed
K3.45
63.28
83.05
K3.44
83.54
Chameleon
62,87
60.28
59.81
49.74
48.97
48.02
57.02
60.53
Squirrel
44,94
41.70
41.77
36.63
36.27
35,07
38.55
42,40
TwischDE
67.20
67.03
66.83
64.40
66.13
65.45
06.22
67.08
GAT
Actor
21.74
22:57
22.69
21.67
22.75
22.75
21.91
21.97
Muing
74.30
75.90
71.10
72.60
73.20
68.70
73,50
72.10
Proteins
71.32
72.96
71.64
70.89
72.02
71.86
70.61
71.09
Encymes
28.02
29.70
28.67
25.51
26.79
25.08
26.38
29.11
Rodiit
49.31
47.96
48.87
48.35
IMD6
47.56
49.36
47.56
Collab
where ε and Ø2 are sample means, sf and s² are unbiased sample variance, and n1 and ni are the sizes of the samples. However, Cohen's d assumes that the sample standard deviation is an unbiased estimator of the population standard deviation. In small samples, this assumption does not hold, as the sample standard deviation tends to underestimate the true population variability. To address this bias, Hedges', g statistic [39] introduces a correction factor that adjusts Cohen's 's d statistic for small sample sizes:
3 4(n + 122 - 9 d
g ~0
(G.3)
[14] suggested that an effect size of 0.2 be considered small, 0.5 be considered medium, and 0.8 be considered large. Table we present Hedges' g statistic for the statistical tests in Section 5.2. We can clearly see that for homophilic datasets, there is strong positive effect of using the dropping methods, but for heterophilic datasets and graph classification datasets, there is at most small positive effect of using the dropping methods; rather, in most cases there is negative effect.
G.4 Performance of GIN with DropSens
In Section 5.3, we showed that when modelling long-range graph-classificttion tasks using GCNs, DropSens outperforms state-of-the-art graph-rewiring techniques designed for alleviating over- squashing. However, it does not perform as well with GIN, as can be seen in Table unsur- prising, since DropSens specifically designed to work with GCN's message-passee -passing scheme.
34

---

Tabbe Difference in mean test accuracy (%) between the best performing configuration of each dropout method and the baseline NoDrop model, with GAT as the base model. Cell colors represent p- p-values from t-test evaluating whether dropout improves performance.
(a) Node classification tasks.
Homophilic Networks
Heterophilic Networks
Dropout
Cora
CiteSeer
PubMed
Chameleon
Squirrel
TwitchDE
DropEdge
+0.884
+0.668
0.075
33.59
33.64
-0.363
DropNode
-0.476
-0.426
-0.358
-13.128
-8.303
-2.01
DropAgg
+0.303
+0.368
-0.340
-13.897
-8.669
-1.071
DropGNN
+0.543
+1.012
-0.313
-14.850
-9.869
-1.744
Dropout
+1.061
-0.140
+0.081
-5.851
-6.390
-0.981
DropMessage
+0.887
-0.425
+-0.83
-2.344
-2.534
-0.114
(b) Graph classification tasks.
Molecular Networks
Social Networks
Dropout
Mutag
Proteins
Enzymes
Reddit
IMDb
Collab
DropEdge
33.200
+0.321
+00.466
-0.750
-0.520
+0.000
DropNode
11700
-0.429
2.914
+1.440
+1.280
+0.000
DropAgg
-1.100
+0.696
-.632
+0.160
+0,280
+0,000
DropGNN
-5.600
+0.536
-3.40
-0.360
-0.520
+0.000
Dropout
-0.800
-0.714
-2.447
+1.520
++.420
+0.000
DropMessage
-2.200
-0.232
+-0.877
+1.190
+22120
+0.000
This highlights the main limitation of DropSens, necessitating architecture-specific alteration to the edge-dropping strategy, which is not practical in general.
G.5 Best-performing Dropping Probabilities
For the real-world datasets in Section 5.2, we report the best performing dropping probability for different dataset-model-- mmodel-dropout combinations in Table 10.
35

---

Table Hedges' g statistic different bataset-modes mnodel-dropoutt combinations. Color-coding for effect size according to [14]; red denotes negative effect, and green denotes positive effect. Medium to large positive effect sizes in bold.
No effect
Small effect
Medium effect
Large effect
DropSens
DropEdge
DropNode
DropAge
DropGNN
Dropout
DropMessage
Cora
0.355
0.486
0.528
0:204
0.736
0.96
0.308
CheSeerr
0.653
0.621
-0.11
0.679
0.906
-0.29
0.121
PubMed
0.031
-0.298
0.194
-1.822
-0.601
2.337
1. 1.586
Chameloon
-1.97
-4.622
-1.655
-1.352
Squirrel
-0.066
-0.222
-0.894
-8.94
-0.984
-0.952
-0.339
TwitchDi
0.324
0.045
1,275
3.844
0.944
0.568
0.3
GCN
Actor
0.499
0.301
0.143
0.507
0.693
0.202
0.322
Mutag
0.524
-0.126
0.121
0,292
-0.281
-0,022
Fnzymes
-0.77
-0.482
Reddit
0.352
0.946
-1828
22443
2.377
0.131
0.588
IMDb
0.277
0.147
-0.081
0.121
-0.305
0.147
0.603
Collab
-0.314
-0.742
-1.158
-3.612
0.191
-0.775
0.658
-2983
-1.474
-0.525
3.556
8.296
PubMed
0.486
1.358
1.031
1.185
1.447
1.961
1.71
Chameloon
22912
-1.794
-0.654
-1.635
-2.31
-0.246
0 9092
Squirrel
-0.837
-0.499
-0.318
-18823
-1.988
0.391
0.92
TwitchDE
1.056
0.35
0.17
0.426
0.025
0.475
0.775
GIN
0.043
Mutag
0.142
-0.212
-0.717
0.017
-0.317
0.049
0.097
Proteins
-0.196
-0.24
0.121
0.032
-9.136
0.153
0.331
Enzymes
-2.24
1.222
1.008
00086
-1644
-. 203
-..33
Roddit
-0.183
0.641
-0.088
-0.033
-0.527
Collab
1.22
-0.203
0.048
-0.374
-1.44
0.147
0.562
Cora
1.233
0.992
0.829
0.496
0.894
1.842
1.788
CiteSeer
0.521
0.674
-0.331
0.355
1.015
-0.118
-0.319
PubMed
0.163
0.12
0.63
0.629
0.393
0.114
0.247
Squirrel
-12669
-1076
-2.961
-3.363
-3.722
-2.28
-0.799
TwitcDDE
-0.188
-0.354
-1.711
-0.859
-0.793
-0.633
-0.093
GAT
Actor
1.138
1.143
00009
1.202
1.074
0.201
0.265
0.208
-0.333
-01844
-0.116
-0.356
-0.344
-0.198
Enzymes
-0.494
-0.26
-0.391
-0.356
0.109
Reddit
0.234
-0.234
0.468
0.057
-0.123
0.491
0.328
IMDb
0.408
0.124
0.292
0.064
-0.134
0.318
0.474
Collaab
0.0
0.0
0.0
Table Performance GIN with different rewiring methods in graph-classificttion tasks, following [8, 44].
First, second, and third best results are colored.
Rewiring
Mutag
Proteins
Enzymes
Reddit
IMDb
Collab
None
77.70
70.80
33.80
86.79
70.18
72.99
Last FA
83.45
72.30
47.40
90.22
70.91
75.06
Every FA
72.55
70.38
28.38
50.36
49.16
32.89
DIGL
79.70
70.76
35.72
76.04
64.39
54.50
SDRF
78.10
69.81
35.82
86.44
69.72
72.96
FoSR
78.00
75.11
29.20
87.35
71.21
73.28
GTR
77.60
73.13
30.57
86.98
71.28
72.93
DropSens
80.90
68.20
30.40
90.32
67.50
70.68
36

---

Table 10: Best performing dropout configuration Qmax and for DropSens, and y for other dropping methods.
GNN
Dataset
DropSens
DropEdge
DropNode
DropAgg
DropGNN
Dropout
DropMessage
Cora
0.8,
0.9
0.1
0.9
0.9
0.6
0.4
CiteSoer
0.8, 0.9
0.7
0.2
0.8
0.9
0.1
0.1
PubMed
0.3
Chameleon
0.2,
0.1
0.2
0.1
Squirrel
0.3, 0.9
0.1
0.1
0.1
0.1
0.3
0.2
TwitchDE
0.2. 0.95
0.2
0.2
0.1
0.1
0.1
0.2
GCN
0.9
Mutag
0.2,
0.4
0.2
0.1
0.1
Proteins
0.2, 0.96
0.2
0.3
0.5
0.5
0.2
0.3
Enzymes
0.2. 0.95
0.1
0.1
0.1
0.3
Reddät
IMDb
0.5,
0.9
0.2
0.5
0.9
0.4
0.3
Collab
0.5, 0.95
0.2
0.1
0.1
0.1
0.1
0.1
Cora
0.2,
0.1
0.4
0.1
0.8
Citeeeer
PubMed
0.2,
0.1
0.3
0.1
0.1
0.7
Cl Chameleun
0.2, 0.9
0.1
0.1
0.1
0.1
0.2
0.4
Squirrel
0.2
0.1
TwitchDE
0.8,
0.5
0.1
0.1
GIN
Actor
0.8
0.9
0.4
0.9
0.9
0.7
0.2
Mutag
0.8, 0.95
0.1
0.1
0.2
0.1
0.1
0.1
Proteins
0.2,
0.1
Enzymes
0.8, 0.95
0.1
0.1
0.1
Roddit
0.2. 0.95
0.1
0.1
0.1
0.1
0.1
0.3
IMDb
0.2, 0.9
0.1
0.3
0.3
0.1
0.1
0.6
Collab
0.1
Cora
0.8,
0.7
0.2
0.5
0.7
CiteSeer
0.5, 0.95
0.9
0.1
0.9
0.9
0.1
0.1
PubMed
0.2, 0.95
0.1
0.1
0.1
0.6
0.8
Chameleon
Squirrel
0.2, 0.95
0.1
0.1
0.1
0.1
0.1
0.1
TwitcDDE
0.2, 0.96
0.1
0.1
0.1
0.6
0.1
0.1
Actor
0.8.
0.8
0.1
0.8
Mutag
0.7
Proteins
0.5,
0.7
0.1
0.5
0.1
0.4
Enzymes
0.8. 0.95
0.1
0.1
0.1
0.3
0.2
0.2
Reddit
0.8.
0.8
0.6
0.8
0.8
0.3
Collab
0.2, 0.9
0.1
0.1
0.1
0.1
37

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The following quotations are from the abstract.
"While several Dropout-style algorithms, such as DropEdge and DropMessage, have successfully addressed over-smoothing. their impact over-squashing remains largely unexplored." Appendix A.2 discusses the evaluation protocol adopted by sev- eral methods designed for alleviating over-smoothing and training deep GNNs, high- lighting how their focus has been largely limited to homophilic networks, which are commonly short-range tasks [53, 100].
In Section 3, "we present theoretical results showing that DropEdge-varie varriatss reduce sensitivity between distant nodes, limiting their suitability for long-range tasks."
variant of DropEdge that explicitly controls the proportion of information lost due edge-dropping."
In Section 4, "..... we introduce DropSens, a sensitivity-
we
See Sections 5.1 and 5.2 for "our experiments on long-range synthetic and real- world datasets confirm the predicted limitations of existing edge-dropping and feature- dropping methods."
In Section 5.3, we show that "DropSens consistently outperforms graph rewiring tech- niques designed to mitigate over-squashing.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We discuss the limitations of our theoretical results in Section 6, particularly pertaining to the class MPNNs analysed.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate" "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
38

---

The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't It acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We have provided the proofs of the theoretical results for linear GCNs in Appendix B, for nonlinear MPNNs in Appendix C.I, and for test-time MC-averaging in Appendix C.2. To the best of our knowledge, they are correct.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: All necessary details for reproducing the plots in Section are provided in Appendix D. The setup for the experiments in Section 5 are detailed in Appendix E.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
39

---

While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or a way re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case au- thors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, it may be that access to the model limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We have attached ZIP file containing the code, including instructions to reproduce the figures and the tables. We have also included all the necessary details for reproducing experiments in Appendix D and Appendix E. Once the review process is complete, we will include a link to the GitHub repository for this project.
Guidelines:
The answer NA means that paper does not include experiments requiring code. Please see the NeurIPS code and data submission guidelines httts::/nnpss.c//ubbbl
quides/CooeeuubmissinnPP
for more details.
While we encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: hwtpppppbiieiguueeee/eeeeebuueae
for more details. The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer:
[Yes]
Justification:
We provide all relevant information in Appendix E.2.
Guidelines:
The answer NA means that the paper does not include experiments.
40

---

The experimental setting should be presented in the core of the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We provide the statistical significance of the experimental results in Table and Table 5, as well as the corresponding effect sizes in Table We present the results with error bars in Figure 9. The variance in performance consistently low, as also observed by [33], so we avoid clutter by not including error bars in Figure 2.
the SyntheticZINC dataset is
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of eπгоrs is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
show in tables
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer:
[Yes]
Justification:
The details are provided in the introduction of Appendix E.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (c.g.. preliminary failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http:://meaiip.cccpppbleetttttts
41

---

Answer: [Yes]
To the best of our knowledge, there are no ethical concerns regarding our submission.
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work assesses the efficacy of dropout methods performance of GNNs in long-range tasks, and has no direct societal impacts to the best of our knowledge.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our submission does not introduce any high risk algorithms, models, or datasets.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards allow for controlled use of the model, for example by re- quiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
42

---

We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: Our code is original, but relies on the PyTorch framework [67]. and we only use data that publicly available through the PyG API [24], ensuring that the license and terms of use are properly respected.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, paperswitheode. spperswithcode..omdddee com/datasets has cu- rated licenses for some datasets. Their licensing guide help determine the license of a dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. If this information is available online, the authors are encouraged reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and the documenta- tion provided alongside the assets?
Answer: [Yes]
Justification: We have attached ZIP file containing the code, including instructions to reproduce the figures and the tables. We have also included all the necessary details for reproducing our experiments Appendix and Appendix E. Once the review process is complete, we will include a link to the GitHub repository for this project.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/codeemmodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given to participants and screenshots, if applicable, well as details about compensation (if any)?
Answer: [NA]
Justification: Our research does not involve crowdsourcing or research with human sub- jects.
Guidelines:
43

---

The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our research does not involve research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending on the country which research conducted, IRB approval (or equiva-
lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
The project, in its entirety, was carried out without the assistance of any LLM.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMMs as any important, original, or non-standard components.
Please refer to our LLM policy (ttps://mmuuisss.ccoooocceeeesss for what should or should not be described.
44


Reviews:
[{"review_id": "5ynOQT7bT2", "reviewer": "Reviewer_mWNa", "summary": "The paper investigates GNN-specific dropout methods and their effect on two phenomena preventing high depth in message passing GNNs, namely, oversmoothing and oversquashing. While the positive effect of such dropout methods on oversmoothing has been investigated, their effect on oversquashing and long-range interactions is underexplored. The authors use an existing sensitive analysis quantifying the dependence of a node's embedding on the initial features of distant nodes and generalize it to situations where edges are dropped randomly. This theoretical analysis suggests that higher depth under dropout does not necessarily lead to a better ability to capture long-range interaction. Experiments support the theoretical results.", "questions": "**Q1)** Could you clarify my questions regarding the experimental evaluation mentioned in W1?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 4, "originality": 3, "strengths_and_weaknesses": "## Strengths\n\n**S1)** The interplay between dropout, oversmoothing, and oversquashing is highly relevant and gives new insights into the capabilities and predictive performance of GNNs.\n\n**S2)** The paper summarizes the related work well and puts the contribution in the context of state-of-the-art techniques.\n\n**S3)** The paper makes theoretical contributions (albeit under limitations) and shows the relevance of the theoretical results empirically. The limitations are clearly stated and discussed.\n\n## Wekaness\n\n**W1)** The experimental evaluation has several weaknesses and does not provide a consistent picture of the topic:\n * Figure 1(b) is difficult to read since curves overlap. In Section 4, it is claimed that the proposed method, DropSens, improves the sensitivity compared to DropEdge. However, as both lines almost overlap, I cannot follow the interpretation.\n * I do not understand why DropSens is not included in the experiments of Sections 5.1 and 5.2; it would be highly relevant to see how the method compares to other dropout methods in these experiments.\n * Figure 2 shows that NoDrop achieves the best results. Why is this dataset suitable for comparing different dropout methods?\n\n## Minor remarks\n * In Eq. (2), the set should be the argument of the Out function.\n * Eq. (3.2) The index $\\mathbf{M}^{(1)},...$ is not clear.", "was_revised": true, "final_justification": "The authors clarified my question regarding the interpretation of Figure 2 in the rebuttal, and I believe that the promised changes will fix the minor flaws I mentioned in my review. I keep my rating.", "rebuttal": "Thank you very much for the insightful summary, for recognizing the strengths of our work, and for the overall feedback!\n\nBefore we address your concerns, we wanted to bring to your attention that we had accidentally omitted the DropSens configuration \\$(c, q\\_{\\max}) = (0.8, 0.3)\\$ from our original hyperparameter sweep. This has now been included, and the results have been updated accordingly. The overall findings remain unchanged, with the exception that **DropSens now ranks 3rd on the Proteins dataset**.\n\n---\n\nKindly find our responses to the concerns raised:\n\n> Figure 1(b) is difficult to read since curves overlap. In Section 4, it is claimed that the proposed method, DropSens, improves the sensitivity compared to DropEdge. However, as both lines almost overlap, I cannot follow the interpretation.\n\nThank you for pointing this out &ndash; we agree that the overlapping curves in Figure 1(b) make the comparison difficult to interpret. To address this, **we have revised Figure 1(b) by embedding a subplot** that explicitly shows the **ratio of influence at different distances between DropSens and DropEdge**. This makes the differences between the two methods much more visible. Kindly find the entries of the plot below, with the columns denoting shortest distance between nodes:\n\n| $d_G(j,i) =$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 |\n| :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: |\n|  | 0.7312 | 1.0247 | 1.0668 | 1.1233 | 1.0938 | 1.1548 | 1.2283 |\n\nCompared to DropEdge, DropSens decreases sensitivity of a node's final representations to its input features ($d=0$), and increases it to other nodes ($d \\geq 1$). **This effect is especially significant for distant nodes, suggesting that DropSens should be better at modeling LRIs than DropEdge**.\n\nWe hope this modification will make the comparison and the interpretation in Section 4 clearer. \n\n> I do not understand why DropSens is not included in the experiments of Sections 5.1 and 5.2; it would be highly relevant to see how the method compares to other dropout methods in these experiments.\n\nThat makes complete sense! **We have included the results for DropSens, as well as a commentary on the results** in Section 5.3:\n\n|  | Cora | CiteSeer | PubMed | Chameleon | Squirrel | TwitchDE |\n| :-: | :-: | :-: | :-: | :-: | :-: | :-: |\n| GCN | +0.308 | +0.239 | +0.383 | +1.069 | +0.372 | -0.018 |\n| GIN | -0.022 | -0.065 | -0.666 | +0.174 | +0.330 | +0.616 |\n| GAT | +0.577 | +0.663 | -0.003 | -3.859 | -1.583 | -0.090 |\n\n|  | Mutag | Proteins | Enzymes | Reddit | IMDb | Collab |\n| :-: | :-: | :-: | :-: | :-: | :-: | :-: |\n| GCN | +1.700 | +3.161 | +0.716 | -3.670 | +1.340 | -1.818 |\n| GIN | -2.700 | -1.304 | -1.650 | -4.500 | -6.200 | -1.379 |\n| GAT | +4.300 | +1.036 | +0.897 | +0.400 | -0.760 | 0.000 |\n\n\"*We now evaluate whether DropSens offers meaningful improvements over a NoDrop baseline, consistent with our analysis for other dropout methods. Results for GCN and GIN are shown in Table 1a, and those for GAT are in Table 7. The performance boost observed with DropSens is much more remarkable for GCN than for other architectures, which is unsurprising since DropSens was specifically designed to work with GCN's message-passing scheme. We also observe that while it offers significant improvement in 5/6 node classification tasks, its effect on graph classification &ndash; while positive in 4/6 datasets &ndash; is not statistically significant.*\"\n\nJust to clarify our scope: **We do not claim that DropSens undoes all the negative effects of DropEdge**. Rather, we intend to demonstrate that techniques originally designed for mitigating over-smoothing can severely underperform on long-range tasks, but **they can be readily adapted to perform *better* on long-range tasks**.\n\nDoes this address your concerns?\n\n> Figure 2 shows that NoDrop achieves the best results. Why is this dataset suitable for comparing different dropout methods?\n\nThank you for this question. The SyntheticZINC dataset &ndash; introduced in Giovanni et al. (2024, Section 5.1); described further in our Appendix E.1 &ndash; was specifically designed to study how different levels of information mixing in the underlying ground-truth affect model performance. Here's a brief overview of how it is designed:\n\n1. A desired mixing level \\$\\alpha \\in \\[0, 1]\\$ is fixed.\n2. Commute times between all node pairs in a graph are computed.\n3. A node pair is selected whose commute time lies at the \\$\\alpha\\$-th percentile of the graph's commute time distribution.\n\nAs shown in Giovanni et al. (2024, Theorem 4.4), **over-squashing in GNNs &ndash; especially with MAX pooling for graph classification** (as is also our setup) **&ndash; is directly linked to the commute time between nodes.** Therefore, SyntheticZINC is well-suited for comparing dropout methods in this context: **it provides a controlled environment to isolate and measure the over-squashing effects of different algorithms**.\n\nDoes that clarify your concern about the suitability of this dataset?\n\n> In Eq. (2), the set should be the argument of the Out function.\n\nYes, thank you for the correction!\n\n> Eq. (3.2) The index \\$\\mathbf{M}^{(1)}, \\ldots\\$ is not clear.\n\nFair enough, **we have now defined the variables to be the edge masks** in the preceding line. Kindly let us know in case it still remains unclear.\n\n---\n\n**References**:\n\nFrancesco Di Giovanni, T. Konstantin Rusch, Michael Bronstein, Andreea Deac, Marc Lackenby, Siddhartha Mishra, and Petar Velickovic. *How does over-squashing affect the power of GNNs?* Transactions on Machine Learning Research, 2024."}, {"review_id": "zn5ChGvvmw", "reviewer": "Reviewer_SqpF", "summary": "This paper analyses how popular random‐dropping techniques for deep graph neural networks (GNNs) --- DropEdge, DropNode, DropAgg, DropGNN and DropMessage---affect over-squashing, a bottleneck that blocks long-range information flow. By computing the expected Jacobian of linear and nonlinear GCNs under random edge masks, the authors prove that DropEdge-style methods shrink sensitivity between distant nodes at an exponential rate, while marginally increasing sensitivity to immediate neighbours. To mitigate this, they introduce DropSens, which chooses a per-edge drop probability that preserves a user-specified fraction c of message strength, thus keeping long-range sensitivity constant while dropping the same number of edges. Experiments on SyntheticZINC, six node-classification benchmarks (homophilic vs heterophilic) and six graph-classification datasets show: (i) random dropping indeed helps short-range tasks but hurts or fails to help long-range ones; (ii) DropSens consistently outperforms or matches recent graph-rewiring baselines on long-range node tasks and is competitive on graph-level tasks while remaining projection-free.", "questions": "1. Please report GPU wall-clock time and memory for DropSens vs DropEdge and two rewiring baselines on the Squirrel (heterophilic) dataset with a 32-layer GCN until convergence to a fixed validation loss.\n\n2. Provide an ablation on SyntheticZINC varying the preserved-information parameter $c\\in\\{0.7,0.8,0.9,0.95\\}$; show accuracy and number of edges kept.\n \n3. Extreme degree graphs How does DropSens behave on power-law graphs where a few hubs dominate degrees? Include an experiment or theoretical bound on maximum drop probability in that regime.", "limitations": "The authors candidly state that the theory assumes standard message-passing with known parallel transport and that DropSens must be tailored to the propagation rule; extending it to attention or transformer-style layers is non-trivial . They also acknowledge that experiments are small-scale and limited to a few datasets.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. The theoretical contribution is clear and original: the authors give the first explicit sensitivity decay analysis for edge-dropping schemes and extend it to nonlinear MPNNs, filling a gap in the literature on over-squashing. \n\n2. The proposed DropSens is simple, requires no extra model parameters, and is derived directly from the theory, illustrating good “analysis-to-algorithm” design. \n\n3. Empirical evaluation spans synthetic and real datasets, uses three backbone architectures (GCN, GIN, GAT) and includes statistical significance tests and effect sizes, lending credibility to the claims . The authors also release pseudocode and discuss computational shortcuts, supporting reproducibility.\n\nWeaknesses:\n\n1. Empirical scope is still modest: all large-scale experiments run on CPUs with no wall-clock comparisons, so the claimed training-speed advantage of DropSens remains anecdotal. \n\n2. DropSens relies on in-degree–specific formulas and was tuned for GCN; results for GIN and GAT are weaker, underlining limited architecture generality. \n\n3. The paper does not explore the effect of the preservation hyper-parameter c nor the sensitivity of DropSens to degree distribution outliers.", "was_revised": true, "final_justification": "Thank you the author(s) for your clarification on my previous misunderstanding, taking my suggestion into account and completing several extra experiments which can be revised into the new version of the paper. I have no more questions, and at this stage I support the acceptance of the paper.", "rebuttal": "Thank you very much for the insightful summary, for recognizing the strengths of our work, and for the overall feedback!\n\nBefore we address your concerns, we wanted to bring to your attention that we had accidentally omitted the DropSens configuration \\$(c, q\\_{\\max}) = (0.8, 0.3)\\$ from our original hyperparameter sweep. This has now been included, and the results have been updated accordingly. The overall findings remain unchanged, with the exception that **DropSens now ranks 3rd on the Proteins dataset**.\n\n---\n\nKindly find our responses to the concerns raised:\n\n> Empirical scope is still modest: all large-scale experiments run on CPUs with no wall-clock comparisons, so the claimed training-speed advantage of DropSens remains anecdotal.\n\nThank you for pointing this out. To clarify, the hardware setup used for all large-scale experiments is described in Appendix E: **we use 4$\\times$ NVIDIA GeForce GTX TITAN X GPUs (12 GB VRAM each)**.\n\nYou're absolutely right that wall-clock runtimes were not reported in the initial submission. We have now addressed this:\n\n**We first show the preprocessing time required to compute edge-dropping probabilities for DropSens as a function of node in-degree**, since the *cost of solving for $q_i$ grows with $d_i$*. We plot results for $d_i = 1, 2, \\ldots, 100$, averaged over $c = 0.1, 0.2, \\ldots, 0.9$ in Figure 6b; for readability, we report values only for $d_i = 1, 2, 5, 10, 20, 50, 100$ in the table below.\n\n|  | 1 | 2 | 5 | 10 | 20 | 50 | 100 |\n| :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: |\n| Exact Computation time $\\times 10^{-2}$ | $3.316 \\pm 5.961$ | $1.904 \\pm 0.952$ | $2.713 \\pm 0.728$ | $4.011 \\pm 1.514$ | $10.181 \\pm 6.186$ | $43.803 \\pm 23.147$ | $169.897 \\pm 52.593$ |\n| Approximation Computation Time $\\times 10^{-6}$ | $3.253 \\pm 0.568$ | $1.316 \\pm 0.131$ | $1.097 \\pm 0.021$ | $1.117 \\pm 0.025$ | $1.113 \\pm 0.013$ | $1.089 \\pm 0.062$ | $1.103 \\pm 0.011$ |\n\n**We now compare the initialization and sampling time of DropSens ($c=0.8, q_{\\max}=0.5$) compared to sampling time of DropEdge**, averaged over 10 runs, isolating the runtime difference since sampling is the only point where the two methods differ computationally$.^1$ We have added this comparison in Figure 7, and also present the results in the table below, with all entries reported in milliseconds:\n\n|  | Cora | CiteSeer | PubMed | Chameleon | Squirrel | TwitchDE | Actor | Mutag | Proteins | Enzymes | Reddit | IMDb | Collab |\n| :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: |\n| DropSens Initialization | $104$ | $67$ | $74$ | $89$ | $85$ | $83$ | $43$ | $49$ | $68$ | $58$ | $69$ | $132$ | $483$ |\n| DropSens Sampling | $17$ | $13$ | $51$ | $50$ | $61$ | $44$ | $16$ | $13$ | $39$ | $27$ | $92$ | $58$ | $1163$ |\n| DropEdge Sampling | $1$ | $1$ | $0$ | $1$ | $0$ | $0$ | $0$ | $1$ | $0$ | $1$ | $1$ | $1$ | $6$ |\n\nAs expected, **DropSens sampling is more expensive** due to the need to compute edge-wise dropping probabilities per graph. That said, **this step accounts for only a small fraction of overall training time and was never the bottleneck in our experiments**\n\n***Note**: Runtimes might vary form server to server, but we expect the trends to be similar.*\n\nWe do want to clarify that **we do not claim a training-speed advantage for DropSens**. On the contrary, due to its preprocessing step, it may be marginally slower than DropEdge. We made this explicit in Appendix E.3, where we also provide a low-cost approximation for solving Equation 4.1.\n\nDoes this address your concern about the empirical scope and runtime reporting?\n\n> DropSens relies on in-degree–specific formulas and was tuned for GCN; results for GIN and GAT are weaker, underlining limited architecture generality.\n\nThank you &ndash; we agree that this is an important limitation, and we've acknowledged it in our conclusion.\n\nDropSens was specifically derived for GCN-style architectures, where the edge weights used in message aggregation are simple functions of node degree. **Extending it to other architectures raises nontrivial challenges**:\n1. GIN uses constant edge weights, so the sensitivity of a node to its neighbors simplifies to $(1 - q)\\|\\|\\mathbf{W}\\|\\|$ for dropping probability $q$. **Enforcing a fixed information preservation ratio $c$ leads to $q = 1 - c$, which is equivalent to DropEdge**. This limitation arises because GIN’s aggregation is insensitive to the local graph structure, making a principled variant of DropSens unnecessary.\n2. GAT, in contrast, uses feature-dependent attention weights that vary at every layer and iteration. This means **a DropSens-style approach would require recomputing edge masks dynamically in each iteration and each layer**, negating the simplicity we aim for. Moreover, the presence of softmax attention makes a closed-form derivation of sensitivity intractable (if at all possible).\n\nIn short, while DropSens is not directly applicable to GIN or GAT, **this is a consequence of their architectural design, not a shortcoming of the method per se**. We see this as an opportunity for future work &ndash; developing principled dropout strategies tailored to different message-passing schemes.\n\nDoes this address your concern regarding the architectural generality of DropSens?\n\n> The paper does not explore the effect of the preservation hyper-parameter c nor the sensitivity of DropSens to degree distribution outliers.\n\nThank you for highlighting this. You’re absolutely right that we did not explicitly discuss the role of the preservation hyper-parameter $c$ in the *main text*. While Figure 6a does compare the dropping probabilities for different values of $c$, we have now **added a discussion at the end of Section 4 to clarify how varying $c$ affects the dropping probabilities** for different in-degrees.\n\nRegarding sensitivity to degree outliers, DropSens assigns dropping probabilities based on the degree of the target node, which means that edges connected to extremely high-degree nodes may receive disproportionately high dropping probabilities. **To prevent overly aggressive edge-removal in such cases, we clip the computed probabilities**, as described under \"DropSens Configurations\" in Appendix E.2. We have also added this implementation detail at the end of Section 4 to make this design choice explicit:\n\n\"*Note that higher values of $c$ encourage lower $q_i$, while lower values permit $q_i$ to take higher values; see Figure 6a. Since this can result in abnormally high dropping probabilities, we clip the value of $q_i$ in our experiments using another hyperparameter, $q_{\\max}$; see details in Appendix E.2.*\"\n\nDoes this address your concern about both the role of $c$ and the robustness to degree outliers?\n\n> Provide an ablation on SyntheticZINC varying the preserved-information parameter $c \\in 0.7, 0.8, 0.9, 0.95$; show accuracy and number of edges kept.\n\nThank you for the suggestion &ndash; we agree that this ablation would offer valuable insight. As a first step, **we evaluate DropSens with $c = 0.9, 0.65$**, which preserve approximately the same number of edges in expectation ($\\approx 402$k, $248$k, respectively) as DropEdge with $q = 0.2, 0.5$ ($\\approx 400$k, $250$k, respectively).\n\nKindly find the results for DropSens with $c = 0.9$ below, where we observe that it improves on its DropEdge counterpart, $q=0.2$; we will report on $c = 0.65$ soon.\n\n**Train MAE $\\times 10^{-2}$** (lower is better)\n| Method | $\\alpha=0.1$ | $0.2$ | $0.3$ | $0.4$ | $0.5$ | $0.6$ | $0.7$ | $0.8$ | $0.9$ | $1.0$ |\n| :-:| :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: |\n| DropSens ($c=0.9$) | $6.062$ | $6.831$ | $7.203$ | $7.297$ | $8.204$ | $7.157$ | $6.605$ | $6.552$ | $6.545$ | $6.807$ |\n| DropEdge ($q=0.2$) | $6.369$ | $7.016$ | $7.389$ | $7.339$ | $7.455$ | $7.374$ | $6.993$ | $7.420$ | $6.588$ | $7.213$ |\n| DropSens ($c=0.65$) |  |  |  |  |  |  |  |  |  |  |\n| DropEdge ($q=0.5$) | $8.218$ | $8.954$ | $9.173$ | $9.210$ | $9.109$ | $9.076$ | $8.834$ | $8.807$ | $8.754$ | $9.067$ |\n\n**Test MAE $\\times 10^{-2}$** (lower is better)\n| Method | $\\alpha=0.1$ | $0.2$ | $0.3$ | $0.4$ | $0.5$ | $0.6$ | $0.7$ | $0.8$ | $0.9$ | $1.0$ |\n| :-:| :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: |\n| DropSens ($c=0.9$) | $6.739$ | $7.221$ | $7.830$ | $8.156$ | $9.134$ | $8.221$ | $7.442$ | $7.118$ | $6.760$ | $6.355$ |\n| DropEdge ($q=0.2$) | $7.096$ | $7.496$ | $8.262$ | $8.567$ | $8.781$ | $8.801$ | $8.168$ | $8.099$ | $7.066$ | $7.221$ |\n| DropSens ($c=0.65$) |  |  |  |  |  |  |  |  |  |  |\n| DropEdge ($q=0.5$) | $13.326$ | $13.459$ | $14.805$ | $15.215$ | $14.753$ | $14.501$ | $14.101$ | $13.567$ | $12.566$ | $13.381$ |\n\n> How does DropSens behave on power-law graphs where a few hubs dominate degrees? Include an experiment or theoretical bound on maximum drop probability in that regime.\n\nThank you for raising this important point. You're absolutely right that on power-law graphs, **a small number of high-degree hubs can lead DropSens to assign extremely high dropping probabilities, potentially close to $1$**. Since DropSens does not impose a theoretical bound on dropping probability (except the vacuous bound, $1$), this behavior is expected when in-degrees are very large.\n\nTo mitigate this, **we cap the dropping probabilities using a hyper-parameter $q_{\\max}$, which ensures that even high-degree nodes retain a minimum level of connectivity**. This clipping mechanism is already implemented in our experiments, but we realize this detail was not clearly communicated. **We have now added a clarification at the end of Section 4 to make this design choice explicit**.\n\nDoes this address your concern about DropSens on power-law graphs and the lack of a theoretical bound?\n\n---\n\n**Footnotes**:\n\n1. For graph classification tasks, edge masks are computed in one go (instead of one mini-batch at a time, as in practice)."}, {"review_id": "06zlMxLDI7", "reviewer": "Reviewer_5aYk", "summary": "The paper looks at various dropout methods for graph NNs. These method have been\nintroduced to try and alleviate the over-smoothing problem. The paper postulates\nthat these methods might actually make another problem, over-squashing, worse,\nbecause they introduce more bottlenecks in the graph. The authors show this is\nin fact true when the model is a linear GCN.\nThe analysis is used to design a new dropout method, DropSens, which makes the\ndropout node-dependent in such a way that it reduces over-squashing. DropSens is\nshown to be more effective in enabling long-range interactions in GCNs than\nalternative graph rewiring methods.", "questions": "- Do you mean to include a kronecker delta ($\\delta_{ij}$) in Eq. (3.3)?\n- Can you provide more experiments with a wider variety of datasets? Only 3\n  homophilous and 3 heterphilous datasets is lacking.\n- Can you provide an explanation as to why you believe DropSens has an advantage\n  over graph rewiring methods?\n- Can you speculate (or even better, evaluate) on a sensible version of DropSens for GIN/GAT?", "limitations": "Authors should mention a small number of 'real world' datasets as a limitation", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n- The paper provides a clear and sufficient background for understanding the\n  problem of over-squashing.\n- The proposed method (GCN+DropSens) is clear and targeted, and provides obvious improvements\n  over the GCN+Rewiring in the node-classification setting.\n- The work provides a fairly convincing explanation as to why dropout methods\n  damage long-range abilities for GCNs.\n\nWeaknesses:\n\n- While performance improvements are clear for node-classification tasks,\n  improvements are less clear on the graph-classification tasks\n  (Table 2 (b)). For example, DropSens underperforms by $\\sim$10 points on\n  Mutag, $\\sim 15$ points on IMDb\n- DropSens only performs well on GCN, and not on GAT or GIN.\n- The paper does not propose an alternative for these GAT/GIN.\n- The empirical analysis should include more datasets.\n- Empirical results from the paper are not clear from the abstract (i.e. that DropSens only works well on GCN).\n\nOverall the results are lacking, and the paper could be drastically improved by adding more datasets and/or an improvement for GIN.\n\nMinor issues:\n\n- Some notations are not clearly defined. For example, ND/DE in the\n  expectations (line 195, line 145), difference between P and \\dot{P} could be\n  clearer, and $E_{M^i}$ is not properly defined.\n- A comparison between DropSens and the other dropout variants would be helpful;\n  perhaps this could be done by include the best dropout method in Table 2.\n- Missing error bars in Table 2, Figure 3", "was_revised": true, "final_justification": "I believe this is a clearly written paper, with the proposed DropSens method well motivated and producing benefits in practice regarding long-range interactions. I thank the authors for running more benchmarks\n\nWhile the reviewers addressed the majority of my points, I keep my rating because the method is weaker for the other common architectures (GAT/GIN) and there doesn't seem to be any obvious recourse here.", "rebuttal": "Thank you very much for the insightful summary, for recognizing the strengths of our work, and for the overall feedback!\n\nBefore we address your concerns, we wanted to bring to your attention that we had accidentally omitted the DropSens configuration \\$(c, q\\_{\\max}) = (0.8, 0.3)\\$ from our original hyperparameter sweep. This has now been included, and the results have been updated accordingly. The overall findings remain unchanged, with the exception that **DropSens now ranks 3rd on the Proteins dataset**.\n\n---\n\nKindly find our responses to the concerns raised:\n\n> While performance improvements are clear for node-classification tasks, improvements are less clear on the graph-classification tasks (Table 2 (b)). For example, DropSens underperforms by $\\sim 10$ points on Mutag, $\\sim 15$ points on IMDb\n\nThank you for highlighting this. We agree that DropSens underperforms the best rewiring method on the two datasets you mention. That said, we would like to point out that **DropSens achieves the best performance on 3 out of the 6 graph classification tasks, and ranks 3rd on another**. Note that in the case of the IMDb dataset, *DIGL exhibits unusually strong performance*, even outperforming several more recent graph rewiring methods such as SDRF, FoSR, and GTR. While we are unsure of the exact reason for this, we do observe that **DropSens remains competitive with the rest of the baselines on this dataset**.\n\n> DropSens only performs well on GCN, and not on GAT or GIN.\n\n> The paper does not propose an alternative for these GAT/GIN.\n\n> Can you speculate (or even better, evaluate) on a sensible version of DropSens for GIN/GAT?\n\nThank you &ndash; we agree that this is an important limitation, and we've acknowledged it in our conclusion.\n\nDropSens was specifically derived for GCN-style architectures, where the edge weights used in message aggregation are simple functions of node degree. **Extending it to other architectures raises nontrivial challenges**:\n1. GIN uses constant edge weights, so the sensitivity of a node to its neighbors simplifies to $(1 - q)||\\mathbf{W}||$ for dropping probability $q$. **Enforcing a fixed information preservation ratio $c$ leads to $q = 1 - c$, which is equivalent to DropEdge**. This limitation arises because GIN’s aggregation is insensitive to the local graph structure, making a principled variant of DropSens unnecessary.\n2. GAT, in contrast, uses feature-dependent attention weights that vary at every layer and iteration. This means **a DropSens-style approach would require recomputing edge masks dynamically in each iteration and each layer**, negating the simplicity we aim for. Moreover, the presence of softmax attention makes a closed-form derivation of sensitivity intractable (if at all possible).\n\nIn short, while DropSens is not directly applicable to GIN or GAT, **this is a consequence of their architectural design, not a shortcoming of the method per se**. We do not propose alternatives for these architectures in this paper, but see this as an opportunity for future work &ndash; developing principled dropout strategies tailored to different message-passing schemes.\n\nDoes this address your concern regarding the architectural specificity of DropSens and the lack of proposed variants for GAT and GIN?\n\n> The empirical analysis should include more datasets.\n\n> Can you provide more experiments with a wider variety of datasets? Only 3 homophilous and 3 heterphilous datasets is lacking.\n\nThank you for the suggestion. We used **a total of 14 datasets in our empirical evaluation &ndash; one synthetic graph regression dataset, 7 real-world node classification datasets and 6 graph-classification ones**. The node classification datasets were carefully chosen to span both short-range and long-range tasks, in line with prior work studying over-squashing effects. The graph classification datasets follow the benchmark selection used in recent influential work on rewiring strategies. While we agree that broader empirical coverage is always desirable, we believe our current set strikes a strong balance between diversity and relevance for the problem setting.\n\nThat said, **we are aiming to share a comparison between NoDrop, DropEdge and DropSens on the PeptidesStruct graph-regression dataset from the Long Range Graph Benchmark** by the end of discussion period. We would appreciate your patience as we work on it.\n\n> Empirical results from the paper are not clear from the abstract (i.e. that DropSens only works well on GCN).\n\nThank you for this feedback &ndash; **we’ve updated the abstract to clarify that DropSens is specifically designed for GCNs, and that its empirical effectiveness is primarily demonstrated in that setting**:\n\n\"*To address this, we introduce DropSens, a sensitivity-aware variant of DropEdge, which is developed following the message-passing scheme of GCN. [...] DropSens with GCN consistently outperforms graph rewiring techniques designed to mitigate over-squashing, suggesting that simple, targeted modifications can substantially improve a model's ability to capture long-range interactions.*\"\n\n> Some notations are not clearly defined. For example, ND/DE in the expectations (line 195, line 145), difference between P and \\dot{P} could be clearer, and $E_{M_i}$ is not properly defined.\n\nThank you for pointing this out &ndash; **we’ve made the following clarifications to address these notational issues**:\n1. The subscripts ND and DE now explicitly refer to NoDrop and DropEdge models, respectively.\n2. We’ve added a footnote clarifying that $\\dot{\\mathbf{P}}$ and $\\ddot{\\mathbf{P}}$ denote the expected propagation matrices under the asymmetric and symmetric propagation rules, respectively.\n3. To reduce ambiguity, we’ve renamed $\\mathbf{P}$ &ndash; previously used for the transition matrix of a uniform random walk &ndash; to $\\mathbf{T}$.\n4. We’ve also defined the expectation $\\mathbb{E}_{\\mathbf{M}_i}$ over edge masks, right before Equation 3.2.\n\nDoes this address your concerns regarding notation clarity?\n\n> A comparison between DropSens and the other dropout variants would be helpful; perhaps this could be done by include the best dropout method in Table 2.\n\nThank you for the suggestion. We agree that a broader comparison with other dropout variants could be valuable, especially to situate DropSens in the wider space of dropping methods. Accordingly, we have added the performance rankings for dropout methods in Appendix G.1 (Table 6). Notably, **DropSens ranks 1stin $11/38 \\approx 29\\\\%$ of dataset$\\times$model combinations, and places within the top-3 in $21/38 \\approx 55\\\\%$ cases**, highlighting its efficacy across a broad range of settings.\n\nJust to clarify our scope and intent: our goal in introducing DropSens was not to establish a new state-of-the-art dropout method, but rather to demonstrate that *techniques originally designed for mitigating over-smoothing can be adapted to also address over-squashing in a principled way*. For this reason, our comparisons focus on DropEdge and NoDrop as representative baselines.\n\n> Missing error bars in Table 2, Figure 3\n\nThank you for the observation. We omitted error bars from Table 2 primarily due to space constraints. Additionally, since **Table 2 already reports p-values, which directly address statistical significance**, we felt this conveyed the relevant information more concisely. For Figure 3, error bars are non-trivial to compute since we report relative improvement. Instead, **we have included mean difference and the standard error** as text above the bars, in the revised version to reflect variability across runs:\n\n| Cora | CiteSeer | PubMed | Chameleon | Squirrel | TwitchDE | Mutag | Proteins | Enzymes | Reddit | IMDb | Collab |\n| :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: |\n| $-0.11 \\pm 0.07$ | $-0.45 \\pm 0.13$ | $-0.00 \\pm 0.06$ | $1.70 \\pm 0.57$ | $0.36 \\pm 0.21$ | $0.08 \\pm 0.15$ | $2.80 \\pm 1.98$ | $1.41 \\pm 0.82$ | $1.31 \\pm 1.19$ | $4.71 \\pm 0.99$ | $0.04 \\pm 1.03$ | $-0.67 \\pm 0.84$ |\n\nDoes this address your concern?\n\n> Do you mean to include a kronecker delta ($\\delta_{ij}$) in Eq. (3.3)?\n\nYes, thank you for catching that. We have specified that Equations 3.3 and 3.4 hold if and only if $(j \\to i) \\in \\mathcal{E}$.\n\n> Can you provide an explanation as to why you believe DropSens has an advantage over graph rewiring methods\n\nThank you for this question. We want to clarify that we do not claim DropSens to have an advantage over graph rewiring methods. Our goal was to demonstrate that a simple modification to DropEdge can lead to consistent performance gains, particularly by taking sensitivity to distant nodes into account.\n\nThat said, we believe DropSens performs competitively in practice for two reasons:\n1. It **addresses both over-smoothing and over-squashing simultaneously**, rather than focusing on just one of the problems, and\n2. As a stochastic method, it **introduces a regularization effect** that improves generalization."}, {"review_id": "ffSUyFaFAL", "reviewer": "Reviewer_RHiq", "summary": "Graph neural networks are known to suffer from issues like over-squashing (due to topological bottlenecks) which affect long-range interactions and over-smoothing, wherein repeated rounds of information aggregation results in node representations losing their discriminative power. This work explores the connections between Dropout style algorithms such DropEdge, DropNode, DropAgg and DropGNN and over-squashing. While Drop-out style algorithms have been shown to mitigate over-smoothing and improve downstream performance, this current work highlights the limitations of such methods by showing how these methods desensitize distant nodes to each other consequently making over-squashing worse. As a resolution DropSens is proposed which is a sensitivity-aware variant of DropEdge that can control the proportion of information lost due to edge-dropping, ensuring long-range interactions between distant nodes is enhanced. Extensive experiments on different datasets and GNN (GCN and GIN) models confirm their hypothesis.", "questions": "**See weaknesses**", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n\n1. The characterization of interaction between random dropout style algorithms and over-squashing via the sensitivity analysis is really interesting.\n\n2. The proposed DropSens algorithm seems to increase the sensitivity of long-range nodes and thus possibly help with over-squashing.\n\n3. The paper is well-written and well-structured.\n\n**Weaknesses**\n\n1. While I understand the whole dichotomy between over-squashing and over-smoothing trade-off, I am not really sure if the current motivation of the work is strong enough. The sensitivity analysis has already been proposed in [1] and [2] and making use of this analysis to show that dropout style algorithms might make over-squashing worse while is an interesting observation but its perhaps not entirely unexpected, since the dropout style algorithms were originally proposed with different design goals. \n\n2. The discussion on sensitivity analysis (Figure 1) could use a little more nuance. How would the sensitivity analysis look like for a heterophilic dataset?  Does random edge dropping affect **different-class neighbors** more than **same-class neighbors** (which would be good)? Or does it reduce both? And thus could potentially explain why we see no significant results on heterophilic datasets?\n\n3. The paper argues that random edge dropping harms long-range tasks, and the results on heterophilic datasets are presented as evidence. However, one might intuitively expect dropping a small number of edges might be beneficial in heterophilic settings, since its more likely we prune connections between nodes of different labels? For instance, the work talks about absolute sensitivity reduction between distant nodes through random dropout style algorithms, but it is possible deleting a small number of edges in a heterophilic setting might reduce the influence of noisy neighbours and thus might improve relative sensitvity between same-class distant nodes?\n\n4. Experiments on Long Range Graph Benchmark datasets (LRGB) [3] [4] are missing. I think this is an important benchmark to include if the theme is on long range interactions. It would be interesting to see how these Dropout style algorithms including the proposed DropSens perform when it comes to LRGB datasets. I understand the datasets in LRGB have different tasks but PASCAL-VOC is a node classification task and datasets such as peptides-func and peptides-struct are graph classification and regression tasks respectively and ideally should have no problem including them in the experiments (since results on graph classification is already included in the work anyway).\n\n5. I think the work currently assumes somewhat pessimistic view - **dropout style algorithms which remove edges are detrimental**, but what about strategic edge deletions? For instance [5] shows that specific edge deletions can increase the spectral gap via the Braess paradox and thus can mitigate over-squashing while not making over-smoothing worse?\n\n\n\n**References**\n\n1. Understanding over-squashing and bottlenecks on graphs via curvature. Topping et al, ICLR 2022.\n\n2. On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology. Di Giovanni et al, ICML 2023.\n\n3. Long Range Graph Benchmark, Dwivedi et al 2022.\n\n4. Where Did the Gap Go? Reassessing the Long-Range Graph Benchmark, Toenshoff et al, TMLR 2023.\n\n5. Spectral Graph Pruning Against Over-squashing and Over-smoothing, Jamadandi et al, NeurIPS, 2024.", "was_revised": true, "final_justification": "The authors have done a good job of providing with extra experiments. However, I maintain my position on the fundamental motivation: demonstrating that random dropout-style algorithms perform poorly on long-range tasks—when they were designed for entirely different purposes—feels like evaluating the wrong tool for the wrong job. Further, results on LRGB which actually have long range interactions suggest the proposed DropSens (and Drop-out variants like DropEdge) perform poorly compared to NoDrop also reinforces my initial concern about the applicability of such methods for modeling long range interactions.\nI have increased my score from 2 to 4 in recognition of the authors' responses and the technical merit of their approach, but I am not entirely convinced to champion this paper for acceptance.", "rebuttal": "Thank you very much for the insightful summary, for recognizing the strengths of our work, and for the overall feedback!\n\nBefore we address your concerns, we wanted to bring to your attention that we had accidentally omitted the DropSens configuration \\$(c, q\\_{\\max}) = (0.8, 0.3)\\$ from our original hyperparameter sweep. This has now been included, and the results have been updated accordingly. The overall findings remain unchanged, with the exception that **DropSens now ranks 3rd on the Proteins dataset**.\n\n---\n\nKindly find our responses to the concerns raised:\n\n> [...] making use of this analysis to show that dropout style algorithms might make over-squashing worse [...] perhaps not entirely unexpected, since the dropout style algorithms were originally proposed with different design goals.\n\nThank you for sharing your perspective. We agree that it may seem intuitive that dropout-style methods reduce sensitivity between distant nodes. However, **our theoretical analysis serves a deeper purpose** than simply confirming this behavior: it provides a concrete understanding of ***why*** and ***how*** these methods fall short in the context of long-range tasks, and it **motivates the design of DropSens as a principled alternative**.\n\nWhile it may not be surprising that these methods diminish long-range sensitivity, the key concern we highlight is that **this fundamentally undermines their utility for the very tasks that deeper GNNs aim to solve**:\n\n*The original motivation behind alleviating over-smoothing was to enable training of deeper MPNNs, which are only necessary when long-range dependencies matter. But if dropout-based methods worsen over-squashing, they negate this benefit &ndash; deep models may remain trainable (i.e., node representations don't collapse), but the model is still unable to leverage information from distant nodes for prediction.*\n\nThis, in our view, is a **critical and underappreciated limitation**. We are not claiming that these methods are ineffective in general, but that **they should *not* be applied in isolation when long-range interactions are important**. Our hope is this analysis will motivate practitioners to thoroughly assess the effects of methods designed for alleviating over-smoothing and training deep GNNs, with regards to their effects on over-squashing.\n\n> How would the sensitivity analysis look like for a heterophilic dataset? [...] could potentially explain why we see no significant results on heterophilic datasets?\n\nThank you for these thoughtful questions. First, we’d like to clarify a possible misconception: **our sensitivity analysis (as shown in Figure 1) does not depend on node labels**. It measures the norm of the Jacobian of the final node representations (e.g., logits or regressands) with respect to the input node features. As such, **it is agnostic to whether a dataset is homophilic or heterophilic** &ndash; the analysis captures how much a node’s output depends on the input features of other nodes, regardless of class.\n\nSecond, **random edge-dropping methods like DropEdge are entirely blind to node or edge attributes**, including class membership. They drop edges uniformly at random, and thus **reduce influence from both same-class and different-class neighbors indiscriminately**. This uniformity could indeed be suboptimal, and it points toward a promising direction, as you hint: *incorporating structural or label-aware heuristics to guide edge dropping* may help preserve task-relevant information more effectively, especially in settings where homophily cannot be assumed.\n\nAs for why dropout methods perform much worse on heterophilic datasets than on homophilic datasets, we refer to Section 5.2:\n\n\"*[...] homophilic datasets have local consistency in node labels, i.e. nodes closely connected to each other have similar labels. On the other hand, in heterophilic datasets, nearby nodes often have dissimilar labels. Since DropEdge-variants increase the sensitivity of a node’s representations to its immediate neighbors, and reduce its sensitivity to distant nodes, we expect it to improve performance on homophilic datasets but harm performance on heterophilic ones […]*\"\n\n> [...] one might intuitively expect dropping a small number of edges might be beneficial in heterophilic settings [...] might reduce the influence of noisy neighbours and thus might improve relative sensitvity between same-class distant nodes?\n\nThank you for this thoughtful observation. We understand the intuition that dropping a small number of edges might reduce the influence of noisy (i.e., different-class) neighbors in heterophilic settings. However, we believe this intuition overlooks a key limitation of random edge-dropping methods like DropEdge: **they do not use any information from node features, class labels, or graph structure when sampling edge masks**. Edges are dropped independently and uniformly at random, with no consideration for whether an edge connects same-class or different-class nodes.\n\nThis means that while it is possible that a given sampled mask might coincidentally drop some \"noisy\" edges, **the probability of consistently retaining the correct paths for information flow &ndash; especially between distant same-class nodes &ndash; is extremely low**. This is because successful long-range propagation typically requires *entire paths* of edges to be active in the forward pass. Dropping even a single edge on such a path breaks the flow of information. Hence, random dropout is more likely to disrupt useful long-range communication than improve it, particularly in heterophilic graphs where same-class nodes tend to be farther apart.\n\nThis is precisely the phenomenon our sensitivity analysis and experiments aim to highlight: dropout methods, while helpful in alleviating over-smoothing, can severely exacerbate over-squashing by indiscriminately pruning edges &ndash; thereby reducing a node’s sensitivity to informative distant features.\n\nUltimately, **if the goal is to reduce influence from different-class neighbors while preserving important long-range same-class connections, this requires structured or informed edge-dropping, not random sampling**. Our work points toward this need by showing the limitations of uniform random edge-drop methods in heterophilic and long-range settings.\n\n> Experiments on Long Range Graph Benchmark are missing [...]\n\nThank you for this thoughtful suggestion. We fully agree that the LRGB benchmark is highly relevant for evaluating long-range reasoning capabilities, and we appreciate the opportunity to clarify our decision.\n\nFirst, we would like to highlight the computational cost of our experiments. For each *dataset $\\times$ GNN $\\times$ dropping method* combination, we conducted 20 runs across 9 different dropping probabilities, followed by 30 additional runs for the best configuration (see \"Number of Independent Runs\" under Appendix E.2 to learn why we take 50 runs for evaluation), totaling **210 runs per setting**. Extending this setup to large-scale LRGB datasets, which involve significantly larger graphs and longer training times, was unfortunately beyond our available compute budget.\n\nSecond, **our current choice of datasets was motivated by the desire to make direct and meaningful comparisons with prior works on graph rewiring for alleviating over-squashing** (Black et al., 2023; Karhadkar et al., 2023; Topping et al., 2022). These prior works have widely adopted the benchmark suite used in our study, so evaluating on these datasets allowed us to assess DropSens in the context of established baselines.\n\nThat said, we recognize the value of testing dropout-style methods on LRGB tasks, and we agree that it is an exciting direction, especially since the LRGB datasets include both node- and graph-level tasks, making them a natural complement to our current benchmark. For that reason, **we are aiming to share a comparison between NoDrop, DropEdge and DropSens on the PeptidesStruct graph-regression dataset** by the end of discussion period. We would appreciate your patience as we work on it.\n\n> I think the work currently assumes somewhat pessimistic view [...] can mitigate over-squashing while not making over-smoothing worse?\n\nThank you for sharing this reference &ndash; we weren’t previously aware of it, and we found it very insightful. We fully agree that *strategic* edge deletion offers a promising approach to addressing both over-smoothing and over-squashing. In fact, this aligns with our broader message: **it’s not the act of edge deletion itself that is harmful, but *how* it is done**.\n\n**Our work critiques dropout-style methods like DropEdge not because they remove edges per se, but because they do so uniformly at random**, without regard to the underlying graph topology or feature space. By contrast, **methods that perform *informed* or *topology-aware* edge deletion** &ndash; including those leveraging phenomena like the Braess paradox to enhance spectral properties &ndash; **can potentially mitigate over-squashing without exacerbating over-smoothing**. We view such methods as complementary to our analysis, and have discussed a few works on unified treatment of over-smoothing and over-squashing in Appendix A.4; we have also added the reference you shared in this section.\n\n---\n\n**References**:\n\nMitchell Black, Zhengchao Wan, Amir Nayyeri, and Yusu Wang. *Understanding oversquashing in GNNs through the lens of effective resistance*. In International Conference on Machine Learning, 2023.\n\nKedar Karhadkar, Pradeep Kr. Banerjee, and Guido Montufar. *FoSR: First-order spectral rewiring for addressing oversquashing in GNNs*. In International Conference on Learning Representations, 2023.\n\nJake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein. *Understanding over-squashing and bottlenecks on graphs via curvature*. In International Conference on Learning Representations, 2022."}]

Author rebuttal:

Meta-review: This paper investigates the impact of dropout-based methods (DropEdge, DropNode, etc.) on over-squashing in Graph Neural Networks, revealing that while these methods address over-smoothing, they can exacerbate over-squashing by reducing sensitivity to distant nodes. The authors propose DropSens, a sensitivity-aware variant that preserves long-range interactions while maintaining the benefits of edge dropping. The work received scores of 5 (accept), 4 (borderline accept), 4 (borderline accept), and 4 (borderline accept) from four engaged reviewers. Strengths include: (1) Novel theoretical insight - The paper provides the first systematic analysis of how dropout methods affect over-squashing through sensitivity analysis, revealing an important but previously unrecognized trade-off between addressing over-smoothing and preserving long-range interactions; (2) Strong theoretical foundation - The mathematical analysis extending sensitivity measures to edge-dropping scenarios is rigorous and well-motivated, leading naturally to the DropSens algorithm design; (3) Comprehensive experimental validation - The authors conducted extensive experiments across synthetic and real-world datasets, responded thoroughly to reviewer concerns by adding results on LRGB datasets, and provided detailed computational analysis; (4) Practical contribution - DropSens offers a principled solution that maintains simplicity while addressing the identified limitations. Limitations acknowledged: (1) Architecture specificity - DropSens is primarily designed for GCN architectures, with limited applicability to GIN/GAT due to their different message-passing schemes; (2) Scope constraints - While the experimental evaluation is solid, it focuses on medium-scale datasets with some computational limitations for larger benchmarks. The authors demonstrated exceptional responsiveness during the review process, conducting additional experiments, updating experimental setups to match prior work, and providing thorough theoretical explanations. All reviewers acknowledged the quality of the responses and the authors' transparency in reporting both positive and negative results. The work makes a valuable contribution to understanding the complex interplay between different GNN training techniques and their effects on fundamental graph learning challenges.
Decision: Accept (poster)