Dissecting the Diffusion Process in Linear Graph Convolutional Networks
Authors: Yifei Wang
Yisen Wang
Jiansheng Yang
Zhouchen Lin
Venue: NeurIPS 2021 Poster (2021)
Keywords: Graph Neural Networks
Graph Heat Equation
Linear Models

Abstract: Graph Convolutional Networks (GCNs) have attracted more and more attentions in recent years. A typical GCN layer consists of a linear feature propagation step and a nonlinear transformation step. Recent works show that a linear GCN can achieve comparable performance to the original non-linear GCN while being much more computationally efficient. In this paper, we dissect the feature propagation steps of linear GCNs from a perspective of continuous graph diffusion, and analyze why linear GCNs fail to benefit from more propagation steps. Following that, we propose Decoupled Graph Convolution (DGC) that decouples the terminal time and the feature propagation steps, making it more flexible and capable of exploiting a very large number of feature propagation steps. Experiments demonstrate that our proposed DGC improves linear GCNs by a large margin and makes them competitive with many modern variants of non-linear GCNs.

Dissecting the Diffusion Process in Linear Graph Convolutional Networks
Yifei Wang' Yisen Wang2.3+ Jiansheng Yang' Zhouchen Lin
School of Mathematical Sciences, Peking University, Beijing, China
2 Key Lab. of Machine Perception, School of Artificial Intelligence, Peking University, Beijing, China Institute for Artificial Intelligence, Peking University, Beijing, China
Pazhou Lab, Guangzhou, China
waei__wan@pku...o yjs@math, pku, edu..ddu.cc en, zlin@pku.edu. edu.
eer.ngupkueeu...... edu. cn, yisen. wwwg:pku.g@@peeeeoomm edu.cc
Abstract
Graph Convolutional Networks (GCNs) have attracted more and more attentions in recent years, A typical GCN layer consists of linear feature propagation step and nonlinear transformation step. Recent works show that a linear GCN can achieve comparable performance to the original non-linear GCN while being much more computationally efficient. In this paper, we dissect the feature prop- agation steps of linear GCNs from perspective of continuous graph diffusion, and analyze why linear GCNs fail to benefit from more propagation steps. Fol- lowing that, we propose Decoupled Graph Convolution (DGC) that decouples the terminal time and the feature propagation steps, making it more flexible and capa- ble of exploiting very large number of feature propagation steps. Experiments demonstrate that our proposed DGC improves linear GCNs by a large margin and makes them competitive with many modern variants of non-linear GCNs. Code is available at https: / //github, com/ y rrffeiwanng" 77DGC.
Introduction
Recently, Graph Convolutional Networks (GCNs) have successfully extended the powerful repre- sentation learning ability of modern Convolutional Neural Networks (CNNs) to the graph data [7]. graph convolutional layer typically consists of two stages: linear feature propagation and non- linear feature transformation. Simple Graph Convolution (SGC) [21] simplifies GCNs by removing the nonlinearities between GCN layers and collapsing the resulting function into a single linear transformation, which is followed by single linear classification layer and then becomes linear GCN. SGC can achieve comparable performance to canonical GCNs while being much more com- putationally efficient and using significantly fewer parameters. Thus, we mainly focus on linear GCNs this paper.
Although being comparable to canonical GCNs, SGC still suffers from a similar issue as non-linear GCNs, that is, more (linear) feature propagation steps K will degrade the performance catastroph- ically. This issue is widely characterized as the "over-smoothing" phenomenon. Namely, node features become smoothed out and indistinguishable after too many feature propagation steps [10].
In this work, through a dissection of the diffusion process of linear GCNs, we characterize funda- mental limitation of SGC. Specifically, we point that its feature propagation step amounts very coarse finite difference with fixed step size Al 1, which results in a large numerical error.
Corresponding author: Yisen Wang biisenwwang @ pku.edu.cn).
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

And because the step size is fixed, more feature propagation steps will inevitably lead to a large terminal time T= K At + oo that over-smooths the node features.
To address these issues, we propose Decoupled Graph Convolution (DGC) by decoupling the termi- nal time T and propagation steps K. In particular,
flexibly choose continuous terminal time T' for the optimal tradeoff' between under-smoothing and over-smoothing, and then fix the terminal time while adopting more propagation steps K. In this way, different from SGC that over-smooths with more propagation steps, our proposed DGC can obtain more fine-grained finite difference approximation with more propagation steps, which contributes to the final performance both theo- retically and empirically. Extensive experiments show that DGC (as a linear GCN) improves over SGC significantly and obtains sfute-o--hh-asee results that are comparable to many modern non-linear GCNs. Our main contributions are summarized as follows:
We investigate SGC by dissecting its diffusion process from a continuous perspective, and characterize why it cannot benefit from more propagation steps.
We propose Decoupled Graph Convolution (DGC) that decouples the terminal time T and the propagation steps K, which enables us to choose a continuous terminal time flexibly while benefiting from more propagation steps from both theoretical and empirical aspects.
Experiments show that DGC outperforms canonical GCNs significantly and obtains state- of-the-art (SOTA) results among linear GCNs, which is even comparable to many competi- tive non-linear GCNs. We think DGC can serve as a strong baseline for the future research.
2
Related Work
Graph convolutional networks (GCNs). To deal with non-Euclidean graph data, GCNs are pro- posed for direct convolution operation over graph, and have drawn interests from various domains. GCN is firstly introduced for a spectral perspective [26, 7]. but soon it becomes popular as general message passing algorithm in the spatial domain. Many variants have been proposed to improve its performance, such as GraphSAGE [5] with LSTM and GAT with attention mechanism [19].
Over-smoothing issue. GCNs face a fundamental problem compared standard CNNs, i.e., the over-smoothing problem. Li el al. [10] offer a theoretical characterization of over-smoothing based on linear feature propagation. After that, many researchers have tried to incorporate effective mech- anisms in CNNs to alleviate over-smoothing. DeepGCNs [9] shows that residual connection and di- lated convolution can make GCNs go as deep as CNNs, although increased depth does not contribute much. Methods like APPNP [8] and JKNet [25] avoid over-smoothing by aggregating multiscale information from the first hidden layer. DropEdge [16] applies dropout to graph edges and find enables training GCNs with more layers. PairNorm [27] regularizes the feature distance to be close to the input distance, which will not fail catastrophically but still decrease with more layers.
Continuous GCNs. Deep CNNs have been widely interpreted from a continuous perspective, e.g., ResNet [6] as the Fuler discretization of Neural ODEs [11, 3]. This viewpoint has recently been borrowed to understand and improve GCNs, GCDE [15] directly extends GCNs to a Neural ODE, while CGNN [22] devises a GCN variant inspired by new continuous diffusion. Our method is also inspired by the connection between discrete and continuous graph diffusion, but alternatively, we focus on their numerical gap and characterize how affects the final performance.
Linear GCNs SGC [21] simplifies and separates the two stages of GCNs: feature propagation and (non-linear) feature transformation. It finds that utilizing only simple logistic regression after feature propagation (removing the non-linearities). which makes it a linear GCN, can obtain com- parable performance canonical GCNs. In this paper, we further show that a properly designed linear GCN (DGC) can be on-par with state-of-the-art non-linear GCNs while possessing many desirable properties. For example, as linear model, DGC requires much fewer parameters than non-linear GCNs, which makes it very memory efficient, and meanwhile, its training is also much faster (~ 100x) than non-linear models as it could preprocess all features before training.
3 Dissecting Linear GCNs from Continuous Dynamics
In this section, we make a brief review SGC [21] in the context of semi-supervised node classifi- cation task, and further point out its fundamental limitations.

---

3.1 Review of Simple Graph Convolution (SGC)
Define a graph as g A), where (Ui...., Un denotes the vertex set of n nodes, and A E R=x= is an adjacency matrix where ag denotes the edge weight between node vi and ey- The degree matrix D diag(dı..... :d,...;;dd) dn) of A is a diagonal matrix with its i-th diagonal entry as d, Σj Mij- Each node v; is represented by d-dimensional feature vector x; E IRd and denote the feature matrix as X E Raxd [xi...., xn). Each node belongs to one out of C classes,
denoted by one-hot vector y; E 1J. In node classification problems, only subset of nodes Vi C V is labeled and we want to predict the labels of the rest nodes Vu = VVV-
SGC shows that we can obtain similar performance with simplified GCN,
(1) which pre-processes the node features X with K linear propagation steps, and then applies linear classifier with parameter @ Specifically, at the step k. each feature x, is computed by aggregating features in its local neighborhood. which can be done in parallel over the whole graph for K steps.
YSGC softmax (S* (x);
( + S where -ー - AD-
x s
Here À A is the adjacency matrix augmented with the self-loop I, D the degree matrix of A, and S denotes the symmetrically normalized adjacency matrix. This step exploits the local graph structure to smooth out the noise in each node.
At last, SGC applies a multinomial logistic regression (a.ka. softmax regression) with parameter + to predict the node labels YsaC from the node features of the last propagation step X (K);
YSGC = softmax
(x
(3)
)) steps are linear, SGC is essentially a linear version of GCN that only relies on linear features from the input.
Because both the feature propagation (S X) and classification (X (x)
3.2 Equivalence between SGC and Graph Heat Equation
Previous analysis of linear GCNs focuses on their asymptotic behavior as propagation steps K + oo (discrete), known as the over-smoothing phenomenon [10]. In this work, we instead provide novel non-asymptotic characterization of linear GCNs from the corresponding continuous dynamics, graph heat equation [4]. A key insight is that we notice that the propagation of SGC can be seen equiva- lently as a (coarse) numerical discretization of the graph diffusion equation, as we show below.
Graph Heat Equation (GHE) is well-known generalization of the heat equation on graph data, which is widely used to model graph dynamics with applications in spectral graph theory [4], time series [12], combinational problems [13], etc. In general, GHE can be formulated follows:
dX. de
LX,, = =X,
X
0) refers to the evolved input features at time I, and L refers to the graph Laplacian matrix. Here, for the brevity of analysis, we take the symmetrically normalized graph Laplacian for
where X, (1 2
the augmented adjacency À and overload the notation as L= D D A - S.
D-
As GHE is a continuous dynamics, in practice we need to rely on numerical methods to solve it. We find that SGC can be seen coarse finite difference of GHE. Specifically, apply the forward Euler method to Eq. (4) with an interval At:
X =X,- A/LX, - At(I S)X, = [(1 At)I - A/S) X.
(5)
By involving the update rule for K forward steps, we will get the final features X, at the terminal time T At:
X - - where ( = (1 - I ArS. Comparing to Eq. (2),
(6)
that the Euler discretization of GHE becomes SGC when the step size At = 1. Specifically, the diffusion matrix S(A)) reduces to the SGC diffusion matrix S and the final node features, Xy and (K), become equivalent. Therefore, SGC with K propagation steps essentially finite difference approximation to GHE with K forward steps (step size Al = 1 and terminal time T = K).
3

---

3.3 Revealing the Fundamental Limitations of SGC
Based on the above analysis, we theoretically characterize several fundamental limitations of SGC: feature over weer-snothing, large numerical errors and large learning risks. Proofs are in Appendix B.
Theorem 1 (Oversmoothing from a spectral view). Assume that the eigendecomposition of the Laplacian matrix as L Σ S, with eigemaauus X and eigenvectors u,- Then, the heat equation (Eq. (4)) admits closed-form solution time t, known the heat kernel H, e 2i=1 e u,u," As t + oc, H, asymptotically converges to a non-inoormative equilibrium as t. 00, due to the non-trivial (i.e., positive) eigenvalues vanishing:
lim e Act = [0, [0, 1-00
if>; 0 if 1 ,..,.. n.
11 =
Remark 1. In steps K - will inevitably lead over-smoothed non-informative features.
K. Thus, according to Theorem 1, a large number of propagation
Theorem (Numerical errors). For the initial value problem in Eq. (4) with finite terminal time T, the numerical error of the forward Euler method in Eq. (5) with K steps can be upper bounded by
T
X
(ZTIIII-1)
(8)
2K
Remark Since 7= K in SGC, the upper bound reduces e (e (eTiLl) - 1) (e a constant). We can see that the numerical error will increase exponentially with more propagation steps.
Theorem (Learning risks). Consider a simple linear regression problem (X, Y) on graph, where the observed input features X are generated by corrupting the ground truth features X with the following inverse graph diffusion with time T
dX, dt
LXX, where Xo X and Xx. = X.
(9)
Denote the population risk with ground truth features as R(W) = E Y
X. W| and that of Supposing that
Euler method applied input X (Eq. (5)) as R(W) = Y
| Y
XW
X 2 M oC, we have the following upper bound:
R(W) R(W) + 2/
E [
[x)
||
M
e
|e - =1l")
(10)
Remark 3. Following Theorem 3, we can see that the upper bound can be minimized by finding an optimal terminal time such that T T and minimizing the numerical error %
(K)
While
SGC fixes the step size At = 1, thus T and K are coupled together, which makes it less flexible to minimize the risk in Eq. (10).
The Proposed Decoupled Graph Convolution (DGC)
In this section, we introduce our proposed Decoupled Graph Convolution (DGC) and discuss how it overcomes the above limitations of SGC.
4.1 Formulation
Based on the analysis in Section 3.3, we need to resolve the coupling between propagation steps K and terminal time T caused by the fixed time interval At Therefore, we regard the terminal time T and the propagation steps K as two free byperparameters in the numerical integration via flexible time interval. In this way, the two parameters can play different roles and cooperate together to attain better results: 1) we can fiexibly choose 7 to tradeoff between under-smoothing and over- smoothing to find sweet spot for each dataset; and 2) given an optimal terminal time we can also flexibly increase the propagation steps K for better numerical precision with At = T/ K + 0.

---

(K-50)
T-0
T+1
T-5.3
T-50
Acc-57.9
Acc
Reed T (T-5.3)
8x1
K-55
Acc-57.9
Acc:17.8
Acc-82.
Acce 82.8
Acc-82.9
Figure I: 1-SNE input feature visualization and the corresponding test accuracy (%) under different terminal time (T) and different number of propagation steps (K). Experiments conducted with ours DGC-Euler model on the Cora dataset. Each point represents node in the graph and its color denotes the class of the node.
In practice, moderate number of steps sufficient attain the best classification accuracy, hence we can also choose a minimal K among the best for computation efficiency.
Formally, propose our Decoupled Graph Convolution (DGC) follows:
YDGC softmax
X θ
where X,- ode dede_int(X,,)) At, K).
(11)
Here ode iintiitttn.t At, K) refers to the numerical integration of the graph heat equation that starts from X and runs for K steps with step size At. Here, we consider two numerical schemes: the forward Euler method and the Runge-Kutta (RK) method.
DGC-Euler. As discussed previously. the forward Euler gives an update rule as in Eq. (5). With terminal time T and step size At = T/K, we can obtain X, after K propagation steps:
X, [S(T/KK] X, where ((T/K) = ( 1+ . S.
(12)
DGC-RK. Alternatively, we can apply higher-order finite difference methods to achieve better nu- merical precision, the cost of more function evaluations intermediate points. One classical method is the 4th-order Runge- (RK) method, which proceeds with
8 &, A (R, 2R2 + 2R, + R4)
S(50 X,
(13)
where
R X R₂ = X A/LR, R3 X, - ALLR, R. = X₁ AILRa.
(14)
Replacing the propagation matrix S(T/K) in DGC-Euler with the RK-matrix (T/K) we can get 4th-order model, namely DGC-RK, whose numerical error can be reduced to O(1/K" K*) order.
Remark. In GCN [7], self-loop I is heuristically introduced in the adjacency matrix À A +I to prevent numerical instability with more steps K. Here, we notice that the DGC-Euler diffusion matrix (At) (1 I+) AtS naturally incorporates the self-loop into the diffusion process as momentum term, where At flexibly tradeoffs information from the self-loop and the neighborhood. Therefore, in DGC, can also remove the self-loop from À and increasing K is still numerically stable with fixed T. We name the resulting model as DGC-sym with symmetrically normalized adjacency matrix Saym = D AD-AA which aligns with the canonical normalized graph Laplacian Laym = D (D A) Laplacians from spectral perspective, L
I Sgym in the spectral graph theory [4]. Comparing the two has smaller spectral range than Laym [21]. According to Theorem 2, L will have faster convergence rate of numerical error.
5

---

Table I: A comparison of propagation rules. Here ( E X represents input features after k feature propagation steps and X = X; H denotes the hidden features of non-linear GCNs at layer k; W denotes the weight matrix; o refers a activation function; a, B are coefficients.
Method
Type
Propagation rule
GCN [7]
Non-linear
H (SH (k-11)
APPNP [8]
Non-linean
H (1 aHHHH k-1) + aH
CGNN [22]
Non-linear
(k) (1 a- 1/ W HO)
SGC [21]
Linear
x (X)--1) -T(K)- S
DGC-Euler (ours)
Linear
X (4) = (1- ((k-1) + +TT/K)
4.2 Verifying the Benefits DGC
Here we demonstrate the advantages of DGC both theoretically and empirically.
Theoretical benefits. Revisiting Section 3.3, DGC can easily alleviate the limitations of existing linear GCNs shown in Remarks 1, by decoupling T and K.
For Theorem 1, by choosing a fixed terminal time T with optimal tradeoff, increasing the propagation steps K in DGC will not lead to over-smoothing in SGC;
For Theorem 2, with T is fixed, using more propagation steps (K - xc) in DGC will help
minimize the numerical error er
[K) with a smaller step size Al = T/K + 0;
For Theorem 3, by combining flexibly chosen optimal terminal time T and minimal numerical error with a large number of steps K, we can get minimal learning risks.
Empirical evidence. To further provide an intuitive understanding of DGC, we visualize the propa- gated input features of our proposed DGC-Euler on the Cora dataset in Figure 1. The first row shows that there exists an optimal terminal time T for each dataset with the best feature separability (e.g., 5.3 for Cora). Either a smaller T (under-smooth) up and make them more indistinguishable, which eventually leads to lower accuracy. From the sec- ond row, we can see that, with fixed optimal T. too large step size AL (i.e., too small propagation steps K) will lead to feature collapse, while gradually increasing the propagation steps K makes the nodes of different classes more separable and improve the overall accuracy.
larger T (over-smooth) will mix the features
4.3 Discussions
To highlight the difference of DGC to previous methods, we summarize their propagation rules in Table 1. For non-linear methods, GCN [7] uses the canonical propagation rule which has the oversmoothing issue, while APPNP [8] and CGNN [22] address it by further aggregating the initial hidden state (0) repeatedly at each step. In particular, we emphasize that our DGC-Euler differ- ent from APPNP in terms of the following aspects: 1) DGC-Euler is linear model and propagates on the input features x(k while APPNP is non-linear and propagates non-linear embedding (k) 2) at each step, APPNP aggregates features from the initial step H)),, while DGC-Fuler aggregates features from the last step X (k)1) 3) APPNP aggregates a large amount (1 - a) of the propagated features (- while DGC-Euler only takes a small step At (T/K) towards the new features (k-)) For linear methods, SGC has several fundamental limitations as analyzed in Section 3.3, while DGC addresses them by flexible and fine-grained numerical integration of the propagation process.
Our dissection of linear GCNs also suggests different understanding of the over-smoothing prob- lem. As shown Theorem 1, over-smoothing is an inevitable phenomenon of (canonical) GCNs, while we can find terminal time to achieve an optimal tradeoff between under-smoothing and over- smoothing. However, we cannot expect more layers can bring more profit if the terminal time goes to infinity, that is, the benefits of more layers can only be obtained under a proper terminal time.

---

Table Test accuracy (%) of semi-supervised node classification on citation networks.
Type
Method
Cora
Citeseer
Pubmed
GCN [7]
81.5
70.3
79.0
GAT [19]
83.0 + 0.7
72.5 = 0.7
79.0 = 0.3
GraphSAGE [5]
82.2
71.4
75.8
JKNet [25]
81.1
69.8
78.1
Non-linear
APPNP [8]
83.3
71.8
80.1
GWWN [24]
82.8
71.7
79.1
GraphHeat [23]
83.7
72.5
80.5
CGNN [22]
84.2 = 0.6
71.8 0.7
76.8 = 0.6
GCDE [15]
83.8 + 0.5
72.5 + 0.5
79.9 + 0.3
Label Propagation [28]
45.3
68.0
63.0
DeepWalk [14]
70.7 0.6
0.5
76.8 1 0.6
Linear
SGC [21]
81.0 0.0
78,9 7.1
SGC-PairNorm [27]
81.1
70.6
78.2
SIGN-lineat [17]
81.7
72.4
78.6
DGC (ours)
83.3 - 0.0
73.3 = 0.1
80.3 + 0.1
Experiments
In this section, we conduct a comprehensive analysis on DGC and compare it against both linear and non-lincar GCN variants on collection of benchmark datasets.
5.1 Performance on Semi-supervised Node Classification
Setup. For semi-supervised node classification, we use three standard citation networks, Cora, Citeseer, and Pubmed [18] and adopt the standard data split as in [7, 19, 24, 23, 15]. Here, we compare DGC against several representative non-linear and linear methods that also adopts the standard data split. For non non-linear GCNs, we include I) classical baselines like GCN [7], GAT [20], GraphSAGE [5], APPNP [8] and JKNet [25]; spectral methods using graph heat kernel [24, 23]; and 3) continuous GCNs [15, 22]. For linear methods, we present the results Label Propagation [28], DeepWalk [14]. SGC (linear GCN) [21] well its regularized version SGC-PairNorm [27]. We also consider linear version of SIGN [17], SIGN-linear, which extends SGC by aggregating features from multiple propagation stages (K 1, ...). ). For DGC, adopt the Euler scheme, Le., DGC-Euler (Eq. (12)) by default for simplicity. We report results averaged over 10 random Data statistics and training details are in Appendix A.
We compare DGC against both linear and non-linear baselines for the semi-supervised node classi- fication task, and the results are shown in Table 2.
DGC v.S. linear methods. We can see that DGC shows significant improvement over previous linear methods across three datasets. In particular, compared to SGC (previous SOTA methods), DGC obtains 83.3 v.s. 81.0 on Cora, 73.3 v.s. 71.9 on Citeseer and 80.3 v.s. 78.9 on Pubmed. This shows that in real-world datasets, flexible and fine-grained integration by decoupling T and K indeed helps improve the classification accuracy SGC by a large margin. Besides, DGC also outperforms the multiscale SGC, SIGN-linear, suggesting that multiscale techniques cannot fully solve the limitations of SGC, while DGC can overcome these limitations by decoupling T and K. As discussed in Appendix C, DGC still shows clear advantages over SIGN when controlling the terminal time T while being more computationally efficient, which indicates that the advantage of DGC is not only real-valued 7,, but also the improved numerical precision by adopting large K.
DGC v.s. non-linear models. Table further shows that DGC, a linear model, even outper- forms many non-linen linear GCNs on semi-supervised tasks. First, DGC improves over classical GCNs like GCN [7], GAT [19] and GraphSAGE [5] by a large margin. Also, DGC comparable to, and sometimes outperforms, many modern non-linear GCNs. For example, DGC shows a clear advan- tage over multiscale methods like JKNet [25] and APPNP [8]. DGC is also comparable to spectral methods based on graph heat kernel, e.g. GWWN [24], GraphHeat [23], while being much more

---

Table Test accuracy (%) of fully-supervised node classification on citation networks.
Type
Method
Cora
Citeseer
Pubmed
GCN [7]
85.8
73.6
88.1
Non-linear
GAT [19]
86.4
74.3
87.6
JK-MaxPool [25]
89.6
77.7
JK-Concat [25]
89.1
78.3
JK-LSTM [25]
85.8
74.7
APPNP [8]
90.2
79.8
86.3
SGC [21]
85.8
78.1
83.3
Linear
DGC (ours)
88.2 0.0
78.7 + 0.0
89.4 0.0
efficient simple linear model. Besides, compared non-linear continuous models like GCDE [15] and CGNN [22], DGC also achieves comparable accuracy only using simple linear dynamic.
5.2 Performance on Fully-supervised Node Classification
Setup. For fully-supervised node classification, also the three citation networks, Cora, Cite- seer and Pubmed, but instead randomly split the nodes in three citation networks into 60%, 20% and 20% for training, validation and testing, following the previous practice in [25]. Here, we include the baselines that also have reported results in the fully supervised setting, such as GCN [7]. GAT [19] (reported baselines in [25]), and the three variants of JK-Net: JK-MaxPool, JK-Coneat and JK-LSTM [25]. Besides, we also reproduce the result of APPNP [8] for a fair comparison. Dataset statistics and training details are described in Appendix.
Results. The results of the fully-supervised semi-classification task are basically consistent with the semi-supervised setting. As linear method, DGC not only improves the state-of-the-art linear GCNs by a large margin, but also outperforms GCN [7]. GAT [19] significantly. Besides, DGC is also comparable multiscale methods like JKNet [25] and APPNP [8], showing that good linear model like DGC is also competitive for fully-supervised tasks.
5.3 Performance on Large Scale Datasets
Setup. More rigorously, also conduct the comparison on a large-scale node classification dataset, the Reddit networks
Table 4: Test accuracy (%) comparison with in- ductive methods large scale dataset, Red- dit. Reported results are averaged over 10 runs. OOM: out of memory.
[5]. Following SGC [21], we adopt the inductive setting, where we use the subgraph of training nodes as train- ing data and use the whole graph for the valida- tion/testing data. For a fair comparison, we use the same training configurations as SGC [21] and include reported baselines, such as GCN [7], FastGCN [2], three variants of GraphS AGE [5]. and RandDGI (DGI with randomly initial- ized encoder) [20]. We also include APPNP [8] for a comprehensive comparison.
Type
Method
Acc.
GCN [7]
OOM
Fas1GCN [2]
93.7
GraphSAGE-GCn [5]
93.0
Non-linear
GraphSAGE- mean [5]
95.0
GraphSAGE-LLTM [5]
95.4
APPNP [8]
95.0
Results. We can see DGC still achieves the best accuracy among linear methods and im- prove 0.9% accuracy over SGC. Meanwhile, it
RandDGI [20]
93.3
Linear
SGC [21]
94.9
superior to the three variants of GraphSAGE as well as APPNP. Thus, DGC is still the state- of-the-art linear GCNs and competitive against nonlinear GCNs on large scale datasets.
DGC (ours)
95.8

---

Over smoothing more depth
Robustness Comsorison
Compuration Comparison
WAC Can
D&C Gaia
D0C2
93.
80.0
500, Cleoser
-9
DAC (1-11
DAC (T6-2)
9:00 Puliced
Dao Puiree
Text dww mo
50026/21
GMKN
AT1x
BAR (T-1
533
88
430
17.0
313
Reatov Total Traiing Time
Figure 2: Left: test accuracy (%) with increasing feature propagation steps on Cora. Middle: com- parison of robustness under different noise scales three citation networks. Right: comparison of relative total training time for 100 epochs on the Pubmed dataset.
Table 5: Comparison of explicit computation time of different training stages on the Pubmed dataset with a single NVIDIA GeForce RTX 3090 GPU.
Type
Method
Preprocessing Time
Training Time
Total Time
SGC (K 2) [21]
3.8 ms
61.5 ms
65.3 ms
Linear
DGC (K = 2) (ours)
3.8 ms
61.5 ms
65.3 ms
DGC (K 100) (ours)
169.2 ms
55.8 ms
225.0 ms
Nonlinear
GCN [7]
17.0 s
17.0
5.4 Empirical Understandings of DGC
Setup. Here we further provide comprehensive analysis of DGC. First, we compare its over- smoothing behavior and computation time against previous methods. Then we analyze several fac- tors that affect the performance of DGC, including the Laplacian matrix L, the numerical schemes and the terminal time T. Experiments are conducted on the semi-supervised learning tasks, and we adopt DGC-Euler with the default hyperparameters unless specified.
Non-over-smoothing with increasing steps. In the left plot of Figure 2, we compare different GCNs with increasing model depth (non-linear GCNs) or propagation steps (linear GCNs) from 2 to 1000. Baselines include SGC [21], GCN [7], and our DGC with three different terminal time T (1, 5.3, 10). First, we notice that SGC and GCN fail catastrophically when increasing the depth, which consistent with the previously observed over-smoothing phenomenon. Instead, all three DGC variants can benefit from increased steps. Nevertheless, the final performance will degrade if the terminal time is either too small (T = 1, under-smoothing) or too large (T = 10, over-smoothing). DGC enables to flexibly find the optimal terminal time (T 5.3). Thus, can obtain the optimal accuracy with an optimal tradeoff between
smoothing and over-smoothing.
Robustness to feature noise. In real-world applications, there are plenty of noise in the collected node attributes, thus it crucial for GCNs to be robust to input noise [1]. Therefore, we compare the robustness of SGC and DGC against Gaussian noise added to the input features, where stands for the standard deviation of the noise. Figure (middle) shows that DGC significantly more robust than SGC across three citation networks, and the advantage is clearer larger noise scales. As discussed in Theorem 3, the diffusion process in DGC can be seen as denoising procedure, and consequently, DGC's robustness to feature noise can be contributed to the optimal tradeoff between over-smoothing and undor-smoothing with a flexible choice of T and K. In comparison, SGC is not as good DGC because it cannot find such sweet spot accurately.
Computation time. In practice, linear GCNs can accelerate training by pre-processing features with all propagation steps and storing them for the later model training. Since pre- pre-processing costs much fewer time than training (<5% in SGC), linear GCNs could be much faster than non-linear ones. As shown in Figure 2 (right), DGC is slightly slower (3x) than SGC, but DGC achieves much higher accuracy. Even so, DGC is still much faster than non-linear GCNs (>100x). Indeed, as further shown in Table 5, the computation overhead of DGC over SGC mainly lies in the preprocessing stage, which is very small in SGC and only leads to around twice longer total time. Instead, GCN is much slower as it involves propagation in each training loop, leading to much slower training.

---

Nutwical
Terninal
60.5
+1.0
140
Tea ToR-ee2
Tear 400. (3)
82.0
15.0
1300
Wihcossflocs
Ruge-Aalt
430
30.3
60.0
Propapriin 100
Popepitoondep
Figure 3: Algorithmic analysis of our proposed DGC. Left: test accuracy (%) of two kinds of Laplacian, L == I- S (with self-loop) and Lyym = I Ssym (without self-loop), with increasing steps K and fixed time T Cora. Middle: test accuracy (%) of two numerical schemes, Euler and Kutge-Kutta, with increasing steps K and fixed T under fixed terminal time on Cora. Right: test accuracy (%) with varying terminal time and fixed steps K on Cora.
Graph Laplacian. As shown in Figure 3 (left), in DGC, both the two Laplacians, (with self-loop) and Laym (without self-loop), can consistently benefit from more propagation steps without leading to numerical issues. Further comparing the two Laplacians, we can see that the augmented Laplacian L obtains higher accuracy than the canonical Laplacian Lyym and requires fewer propagation steps K to obtain good results, which could also be understood from our analysis in Section 3.3.
Numerical scheme. By comparing differrnnt numerical schemes in Figure 3 (middle), we find that the Runge-Kutte Kutta method demonstrates better accuracy than the Euler method with a small K. Nev- ertheless, K increases, the difference gradually vanishes. Thus, the Euler method is sufficient for DGC to achieve good performance, and it is more desirable in terms of its simplicity and efficiency.
Terminal time T. In Figure (right), we com- pare the test accuracy with different terminal time T. We show that indeed, in real-world datasets, there exists sweet spot that achieves the optimal tradeoff between under-smoothing and smotthng. In Table 6, we list the best terminal time that we find on two large graph datasets, Pubmed and Reddit. We can see that T is almost consistent across different Lapla- cians on each dataset, which suggests that the optimal terminal time T is an intrinsic prop- erty of the dataset.
Table 6: Optimal terminal time 7 on the trans- ductive task, Pubmed, and the inductive task, Red- dit, with different Laplacians.
Dataset
Laplacian
T
Acc
6.0
80.3
Pubmed
I- Ssym
6.0
79.8
I S
2.7
95.5
Reddit
I Saym
2.6
95.8
6 Conclusions
In this paper, we have proposed Decoupled Graph Convolution (DGC), which improves signifi- cantly over previous linear GCNs through decoupling the terminal time and feature propagation steps from a continuous perspective. Experiments show that our DGC is competitive with many modern variants of non-linear GCNs while being much more computationally efficient with much fewer parameters learn.
Our findings suggest that, unfortunately, current GCN variants still have not shown significant ad- vantages over properly designed linear GCN. We believe that this would attract the attention of the community to reconsider the actual representation ability of current nonlinear GCNs and propose new alternatives that can truly benefit from nonlinear architectures.
Acknowledgement
Yisen Wang is partially supported by the National Natural Science Foundation of China under Grant 62006153, and Project 2020BD006 supported by PKU-Baidu Fund. Jiansheng Yang supported by the National Science Foundation of China under Grant No. 11961 141007. Zhouchen Lin was supported by the NSF China (No.s 61625301 and 61731018), NSFCTiannur Fund for Mathematics (No. 12026606) and Project 2020BD006 supported by PKU-Baidu Fund.
10

---

References
[1] Alcksandar Bojchevski and Stephan Günnemann. Certifiable robustness to graph perturba- tions. NeurIPS, 2019.
[2] Jie Chen, Tengfei Ma, and Cao Xiao. FastGCN: fast learning with graph convolutional net- works via importance sampling. ICLR, 2018.
[3] Ricky TQ Chen, Yulia Rubanova, Jesse Bettencourt, and David K Duvenaud. Neural ordinary differential equations. NeurIPS, 2018. 2
[4] Fan RK Chung and Fan Chung Graham. Spectral graph theory. American Mathematical
Society, 1997. 3.5
[5] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. NeurIPS, 2017. 8
[6] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. CVPR, 2016. 2
[7] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. ICLR, 2017. 1, 6,
[8] Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnnemann. Predict then propagate: Graph neural networks meet personalized pagerank. ICLR, 2019. 2, 6, 7,8
[9] Guohao Li, Matthias Muller, Ali Thabet, and Bernard Ghanem. DeepGCNs: Can gens go as deep cnns? CVPR, 2019. 2
[10] Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional net- works for semi-supervised learning. AAAI, 2018. 1,2,3
[11] Yiping Lu, Aoxiao Zhong, Quanzheng Li, and Bin Dong. Beyond finite layer neural networks: Bridging deep architectures and numerical differential equations. ICMI, 2018. 2
[12] Georgi S Medvedev. Stochastic stabilly of continuous time consensus protocols. SIAM Journal on Control and Optimization, 50(4): 159-1885, 2012.
[13] Georgi S Medvedev. The nonlinear heat equation on dense graphs and graph limits. SIAM Journal on Mathematical Analysis, 46(4):2743-2766, 2014.
[14] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. DeepWalk: Online learning of social repre- sentations. SIGKDD, 2014. 7
[15] Michael Poli, Stefano Massaroli, Junyoung Park, Atsushi Yamashita, Hajime Asama, and Jinkyoo Park. Graph neural ordinary differential equations. arXiv preprint arXiv: 191107532, 2019. 2, 8 8
[16] Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. DropEdge: Towards deep graph convolutional networks on node classification. ICLR, 2019.
[17] Emanuele Rossi, Fabrizio Frasca, Ben Chamberlain, Davide Eynard, Michael Bronstein, and Federico Monti. SIGN: Scalable inception graph neural networks. arXiv preprint
1xXi:20044111998 2020. 7
[18] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-
Rad. Collective classification in network data. Al Magazine, 29(3):93-95 93, 2008. 7
[19] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. ICLR, 2018. 2, 7,
[20] Petar Velickovic, William Fedus, William L Hamilton, Pietro Liò, Yoshua Bengio, and R De- von Hjelm. Deep graph infomax. ICLR, 2019. 7,8
[21] Felix Wu, Tianyi Zhang, Amauri Holanda de Souza Jr, Christopher Fifty, Tao Yu, and Kilian Q Weinberger. Simplifying graph convolutional networks. ICMI, 2019, 1, 5, 6, 7, 8,

---

[22] Louis-Paseee Xhonneux, Meng Qu, and Jian Tang. Continuous graph neural networks. ICML,
2020. 2. 6,
[23] Bingbing Xu, Huawei Shen, Qi Cao, Keting Cen, and Xueqi Cheng. Graph convolutional
networks using heat kernel for semi-supervised learning. arXiv preprint urXiv:2007.16000 2020.
[24] Bingbing Xu, Huawei Shen, Qi Cao, Yunqi Qiu, and Xueqi Cheng. Graph wavelet neural network. ICLR, 2019.
[25] Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. ICML, 2018. 2, 8 8
[26] Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. ICML,, 2016. 2
[27] Lingxiao Zhao and Leman Akoglu. PairNorm: Tackling oversmoothing in gnns. ICLR, 2020.
2,
[28] Xiaojin Zhu, Zoubin Ghahramani, and John D Lafferty. Semi-supervised learning using gaus- sian fields and harmonic functions. ICML, 2003. 7
12


Reviews:
[{"review_id": "hdbPhWUlvdt", "reviewer": "Reviewer_uCUs", "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.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n\n1. 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. \n\n2. 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.\n\n3. 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.\n\nCons:\n\n1. 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.\n\n2. 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.\n\n3. 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"ethical_concerns": "No.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6hrs"}, "extra_text": {}}, {"review_id": "dWEBRjj93KD", "reviewer": "Reviewer_Cbfn", "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).", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength：\n- 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.\n- 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. \n- 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. \n\nWeakness:\n- 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?\n- 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?\n- The authors showed the robustness to feature noise in Sec. 5.4, but I am curious to know why DGC is better here?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "see the above weakness.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "LeCitDScTJQ", "reviewer": "Reviewer_isgE", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nConcerns:\n\n1. 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$.\n2. 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.\n3. 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.\n4. Theorem 1 is not too novel compared with results (around Proposition 1) in [2] that GCN asymptotically converges to non-informative equilibrium.\n5. 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.\n\nTypos:\n\n1. in lines 30-31 of appendix, both $n$ should be $k$.\n2. in line 46 of appendix, the left square bracket is not at the appropriate position in the first inequality.\n3. re-statement of Theorem 3 in appendix is not consistent with that in the main text.\n\n[1] Sign: Scalable inception graph neural networks. F Frasca, E Rossi, D Eynard, B Chamberlain, M Bronstein, F Monti.\n\n[2] Graph Neural Networks Exponentially Lose Expressive Power for Node Classification. K Oono, T Suzuki.\n\nTherefore, 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.\n\n======================== post rebuttal =======================\n\nI would like to increase my score from 5 to 6 based on authors' responses.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "EdriHSH_8Oa", "reviewer": "Reviewer_1oqx", "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. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\n1.\tThe 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.  \n2.\tThe 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. \n3.\tLots 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. \n\nWeakness:\n1.\tThe background on linear GCNs may not be clear. Why do we need to study linear GCN? Most of current models are non-linear. \n2.\tThe difference between with self loop and without self loop?\n3.\tThe authors used the step-size to be T/K. Why exactly T/K? can we use larger or smaller than T/K?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No significant social risk", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

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)