On Provable Benefits of Depth in Training Graph Convolutional Networks
Year: 2022

Abstract:
Graph Convolutional Networks (GCNs) are known to suffer from performance degradation as the number of layers increases, which is usually attributed to oversmoothing. Despite the apparent consensus, we observe that there exists a discrepancy between the theoretical understanding of over-smoothing and the practical capabilities of GCNs. Specifically, we argue that over-smoothing does not necessarily happen in practice, a deeper model is provably expressive, can converge to global optimum with linear convergence rate, and achieve very high training accuracy as long as properly trained. Despite being capable of achieving high training accuracy, empirical results show that the deeper models generalize poorly on the testing stage and existing theoretical understanding of such behavior remains elusive. To achieve better understanding, we carefully analyze the generalization capability of GCNs, and show that the training strategies to achieve high training accuracy significantly deteriorate the generalization capability of GCNs. Motivated by these findings, we propose a decoupled structure for GCNs that detaches weight matrices from feature propagation to preserve the expressive power and ensure good generalization performance. We conduct empirical evaluations on various synthetic and real-world datasets to validate the correctness of our theory.

heading: 1 Introduction
text: In recent years, Graph Convolutional Networks (GCNs) have achieved state-of-the-art performance in dealing with graph-structured applications, including social networks [28, 21, 51, 12, 44], traffic prediction [10, 45, 34, 31], knowledge graphs [52, 53, 43], drug reaction [14, 16] and recommendation system [2, 60]. Despite the success of GCNs, applying a shallow GCN model that only uses the information of a very limited neighborhood on a large sparse graph has shown to be not effective [23, 6, 20, 9, 46]. As a result, a deeper GCN model would be desirable to reach and aggregate information from farther neighbors. The inefficiency of shallow GCNs is exacerbated even further when the labeled nodes compared to graph size is negligible, as a shallow GCN cannot sufficiently propagate the label information to the entire graph with only a few available labels [35].
Although a deeper GCN is preferred to perceive more graph structure information, unlike traditional deep neural networks, it has been pointed out that deeper GCNs potentially suffer from oversmoothing [35, 41, 26, 4, 58], vanishing/exploding gradients [33], over-squashing [1], and training difficulties [62, 38], which significantly affect the performance of GCNs as the depth increases. Among these, the most widely accepted reason is “over-smoothing”, which is referred to as a phenomenon due to applying multiple graph convolutions such that all node embeddings converge to a single subspace (or vector) and leads to indistinguishable node representations.
The conventional wisdom is that adding to the number of layers causes over-smoothing, which impairs the expressiveness power of GCNs and consequently leads to a poor training accuracy. However, we observe that there exists a discrepancy between theoretical understanding of their inherent capabilities
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
and practical performances. According to the definition of over-smoothing that the node representation becomes indistinguishable as GCNs goes deeper, the classifier has difficulty assigning the correct label for each node if over-smoothing happens. As a result, the training accuracy is expected to be decreasing as the number of layers increases. However, as shown in Figure 1, GCNs are capable of achieving high training accuracy regardless of the number of layers. But, as it can be observed, deeper GCNs require more training iterations to reach a high training accuracy, and its generalization performance on evaluation set decreases as the number of layers increases. This observation suggests that the performance degradation is likely due to inappropriate training rather than the low expressive power caused by over-smoothing. Otherwise, a low expressiveness model cannot achieve almost perfect training accuracy simply by proper training tricks alone.1 Indeed, recent years significant advances have been witnessed on tweaking the model architecture to overcome the training difficulties in deeper GCN models and achieve good generalization performance [38, 6, 33, 62].
Contributions. Motivated by aforementioned observation, i.e., still achieving high training accuracy when trained properly but poor generalization performance, we aim at answering two fundamental questions in this paper:
Q1: Does increasing depth really impair the expressiveness power of GCNs? In Section 4, we argue that there exists a discrepancy between over-smoothing based theoretical results and the practical capabilities of deep GCN models, demonstrating that over-smoothing is not the key factor that leads to the performance degradation in deeper GCNs. In particular, we mathematically show that over-smoothing [41, 26, 35, 4] is mainly an artifact of theoretical analysis and simplifications made in analysis. Indeed, by characterizing the representational capacity of GCNs via Weisfeiler-Lehman (WL) graph isomorphism test [39, 55], we show that deeper GCN model is at least as expressive as the shallow GCN model, the deeper GCN models can distinguish nodes with a different neighborhood that the shallow GCN cannot distinguish, as long as the GCNs are properly trained. Besides, we theoretically show that more training iterations is sufficient (but not necessary due to the assumptions made in our theoretical analysis) for a deeper model to achieve the same training error as the shallow ones, which further suggests the poor training error in deep GCN training is most likely due to inappropriate training.
Q2: If expressive, why then deep GCNs generalize poorly? In Section 5, in order to understand the performance degradation phenomenon in deep GCNs during the evaluation phase, we give a novel generalization analysis on GCNs and its variants (e.g., ResGCN, APPNP, and GCNII) under the semi-supervised setting for the node classification task. We show that the generalization gap of GCNs is governed by the number of training iterations, largest node degree, the largest singular value of weight matrices, and the number of layers. In particular, our result suggests that a deeper GCN model requires more iterations of training and optimization tricks to converge (e.g., adding skip-connections), which leads to a poor generalization. More interestingly, our generalization analysis shows that most of the so-called methods to solve oversmoothing [47, 61, 6, 29] can greatly improve the generalization ability of the model, therefore results in a deeper model.
1The results in Figure 1 can be reproduced by removing both the dropout and weight decay operation. These two augmentations are designed to improve the generalization ability (i.e., validation/testing accuracy) of the model but might hurt the training accuracy, because of the randomness and also an extra regularization term on the model parameters which are introduced during training. A simple experiment using DGL can be found here.
The aforementioned findings naturally lead to the algorithmic contribution of this paper. In Section 6, we present a novel framework, Decoupled GCN (DGCN), that is capable of training deeper GCNs and can significantly improve the generalization performance. The main idea is to isolate the expressive power from generalization ability by decoupling the weight parameters from feature propagation. In Section 7, we conduct experiments on the synthetic and real-world datasets to validate the correctness of the theoretical analysis and the advantages of DGCN over baseline methods.

heading: 2 Related works
text: Expressivity of GCNs. Existing results on expressive power of GCNs are mixed, [39, 37, 7, 5] argue that deeper model has higher expressive power but [41, 26, 25] have completely opposite result. On the one hand, [39] shows a deeper GCN is as least as powerful as the shallow one in terms of distinguishing non-isomorphic graphs. [37] shows that deep and wide GCNs is Turing universal, however, GCNs lose power when their depth and width are restricted. [7] and [5] measure the expressive power of GCNs via its subgraph counting capability and attribute walks, and both show the expressive power of GCNs grows exponentially with the GCN depth. On the other hand, [25] studies the infinity wide GCNs and shows that the covariance matrix of its outputs converges to a constant matrix at an exponential rate. [41, 26] characterize the expressive power using the distance between node embeddings to a node feature agnostic subspace and show the distance is decreasing as the number of layers increases. Details are deferred to Section 4 and Appendix B. Such contradictory results motivate us to rethink the role of over-smoothing on expressiveness.
Generalization analysis of GCNs. In recent years, many papers are working on the generalization of GCNs using uniform stability [50, 63], Neural Tangent Kernel [15], VC-dimension [49], Rademacher complexity [18, 42], algorithm alignment [56, 57] and PAC-Bayesian [36]. Existing works only focus on a specific GCN structure, which cannot be used to understand the impact of GCN structures on its generalization ability. The most closely related to ours is [50], where they analyze the stability of the single-layer GCN model, and show that the stability of GCN depends on the largest absolute eigenvalue of its Laplacian matrix. However, their result is under the inductive learning setting and extending the results to the multi-layer GCNs with different structures is non-trivial.
Literature with similar observations. Most recently, several works have similar observations on the over-smoothing issue to ours. [62] argues that the main factors to performance degradation are vanishing gradient, training instability, and over-fitting, rather than over-smoothing, and proposes a node embedding normalization heuristic to alleviate the aforementioned issues. [38] argues that the performance degradation is mainly due to the training difficulty, and proposes a different graph Laplacian formulation, weight parameter initialization, and skip-connections to improve the training difficulty. [59] argues that deep GCNs can learn to overcome the over-smoothing issue during training, and the key factor of performance degradation is over-fitting, and proposes a node embedding normalization method to help deep GCNs overcome the over-smoothing issue. [30] improves the generalization ability of GCNs by using adversarial training and results in a consistent improvement than all GCNs baseline models without adversarial training. All aforementioned literature only gives heuristic explanations based on the empirical results, and do not provide theoretical arguments.

heading: 3 Preliminaries
text: Notations and setup. We consider the semi-supervised node classification problem, where a selfconnected graph G = (V, E) withN = |V| nodes is given in which each node i ∈ V is associated with a feature vector xi ∈ Rd0 , and only a subset of nodes Vtrain ⊂ V are labeled, i.e., yi ∈ {1, . . . , |C|} for each i ∈ Vtrain and C is the set of all candidate classes. Let A ∈ RN×N denote the adjacency matrix and D ∈ RN×N denote the corresponding degree matrix with Di,i = deg(i) and Di,j = 0 if i 6= j. Then, the propagation matrix (using the Laplacian matrix defined in [28]) is computed as P = D−1/2AD−1/2. Our goal is to learn a GCN model using the node features for all nodes {xi}i∈V and node labels for the training set nodes {yi}i∈Vtrain , and expect it generalizes well on the unlabeled node set Vtest = V \ Vtrain. GCN architectures. In this paper, we consider the following architectures for training GCNs:
There exist a fully connected layer after node feature
No fully connected layer after node feature
Cora
• Vanilla GCN [28] computes node embeddings by H(`) = σ(PH(`−1)W(`)), where H(`) = {h(`)i }Ni=1 is the `th layer node embedding matrix, h (`) i ∈ Rd` is the embedding of ith node,
W(`) ∈ Rd`×d`−1 is the `th layer weight matrix, and σ(·) is the ReLU activation. • ResGCN [33] solves the vanishing gradient issue by adding skip-connections between adjacency
layers. More specifically, ResGCN computes node embeddings by H(`) = σ(PH(`−1)W(`)) + H(`−1), where node embeddings of the previous layer is added to the output of the current layer to facilitate the training of deeper GCN models. • APPNP [29] adds skip-connections from the input layer to each hidden layer to preserve the feature information. APPNP computes node embeddings by H(`) = α`PH(`−1) +(1−α`)H(0)W, where α` ∈ [0, 1] balances the amount of information preserved at each layer. By decoupling feature transformation and propagation, APPNP can aggregate information from multi-hop neighbors without significantly increasing the computation complexity. • GCNII [6] improves the capacity of APPNP by adding non-linearty and weight matrix at each individual layer. GCNII computes node embeddings by H(`) = σ ( (α`PH
(`−1) + (1 − α`)H (0))W̄(`) ) , where W̄(`) = β`W(`) + (1− β`)I, constant α` same as APPNP, and constant β` ∈ [0, 1] restricts the power of `th layer parameters.

heading: 4 On true expressiveness and optimization landscape of deep GCNs
text: Empirical validation of over-smoothing. In this section, we aim at answering the following fundamental question: “Does over-smoothing really cause the performance degradation in deeper GCNs?” As first defined in [35], over-smoothing is referred to as a phenomenon where all node embeddings converge to a single vector after applying multiple graph convolution operations to the node features. However, [35] only considers the graph convolution operation without non-linearity and the per-layer weight matrices. To verify whether over-smoothing exists in normal GCNs, we measure the pairwise distance between the normalized node embeddings with varying the model depth.2 As shown in Figure 2, without the weight matrices and non-linear activation functions, the pairwise distance between node embeddings indeed decreases as the number of layers increases. However, by considering the weight matrices and non-linearity, the pairwise distances are actually increasing after a certain depth which contradicts the definition of over-smoothing that node embeddings become indistinguishable when the model becomes deeper. That is, graph convolution makes adjacent node embeddings get closer, then non-linearity and weight matrices help node embeddings preserve distinguishing-ability after convolution.
Most recently, [41, 26] generalize the idea of over-smoothing by taking both the non-linearity and weight matrices into considerations. More specifically, the expressive power of the `th layer node embeddings H(`) is measured using dM(H(`)), which is defined as the distance of node embeddings to a subspace M that only has node degree information. Let denote λL as the second largest eigenvalue of graph Laplacian and λW as the largest singular value of weight matrices. [41, 26] show that the expressive power dM(H(`)) is bounded by dM(H(`)) ≤ (λWλL)` · dM(X), i.e., the expressive power of node embeddings will be exponentially decreasing or increasing as the number
2The pairwise distances are computed on the normalized node embeddings H(`)/‖H(`)‖2F to eliminate the effect of node embedding norms.
of layers increases, depending on whether λWλL < 1 or λWλL > 1. They conclude that deeper GCN exponentially loss expressive power by assuming λWλL < 1. However, we argue that this assumption does not always hold. To see this, let suppose W(`) ∈ Rd`−1×d` is initialized by uniform distribution N (0, √ 1/d`−1). By the Gordon’s theorem for Gaussian matrices [11], we know its
expected largest singular value is bounded by E[λW ] ≤ 1 + √ d`/d`−1, which is strictly greater than 1 and λW usually increases during training. The above discussion also holds for other commonly used initialization methods [19, 22]. Furthermore, since most real world graphs are sparse with λL close to 1, e.g., Cora has λL = 0.9964, Citeseer has λL = 0.9987, and Pubmed has λL = 0.9905, making assumption on λWλL < 1 is not realistic. As shown in Figure 3, when increasing the number of layers, we observe that the distance dM(H(`)) is decreasing on untrained-GCN models, however, the distance dM(H(`)) is increasing on trained-GCN models, which contradicts the conclusion in [41]. Due to the space limit, we defer the more empirical evidence to Appendix B. Through these findings, we cast doubt on the power of over-smoothing based analysis to provide a complete picture of why deep GCNs perform badly.
Definition 1. Let T Li denote the L-layer computation tree of node i, which represents the structured L-hop neighbors of node i, where the children of any node j in the tree are the nodes in N (i).
Exponentially growing expressieness without strong assumptions. Indeed, we argue that deeper GCNs have stronger expressive power than the shallow GCNs. To prove this, we employ the connection between WL test3 [32] and GCNs. Recently, [39] shows that GCNs have the same expressiveness as the WL-test for graph isomorphism if they are appropriately trained, i.e., a properly trained L-layer GCN computes different node representations for two nodes if their L-layer computation tree (Definition 1) have different structure or different features on the corresponding nodes. Since L-GCN can encode any different computation tree into different representations, it is natural to characterize the expressiveness of L-GCN by the number of computation graph it can encode.
Theorem 1. Suppose T L is a computation tree with binary node features and node degree at least d. Then, by assuming the computation tree of two nodes are disjoint, the richness (i.e., the number of computation graphs a model can encode) of the output of L-GCN defined on T L is at least |L-GCN(T L)| ≥ 2(d− 1)L−1.
The proof is deferred to Appendix C. The above theorem implies that the richness of L-GCN grows at least exponentially with respect to the number of layers.
Comparison of expressiveness metrics. Although distance-based expressiveness metric [41, 26] is strong than WL-based metric in the sense that node embeddings can be distinct but close to each other, the distance-based metric requires explicit assumptions on the GCN structures, weight matrices, and graph structures comparing to the WL-based metric, which has been shown that are not likely hold. On the other hand, WL-based metric has been widely used in characterizing the expressive power of GCNs in graph-level task [39, 37, 7, 5]. More details are deferred to related works (Section 2).
3WL test is a recursive algorithm where the label of a node depends on its own label and neighbors from the previous iterations, i.e., c(`)i = Hash(c (`−1) i , {c (`−1) j |j ∈ N (i)}), where Hash(·) bijectively maps a set of values to a unique value that has not been used in the previous iterations. After L-iterations, the WL test will assign two nodes with a different label if the L-hop neighborhood of two nodes are non-isomorphic.
Although expressive, it is still unclear why the deeper GCN requires more training iterations to achieve small training error and reach the properly trained status. To understand this, we show in Theorem 2 that under assumptions on the width of the final layer, the deeper GCN can converge to its global optimal with linear convergence rate. More specifically, the theorem claims that if the dimension of the last layer of GCN dL is larger than the number of data N 4, then we can guarantee the loss L(θT ) ≤ ε after T = O(1/ε) iterations of the gradient updates. Besides, more training iterations is sufficient (but not necessary due to the assumptions made in our theoretical analysis) for a deeper model to achieve the same training error as the shallow ones.
Theorem 2. Let θt = {W(`)t ∈ Rd`−1×d`}L+1`=1 be the model parameter at the t-th iteration and using square loss L(θ) = 12‖H
(L)W(L+1)−Y‖2F, H(`) = σ(PH(`−1)W(`)) as objective function. Then, under the condition that dL ≥ N we can obtain L(θT ) ≤ if T ≥ C(L) log(L(θ0)/ ), where is the desired error and C(L) is a function of GCN depth L that grows as GCN becomes deeper.
A formal statement of Theorem 2 and its proof are deferred to Appendix D. Besides, gradient stability also provides an alternative way of empirically understanding why deeper GCN requires more iterations: deeper neural networks are prone to exploding/vanishing gradient, which results in a very noisy gradient and requires small learning rate to stabilize the training. This issue can be significantly alleviated by adding skip-connections (Appendix E.5). When training with adaptive learning rate mechanisms, such as Adam [27]5, noisy gradient will result in a much smaller update on current model compared to a stabilized gradient, therefore more training iterations are required.

heading: 5 A different view from generalization
text: In the previous section, we provided evidence that a well-trained deep GCN is at least as powerful as a shallow one. However, it is still unclear why a deeper GCN has worse performance than a shallow GCN during the evaluation phase. To answer this question, we provide a different view by analyzing the impact of GCN structures on the generalization.
Transductive uniform stability. In the following, we study the generalization ability of GCNs via transductive uniform stability [17], where the generalization gap is defined as the difference between the training and testing errors for the random partition of a full dataset into training and testing sets. Transductive uniform stability is defined under the notation that the output of a classifier does not change much if the input is perturbed a bit, which is an extension of uniform stability [3] from the inductive to the transductive setting. The previous analysis on the uniform stability of GCNs [50] only shows the result of GCN with one graph convolutional layer under inductive learning setting, which cannot explain the effect of depth, model structure, and training data size on the generalization, and its extension to multi-layer GCNs and other GCN structures are non-trivial.
Problem setup. Letm = |Vtrain| and u = |Vtest| denote the training and test dataset sizes, respectively. Under the transductive learning setting, we start with a fixed set of points Xm+u = {x1, . . . , xm+u}. For notational convenience, we assume Xm are the first m data points and Xu are the last u data points of Xm+u. We randomly select a subset Xm ⊂ Xm+u uniformly at random and reveal the labels Ym for the selected subset for training, but the labels for the remaining u data points Yu = Ym+u \ Ym are not available during the training phase. Let Sm = ((x1, y1), . . . , (xm, ym)) denotes the labeled set and Xu = (xm+1, . . . , xm+u) denotes the unlabeled set. Our goal is to learn a model to label the remaining unlabeled set as accurately as possible.
For the analysis purpose, we assume a binary classifier is applied to the final layer node representation f(h
(L) i ) = σ̃(v >h (L) i ) with σ̃(·) denotes the sigmoid function. We predict ŷi = 1 if f(h (L) i ) > 1/2 and ŷi = 0 otherwise, with ground truth label yi ∈ {0, 1}. Let denote the perturbed dataset as Sijm , (Sm \{(xi, yi)})∪{(xj , yj)} and Xiju , (Xu \{xj})∪{xi}, which is obtained by replacing the ith example in training set Sm with the jth example from the testing set Xu. Let θ and θij denote the weight parameters trained on the original dataset (Sm, Xu) and the perturbed dataset (Sijm, X ij u ),
4This type of over-parameterization assumptions are required and commonly used in other neural network convergence analysis to guarantee that the model parameters do not change significantly during training.
5In the Adam optimizer, the contribution of bias correction of moments varies exponentially over epochs completed. Although the learning rate hyper-parameter is a constant, the contribution of gradients to updated weight varies over epochs, hence adaptive. Please refer to the Chapter 8.5 of [48] for more details.
respectively. Then, we say transductive learner f is -uniformly stable if the outputs change less than when we exchange two examples from the training set and testing set, i.e., for any Sm ⊂ Sm+u and any i, j ∈ [m+ u] it holds that supi∈[m+u] |f(h (L) i )− f̃(h̃ (L) i ))| ≤ , where f(h (L) i ) and f̃(h̃ (L) i ) denote the prediction of node i using parameters θ and θij respectively.
To define testing error and training error in our setting, let us introduce the difference in probability between the correct and the incorrect label as p(z, y) , y(2z−1)+(1−y)(1−2z) with p(z, y) ≤ 0 if there exists a classification error. Let denote the γ-margin loss as Φγ(x) = min(1,max(0, 1−x/γ)). Then, the testing error is defined as Ru(f) = 1u ∑m+u i=m+1 1 { p(f(h (L) i ), yi) ≤ 0 } and the training
loss is defined asRγm(f) = 1m ∑m i=1 Φγ(−p(f(h (L) i ), yi)). 6 Theorem 3 (Transductive uniform stability bound [17]). Let f be a -uniformly stable transductive learner and γ, δ > 0, and define Q = mu/(m+ u). Then, with probability at least 1− δ over all training and testing partitions, we haveRu(f) ≤ Rγm(f) + 2γO ( √ Q ln(δ−1) ) +O ( ln(δ−1)√ Q ) .
Recall that as we discussed in Section 4, deeper GCN is provable more expressive and can achieve very low training error Rγm(f) if properly training. Then, if the dataset size is sufficiently large, the testing errorRu(f) will be dominated by the generalization gap, which is mainly controlled by uniformly stable constant . In the following, we explore the impact of GCN structures on . Our key idea is to decompose the into three terms: the Lipschitz continuous constant ρf , upper bound on gradient Gf , and the smoothness constant Lf of GCNs. Please refer to Lemma 1 for details.
Lemma 1. Suppose function f(h(L)) is ρf -Lipschitz continuous, Lf -smooth, and the gradient of loss w.r.t. the parameter is bounded by Gf . After T steps of full-batch gradient descent, we have =
2ηρfGf m ∑T t=1(1 + ηLf ) t−1.
The proof is deferred to Appendix K. By using Lemma 1, we can derive constant of different model structures by comparing the Lipschitz continuity, smoothness, and gradient scale.
Before proceeding to our result, we make the following standard assumption on the node feature vectors and weight matrices, which are previously used in generalization analysis of GCNs [18, 36]. Assumption 1. We assume the norm of node feature vectors, weight parameters are bounded, i.e., ‖xi‖2 ≤ Bx, ‖W(`)‖2 ≤ Bw, and ‖v‖2 ≤ 1.
In Theorem 4, we show that the generalization bounds of GCN and its variants are dominated by the following terms: maximum node degree d, model depth L, training/validation set size (m,u), training iterations T , and spectral norm of the weight matrices Bw. The larger the aforementioned variables are, the larger the generalization gap is. We defer the formal statements and proofs to Appendices F, G, H, and I.
Theorem 4 (Informal). We say model is -uniformly stable with = 2ηρfGfm ∑T t=1(1 + ηLf ) t−1 where the result of ρf , Gf , Lf are summarized in Table 1, and other related constants as
Bαd = (1− α) ∑L `=1(α √ d)`−1 + (α √ d)L, Bβw = βBw + (1− β),
Bα,β`,d = max { β ( (1− α)L+ α √ d ) , (1− α)LBβw + 1 } .
(1)
In the following, we provide intuitions and discussions on the generalization bound of each algorithm:
• Deep GCN requires iterations T to achieve small training error. Since the generalization bound increases with T , more iterations significantly hurt its generalization power. Note that our results considers bothBw ≤ 1 andBw > 1, where increasing model depth will not hurt the generalization if Bw ≤ 1, and the generalization gap becomes sensitive to the model depth if Bw > 1. Notice that Bw > 1 is more likely to happen during training as we discussed in Section 4. • ResGCN resolves the training difficulties by adding skip-connections between hidden layers. Although it requires less training iterations T , adding skip-connections enlarges the dependency
6Notice that a different loss function is used in convergence analysis (i.e., L(θ) in Theorem 7) and generalization analysis (Rγm(f) in Theorem 4). We do this because current understanding on the convergence of deep neural networks is still mostly limited to the square loss, but the margin loss is a more suitable and widely accepted loss function for generalization analysis.
Remark 1. It is worthy to provide an alternative view of DropEdge [47] and PairNorm [61] algorithms from a generalization perspective. To improve the generalization power of standard GCNs, DropEdge randomly drops edges in the training phase, which leads to a smaller maximum node degree ds < d. PairNorm applies normalization on intermediate node embeddings to ensure that the total pairwise feature distances remain constant across layers, which leads to less dependency on d and Bw. However, since deep GCN requires significantly more iterations to achieve low training error than shallow one, the performance of applying DropEdge and PairNorm on GCNs is still degrading as the number of layers increases. Most importantly, our empirical results in Appendix E.3 and E.4 suggest that applying Dropout and PairNorm is hurting the training accuracy (i.e., not alleviating over-smoothing) but reducing the generalization gap.

heading: 6 Decoupled GCN
text: We propose to decouple the expressive power from generalization ability with Decoupled GCN (DGCN). The DGCN model can be mathematically formulated as Z = ∑L `=1 α`f
(`)(X) and f (`)(X) = P`X ( β`W (`) + (1 − β`)I ) , where W(`), α` and β` are the learnable weights for `th layer function f (`)(X).7 The design of DGCN has the following key ingredients:
• (Decoupling) The generalization gap in GCN grows exponentially with the number of layers. To overcome this issue, we propose to decouple the weight matrices from propagation by assigning weight W(`) to each individual layerwise function f (`)(X). DGCN can be thought of as an ensemble of multiple SGCs [54] with depth from 1 to L. By doing so, the generalization gap has less dependency on the number of weight matrices, and deep models with large receptive fields can incorporate information of the global graph structure. Please refer to Theorem 5 for the details. • (Learnable α`) After decoupling the weight matrices from feature propagation, the layerwise function f (`)(X) with more propagation steps can suffer from less expressive power. Therefore,
7A similar architecture has been previously used in [8], where they empirically show that relaxing the layer weights to negative values can further boost the performance.
we propose to assign a learnable weight α` for each step of feature propagation. Intuitively, DGCN assigns smaller weight α` to each layerwise function f (`)(X) with more propagation steps at the beginning of training. Throughout the training, DGCN gradually adjusts the weight to leverage more useful large receptive field information. • (Learnable β`) A learnable weight β` ∈ [0, 1] is assigned to each weight matrix to balance the expressiveness with model complexity, which guarantees a better generalization ability.
Theorem 5. Let suppose α` and β` are pre-selected and fixed during training. We say DGCN is DGCN-uniformly stable with DGCN = 2ηρfGf m ∑T t=1(1 + ηLf ) t−1 where
ρf = Gf = O ( ( √ d)LBx ) , Lf = O ( ( √ d)LBx ( ( √ d)LBx max{1, Bw}+ 1) )) . (2)
The details are deferred to Appendix J, and comparison of bound to other GCN variants are summarized in Table 1. Depending on the automatic selection of α`, β`, the generalization bound of DGCN is between APPNP and GCN. In the following, we make connection to many GCN structures:
• Connections to APPNP: APPNP can be thought of as a variant of DGCN. More specifically, the layerwise weight in APPNP is computed as α` = α(1− α)` for ` < L and α` = (1− α)` for ` = L given some constant α ∈ (0, 1), and the weight matrix is shared between all layers. Although DGCN has L weight matrices, its generalization is independent of the number of weight matrices, and thus enjoys a low generalization error with high expressiveness. • Connections to GCNII: GCNII can be regarded as a variant of DGCN. Compared to GCNII, the decoupled propagation of DGCN significantly reduces the dependency of generalization error to the weight matrices. Besides, the learnable weights α` and β` allow DGCN to automatically adapt to challenging large-scale datasets without time-consuming hyper-parameter selection. • Connections to ResGCN: By expanding the forward computation of ResGCN, we know that ResGCN can be think of as training an ensemble of GCNs from 1 to L layer, i.e., H(L) = ∑L `=1 α`σ(PH
(`−1)W(`)) with α` = 1. In other word, ResNet can be regarded as the “summation of the model complexity” of L-layer. However, DGCN is using ∑L `=1 α` = 1, which can be thought of as a “weighted average of model complexity”. Therefore, ResGCN is a special case of DGCN with equal weights α` on each layerwise function. With just a simple change on the ResNet structure, our model DGCN is both easy to train and good to generalize.

heading: 7 Experiments
text: Synthetic dataset. We empirically compare the generalization error of different GCN structures on the synthetic dataset. In particular, we create the synthetic dataset by contextual stochastic block model (CSBM) [13] with two equal-size classes. CSBM is a graph generation algorithm that adds Gaussian random vectors as node features on top of classical SBM. CSBM allows for smooth control over the information ratio between node features and graph topology by a pair of hyper-parameter
(µ, λ), where µ controls the diversity of the Gaussian distribution and λ controls the number of edges between intra- and inter-class nodes. We generate random graphs with 1000 nodes, average node degree as 5, and each node has a Gaussian random vector of dimension 1000 as node features. We chose 75% nodes as training set, 15% of nodes as validation set for hyper-parameter tuning, and the remaining nodes as testing set. We conduct an experiment 20 times by randomly selecting (µ, λ) such that both node feature and graph topology are equally informative.
As shown in Figure 4, we have the following order on the generalization gap given the same training iteration T : APPNP ≤ GCNII ≤ GCN ≤ ResGCN, which exactly match the theoretical result in Theorem 4. More specifically, ResGCN has the largest generalization gap due to the skip-connections, APPNP has the smallest generalization gap by removing the weight matrices in each individual layer. GCNII achieves a good balance between GCN and APPNP by balancing the expressive and generalization power. Finally, DGCN enjoys a small generalization error by using the decoupled GCN structure.
Open graph benchmark dataset. As pointed out by Hu et al. [24], the traditional commonly-used graph datasets are unable to provide a reliable evaluation due to various factors including dataset size, leakage of node features and no consensus on data splitting. To truly evaluate the expressive and the generalization power of existing methods, we evaluate on the open graph benchmark (OGB) dataset. Experiment setups are based on the default setting for GCN implementation on the leaderboard. We choose the hidden dimension as 128, learning rate as 0.01, dropout ratio as 0.5 for Arxiv dataset, and no dropout for Products and Protein datasets. We train 300/1000/500 epochs for Products, Proteins, and Arxiv dataset respectively. Due to limited GPU memory, the number of layers is selected as the one with the best performance between 2 to 16 layers for Arxiv dataset, 2 to 8 layers for Protein dataset, and 2 to 4 for Products dataset. We choose α` from {0.9, 0.8, 0.5} for APPNP and GCNII, and use β` = 0.5/` for GCNII, and select the setup with the best validation result for comparison.
As shown in Table 2, DGCN achieves a compatible performance to GCNII8 without the need of manually tuning the hyper-parameters for all settings, and it significantly outperform APPNP and ResGCN. Due to the space limit, the detailed setups and more results can be found in Appendix E. Notice that generalization bounds are more valuable when comparing two models with same training accuracy (therefore we first show in Section 4 that deeper model can also achieve low training error before our discussion on generalization in Section 5).
In Table 2, because ResGCN has no restriction on the weight matrices, it can achieve lower training error and its test performance is mainly restricted by its generalization error. However, because GCNII and APPNP have restrictions on the weight matrices, their performance is mainly restricted by their training error. A model with small generalization error and no restriction on the weight (e.g., DGCN)
is preferred as it has higher potential to reach a better test accuracy by reducing its training error.

heading: 8 Conclusion
text: In this work, we show that there exists a discrepancy between over-smoothing based theoretical results and the practical behavior of deep GCNs. Our theoretical result shows that a deeper GCN can be as expressive as a shallow GCN, if it is properly trained. To truly understand the performance decay issue of deep GCNs, we provide the first transductive uniform stability-based generalization analysis of GCNs and other GCN structures. To improve the optimization issue and benefit from depth, we propose DGCN that enjoys a provable high expressive power and generalization power. We conduct empirical evaluations on various synthetic and real-world datasets to validate the correctness of our theory and advantages over the baselines.
8† GCNII underfits with the default hyper-parameters. ‡ GCNII achieves 72.74 ± 0.16 by using hidden dimension as 256 and a different design of graph convolution layer. Refer here for details.

heading: Acknowledgements
text: This work was supported in part by NSF grant 2008398.

Review summaries:
The deals with semi-supervised learning with graphs using graph neural networks. Specifically, it investigates the benefits of depth both from a (learning) theory as well as an empirical standpoint.   The key contributions are: 1. Questioning the common folklore belief that deep GNNs are not expressive due to "over-smoothing" 2. Studying the generalization performance of GNNs using uniform stability theory  3. Introducing  "Decoupled GCNs" which learn linear combinations of single-layer GNNs (using powers of the Laplacian). 4. Experimental study validating the theoretical results. 

The paper provides a novel theoretical understanding of over-smoothing and point out that the major impact of poor performance is due to the generation gap. The paper brings a new point about why deep GCN fails. Moreover, the paper designs a new framework according to their theorem although the proposed framework is just a dense version of GCNII.

This paper analyzed GCN model for node classification in depth. The paper first analyzed the deep model's performance degeneration problem and argued that the deep model's expressiveness is not worse than shadow model so it does not suffer from oversmoothing problem. In fact, the degeneration of deep model comes from the hardness of training instead of oversmoothing, and the papers theoretically proved that deep model needs more iterations to converge, under a strong assumption. The above explanation explained the training loss but not characterize the final test performance. The author further explored the generalization error (the gap between training loss and test loss) and proved that under transductive setting the generalization error is affected by the number of training epochs, the number of layers, singluar value of weight matrix and largest node degrees, which explained why deep models have degenerated test performance. The author finally proposed a weight to decouple weight matrix and feature propagation operations, which keeps the expressiveness and also improves generalization ability.