Demystifying Oversmoothing in Attention-Based Graph Neural Networks

Summary

The authors provide theoretical proofs on the oversmoothing problem in GCNs and GATs through Ergodicity analysis of infinite product of matrices. The authors provide a bound in convergence of oversmoothing problem and provides suggestions on choices in activation function to relief oversmoothing problem.

Strengths

- Approaching oversmoothing problem with Ergodicity is fairly new - Implications on choices of activation functions are straight forward - The article is very easy to follow

Weaknesses

- It would be better if the authors could add a experiment with a plot directly showing JSR

Questions

- If we break the assumption A4 by using a $\sigma(x)/x >1$, or $\sigma(0)\neq 0$, does GNNs stop having oversmoothing issues or will there be other problems?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

3 good

Contribution

4 excellent

Limitations

N/A

Summary

The objective of this paper is to examine the occurrence of over-smoothing phenomena in attention-based Graph Neural Networks (GNN). Over-smoothing refers to a situation where deepening the network results in similar node representations. The researchers demonstrate the presence of over-smoothing in attention-based GNNs using a versatile methodology that can be applied to various GNN types. They establish this proof by treating the network as a nonlinear and time-varying dynamical system. Moreover, the authors support their assertions with empirical evidence.

Strengths

* The paper exhibits excellent writing quality, as it effectively communicates the author's intentions even when dealing with complex mathematical concepts. The clarity of the paper makes it easily comprehensible for readers. * The theoretical claims are clear and the proofs are valid. * The authors propose a generic approach to examine over-smoothing in GNNs with non-restrictive conditions. While their main focus is on attention-based models, the results include a wider range of models.

Weaknesses

* The main shortcoming of the paper is the lack of suggestions for solving the over-smoothing problem. [1] suggests scaling to avoid the phenomena, are they any other ways to alleviate the problem? [1] Oono et al. Graph Neural Networks Exponentially Lose Expressive Power for Node Classification, ICLR (2020)

Questions

* Is it possible to extend the over-smoothing to any node similarity measure as defined in Definition 1 ? * Is it possible to directly expand the results from the paper to transformer-based GNNs? What is possible to say about the existence of over-smoothing in that case?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

There is no evidence of ethical problems with this submission.

Summary

This paper provides a definitive answer to the question that whether the graph attention mechanism can mitigate over-smoothing through a rigorous mathematical analysis. The theoretical results establish that the graph attention mechanism cannot prevent over-smoothing and loses expressive power exponentially.

Strengths

S1. Exploring theoretical results on the performance of attention-based GNNs on over-smoothing problems is meaningful and challenging. S2. The theoretical results obtained in this paper can provide some instructive and valuable information on over-smoothing research.

Weaknesses

Reliability 1. The reliability of the motivation can be enhanced by adding more literature that discusses the controversy surrounding whether attention-based GNNs alleviate the over-smoothing problem. Significance 1. Only homophily graphs are considered in the paper. In addition, heterophily datasets also should be considered to verify the overall performance of GNN as pointed out by recent publications [1,2]. 2. In addition, experiments on larger datasets will strengthen the significance of the contributions. [1]Pei, H., Wei, B., Chang, K. C. C., Lei, Y., & Yang, B. (2020). Geom-GCN: Geometric graph convolutional networks. In ICLR. [2]Lim, D., Hohne, F., Li, X., Huang, S. L., Gupta, V., Bhalerao, O., & Lim, S. N. (2021). Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods. In NeurIPS, 34, 20887-20902.

Questions

1.Missing a number of reliable literature support the claim of attention-based GNNs' ability to alleviate the over-smoothing problem, and most of the works listed in this paper suggest that attention-based GNNs suffer from over-smoothing. This is insufficient to support the author's argument that there is controversial whether the graph attention mechanism can mitigate over-smoothing. 2.What criteria were used to select the negative slope values in the experiment? 3.How sensitive are the hyperparameters (e.g. negative slope values) to the performance?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

N/A

Summary

The paper addresses the question of whether graph attention mechanism could prevent oversmoothing in Graph Neural Networks (GNN) and provides a negative result. Existing results on graph attention are available for 1-layer GNN. The current work analyzes the general case of multi-layered graph attention in the context of nonlinear, time-varying dynamical systems. Through a nicely presented rigorous theoretical analysis, the paper shows that (1) oversmoothing happens even for multi-layered attention based GNN (hence attention based mechanisms fundamentally does not change the aggregator operator) (2) oversmoothing happens at exponential rate and the analysis can be also generalized to GCNs. The numerical experiments demonstrate the validation of the claims made in the paper. The presented analysis could be useful in understanding other aspects of graph attention.

Strengths

1. The paper addresses an important question of oversmoothing in multi-layered graph attention neural networks. It is very well written and the ideas across different sections are nicely connected. There is ample amount of intuition behind choice of various techniques used in the paper and the theorems/lemmas are well explained. 2. The ideas/techniques introduced in the paper are well developed, original and should be useful in understanding other aspects of attention based GNNs. I like that the authors provide remarks (lines 257) which address how the paper differs from previous techniques used in theoretical analysis of graph attention. 3. The results of the paper are of significance in understanding of GNNs in terms of developing an understanding of trajectory of matrices in graph attention and hence indirectly supporting methods like edge-dropping etc.

Weaknesses

1. Some of the prior work on reducing oversmoothing [1] and impact of the current work for understanding them could be included as limitation for the current work. It would be great if authors could talk about if some of the techniques developed here applies to them. [1] Chen, Deli, et al. "Measuring and relieving the over-smoothing problem for graph neural networks from the topological view." Proceedings of the AAAI conference on artificial intelligence. Vol. 34. No. 04. 2020.

Questions

Q1. Typo: The sub-indices for $W^{(k)}$ in recursive formulation of *Eq (6)* is flipped and should be - $j_k, j_{k+1}$ instead of $j_{k+1}, j_k$. This would match those in *Eq 5* case $W_{ji}^{(t)}$ for $j_{k+1}=i$. Same goes for the supplement. Please check that the proof that The proof the follows is alright. Q2. In lines $286.287$, how is the existence of $q<1$ justified? I understand that this is an assumption in the *Theorem 1*, but could the authors shed light on nature of values $q$ takes since it dictates the convergence.

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

None

Thank you for the rebuttal

The response from the authors addresses my questions.