Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: Along the line of linear GCNs, this paper dissects the feature propagation steps via continuous graph diffusion. With theoretical analysis on numerical methods to approximate Graph Heat Equation, the paper proposes a linear GCN, named as DGC, that decouples terminal time $T$ and propagation steps $K$. As shown in real-world experiments, DGC enjoys competitive results compared with linear and non-linear GNNs.
main_review: Linear GCN is a rising topic in the domain of Graph Neural Networks, since it enjoys much faster speed during training and scalability on large graphs. This paper decouples terminal time $T$ and propagation steps $K$ to design a Linear GCN with optimal tradeoff between oversmoothing and undersmoothing, while most typical models do not pay attention to such decoupling. I like the setting of Theorem 3 as a motivation to find the optimal terminal time $T^*$. However, there are some concerns to address.

Concerns:

1. mistakes in the bound in Theorem 3: to derive the last inequality in line 46 of appendix, (1) a coefficient of 2 is missing as $||a+b||^2\le 2||a||^2+2||b||^2$, and (2) $M$ is a bound for the norm of $X_c$ but the paper is seemingly using $M$ as a bound for norm of $X_0$ where $X_0=e^{T^*L}X_c$.
2. possible experiments to extend: (1) there is an earlier related work [1] that concatnates different orders of $A^kX,k=1,\dots$. It would be interesting to compare SIGN with DGC in a fair style, such as with the same terminal time $T$. Note that data split for Reddit dataset in [1] looks different from DGC. (2) it would be more promising to try DGC on OGB node classification benchmark.
3. For computation time in Section 5.4, it is necessary to explicitly report the pre-processing time of DGC. I suppose it uses approximately $50\times$ pre-processing time for DGC(K=100) compared with SGC(K=2), which makes the total training time $3\times$ considering about 5% of training time of SGC is for pre-processing. Then, as I mentioned in Concern 2, if SIGN [1] works with similar performance with DGC, since SIGN is with a closer pre-processing time to SGC, it might raise questions on design details of DGC.
4. Theorem 1 is not too novel compared with results (around Proposition 1) in [2] that GCN asymptotically converges to non-informative equilibrium.
5. although the paper mentions a variant DGC-RK based on 4-order Runge-Kutta method, its performance is not shown. It would be interesting to conduct ablation study with it to explore whether it is necessary to utilize higher-order finite difference method and strengthen the argument of Theorem 2 on numerical errors.

Typos:

1. in lines 30-31 of appendix, both $n$ should be $k$.
2. in line 46 of appendix, the left square bracket is not at the appropriate position in the first inequality.
3. re-statement of Theorem 3 in appendix is not consistent with that in the main text.

[1] Sign: Scalable inception graph neural networks. F Frasca, E Rossi, D Eynard, B Chamberlain, M Bronstein, F Monti.

[2] Graph Neural Networks Exponentially Lose Expressive Power for Node Classification. K Oono, T Suzuki.

Therefore, I suggest it is below the acceptance threshold for novelty compared with [1,2]. If my concerns about SIGN are addressed, I am willing to raise my score.

======================== post rebuttal =======================

I would like to increase my score from 5 to 6 based on authors' responses.
limitations_and_societal_impact: No.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper investigated the feature propagation steps of linear GCNs from a perspective of continuous graph diffusion, and analyzed why linear GCNs fail to benefit from more propagation steps. From the perspective of diffusion equation, the authors decoupled the terminal time and the feature propagation steps, and proposed DGC to make it more flexible and capable of exploiting a very large number of feature propagation steps. Theoretical insights and extensive experiments on benchmark and large graph datasets have verified the superiority of DGC. 
main_review: Strength:
1.	The paper is very insightful and inspiring, especially on the analysis of the linear part of GCN (SGC), which provide a clear explanation on why SGC will oversmooth, i.e., cannot benefit from more propagation steps. The view from diffusion process is novel and has solid theoretical foundations.  
2.	The proposed strategy of decoupling the terminal time T and the propagation steps K is simple but effective. It enables a flexible tradeoff between under-smoothing and over-smoothing and a more fine-grained numerical integration scheme. Besides, the authors provided a solid theoretical analysis for their method with asymptotic, numerical and risk properties from a continuous perspective. 
3.	Lots of experiments are provided to understand and evaluate the proposed methods. They show that the proposed method can outperform canonical GCNs significantly and obtain SOTA results among linear GCNs. Its performance is even close to that of SOTA non-linear GCNs, thus can serve as a strong baseline for future studies on GCNs. The experiments covered lots of aspects, including linear/non-linear models and extensive ablation studies, which definitely convinced me of the effectiveness of the proposed method. 

Weakness:
1.	The background on linear GCNs may not be clear. Why do we need to study linear GCN? Most of current models are non-linear. 
2.	The difference between with self loop and without self loop?
3.	The authors used the step-size to be T/K. Why exactly T/K? can we use larger or smaller than T/K?
limitations_and_societal_impact: No significant social risk
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: Non-linear GCNs have attracted a lot of attention recently, and many methods are proposed around them. However, this paper finds and investigates that current GCN variants still have not shown significant advantages over a properly designed linear GCN (their proposal). This is significant to the whole field and can help shape a new direction to propose real powerful non-linear GCNs.

main_review: Pros:

1. Although recent works have shown that a linear GCN can achieve comparable performance to the original non-linear GCNs, researchers still do not investigate this situation deeply. This paper fills this gap and, correspondingly, proposes a powerful linear GCN. This strong linear-case solution can help researchers rethink the most important part of the non-linear GCN. 

2. The paper is technically sound. It is novel to dissect the feature propagation steps of linear GCNs from a perspective of continuous graph diffusion. Experimental results demonstrate the effectiveness of the proposed method.

3. It is novel to link oversmoothing issue to the terminal time. The proposed dissection of linear GCNs suggests a different understanding of the oversmoothing problem. In Theorem 1, oversmoothing is an inevitable phenomenon of (canonical) GCNs, while this paper finds a terminal time to achieve an optimal tradeoff between under-smoothing and oversmoothing, which is novel and significant.

Cons:

1. Readability should be improved. For a reader who does not know GCN, it is hard to understand the feature propagation steps of GCNs and the meaning of continuous graph diffusion. Some basic intros regarding them should be added. For example, the preliminary section can be added.

2. In addition, T and K should be introduced in the caption as well to improve the readability of Figure 1. Some subfigures in Figure 1 are less informative (e.g., second line, the second one (left to right)). It is hard to get the main information from them.

3. The difference between linear and non-linear GCNs should be analyzed deeply. In some datasets, some non-linear GCNs still outperform linear ones. What properties contained in these datasets make non-linear ones better? In some datasets, linear GCNs are better than non-linear ones. What properties contained in these datasets make linear ones better? It would be better to discuss the results by visiting datasets in detail.
limitations_and_societal_impact: The authors have not discussed limitations and potential social impacts. I suggest discussing the potential social impact from the trained networks that have low accuracy (in the node classification tasks).
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This work studies linear GCNs and tries to provide a solution to find the optimal tradeoff between under-smoothing and over-smoothing. It first pointed out the limitations of SGC, then propose the Decoupled Graph Convolution (DGC) model to address the limitations. The key idea is to view the feature propagation step in linear GCN from a perspective of continuous graph diffusion, and dissect the terminal time and the propagation steps to enable choosing a flexible continuous terminal time (and therefore can benefit from more propagation steps).
main_review: Strength：
- Different from the discrete linear GCN model, this paper utilizes the continuous version of GCN so that the termination time T can be controlled independantly from the number of propagation setps K. Decoupling terminal time and number of steps is a very good point.
- Theoretical part is clear and seems solid. The authors first pointed out the weakness of SGC from the theoretical perspective and then show the proposed DGC address these weakness successfully. 
- Experiments from different aspects are conducted to verify the proposed DGC. The comparisons and the ablation studies are comprehensive and make it clear to know how and why DGC works. 

Weakness:
- In Figure 2, the authors set the DGC to K=100, i.e., propagating 100 times. And SGC only propagates 2 times, so why the training time DGC is only 3 times slower than SGC, is it because SGC converges slower than DGC?
- Could the authors give some insights on when linear models like DGC should be used in real applications, and when non-linear models should be used?
- The authors showed the robustness to feature noise in Sec. 5.4, but I am curious to know why DGC is better here?
limitations_and_societal_impact: see the above weakness.
review_title: null

Meta-review: This is a half understanding and half methodology paper, studying why existing linear GCNs cannot benefit from more feature propagation steps, and proposing *decoupled graph convolution* to make linear GCNs possible to benefit from a very large number of feature propagation steps. The writing is clear, the motivation is strong, the idea is novel, and the results are significant. Thus, I think it should be accepted for publication.
Decision: Accept (Poster)