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

Authors: Jasraj Singh, Keyue Jiang, Brooks Paige, Laura Toni
Primary area: learning on graphs and other geometries & topologies
Keywords: Graph Neural Networks, Over-squashing, DropEdge

Abstract:
Message Passing Neural Networks (MPNNs) are a class of Graph Neural Networks (GNNs) that leverage the graph topology to propagate messages across increasingly larger neighborhoods. The message-passing scheme leads to two distinct challenges: over-smoothing and over-squashing. While several algorithms, e.g. DropEdge and its variants – DropNode, DropAgg and DropGNN – have successfully addressed the over-smoothing problem, 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. In this work, we take the first step towards closing this gap by studying the aforementioned algorithms in the context of over-squashing. We present novel theoretical results that characterize the negative effects of DropEdge on sensitivity between distant nodes, suggesting its unsuitability for long-range tasks. Our findings are easily extended to its variants, allowing us to build a comprehensive understanding of how they affect over squashing. We evaluate these methods using real-world datasets, demonstrating their detrimental effects. Specifically, we show that while DropEdge-variants improve test-time performance in short-range tasks, they deteriorate performance in long-range ones. Our theory explains these results as follows: random edge-dropping lowers the effective receptive field of GNNs, which although beneficial for short-range tasks, misaligns the models on long-range ones. This forces the models to overfit to short-range artefacts in the training set, resulting in poor generalization. Our conclusions highlight the need to re-evaluate various methods designed for training deep GNNs, with a renewed focus on modelling long-range interactions.

Decision: reject
Reviewer scores: 6, 5, 5, 5

Reviews and discussion:
<thread>
creation date:
1729254424438

thread_type:
official_review

<thread_object>
creator: reviewer_ku4n

<content>
summary:
This paper investigates the effects of DropEdge and other variants on over-squashing problem, by calculating the sensitivity theoretically and emperically.

strengths:
- The motivation is quite clear and solid. 
- Overall the writing is pretty good and understandable.
- The paper's logic is sound, and the assumptions are reasonable. 
- The empirical study on sensitivity is well-designed and makes great sense.
- The experiments on real world datasets align well with the theory and intuition.

weaknesses:
- The proof in appendix A1 is not quite clear. Maybe explain more.
- There are some datasets on long range interaction (LRI) and over-squashing, say trees match and peptides datasets. They are missing from the experiments. 
- 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.

questions:
See weakness. Can you explain more the derivation in A1?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730104606320

thread_type:
official_review

<thread_object>
creator: reviewer_bihw

<content>
summary:
The paper investigates the effects of random edge-dropping algorithms, such as DropEdge and its variants (DropNode, DropAgg, and DropGNN), on over-squashing in MPNNs. Over-squashing occurs when information from exponentially growing neighborhoods is compressed into finite-sized node representations, limiting the ability to capture long-range interactions.

strengths:
1. This paper is well written and easy to follow.
2. The paper provides a comprehensive analysis of different types of MPNNs.

weaknesses:
1. 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.
2. The conclusions described in Lemma 3.2 and Theorem 3.1 of the paper lack quantitative descriptions, which makes the conclusions less compelling. Additionally, the paper does not discuss potential solutions; it only analyzes this phenomenon, which limits the contribution of the work.
3. The paper only discusses DropEdge and its variants. In fact, for graph random dropping methods, Dropout [1,2] is the most commonly used, while DropMessage [3,4] is the most advanced. The lack of exploration of such non-edge dropping methods significantly limits the applicability of this work.
4. 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.


[1] Improving neural networks by preventing co-adaptation of feature detectors.

[2] Dropout: a simple way to prevent neural networks from overfitting

[3] Dropmessage: Unifying Random Dropping for Graph Neural Networks

[4] Unifying Graph Contrastive Learning via Graph Message Augmentation

questions:
Please refer to the points I mentioned in the weakness section.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730188079875

thread_type:
official_review

<thread_object>
creator: reviewer_z8l5

<content>
summary:
This paper investigates the impact of random edge-dropping techniques on the issue of over-squashing in GNNs, specifically in the context of message-passing neural networks (MPNNs). While previous studies have explored edge-dropping methods to address over-smoothing, this paper highlights that these methods can exacerbate over-squashing, thus hindering GNNs’ performance on long-range tasks. Through theoretical analysis and empirical validation, the authors demonstrate that edge-dropping methods reduce the sensitivity of distant nodes to each other, leading to limited message-passing across long distances. The results suggest that while random edge-dropping methods like DropEdge improve performance in short-range tasks, they deteriorate performance in long-range tasks due to overfitting to local structures.

strengths:
- This work provides a fresh perspective by focusing on over-squashing, a less-explored limitation of edge-dropping techniques in GNNs

- The paper presents a comprehensive theoretical framework, supported by experiments that confirm the detrimental impact of edge-dropping on long-range node interactions.

- The paper provides clear explanations showing how random edge-dropping improves accuracy in short-range tasks but worsens performance in long-range tasks.

weaknesses:
- 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.

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

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

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


Refs:

[1] On the bottleneck of graph neural networks and its practical implications.

[2] SkipNode: On alleviating performance degradation for deep graph convolutional networks

[3] Dropmessage: Unifying random dropping for graph neural networks

questions:
Please see the weaknesses listed above.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730373239359

thread_type:
official_review

<thread_object>
creator: reviewer_3v8w

<content>
summary:
The paper studies the effect that randomly dropping edges (in different ways) has on over-squashing and more broadly on the propagation of information. The conclusion is that techniques like DropEdge have a negative effect on the sensitivity between distant nodes, but possibly a positive effect on closer nodes. This is shown both mathematically and through experiments.

strengths:
The paper is well presented and well written. There is a good amount of literature review and context provided as well. The authors study different scenarios and overall provide a pretty detailed mathematical understanding of the topic they wish to study.

weaknesses:
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. In fact, the converse is a motivation for graph rewiring techniques — adding the smallest amount of edges to maximise the propagation of information. 

From another point of view, I believe that this trade-off is clear also when contrasting over-squashing and over-smoothing. A large spectral gap means better sensitivity, but also means more smoothing. For this reason,  removing edges (which will likely lower the spectral gap) will have the effect of combatting over-smoothing, by reducing the connectivity (meaning global sensitivity is lowered). 

I do believe that the work is well-written and quite thorough. For this reason I do not wish to be overly negative in my initial scoring, although I would need to be convinced during the rebuttal phase on the strength of the contribution. 

It is also worth pointing out that there already are a number of works [e.g. 1, 2] that link the trade offs between over-smoothing to over-squashing.

[1] Revisiting Over-smoothing and Over-squashing Using Ollivier-Ricci Curvature. ICML 2023
[2] On the Trade-off between Over-smoothing and Over-squashing in Deep Graph Neural Networks. CIKM 2023

questions:
Related to the weakness, I would appreciate if the authors could comment on why they believe the main claim to be a surprise to readers working in related areas? 

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 (see my comment in the weaknesses section above on  spectral gaps).

[1] Revisiting Over-smoothing and Over-squashing Using Ollivier-Ricci Curvature. ICML 2023
[2] On the Trade-off between Over-smoothing and Over-squashing in Deep Graph Neural Networks. CIKM 2023
</content>
</thread_object>

</thread>
<thread>
creation date:
1732204543668

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Common Response to the Reviewers' Feedback

comment:
We sincerely appreciate the feedback from the reviewers. We will use this response to address some of the shared concerns.

**Significance of the work**. Reviewers 3v8w and Ku4N mention that it is not surprising for random edge-dropping methods to exacerbate the over-squashing problem, and that they are not promoted for long-range tasks. While we do agree that it might be intuitive for such methods to reduce sensitivity between distant nodes, our work theoretically characterizes the precise dependence of this decay on dropping probability and the degree distribution of the graph. We believe that such a precise characterization can guide the design of dropping methods that keep over-squashing in check. 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. The aim of our work was *not* to simply present results for edge-dropping methods, but rather to draw attention to the limited evaluation protocol employed for a suite of algorithms designed for training deep GNNs. The focus has largely been limited to short-range tasks like citation networks (eg. Cora, CiteSeer, PubMed), recommendation networks (eg. ogbn-products) and social networks (eg. karate, Reddit). However, the primary use-case of deep GNNs is in long-range tasks, and trainability on short-range tasks is of little significance. 

A trade-off between over-smoothing and over-squashing has been established in the literature, especially when using graph rewiring techniques (see Appendix A.3). Our work draws inspiration from these results 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?* We demonstrate the prevalence of this problem through poor test-time performance of methods designed for training deep GNNs in common tasks involving heterophilic networks. 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.

Our hope is to draw attention to the importance of critically assessing similar methods, such as normalization techniques and residual connections (see Appendix A.1). Understanding their effects on over-squashing and long-range tasks &ndash; the more relevant use case of deep GNNs &ndash; is essential for assessing their broader applicability. Some other methods designed for alleviating over-smoothing, eg. NodeNorm [1] and PairNorm [2], might not come at the cost of higher over-squashing levels. For long-range tasks, practitioners must seek such techniques instead of popular choices like Dropout or DropEdge.

Finally, our analysis is also expected to inspire a study on other graph rewiring methods, including those introduced for alleviating over-squashing (see Appendix A.2 and A.3), eg. CurvDrop [3] and BORF [4]. While theoretically motivated, a sensitivity analysis of these methods remains largely lacking, which makes it unclear whether the performance boost in real-world settings is indeed due to improved long-range information propagation, as intended, or perhaps something else.

[1] Kuangqi Zhou, Yanfei Dong, Kaixin Wang, Wee Sun Lee, Bryan Hooi, Huan Xu, and Jiashi Feng. Understanding and resolving performance degradation in deep graph convolutional networks. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pp. 2728&ndash;2737, 2021b.

[2] Lingxiao Zhao and Leman Akoglu. Pairnorm: Tackling oversmoothing in gnns. In International Conference on Learning Representations, 2020.

[3] 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 Web Conference 2023, WWW ’23, pp. 221&ndash;230, New York, NY, USA, 2023. Association for Computing Machinery.

[4] 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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732563438999

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Additional Results

comment:
**Updates to the Manuscript** 

1. We mistakenly characterized the decay rate of sensitivity as super-exponential, when it is actually polynomial. We have fixed this in the manuscript. 

2. We have added some additional explanation for the proof of Lemma 3.2 upon the suggestion of reviewer Ku4N. 

3. We have added a related works section in the appendix. Appendix A.1 discusses the over-smoothing methods that we believe can benefit from further evaluation, especially with an emphasis on long-range tasks. Appendix A.2 discusses methods designed for alleviating over-squashing, and Appendix A.3 discusses the trade-off between over-smoothing and over-squashing, as well as the methods designed to tackle the two problem simultaneously. 

**Additional Results** (not in the manuscript) 

1. We evaluated Dropout, DropMessage and SkipNode, following a similar protocol as in Section 4. The results presented below corroborate our findings about stochastic dropping methods: 
| Method | GNN | Cora | CiteSeer | Chameleon | TwitchDE | Squirrel | 
| ------ | --- | ---- | -------- | -------- | -------- | -------- | 
| Dropout | GCN | +0.034 | -0.309 | -0.610 | -0.465 | -0.300 | 
| Dropout | GAT | +0.120 | -0.110 | -0.836 | -0.545 | -0.397 | 
| DropMessage | GCN | -0.220 | -0.607 | -0.404 | -0.364 | -0.199 | 
| DropMessage | GAT | +0.028 | -0.368 | -0.530 | -0.697 | -0.148 | 
| SkipNode | GCN | +0.161 | +0.017 | -0.528 | -0.285 | -0.244 | 
| SkipNode | GAT | +0.403 | +0.466 | -0.436 | +0.248 | +0.278 | 

2. We also expect residual connections (ResGCN) to be similarly unsuited for long-range tasks, not by reducing the strength of signal over long distances, but rather by amplifying the strength of short-range signals (cf. influence distribution [1]). We present the empirical influence distribution of a 6-layer ResGCN, computed for the Cora network, [here](https://drive.google.com/file/d/1B8i2HB-5Zkq4TbHJ8mdT_dC1g5VpY2LW/view?usp=sharing) (shared using a throw-away account). Here, we can clearly see that residual connections significantly reduce the influence of distant nodes on final representations, and can thus be expected to be unsuitable for long-range tasks.

[1] Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 5453–5462. PMLR, 07 2018.
</content>
</thread_object>

</thread>


Metareview:
metareview:
**(a) Scientific Claims and Findings:**
The paper investigates the impact of random edge-dropping techniques, such as DropEdge, on the over-squashing phenomenon in Graph Neural Networks (GNNs). While these methods have been effective in mitigating over-smoothing and facilitating the training of deep GNNs, their influence on over-squashing has remained unexplored. The authors present theoretical analyses demonstrating that random edge-dropping exacerbates over-squashing, thereby degrading model performance on tasks requiring long-range dependencies. Empirical evaluations on real-world datasets corroborate these findings, showing that although DropEdge variants enhance performance in short-range tasks, they deteriorate performance in long-range tasks. The study concludes that random edge-dropping reduces the effective receptive field of GNNs, which, while beneficial for short-range tasks, misaligns models for long-range interactions, leading to overfitting to short-range artifacts in the training data and poor generalization.

**(b) Strengths:**
* Theoretical Insight: The paper provides a theoretical framework that elucidates the negative impact of random edge-dropping on over-squashing in GNNs.
* Empirical Evaluation: The authors conduct extensive experiments on five real-world (relatively small-scale) datasets, offering empirical evidence that supports their theoretical claims and highlighting the practical implications of their findings.
* Critical Re-evaluation of Existing Methods: The study prompts a reassessment of widely adopted techniques like DropEdge and its variants, especially concerning their suitability for tasks involving long-range dependencies.

**(c) Weaknesses:**
* Novelty of insight: It is well known and intuitive that dropping edges increases over-squashing (as also noted by Reviewers 3v8w and Ku4N). The authors argue that they provide a precise characterisation of the effect of randomly dropping edges. However, they analyse the effect on a proxy measure that has been related to over-squashing (i.e. sensitivity) and not the generalization performance of GNNs. Furthermore, the quantification is limited to linear GCNs.
* Lack of Proposed Solutions (Minor): While the paper identifies and analyzes the problem of exacerbated over-squashing due to random edge-dropping, it does not propose alternative methods or solutions to address this issue, leaving the reader without guidance on how to mitigate the identified problem. Y
* Limited Scope of Analysis: The focus is primarily on random edge-dropping techniques; the paper does not explore other potential factors contributing to over-squashing or consider a broader range of methods that might alleviate this issue. Even though the main story evolves on over-squashing and long range tasks, the studied datasets are mostly small scale and not related to this issue.
* Limited Scope of Theory: The theory is limited to linear GCNs and average effects on sensitivity. It does not really quantify the scale of the problem.
* Absence of Practical Recommendations: The study highlights the detrimental effects of certain techniques but falls short of providing actionable recommendations for practitioners seeking to balance the trade-offs between over-smoothing and over-squashing in GNNs.

**(d) Reasons for Rejection:**
After careful consideration, the decision to reject the paper is based on the following reasons:
1. Narrow Focus Without Broader Context: While the analysis of random edge-dropping is interesting and thorough, the paper does not situate its findings within a broader context of GNN training challenges, potentially limiting its relevance to a wider audience. The theoretical insight is relatively well known and, considering this fact, the theoretical quantification of the random edge dropping effect not sufficiently realistic, to create a high enough impact. The experiments cannot compensate for the limitation of the theory, as they do quantify the detrimental effect on a wide range of tasks, disentangling the potentially positive effect of over-smoothing  from the detrimental effect of over-squashing.
Addressing these concerns by proposing mitigation strategies, offering practical guidance, or situating the findings within a broader context would enhance the paper's contribution and its potential for acceptance in future submissions.
Alternatively, the authors have posed an interesting question during the rebuttal: “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?”
It’s more general analysis looking at a wide range of different methods supporting their hypothesis could also be of merit, but it would require a more comprehensive study  of different approaches.