Effects of Random Edge-Dropping on Over-Squashing in Graph Neural Networks

Thank you for your review! Kindly find our responses below to the weaknesses and questions raised.

The proof in appendix A1 is not quite clear. Maybe explain more.

We have added some remarks building up to the computation of the expected message weight in Appendix B.1. Kindly let us know if anything remains unclear.

There are some datasets on long range interaction (LRI) and over-squashing, say trees match and peptides datasets. They are missing from the experiments.

Reviewer Z8L5 remarked something similar as well. Kindly check our comment addressing these concerns together under the heading “set of datasets used”. We assume you are referring to the NeighborsMatch dataset in [1]. We do agree that evaluation on more datasets is always desirable for making generalizable conclusions. In particular, the NeighborsMatch dataset would have been a suitable choice for demonstrating the effect of edge-dropping on model performance in long-range tasks. However, due to the synthetic nature of the dataset, such an experiment would only serve to establish the point that these methods limit a model’s capacity to learn long-range information. Indeed, Figures 1, 4 and 5 establish exactly that, since the model is unable to effectively propagate information over long distances.

As for the peptides datasets (we assume you are referring to the long-range graph benchmark [2]), the problem is that they are graph-level tasks. Specifically, regardless of whether the node representations are learnt as a function of distant nodes or not (i.e., whether over-squashing occurs), the prediction is made by mixing the information from all the nodes, making the effect of over-squashing on model performance hard to disentangle.

We chose the datasets in this work with the aim of highlighting a critical distinction in the results for homophilic and heterophilic datasets, which was suggested by the theory in Section 3. We did not see a similar intent in adding the suggested datasets, which is why we did not include it in our analysis. However, upon your suggestion, we will continue working on this study and add the results for the suggested datasets to the final version of this work; the large size of these datasets prevents us from presenting the results by the end of the rebuttal period.

The contribution of the paper is marginal. The mainstream of solving over-squashing is by graph rewiring or graph transformers. This paper addresses DropEdge and variants cannot solve over-squashing, that's fine, but empirically that is already true, and no one uses it for LRI.

Reviewer 3v8w remarked something similar as well. Kindly check our comment addressing these concerns together under the heading “significance of the work”. We refrain from including the case of graph transformers since it deviates from the common framework shared by the methods we study – regularizing models with stochastic message passing. We would like to emphasize that our goal was not to challenge the use of methods designed to alleviate over-squashing, but instead those that target over-smoothing, particularly citing their significantly limited evaluation on long-range tasks – the primary use-case of deep GNNs. Accordingly, we have also not included the graph rewiring methods you mentioned. Although, we do believe that a sensitivity analysis – similar to the one in our work – of methods targeting over-squashing can make it clearer whether the performance boost in real-world settings is due to improved long-range information propagation.

While it is true that DropEdge is not typically promoted for modeling LRIs, it is worth noting that no prior work explicitly discourages its use for long-range tasks either. Importantly, related graph rewiring methods aimed at alleviating over-squashing do not benchmark their performance against DropEdge (or variants) on long-range tasks. Despite this, DropEdge remains a widely used regularization method for MPNNs and training deep GNNs. We demonstrate that it is unsuitable for long-range tasks, which are the main use-case practitioners opt deeper GNNs for. This highlights an important gap in current evaluations and emphasizes the need for caution when applying such methods, as their effectiveness heavily depends on task requirements. The literature lacks such negative results, which are essential to assess the broader applicability of these techniques effectively.

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

[2] Vijay Prakash Dwivedi, Ladislav Rampášek, Mikhail Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. Long range graph benchmark. In Thirty-sixth Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2022.

Additionally, the paper does not discuss potential solutions; it only analyzes this phenomenon, which limits the contribution of the work.

Reviewer Z8L5 remarked something similar as well. Kindly check our comment addressing these concerns together under the heading “solution for the highlighted problem”, where we also describe how our theoretical analysis can be used to design a DropEdge variant with node-wise dropping probability set to minimize information loss during message-passing. While we do agree that evaluating such a method could strengthen our work, several methods have already been introduced to address this problem (see Appendix A.2 and A.3). Instead, our goal was to instead highlight the problem of limited evidence supporting the suitability of methods designed for alleviating over-smoothing in tackling long-range tasks – the primary use-case of deep GNNs.

The paper only discusses DropEdge and its variants. In fact, for graph random dropping methods, Dropout is the most commonly used, while DropMessage is the most advanced. The lack of exploration of such non-edge dropping methods significantly limits the applicability of this work.

Reviewer Z8L5 remarked something similar as well. Kindly check our comment addressing these concerns together under the heading “set of methods evaluated”. In particular, while we will not be able to include a theoretical analysis of Dropout, DropMessage and SkipNode by the end of the rebuttal period, we are working on adding the empirical results for them. We hope that would address your concern.

The experimental section of the paper is insufficient as it only includes a limited set of node classification tasks. Other downstream tasks, such as link prediction and graph classification, are missing experimental results.

In graph-level tasks, regardless of whether the node representations are learnt as a function of distant nodes or not (i.e., whether over-squashing occurs), the prediction is made by mixing the information from all the nodes, making the effect of over-squashing on model performance hard to disentangle. In other words, even if information fails to mix over distant nodes via message-passing, it may get mixed by the pooling layer.

The effect of a method on over-squashing can be expected to be closely related to link prediction tasks. However, we have not come across any long-range link prediction datasets; kindly let us know if we missed out on any.

We wish to emphasize that our goal is not to simply compare these methods across a range of datasets, but rather verify their suitability towards long-range tasks in particular. The effect of a method on over-squashing should be closely related to the model performance on long-range node-classification tasks, but that conclusion is hard to extend to other problem types, eg. graph-level tasks.

Thank you for your review! Kindly find our responses below to the weaknesses and questions raised.

I do not find the main experiments of the paper convincing. The authors categorize the experimental results in Table 2 into homophilic datasets and heterophilic datasets to verify that the experimental results align with the theoretical results. In fact, I think that the magnitude of the Spearman correlation values in Table 2 depends on the optimal dropping probability for that dataset, rather than the homogeneity of the dataset. In other homophilic datasets, such as PubMed and ogbn-arxiv, the optimal dropping probability is quite small, and I do not think the same conclusions as those in the paper can be reached.

Excellent remark! We do agree that the experiment setup is not flawless, and that if the optimal dropping probability, the correlation can be expected to be negative. In Figure 2a, we show that the test accuracy for Cora and CiteSeer monotonically increases with DropEdge probability. As for PubMed and obgn-arxiv, we will work the results for them right after we have the results for Dropout, DropMessage and SkipNode with the current set of datasets!

In the meantime, can we check which method has low optimal dropping probability for PubMed? We checked the DropEdge paper [1], and the optimal probabilities reported in Table 6 are quite high for PubMed – 0.3 for GCN, 0.7 for ResGCN, 0.5 for JKNet, 0.5 for IncepGCN, and 0.8 for GraphSage. In the GRAND (DropNode) paper [2], the optimal dropping probability reported is 0.5, with 0.6 dropout rate in the input layer and 0.8 in the hidden layers. As for DropAgg [3], the optimal dropping probabilities are not reported, and for DropGNN [4], they are only reported for synthetic datasets. Kindly let us know what we might have missed.

Regardless, the results reported in these papers usually correspond to the best performing models over multiple training runs. This is in contrast to our experimental design, where we use the average performance over multiple runs to compute the correlation statistics, effectively disregarding the variance in model performance under different dropping methods.

The conclusions described in Lemma 3.2 and Theorem 3.1 of the paper lack quantitative descriptions, which makes the conclusions less compelling.

Taking your feedback into account, we now direct the reader to the appendix for the quantitative results corresponding to Theorem 3.1. We have presented the quantitative results for Theorem 3.1 in the appendix due to limited space available in the main text. The exact quantitative statement would depend on the choice of dropping method, so we simply summarize the conclusion in the main text.

As for Lemma 3.2, it follows directly from the discussion after Lemma 3.1. Instead of restating the quantitative results, we chose to summarize the conclusion for brevity. The precise statement would depend on the choice of the algorithm used, so the reader may kindly refer to the preceding discussion for further details.

[1] Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. In International Conference on Learning Representations, 2020.

[2] 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 learning on graphs. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 22092–22103. Curran Associates, Inc., 2020.

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

[4] Pál András Papp, Karolis Martinkus, Lukas Faber, and Roger Wattenhofer. Dropgnn: Random dropouts increase the expressiveness of graph neural networks. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 21997–22009. Curran Associates, Inc., 2021.

Thank you for the author's patient responses. I have thoroughly read all the author's replies as well as the feedback from other reviewers. While the author has provided responses to most of the issues, many of them still require substantial experimental validation. Although the textual content shows potential directions for improvement, these have not been fully implemented yet. Therefore, I believe this paper still requires significant revisions. Additionally, in my opinion, a specialized version of DropMessage is likely the most feasible solution, and the author may consider delving deeper into this technique.

Thank you for your review! Kindly find our responses below to the weaknesses and questions raised.

While the paper identifies limitations of random edge-dropping methods—which are not specifically designed to address over-squashing—it lacks a proposed solution or guidance on mitigating over-squashing for these methods.

Reviewer biHW remarked something similar as well. Kindly check our comment addressing these concerns together under the heading “solution for the highlighted problem”, where we also describe how our theoretical analysis can be used to design a DropEdge variant with node-wise dropping probability set to minimize information loss during message-passing. In particular, while we do agree that proposing such a method would strengthen our work, several methods have already been introduced to address this problem (see Appendix A.2 and A.3). Instead, our goal was to highlight the problem of limited evidence supporting the suitability of methods designed for alleviating over-smoothing in tackling long-range tasks – the primary use-case of deep GNNs.

The choice of datasets could be improved. It may be beneficial for the authors to follow the experimental setup outlined in [1].

Reviewer Ku4N remarked something similar as well. Kindly check our comment addressing these concerns together under the heading “set of datasets used”. In particular, while we do appreciate the value of extensive evaluation on a variety of datasets, the size of the datasets used in [1], in addition to the short rebuttal period, we will unfortunately be unable to evaluate on the suggested datasets. However, we will continue working on this study and add the results for the suggested datasets to the final version of this work.

Some relevant works are omitted: (1) SkipNode [2], which selectively skips nodes at each layer, and (2) DropMessage [3], which introduces a generalizable framework for dropout-based techniques in GNNs.

Reviewer biHW remarked something similar as well. Kindly check our comment addressing these concerns together under the heading “set of methods evaluated”. In particular, while we will not be able to include a theoretical analysis of Dropout, DropMessage and SkipNode by the end of the rebuttal period, we are working on adding the empirical results for them. We hope that would address your concern.

The source codes and the used datasets should be provided to facilitate the reproducibility of this work. Please refer to https://anonymous.4open.science.

While we do acknowledge that the linked repository-anonymization tool is quite popular, we are wary of using it because of the extensive set of write permissions it requests to all public and private repository data. This includes the code, settings, webhooks and services, deploy keys and collaboration invites. We don’t see why such extensive access is necessary. If you have any suggestion for safely sharing the code, kindly let us know.

Please note that we will share the code as soon as the final scores are released, regardless of the outcome since this submission will be de-anonymized at that point anyway.

Thank you for your review! Kindly find our responses below to the weaknesses and questions raised.

I believe that the main weakness is that the core claim of the paper is not surprising. It is clear in general that removing edges will decrease the sensitivity.

Reviewer Ku4N remarked something similar as well. Kindly check our comment addressing these concerns together under the heading “significance of the work”. Notably, we found that edge-dropping can increase sensitivity between neighboring nodes, as shown in Figures 1, which is an unintuitive result in general. This empirical observation helps explain why deep GNNs perform well on short-range tasks with DropEdge, DropNode, DropGNN and DropAgg, despite the model-dataset misalignment – the reduced receptive fields guide the model to prioritize short-range signals, and prevent overfitting to the long-range ones.

We show that conclusions on the efficacy of edge-dropping methods in regularizing models may not be trivially extended to long-range tasks. The literature lacks such negative results which emphasize the need for practicing caution when employing these methods when training deep GNNs. Our hope is to draw attention to the evaluation of other methods designed for alleviating over-smoothing and training deep GNNs (see Appendix A.1) being limited to short-range tasks, where such deep models are arguably unnecessary. It is important to critically reassess these methods with a renewed focus on long-range tasks – the more relevant use case of deep GNNs.

In fact, the converse is a motivation for graph rewiring techniques — adding the smallest amount of edges to maximize the propagation of information.

We do agree that addition of edges has been shown to be necessary for alleviating over-squashing. The motivation for our work was to challenge the widespread adoption of Dropout and DropEdge for regularizing GNNs. We intended to establish that methods designed for alleviating over-smoothing have not been evaluated in a systematic manner, particularly on long-range tasks (understandably, because over-squashing was discovered more recently). Therefore, practitioners must exercise caution when adopting these methods for training deep GNNs. In the case of edge-dropping methods, this means ensuring that the ground-truth labels do not rely on long-range information propagation.

Could the authors comment on how the findings are different from works such as [1, 2] that already comment on the trade-off between over-squashing and over-smoothing, especially [2] connecting it to spectral quantities.

The focus of our work is not to provide new insights into the over-smoothing vs. over-squashing trade-off itself. In fact, we drew inspiration from these works and sought to address a critical, overlooked question: Given the known trade-off between over-smoothing and over-squashing, might methods designed to alleviate over-smoothing be unsuited for long-range tasks – the primary motivation for using deep GNNs? To that end, we investigate how dropping probability and node degrees impact over-squashing, and how such methods affect model performance in long-range tasks. While [1, 2] do predict that edge-dropping methods would exacerbate the over-squashing problem, we precisely characterize the dependence of this phenomenon on the dropping probability and the degree sequence of the network, and demonstrate the negative effects on performance in common real-world tasks.

[1] Khang Nguyen, Hieu Nong, Vinh Nguyen, Nhat Ho, Stanley Osher, and Tan Nguyen. Revisiting over-smoothing and over-squashing using ollivier-ricci curvature. In Proceedings of the 40th International Conference on Machine Learning, ICML’23. JMLR.org, 2023.

[2] Jhony H. Giraldo, Konstantinos Skianis, Thierry Bouwmans, and Fragkiskos D. Malliaros. On the trade-off between over-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 Computing Machinery.

Solution for the highlighted problem. Reviewers Z8L5 and biHW raise concerns about the lack of a proposed solution. In Section 3, we precisely characterize the dependence of sensitivity on the dropping probability and the degree sequence of the graph. Future works may exploit these relations to design new methods that systematically drop edges while limiting over-squashing levels. For example, one may design a DropEdge variant with node-wise dropping probability set to ensure that the message weight over each edge does not decrease by more than a preset threshold, say 0.9. We leave such an exploration for future works since extensive research is already aimed at addressing over-squashing using graph rewiring, and we wish to highlight a different problem.

While we do agree that proposing such a method would strengthen our work, several methods have already been introduced to address this problem (see Appendix A.2 and A.3). Instead, our goal was to highlight the problem of limited evidence supporting the suitability of methods designed for alleviating over-smoothing in tackling long-range tasks – the primary use-case of deep GNNs. The closest example to the methods we analyze is CurvDrop, which addresses the over-squashing problem by selectively dropping edges based on their curvatures. This prevalence of the problem we highlight can be seen in the evaluation of CurvDrop, which is limited to citation networks, a synthetic SBM dataset and the karate network – all short-range tasks.

Set of methods evaluated. Reviewers Z8L5 and biHW suggested adding methods like Dropout, DropMessage and SkipNode, which aim to tackle the problem of over-smoothing as well. We did recognize the relevance of these methods, but refrained from including them in order to maintain a focus on edge-dropping methods, which none of these methods are a type of. While we will not be able to include a theoretical analysis of these methods by the end of the rebuttal period, we are working on adding the empirical results for them.

Set of datasets used. Reviewers Z8L5 and Ku4N raise a concern about the limited set of datasets used for evaluation. We do agree that evaluation on more datasets is always desirable for making generalizable conclusions. We chose the datasets in this work with the aim of highlighting a critical distinction in the results for homophilic and heterophilic datasets, which was suggested by the theory in Section 3. We do see the value in testing the edge-dropping methods with the suggested large scale datasets, however since we perform 200 runs (10 dropping probabilities, 4 model depths, 5 runs each) for each model-datasets-dropout combination, we will be unable to present the results for these datasets by the end of the rebuttal period. However, we will continue working on this study and add the results for the suggested datasets to the final version of this work.