Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The deals with semi-supervised learning with graphs using graph neural networks. Specifically, it investigates the benefits of depth both from a (learning) theory as well as an empirical standpoint. 

The key contributions are:
1. Questioning the common folklore belief that deep GNNs are not expressive due to "over-smoothing"
2. Studying the generalization performance of GNNs using uniform stability theory 
3. Introducing  "Decoupled GCNs" which learn linear combinations of single-layer GNNs (using powers of the Laplacian).
4. Experimental study validating the theoretical results. 
main_review: **Contribution/Originality:** The paper aims at demystifying the role of depth for the expressivity/generalization properties of GCNs/GNNs. To that, they first try to show that the number of expressible equivariant functions grows exponentially with the depth (Thm 1). They then show that deeper GCNs need more iterations to converge while achieving the same training error (Thm 2, *the exact setup of the statement, seems to be missing in the main text*. It is not clear to me.). They then leverage known results from learning theory, namely the "transductive uniform stability bound", to study the generalization performance of different variants of GCNs, which, as far as I know, has not been done so far.
Moreover, they introduce "decoupled GCN", see lines 324/5, which learn linear combinations of single layer GNNs (using powers of the Laplacian) and relate their generalization performance to other GCN variants. 
The theory is complemented by an experimental study validating the theoretical results. 

**Clarity:** Unfortunately, the paper is **not clear**, it seems to be written up in a hasty manner. For example:
In the statement of Thm 1 the meaning of "richness" is not clear, although it could have been made clear as the result is just a simple combinatorial insight. This sloppiness continues throughout the whole paper making some theorems almost non-understandable (e.g., Thm. 2).

**Significance:** The findings are significant to the GNN community. 

Pros:
+ First (real) principled attempt to understand the role of depth in the generalization performance of GNNs 
+ Good coverage of (relevant) related work
+ Reasonably well-executed experimental study

Cons:
+ Unclear statements and sloppiness throughout. The presentation lacks clarity overall.

Minor remarks:
There are many spelling and grammar mistakes throughout the paper that could have been found easily by using a standard spell/grammar checker. 

Suggestion:
Put in the work and make everything mathematically precise and clear, while also making it easier for the reader to understand the significance of the results. I am looking forward to a revised, cleaned-up version of this paper. 
limitations_and_societal_impact: Not applicable.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper provides a novel theoretical understanding of over-smoothing and point out that the major impact of poor performance is due to the generation gap. The paper brings a new point about why deep GCN fails. Moreover, the paper designs a new framework according to their theorem although the proposed framework is just a dense version of GCNII.
main_review: Pros:
1. The paper point out the issues that the previous papers may neglect some other reasons that cause poor performance besides over-smoothing. Many papers assumes that the singular values of weights <1 and the second largest eigenvalue <1. However, the paper finds that the singular values of weights is not always <1 and the second largest eigenvalue is very close to 1 in the rea-world datasets. Consequently, it may not cause the vanishing of the layer outputs along infinite layers.
2. The paper theoretically analyzes another fact of poor performance, the generation gap. Lemma 1 formulates the generation gap in terms of Lipschitz continuity, smoothness and gradient scale.

Cons:
1. In Figure1, the paper claims that GCN would reach a high training accuracy on Cora with efficient number of iterations. However, I tested GCN on Cora with lr=[0.01~$10^-10$], dropout=0.5, hidden=128, epochs=6000, layers=8 (Basic modules from dgl). I did not get neither converged training loss nor high training accuracy. So how does the authors train the GCN to get high training accuracy?
2.  The experimental results does not show the results with very deep GCNs such as 32 layers or 64 layers. And the paper did not compare with some other over-smoothing-coping methods such as dropedge, Pair norm, etc. Or I might miss them in the Appendix.
3. The main theoretical results are not related to the Laplacian matrix. It seems that the paper relax the Laplacian matrix to be no larger than 1 (The largest eigenvalue). It could be a tighter bound with the second largest eigenvalue. Moreover, it is little confused between layer number $L$ and Laplacian matrix $\mathbf{L}$. 
4. In [26], it involves the analysis for GCN with bias. The paper does not discuss the situation with bias. It might be a good future work. 
5. The fonts of figures are too small.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper analyzed GCN model for node classification in depth. The paper first analyzed the deep model's performance degeneration problem and argued that the deep model's expressiveness is not worse than shadow model so it does not suffer from oversmoothing problem. In fact, the degeneration of deep model comes from the hardness of training instead of oversmoothing, and the papers theoretically proved that deep model needs more iterations to converge, under a strong assumption. The above explanation explained the training loss but not characterize the final test performance. The author further explored the generalization error (the gap between training loss and test loss) and proved that under transductive setting the generalization error is affected by the number of training epochs, the number of layers, singluar value of weight matrix and largest node degrees, which explained why deep models have degenerated test performance. The author finally proposed a weight to decouple weight matrix and feature propagation operations, which keeps the expressiveness and also improves generalization ability. 
main_review: 1. Originality: the analysis of performance of deep models is comprehensive in terms of training and test performance, and is novel. The author gives enough empirical observations as well as solid theoretical analysis (although some parts are not clear enough, and I'm not sure whether the proof contains error or not). Overall the novelty is great.

2. Quality: in general I buy the story as all explanations align with my own experience and also greatly explains their observations. However I do have several questions. And feel some claims seem too aggressive without solid enough theoretical results. 
 - Line 120 defines the normalized Laplacian matrix and DAD which is not correct, I-DAD is the normalized Laplacian matrix.
 - Theorem 1 charaterize node feature richness by using graph-level result, and this needs to view each node embedding as a graph embedding of the computational tree structure. I want to know whether the result rely on independent assumption of very computational subgraph (in definition 1). In general N computational subgraphs in original GNN are coupled together instead of independent, which is true for graph level tasks. 
 - Theorem 2 needs dL >= N, which is not valid in real world, (however you can assume a wide enough representation with NxN matrix size in theory) , I would like to know how does this affect the result of theorem 2 if dL is a constant like 512. 
 - Statement from line 308 to line 310 seems to bold and incorrect to me, as you can also pickup hyper-parameter to make the order incorrect. I hope the author can provide more solid analysis instead of this vague argument. This argument is intended to match empirical observation in my understanding. 
- There are conflicted statement about resnet, the line 292-295 is very different from line 354-357. One argument said residual connection worse the generalization while the other said that resnet is very similar to DGCN. I hope the author provide more analysis to explain why adding residual worse the generalization ability. 
 - The Remark 1 is great empirical observation, however the statement sounds too confirm to me. If you can give more theoertical analysis out of empirical observation the remark 1 will become solid to me. 
 - The generalization error is showed only on synthetic dataset and cora. I would like to see the empirical analysis over OGB dataset. 
 - Table 1 is hard to read as it involves so many equations, if you would provide some intuition of them on the title of the table it will be a lot easier to follow. 

3. Clarity: in general the paper is well-written and easy to follow.

4. Significance: the DGCN performance is not solid enough. This is acceptable as all previous analysis is novel and comprehensive enough. Nevertheless, I do expect that DGCN can help better generalization ability as it is specially designed. The similar performance between DGCN and APPNP suggests the generalization gap is not fully charaterized by the theory presented in this paper (whether upper bound is tight or not). 




limitations_and_societal_impact: NA
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors argue that over-smoothing does not necessarily happen in practice and prove that a deep model is expressive as long as properly trained and can converge to global optimal with linear convergence rate. They also analyze the generalization capability of GCNs  and propose a decoupled structure for GCNs to preserve the expressive power and ensure  good generalization performance.
main_review: Strength:
1. Understanding over-smoothing problem is important for GNNs and it’s still there although there are many deep GNN models can empirically get good results.
2. I personally very like some points in this paper, e.g. “…over-smoothing is mainly an artifact of theoretical analysis and simplifications made in analysis…”; “Existing results expressive power are mixed, [38, 36, 7, 5] argue that deeper
 model has higher expressive power but [40, 26, 25] has the completely contradict result”
3. The authors provide detailed theoretical analysis of over-smoothing and it’s important for the whole ML community.


Weakness&Advice:

1. In theorem 2, why do you need $d_L \geq N$. This condition seems impractical.
2. Page 7 is the worst part of this paper because of writing problem. The writing is understandable but not reader friendly.
3. The font size in all figures need to be enlarged.
4. Lemma 1 can be moved to appendix and theorem 4 need to be elaborated. The content in page 7 is not reader friendly.
4. In Figure 4, some curves stops before iteration 200. Need more explanation. What is the results on test set.
5. Line 335-337, “…DGCN assigns smaller weight to each layerwise function $f^l(X)$ with more propagation steps at the beginning of training. Throughout the training, DGCN gradually adjusts the weight to leverage more useful large receptive field information.” It’s better to provide a figure on how $\alpha_l$ changes during training to confirm this claim.

Some grammar problems: 

Line 5, “…over-smoothing not necessarily  happen…” —> “…over-smoothing does not necessarily  happen…”.
Line 226, “a deeper GCNs has worse performance” —> “a deeper GCN has worse performance”. There are some misuses of ‘GCN’ and ‘GCNs’ in other places, please double check.

I will raise my score if the writing can be improved. Overall, I would like to see this paper to be published.

limitations_and_societal_impact: Yes, the authors adequately addressed the limitations and potential negative societal impact .
review_title: null

Meta-review: This work provides theoretical and empirical evidence that over-smoothing does not necessarily happen in practice: it is shown that a deep GCN is expressive as long as properly trained, as well as that it can converge to a globally optimal solution. The paper also discusses the generalization capability of GCNs.

The reviewers and AC agree that these contributions are valuable to the GNN community and non-trivial.

The paper contained some small bugs, but these should be easily fixable in the camera-ready version.
Decision: Accept (Poster)