Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper provided a novel viewpoint to understand the over-smoothing of deep GCNs by analyzing the asymptotic behavior of the Graph Neural Tangent Kernel (GNTK), which governs the optimization trajectory under gradient descent for wide GCNs. It is shown the trainability of GNTK (and thus wide and deep GCNs) drops at an exponential rate in the optimization process. It is also found that residual connection-resemble techniques can only help slow down the exponential decay of trainability but cannot overcome the problem. Following the "Critical Connectivity in Random Graph" by (Erdos & Renyi, 2011), the paper also provided insights on what critical edge-drop rate should be used in DropEdge. Experiments verify the theoretical results, and the critical DropEdge can consistently outperform other drop rates.
main_review: ### Strengths:
1. The idea of using GNTK to understand the over-smoothing issue is interesting. I think this approach opens up new viewpoints and directions on understanding GNNs and should be interesting to the community.
2. The experiment results aligned with the theoretical claims and insights very well and showed that the messages in the paper are sound.
3. Dropping edges following the critical connectivity theorem is insightful. Although it is a sample add-on to the DropEdge method (Rong et al., 2019), this extra piece of information is important.

### Questions:
1. I am curious whether this critical drop rate would still be the best on some denser graphs? It seems that the three node classification benchmarks considered are all relative sparse graphs whose average node degree is less than 5. The critical drop rate leads to a graph whose average node degree is equal to 1. And this might be too sparse for some denser input graphs (i.e., dropping too much information)? I found this critical DropEdge also provides some insights on improving the Message Passing architecture. Thus some further exploration might be interesting.
2. The insights behind critical DropEdge is to break the connectivity. However, it is unclear how this would affect the theoretical results (Corollary 1). Do you think there are other possible methods to get rid of the exponential decay without affecting the connectivity?

### Weaknesses:
1. The baseline methods considered in the paper are limited. I agree that DropEdge should be the most relevant baseline, but it would be better to discuss some other methods (e.g., normalization-based approaches). I also find the related work section insufficient. It would be interesting if the new theoretical framework could provide some insights on the other research on understanding/solving the over-smoothing issue.
summary_of_the_review: This paper tries to understand the over-smoothing problem of deep and wide GCNs using the theoretical framework provided by GNTKs. The results on the exponential decay of trainability, residual connections, and critical connectivity are insightful and should be interesting to the community. The experimental results are well-aligned with the claims and show the soundness of theoretical findings. Given the novelty and significance of the findings, I am happy to recommend this paper for acceptance.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper aims at tackling the well-known over-smoothing problem of deep graph neural networks (GNNs) from a theoretical perspective. Specifically, the authors exploit the Graph Neural Tangent Kernel (GNTK) and use it to analyze the trainablility of GNTK in the large depth, which provides insight for the reason of the over-smoothing problem. According to the theoretical analysis, the trainablility of wide and deep GNNs drops exponentially in the optimization process, and the residual connection can only mildly mitigate this problem. Based on the analysis, the authors modify the DropEdge method and propose the Critical DropEdge (C-DropEdge). Both numerical and real experiments are provided to demonstrate the validity of the theoretical analysis and the proposed C-DropEdge.
main_review: ### Strengths

1. The investigation of the trainability of the ultra-wide GCNs via the GNTK view has its novelty for the graph machine learning community and provides new perspective for the over-smoothing problem.
2. The Proposition 1 provides more information on the power of the DropEdge method and motivates the derivation of C-DropEdge.
3. Detailed experimental analyses (Fig 1, Table 2) are provided.
4. Both the Sec 2 and the Sec 6 are well written and provide clear and fruitful preliminary knowledge on this work.

### Weaknesses

1. About the derivation of the C-DropEdge

   (1). The authors make extrapolation from the connected component size to information flow and show the information transforms in the critical random graph at a polynomial rate rather than an exponential rate. It would be better to further analyze the convergence rate of the GNTK in the critical random graph and show that the exponential drop of the trainability is mitigated by the proposed technique.

2. About the experimental results: 

   (1). To validate that the C-DropEdge can better mitigate the loss of the trainability of deep GNNs, the training performance should be provided besides Table 1. Moreover, the convergence results of GNTKs with C-DropEdge should also be provided to compare the mitigating effect between residual connection and C-DropEdge.

   (2). Suggestions for the next version of this paper: there can be more baseline methods to verify the C-DropEdge. Different model architectures [1, 2] and normalization mechanisms [3, 4] can be tested to provide more general insight on the effect of the C-DropEdge for the methods in use in the graph ml community.

3. Minor issues:

   (1) In the theorem 2, the readers can only get that the original base $\alpha$ of the exponential convergence rate term is replaced by a new base $\tilde\alpha$ (it is even not defined), and the second largest eigenvalue of the transition matrix under the residual connection setting is larger. It is not straightforward to conclude that the "slow down" effect of the residual connection, especially for those who do not have enough theoretical background knowledge.

   (2) The wording "residual connection-resemble technique" is perplexing.

[1]. Chen et al, Simple and Deep Graph Convolutional Networks. ICML 2020

[2]. Li et al, Deepergcn: All you need to train deeper gcns. arxiv preprint.

[3]. Zhao et al, Pairnorm: Tackling oversmoothing in gnns. ICLR 2020.

[4]. Zhou et al, Towards Deeper Graph Neural Networks with Differentiable Group Normalization. NeurIPS 2020.
summary_of_the_review: The over-smoothing problem of deep GNNs is a well-known problem in the graph ml community, which impedes the researchers to fully unlock the power of the GNNs due to the limits of the model capacity. The authors try to provide a new perspective via the GNTK view. However, there exists logical gap between the theoretical results and the claims and the derivation of the proposed C-DropEdge algorithms. Detailed experimental results are also necessary to better demonstrate the effect of the proposed method. **Thus, my recommendation for this paper is "weak rejection".** If the authors can address the questions in the above "Weakness" section well, I am willing to consider raising my scores.

********* After Rebuttal *********

The authors have addressed by concerns and I am willing to raise my scores to "Weak Accept".
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper utilizes the latest technology called GNTK to explore the trainability of deep graph convolutional networks. They prove that the trainability will decay exponentially as layers go deeper and residual connection only mitigates this phenomenon. They proposed to utilize drop edge methods to solve this problem. The dropout rate is determined by the theory. And the experimental result shows that their solution is better than the baseline.
main_review: 1. Previous methods only explore the expressivity of GCN and this work focuses on a more fundamental problem, whether gradient descent can find a good solution for deepGCN.

2. This paper has a solid and detailed mathematical derivation of the proposed theory. The experiments actually show that the residual connection doesn’t solve the problem but slows down the collapse speed during training and the distance between elements drops exponentially, which corresponds to the exponential decay of trainability.

Comments:
1. The proposed solution edge drop has been widely applied in many models. The optimal dropout rate is not a significant breakthrough. It could be easily found by the hyperparameters search. 

2. The experimental setting still has some problems. There is only one baseline which is published in 2020. Maybe the author could incorporate more methods that aim to train a deep graph convolutional model to show their solution's superior performance. 

3. The comparison is not fair. The hyperparameters for the baseline have been set the same as the original paper. But the train/validation/test set may not be the same. Because this paper reported results for the baseline are not consistent with the original paper. For example for 8 layers, the Cora dataset reported by the original paper on GCN and JKNet model is 85.80 and 87.80. The corresponding result in this paper is 75.1,  82.0.

summary_of_the_review: The experimental results prove the consistency between the theory and reality.
For the weakness of this paper, the proposed solutions to solve this problem are far less attractive and the comparison with the baseline is not fair.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper uses a GNTK formulation to show how the performance of a deep GCN decays for node classification tasks with increasing depth. The authors show that in the infinite-width settings (where NTKs are valid) a very deep network amounts to a constant GNTK, meaning that the kernel value between any pair of nodes converges to the same value. Consequently, node classification performance degrades drastically with depth. Based on this analysis, the authors then propose a workaround to mitigate this decay by dropping edges in the original graph.

main_review: The theoretical perspective presented is interesting. However, I have the following comments:

1) In Corollary 1 it is claimed that there exists some L_0 for which for all L > L_0 the GNTK at depth L is singular. In the proof of the corollary, the authors say that this follows from Theorem 1. However, I do not see exactly why this is the case. The fact that the limit of the GNTK is singular does not imply that there exist some finite L_0 for which this is singular. Is this right?

2) In Theorem 2, I presume that there is some implicit relation between \tilde{\lambda_2} and \tilde{\alpha}, otherwise the last sentence about the relation of the second eigenvalue of \mathcal{A}(G) is irrelevant to the rest of the result and to the discussion after the Theorem. In other words, for the Theorem 2 to imply that “residual connection can slow down convergence rate”, I imagine that the authors are referring to the fact that \tilde{\alpha} in Theorem 2 is larger than \alpha in Theorem 1, but this is never stated.

3) The \alpha in Theorem 3 has to be the same as the \alpha in Theorem 1 for the story to make sense. I understand that this is the case, but this is never mentioned.

4) The solution proposed by the authors not to converge to a singular GNTK is to break the connectivity in the graph by dropping edges. However, this brings up a few natural follow-up concerns that are not addressed:
i) Wouldn’t you still have the same problem within each connected component of the new graph?
ii) Is really destroying information (deleting edges) present in your graph the best way to shield against the effect of deeper networks?
iii) Can something be said either theoretically or empirically about the GNTK of such networks? One would expect a Theorem like 1, 2, or 3 but for this new case showing that in the limit this architecture converges to something useful for classification, but there is no discussion in this direction.

5) The empirical results of Critical-DropEdge are not too much better than the baseline which suffers from exponential convergence. For example, the vanilla GCN in CORA goes from an accuracy of 79.8% with 4 layers to 20.1% with 32 layers, a massive decay. However, with the technique presented here this drop goes from 82.0% to 24.7%, which is in the same order of a massive drop. Moreover, for GCN, even with the proposed critical DropEdge, the architecture with 4 layers outperforms all of the deeper alternatives across the three datasets studied. In this sense, it seems like the proposed methodology mildly slows down the deterioration with depth, but cannot leverage depth since shallow GCNs are still performing better.

6) There are several typos and inconsistencies that should be addressed. E.g., if we only focus on page 6: 
- in Theorem 2 the first appearance of \alpha should be \tilde{\alpha}
- in Theorems 2 and 3 the authors refer to v and v’ as matrices when they are vectors
- the probability p=|E|/E_t is not the probability of dropping an edge but the probability of retaining an edge.
- the sentence “the probability that there is an open path from some fixed point (say the origin) to a distance decreases polynomially” seems to be taken from somewhere else and copied out of context. What is an “open path” here? What is the “origin” in a graph? What “distance” are we referring to?
- Maybe it might be better to cite the original paper from Erdos-Renyi using the actual date. This is a paper from the 60s and it might be misleading to present this result as something from 2011 even if this paper was included in some more modern collection of papers. 
summary_of_the_review: The authors present an interesting perspective to justify the decay in performance of deep GCNs. On the downside, the provided solution is not studied within the same theoretical framework and does not show promising empirical results.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: They first investigate the trainability of deep GCNs through GNTK, instead of expressive power, and theoretically prove that the convergence rate of the GNTK is exponential. A similar analysis is given to residual techniques in GCNs, which shows residual techniques can alleviate such a problem to some extent but cannot solve it. Finally, based on their findings and analysis, they propose an edge-based sampling method named Critical DropEdge, to overcome the exponential decay of trainability.
main_review: Strength: 
(a) They are the first to focus on the trainability of deep GCNs through GNTK, instead of expressive power. 
(b) Analysis and proof of the exponential convergence rate of the GNTK and that of residual techniques. 

Weakness:
 (a) An error in and equation 6 when formulating GCNs. Graph Convolutional Networks do not have such decoupled formulations.
 (b) A fundamental error in and equation 1, 7 when formulating GNNs or GCNs. The non-linear activation function phi appears at the most INNER place in equation 1, 7, before the transformation. But neural networks usually have their activation after the transformation. Note that the activation functions are NON-LINEAR functions. All the analyses based on such an equation may be rechecked.
(c) Their experiments are based on only three citation datasets, which are limited both in fields and scales. 
(d) No detailed information such as data splits is provided.

summary_of_the_review: The paper's insights are good, but the theoretical analysis seems based on a wrong equation, so they may need to recheck the results. Experiments conducted on more types of datasets in different fields and scales are required.
review_title: null

Meta-review: In this paper, the authors established interesting theoretical results regarding the behavior Graph Neural Tangent Kernel (GNTK). They also provide sufficient evidence (some of which during rebuttal) that their approach is valid. We have had many discussions and I suggest that the authors apply reviewers' comments to the final version of their paper.
Decision: Accept (Poster)