Learning to Control the Smoothness of GCN Features

Thank you for your thoughtful review and valuable feedback. In what follows, we provide point-by-point responses to your comments on the weaknesses and limitations of our paper and your questions.

---

1: The removal of white space in the paper makes it hard to read.

Response: We appreciate your feedback and we are happy to move certain parts to the appendix to make the paper easier to read.

---

2: The math could be made more intuitive by giving verbal explanations before the theorems. The cramming of the paper and not highlighting enough what the main contributions should be improved. Could you provide more intuitive examples or visual aids to help readers better understand the geometric characterization of smoothness in GCN features?

Response: Again, we appreciate your comment. We have summarized the main contributions in verbal explanations in Section 1.1. We also provide navigation for each contribution to the particular sections for details. In Lines 110-122, we provide a very brief review of used results from spectral graph theory.

Regarding the geometric insight, all we established is that there is a high-dimensional sphere associated with the input and output of ReLU and leakyReLU. In Sections 3.1 and 3.2, we provide details on the center and radius of these spheres.

---

3: Why did you choose the specific baselines for comparison? How would SCT perform against other SOTA GCN and GNN models not included in your study? It would benefit from a broader comparison with additional SOTA methods in GCNs and GNNs to provide a more comprehensive evaluation of its effectiveness.

Response: We design the experiments to solidify our theoretical results and verify the effectiveness of the informed algorithm. In particular, we have the following two purposes in mind: First, SCT can avoid over-smoothing for GCN. Second, learning to balance the smooth and non-smooth features can improve the performance of GCN-style models that even do not suffer from over-smoothing. We choose two state-of-the-art GCN-style models - GCNII and EGNN - as the testbeds. To show the effectiveness of the proposed approach, we have comprehensively studied models with different layers on 10 different benchmark datasets, covering all datasets from the papers we have benchmarked on.

Our proposed SCT can be treated as a bias term for GCN-style models and it can be integrated with many other GNNs. Studying other GNNs can be interesting for future work, especially whether the proposed SCT can improve the performance of other GNNs. We are happy to provide some comments in the revised paper.

---

4: Incorporating more real-world applications and diverse datasets would demonstrate the practical relevance and versatility of the proposed method.

Response: Our work is primarily theoretical with an informed practical algorithm. Using diverse existing celebrated benchmark tasks is a crucial step in evaluating the work. To better contrast with existing works, we used tasks from existing papers. We have further tested the performance of SCT on the peptide dataset originating from biophysics applications; our results in Table 6 of the rebuttal file further confirm the effectiveness and versatility of the proposed SCT.

---

5: The drop in accuracy for deeper models is noted but not deeply analyzed. A more thorough investigation into the causes of this performance degradation, beyond mentioning vanishing gradients, could offer insights into potential improvements. What happens if you use techniques that combat eg oversmoothing? Can you elaborate on the causes of performance degradation in deeper models? Have you considered any specific techniques to mitigate this issue?

Response: The drop in accuracy for deeper models occurs for GCN and GCN-SCT but not for other models that have skip connections in their architectures, which motivates us to investigate the vanishing gradient issue. It is noted in the original ResNet paper that using skip connections can effectively alleviate vanishing gradients in training deep networks. Our results in Figure 4 in the appendix confirm that vanishing gradients occur for GCN and GCN-SCT but not for other models.

The skip connection has become a celebrated technique to mitigate the vanishing gradient issue, and this is also the case for training deep GCNs.

---

6: While the paper mentions computational efficiency, a more detailed discussion on the computational overhead introduced by SCT, including potential trade-offs between accuracy and efficiency, would be beneficial.

Response: The computational overhead introduced by SCT is not very significant compared to the whole cost of training and deploying GNN-style models. Notice that we can avoid performing eigendecomposition by using the fact that the basis of the space $\mathcal{M}$ -- eigenspace associated with the largest eigenvalue of the message-passing matrix -- is given by the indicator functions of each connected component of the graph; see Lines 110-114. Therefore, the problem reduces to finding connected components of the graph, and an efficient approach to identifying connected components for undirected graphs is using disjoint set union (DSU). Initially declare all the nodes as individual subsets and then visit them. When a new unvisited node is encountered, unite it with the under. In this manner, a single component will be visited in each traversal. The time complexity is $O(V)$.

We provide the computational time for models with and without SCT for Ogbn-arxiv in Table 2 of the rebuttal file.

---

7: Providing more detailed discussions on computational efficiency and potential negative societal impacts.

Response: We will include these in the revision. See our response the point 6 above for computational efficiency.

---

Thank you for considering our rebuttal. We appreciate your feedback and are happy to address further questions on our paper.

Thank you for your thoughtful review, valuable feedback, and endorsement. We appreciate your invaluable suggestions and will revise the paper accordingly. In what follows, we provide point-by-point responses to your comments on the weaknesses of the paper.

---

1. While I can see that normalized smoothness has its own merit, this notion could be better motivated and connected to the literature.

Response: We appreciate all your invaluable suggestions and are happy to incorporate these suggestions in the revision.

The normalized smoothness notion was pointed out in [4], and we adapted this notion and noticed the equivalence between Dirichlet energy and the orthogonal complement of the projection of features onto the eigenspace. The analysis in [27,4] is asymptotic, but both normalized or unnormalized smoothness notions can characterize the smoothness of node features for GCN with a finite number of layers. A particular motivation for our work is the empirical correlation between the accuracy of GCN and a normalized smoothness-related quantity studied in [27]. As such, we propose a practical approach to control the smoothness of GCN features based on our observed geometric relationship between the input and output of activation functions.

---

2: The analysis only applies for GCNs, while whether the analysis or the proposed method can be extended to more complexed GNNs such as GATs or graph transformers is unclear.

Response: It has recently been proved in [A] that attention-based GNNs also suffer from over-smoothing. Specifically, [A] demonstrates that the node features converge to the same eigenspace as those in GCN. While using a different smoothness notion, they show that their measurement is equivalent to the one used by Oono & Suzuki (ICLR, 2020) and our work. Consequently, since the characterization of smoothness is the same, our technique can be applied to these frameworks to control normalized smoothness. In particular, in our analysis, $\bf z$ can be the feature obtained through any graph convolution, including attention-based methods. We will incorporate these discussions in the revision.

The main reason we did not include these models in our work is that, within the scope of "controlling smoothness" (which is not the same as mitigating over-smoothing), to the best of our knowledge, we only found EGNN to be an example in this branch. This is why we included it in our comparisons. Moreover, since it is built upon GCN and GCNII, we also included these two models.

[A] Wu, Xinyi, et al. "Demystifying oversmoothing in attention-based graph neural networks." NeurIPS, 2023.

---

3: The analysis only applies for ReLU and LeakyReLU, which reads a bit specific. I wonder if the results can be generalized to a general family of nonlinearities.

Response: The geometric characterization of the effects of activation functions in Section 3 uses some particular piecewise linear properties of ReLU and LeakyReLU. We expect a similar analysis can be applied to some other piecewise linear activation functions.

Some analyses of the achievable smoothness using the proposed SCT (in Section 4) can be extended to more general activation functions like ELU and SELU; see our discussion in Lines 233-235.

---

4: For the experiments, there is a lack of baseline comparisons except the basic backbone architecture. For example, I wonder how it would compare to APPNP, which is proposed to balance the need to explore larger neighborhood and locality and the implicit goal is also to produce node features with the "right" amount of smoothness.

Response: We have incorporated APPNP into our experimental results. We train APPNP using the optimal hyperparameters as reported by the APPNP paper. The results are reported in Table 4 of the rebuttal file.

---

5: Another presentation suggestion I have for the authors is that one should minimize the use of in-text math and bold or italic fonts for highlighting (such as line 167-173).

Response: We appreciate your suggestion and will account for this in the revision.

---

Thank you for considering our rebuttal. We appreciate your feedback and are happy to address further questions on our paper.

Thank you for your thoughtful review, valuable feedback, and endorsement. In what follows, we provide point-by-point responses to your comments on the weaknesses and limitations of our paper and your questions.

---

1: I need help understanding the explanation in Section 3.3. More specifically, it is difficult to understand that the independence of the inequality means that the upper bound of the inequality does not depend on the value of $\mathbf{Z}_{\mathcal{M}}$. I suggest writing it explicitly.

Response: To understand this better, we consider two inputs ${\bf Z}, {\bf Z}’\in \mathbb{R}^{d\times n}$, where ${\bf Z}\_{\mathcal{M}^\perp}={\bf Z}’\_{\mathcal{M}^\perp}$ but ${\bf Z}\_{\mathcal{M}} \neq {\bf Z}’\_{\mathcal{M}}$. Moreover, let ${\bf H}=\sigma(\bf Z)$ and $\bf H’=\sigma(\bf Z’)$ with $\sigma$ being ReLU or leaky ReLU. Based on our geometric results in Sections 3.1 and 3.2, we have $||\bf H||\_{\mathcal{M}^\perp}\leq ||\bf Z||\_{\mathcal{M}^\perp}$ and $||\bf H’||\_{\mathcal{M}^\perp}\leq ||\bf Z’||\_{\mathcal{M}^\perp}$. Notice that $\bf Z\_{\mathcal{M}^\perp}=\bf Z’\_{\mathcal{M}^\perp}$, we have $||\bf H’||\_{\mathcal{M}^\perp}\leq ||\bf Z||\_{\mathcal{M}^\perp}$.

Notice that $||\bf H’||\_{\mathcal{M}^\perp}\leq ||\bf Z||\_{\mathcal{M}^\perp}$ indicates that altering $\bf Z$ to any $\bf Z’$ with $\bf Z\_{\mathcal{M}^\perp}$ being preserved does not change the fact that $||\bf H’||\_{\mathcal{M}^\perp}$ will be upper bounded by $||\bf Z||\_{\mathcal{M}^\perp}$.

We have revised our paper per your suggestion.

---

2: P7, L.265: It seems strange that although SCT changes its architecture depending on whether the underlying GNN is GCT or GCNII, it has the same name. I suggest naming SCT for GCT and SCT for GCNII differently.

Response: Thank you for your suggestion, we will name them to specify the use of different SCT architectures in the revised paper.

---

3: P5, L.196: ${\bf e}\rightarrow {\bf e}\_1$ P6, L.209: What is the value of $\alpha$ of $\sigma_{\alpha}$?

Response: L196: For the sake of notation, we denote ${\bf e}_1$ as ${\bf e}$ as pointed out in L193-194. We are happy to denote it as ${\bf e}_1$.

L209: $\alpha$ is a smoothness control parameter and we vary this parameter from -1.5 to 1.5.

---

4. I recommend evaluating whether SCT has bad effects when the model does not cause oversmoothing.

Response: Thank you for your suggestion. Indeed, we have evaluated the effect of SCT on GCNII and EGNN - two state-of-the-art GCN-style models that do not suffer from over-smoothing. Our numerical results show that SCT can further improve the performance of these models. Though GCNII and EGNN do not suffer from over-smoothing, the node features learned by these two models do not necessarily have a good balance between smooth and non-smooth components that are optimal for node classification. In fact, we can improve the performance of these models by letting the model automatically learn a good balance between smooth and non-smooth features.

On the one hand, it is crucial to avoid over-smoothing for node classification. On the other hand, as noticed empirically by Oono & Suzuki (ICLR, 2020) the ratio between smooth and non-smooth features is highly correlated with the classification accuracy. Based on this empirical observation and our established geometric insights, we have proposed SCT to let GCN-style models automatically learn features with a desired smoothness to improve node classification.

---

Thank you for considering our rebuttal. We appreciate your feedback and are happy to address further questions on our paper.

Thank you for your thoughtful review and valuable feedback. In what follows, we provide point-by-point responses to your comments on the weaknesses and limitations of our paper and your questions.

---

1: The paper does not compare to established baselines from other competing methods. E.g. tables in arxiv:2202.04579 or arxiv:2210.00513 and add the results to the comparison in this paper.

Response: Thank you for pointing out these papers to us.

Our choice of architecture is based on the baseline of EGNN and we incorporate architectures in a comparable manner using the PyTorch Geometric framework. We provide full baseline architectures and hyperparameter details for all experiments. This enables us to consistently study the layer-wise bias introduced by SCT. The reviewer recommended papers use different architectures -- each model has a customized architecture, making it difficult to study the effects of SCT (a layer-wise bias term) introduced in different models.

Of the reviewer-recommended works, the model that makes the most sense for comparison to our method is G2-GCN. Notice that they do not provide details regarding the optimal hyperparameters selected for each experiment in either the paper or source code. Instead, they provide a range of randomly chosen parameters in the paper. It is beyond the purview of this work to fine-tune G2-GCN and so a reasonable hyperparameter selection was chosen. We compare the G2-GCN architecture with and without SCT. The results are listed in Table 4 of the rebuttal pdf.

As pointed out by Reviewer pS2J, our numerical results show that the proposed method is effective for various data sets and models, showing the versatility of the proposed method.

---

2: The paper reports different (mostly weaker) performance for the baseline models such as GCN and GCNII.

Response: The GCN and GCNII architectures we used are different from those in the reviewer-mentioned papers. Our used architectures provide a direct comparison between layer-wise operations performed by the addition of the SCT bias. We do not claim to achieve state-of-the-art performance but provide a reasonable baseline to compare methodologies. This provides a testbed for verifying our theoretical results. We utilize standard implementations of the GCN and GCNII layers using PyTorch Geometric. For additional comparison, Table 3 of the rebuttal pdf provides results for including SCT in the GCN architectures mentioned by the reviewer. Again, SCT improves the baseline model with a noticeable margin.

---

3: Please show the results for the datasets in Table 2 in the same way as you show them in Table 1, i.e., for increasing number of layers.

Response: In Table 5 of the rebuttal PDF file, we provide the corresponding table for the Texas dataset. We provide results for only the Texas dataset due to the space limitation, similar results hold for other datasets based on our experiments.

---

4: Justify the claim that the accuracy drop in Table 1 is due to vanishing gradients and not oversmoothing.

Response: We investigate the vanishing gradient issue in training deep GCN and GCN-SCT by plotting the gradient norm in Fig. 4 in the appendix, confirming that the vanishing gradient occurs for GCN and GCN-SCT but not for other models.

---

5: Figure 4 in the appendix showing gradient norms is not meaningful. The y-axis should be displayed on a logarithmic scale.

Response: We appreciate your feedback. In the rebuttal file, we have provided the updated figures in Figure 1. We also show the exponential decay in gradient norms.

---

6: The structure and readability of this paper should be improved.

Response: We are happy to incorporate your comments in the revision.

---

7: How expensive is it to compute the eigenbasis for the term (5)? How does it scale w.r.t. the number of nodes and edges? How long does it take to compute for the biggest graph considered here, i.e., arxiv graph?

Response: The computational overhead introduced by SCT is not very significant compared to the entire cost of training and deploying GNNs. Notice that we can avoid performing eigendecomposition by using the fact that the basis of the space $\mathcal{M}$ is given by the indicator functions of each connected component of the graph; see Lines 110-114. Therefore, the problem reduces to finding connected components of the graph, and an efficient approach to identifying connected components for undirected graphs is using disjoint set union (DSU). Initially declare all the nodes as individual subsets and then visit them. When a new unvisited node is encountered, unite it with the under. In this manner, a single component will be visited in each traversal. The time complexity is $O(V)$.

We provide the computational time for models with and without SCT for Ogbn-arxiv in Table 2 in the rebuttal file.

---

8: Significance of the results. There are more effective models and methods available for mitigating oversmoothing, which have not been cited or empirically compared.

Response: Please refer to our response to your first comment on the significance of numerical results. We appreciate the reviewer pointing out these references to us; we are happy to cite them in the revision.

---

9: There are no provided estimates for choosing the parameter alpha, which instead has to be learned through gradient descent.

Response: The desired smoothness that favors node classification is task-dependent and unknown. As such, we make the model learn to automatically balance smooth and non-smooth features; our empirical results show that such a learning-based strategy does improve the performance of some remarkable GCN-style models.

---

Thank you for considering our rebuttal. We appreciate your feedback and are happy to address further questions on our paper.

Dear Reviewer 5MTH,

Thank you for your response. Additional experimental results are provided in the one-page pdf file and the other changes have been made in the revised paper, which is straightforward to do. We cannot update the paper on openreview per the rebuttal rule. The system does not allow us to upload the revised version.

Regards,

Authors

Thank you for your thoughtful review and valuable feedback. In what follows, we provide point-by-point responses to your comments.

---

1. There is a slight improvement to be found in models with SCT, but this is not too surprising, as these models also have more parameters, and mostly improvements are quite slim.

Response: The accuracy improvement is task-dependent, and it is quite substantial for more challenging heterophilic datasets. As shown in Table 2 of our paper, the accuracy improvements are often more than 10%. In the rebuttal file, we have conducted hypothesis testing on the significance of the accuracy improvement due to the proposed SCT. The results in Table 1 of the rebuttal file confirm the statistical significance of accuracy improvement.

The accuracy improvement using SCT is not because of using more parameters: 1) Table 1 shows the baseline model with SCT and 2 layers can often achieve better accuracy than the baseline model without SCT but has 4, 16, or 32 layers. This is especially true for larger graphs like Coauthor-Physics and Ogbn-arxiv. 2) Table 2 shows that the baseline model with SCT and a shallow architecture can significantly outperform the same model without SCT but with a deeper architecture.

---

2. Learning the normalized smoothness of features does not actually seem to help in the case of GCN.

Response: The accuracy drop for GCN and GCN-SCT with a large number of layers is because of the vanishing gradient issue rather than over-smoothing. We investigate the vanishing gradient issue in training deep GCN and GCN-SCT by plotting the gradient norm in Figure 4 in the appendix.

The drop in accuracy for deeper models does not occur for other models that have skip connections in their architectures. It is noted in the original ResNet paper that using skip connections can effectively alleviate vanishing gradients in training deep networks. Controlling the smoothness of node features cannot help solve the vanishing gradient issue.

---

3: GCNII and EGNN don’t suffer from oversmoothing to begin with.

Response: On the one hand, avoiding over-smoothing for node classification is crucial. On the other hand, as noticed empirically by Oono & Suzuki (ICLR, 2020) the ratio between smooth and non-smooth features is correlated with the classification accuracy. Based on this observation and our established geometric insights, we have proposed SCT to let GCN-style models automatically learn features with a desired smoothness to improve node classification.

GCNII and EGNN are two state-of-the-art GCN-style models. We apply SCT to these models to show that learning to balance smooth and nonsmooth features can improve the performance of GCN-style models. Though GCNII and EGNN do not suffer from over-smoothing, the learned node features do not necessarily have a good balance between smooth and non-smooth components that are optimal for node classification. In fact, we can improve the performance of these models by letting the model automatically learn a good balance between smooth and non-smooth features.

---

4: Does the norm of the features $||z||\rightarrow 0$ tends towards 0? Doesn't this mean that features are also unusable in deeper layers?

Response: Under GCN dynamics, $||z||\rightarrow 0$ as the number of layers goes to infinity. However, it doesn’t mean that features are unusable in deeper layers. Notice that $||z||\neq 0$ for GCN with any finite layer, and the classification results do not change when multiplying features by a constant.

The feature norm itself does not capture the full spectrum of the smoothness of node features; the ratio between smooth and non-smooth features is an alternative smoothness notion.

---

5: Is this analysis extendable to other architectures? E.g. GAT and other attention-based methods are also known to oversmooth, can a similar trick be applied there?

Response: It has recently been proved in [1] that attention-based GNNs also suffer from over-smoothing. Specifically, [1] demonstrates that the node features converge to the same eigenspace as those in GCN. While using a different smoothness notion, they show that their measurement is equivalent to the one used by Oono & Suzuki (ICLR, 2020) and our work. Consequently, since the characterization of smoothness is the same, our technique can be applied to these frameworks to control normalized smoothness. In particular, in our analysis, $\bf z$ can be the feature obtained through any graph convolution, including attention-based methods. We will incorporate these discussions in the revision.

The main reason we did not include these models in our work is that, within the scope of "controlling smoothness" (which is not the same as mitigating over-smoothing), to the best of our knowledge, we only found EGNN to be an example in this branch. This is why we included it in our comparisons. Moreover, since it is built upon GCN and GCNII, we also included these two models.

[1] Wu, Xinyi, et al. "Demystifying oversmoothing in attention-based graph neural networks." NeurIPS, 2023.

---

6: Table 5 details the hyperparameters that were tried for each model. These seem to be very many combinations. Is it correct that you tried approx. 1.2 Million hyperparameter combinations for EGNN?

Response: Thank you for raising this point about the clarity of Table 5. Notice that in [2] Table 4 the optimal hyperparameters are listed for EGNN. We particularly examine tuning over $c\_{max}$, $\alpha$, and $\theta$. We tune GCN using the upper section of Table 2 and use the same selection of values for GCNII but adjust $\alpha$ and $\beta$. There are only 324 combinations and the runtime is under 60s per test.

[2] https://arxiv.org/pdf/2107.02392

---

Thank you for considering our rebuttal. We appreciate your feedback and are happy to address further questions on our paper.

We thank the reviewer for the thoughtful review, valuable feedback, and endorsement.

Regarding the pointed-out weakness, we can avoid performing eigendecomposition by using the fact that the basis of the space $\mathcal{M}$ -- eigenspace associated with the largest eigenvalue of the message-passing matrix -- is given by the indicator functions of each connected component of the graph; see Lines 110-114. Therefore, the problem reduces to finding connected components of the graph, and an efficient way to identify connected components for undirected graphs is using disjoint set union (DSU). Initially declare all the nodes as individual subsets and then visit them. When a new unvisited node is encountered, unite it with the under. In this manner, a single component will be visited in each traversal. The time complexity is $O(V)$.

---

Thank you for considering our rebuttal. We appreciate your feedback and are happy to address further questions on our paper.