Effects of Dropout on Performance in Long-range Graph Learning Tasks

Thank you very much for the insightful summary, for recognizing the strengths of our work, and for the overall feedback!

Before 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.

Kindly find our responses to the concerns raised:

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

Thank 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.

While 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:

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 – 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.

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

How would the sensitivity analysis look like for a heterophilic dataset? [...] could potentially explain why we see no significant results on heterophilic datasets?

Thank 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 – the analysis captures how much a node’s output depends on the input features of other nodes, regardless of class.

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

As for why dropout methods perform much worse on heterophilic datasets than on homophilic datasets, we refer to Section 5.2:

"[...] 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 […]"

[...] 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?

Thank 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.

This 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 – especially between distant same-class nodes – 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.

This 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 – thereby reducing a node’s sensitivity to informative distant features.

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

Experiments on Long Range Graph Benchmark are missing [...]

Thank 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.

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

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

That 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.

I think the work currently assumes somewhat pessimistic view [...] can mitigate over-squashing while not making over-smoothing worse?

Thank you for sharing this reference – 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.

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 – including those leveraging phenomena like the Braess paradox to enhance spectral properties – 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.

References:

Mitchell 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.

Kedar Karhadkar, Pradeep Kr. Banerjee, and Guido Montufar. FoSR: First-order spectral rewiring for addressing oversquashing in GNNs. In International Conference on Learning Representations, 2023.

Jake 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.

Thank you very much for the response!

[...] all the dropout-style methods have primarily been evaluated on homophilic graphs [...] where the label/feature of nodes are homophilic and LRIs might not be a problem and Drop-out style methods work and they also meet their intended design goal of training deeper GNNs. [...] This makes the motivation feel less like a novel insight and more like an application of a known tool to the wrong problem.

Thank you for raising this concern. We believe the disagreement stems from a different understanding of the purpose behind dropout-style methods and deep MPNNs.

Our work focuses on message-passing neural networks (MPNNs), where depth is synonymous with reach, since the number of layers directly governs how far information can propagate in the graph. Therefore, we believe the motivation for training deep MPNNs is precisely to model long-range interactions. In fact, using deep MPNNs on tasks with only short-range dependencies may result in dataset-model misalignment. This is why we argue that evaluating such methods solely on homophilic datasets (where long-range signals are not necessary) paints an incomplete picture. As we discuss in Appendix A.2, this has led to relatively little attention being paid to how these methods affect performance on tasks that do require long-range modelling.

Since dropout-based methods compromise sensitivity to distant nodes, as we show both theoretically and empirically, the very reason for going deeper is undermined. The model may remain trainable by mitigating over-smoothing, but it cannot leverage the long-range signals, defeating the very purpose of going deeper.

Does this clarify the motivation behind our work, and the significance of our findings?

[...] it can also refer to feature heterophily, where connected nodes have dissimilar feature distributions [...] It would help us understand whether the observed reduction in sensitivity just harms all long-range connections equally, or if it has a more nuanced, feature-dependent effect that could better explain the performance on these graphs.

Ah, I see – that makes total sense! Just to make sure we are on the same page, you're suggesting that comparing the sensitivity profiles of homophilic and heterophilic datasets is helpful because homophily extends beyond node labels, so despite being label-agnostic, sensitivity analysis may offer an explanation for the difference in performances on these datasets – correct?

Would a comparison between the sensitivity profiles of PubMed (edge- and feature-homophilic, as suggested by Zheng et al. (2024, Table 3)) and Chameleon (edge- and feature-heterophilic) help address your concern?

I also think the paper could benefit from analysing what kind of edges are more likely dropped when applying Drop-out style algorithms to heterophilic datasets (same-class vs different class) [...] For instance, in a heterophilic graph dropping an edge increases the sensitvity to nearby neighbours which might be bad but if the long range interaction we are trying to capture also has a different label then it could be beneficial vs if that node had a same label, then its bad.

If I understand correctly, the question here is whether random edge-dropping affects same-class and different-class node pairs differently, particularly in the context of heterophilic graphs. In other words, you're pointing to how the topology of heterophilic datasets may influence which types of connections are disproportionately impacted by dropout.

Would it be helpful if we conducted an analysis similar to what we did for Cora, but using Chameleon instead, and with same-class and different-class node pairs grouped and analyzed separately? This would allow us to see whether dropout has different effects depending on the label relationship between nodes.

Yilun Zheng, Sitao Luan, and Lihui Chen. What Is Missing In Homophily? Disentangling Graph Homophily For Graph Neural Networks. In Annual Conference on Neural Information Processing Systems, 2024.

[...] this does not necessarily mean it fundamentally undermines their utility for the very tasks that deeper GNNs aim to solve.

Kindly see our remark above. To reiterate, we are not suggesting that these algorithms are without merit – they are effective at preventing overfitting and can help alleviate over-smoothing, thereby improving the trainability of deeper MPNNs. However, this often comes at the cost of exacerbating over-squashing, which limits their suitability for long-range tasks – the very setting where deeper MPNNs are most needed.

Instead, we view these techniques primarily as different regularizers that can be complementary to methods specifically aimed at alleviating over-squashing. For instance, Dropout was used alongside graph rewiring approaches in works such as Black et al. (2023); Karhadkar et al. (2023); and Topping et al. (2022).

We hope this makes the our motivation clear.

References

Mitchell 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.

Kedar Karhadkar, Pradeep Kr. Banerjee, and Guido Montufar. FoSR: First-order spectral rewiring for addressing oversquashing in GNNs. In International Conference on Learning Representations, 2023.

Jake 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.

First off, thank you very much for actively engaging in the discussion – we really appreciate the thoughtful feedback!

We're currently working on adding experimental results for heterophilic datasets, but in the meantime, we wanted to briefly respond to your first point.

Firstly, increasing model depth does not help with long-range interactions.

We mostly agree – increasing depth does improve the reach of MPNNs, but problems like over-smoothing and over-squashing limit their potential in practice. That’s precisely why much of the community, including us, is interested in mitigating these issues.

Graph rewiring has largely been proposed to mitigate over-squashing [...] these techniques modify the graph in a principled way [...] Random edge modifications do not have such guarantees.

We agree that dropout-based techniques don't provide formal guarantees for information flow. Therefore, their detrimental effects on over-squashing doesn’t invalidate the claims made by those works – namely, that they alleviate over-smoothing and improve the trainability of deeper MPNNs.

Consequently, methods that talk about training deeper GNN models do not have the objective of modeling long-range interactions. For instance in [2] the DropEdge acts as a graph augmentor and is supposed to help with over-fitting and over-smoothing and thus allows for training deeper GNNs [...]

Respectfully, we’d disagree. The motivation for deep MPNNs largely stems from the goal of capturing long-range interactions (LRIs). As noted in Li et al. (2018), a foundational work on over-smoothing:

"Since the graph convolution is a localized filter [...] a shallow GCN cannot sufficiently propagate the label information to the entire graph with only a few labels. [...] the accuracy of GCNs decreases much faster than the accuracy of label propagation. [...] it reflects the inability of the GCN model in exploring the global graph structure."

If the task were inherently short-range, there would be little reason to train deep MPNNs, i.e. execute multiple message-passing steps, at all. In such cases, improving the capacity of the message, aggregation or update functions (e.g., using deeper MLPs as update functions in GIN), while keeping the number of message-passing steps low, would be a more effective and efficient alternative, and would avoid the challenge of over-smoothing altogether.

Alon & Yahav (2021) make a similar point when distinguishing between short- and long-range tasks:

"Over-smoothing was mostly demonstrated in short-range tasks [...] – tasks that have small problem radii, where a node’s correct prediction mostly depends on its local neighborhood. [...] Since the learning problems depend mostly on short-range information in these datasets, it makes sense why more layers than the problem radius might be extraneous."

This framing further supports our view that the primary motivation for alleviating over-smoothing and training deeper GNNs is, indeed, to capture LRIs.

Finally, regarding the point that random dropout-like algorithms target overfitting: while we acknowledge their effectiveness on short-range tasks, in the context of long-range tasks, their benefits are often overshadowed by increased over-squashing and a tendency to overfit to short-range signals. We explore this in Appendix F, and request you to check Figures 7 and 9 for supporting evidence.

[...] similarly in [3] DropGNN helps with increasing model expressivity (Weisfeler-Leman tests etc) they dont even train a deeper GNN model [...]

We agree, and thank you for pointing this out – we apologize for the oversight. We've now added a clarification noting that while DropGNN falls under the broader class of edge-dropping algorithms, its design was not motivated by the goal of alleviating over-smoothing or enabling the training of deeper GNNs.

Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations, 2021.

Qimai Li, Zhichao Han, and Xiao-ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. Proceedings of the AAAI Conference on Artificial Intelligence, 2018.

Below, we present the average sensitivity under DropEdge, normalized by average sensitivity with NoDrop, to understand how the relative sensitivities vary for homophilic and heterophilic datasets:

It is interesting to note that the relative sensitivity is higher for heterophilic datasets than for homophilic datasets. That is, the graph topology and node features enable LRIs to be modelled better for heterophilic datasets than for homophilic datasets.

Yet, relative sensitivity falls below 1 (i.e., sensitivity under DropEdge is lower than under NoDrop) for nodes more than 2-hops away. This is not much of an issue for homophilic datasets, which are inherently short-range tasks, but it explains the poor performance on heterophilic datasets, which require modelling LRIs.

Next, we observe how DropSens improves on DropEdge by comparing their sensitivity profiles:

It is clear to observe that DropSens allows node representations to be more sensitive to distant ($d \geq 3$) nodes' features, than DropEdge, thereby improving performance on heterophilic datasets.

What is interesting is that for homophilic datasets, DropSens is more sensitive to nearby nodes than DropEdge, allowing the model to effectively capture short-range interactions. Although it is poorer at capturing short-range interactions for heterophilic datasets, the table below shows that DropSens improves over NoDrop on that front, similar to DropEdge:

This set of experiments suggests that DropSens strikes a perfect balance between NoDrop and DropEdge:

1. improves sensitivity to nearby nodes ($d \leq 2$), over NoDrop
2. improves sensitivity to distant nodes ($d \geq 3$), over DropEdge
3. mitigates over-fitting (by stochastic regularization) and over-smoothing (by reducing message-passing), just as DropEdge

Thank you very much for the insightful summary, for recognizing the strengths of our work, and for the overall feedback!

Before 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.

Kindly find our responses to the concerns raised:

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

Thank 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.

DropSens only performs well on GCN, and not on GAT or GIN.

The paper does not propose an alternative for these GAT/GIN.

Can you speculate (or even better, evaluate) on a sensible version of DropSens for GIN/GAT?

Thank you – we agree that this is an important limitation, and we've acknowledged it in our conclusion.

DropSens 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:

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

In 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 – developing principled dropout strategies tailored to different message-passing schemes.

Does this address your concern regarding the architectural specificity of DropSens and the lack of proposed variants for GAT and GIN?

The empirical analysis should include more datasets.

Can you provide more experiments with a wider variety of datasets? Only 3 homophilous and 3 heterphilous datasets is lacking.

Thank you for the suggestion. We used a total of 14 datasets in our empirical evaluation – 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.

That 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.

Empirical results from the paper are not clear from the abstract (i.e. that DropSens only works well on GCN).

Thank you for this feedback – 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:

"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."

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.

Thank you for pointing this out – we’ve made the following clarifications to address these notational issues:

1. The subscripts ND and DE now explicitly refer to NoDrop and DropEdge models, respectively.
2. 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.
3. To reduce ambiguity, we’ve renamed $\mathbf{P}$ – previously used for the transition matrix of a uniform random walk – to $\mathbf{T}$.
4. We’ve also defined the expectation $\mathbb{E}_{\mathbf{M}_i}$ over edge masks, right before Equation 3.2.

Does this address your concerns regarding notation clarity?

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.

Thank 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.

Just 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.

Missing error bars in Table 2, Figure 3

Thank 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:

Does this address your concern?

Do you mean to include a kronecker delta ($\delta_{ij}$) in Eq. (3.3)?

Yes, 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}$.

Can you provide an explanation as to why you believe DropSens has an advantage over graph rewiring methods

Thank 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.

That said, we believe DropSens performs competitively in practice for two reasons:

1. It addresses both over-smoothing and over-squashing simultaneously, rather than focusing on just one of the problems, and
2. As a stochastic method, it introduces a regularization effect that improves generalization.

Thank you again for your thoughtful feedback.

Of course, we will make sure to document the current limitations of DropSens in the revised manuscript, including why adapting it to architectures like GIN and GAT is non-trivial. We hope these observations can help guide future work toward extending DropSens-style approaches to a broader range of models.

We didn’t mean to imply that benchmarking additional datasets is an unreasonable request – rather, we aimed to strike a balance between coverage and relevance given space and resource constraints. That said, we understand if concerns about dataset diversity remain. In this regard, we’d like to point you to the new results for NoDrop, DropEdge, and DropSens on PeptidesStruct, shared in the comment titled "Updated DropSens Rankings and Results on the LRGB Dataset".

We truly appreciate your engagement and hope our responses have clarified our position.

Thank you very much for the insightful summary, for recognizing the strengths of our work, and for the overall feedback!

Before 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.

Kindly find our responses to the concerns raised:

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.

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

You're absolutely right that wall-clock runtimes were not reported in the initial submission. We have now addressed this:

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.

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:

As 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

Note: Runtimes might vary form server to server, but we expect the trends to be similar.

We 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.

Does this address your concern about the empirical scope and runtime reporting?

DropSens relies on in-degree–specific formulas and was tuned for GCN; results for GIN and GAT are weaker, underlining limited architecture generality.

Thank you – we agree that this is an important limitation, and we've acknowledged it in our conclusion.

DropSens 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:

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

In 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 – developing principled dropout strategies tailored to different message-passing schemes.

Does this address your concern regarding the architectural generality of DropSens?

The paper does not explore the effect of the preservation hyper-parameter c nor the sensitivity of DropSens to degree distribution outliers.

Thank 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.

Regarding 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:

"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."

Does this address your concern about both the role of $c$ and the robustness to degree outliers?

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.

Thank you for the suggestion – 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).

Kindly 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.

Train MAE $\times 10^{-2}$ (lower is better)

Test MAE $\times 10^{-2}$ (lower is better)

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.

Thank 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.

To 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.

Does this address your concern about DropSens on power-law graphs and the lack of a theoretical bound?

Footnotes:

1. For graph classification tasks, edge masks are computed in one go (instead of one mini-batch at a time, as in practice).

Thank you very much for actively engaging in the review process. If you have no further concerns remaining unresolved, we would appreciate it if you would consider updating your rating!

We present the full results for DropSens on SyntheticZINC below (bold indicates better performance in the comparisons 1. DropSens ($c = 0.9$) v.s. DropEdge ($q = 0.2$), and 2. DropSens ($c = 0.65$) v.s. DropEdge ($q = 0.5$)):

Train MAE $\times10^{-2}$ (lower is better)

Test MAE $\times10^{-2}$ (lower is better)

It is clear to see that DropSens outperforms DropEdge in most cases, demonstrating the benefits brought in by simple sensitivity-aware modifications to algorithms originally designed for alleviating over-smoothing and training deep GNNs.

Thank you very much for the insightful summary, for recognizing the strengths of our work, and for the overall feedback!

Before 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.

Kindly find our responses to the concerns raised:

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.

Thank you for pointing this out – 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:

Compared 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.

We hope this modification will make the comparison and the interpretation in Section 4 clearer.

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.

That makes complete sense! We have included the results for DropSens, as well as a commentary on the results in Section 5.3:

"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 – while positive in 4/6 datasets – is not statistically significant."

Just 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.

Does this address your concerns?

Figure 2 shows that NoDrop achieves the best results. Why is this dataset suitable for comparing different dropout methods?

Thank you for this question. The SyntheticZINC dataset – introduced in Giovanni et al. (2024, Section 5.1); described further in our Appendix E.1 – 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:

1. A desired mixing level $\alpha \in [0, 1]$ is fixed.
2. Commute times between all node pairs in a graph are computed.
3. A node pair is selected whose commute time lies at the $\alpha$-th percentile of the graph's commute time distribution.

As shown in Giovanni et al. (2024, Theorem 4.4), over-squashing in GNNs – especially with MAX pooling for graph classification (as is also our setup) – 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.

Does that clarify your concern about the suitability of this dataset?

In Eq. (2), the set should be the argument of the Out function.

Yes, thank you for the correction!

Eq. (3.2) The index $\mathbf{M}^{(1)}, \ldots$ is not clear.

Fair 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.

References:

Francesco 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.