On information dropping and oversmoothing in graph neural networks

Dear Reviewer yTML

Thank you for your response and important feedback! We agree with you and realize that the original draft of our paper had major clarity issues, especially in sections 4.1 and 4.2, and the overall motivations and conclusions of the paper were not clearly explained. We have revised large portions of the paper to address the clarity issues.

I encountered challenges in comprehending certain sections of the paper, particularly sections 4.1 and 4.2. I believe the clarity of these sections could be significantly improved

We have made Section 4 clearer to read – in particular we have corrected notation that was inconsistent and convoluted (especially regarding the optimized representation / message matrix). The derivation there is standard in the literature and is not the main contribution of our work. We have made clearer references to the foundational works on the IB principle in neural networks. We hope this section is now more understandable.

The introduction, literature review and conclusion sections have been revised to make it clearer what the paper’s objectives and takeaways are. To clarify, we focus on investigating the effect of random dropping approaches on oversmoothing, and the degree to which oversmoothing is relevant to improving model performance in practice. Our proposal of Learn2Drop mainly serves to address the problems of using existing random dropping approaches at test time.

scenarios exist where the Normalized Dirichlet Energy may approach zero, yet the test accuracy remains high.

Your concerns on the use of Normalized Dirichlet energy (NDE) are valid and it is true that we did not motivate its use properly. Reviewer K9Rv had similar concerns. As such we have completely removed the use of normalized Dirichlet energy from the paper and have redone the experiments using both standard Dirichlet energy and MAD. We added a discussion on the benefits and pitfalls of using either metric in Section 3.1. The empirical results after switching to standard Dirichlet energy and MAD are very similar to our original results, and our conclusions remain the same. This suggests that the theoretical differences between each metric are not significant in practice, at least for our investigation.

Oversmoothing within the same class might not be as relevant

This is an interesting take and suggestion. The existing metrics of Dirichlet energy and MAD look indiscriminately at all node pairs (which are connected by an edge). It would be interesting to observe oversmoothing for only the pairs of nodes that are of different classes, since differentiating between nodes is what matters for classification accuracy. We did some additional experiments (for section 3.2) where we compute Dirichlet energy and MAD while only considering these pairs of nodes in different classes. The plots for those are placed in the Appendix. The overall results are highly similar to when comparing all pairs, although the absolute value of the smoothing differs. However, we are mostly concerned with the trend of this metric, rather than its absolute value.

My concerns extend to the topic of reproducibility.

We have tried to improve the reproducibility of our work by including model training and parameter selection details in a new experimental setup section in the Appendix.

We hope our revisions to the paper have addressed your concerns and would be grateful for any further comments or feedback.

Thank you,

The authors.

I've reviewed the responses from both other reviewers and your comments. I recognize the potential in this work, but it's still in the early stages, with the paper's narrative having shifted, raising additional unanswered questions. It's important to note that reducing oversmoothing doesn't always directly lead to performance enhancements, a point known in the community.

To strengthen the paper, consider these suggestions:

1. Identify instances where simple methods like dropedge contribute to performance improvement, regardless of oversmoothing considerations.
2. Examine cases where such simple methods prove ineffective, outlining reasons for their failure or proposing alternative approaches.
3. Conclude the paper by exploring when reducing oversmoothing correlates with performance enhancements and when it does not.

Focusing on these aspects could enhance the paper's impact. I would encourage the authors to pursue some of these directions and submit to the next conference, considering the fact that the rebuttal process is coming to a close, soon.

Dear Reviewer K9Rv,

We thank you for your response and important feedback. We are glad you have pointed out the issues and inconsistencies you found. We have made many changes to the paper in response to your feedback.

Please improve literature review.

We have revised our literature review of oversmoothing. This has been placed in Section 2.2. Thank you for mentioning the paper by Keriven (2022). Indeed there has been recent work that has tried to analyze the relationship between oversmoothing and generalization from a theoretical perspective. Our work is a contribution from an empirical perspective. One of our conclusions is that oversmoothing is not strictly related to model performance in practice, and minimizing oversmoothing by itself can be undesirable. For example, applying random dropping on the message matrix at test time will reduce oversmoothing according to both MAD and Dirichlet energy – however this does not result in a useful model. We believe that this challenges the prior ‘consensus’ in the literature that oversmoothing reduction is desirable, giving new insights from an empirical perspective, and also aligns with the theory work by Kerivan (2022) that the truth is simply ‘reducing oversmoothing is always better’.

NDE is not a good metric to measure oversmoothing due to at least the three following issues:

We have removed the normalized Dirichlet energy (NDE) from the paper, and have redone our experiments using both standard Dirichlet energy (DE) and mean average distance (MAD).

• In Section 3.1 we have added a clearer explanation of the advantages and drawbacks of each metric. The figures in our paper have also been updated to reflect this. The empirical results on oversmoothing analysis are actually very similar between DE, MAD (and NDE), and the conclusions of our paper remain the same.
• We note that while the issues faced by MAD (and NDE) are problematic for a theoretical analysis, for our experiments they don’t seem to create a noticeable difference in practice. Our main use case of these metrics is to compare the relative amount of oversmoothing between different GNNs, which is possible with MAD as it exhibits layerwise exponential convergence for high dimensional node representations. While DE has the theoretically sound property that complete smoothing is equivalent to 0, in practice this does not make a significant difference to our empirical observations.

Although the authors argue that random dropping methods could introduce too much noise during test, the paper does not provide empirical evidence

• We have now included them in Table 1 the results for using DropEdge and DropMessage at test time – we apologize for forgetting to include them in the original submission. We have also taken reviewer yTML’s advice to average the inference results over multiple passes to make this baseline stronger.

seems a GNN with skip connections are perfect remedies for oversmoothing

GNN+skip connection are now in Figures 1, 3 and 4. It certainly does appear like the ‘perfect remedy’ for oversmoothing like you’ve pointed out – according to both Dirichlet energy and MAD in fact. This is also the case with enabling DropMessage at test time. What this suggests is that while certain methods that perform well are correlated with having lower oversmoothing, it is questionable whether we can justify one model as being better than another by solely using the oversmoothing reduction as our deciding factor. In the case of simply applying DropMessage at test time, this reduces oversmoothing while being detrimental to model performance. In the recent survey by Rush et al (2023), we can see similar results, in which methods such as PairNorm are highly effective in limiting oversmoothing but are outperformed by many other methods. Rusch et al interpret this as the result of some models sacrificing expressive power to reduce oversmoothing. However, we propose the new perspective that a model which improves performance may not be strictly related to oversmoothing at all – for instance, DropEdge and DropMessage mainly improve performance by providing a data augmentation effect that benefits training.

Finally, the overall objective of our work wasn’t clearly explained in the original submission. Our main contribution is investigating the effect of random dropping approaches on smoothing, rather than trying to propose a superior method of solving oversmoothing. We’ve revised the abstract, the introduction and conclusion to address this.

Thank you for taking the time to provide us with valuable feedback – we hope you can take a look at our revisions and we would be grateful to hear further comments on areas that can be improved.

Thank you,

The authors.

Dear Reviewer K9Rv,

We would like to kindly request your feedback on the revisions made to our paper -- we have thoroughly addressed the concerns raised in your initial review and made significant changes to the paper.

We would greatly appreciate any additional comments or suggestions you may have before the end of the rebuttal period. We understand the time constraints and appreciate your consideration in providing timely feedback.

Thank you for your valuable contribution to improving our work.

Sincerely,

The authors

Dear Reviewer xrXy,

Thank you for taking the time to provide us with feedback and suggestions. We agree with your comments – oversmoothing is a challenging phenomenon to evaluate. Its relationship with model performance is not as straightforward as one might think – as suggested by our findings. There are many instances where doing simple yet unhelpful things – such as dropping messages at inference time – will apparently solve oversmoothing but fail to improve actual performance. There are also other cases such as with DropEdge, where it may be easy to believe that performance improvement comes from oversmoothing reduction, but in reality may come from elsewhere.

Use perhaps more than one metric to evaluate oversmoothing.

We have taken your suggestion of using two different metrics of evaluating oversmoothing – we removed the use of normalized Dirichlet energy due to many concerns pointed out by the other reviewers, and now all our experiments are conducted using both the standard Dirichlet energy, as well as MAD. While Dirichlet energy has some good theoretical properties, MAD is also commonly used in the literature and less sensitive to arbitrary scaling of the embeddings. Both metrics lead to similar conclusions – in particular, the analysis of the layer-wise exponential smoothing in section 5.1 is almost identical between Dirichlet energy and MAD. The similarity in the conclusions drawn from both metrics reinforces the soundness of our approach.

However, the variance can be reduced with multiple forward passes, each with a different realization of DropMessage.

This is a useful suggestion and would serve as a much better baseline than simply applying random dropping at test time. We have modified the table of accuracies in the results section so that the results for DropEdge and DropMessage at test time are done by averaging the model prediction over 10 inference passes. We do witness a small reduction in variance, but the overall results are still poor. Effectively we are averaging over more inference passes and the mean test accuracies are still low. We believe that this provides a more robust comparison and strengthens the validity of our findings.

We highly appreciate your insightful feedback and suggestions – we will be grateful for any further comments.

Thank you,

The authors.

Dear Reviewer xrXy,

We would like to kindly request your feedback on the revisions made to our paper -- we have thoroughly addressed the concerns raised in your initial review and made significant changes to the paper.

We would greatly appreciate any additional comments or suggestions you may have before the end of the rebuttal period. We understand the time constraints and appreciate your consideration in providing timely feedback.

Thank you for your valuable contribution to improving our work.

Sincerely,

The authors

Dear Reviewer nv43,

We thank you for your response and important feedback! You highlighted an important point - on the comparison of our Learn2Drop with the latest existing approaches for addressing oversmoothing. We would first like to mention that in the original paper, the main motivation of our work wasn’t clearly addressed and it was misleading. We admittedly overemphasized the significance of ‘reducing oversmoothing’ and would like to highlight that the main novelty of our work is an empirical study and critical look of whether oversmoothing is actually relevant in practice for dropping methods, rather than finding the best way to minimize it.

The writings of the paper can also be improved.

We have made significant changes to many sections of the paper to make its meaning clearer. In particular, the introduction and conclusion sections have been revised to clarify our contributions**. In summary,

• Our primary contribution is analyzing whether random dropping approaches have an effect on oversmoothing, which we show to be not necessarily true since the methods are applied only during training. This suggests that DropEdge for instance, is fundamentally more of a data augmentation tool.
• We observe that simply dropping random message elements at test time will result in significant oversmoothing reduction, but translates to poor test accuracy. This suggests that minimizing oversmoothing is not necessarily useful.
• Learn2Drop was motivated by the question of whether we can perform this random dropping at test time in a more informed manner. We don’t aim to beat existing oversmoothing reduction approaches, but rather focus on bringing the potential benefits of existing random dropping methods to test time. Although we observe that Learn2Drop achieves oversmoothing reduction, this doesn’t prove that reducing oversmoothing is strictly the reason why it performs better. It is possible that Learn2Drop’s oversmoothing reduction is just a side effect and not the main reason it performs better. This is what we believe is happening for DropEdge. Learn2Drop serves more as a way to give us insight into the relationship between oversmoothing and model performance, as opposed to solely focusing on reducing oversmoothing.

First, in addition to DropEdge and DropMessage, there are other methods that aim to address the oversmoothing issue. The authors may consider to compare with them.

Following your advice, to make our results more informed, we have added the recent method GraphCon proposed by Rusch (2022) which we treat as a ‘complex’ method of addressing oversmoothing. This is added into Table 1. Although both our approach and GraphCon can effectively prevent the layer-wise exponential behavior of smoothing, there is a still a performance gap between ‘optimally dropping at test time using Learn2Drop’ and GraphCon, which further suggests that it is important to see that oversmoothing is perhaps not the only factor when it comes to making a GNN more accurate. However, an important point is that creating a method that outperforms state of the art methods for reducing oversmoothing is not the purpose / goal of this work, and we don’t expect our approach to result in better accuracy than those methods.

The authors claim that DropMessage at testing time may introduce a high amount of variance in the model predictions.

We apologize for not having included these results in the original paper – we have also added results into Table 1 showing the performance of models when applying DropEdge and DropMessage at test time. These results are obtained by averaging multiple inference passes to make it a stronger baseline, as suggested by reviewer yTML.. The results are poor and inconsistent, which is likely why the methods were originally proposed to only be used during training.

Why use Dirichlet energy instead of mean average distance?

The main reason for using Dirichlet energy is that it holds the convenient theoretical property that 0 energy is equivalent to complete oversmoothing (all node representations being identical). However, for our empirical comparisons this property does not make a noticeable difference compared to just using MAD. As other reviewers had concerns about the use of normalized Dirichlet energy, we have removed its use from the paper. Our results were rerun while using standard Dirichlet energy and MAD.

What does DO mean in Table 1?

That refers to the Dropout method. We have edited that column of the table to make the names clearer.

We hope our revisions to the paper have addressed your concerns and look forward to hearing your thoughts on them.

Thank you,

The authors.

Dear Reviewer nv43,

We would like to kindly request your feedback on the revisions made to our paper -- we have thoroughly addressed the concerns raised in your initial review and made significant changes to the paper.

We would greatly appreciate any additional comments or suggestions you may have before the end of the rebuttal period. We understand the time constraints and appreciate your consideration in providing timely feedback.

Thank you for your valuable contribution to improving our work.

Sincerely,

The authors