Graph Neural Networks Do Not Always Oversmooth

Summary

This paper studies the over-smoothing effect in Graph Convolution Networks in the infinite width limit using their Gaussian processes equivalence. The authors generalize the concept of deep information propagation to GCNs and identify the similarity between ordered and chaotic phases in deep neural networks to over-smoothing and non over-smoothing regimes in GCNs. Using this, they show that initializing weights with large variance is sufficient to escape over-smoothing in GCNs.

Strengths

1. The theory of using deep information propagation to graphs is novel and interesting. Although many works studied over-smoothing in GNNs, this paper analyzes it from a new perspective resulting in interesting findings. 2. The paper is well written and structured. I appreciate the authors discussed the implications and limitations of their work in detail.

Weaknesses

1. The analysis is done using column shift stochastic shift operator, but in practice, GCNs are usually constructed with degree normalized adjacencies such as $D^{-1/2}AD^{-1/2}$ or $D^{-1}A$. I wonder if the results would translate in this case as well. The authors have discussed this in the limitations, perhaps giving empirical evidence using CSBM could help counter this weakness. 2. The theoretical analysis is in infinite width limit so it may not hold well in the finite width setting. But in my opinion this is not a critical weakness of the paper as the analysis in finite width is more challenging.

Questions

Please refer to the Weaknesses for major comments and minor ones are listed below. 1. To strengthen the paper further, I suggest the authors evaluate their findings on at least one real graph data like Cora or Citeseer. I understand the computational difficulties, and to tackle it, one can consider a small labeled set. 2. Would the result extend to other graph neural networks like GAT too? 2. What is the significance of considering $\epsilon$ noise in $Y$ (eq. 2)?

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

Limitations are already discussed in the paper which I list below. I don't see any other additional limitations. 1. The analysis is in infinite width limit. 2. The considered shift operator is different from the one usually used in practice. 3. Computational disadvantages in determining the variance of weights.

Summary

The paper investigates whether oversmoothing in GNNs is avoidable in theory. It investigates why oversmoothing occurs and derives an affirmative answer. In particular, depending on the variance of the initial weight matrices, GNNs can either enter a "regular" (oversmoothing) or "chaotic" phase (non-oversmoothing). These theoretical findings are confirmed by experiments on small-scale synthetic graphs.

Strengths

- The work focuses on a fundamental problem in GNNs, which is introduced and motivated well. - The background is concise yet easy to follow. - The paper questions the establishing belief that oversmoothing is inevitable, making this work highly significant. - The experiments are insightful and presented well. - The approach is original, and the presentation is clearly written and high-quality.

Weaknesses

- The transfer of the newly developed theory to practical networks is minimal. Sec. 4.3 still considers a CSBM instead of real-world data. - The work only considers GCNs. - The derivation of Eq. (17) is a bit hard to follow without further explanation. - No implementation is provided. No reason is given for why that is the case (cf. l. 529). However, the code for the experiments is also not the work's main contribution. Minor comments: - The reason for the specific definition of $\phi$ in l. 120 is only given in l. 148. This could be referenced earlier. - I assume that the sum in (16) is over all $\gamma$ and $\delta$. If so, a comma would help clarify that. Analogous in (17). - The order of the appendices A and B is reversed with respect to the presentation in the main paper. - The captions of the experiment figures are somewhat redundant from the main text. - One could also directly label the lines in Fig. 1c (instead of in the caption), making it more easily readable. Similar for Fig. 3b.

Questions

1. Regarding l. 175: Is the fixed point intentionally equal for all $\alpha,\beta$? 2. What does the solid line in Fig. 2d show? Isn't this a purely empirical plot? 3. How is allowing additional layers a "computational benefit" (l. 296ff)?

Rating

7

Confidence

3

Soundness

4

Presentation

4

Contribution

3

Limitations

Limitations are discussed adequately. It could be mentioned that the experiments are limited in both the GNN architectures that were investigated as well as the datasets the experimetns were perfromed on. The paper does not contain a broader impact statement or similar section on ethical considerations. This is perfectly acceptable for the work under review.

Summary

This work aims to understand whether GNNs in large depths always suffer from oversmoothing. The research starts from the equivalance of gaussian process (GP) and infinitely-wide NNs, and utilize eigenvalues of the linearization of GCN GP to quantify whether the model is in the phase of oversmoothing or not. After identify the intialization scale $$\sigma_w$$ as the key factor, it empirically verifies how deep GCN GPs and GCNs performance with different scales on synthetic graphs, and it turns out larger intialization does overcome the oversmoothing.

Strengths

1. The motivation is natural and the result is good: oversmoothing is an important question in the community, and the initialization scale was not took care of much before. 2. The research path is clear: while it is hard to directly understand finite-width GNNs, the equivalence of GCN GPs and infinite-width GCNs make it feasible to at least understand the problem in the wide regime, and then the argument could be empirically verified for finite widths.

Weaknesses

1. Evaluation is a little weak for more practical settings: for example, add some experiments on classification tasks on simple datasets like cora, citeseer. The goal would be to provide a better measurement of the performance with large initialization, since the currently provided results on synthetic settings are less pesuasive for practitioners to use such large intialization vs other methods to overcome oversmoothing.

Questions

1. a good addition would be to empirically verify how the eiganvalues change along training, which is to understand whether oversmoothing will appear or disappear with a certain scale of initialization. 2. what is the connection between this work and [1] about the singular values of weights? In section 3.3, they denote the singular values as $s$, and if the value is large, the bound for oversmoothing will not hold any more. Is this case the same as what is discussed in this work? --- Reference: [1] GRAPH NEURAL NETWORKS EXPONENTIALLY LOSE EXPRESSIVE POWER FOR NODE CLASSIFICATION.

Rating

5

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

Yes.