Dissecting the Diffusion Process in Linear Graph Convolutional Networks
Year: 2022

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. Code is available at https://github.com/yifeiwang77/DGC.

heading: 1 Introduction
text: Recently, Graph Convolutional Networks (GCNs) have successfully extended the powerful representation learning ability of modern Convolutional Neural Networks (CNNs) to the graph data [7]. A graph convolutional layer typically consists of two stages: linear feature propagation and nonlinear 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 a single linear classification layer and then becomes a linear GCN. SGC can achieve comparable performance to canonical GCNs while being much more computationally efficient and using significantly fewer parameters. Thus, we mainly focus on linear GCNs in 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 catastrophically. 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 a fundamental limitation of SGC. Specifically, we point out that its feature propagation step amounts to a very coarse finite difference with a fixed step size ∆t = 1, which results in a large numerical error.
∗Corresponding author: Yisen Wang (yisen.wang@pku.edu.cn).
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
And because the step size is fixed, more feature propagation steps will inevitably lead to a large terminal time T = K ·∆t→∞ that over-smooths the node features. To address these issues, we propose Decoupled Graph Convolution (DGC) by decoupling the terminal time T and propagation stepsK. In particular, we can flexibly choose a 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 a more fine-grained finite difference approximation with more propagation steps, which contributes to the final performance both theoretically and empirically. Extensive experiments show that DGC (as a linear GCN) improves over SGC significantly and obtains state-of-the-art 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 stateof-the-art (SOTA) results among linear GCNs, which is even comparable to many competitive non-linear GCNs. We think DGC can serve as a strong baseline for the future research.

heading: 2 Related Work
text: Graph convolutional networks (GCNs). To deal with non-Euclidean graph data, GCNs are proposed 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 a 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 to standard CNNs, i.e., the over-smoothing problem. Li et al. [10] offer a theoretical characterization of over-smoothing based on linear feature propagation. After that, many researchers have tried to incorporate effective mechanisms in CNNs to alleviate over-smoothing. DeepGCNs [9] shows that residual connection and dilated 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 it 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 Euler 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 a 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 it 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 a simple logistic regression after feature propagation (removing the non-linearities), which makes it a linear GCN, can obtain comparable performance to 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 a 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 (∼ 100×) than non-linear models as it could preprocess all features before training.

heading: 3 Dissecting Linear GCNs from Continuous Dynamics
text: In this section, we make a brief review of SGC [21] in the context of semi-supervised node classification task, and further point out its fundamental limitations.

heading: 3.1 Review of Simple Graph Convolution (SGC)
text: Define a graph as G = (V,A), where V = {v1, . . . , vn} denotes the vertex set of n nodes, and A ∈ Rn×n is an adjacency matrix where aij denotes the edge weight between node vi and vj . The degree matrix D = diag(d1, . . . , dn) of A is a diagonal matrix with its i-th diagonal entry as di = ∑ j aij . Each node vi is represented by a d-dimensional feature vector xi ∈ Rd, and we denote the feature matrix as X ∈ Rn×d = [x1, . . . ,xn]. Each node belongs to one out of C classes, denoted by a one-hot vector yi ∈ {0, 1}C . In node classification problems, only a subset of nodes Vl ⊂ V is labeled and we want to predict the labels of the rest nodes Vu = V\Vl. SGC shows that we can obtain similar performance with a simplified GCN,
ŶSGC = softmax ( SKXΘ ) , (1)
which pre-processes the node features X with K linear propagation steps, and then applies a linear classifier with parameter Θ. Specifically, at the step k, each feature xi is computed by aggregating features in its local neighborhood, which can be done in parallel over the whole graph for K steps,
X(k) ← SX(k−1), where S = D̃− 12 ÃD̃− 12 =⇒ X(K) = SKX. (2) Here Ã = A + I is the adjacency matrix augmented with the self-loop I, D̃ is 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.k.a. softmax regression) with parameter Θ to predict the node labels ŶSGC from the node features of the last propagation step X(K):
ŶSGC = softmax ( X(K)Θ ) . (3)
Because both the feature propagation (SKX) and classification (X(K)Θ) steps are linear, SGC is essentially a linear version of GCN that only relies on linear features from the input.

heading: 3.2 Equivalence between SGC and Graph Heat Equation
text: Previous analysis of linear GCNs focuses on their asymptotic behavior as propagation stepsK →∞ (discrete), known as the over-smoothing phenomenon [10]. In this work, we instead provide a 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 equivalently as a (coarse) numerical discretization of the graph diffusion equation, as we show below.
Graph Heat Equation (GHE) is a 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 as follows:{
dXt dt = −LXt, X0 = X, (4)
where Xt (t ≥ 0) refers to the evolved input features at time t, and L refers to the graph Laplacian matrix. Here, for the brevity of analysis, we take the symmetrically normalized graph Laplacian for the augmented adjacency Ã and overload the notation as L = D̃− 1 2 ( D̃− Ã ) D̃− 1 2 = I− S.
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 as a coarse finite difference of GHE. Specifically, we apply the forward Euler method to Eq. (4) with an interval ∆t:
X̂t+∆t =X̂t −∆tLX̂t = X̂t −∆t(I− S)X̂t = [(1−∆t)I + ∆tS] X̂t. (5) By involving the update rule for K forward steps, we will get the final features X̂T at the terminal time T = K ·∆t:
X̂T = [S (∆t)]KX, where S(∆t) = (1−∆t)I + ∆tS. (6)
Comparing to Eq. (2), we can see that the Euler discretization of GHE becomes SGC when the step size ∆t = 1. Specifically, the diffusion matrix S(∆t) reduces to the SGC diffusion matrix S and the final node features, X̂T and X(K), become equivalent. Therefore, SGC with K propagation steps is essentially a finite difference approximation to GHE with K forward steps (step size ∆t = 1 and terminal time T = K).

heading: 3.3 Revealing the Fundamental Limitations of SGC
text: Based on the above analysis, we theoretically characterize several fundamental limitations of SGC: feature over-smoothing, 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 = ∑n i=1 λiuiu > i , with eigenvalues λi and eigenvectors ui. Then, the heat
equation (Eq. (4)) admits a closed-form solution at time t, known as the heat kernel Ht = e−tL =∑n i=1 e −λituiu > i . As t → ∞, Ht asymptotically converges to a non-informative equilibrium as t→∞, due to the non-trivial (i.e., positive) eigenvalues vanishing:
lim t→∞
e−λit = { 0, if λi > 0 1, if λi = 0 , i = 1, . . . , n. (7)
Remark 1. In SGC, T = K ·∆t = K. Thus, according to Theorem 1, a large number of propagation steps K →∞ will inevitably lead to over-smoothed non-informative features. Theorem 2 (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∥∥∥e(K)T ∥∥∥ ≤ T‖L‖‖X0‖2K (eT‖L‖ − 1) . (8) Remark 2. Since T = K in SGC, the upper bound reduces to c · ( eT‖L‖ − 1 ) (c is a constant). We can see that the numerical error will increase exponentially with more propagation steps. Theorem 3 (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 Xc with the following inverse graph diffusion with time T ∗ :
dX̃t dt = LX̃t, where X̃0 = Xc and X̃T∗ = X. (9)
Denote the population risk with ground truth features as R(W) = E ‖Y −XcW‖2 and that of Euler method applied input X (Eq. (5)) as R̂(W) = E ∥∥∥Y − [S(∆t)]K XW∥∥∥2 . Supposing that E‖Xc‖2 = M <∞, we have the following upper bound:
R̂(W) < R(W) + 2‖W‖2 ( E ∥∥∥e(K)
T̂ ∥∥∥2 +M ∥∥∥eT?L∥∥∥2 · ∥∥∥e−T?L − e−T̂L∥∥∥2) . (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 ∥∥∥e(K) T̂
∥∥∥. While SGC fixes the step size ∆t = 1, thus T and K are coupled together, which makes it less flexible to minimize the risk in Eq. (10).

heading: 4 The Proposed Decoupled Graph Convolution (DGC)
text: In this section, we introduce our proposed Decoupled Graph Convolution (DGC) and discuss how it overcomes the above limitations of SGC.

heading: 4.1 Formulation
text: 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 ∆t = 1. Therefore, we regard the terminal time T and the propagation steps K as two free hyperparameters in the numerical integration via a flexible time interval. In this way, the two parameters can play different roles and cooperate together to attain better results: 1) we can flexibly choose T to tradeoff between under-smoothing and oversmoothing to find a sweet spot for each dataset; and 2) given an optimal terminal time T , we can also flexibly increase the propagation steps K for better numerical precision with ∆t = T/K → 0.
In practice, a moderate number of steps is sufficient to attain the best classification accuracy, hence we can also choose a minimal K among the best for computation efficiency.
Formally, we propose our Decoupled Graph Convolution (DGC) as follows: ŶDGC = softmax ( X̂TΘ ) , where X̂T = ode_int(X,∆t,K). (11)
Here ode_int(X,∆t,K) refers to the numerical integration of the graph heat equation that starts from X and runs for K steps with step size ∆t . 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 ∆t = T/K, we can obtain X̂T after K propagation steps:
X̂T = [ S(T/K) ]K X, where S(T/K) = (1− T/K) · I + (T/K) · S. (12)
DGC-RK. Alternatively, we can apply higher-order finite difference methods to achieve better numerical precision, at the cost of more function evaluations at intermediate points. One classical method is the 4th-order Runge-Kutta (RK) method, which proceeds with
X̂t+∆t = X̂t + 1
6 ∆t (R1 + 2R2 + 2R3 + R4)
∆ = S (∆t) RK X̂t, (13)
where
R1 = X̂k, R2 = X̂k − 1
2 ∆tLR1, R3 = X̂k −
1 2 ∆tLR2, R4 = X̂k −∆tLR3. (14)
Replacing the propagation matrix S(T/K) in DGC-Euler with the RK-matrix S(T/K)RK , we can get a 4th-order model, namely DGC-RK, whose numerical error can be reduced to O(1/K4) order.
Remark. In GCN [7], a self-loop I is heuristically introduced in the adjacency matrix Ã = A + I to prevent numerical instability with more steps K. Here, we notice that the DGC-Euler diffusion matrix S(∆t) = (1−∆t)I+∆tS naturally incorporates the self-loop I into the diffusion process as a momentum term, where ∆t flexibly tradeoffs information from the self-loop and the neighborhood. Therefore, in DGC, we can also remove the self-loop from Ã and increasing K is still numerically stable with fixed T . We name the resulting model as DGC-sym with symmetrically normalized adjacency matrix Ssym = D− 1 2 AD− 1 2 , which aligns with the canonical normalized graph Laplacian Lsym = D − 12 (D−A) D− 12 = I − Ssym in the spectral graph theory [4]. Comparing the two Laplacians from a spectral perspective, L = I − S has a smaller spectral range than Lsym [21]. According to Theorem 2, L will have a faster convergence rate of numerical error.

heading: 4.2 Verifying the Benefits of DGC
text: 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, 2, 3 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 as in SGC;
• For Theorem 2, with T is fixed, using more propagation steps (K →∞) in DGC will help minimize the numerical error ∥∥∥e(K)T ∥∥∥ with a smaller step size ∆t = T/K → 0; • For Theorem 3, by combining a 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 propagated 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) or a larger T (over-smooth) will mix the features up and make them more indistinguishable, which eventually leads to lower accuracy. From the second row, we can see that, with fixed optimal T , too large step size ∆t (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.

heading: 4.3 Discussions
text: 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 H(0) repeatedly at each step. In particular, we emphasize that our DGC-Euler is different from APPNP in terms of the following aspects: 1) DGC-Euler is a linear model and propagates on the input features X(k−1), while APPNP is non-linear and propagates on non-linear embedding H(k−1); 2) at each step, APPNP aggregates features from the initial step H(0), while DGC-Euler aggregates features from the last step X(k−1); 3) APPNP aggregates a large amount (1 − α) of the propagated features SH(k−1) while DGC-Euler only takes a small step ∆t (T/K) towards the new features SX(k−1). 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 a different understanding of the over-smoothing problem. As shown in Theorem 1, over-smoothing is an inevitable phenomenon of (canonical) GCNs, while we can find a terminal time to achieve an optimal tradeoff between under-smoothing and oversmoothing. 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.

heading: 5 Experiments
text: In this section, we conduct a comprehensive analysis on DGC and compare it against both linear and non-linear GCN variants on a collection of benchmark datasets.

heading: 5.1 Performance on Semi-supervised Node Classification
text: 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 our DGC against several representative non-linear and linear methods that also adopts the standard data split. For non-linear GCNs, we include 1) classical baselines like GCN [7], GAT [20], GraphSAGE [5], APPNP [8] and JKNet [25]; 2) spectral methods using graph heat kernel [24, 23]; and 3) continuous GCNs [15, 22]. For linear methods, we present the results of Label Propagation [28], DeepWalk [14], SGC (linear GCN) [21] as well as its regularized version SGC-PairNorm [27]. We also consider a linear version of SIGN [17], SIGN-linear, which extends SGC by aggregating features from multiple propagation stages (K = 1, 2, . . . ). For DGC, we adopt the Euler scheme, i.e., DGC-Euler (Eq. (12)) by default for simplicity. We report results averaged over 10 random runs. Data statistics and training details are in Appendix A.
We compare DGC against both linear and non-linear baselines for the semi-supervised node classification 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, a flexible and fine-grained integration by decoupling T and K indeed helps improve the classification accuracy of 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 a real-valued T , but also the improved numerical precision by adopting a large K.
DGC v.s. non-linear models. Table 2 further shows that DGC, as a linear model, even outperforms many non-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 is comparable to, and sometimes outperforms, many modern non-linear GCNs. For example, DGC shows a clear advantage 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
efficient as a simple linear model. Besides, compared to non-linear continuous models like GCDE [15] and CGNN [22], DGC also achieves comparable accuracy only using a simple linear dynamic.

heading: 5.2 Performance on Fully-supervised Node Classification
text: Setup. For fully-supervised node classification, we also use the three citation networks, Cora, Citeseer 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-Concat 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 a 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 to multiscale methods like JKNet [25] and APPNP [8], showing that a good linear model like DGC is also competitive for fully-supervised tasks.

heading: 5.3 Performance on Large Scale Datasets
text: Setup. More rigorously, we also conduct the comparison on a large-scale node classification dataset, the Reddit networks [5]. Following SGC [21], we adopt the inductive setting, where we use the subgraph of training nodes as training data and use the whole graph for the validation/testing data. For a fair comparison, we use the same training configurations as SGC [21] and include its reported baselines, such as GCN [7], FastGCN [2], three variants of GraphSAGE [5], and RandDGI (DGI with randomly initialized encoder) [20]. We also include APPNP [8] for a comprehensive comparison.
Results. We can see DGC still achieves the best accuracy among linear methods and improve 0.9% accuracy over SGC. Meanwhile, it is superior to the three variants of GraphSAGE as well as APPNP. Thus, DGC is still the stateof-the-art linear GCNs and competitive against nonlinear GCNs on large scale datasets.

heading: 5.4 Empirical Understandings of DGC
text: Setup. Here we further provide a comprehensive analysis of DGC. First, we compare its oversmoothing behavior and computation time against previous methods. Then we analyze several factors 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 is 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 us to flexibly find the optimal terminal time (T = 5.3). Thus, we can obtain the optimal accuracy with an optimal tradeoff between under-smoothing and over-smoothing.
Robustness to feature noise. In real-world applications, there are plenty of noise in the collected node attributes, thus it is 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 2 (middle) shows that DGC is significantly more robust than SGC across three citation networks, and the advantage is clearer on larger noise scales. As discussed in Theorem 3, the diffusion process in DGC can be seen as a denoising procedure, and consequently, DGC’s robustness to feature noise can be contributed to the optimal tradeoff between over-smoothing and under-smoothing with a flexible choice of T and K. In comparison, SGC is not as good as DGC because it cannot find such a 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-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 (3×) than SGC, but DGC achieves much higher accuracy. Even so, DGC is still much faster than non-linear GCNs (>100×). 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.
Graph Laplacian. As shown in Figure 3 (left), in DGC, both the two Laplacians, L (with self-loop) and Lsym (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 test accuracy than the canonical Laplacian Lsym 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 different numerical schemes in Figure 3 (middle), we find that the Runge-Kutta method demonstrates better accuracy than the Euler method with a small K. Nevertheless, as 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 3 (right), we compare the test accuracy with different terminal time T . We show that indeed, in real-world datasets, there exists a sweet spot that achieves the optimal tradeoff between under-smoothing and over-smoothing. 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 Laplacians on each dataset, which suggests that the optimal terminal time T ∗ is an intrinsic property of the dataset.

heading: 6 Conclusions
text: In this paper, we have proposed Decoupled Graph Convolution (DGC), which improves significantly 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 to learn.
Our findings suggest that, unfortunately, current GCN variants still have not shown significant advantages over a 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.

heading: Acknowledgement
text: 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 is supported by the National Science Foundation of China under Grant No. 11961141007. Zhouchen Lin was supported by the NSF China (No.s 61625301 and 61731018), NSFC Tianyuan Fund for Mathematics (No. 12026606) and Project 2020BD006 supported by PKU-Baidu Fund.

Review summaries:
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.

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. 

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. 

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).