On Provable Benefits of Depth in Training Graph Convolutional Networks
Authors: Weilin Cong
Morteza Ramezani
Mehrdad Mahdavi
Venue: NeurIPS 2021 Poster (2021)
Keywords: graph neural network
over-smoothing
generalization
expressive power
optimization

Abstract: Graph Convolutional Networks (GCNs) are known to suffer from performance degradation as the number of layers increases, which is usually attributed to over-smoothing. 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.

On Provable Benefits of Depth in Training Graph Convolutional Networks
Weilin Cong Penn State
Morteza Ramezani
Mehrdad Mahdavi Penn State mzm6160psu. edu
Penn State morteza@cse. psu. edu
wxc2720psu.ede edu
Abstract
Graph Convolutional Networks (GCNs) known to suffer from performance degradation as the number of layers increases, which is usually attributed to over- smoothing. Despite the apparent consensus, we observe that there exists discrep- ancy between the theoretical understanding of over-smoothing and the practical capabilities of GCNs. Specifically, we argue that over-smoothing does essarily happen in practice, a deeper model is provably expressive, can converge 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 GCNs. Motivated by these findings, propose decoupled structure for GCNs that detaches weight matrices from feature propagation preserve the expressive power and ensure good generalization performance. We conduct empirical evaluations various synthetic and real-world datasets to validate the correctness of our theory.
Introduction
In recent years, Graph Convolutional Networks (GCNs) have achieved state-of-ther performance in dealing with graph-structured applications, including social networks [28, 21, 51, 12, 44], traffic prediction [10, 45, 34,31J, 31], knowledge graphs [52, 53, 43], drug reaction [14, 16] and recommendation the
system [2, 60]. Despite the success of GCNs, applying shallow GCN model that only information a very limited neighborhood on a large sparse graph has shown to be not effective [23, 6, 20, 46). As result, deeper GCN model would be desirable reach and aggregate information from farther neighbors. The inefficiency of shallow GCNs exacerbated even further when the labeled nodes compared graph size negligible, the label information to the entire graph with only few available labels [35].
shallow GCN cannot sufficiently propagate
Although deeper GCN is preferred to perceive more graph structure information, unlike traditional deep neural networks, has been pointed out that deeper GCNs potentially suffer from over- smoothing [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 "ovver-mmoohhnng" which is referred
phenomenon due to applying multiple graph convolutions such that all node embeddings converge to single subspace (or vector) and leads to indistinguishable node representations.
The conventional wisdom that adding to the number of layers causes over-smoothing, which impairs the expressiveness power of GCNs and consequently leads to poor training accuracy. However, observe that there exists a discrepancy between theoretical understanding their inherent capabilities
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Highest F1-score| / Layers
# Iterationn until highest F1-score Layers
1.00
Number fieratoons tlons of training
Highost F1-ccore
Number Iteraaions
8000
0.95
Highost fuan Plassare
Highest Fliacore
6000
Highest Fl Floseare
0.90
4000
0.85
2000
Number layers
Number layers
Figure 1: Comparison of Fl-score for GCN with different depth on Cora dataset, where deeper models can achieve high training accuracy, but complicate the training by requiring more iterations to converge and suffer from poor generalization.
and practical performances. According to the definition of ovor-smoothing that the node representation becomes indistinguishable 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 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 inappropriate training rather than the low expressive power caused by werrssoothiin. Otherwise, low expressiveness model cannot achieve almost perfect training accuracy simply by proper training tricks alone.' 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].
capable
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 Heiseellrr-ehhmar (WI.) 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, long as the GCNs are properly trained. Besides, we theoretically show that more training iterations is sufficient (but nor necessary due the assumptions made in our theoretical analysis) for 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 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 soincconnections). which leads a poor generalization. More interestingly, our generalization analysis shows that most of the so-called methods to solve over- smoothing (47, 61. 6, 29] can greatly improve the generalization ability of the model, therefore results in deeper model.
'The results in Figure I can be reproduced by removing both dropout 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.
2 Related works
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 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 node feature agnostic subspace and show the distance is decreasing as the number of layers increases. Details are deferred to Section and Appendix B. Such contradictory results motivate us rethink the role of over- svor-snoo 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 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 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 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 consistent improvement than all GCNs bascline models without adversarial training. All aforementioned literature only gives heuristic explanations based on the empirical results, and do not provide theoretical arguments.
3 Preliminaries
Notations and setup. We consider the semi semi-supervised node classification problem, where self- connected graph 9 = (V,E) with N | nodes is given in which each node i is associated with feature vector x; Rdd, and only subset of nodes Virai V are labeled, i.e., y/ E {1,.... [C]} for each i E Vraan and C is the set of all candidate classes. Let A E R X denote the adjacency matrix and D N denote the corresponding degree matrix with D,, = deg(i) and Di,j if i / j. Then, the propagation matrix (using the Laplacian matrix defined in [28]) is computed as P D 1/2 1/22A AD 11/2. Our goal is to learn a GCN model using the node features for all nodes {x: and node labels for the training set nodes (11) Jev. and expect it generalizes well on the unlabeled node set Viea = V Vinain
GCN architectures. In this paper, consider the following architectures for training GCNs:
3

---

H(G LH HO
H aLL W
H
0.325
0.035
RCW clar dRaa
OCM into clds dilato
0.315
0.015
Essance
5661 vesedless dsconce 187a diicuce
190%
0.335
0.035
Nar typtrs
of
Figure 2: Comparison of intra- and inter-class normalized node embeddings ((HH)((()) pairwise distance on Cora dataset. See Appendix A for more evidences.
Vanilla GCN [28] computes node embeddings by H (PHH(-)W()) where H
[b. y > ===1 is the 9th layer node embedding matrix, h (2)
E IR is the embedding of ith node,
W(O) E Rdexde-1 is the 9th 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 o (PH(-))
(e-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 fea-
ture information. APPNP computes node embeddings by H = or (H + (1 - (1-az) H()) W", where a E [o. 1] balances the amount of information preserved at each layer. By decoupling fea- ture transformation and propagation, APPNP 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 o ((a,PH(f-) + (1
ar) H (+) where W Be (+()) (1 - I. constant a same as APPNP, and constant
3e E [0, 1] restricts the power of /th layer parameters.
On true expressiveness and optimization landscape of deep GCNs
Empirical validation of over-smoothing. In this section, we aim 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 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 withou 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- 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-abiity 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 (()) measured using (H((H())) which is defined as the distance of node embeddings to a subspace M that only has node degree information. Let denote ',. the second largest eigenvalue of graph Laplacian and my as the largest singular value of weight matrices. [41, 26] show that the expressive power (H(()))) is bounded by (H & (Aw A (X) i.c., the expressive power of node embeddings will be exponentially decreasing or increasing as the number
"The pairwise distances are computed on the normalized node embeddings ( effect of node embedding norms.
(013 { (
eliminate the

---

dujet)
ofbytr
1.36
Darfore tranting
Before traiiing
1.7
1.32
1.30
10
Mam tyytt
Mam layors
OCW dy Num of layrrs
GCM /amm layers
5020
-020
3020
2.0
2020
2.4
1020
2.2
2.0
Num of lnpert
Bamm of ayyers
Figure 3: Compare (H(( and Aw (W(1)) on both trained- (using 500 gradient update) and unfrained-GGNN models on Cora dataset.
of layers increases, depending on whether Åy < 1 or AW A > 1. They conclude that deeper GCN exponentially loss expressive power by assuming Aw < 1. However, we argue that this assumption does not always hold. To see this, let suppose W E R ixde is initialized by uniform distribution (0, VT/de-1)- By the Gordon's theorem for Gaussian matrices [11], we know its expected largest singular value is bounded by [[Aw] S 1 + dd//de-1. which is strictly greater than 1 and Aw 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 A close to 1, c.g. Cora has λ 0.9964, Citeseer has 0 = 0.9987, and Pubmed has λ 0.9905, making assumption on Aw λy < is not realistic. As shown in Figure 3, when increasing the number of layers, we observe that the distance (H is decreasing on intrraindd-GCY models, however, the distance d (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-smoothne weo-shng based analysis to provide a complete picture of why deep GCNs perform badly.
Definition 1. Let Th denote the I--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()).
Exponentially growing expressieness without strong assumptions. Indeed, we argue that deeper GCNs have stronger expressive power than the shallow GCNs. To prove this, employ the connec- tion between WL test [32] and GCNs. Recently, [39] shows that GCNs have the same expressiveness the WL-test for graph isomorphism if they appropriately trained, i.e., a properly trained L-layer GCN computes different node representations for two nodes their L--aaer computation tree (Definition 1) have different structure different features 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 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 TL is at least [L-GCN(T*)] 2 2(d 11--1
The proof is deferred to Appendix C. The above theorem implies that the richness of L-GCN grows least exponentially with respect to the number of layers.
Comparison of expressiveness metrics. Although distance-based expressiveness metric [41, 26] is strong than WI--baedd 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 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).
'W. test is recursive al algorithm where the label of a node depends on its own label and neighbors from the previous iterations, i.c., (00)) Hash(c (f-1) ( E (o))). where Hash(-) bijectively maps a set of values to unique value that has not been used in the previous iterations. After L-iterations, the WL test will assign nodes with different label if the L-hop neighborhood of two nodes are iommisomo..
5

---

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 dz is larger than the number of data No, then we can guarantee the loss [() I ε after = (L/ss) 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.
Let 0: = (w!") E TRde-1 Xde ) DE= using square loss (()) = (1IH(() -Y H()) = (PH(( as objective function. Then, under the condition that dı 2 N we can obtain [(Or) S < 2 C(L) log( /(0))/c). where e is the desired error and (L) is a function of GCN depth L that grows as GCN becomes deeper.
Theorem 2.
be the model parameter at the 1-th iteration and
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 ssploding/vanishing gradient, which results in 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]', noisy gradient will result in a much smaller update on current model compared to a stabilized gradient, therefore more training iterations are required.
5 A different view from generalization
In the previous section, we provided evidence that well-trained deep GCN is at least as powerful as shallow one. However, it 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 classifier does not change much if the input is perturbed a bit, which is an extension of uniform stability [3] from the inductive 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. Let m M and Viesa denote the training and test dataset sizes, respectively. Under the transductive learning setting, we start with a fixed set of points Xm+ { TTm. }. For notational convenience, we assume Xm are the first m data points and X,, are the last u data points of Xm+.. We randomly select a subset Xm C Xm+= uniformly at random and reveal the labels Ym for the selected subset for training, but the labels for the remaining u data points Y, = Ym++a \ Yn, are not available during the training phase. Let S. = ((ø1. Vi),.... (Im. 3mm) denotes the labeled set and X2 (Im+1.... ... mm+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 binary classifier is applied to the final layer node representation f [h (4) = ā(v h, ()) with ā-)) denotes the sigmoid function. We predict g. = if f(h(")) > 1/2 and 0. 0 otherwise, with ground truth label y/ {0, 1}. Let denote the perturbed dataset as SM & (S... \ ((x,, v.))) U ( (2,,, U;}} } and Xy & (X,, \ {x,)) (æ;), which is obtained by replacing the ith example in training set Sm with the jthh example from the testing set X,. Let θ and Ø denote the weight parameters trained on the original dataset (5m.))) and the perturbed dataset (S m/ X²)).
"This 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. "In the Adam optimizer, the contribution of bias correction of moments varies exponentially over epochs completed, Although the learning rate parammer is 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 is e-uniformly stable if the outputs change less than e when we exchange two examples from the training set and testing set, i.e., for any S.n C Sm+x and any i,j E [m + u| it holds that su [f(b, f(h s c, where fb, (") and f(b, (
denote the prediction of node using parameters f and 0 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(2, y) $ there exists a classification error. Let denote the 7--argin loss as (x) = min(1, max(0, x/>)).
22) with p(2. y) - 0f
Then, the testing error is defined as (J) - Dmm+t (p (1)((")), m.) s 0} and the training
loss is defined as R.7, (f) = J
m > P>(- ).u:)).
Theorem 3 (Transductive uniform stability bound [17D- Let be a e-uniformly stable transductive learner and Y, 5 > O, and define Q mu/ (m/mmm= + u). Then, with probability at least 1 - 8 over all
training and testing partitions, we have Ro(f) S R (f) + 200 (evQIn(6-1) + +0 (In(8-1 1)
Recall that as we discussed in Section 4, deeper GCN is provable more expressive and can achieve very low training сπхог R7, (f) if properly training. Then, if the dataset size is sufficiently large, the testing error R., (f) will be dominated by the generalization gap, which mainly controlled by uniformly stable constant In the following, we explore the impact of GCN structures on c. Our key idea is to decompose the c into three terms: the Lipschitz continuous constant Py. upper bound on gradient Gy. and the smoothness constant Ly of GCNs. Please refer to Lemma I for details.
Lemma 1. Suppose function f(((5) is py-Liscchitz continuous, smoothh, and the gradient of loss w.r.l. the parameter is bounded by GJ. After T steps of full-batch gradient descent, we have Gn m
The proof is deferred to Appendix K. By using Lemma I, 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 generalization analysis of GCNs [18. 36). Assumption 1. We assume the norm of node feature vectors, weight parameters are bounded, i.e., ||x:||2 < B,, | ||2 S Bun and || < 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, graining/validation set size (m, u). training iterations 7', and spectral norm of the weight matrices B 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 c-uniformly stable with c == == =22p,Gs ΣT (1 + nL where the result of p.: G5, Ly are summarized in Table I, and other related constants as
m.
(av/)": B = BB + +(1 3). Bed = max {8((1 a) ()] -
B (1 a) E/
(I)
-1 L. +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 both B., < 1 and B., > 1, where increasing model depth will not hurt the generalization if B., < 1, and the generalization gap becomes sensitive to the model depth if B., > 1. Notice that B,, >1 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 ckip-connections enlarges the dependency
'Notice that a different loss function is used in convergence analysis (i.e., L(0) in Theorem 7) and gener- alization analysis (R2, (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.
7

---

Table 1: Comparison of uniform stability constant of GCN variants, where O() is used hide constants that shared between all bounds.
Pf and G5
Lf
Ci and C2
O(C+C,)
([C+C(((+++))C))) +2)
G max(1, v /d C2 vd(1 Bz)
<OCN
(()
G 1 vdB C2 vd(1 + B2)
CResGeN
CAPPN
O(Gi)
O(C](C()))) +1
C Bg C2 = max B
<ocNN
O(BC)C2)
0laSCtCa((aBL +2C0C, + 28))
C max[I,aydB3 C₂ Va B B.
<DOCN
O(Ci)
O(C(CC,)))) +1)
C (vd)+B2.C, max B
on the number of layers and the spectral norm of weight matrices Bw. therefore results in a larger generalization gap and a poor generalization performance..
APPNP alleviates the aforementioned dependency by decoupling the weight parameters and feature propagation. As result, its generalization gap does not significantly change L and B increase. The optimal a that minimizes the generalization gap can be obtained by finding the a that minimize the term B3- Although APPNP can significantly reduce the generalization gap. because a single weight matrix is shared between all layers, its expressive power is not enough for large-scale challenging graph datasets [24].
To gain expressiveness, GCNII proposes to add the weight matrices back and add another apeerpparamete that explicitly controls the dependency
B.. Although GCNII achieves the state-of- offte-r performances on several graph datasets, the selection of hyper-parameters is non-trivial compared to APPNP because a, 3 are coupled with L, Bw. and d. In practice, [6] builds a very deep GCNII by choosing / dynamically decreases as the number of layers and different a values for different datasets.
By property chosen hyper-paramen parameters, we have the following order on the generalization gap given the same training iteration T: APPNP < GCNII < GCN I ResGCN, which exactly match our empirical evaluation on the generalization gap in Section 7 and Appendix E.
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 dy < d. PairNorm applies normalization on intermediate node embeddings ensure that the total pairwise feature distances remain constant across layers, which leads to less dependency on d and Bu. 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 Appendix E.3 and E.4 suggest that applying Dropout and PairNorm is hurting the training accuracy (i.e., not alleviating smoothing) but reducing the generalization gap.
Remark 1.
Decoupled GCN
We propose to decouple the expressive power from generalization ability with Decoupled GCN (DGCN). The DGCN model can be mathematically formulated as Z = E (x) and ((0 p'x (3, ( + (1 - 3,)1), where W(O), oe and 3r are the learnable weights for /th layer function (()))))) 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 decouple the weight matrices from propagation by assigning weight (()) each individual layerwise function (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 a²) After decoupling the weight matrices from feature propagation, the layerwise function (X) with more propagation steps can suffer from less expressive power. Therefore,
"A similar architecture has been previously used in [8], where they empirically show that relaxing the layer weights to negative values further boost the performance.
8

---

Geneckoation emer Thaodon
Generdlatioon oor forsters
Gerersiaat on enter teiviions
14
903 lond
04
125
130
FLacome (terniens
CCU off salk (Tod 350
Pacodki--4 vall (har7)-
50n Lofe AUL 3021
A.9 Lide Thar
JIMe 2-4
15
15
115
Figure 4: Comparison of generalization error on synthetic dataset. The curve early stopped at the
largest training accuracy iteration.
we propose assign learnable weight og for each step of feature propagation. Intuitively, DGCN assigns smaller weight og to each layerwise function (X)(X) with more propagation steps at the beginning training. Throughout the training, DGCN gradually adjusts the weight to leverage more useful large receptive field information.
(Learnable 3e) A learnable weight 3r E [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 ae and Br are pre-selected and fixed during training. We say DGCN is uniforrly stable with Coccs GnpsGi Σt (1 + nL 11 where
Pf ===C==0(va)\B)) o ( (x(a)) max (1, B + 1))
(2)
The details deferred to Appendix J, and comparison of bound to other GCN variants are summa- rized in Table 1. Depending on the automatic selection of oee, 3r, the generalization bound of DGCN between APPNP and GCN. In the following, we make connection 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 ag a a) for É < L and az (1 a)* for L given some constant a E (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 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 og and 33 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.c., with ag 1. In other word, ResNet can be regarded as
(L) = - Qgo (P the "summation of the model complexity" of L-layer. However, DGCN is using Σ ag = 1, which can be thought of as "weighted average of model complexity". Therefore, ResGCN is a special case of DGCN with equal weights ag 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.
Experiments
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 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

---

(n, A), 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-paramen tuning, and the remaining nodes as testing set. We conduct an experiment 20 times by randomly selecting (J,, A) 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 v GCNII S GCN < ResGCN, which exactly match the theoretical result in Theorem 4. More specifically, ResGCN has the largest generalization gap due to the skip connectiss 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) and Arxiv dataset respectively. Due to limited GPU memory, the number of layers is selected as the one with the best performance between to 16 layers for Arxiv dataset, to layers for Protein dataset, and 2 to 4 for Products dataset. We choose og from (0.9, 0.8, 0.5) for APPNP and GCNII, and use Bg = 0.5/ for GCNII, and select the setup with the best validation result for comparison.
epochs for Products, Proteins,
As shown in Table 2. DGCN achieves a compatible performance to GCNII 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 re-
striction on the weight matrices, it can achieve lower training error and its test
Table 2: Comparison of F1 Fc-se on OGB dataset.
%
Products
Proteins
Arvix
performance mainly restricted by its
GCN
75.39 + 0.21
71.66 + 0.48
71.56 + 0.19
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 eиror and no restriction on the weight (e.g., DGCN)
ResGCN
75.53 0.12
74.50
0.41
72.56 1 0.31
APPNP
66.35 + 0.10
71.78 + 0.29
68.02 + 0.55
GCNII
71.93
0.351
75.60
0.47
72.57 + 0.231
DGCN
76.09 + 0.29
75.45 + 0.24
72.63 + 0.12
is preferred it has higher potential reach a better test accuracy by reducing its training error.
8 Conclusion
In this work, 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 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 validate the correctness of our theory and advantages over the baselines.
't GCNII undertits with the default hyper- paraamearrettes.. & GCNII achieves 72.74 + 0.16 by using hidden dimension 256 and different design of graph convolution layer. Refer here for details.
10

---

Acknowledgements
This work was supported in part by NSF grant 2008398.
References
[1] Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations, 2020.
[2] Rianne van den Berg, Thomas N Kipf, and Max Welling. Graph convolutional matrix completion. arXiv preprini arXiv: / 701. 02266,, 2017.
[3] Olivier Bousquet and André Elisseeff. Stability and generalization. Journal of machine learning research, 2 2002.
[4] Chen Cai and Yusu Wang. A note on over-smoothing for graph neural networks. arXiv preprint 0ttt::2006.33112 2020.
[5] Lei Chen, Zhengdao Chen, and Joan Bruna. On graph neural networks versus graph-augmented mlps. In International Conference on Learning Representations, 2020.
[6] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 1725-1735. PMLR, 2020.
[7] Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
[8] Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. 2021.
[9] Weilin Cong, Rana Forsati, Mahmut T. Kandemir, and Mehrdad Mahdavi. Minimal variance sampling with provable guarantees for fast training of graph neural networks. In KDD '20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, CA, USA, August 23-27, 2020, pages 1393-1403, ACM, 2020.
[10) Zhiyong Cui, Kristian Henrickson, Ruimin Ke, and Yinhai Wang. Traffic graph convolutional recurrent neural network: A deep learning framework for network-seall traffic learning and forecasting. IEEE Transactions Intelligent Transportation Systems, 2019.
[11] Kenneth R Davidson and Stanislaw Szarek. Local operator theory, random matrices and banach spaces. Handbook of the geometry of Banach spaces, 131173366)131, 2001.
[12] Songgaojun Deng, Huzefa Rangwala, and Yue Ning. Learning dynamic context graphs for predicting social events. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2019, Anchorage, AK, USA, August 4-8, 2019, pages 1007-1016. ACM, 2019.
[13] Yash Deshpande, Subhabrata Sen, Andrea Montanari, and Elchanan Mossel. Contextual stochastic block models. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 8590-8602, 2018.
[14] Kien Do, Truyen Tran, and Svetha Venkatesh. Graph transformation policy network for chemical reaction prediction. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, KDD 2019, Anchorage, AK, USA, August 4-8, 2019, pages 750-760. ACM, 2019.
[15] Simon S. Du, Kangeheng Hou, Ruslan Salakhutdinov, Barnabás Péczos, Ruosong Wang, and Keyulu Xu. Graph neural tangent kernel: Fusing graph neural networks with graph kernels. In Advances in Neurul Information Processing Systems 32: Annual Conference Neural Information Processing Systems 2019, NeurIPS 2019, December 8- 14, 2019, Vancouver, BC, Canada, pages 5724-5734, 2019.
11

---

[16] David Duvenaud, Dougal Maclaurin, Jorge Aguilera- lntrrrapppraguiree.. Rafael Bomnez-Bmmbarelli, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan Adams. Convolutional networks on graphs for learning molecular fingerprints. In Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pages
2015.
[17] Ran El- Yaniv and Dmitry Pechyony. Stable transductive learning. In Learning Theory, 19th Annual Conference on Learning Theory, COLT 2006, Pittsburgh, PA, USA, June 22-25, 2006, Proceedings, volume 4005 of Lecture Notes in Computer Science, pages 35-49. Springer, 2006.
[18) Vikas K. Garg, Stefanie Jegelka, and Tommi S. Jaakkola. Generalization and representational limits of graph neural networks. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 3419-3430. PMLR, 2020.
[19] Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedfor- ward neural networks. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pages 249-256. JMLR Workshop and Conference Proceedings, 2010.
[20] Shunwang Gong, Mehdi Bahri, Michael M. Bronstein, and Stefanos Zafeiriou. Geometrically principled connections in graph neural networks. In 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2020, Seattle, WA, USA, June 13-19, 2020, pages 11412-1 1421. IEEE, 2020.
[21] William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 1034-1034, 2017.
[22] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance imagenet classification. In 2015 IEFE International Conference on Computer Vision, ICCV 2015, Santiago, Chile, December 7-13, 2015, pages 1026-1034, IEEE Computer Society, 2015.
[23] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016, Las Vegas, NV, USA, June 27-30, 2016, pages 770-778. IEEE Computer Society, 2016.
[24] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In Advances in Neural Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
[25] Wei Huang, Yayong Li, Weitao Du, Richard Yi Da Xu, Jie Yin, and Ling Chen. Wide graph neural networks: Aggregation provably leads to exponentially trainability loss. arXiv preprint arXiv:2103.03113, 2021.
[26] Wenbing Huang, Yu Rong, Tingyang Xu, Fuchun Sun, and Junzhou Huang. Tackling over- smoothing for general graph convolutional networks. arXiv e-prints, pages arXiv-2008, 2020.
[27] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
[28] Thomas N. Kipf and Max Welling. Semi- -upervupee classification with graph convolutional networks. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Truck Proceedings. OpenReview.net, 2017.
[29] Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
[30] Kezhi Kong, Guohao Li, Mucong Ding, Zuxuan Wu, Chen Zhu, Bernard Ghanem, Gavin Taylor, and Tom Goldstein. Flag: Adversarial data augmentation for graph neural networks, arXiv preprint arXiv:2010.09891, 2020.
[31] Srijan Kumar, Xikun Zhang, and Jure Leskovec. Predicting dynamic embedding trajectory in temporal interaction networks. In Proceedings of the 25th ACM SIGKDD International
12

---

Conference on Knowledge Discovery & Data Mining, KDD 2019, Anchorage, AK, USA, August 4-8, 2019, pages 1278-1278. ACM, 2019.
[32] AA Leman and B Weisfeiler. A reduction of graph to a canonical form and an algebra arising rechiieecatrhnni Informatsiya, 2(9):12-16, 1968.
during this reduction.
[33] Guohao Li, Matthias Müller, Ali K. Thabet, and Bernard Ghanem. Deepgens: Can gens go as deep as cnns? In 2019 IEEE/CVF International Conference on Computer Vision, ICCV 20/9, Seoul, Korea (South), October 27- -Noember 2, 2019, pages 9266-9275. IEEE, 2019.
[34] Jia Li, Zhichao Han, Hong Cheng. Jiao Su, Pengyun Wang, Jianfeng Zhang, and Lujia Pan. Predicting path failure in time-evolving graphs. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2019, Anchorage, AK, USA, August 4-8, 2019, pages 1279-1289. ACM, 2019.
[35] Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for remi-superrised learning. In Proceedings of the Thirly-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018, pages 3538-3545. AAAI Press, 2018
[36] Renjie Liao, Raquel Urtasun, and Richard Zemel. A pac-bayesian approach to generalization bounds for graph neural networks. arXiv preprint arXiv:2012.0765 2020.
[37] Andreas Loukas. What graph neural networks cannot learn: depth vs width. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
[38] Sitao Luan, Mingde Zhao, Xiao-Wen Chang, and Doina Precup. Training matters: Unlocking potentials of deeper graph convolutional neural networks. arXiv preprint arXiv:2008.088: 2020.
[39] Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In The Thirty-Third AAAI Conference Artificial Intelligence, AAAI 2019, The Thirty- First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January 27- February 1, 2019, pages 4602-4609. AAAI Press, 2019.
[40] Quynh Nguyen. On the proof of global convergence of gradient descent for deep relu networks with linear widths. arXiv preprint arXiv:2101.00661. 2021.
[41] Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
[42] Kenta Oono and Taiji Suzuki. Optimization and generalization analysis of transduction through gradient boosting and application to multi-scale graph neural networks. Advances in Neural Information Processing Systems, 33, 2020.
[43] Namyong Park, Andrey Kan, Xin Luna Dong, Tong Zhao, and Christos Faloutsos. Estimating node importance in knowledge graphs using graph neural networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2019, Anchorage, AK, USA, August 4-8, 2019, pages 596-606. ACM, 2019.
[44] Jiezhong Qiu, Jian Tang, Hao Ma, Yuxiao Dong, Kuansan Wang, and Jie Tang. Deepinf: Modeling influence locality in large social networks. In KDD, 2018.
[45] Afshin Rahimi. Trevor Cohn, and Timothy Baldwin. Semi-supervised user geolocation via graph convolutional networks. In Proceedings of the 56th Annual Meeting of the Association for Compulational Linguistics (Volume 1: Long Papers), pages 2009-2019. Association for Computational Linguistics, 2018
[46] Morteza Ramezani, Weilin Cong, Mehrdad Mahdavi, Anand Sivasubramaniam, and Mahmut Kandemir. Gen meets gpu: Decoupling "when to sample" from "how to sample". Advances in Neural Information Processing Systems, 33, 2020.
[47] Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
13

---

[48] Ruslan Salakhutdinov. Deep learning. In The 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '14, New York, NY. USA August 24 27, 2014, page 1973. ACM, 2014.
[49] Franco Scarselli, Ah Chung Tsoi, and Markus Hagenbuchner. The vapnik-chervoneniis dimension of graph and recursive neural networks. Neural Networks, 108:248-253 2018.
[50] Saurabh Verma and Zhi-Li Zhang. Stability and generalization of graph convolutional neural networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2019, Anchorage, AK, USA, August 4-8, 2019, pages 1539- 1548. ACM, 2019.
[51] Hao Wang. Tong Xu, Qi Liu, Defu Lian, Enhong Chen, Dongfang Du, Han Wu, and Wen Su. MCNE: an end-to-end framework for learning multiple conditional network representations of social network. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2019, Anchorage, AK, USA, August 4-8, 2019, pages 1064-1072. ACM, 2019.
[52] Hongwei Wang. Fuzheng Zhang, Mengdi Zhang, Jure Leskovec, Miao Zhao, Wenjie Li, and Zhongyuan Wang. Knowledge-awee wwwee graph neural networks with label smoothness regular- ization for recommender systems. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Duta Mining, KDD 2019, Anchorage, AK, USA, August 4-8, 2019, pages 968-977. ACM, 2019.
[53] Xiang Wang, Xiangnan He, Yixin Cao, Meng Liu, and Tat-Seng Chua. KGAT: knowledge graph attention network for recommendation. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. KDD 2019, Anchorage, AK, USA, August 4-8, 2019, pages 950-958. ACM, 2019.
[54] Felix Wu, Amauri H. Souza Jr., Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Q Wein- berger. Simplifying graph convolutional networks. In Proceedings of the 36th International Conference on Machine Learning, ICMI. 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 6861-6877 PMLR, 2019.
[55] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
[56) Keyulu Xu, Jingling Li, Mozhi Zhang, Simon S. Du, Ken-ichi Kawarabayashi, and Stefanie Jegelka. What can neural networks reason about? In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
[57] Keyulu Xu, Mozhi Zhang, Jingling Li, Simon Shaolei Du, Ken-Ichi Kawarabayashi, and Stefanic Jegelka. How neural networks extrapolate: From feedforward graph neural networks. In International Conference on Learning Representations, 2021.
[58] Yujun Yan, Milad Hashemi, Kevin Swersky, Yaoqing Yang, and Danai Koutra. Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks. arXiv preprint #xXv:21122.06462 2021.
[59] Chaoqi Yang, Ruijie Wang. Shuochao Yao, Shengzhong Liu, and Tarek Abdelzaher. Revisiting" over-smoothing" in deep gens. arXiv preprint arXiv:2003.1336 2020.
[60] Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2018. London, UK, August 19-23, 2018, pages 974-983. ACM, 2018
[61] Lingxiao Zhao and Leman Akoglu. Pairnorm: Tackling oversmoothing in gnns. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
[62] Kuangqi Zhou, Yanfei Dong, Wee Sun Lee, Bryan Hooi, Huan Xu, and Jiashi Feng. Effective training strategies for deep graph neural networks. arXiv preprint 200002000.07107, 2020
[63] Xianchen Zhou and Hongxia Wang. The generalization error of graph convolutional networks may enlarge with more layers. Neurocomputing, 424:97-106, 2021.
14


Reviews:
[{"review_id": "ZDVwiynGvp_", "reviewer": "Reviewer_aKcs", "summary": "The authors argue that over-smoothing does not necessarily happen in practice and prove that a deep model is expressive as long as properly trained and can converge to global optimal with linear convergence rate. They also analyze the generalization capability of GCNs  and propose a decoupled structure for GCNs to preserve the expressive power and ensure  good generalization performance.", "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. Understanding over-smoothing problem is important for GNNs and it’s still there although there are many deep GNN models can empirically get good results.\n2. I personally very like some points in this paper, e.g. “…over-smoothing is mainly an artifact of theoretical analysis and simplifications made in analysis…”; “Existing results expressive power are mixed, [38, 36, 7, 5] argue that deeper\n model has higher expressive power but [40, 26, 25] has the completely contradict result”\n3. The authors provide detailed theoretical analysis of over-smoothing and it’s important for the whole ML community.\n\n\nWeakness&Advice:\n\n1. In theorem 2, why do you need $d_L \\geq N$. This condition seems impractical.\n2. Page 7 is the worst part of this paper because of writing problem. The writing is understandable but not reader friendly.\n3. The font size in all figures need to be enlarged.\n4. Lemma 1 can be moved to appendix and theorem 4 need to be elaborated. The content in page 7 is not reader friendly.\n4. In Figure 4, some curves stops before iteration 200. Need more explanation. What is the results on test set.\n5. Line 335-337, “…DGCN assigns smaller weight to each layerwise function $f^l(X)$ with more propagation steps at the beginning of training. Throughout the training, DGCN gradually adjusts the weight to leverage more useful large receptive field information.” It’s better to provide a figure on how $\\alpha_l$ changes during training to confirm this claim.\n\nSome grammar problems: \n\nLine 5, “…over-smoothing not necessarily  happen…” —> “…over-smoothing does not necessarily  happen…”.\nLine 226, “a deeper GCNs has worse performance” —> “a deeper GCN has worse performance”. There are some misuses of ‘GCN’ and ‘GCNs’ in other places, please double check.\n\nI will raise my score if the writing can be improved. Overall, I would like to see this paper to be published.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the authors adequately addressed the limitations and potential negative societal impact .", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "ThCn4gw_qXj", "reviewer": "Reviewer_HPrn", "summary": "The paper provides a novel theoretical understanding of over-smoothing and point out that the major impact of poor performance is due to the generation gap. The paper brings a new point about why deep GCN fails. Moreover, the paper designs a new framework according to their theorem although the proposed framework is just a dense version of GCNII.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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:\n1. The paper point out the issues that the previous papers may neglect some other reasons that cause poor performance besides over-smoothing. Many papers assumes that the singular values of weights <1 and the second largest eigenvalue <1. However, the paper finds that the singular values of weights is not always <1 and the second largest eigenvalue is very close to 1 in the rea-world datasets. Consequently, it may not cause the vanishing of the layer outputs along infinite layers.\n2. The paper theoretically analyzes another fact of poor performance, the generation gap. Lemma 1 formulates the generation gap in terms of Lipschitz continuity, smoothness and gradient scale.\n\nCons:\n1. In Figure1, the paper claims that GCN would reach a high training accuracy on Cora with efficient number of iterations. However, I tested GCN on Cora with lr=[0.01~$10^-10$], dropout=0.5, hidden=128, epochs=6000, layers=8 (Basic modules from dgl). I did not get neither converged training loss nor high training accuracy. So how does the authors train the GCN to get high training accuracy?\n2.  The experimental results does not show the results with very deep GCNs such as 32 layers or 64 layers. And the paper did not compare with some other over-smoothing-coping methods such as dropedge, Pair norm, etc. Or I might miss them in the Appendix.\n3. The main theoretical results are not related to the Laplacian matrix. It seems that the paper relax the Laplacian matrix to be no larger than 1 (The largest eigenvalue). It could be a tighter bound with the second largest eigenvalue. Moreover, it is little confused between layer number $L$ and Laplacian matrix $\\mathbf{L}$. \n4. In [26], it involves the analysis for GCN with bias. The paper does not discuss the situation with bias. It might be a good future work. \n5. The fonts of figures are too small.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12"}, "extra_text": {}}, {"review_id": "MX_Y6WCC1Ej", "reviewer": "Reviewer_Z7vj", "summary": "The deals with semi-supervised learning with graphs using graph neural networks. Specifically, it investigates the benefits of depth both from a (learning) theory as well as an empirical standpoint. \n\nThe key contributions are:\n1. Questioning the common folklore belief that deep GNNs are not expressive due to \"over-smoothing\"\n2. Studying the generalization performance of GNNs using uniform stability theory \n3. Introducing  \"Decoupled GCNs\" which learn linear combinations of single-layer GNNs (using powers of the Laplacian).\n4. Experimental study validating the theoretical results. ", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "**Contribution/Originality:** The paper aims at demystifying the role of depth for the expressivity/generalization properties of GCNs/GNNs. To that, they first try to show that the number of expressible equivariant functions grows exponentially with the depth (Thm 1). They then show that deeper GCNs need more iterations to converge while achieving the same training error (Thm 2, *the exact setup of the statement, seems to be missing in the main text*. It is not clear to me.). They then leverage known results from learning theory, namely the \"transductive uniform stability bound\", to study the generalization performance of different variants of GCNs, which, as far as I know, has not been done so far.\nMoreover, they introduce \"decoupled GCN\", see lines 324/5, which learn linear combinations of single layer GNNs (using powers of the Laplacian) and relate their generalization performance to other GCN variants. \nThe theory is complemented by an experimental study validating the theoretical results. \n\n**Clarity:** Unfortunately, the paper is **not clear**, it seems to be written up in a hasty manner. For example:\nIn the statement of Thm 1 the meaning of \"richness\" is not clear, although it could have been made clear as the result is just a simple combinatorial insight. This sloppiness continues throughout the whole paper making some theorems almost non-understandable (e.g., Thm. 2).\n\n**Significance:** The findings are significant to the GNN community. \n\nPros:\n+ First (real) principled attempt to understand the role of depth in the generalization performance of GNNs \n+ Good coverage of (relevant) related work\n+ Reasonably well-executed experimental study\n\nCons:\n+ Unclear statements and sloppiness throughout. The presentation lacks clarity overall.\n\nMinor remarks:\nThere are many spelling and grammar mistakes throughout the paper that could have been found easily by using a standard spell/grammar checker. \n\nSuggestion:\nPut in the work and make everything mathematically precise and clear, while also making it easier for the reader to understand the significance of the results. I am looking forward to a revised, cleaned-up version of this paper. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not applicable. ", "review_text": "", "extra_scores": {"ethical_concerns": "Not applicable. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4h"}, "extra_text": {}}, {"review_id": "5wj0a4Sh7Vn", "reviewer": "Reviewer_btGR", "summary": "This paper analyzed GCN model for node classification in depth. The paper first analyzed the deep model's performance degeneration problem and argued that the deep model's expressiveness is not worse than shadow model so it does not suffer from oversmoothing problem. In fact, the degeneration of deep model comes from the hardness of training instead of oversmoothing, and the papers theoretically proved that deep model needs more iterations to converge, under a strong assumption. The above explanation explained the training loss but not characterize the final test performance. The author further explored the generalization error (the gap between training loss and test loss) and proved that under transductive setting the generalization error is affected by the number of training epochs, the number of layers, singluar value of weight matrix and largest node degrees, which explained why deep models have degenerated test performance. The author finally proposed a weight to decouple weight matrix and feature propagation operations, which keeps the expressiveness and also improves generalization ability. ", "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": "1. Originality: the analysis of performance of deep models is comprehensive in terms of training and test performance, and is novel. The author gives enough empirical observations as well as solid theoretical analysis (although some parts are not clear enough, and I'm not sure whether the proof contains error or not). Overall the novelty is great.\n\n2. Quality: in general I buy the story as all explanations align with my own experience and also greatly explains their observations. However I do have several questions. And feel some claims seem too aggressive without solid enough theoretical results. \n - Line 120 defines the normalized Laplacian matrix and DAD which is not correct, I-DAD is the normalized Laplacian matrix.\n - Theorem 1 charaterize node feature richness by using graph-level result, and this needs to view each node embedding as a graph embedding of the computational tree structure. I want to know whether the result rely on independent assumption of very computational subgraph (in definition 1). In general N computational subgraphs in original GNN are coupled together instead of independent, which is true for graph level tasks. \n - Theorem 2 needs dL >= N, which is not valid in real world, (however you can assume a wide enough representation with NxN matrix size in theory) , I would like to know how does this affect the result of theorem 2 if dL is a constant like 512. \n - Statement from line 308 to line 310 seems to bold and incorrect to me, as you can also pickup hyper-parameter to make the order incorrect. I hope the author can provide more solid analysis instead of this vague argument. This argument is intended to match empirical observation in my understanding. \n- There are conflicted statement about resnet, the line 292-295 is very different from line 354-357. One argument said residual connection worse the generalization while the other said that resnet is very similar to DGCN. I hope the author provide more analysis to explain why adding residual worse the generalization ability. \n - The Remark 1 is great empirical observation, however the statement sounds too confirm to me. If you can give more theoertical analysis out of empirical observation the remark 1 will become solid to me. \n - The generalization error is showed only on synthetic dataset and cora. I would like to see the empirical analysis over OGB dataset. \n - Table 1 is hard to read as it involves so many equations, if you would provide some intuition of them on the title of the table it will be a lot easier to follow. \n\n3. Clarity: in general the paper is well-written and easy to follow.\n\n4. Significance: the DGCN performance is not solid enough. This is acceptable as all previous analysis is novel and comprehensive enough. Nevertheless, I do expect that DGCN can help better generalization ability as it is specially designed. The similar performance between DGCN and APPNP suggests the generalization gap is not fully charaterized by the theory presented in this paper (whether upper bound is tight or not). \n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

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

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

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