Taming Gradient Oversmoothing and Expansion in Graph Neural Networks

1. In line 147, the equation $\||\mathbf{X}\||_F^2 = \mu(\mathbf{X})^2 + \||\mathbf{X} - \mathbf{B}\mathbf{X}\||_F^2$ is presented. a step-by-step derivation or proof of this equation in an appendix, which will greatly enhance the clarity of the methodology presented.

2. The authors provided a mathematical derivation for representation similarity and gradient similarity, validating their correctness in Figures 1 and 2. However, it is unclear which metric better measures over-smoothing, as the relationships among representation similarity, gradient similarity, and test accuracy appear ambiguous in Figure 3. It seems the authors primarily used gradient similarity to assess over-smoothing in Section 5. In references [1] and [2], Dirichlet energy appears to be a more effective metric compared to gradient similarity. It would be helpful if authors could provide a more detailed comparison between gradient similarity and other metrics like Dirichlet energy, including quantitative results, which would help clarify the advantages of their chosen metric.

3. In my view, large datasets can mitigate oversmoothing compared to smaller ones. Intuitively, when aggregating features, each node has more distant neighbors, making it harder for features to become overly similar. As shown in [2], Pubmed and Ogbn-arxiv are less affected, as seen in Table 1. Could authors extend their theoretical analysis to consider the impact of dataset size on oversmoothing to enhance the theoretical persuasiveness of the paper?

4. The Lipschitz constraint method is an effective approach to alleviating over-smoothing and gradient expansion. It would enhance the paper's strength to incorporate 2-3 specific baseline methods from the related work section and utilize 1-2 large datasets from references [1] and [2] that are particularly relevant for comparison.

5. It appears that the theoretical derivation in the paper is based on the GCN model, yet the authors have also conducted some experiments on GAT, such as in Figure 4. Perhaps the authors should provide a corresponding theoretical analysis to enhance the persuasiveness of the paper. Additionally, if the model is changed to another one, such as GraphSage, would the theory still be useful?

[1] A Survey on Oversmoothing in Graph Neural Networks
[2] Dirichlet Energy Constrained Learning for Deep Graph Neural Networks

• Identity Activation Only: Only identity activation are considered (it doesn't seem to be difficult to obtain a result for non-linear activation fixing the origin from your proofs....

• Connected Graphs Why not consider disconnected graphs? It seems to me that with only a bit more work, you can generalize your result by noting that the normalized adjacency matrix has a block-diagonal form in the general (non-bipartide case).

• Results are for non-activated GNNs (identity activation function) but the numerics have non-linear activations (and result with identity activation are not plotted). This latter point, namely that there are no numerical experiments matching the theoretical setting, makes me wonder if there is a gap...Does the theory really come through in practice. One needs illustrations matching the architectural setup in the theorem.

• Theory is for very basic GCNN model (Which is definitely not universal by any means) but many other GNN models are considered in the experiments section. What is the relevance?

In terms of relevance and novelty, as well as related works, I think that the main issue is that most of the presented results are already quite known within the community, and can be found in the literature. For example see "A survey on oversmoothing in graph neural networks" and "Simplifying the Theory on Over-Smoothing". Also, the authors lack a discussion of "Revisiting Graph Neural Networks: All We Have is Low-Pass Filters".

In terms of using the Lipschitz constant and bounding it, it was shown in "On the Robustness of Graph Neural Diffusion to Topology Perturbations" and "Contractive Systems Improve Graph Neural Networks Against Adversarial Attacks" that using it can help to address robustness problems, so it would be interesting to understand the connection between oversmoothing and such approaches.

In terms of experiments, the authors used mostly simple datasets, and I think that it would be beneficial to also study the performance on other tasks and datasets. I think it would also be interesting to see a report of the Dirichlet energy, that is usually reported in oversmoothing studies. Also, I feel that the experiments lack comparisons with other methods that can address oversmoothing (there are already many such methods).

My biggest concern is that the statement on gradient oversmoothing in the asymptotic case is likely to be equivalent to gradient vanishing, i.e., that gradients vanish whenever the proposed similarity measure vanishes and vice versa. In fact, very similar statements to Theorem 1 (i.e., bounds depending on the weight matrix W) can be made for the gradients directly (see Di Giovanni et al, 2024 for instance). Of course it can happen that in the pre-asymptotic case this gradient similarity measure is small or even zero at some point, but this does not denote an issue.

This has to be addressed, otherwise this paper cannot be published. In particular, the authors have to show that there exists an asymptotic regime, where the similarity measure in Theorem 1 goes to zero, but the gradient norms do not. I suspect there are no such cases, but I am happy to be convinced otherwise. The same has to be done for Theorem 2.

That being said, this has also be demonstrated empirically. The provided plots in the paper only show the effect of varying the depth on the similarity measure. The same has to be done for the gradient norms for the exact same setup, i.e., same architecture with same weights. This would demonstrate that there are in fact cases, where gradients oversmooth but do not vanish.

Other issues:

• Some mathematical statements are wrong. For instance, the sentence after equation (3). Here, if B would be perpendicular to span($\bf 1$), it should be in $\mathbb{R}^{N-1,N}$, not in $\mathbb{R}^{N-1,N-1}$. Moreover, this sentence does not add anything to the context and is simply taken from Wu et al. which used it to demonstrate the similarity between this measure and another oversmoothing measure in the literature.
• most of the theory seems to be taken from other papers. It would be good if the authors could state explicitly what is their own theoretical contribution
• it would be good to extend to nonlinear layers, since in practice linear GNNs are not very common
• Only four small-scale graph datasets are considered. It would strengthen the paper if this would be extended.

Minor issues:

• The writing needs to be revised. There are many typos.