Towards Deepening Graph Neural Networks: A GNTK-based Optimization Perspective
Authors: Wei Huang
Yayong Li
weitao Du
Richard Xu
Jie Yin
Ling Chen
Miao Zhang
Venue: ICLR 2022 Poster (2022)
Keywords: Trainablity
Graph Neural Tangent Kernel
Critical DropEdge

Abstract: Graph convolutional networks (GCNs) and their variants have achieved great success in dealing with graph-structured data. Nevertheless, it is well known that deep GCNs suffer from the over-smoothing problem, where node representations tend to be indistinguishable as more layers are stacked up. The theoretical research to date on deep GCNs has focused primarily on expressive power rather than trainability, an optimization perspective. Compared to expressivity, trainability attempts to address a more fundamental question: Given a sufficiently expressive space of models, can we successfully find a good solution via gradient descent-based optimizers? This work fills this gap by exploiting the Graph Neural Tangent Kernel (GNTK), which governs the optimization trajectory under gradient descent for wide GCNs. We formulate the asymptotic behaviors of GNTK in the large depth, which enables us to reveal the dropping trainability of wide and deep GCNs at an exponential rate in the optimization process. Additionally, we extend our theoretical framework to analyze residual connection-based techniques, which are found to be merely able to mitigate the exponential decay of trainability mildly. Inspired by our theoretical insights on trainability, we propose Critical DropEdge, a connectivity-aware and graph-adaptive sampling method, to alleviate the exponential decay problem more fundamentally. Experimental evaluation consistently confirms using our proposed method can achieve better results compared to relevant counterparts with both infinite-width and finite-width. 

Published as a conference paper at ICLR 2022
TOWARDS DEEPENING GRAPH NEURAL NETWORKS: A GNTK-BASED OPTIMIZATION PERSPECTIVE
Wei Huang -f
Yayong Li
University of Technology Sydney weihuang. ut gma ccom
University of Technology Sydney yayong 1 d:i@student...mm wt.. atts.edu.au
Weitao Du
Jie Yin
Northeastern University
The University of Sydney jie. yinesydney.....
weitao. du@northwestern. edu
www.yyynneyyeuuuua...ee.uu edu. au
Richard Yi Da Xu Ling Chen
Miao Zhang
University of Technology Sydney (YiDa. Xu, ling. chen] edu.au au
Aalborg University miaozêcs aau. dk
ABSTRACT
Graph convolutional networks (GCNs) and their variants have achieved great suc- cess in dealing with graph-structured data. Nevertheless, it is well known that deep GCNs suffer from the over-smoothing problem, where node representations tend to be indistinguishable as more layers are stacked up. The theoretical re- search date on deep GCNs has focused primarily on expressive power rather than trainability, an optimization perspective. Compared to expressivity, train- ability attempts to address more fundamental question: Given a sufficiently ex- pressive space of models, can we successfully find good solution via gradient descent-based optimizers? This work fills this gap by exploiting the Graph Neural Tangent Kernel (GNTK), which governs the optimization trajectory under gradi- ent descent for wide GCNs. We formulate the asymptotic behaviors of GNTK in the large depth, which enables to reveal the dropping trainability of wide and deep GCNs at an exponential rate in the optimization process. Additionally, we extend theoretical framework niques, which are found to be merely able to mitigate the exponential decay trainability mildly. Inspired by our theoretical insights on trainability, we propose Critical DropEdge, a connectivity-aware and graph-adaptive sampling method, to alleviate the exponential decay problem more fundamentally. Experimental eval- uation consistently confirms using our proposed method can achieve better results compared to relevant counterparts with both infinite-wide and finite-width.
analyze residual connection- tech-
INTRODUCTION
Recently, Graph Neural Networks (GNNs) have shown incredible abilities to learn node or graph representations and achieved superior performance on various downstream tasks, such as node clas- sification (Kipf Welling, 2017; Veličković et al., 2018; Hamilton et al., 2017), graph classifica- tion (Xu et al., 2019; Lee et al., 2019b; Yuan & Ji, 2020), and link prediction (Kipf & Welling, 2016), etc. However, most GNNs (e.g., GCNs) achieve their best only with a shallow depth, e.g.. or 3 layers, and their performance grows. Towards this phenomenon, research attempts have been made to deepen understanding of current GNN architectures and their expressive power. ei al. (2018) showed that GCN is a special form of Laplacian smoothing, which mixes node representations with nearby neighbors. This mech- anism potentially poses the risk of over-smoothing as more layers are stacked together, where node representations tend to be indistinguishable from each other. Oono & Suzuki (2020) investigated
those tasks would promptly degrade as the number of layers
"Equal Contribution.
Work partially performed while The University of Sydney

---

Published as a conference paper at ICLR 2022
the expressive power of GNNs using the asymptotic behaviors as the layer goes to infinity. They proved that under certain conditions, the expressive power of GCN is determined by the topological information of the underlying graph inherent in the graph spectra.
Nevertheless, it remains clusive how to theoretically understand why deep GCNs fail to optimize. Existing theoretical investigation (Oono & Suzuki, 2020; Xu et al., 2019) GNNs focus mainly on expressivity, which measures the complexity of functions that can be represented by a neural network. Exploring expressivity theoretically convenient, but the corresponding conditions may be violated during the gradient training process, thereby leading to inconsistencies between theo- retical conclusions and empirical results of trained networks (Gühring et al., 2020). Compared to expressivity, trainability addresses a more difficult but fundamental perspective of neural networks: How effectively a neural network can optimized via gradient descent. The advantage of investi- gating trainability is that we can directly determine whether GNNs can be successfully trained under certain conditions, and to what extent. We are therefore inspired to raise two important questions:
Can we theoretically characterize the trainability of graph neural networks with respect to depth, thus understanding why deep GCNs fail to generalize?
Can we further design an algorithm to facilitate deeper GCNs, benefiting from our theoretical investigation?
Our answers are yes to both questions. We resort to the infinitely-wide multi-layer GCN to de- rive our solution. The research on infinitely-wide networks can be traced back to the seminal work of Neal (1996), which showed that single hidden layer networks with random weights at initializa- tion (without training) are Gaussian Processes (GPs) in the infinite width limit. Later, the connection between GPs and multi-layer infinitely-wide networks with Gaussian initialization (Lee et al., 2018; de G. Matthews et al., 2018) and orthogonal weights (Huang et al., 2021) was reported. Recent trends in Neural Tangent Kernel (NTK) have led to a proliferation of studies on the optimization and generalization of infinitely (ultra)-wide networks. In particular, Jacot et al. (2018) made a ground- breaking discovery that gradient descent training in the infinite width limit can be captured by an NTK. Du et al. (2019b) formulated Graph Neural Tangent Kernel (GNTK) for infinitely-wide GNNs and shed light theoretical guarantees for GNNs. Prior to the discovery of GNTK, there was lit- tle understanding of the non-convexity of GNNs, which is analytically intractable. In the learning regime of GCN governed by GNTK, the optimization becomes an almost convex problem, making GNTK a promising perspective to study the trainability of deep GCNs.
In this work, we leverage the GNTK techniques of infinitely-wide networks to investigate whether ultra-wide GCNs are trainable in the large depth. In particular, we formulate the large-depth asymp- totic behavior of the GNTK, illuminated by innovative works on deep networks (Hayou et al., 2019b; Xiao et al., 2020), through which we can analyze the optimization properties of deep GCNs. Specif- ically, we make the following contributions:
To our best knowledge, we are the first to investigate the trainability of deep GCNs through GNTK. We prove that all entries of a GNTK matrix regarding pair of graphs converge exponentially to the same value, making the GNTK matrix singular in the large depth. We thus establish a corollary that the trainability of ultra-wide GCNs exponentially collapses node classification tasks.
We apply our theoretical analysis to the residual connection- theory shows that residual connection can, to some extent, slow down the exponential decay rate of trainability, but lack the ability to fundamentally solve the problem. This result enables to better understand why and to what extent recent residual connection-basee methods work.
techniques for GCNs. Our
Our theoretical framework provides insights to guide the development of deep GCNs. We further propose an edge-based sampling method, named Critical DropEdge, to effectively mitigate the exponential decay of trainability. This graph-adaptive and connectivity-awant method easy to implement in both finitel--wide and infinitely-wied GNNs. Our experiments show using the proposed method can outperform competitors in the large depth.
BACKGROUND AND PRELIMINARIES
We first review the results of infinitely-wide neural networks at initialization. We then review NTK, making a connection to trainability. Finally, we introduce GCNs along with our setup and notation.
2

---

Published as a conference paper at ICLR 2022
2.1 INFINITELY- WIDE NETWORKS AT INITIALIZATION
We begin by considering a fully-connected network of depth L with width my in each layer. The weight and bias in the 1-th layer are denoted by W(O E Im x and 60) e R", Letting the pre-activations be given by hg?, information propagation in this network is governed by,
h (
Ow
((
((w!Dgh-1) h tbb
(1)
mi
where : IR + R is the activation function, one and define the variance scale of the weights and biases, respectively. Given the parameterization that weights and biases are randomly generated by i..dd normal distribution, i.e., W bb ~ [O 1), the pre-activations are Gaussian distributed in the infinite width limit as m1, m2, ................................ mi-1 - oC. This results from the central limit theorem (CLT). Consider dataset X E [Raxd of size n |X], the covariance matrix of Gaussian process kernel (GPK) regarding infinitely-wide network is defined by E x') = Elh (x) (2)h
( (x')] Ac-
cording to the signal propagation (1), the covariance matrix or GPK with respect to layer can be described by recursion relation. (z, (z)x')) = o. -0 (((((=))((((())) +
The mean-fichl theory is a paradigm that studies the limiting behavior of GPK, which is a mea- sure of expressivity for networks (Poole et al., 2016; Schoenholz et al., 2017). In particular, ex- pressivity describes to what extent two different inputs can be distinguished. The property of evolution for expressivity (1) (I)xz)) is determined by how fast it converges its fixed point Ex (1x, 0om Σ (ar, x²). It is shown that in almost the entire parameter space spanned by syper-parameee ow and db. the evolution exhibits a dramatic convergence rate formulated by an exponential function except for critical line known as the edge of chaos (Poole et al., 2016; Schoenholz et al., 2017). Consequently, an infinitely-wide network loses its expressivity exponen- tially in most cases while retaining the expressivity the edge of chaos. Given this reason, we focus on the edge of chaos in this work. In particular, we set the value of hyper--arrametes to satisfy, o² DD ( ('''((V (vq²z) = where q is the fixed point diagonal entries the covariance matrix, and Dz V2x I dze faee-=== ==² is the measure for normal distribution. For the ReLU activation, edge of chaos requires o = 2 and of = 0.
2.2 NEURAL TANGENT KERNEL AND TRAINABILITY
Most studies on iife networks through mean-field theory (Poole et al., 2016; Schoen- holz et al., 2017) have focused solely on initialization without training. Jacot et al. (2018) took step further by considering -nfe networks trained with gradient descent. Let 1 be the learning rate, and L be the loss function. The dynamics of gradient flow for parameters
0 ve (1) ,b, ((9)) E IR [ m=(m=-++))x1 the vector of all parameters, given by,
a0 Ōt
-- -Voo==)) VX(X)
Then, the dynamics of output functions f(X) vee(f R x1 follow,
0f((x) = (X) =
00
(3)
Ø1
where the NTK at time is defined as,
Ox(X Voli(X)Vof( E B
(4)
In general case, the NTK varies with the training time, thus providing substantial insights into the convergence property of neural networks. Interestingly, as shown by Jacot et al. (2018), the NTK converges to an explicit limiting kernel and does not change during training in the infinite- width limit. This leads to a simple but profound result in the case of mean squared error (MSE) loss, = 1 [x)( Y|2, where Y is the label associated with the input X,
(5) where 2x is the limiting kemne.. This is the solution to an ordinary differential equation. As the training time & tends to infinity, the output function fits the label very well, i.e., foo Y. As
S((X (I 7x. + - - (X.X)) (x(X)
3

---

Published as a conference paper at ICLR 2022
proved by Lemma in Hayou et al. (2019b), the network is trainable only if O (X, is non- singular. Quantitatively, the condition number a = Amax/ Amin can be a measure of trainability as confirmed by Xiao et al. (2020).
2.3 GRAPH CONVOLUTIOOAL, NETWORKS
We define undirected graph as G (V,E), where V is a set of nodes and È is set of edges. We denote the number of nodes in graph G by n = [V] The nodes are associated with a node feature matrix X Rexd and the corresponding labels are Y R"*k with d and & being the dimension of node features and number of classes, respectively. In this work, we develop our theory towards understanding the trainability of GCNs on node classification tasks.
GCNs iteratively update node features through aggregating and transforming the representations of their neighbors. Figure in Appendix A illustrates an overview of the information propagation in a general GCN. We define propagation unit to be the combination of a Rtlaaee multi-layer pereeptron (MLP) and one aggregation operation. We use subscript (r) to denote the layer index of MLP in each propagation unit and superscript (1) to indicate the index of aggregation operation, which is also the index of the propagation unit. L is the total number of propagation units. To be specific, the node representation propagation in GCNs through an MLP follows the expression,
(1) (1) (u)
Σ
(c)
((R)
vEN(u)Uu W(
M (1) (u) = Tw ((W (o (w)) tbb
vm
where ((0) = X, ( E R. Xmi-1, and (r) E T. are the learnable weights and biases, respec- tively, & is the activation function, (uu) is the neighborhood of node u, and W(u) U is the union of node u and its neighbors. Equation (6) reveals the node feature aggregation operation among its neighborhood according to a GCN variant (Hamilton et al., 2017). Equation (7) is a standard non- linear transformation with NTK pirattrratttiinntionn (Jacot et al., 2018), where m is the width, i.e.. number of neurons in each layer, ow and σ₁ define the variance scale of the weights and biases. For the activation function, we focus on both ReLU and Tanh, which are denoted as 6(x) = ma x} and o(x) ()) tanh( (z), respectively. Without loss of generality, our theoretical framework can handle other common activation functions, whereas the GNTK work (Du et al., 2019b) only adopted ReL.U.
3
AGGREGATION PROVABLY LEADS TO EXPONENTIAL TRAINABILITY Loss
3.1 GNTK FORMULATION
Based on the definition of NTK (4), we recursively formulate the propagation of GNTK in the infinite-width limit. As information propagation in GCN is built on two operations: aggregation (6) and non-linear transformation (7), the corresponding formulas of GNTK are expressed as follows,
% (u, [W(2) + ((()) +1
Σ DEN EN'''U
Σ
+ 0117)) (v,
(8)
9 (u, n') o (u, u 2/)=(()) (1 (u, u') (u,
The two equations above correspond to the aggregation operation and MLP transformation, respec- tively. To compute the GNTK with respect to the depth, the key step to obtain the covariance matrix >i1) (u, u') = 1i (u) (w)))(())) (u')). According to the CLT, node representation ((r) (1) is Gaussian distribution in the infinite- width limit. Applying this result to equations (6) and (7), the resultant covariance matrix is composed of two parts,
16 (u. IN(2)) + [(())) +1
Σ VEN d'N
Σ
I(t-1)
(0,
(10)
((R)
10 (u, u') _ 21 w (0.5tH) .)) [d(2))()))] tof
(11)
110) (u, = o 2n ( (o.5.1..)) [ + to²
4

---

Published as a conference paper at ICLR 2022
The first equation (10) results from the aggregation operation. Mcanwhile, the second equation (11) corresponds to the R-times non-linear transformations, where Es,,,, takes the expectation with respect centered Gaussian process of covariance $:(0 u, u', and denotes the derivative of øb
(r-1) IR_22 for previous MLP layer across
3.2 TRAINABILITY IN THE LARGE DEPTH
We aim to characterize the behavior of GNTK matrix O (C) E Rnx*, as the depth tends to infinity. From the GNTK formulation, both aggregation (8) and transformation (9) contribute simultaneously to the final limiting result. We derive our theorem on the asymptotic behavior of infinitely-wide GCN in the large depth limit, which is given as follows:
Theorem 1 (Convergence rate of GNTK). If transition matrix A(G) E "R"2xn" is irreducible and aperiodic, with stationary distribution vector #(G) 18 where 6 (G) = A(G)) A(
and 6 (r) (G) E TT²x1 is the result of being vectorized. Then, there exist constants O < a < 1 and
C' > 0, and constant vectors U. E R=n x1 depending on the number of MLP iterations R, such that O (u, (G)) RRÚ 1²) Ca'.
The proof sketch follows a divide-and-conquee manner. In particular, we first analyze the network with only aggregation and prove that A(G) is Markov transition matrix. Then, formulate the behavior of MLP the large depth based on Hayou et al. (2019b). Finally, we derive the final result by considering the operations. We leave the complete proof in Appendix B.
In Theorem 1, we rigorously characterize the convergence properties of GNTK in the large depth limit. As the depth goes infinity, all entries in the GNTK converge exponential rate. We thus have e
unique quantity at an ( (G) ze #(G)" (RIT) as + oc, where 1ax is an (n x n)-
dimensional matrix whose entries are one. The exponential convergence rate of e(() (G) implies that the trainability of infinitely-wind wide GCNs degenerates dramatically, stated below.
Corollary 1 (Trainability of ultra-wide GCNs). Consider GCN of the form (6) and (7), with depth number of non-linear transformations r, an MSE loss, and a Lipchitz activation, trained with gradient descent a node classification task. Then, the oulput function follows, fe(X)-
fu(X) + (I (I-e- -e--- (G) Then, θ (g) (G) is singular when + cC. Moreover, there exists a constant C > 0 such that for all > 0, [X) Y|| >.
We leave proof in Appendix According to the above corollary, as 1 - co, the GNTK matrix would become a singular matrix. This would lead to discrepancy between output f((X) and label Y. which means GNTK loses the ability fit the label. Therefore, an wide GCN with large depth cannot be trained successfully node classification tasks.
TOWARDS DEEPENING GRAPH NEURAL NETWORKS
4.1 THEORETICAL ANALYSIS ON RESIDUAL CONNECTION
We have so far characterized the trainability of vanilla GCNs through the GNTK and showed that the trainability of ultra-wide GCNs drops an exponential rate. Recently, considerable efforts have been made to deepen GCNs, among which residual connection-based techniques are widely applied to resolve the over-smoothing problem (Li et al., 2019). We now apply our theoretical framework to analyze to what extent residual connection techniques could alleviate the trainability loss problem.
We first consider residual connection in aggregation, in which the propagation of the GNTK can be formulated as
(G) = (1 ())(G))(--)(( + 8ō)-))(G),
(12)
where < 5 1 Taking equation (12) as a new aggregation process, then (0) A(G))(( (G), where Á(G) = - () + 8I. We prove that Á(G) is also a transition matrix with greater second largest eigenvalue compared the original matrix A(G).
5

---

Published as a conference paper at ICLR 2022
Theorem 2 (Convergence rate of residual connection in aggregation). Consider GNTK of non- linear transformation (9) and residual connection (12). Then with a stationary vector (G) for A(G), there exist constants 0 π < 1 and C O, and constant vectors e and V' depending on (r) (u, ut)- - #(G) (Rlū+ +") S Cä'. Furthermore, we denote the second largest eigenvalue of A(G) and A(G) as X2 and )2 respectively. Then, X22 > A2-
R. such that 10
The detailed proof of Theorem 2 and the relationship between convergence rate and the second largest cigvenvalue can be found in Appendix D.I. This theorem implies that a residual connection in aggregation can slow down the convergence rate, which is consistent with empirical observations that residual connection can help deepen GCNs.
Then, we consider residual connection only applied on non-linear transformation (MLP). In this case, the recursive equation for the corresponding GNTK can be expressed as,
( (u, n') ( (1-1)(u; u ) (2)) (u, + +1) + 2 (u, n')
(13)
This formula is similar to the vanilla GNTK in the infinite-widd limit. Only an additional residual term appears according to residual connection, It turns out that this term may not help slow down the convergence rate for non-linear transformation.
Theorem (Convergence rate of GNTK with residual connection between transformations). Con- sider a GNTK of the form (8) and (13). If A(G) is irreducible and aperiodic, with stationary distribution HGG), then there exist constants 0 < a < 1 and C > O, and constant vectors and if depending on R, such that, (1) (u, u') (G) (RI(1 + - Ri + r') S Co'.
Note that a in Theorem the same as in Theorem 1. The proof of Theorem 3 can be found in Appendix D.2. Theorem demonstrates that adding residual connection in MLP can not even reduce the convergence rate trainability. Finally, we consider residual connection applied to both aggregation and non- onnlir transformation simultaneously:
Corollary (Convergence rate of GNTK with residual connection in aggregation and transforma- tion). Consider a GNTK of the form (12) and (13). If A(G) is irreducible and aperiodic, with a stationary distribution (G), there exist constants 0 < â < 1 and C >> 0, and constant vectors U, T E RR1xx1 depending on R, such that (0(0) (r) (1, u') - ((G) (Rl(1 + Th =2) S Cāa.
4.2 A NEW SAMPLING METHOD: CRITICAL DROPEDGE
Residual connection is designed from layer-wise perspective, but it has limited abilities to miti- gate the exponential decay of trainability. To better resolve this problem, we need to look deeper into the root cause of the problem the transition matrix corresponding to the aggregation opera- tion. A necessary condition for matrix A(G') to be a probability transition matrix that graph G is connected. Thus, breaking the connectivity condition is promising way of better solving the exponential decay problem. One such method is to perform edge sampling guided by the critical percolation theory (Huang et al., 2018; Erdös & Rényi. 1961) in random graphs
On a finite complete graph of n nodes, there exist E, = n(n 1)/2 edges between all pairs of nodes. A random graph G is achieved by randomly and uniformly preserving some edges from the [E]
complete graph with an edge probability as p E, where |E] is the number of edges preserved in the random graph. In this way, the critical percolation can be realized in the random graph with a critical edge probability Pe = 11/(n - 1) (Erdós & Rényi, 1961). In the thermodynamic limit of - oc, the critical random graph exhibits critical connectivity: the probability that there exists path from a fixed point to another point within a certain distance decreases polynomially.
Proposition 1 (Critical connectivity in random graph (Erdös & Rényi, 1961)), Suppose random graph G has n nodes with constant edge probability p. (1) If p Pe, then almost every random graph is such that its largest component" is of size O(log (2) If > Pe. the random graph has a giant component of size (1 -pp + (1))),, where Opp < 1; (3) If = Pe, then the maximal size of component of almost every graph has order 2/3
In graph theory. component of undirected graph is induced subgraph in which any two nodes are connected to each other by paths.

---

Published as a conference paper at ICLR 2022
(+)
Collagse
Aggrapation Collapoe
Collagge
1.00
1.00
Nomaleed CNTK
0.75
0.6
0.:00
0.50
0.4
0.25
0.25
0.2
250
500
750
25/1
500
750
250
500
750
(d) Vanilia GNTK Convergerie Rate
(6) Residual seatiiation Convergence Rate
(1) Residval MLP Convergence Rate
Elemens-War Ditaace of CNTK
10a
10"
exp 1-115_1)
expp0-00.13
exp(-0.11x)
10-1
10-2
10"2
10
10-1
10-1
10-1
y=xxp(-0.15x)
10-7
Dapth
Death
Depch
Figure I: Convergence rate GNKT. (a)-(c) Entries of the normalized (residual connection) GNTK function of the depth, defined as Rl r. All entries tend to have the same value the depth grows. (d)-(f) The element (entry)-wise distance of the normalized (residual connection) GNTK function of the depth. The convergence rate can be bounded by exponential function exp(-0.15x) for vanilla and residual MLP GNTK, whereas the convergence rate of residual aggregation bounded by y = exp(-0.11æ).
The proposition above implies that the information transforms in the critical random graph at poly- nomial rate rather than an exponential rate. This inspires us to solve the problem of exponentially dropping trainability through designing graph-dependent and connectivity-awaet rithm called Critical DropEdge. In particular, given a graph G, we randomly drop some edges and preserve the number of edges E, Es Pe n/2, approximate the critical graph. Unlike DropEdge (Rong et al., 2019) that randomly removes a certain number of edges from the input graph, our method fixes the edge preserving percentage as p E |V] It is worth noting 2|E|" that DropEdge may choose the edge probability p < Pe where information can only be passed to a distance of O(log n) in the graph, or > Pe where the exponential decay of trainability may occur. further discussion of the relationship between Proposition and the trainability of the corresponding GNTK can be found in Appendix E.
sampling algo-
EXPERIMENTS
In this section, we empirically verify our theoretical results and validate the proposed Critical DropEdge method on node classification tasks. Details of four real-world graph datasets used for node classification are summarized in Table 3 in Appendix F.I.
5.1 CONVERGENCE RESULTS OF GNTKS
Theorems 1-3 provide theoretical convergence rates for (residual) GNTK. We show the correspond- ing numerical verification in Figure 1. We select graph randomly from a bioinformatics dataset (i.e.. MUTAG), which consists of 18 nodes and 21 edges. We generate GNTK of the graph using the implementation of Du et al. (2019h), with ReLU activation, R = and 300. Figure ((a)- (c) show that all entries of normalized GNTKs converge to an identical value as the depth goes larger. Figure (dd)-(f) further indicates that the convergence rate of GNTK is exponential, re- flected by our theorems. By comparing convergence rates, we conclude that the residual connection in aggregation can slow down the convergence rate, which consistent with Theorem 2.
5.2 TRAINABILITY OF WIDE GCNS
We further examine whether ultra-wide GCNs can be trained successfully for node classification. We conduct experiments GCN (Kipf & Welling, 2017), where apply width of 1, 000
7

---

Published as a conference paper at ICLR 2022
each hidden layer and the depth ranging from 2 to 29. Figure 2 shows the training and test accuracy on Cora, Citesser and Pubmed after 300 training epochs. These results show a dramatic drop in both training and test accuracy as the depth grows, confirming that wide GCNs lose trainability significantly in the large depth on node classification, as revealed by Corollary 1.
5.3 PERFORMANCE OF CRITICAL DROPEDGE
Node Classification
We apply Critical DropEdge (referred to as C- DropEdge) to finitely-wide and infinitely-wide GNNs on semi-supervised node classification. The implementation details are given in Appendix F.2.
1.0
Citeseer
0.8
Cora
Accuracy
0.6
Pubmed
For finitel--wide GNNs, we consider three back- bones: GCN, JKNet, and IncepGCN (Rong et al., 2019). For DropEdge, we use the hyper- parameters reported in Rong et (2019) to obtain the results. For C-DropEdge, we perform random hyper-parameter search and fix the edge preserving rate as p(G) 2 In addition, we compare with DGN (Zhou et al., 2020), normalization-basel baseline, which uses GCN (Kipf Welling, 2017) and GAT (Veličković et al., 2018) backbones.
0.4
0.2
0.0
10
20
30
Depth
[V
Figure 2:
Training and test accuracy w.r.t. model depth. Solid and dashed lines are train and test accuracy respectively.
Table summarizes node classification performance of finitely-wide GNNs with 4/8/16/32 layers on three citation networks (Cora, Citesser, Pubmed) and co-author network (Physics). In par- ticular, we report the best performance across different backhones for DropEdge, C-DropEdge and DGN, and leave separate results with different backbones in Appendix G.2. The reported results are the mean and standard deviation over 10 times. As can be seen, C-DropEdge consistently outper- forms GCN, DGN, and DropEdge, especially when the model is deep. Besides, C-Dropldge can achieve smaller eπror variances, demonstrating stronger robustness than DropEdge.
For infinitely wide GCNs, we consider two backbones: GCN (Kipf & Welling, 2017) and JKNet (Xu et al., 2018). The corresponding results can be found in Appendix G.I.
Comparison to DropEdge. DropEdge and C-DropEdge differ largely in their hyper-parameter search space. To ensure good performance, DropEdge needs exhaustively search for the most appropriate edge preserving percentage- one of the most significant hyper-parameters that has a crucial influence on the final performance. contrast, C-DropEdge has a fixed and graph-dependent edge preserving rate, which implies its dge. To verify C-DropEdge can achieve the results close to optimal, we conduct experiments with various edge preserving rates, and present the results in Table 2. We conclude that, from both theo- retical and empirical perspectives, the edge preserving percentage set by C-DropEdge is reasonable and effecttve, achieving the results close to optimal.
space is much smaller than that of DropE-
RELATED WORK
Neural Tangent Kernel. NTKs are used to describe the dynamics of infinitely-wide networks during gradient descent training. In the infinite-width limit, NTK converges to an explicit limit- ing kernel; besides, it stays constant during training, providing a convergence guarantee for over- parameterized networks (Jacot et al., 2018; Lee et al., 2019a; Allen-Zhu et al., 2019; Du et al., 2019a; Zou et al., 2018). Besides, NTK has been applied to various architectures and brought a wealth of results, such as orthogonal initialization (Huang et al., 2021), convolutions (Arora et al., 2019), SVM (Chen et al., 2021), attention (Hron et al., 2020). As for graph networks, GNTK helps us understand how GNNs learn class of smooth functions on graphs (Du et al., 2019b) and how they extrapolate differently from multi-layer perceptron (Xu et al., 2020).
Deep Graph Neural Networks. Since deep GNNs suffer from the over-smoothing problem, large and growing body of literature has made efforts in deepening GNNs. There is a line methods that resort residual connection to retain their feature expressivity in deep layers. Xu et al. (2018) use skip connection along with node representations from different neighborhood ranges to preserve the locality of node representations. Klicpera al. (2019) derive a personalized propagation of
8

---

Published as a conference paper at ICLR 2022
Table I: Comparison results of test accuracy (%) between C-DropEdge, GCN, DropEdge, and DGN.
Datasets
Methods
4-layer
8-layer
16-layer
32-layer
GCN
79.8 +: 1.1
73.2 + 2.7
36.3 1 13.8
20.1 2.4
DropEdge
82.2 0.7
82.0 0.9
82.2
82.1 =
Cora
DGN
$2.0
80.2
1.0
73.0
C-DropEdge
82.5 + 0.7
82.3 + 0.6
82.4 0.8
82.6 = 0.9
GCN
61.2 7.1 1.0
50.2 5.7
21.7 = 3.0
DropEdge
70.7 1.0
70.2 0.8
Citeseer
DGN
0.9
62.9 66.5
63.2 0.9
C-DropEdge
7.6
0.9
7..0
70.7
GCN
87.2+844 0.7
36.3
Dropedge
1.
1.3
1.3
77.2=
Pubmed
DGN
1.0
1.2
77.2
77.0=111
C-DropEdge
7..
77.9 1.0
77.2
77.8 1 1.0
GCN
0.9
8.2
6.2
28.8 9.4
Dropedge
0.8
9.7
9.5
91.3 0.8
Physics
DGN
9.0
0.74
8.6
83.2
C-DropEdge
91.9
91.7 1: 0.6
9..0
91.6 0.6
Table 2: Comparison results of test accuracy at various edge preserving rates. Critical preserving percentage for each dataset is marked in bold. The three best results per model are shaded in blue.
Cora
Citeseer
Pubmed
Percentage
GCN-8
JKNet-4
Percentuge
GCN-4
IncepGCN-4
Percentage
JKNet-16
IncepGCNN322
0.05
58.2 +: 19.6
62.0 1:00::00 0.6
0.15
68.5 = 1.2
70.1 0.7
0.01
76.1 + 1.8
75.5 +: 1.9
69.6 14.
82.1
68.8 =
70.6 0.9
0.05
76.2 + 1.5
76.1 1.3
69.7 +: 12.5
82.2 0.6
0.25
68.7 0.8
70.5 +: 0.9
0.10
76.0 +: 1.4
76.8 + 1.3
0,20
75.1 1.0
62.5 0.7
0,30
68.9 0.8
70.5 0.9
0.15
76.9 + 0.9
77.0 1.4
0.25
77.3 2.5
82.5 1:55+:000 0.7
0.35
69.0
70.8 + 0.6
0.22
76.9 + 0.9
77.8 + 0.9
77.2
62.2
0.40
68.9 0.9
70.5 +: 0.4
0.25
76.9 + 1.1
75.8 + 2.5
0.35
2.8
0.
0.45
68.4 = 1.7
70.1 0.7
0.30
76.8 + 1.1
77.1 1.2
0.40
71.9 5.7
0.6
0.50
68.1 0.9
70.2 - 0.8
0.35
76.4 # 1.2
77.6 1.3
0.45
75.5
8..7
0.55
68.0
70.3 1: 0.7
0.40
76.3 1.3
77.6 1.1
neural predictions (PPNP) based on personalized Pagerank. Other similar works using residual connection can also be seen in (Li et al., 2019; Gong et al., 2020; Chen et al., 2020; Liu et al., 2020). Another line of approaches tackle the issue via regularization mechanisms, such as node/edge dropping (Hou et al., 2019; Rong al., 2019), batch normalization (Dwivedi al., 2020), pair normalization (Zhao & Akoglu, 2020), and group normalization (Zhou et al., 2020). Recently, series of latest works (Loukas, 2020: Zeng et al., 2020; Liet al., 2020; Cong et al., 2021; Huang al., 2020) explore the underlying reasons for performance degradation towards mitigation solutions.
CONCLUSION AND DISCUSSION
In this work, have characterized the asymptotic behavior of GNTK measure the trainability of wide GCNs in the large depth. We prove that the trainability drops at an exponential rate due to the aggregation operation. Furthermore, techniques help deepen GCNs. We demonstrate that these
apply our theoretical framework investigate to
what extent residual connection-basee techniques can merely slow down the decay rate, but are unable to solve the exponential decay problem in essence. To overcome the trainability loss problem, we further propose Critical DropE- dge illuminated by our theoretical framework. The experimental results confirm that our method can mitigate the trainability problem of deep GCNs. Future research directions include designing critical node-centric method so to make better use of node information.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
This work was partially supported by a Collaborative Research Project grant between The University of Sydney and Data61, Australia. We thank the anonymous reviewers for useful suggestions to improve the paper. We also thank Ye Su for helpful discussions. This work was also in collaboration with Digital Research Centre Denmark DIREC, supported by Innovation Fund Denmark.
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over- parameterization. In International Conference Machine Learning, pp. 242-252. PMLR, 2019.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ Salakhutdinov, and Ruosong Wang. On exact computation with infinitely wide neural net. In Advances in Neural Information Processing Systems, pp. 8141-8150, 2019.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph con- volutional networks. In International Conference on Machine Learning, pp. 1725-1735. PMLR, 2020.
Yilan Chen, Wei Huang, Lam Nguyen, and Tsui-Wei Weng. On the equivalence between neural network and support vector machine. Advances in Neural Information Processing Systems, 34, 2021.
Fan Chung and Mary Radcliffe. On the spectra of general random graphs. The electronic journal of combinatorics, pp. P215-P215, 2011.
Weilin Cong, Morteza Ramezani, and Mehrdad Mahdavi. On provable benefits of depth in training graph convolutional networks. Advances in Neural Information Processing Systems, 34, 2021.
Alexander G. de Matthews, Jiri Hron, Mark Rowland, Richard E. Turner, and Zoubin Ghahra- mani. Gaussian process behaviour in wide deep neural networks. In International Conference on Learning Representations, 2018.
Xue Ding and Tiefeng Jiang. Spectral distributions of adjacency and laplacian matrices of random graphs. The annals of applied probability, pp. 2086-2117, 2010.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International conference machine learning, pp. 1675- 1685. PMLR, 2019a.
Simon S Du, Kangcheng Hou, Russ R Salakhutdinov, Barnabas Poczos, Ruosong Wang, and Keyulu Xu. Graph neural tangent kerne:: Fusing graph neural networks with graph kernels. In Advances in Neural Information Processing Systems, pp. 5723-5733 2019b.
Vijay Prakash Dwivedi, Chaitanya Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint arXiv:2003.00982 2020.
Paul Erdös and Alfréd Rényi. On the strength of connectedness of random graph. Acta Mathemat- ica Hungarica, 12(1):261-267 1961.
Paul Erdös and Alfréd Rényi. On the evolution of random graphs In The structure and dynamics of networks, pp. 38-82. Princeton University Press, 2011.
Ari Freedman. Convergence theorem for finite markov chains. Proc. REU, 2017.
Shunwang Gong, Mehdi Bahri, Michael M Bronstein, and Stefanos Zafeiriou. Geometrically prin- cipled connections in graph neural networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 11415-11424, 2020.
Ingo Gühring, Mones Raslan, and Gitta Kutyniok. Expressivity of deep neural networks. arXiv preprint arXiv:2007.04759 2020.
10

---

Published as a conference paper at ICLR 2022
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. In Advances neural information processing systems, pp. 1024-1034, 2017.
Soufiane Hayou, Arnaud Doucet, and Judith Rousseau. On the impact of the activation function on deep neural networks training. In International conference machine learning, pp. PMLR, 2019a.
Soufiane Hayou, Arnaud Doucet, and Judith Rousseau. Mean-field behaviour of neural tangent kernel for deep neural networks. arXiv preprint arXiv:/905. /ttp//995...5... 13654, 2019b.
Yifan Hou, Jian Zhang, James Cheng, Kaili Ma, Richard TB Ma. Hongzhi Chen, and Ming-Chang Yang. Mcasuring and improving the use of graph information in graph neural networks. In International Conference Learning Representations, 2019.
Jiri Hron, Yasaman Bahri, Jascha Sohl-Dickstein, and Roman Novak. Infinite attention: Nugp and ntk for deep attention networks. In International Conference on Machine Learning, pp. 4376- 4386. PMLR, 2020.
Wei Huang, Pengcheng Hou, Junfeng Wang, Robert M Ziff, and Youjin Deng. Critical percolation clusters in seven dimensions and on a complete graph. Physical Review E, 97(2)0022177, 2018.
Wei Huang. Weitao Du, and Richard Yi Da Xu. On the neural tangent kernel of deep networks with orthogonal initialization. In Proceedings of the Thirtieth International Joint Conference Artificial Intelligence, IJCAI-21, pp. 2577-2583, 2021.
Wenbing Huang, Yu Rong, Tingyang Xu, Fuchun Sun, and Junzhou Huang. Tackling over- smoothing for general graph convolutional networks. arXiv preprint arXiv:2108.09866 2020.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kemnl:: Convergence and gen- eralization in neural networks. Advances in neural information processing systems, pp. 8571- 8580, 2018
Dongkwan Kim and Alice Oh. How find your friendly neighborhood: Graph attention design with self-supervision. In International Conference on Learning Representations, 2020.
Thomas N Kipf and Max Welling. Variational graph auto-encoders. NIPS Workshop on Bayesian
Deep Learning, 2016.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net-
works. In International Conference on Learning Representations (ICLR), 2017.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In International Conference Learning Representations, 2019.
Jachoon Lee, Jascha Sohl-dickstein, Jeffrey Pennington, Roman Novak, Sam Schoenholz, and Yasaman Bahri. Deep neural networks gaussian processes. In International Conference Learning Representations, 2018.
Jachoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve linear models under gradient descent. In Advances in newral information processing systems, 2019a
Junhyun Lee, Inyeop Lee, and Jaewoo Kang. Self-attention graph pooling. In International confer- ence on machine learning, pp. 3734-3743. PMLR, 2019b.
Guohao Li, Matthias Muller, Ali Thabet, and Bernard Ghanem. Deepgens: Can GCNs go as deep as CNNs? In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp- 9267-9276. 2019.
Guohao Li, Chenxin Xiong, Ali Thabet, and Beraard Ghanem. Deepergen: All you need to train deeper gens. arXiv preprint arXiv:2006.07739, 2020.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Shirly-Second AAAI conference artificial intelligence, 2018.

---

Published as a conference paper at ICLR 2022
Meng Liu, Hongyang Gao, and Shuiwang Ji. Towards deeper graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, pp- 338-348, 2020.
Andreas Loukas. What graph neural networks cannot learn: depth vs width. In International Con- ference on Learning Representations, 2020.
Radford M Neal. Priors for infinite networks. In Bayesian Learning for Neural Networks, pp. 29-53. Springer, 1996.
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In International Conference on Learning Representations, 2020.
Ben Poole, Subhaneil Lahiri, Maithra Raghu, Jascha Sohl-Dickstein, and Surya Ganguli. Exponen- tial expressivity in deep neural networks through transient chaos. In Advances in neural informa- tion processing systems, pp. 3360-3368, 2016.
Yu Rong. Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks node classification. In International Conference Learning Repre- sentations, 2019.
Jeffrey S Rosenthal. Convergence rates for markov chains. Siam Review, 37(3):387-405, 1995.
Samuel S Schoenholz, Justin Gilmer, Surya Ganguli, and Jascha Sohl-Dickstein. Graph neural networks exponentially lose expressive power for node classification.. In International Conference Learning Representations, 2017.
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint 1rXivv1811.00:: 2018.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
Lechao Xiao, Jeffrey Pennington, and Samuel Schoenholz. Disentangling trainability and general- ization deep neural networks. In International Conference on Machine Learning, pp. 10462- 10472. PMLR, 2020.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International Conference on Machine Learning, pp. 5453-5462. PMLR, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? International Conference on Learning Representations, 2019.
Keyulu Xu, Jingling Li, Mozhi Zhang, Simon S Du, Ken-ichi Kawarabayashi, and Stefanie Jegelka. How neural networks extrapolate: From feedforward to graph neural networks. arXiv preprint arXiv:2009.1 11848, 2020.
Hao Yuan and S. Ji. Structpool: Structured graph pooling via conditional random fields. In ICLR, 2020.
Hanqing Zeng, Muhan Zhang, Yinglong Xia, Ajitesh Srivastava, Rajgopal Kannan, Viktor Prasanna, Long Jin, Andrey Malevich, and Ren Chen. Deep graph neural networks with shallow subgraph samplers. ICLR, 2020.
Lingxiao Zhao and Leman Akoglu. Pairnorm: Tackling oversmoothing in gnns. In International Conference on Learning Representations, 2020.
Kaixiong Zhou, Xiao Huang, Yuening Li. Daochen Zha. Rui Chen, and Xia Hu. Towards deeper graph neural networks with differentiable group normalization. In Advances in neural information processing systems, 2020.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes wwrr-parameterized deep relu networks. arxiv e-prints, art. arXiv preprint arXiv: 1088888, 2018.
12

---

Published as a conference paper at ICLR 2022
A APPENDIX: A GENERAL GCN ARCHITECTURE
GCNs iteratively update node features through aggregating and transforming the representation of their neighbors. Figure 3 illustrates overview of information propagation in general GCN considered this work.
Propagation Unit
Propagation Unit
A Agregatiion
MLP
Aggregation
1=0
Figure 3: Overview of the information propagation in a general GCN.
B APPENDIX: PROOFS FOR THEOREM
B.1 CONVERGENCE OF AGGREGATION GNTK
In Theorem we demonstrate that matrix A(G)) is transition matrix, we first prove this proposition. To this end, we block the non-linear transformation by setting R 0. Then, the propagation of GNTK can be expressed as,
Σ
@ (0-2)
(14)
(V(x) + W(w))+ +1
(uN(u) o' "EN((')
In order to facilitate the calculation, we rewrite Equation (14) as the following format,
(o A(G))V-)(())
(15)
where (G) E ggnxt x1 is the result of being vectorized, and matrix A(G) E xx" a square matrix. We show the key result that A(G) is probability transition matrix, and the limiting behavior of ((I) in the following lemma, Lemma (Convergence of aggregation). Assume R = 0, then lim O00 (u, u') = =
where π (G) E Raax1 satisfying ((G) #G))
Proof.
When R = 0, Equation (14) reduces to.
1 (u, u') [N(')) +1 W(r)+1
Σ Σ
@ @1-1( (v,0')
(u)( ("""(")))u
In order to facilitate calculation, we rewrite the above equation in the format of matrix,
( 4 (G)6V-1))
where (G) E R x1, is the result of being vectorized. Thus, the matrix operation ( e Rnn xn? is obvious that, 1 (1-1) -.. (")
(G)
This implies that the aggregation operation the same for each layer. The next step is to prove A(G) is stochastic matrix (transition matrix);
A(G) 1
13

---

Published as a conference paper at ICLR 2022
According to Equation (14), A(G) can be expressed as Kronecker product of two matrices,
A(G) [BG])((G) @ [BG))((G)
where B(G),C(G) Roxa, We then analyse the two matrices separately:
(1) B(G) is a diagonal matrix, which corresponds to the factor N(a)+I
(ut)i
B
H +1
(2) The element of matrix C(G) is determined by whether there exists edge between vertices,
C(G) 6Gg
where 6.j = 1 if i = j or there is an edge between vertex i and j. otherwise dig 0. We then use the property of matrix B and before Kronecker product,
Σ [B(])C())) ((.))
1
Σ 81 N(uu) + (N(u,) + +1)
According to the definition of Kronecker product, we have,
( = [[C()
where i = a (c 1)n, and j ++ (d 1)n.
So far, we have proved that A(G) a stochastic matrix. According the Perron-Frooenius Theory, a stationary probability vector #(G) E R=nx1
x1 is defined as a distribution, which does not change under application of the transition matrix; that is, is defined as probability distribution, which is also an eigenvector of the probability matrix, associated with eigenvalue 1:
A(G)F(() #(G)
Note that the spectral radius of every stochastic matrix is most by Gershgorin circle theorem. Thus, the convergence rate is governed by the second largest eigenvalue.
Since limy A (G) 7. (G), we have,
= lim (G) = lim (C) 1
1+000
T
#(G)T
where IIG)
is the n² n² matrix all of whose rows are the stationary distribu-
GG)
tion. Then, we can see that every element in 60 (G) converges exponentially to an identical value, depending the stationary distribution and initial state,
lim (00) (u, =0C))
Remark 1. This lemma can extended to the multi- malti--raaph setting, where matrix A(G, G') Ran'' Xnnn with respect to a pair of graphs G, G is a transition matrix as well, and is the number of vertices in graph G'
14

---

Published as a conference paper at ICLR 2022
B.2 CONVERGENCE OF MLP GPK
Before we prove Theorem 1, we introduce the result for the Gaussian Process kernel 2 (G) of a pure MLP. By doing so, we consider network with only non-linear transformation, known as pure MLP. This leads 2 (u, u') Egy) (u, w'), where
subscript (r) denote the layer index. And we rewrite the propagation function for GPK as follows,
(u, u1) o.E 22. (1.B...)))
(ose)r-)))(((((())))) (0(2))((22) to²
(16)
and the variance E(r) E R2 is.
(u,) Em)(u, (t))(u,,u) (ur)(ul
E())
(17)
The large depth behavior has been well studied in Hayou et al. (2019a), and we introduce the result when the edge of chaos is realized. In particular, we set the value of hyper-parameterss to satisfy,
D2 (' 2V
(18)
where q¹ is the fixed point of diagonal elements in the covariance matrix, and f DD = I dze is the measure for normal distribution. For the ReLU activation, equation (18) V2x
requires o = and of =
The key idea is to study the asymptotic behavior of the normalized correlation defined as,
(u, w') C,,, (E(r)(u, u) (rr) (u',u)
(19)
Lemma 2 (Proposition and 3 in Hayou et al. (2019a)). Assume network without aggregation, ie., I. with a Lipschitz nonlinearity d, then,
<(x) (z)+, 1 -Cr(u, u²) ~
9a² 2n
asT a
2 25 1'(o <(x) tanh(r), 1 Cr(u,, as + oo where B = qgp, (d (vT
Proof. We first decompose the integral calculation in the Equation (16) into two parts, diagonal elements and non-diagonal elements:
[6)(u, u) = =0 I @²( (1r-1)(1, + +o
Dz
Eu,)(u, u') 22 I
Dz, )(u1)((u2) o
where "1 11(r-1((u, 2)z1. and U2
VE(r-ny(u',u))
C,-1(u, w()) +
VI C- with Cr-1(u, = (u,))) EEr- u
For simplicity, define (u) (ur u). (u') Egr) (u', w'). We then proceed with the proof by dividing the activation (xx:) into two classes, namely, ReLU and Tanh.
ReLU activation, o(x) = m0. The recursive equation (16) for (u) reduces to,
02 (u) - ( + of
2
The edge of chaos condition 2 D ( 2)}2 2)²² activation, which leads to,
requires oZ and of for ReLU
lim (u) = (u(u) = (1))
2-000
15

---

Published as a conference paper at ICLR 2022
Then the second integration for (u, u') becomes. JDa Cr(,,')) o Dzg -(
v1
to
9r-1(u)
To investigate the propagation of (1,, we set set (u) = gr (r("() = 4, and define,
f(z) T De, of (( + v1 x²22)) oz
Let [0, 1], the derivative of f(x satisfies,
f((x) 2 /
12, 21
D2,
This can be seen from simple derivation,
f(()= = /
(z))o((zz + v1 - 2212) 21-22222 D.1 D.2
V1 - x² (2)
=So, S. ((z1)o (zz) + v1 VI- xzz1)()) [ / ((21)o(<zz) VI -I- x²22) v1=222))(
D.,
D., D.,
vI
Using an identity for Gaussian integration Jp, =g(2) So, {(2) yields,
- x222) o(21)0" v1 x222)] f((x) Jo,, / [d((z)d((z2) + v1 x2)2) ((2)))"(x=) v1-
= =Jo, / ('(z)o + v1 -1-x²z2
D. D.2
Then the second derivative of f(x) becomes, f"(x) ~VI-2²- So using the equation above and the condition (0) 1. obtain another form of the derivative of f(x),
1 f((x) arcsin (x) +
1
Because f arcsinn = x arcsin + +VI x and f(1) = 1, then for x E [0, 1].
f(x) 2x arcsin(x) 221 x2 + 2m
2x
Substituting f(x) C2 (u, u') and Cy-1 (u, ut) into expression above here, we have,
Cr(u, w') 2Cr-1 (u, u') arcsin u')) + 2 C7, + C,- C,-1(u, u()
2x
Now we study the behavior of C,(u, u²) as r tends to infinity. Using Taylor expansion, we have,
2v (1 11-1)3/2 0((1- 2)3/2)
f(r))_-1- =
3π
By induction analysis, the sequence C, u') increases the fixed point 1. Besides, replace I with C,,,,,),
2 (1 Cr( - C,(u, u') +
Let 7r = Crl then have,
2v 3/2 + 0(25/2)
7r+ 9r
7r
3π
16

---

Published as a conference paper at ICLR 2022
so that.
2 3π
v2
112 7,41 1/2
///2 0(12/11)-1/22 -
0(+)
3x
As tends to infinity, have,
V2
-1 1/2 7r41 - -9g
11/2 1/2
3π
means,
V22
1/2
74
r
3x
Therefore, we have,
9 ?
1 C-,,
2r
Tanh activation, (xx) = tanh(z). For the argument of fixed point, we ask readers to refer to Hayou et al. (2019a). Here, only discuss the convergence rate of GPK, which means we directly assume that f(x) tends to as the depth tends to infinity lim Cu(u, u') 1. For the function f(x), a Taylor expansion near yields,
f(z) = 1 (1f (x - 11) f1( + 1(1x0(1()))) 1)5/2)
where (1(1) ou So, (V=22)) and (1) ob Jo_ 10" (V/g2)) then we have,
Denote 1 (r,
+ + 3/3
M+1 = B
25p 10' [+) sJo, 1 [) Therefore,
where B
N5+1 = 7r (1
4r
+0 = = + 8
+ 02)2/2).
B
Thus, have,
3 as r x
(m)
Lemma 2 shows that the covariance matrix converges to a constant matrix at polynomial rate of 1/r2 for ReLU and of 1/r for tanh activation the edge of chaos. This implies that network without aggregation could retain its expressivity at a large depth. However, for general cases, due aggregation, the rate of convergence would change from polynomial exponential. This would cause the trainability of deep GNNs to be problematic, as shown in the following section.
B.3 CONVERGENCE OF GPK FOR GCNs
Then we formally characterize the convergence Gaussian Process kernel I(2 (u, u') of a GCN in the infinite-wii wiitt limit:
Lemma 3. If A(G) is ireducible and aperiodic, with a stationary distribution vector H(G), then there exist constants 0 < 1 and C > O, and constant vector T IR=² depending the number of MLP iterations R, such that
12 (u,) #(G) < Ca'
Proof. We prove the result via an induction method. For = 0, according to the Cauchy- Srr.kkowwkk--shwaarr Inequality
(u, 2i) (1) < 12114 10
17

---

Published as a conference paper at ICLR 2022
Thus, there is constant C, depending C(V,E), and the number of MLP operations R, over feature initialization, such that,
1 (u, u') - =[G)" <C
(0 Assume the result is valid for (r) (u, u'), then we have,
(2) (u, (oo))=((G"aa Coa
where Co a constant satisfying 0 < Co < C. Now we consider the distance between ((++1) (u, x')
and Ca'-1, To compute this, we need to divide the propagation from layer to ++1 layer into three steps:
1. (())
7 (!))
.... (1
(r) (r+1)
2. ()) ((+1)
(8) (0)
3. D(+1)
x(--1)
1(41)
(0) (1)
It is not hard find that steps and correspond non-linear transformation while step 2 corre- sponds to aggregation operation, we then characterize them one by one,
MLP Propagation The assumption
(u wd) T S Coaa implicitly implies that
Vill 1(1 (u,,²)
Cr, w') is close to one. Because Cr(u, w²)
then,
(a.a) x:1y (wr,r))
TGaa #(G)TT+ Coa S SC,(u,u) # - Coa
#(G)T+ Coaa
Because Coaa < 7 we have C,(u, u') = 1+')aa)). Recall the property of MLP propagation function f(x) for Cu, u'), when C, (u, tl') close to 1:
2 (1 1///2222222 0(11 2))/2)
f(r)l=-1- =
3π
This implies,
2/2 (1 -
(C(+t)(uu,))) (u, u')
3x
With this result, we can further obtain,
D ((tt)(,, -[ 10 (ott) (u, E00
(u, u')
s (1 < u') (u, + 15 (u, H(G)*
(u, u') - c (w, u')l 2 (u, u) (u' (w', w²) + 1500 -
= =Ciaf' + Coa' < (Co + Ci)aa.
where C1 is positive constant. Repeat the proof process, we have relation for (1) last step of 1,
(1t) (u, u/) the
1000 (u, [
+ (B-)
(20)
18

---

Published as a conference paper at ICLR 2022
Aggregation Propagation We go through aggregation operation A(G). In this case, use matrix form, and take equation (20) into aggregation function, yielding the result as follows,
-0 (G)
(G) = A(G) + Ō(d'))
where Ō(a') E RBnx1 denotes a vector which every element is bounded by a'.
According to Theorem 4.9 in Freedman (2017), we have (') [T(G) as a xo. When / is finite, the error is of exponential decay. Here, we use < < to denote the corresponding base number. Therefore,
1 100 (u, - S (Co + (R (R- r))a-
Finally, by repeating the result in step 1, we have,
1 ESS (m, (u, v/) #(G)" (Co+ RCi)atth= Ca
Remark 2. In the proof, there is a RC1 term in each propagation of - - + 1, which may lead explosion when I tends infinity. Basically, this problem be solved by a careful analysis, because the constant C₁ is associated with O(a which has smaller order compared O
B.4 CONVERGENCE OF GNTK
Finally, we arrive at our main theorem:
Theorem (Convergence rate of GNTK), If transition matrix A(G) &R"2xn" irreducible and aperiodic, with stationary distribution vector #(G) E R²"x x1, where 5(h (G) (
and () (G) Ra x1 is the result of being vectorized. Then there exist constants 0 and
C' 0, and constant vectors U. gaaxt x1 depending on the number of MLP iterations R, such
that e (1) ( (u, #(G)" RIÚ + 1') Ca'.
Proof. This proof has the same strategy that of Lemma 3. The first step is to understand Equation (9) in the large-depth limit.
(u, u') + (u, w') (u.') 1 - uf w')it())
According to the result of Lemma 3, we have already known.
(u, #(G)
To proceed the proof, we need to work out the behavior of 5:(0) [() (u, u') in the large depth.
ReLU activation, ((x) = maxx(0,z) Recall that we define Cr+1 = ((C,), and we have,
1
f((x) = arcsin(x) (x) + 2
Then, at the edge of chaos,
(u, = (((C(u,,))) 1
aresin(C,(u,
=1- C,(u, 11
19

---

Published as a conference paper at ICLR 2022
Tanh activation, ((x) tanh(2). We have
-1- -19)
At the edge of chaos,
(u, u²) 1+ O(a')
Now we prove the result via an induction method. For = 0, we directly have,
e (u. u') 20 u, n') Σ || |22l ll2 =1
Thus there is constant C, depending G(V, F.), and the number of MLP operations R, over feature initialization,
1 10 (u, u') HGG)T
Assume the result is valid for +
(8) (r) (u, w') then we have,
(r) (u, v - #(G)" (IIT e)) S Ca
Now we consider the distance between 6 04+11/ (u, u²) and ((G)² (R((+))++))) To prove this, we need to divide the propagation from / layer to - layer into three steps:
(r)
1. ( (1) (r) (r+1)
θ (1) (1)
2. (0)
(R) + θ (1+1)
3. ((41)) e (1+1)
(
(1)
For step 1, we have,
(0(0) (rtn)(u, - -
(2(0) (rtt))(u, u') + 500 (1tt)) (u. -()
(G)) 8(1 O(a')) (1 O 1 (2. ((C) 1) s Ca'
Repeat the process, we have relation for + (1) (R) (u, v') at the last transformation in step 1,
10 (R) (u. u') - ((G) ((IR + R r) + T¹) S Ca'
Secondly, we go through an aggregation operation. Because is a Markov chain step, we have, b (1+1) (u, #G)) ((RI R r) き')l s C1
Repeat the result in step 1, we finally have,
1 10 (001)) (u, w') - [ +))+
=10 (1 (u, -D(G- 1) Ca 1+1
C TRAINABILITY OF ULTRA-WIDE GCNS
Corollary 1 (Trainability of ultra-wide GCNs). Consider GCN of the form (6) and (7), with depth I, number of non-lineat transformations r, an MSE loss, and a Lipchitz activation, trained with gradient descent a node classification task. Then, the output function follows, f((X)
- (y (I-X))(Iee (G)r), where X and Y are node features and labels from training Y)) set. Then, @ (7) (G) is singular when + co. Moreover, there exists a constant C. > O such that for all t > 0, (X) Y| C.
20

---

Published as a conference paper at ICLR 2022
Proof. According the result from Jacot et al. (2018), GNTK (G) converges deterministic kernel and remains constant during gradient descent the anfinite-width limit. We omit the proof procedure for this result, since it is now a standard conclusion in the NTK study.
Based on the conclusion above, Lee et (2019a) proved that the infinitely -iide neural network is equivalent to its linearized mode,
)! = fo( Vofo(X))o=a, 0=0
where wi - 0: Oo. We call it linearized model because only zero and first order term of Taylor expansion are kept. Since we know the dynamics of gradient flow using this linearized function are governed by,
Wy Vofo(X (x)
(X) = -n (G)V (x)(
where L is an MSE loss, then the above equations have closed form solutions
(x)
(2) fo(X) (I (1 (C))) (G
Since Lee Lee et (2019a) showed that (X) f((X) in the infinite width limit, thus we have,
(X)= = -
( (o) fo(X) + (I - ( 1
(21)
In Theorem 1, we have shown e ( (G) converges to constant matrix an exponential rate, thus being singular in the large depth limit. According to Equation (21), we know that,
(e) @ (G) (C) (Fo(X)- Y lx - Yl = lle -
Let ( be the GNTK in the large depth limit, 6 ( Q" DQ be the decomposition of the GNTK, where Q is an orthogonal matrix and diagonal matrix. Because e ( D has at least one zero value d, = 0, then
(r) (G) singular,
[lfa(X) - - 11Q (f(X) - YIQII 2 - -
-
Remark 3. In the proof assume the loss is MSE. Nevertheless, the conclusion regarding train- ability can be applied to other common losses such as cross-entropy. For cross-entropy loss, even though cannot derive an analytical expression for the solution, we can prove that the GNTK still governs the trainability and the law of GNTK is not affected by the loss. Thus, the results for trainability still hold in the cross-entropy case.
D CONVERGENCE OF RESIDUAL GNTK
D.1 RESIDUAL CONNECTION AGGREGATION
Theorem 2 (Convergence rate of residual connection in aggregation). Consider GNTK of non- linear transformation (9) and residual connection (12). Then with a stationary vector #(G) for Á(G),, there exist constants 0 < â < 1 and C 0, and constant vectors it and of depending on (r) (u, u') - GG) (RI + T') Cā¹. Furthermore, we denote the second largest eigenvalue of A(G) and A(G) as X2 and '2 respectively. Then, da )2
R, such that (!)
Proof. According to the aggregation function for covariance matrix, we have
T (G) (1 (C) = (11--)444 -11-0)4+0))0
21

---

Published as a conference paper at ICLR 2022
The new aggregation matrix A(G) is stochastic transition matrix as well, which can be from, AG))) = (1 -1- -) ((G) + Iyy=1 11
Then we compare the second largest eigenvalue between two transition matrices. Suppose the eigen- values of the original matrix A(G) are {λı X2 >...> )₂²). We already know that the maximum eigenvalue is \ = 1, and the converge rate is governed by the second largest eigenvalue X2- Now we consider the second largest eigenvalue 2 of matrix A:
d2 = 0)A2 + x2 + 8(1 A2) > A2
Remark 4. The theorem above gives certain conclusion about the relationship between X2 and X2. Here, we discuss more about the relationship between and ā. According (Rosenthal, 1995), the relationship between convergence rate a and the second largest eigenvalue X2 of transition matrix A(G) can be expressed as,
10 (u, - F(G)) +0) S CC <Ca'
where a > X2, and >> 1 is the size of the largest Jordan block of A()). From the above inequality, conclude that the second largest eigenvalue almost governs the convergence rate. However, maintain rigor, we cannot directly obtain < â. Instead, from the result that x2 X2, say that & is roughly larger than a.
D.2 RESIDUAL CONNECTION IN MLP
Theorem (Convergence rate of GNTK with residual connection between transformations), Con- sider a GNTK of the form (8) and (12). If A(G) is irreducible and aperiodic, with stationary distribution x (G), then there exist constants 0 < a < 1 and C >> 0. and constant vectors and v Co..
depending on R, such that, (0)) (7) (u, v') (G)T (Rl(1 + +
Proof. For residual connection in MLP, we have,
o2 4 ( (1+ - 1r - (u)
gr (u) 9r- (u) +
Since o > O, (u) grows at an exponential rate.
Now, we turn to compute the correlation term Cr 2'). For convenience, we suppose q-(u) (u)'.. Then.
Cr+ilu, Er+1(u,
1
[,(,
o2
f(C,(u,
(u+1(u) 1 1
a²
(r(
1
= 2
2
2
a²
1+ o4 C, u²) +
(C,,uu,
1
1
o
2
Using Taylor expansion of near 1, as have been done in the proof of Lemma 2,
2v
f(z))=-1- = 3π
(1 x3/ +0(1- (1[1--2)) 2)3/2)
we have,
2v2 a
ur+ = Cr(u, v1)
- (((0))))/000000001110000 ( (((,,)))))
3m
1
+
2
22

---

Published as a conference paper at ICLR 2022
Note that it is similar to the case of MLP without residual connection:
2v2
Cr+i(u, u() =
[(1 + (()()))))))))
3m
Following the proof diagram in Lemma 3 and Theorem 1, we can obtain the behavior of (:( and ( (u, u') in the large depth limit,
(r) (u, n²)
3 (u, u') - (
tee ) Rl s
CCa
2
Lh "
1 (1, - -#(G)= - ( +
S Caa
2
E APPENDIX: DISCUSSION ON THE TRAINABILITY OF GNTK WITH CRTICAL DROPEDGE
According to the critical percolation theory, there exists a large connected component of order O(n) (Erdös & Rényi, 1961; Erdös Rényi, 201 1), where n is the number of nodes in a graph. This implies that there exists a (connected) graph of size (n)) when we use the critical dropping rate. To preserve information, edges would be resampled at every iteration. This implies that at each iteration during training, the GNN takes a random and large graph. For the whole training process, we can think that we have used all the information conveyed by the graph.
It would be interesting to consider deriving some theoretical results for the limiting behavior of the GNTK in the large depth with Critical DropEdge. Since Critical DropEdge is originated from the random graph theory, promising approach is to analyze spectral distributions of adjacency matrix and Laplacian matrix with a random graph model, like existing studies (Ding & Jiang, 2010; Chung & Radcliffe, 2011).
F APPENDIX: DATASETS AND IMPLEMENTATION DETAILS
F.1 DATASETS
For node classification tasks, Cora, Citeseer and Pubmed (Kipf & Welling, 2017)) are three com- monly used citation networks, and Physics (Shchur et al., 2018) co-author network. Detailed information of the four benchmark datasets is listed as follows and summarized in Table 3.
The Cora dataset consists of 2,708 scientific publications classified into one of seven classes, and 5,429 links. Each publication is described by a 0/1-valued word vector indi- cating the absence/presence of the corresponding word from the dictionary. The dictionary consists of 1,433 unique words.
The Citeseer dataset consists of 3,312 scientific publications classified into one of six classes, and 4,732 links. Each publication is described by 0/1-valued word vector indi- cating the absence/presence of the corresponding word from the dictionary. The dictionary consists of 3,703 unique words.
The Pubmed Diabetes dataset consists of 19,717 scientific publications from PubMed database pertaining to diabetes classified into one of three classes. The citation network consists of 44,338 links. Each publication is described by a TF-IDF weighted word vector from a dictionary comprised of 500 unique words.
The Physics dataset consists of 34,493 authors as nodes, and edges indicate whether two authors have co-authored a paper. Node features paper keywords from the author's papers. Following Kim & Oh (2020), we reduce the original dimension (6,805 and 8,415) to 500 using PCA. The split is the (0--errclass/0-pper--lassr classify each author's 's respective field of study.
The goal of this task is to
23

---

Published as a conference paper at ICLR 2022
Table 3: Details of Datasets
Dataset
Nodes
Edges
Classes
Features
Critical Edge Sampling
Train/ Val/TTstt
Cora
2,708
5,429
7
1,433
24.94%
0.05/0.1 1800.77
Citeseer
3,327
4,732
6
3,703
35.15%
0.04/0. 15/0.30
Pubmed
19,717
44,338
3
500
22.23%
0.003/0.03/0.06
Physics
34,493
247,962
5
500
6.96 %
0.003/0.004/0.99
Table 4: Comparison results of test accuracy (%) with different infinite- wide backbones.
4-layer
8-layer
32-layer
64-layer
Dataset Backbone Orignal C-DropEdge Original C-DropEdge Original C-DropEdge Original C-DropEdge
GCN
79.98
79.98
79.48
80.61
73.75
75.86
72.59
74.03
Cora
JKNet
78.27
77.29
80.26
80.02
78.00
79.01
75.90
76.75
GCN
66.38
66.97
54.42
64.88
50.72
51.22
43.77
46.49
Citeseer
JKNet
67.04
67.67
65.54
66.45
54.57
56.39
46.71
47.96
GCN
74.59
74.77
73,58
76.67
71.63
74.77
66.28
71.72
Pubmed
JKNet
75.30
74.35
76.42
77.17
75.71
76.68
74.81
75.74
F.2 EXPERIMENTAL IMPLEMENTATION
We use the Py Torch implementation to simulate both infinitely-wide and finitely-wide GCNs:
The infinitely-wide GCNs use part of code from Du et al. (2019b), which originally adopted for graph classification. We redesign the calculation method of GNTK (Du et al., 2019b)² according to the formula in Section 3.1 and use it to process node classification tasks.
For finitely-wide GNNs with DropEdge (Rong et al., 2019)3, use the code from (Rong et al., 2019), we perform random syper-parameter search for each model, and report the case giving the best accuracy validation set of each benchmark, following the same strategy as Rong et al. (2019). The difference that, in each experiment, we fix the edge sampling percentage
[V] which listed in the last column of Table 3.
2|l
All codes mentioned above use the MIT license. All experiments are conducted on two Nvidia Quadro RTX 6000 GPUs.
G APPENDIX: ADDITIONAL EXPERIMENTS AND DISCUSSION
G.1 INFINITELYWIDEE BACKBONES
In the main paper, we reported the performance of GCNs with finite-width, here we show more results with respect infinitel-wwide GCNs. shown Table We apply Critical DropEdge to infinitely-wide backbones on emiisuuprrisee node classification. We consider two backbones, which are GCN (Kipf & Welling, 2017) and JKNet (Xu et al., 2018), and the edge preserving per- centage P(G) is shown in Table 3. First, we calculate GNTK with respect to the graph data and GNN, Then, we apply kernel regression with calculated GNTK to complete node classification task.
Table 4 summaries the performance three citation networks. In this table, we report the perfor- mance of GCNs with 4/8/32/64 layers. is shown that, most cases, using Critical DropEdge (C-DropEdge) can achieve better results than original GNNs in the infinitely-wei wide case, especially when the model is deep.
We use the implementation of GNTK available at https: /g/ thub. ctt http://gtht....ooooo/ggggg/////a We use the DropFageimmlemmenttion available at https:://////.. //gi thub. com wwwpthwww....pp....e.occe http:////.mooooppe//////rddggg
24

---

Published as a conference paper at ICLR 2022
Table 5: Comparison results of test accuracy (%) between C-DropEdge and DropEdge.
Backbone Finite
4-layer DropEdge
8-layer DropEdge
Dataset
Original
C-DropEdge
Original
C-DropEdge
GCN
79.8 + 1.1
80.4 1.4
82.0 + 1.2
73.2 = 2.7 75.1 + 2.4
77.3 - 2,5
Cora
JKNet
81.1 1 1.0
82.2 0.7
82.5 + 0.7
80.9 : 1.2
82.0 0.9
82.1 1 0,5
IncepGCN
80.0 0.9
80.6
82.4 0.5
78.6
81.2 1.3
82.3 0.6
GCN
63.7 3.0
69.0 0.8
5.7
52.8
54.1 = 5.9
Citeseer
JKNet
69.6 1.2
70.2
70.3 +.7
1.0
70.5
70.8 1.2
IncepGCNN
69.4 1.5
1.0
70.8 + 0.6
6.20 70.8
70.9 0.5
GCN
1. 0.74
0.4
8. 5.1
58.9 1:99:00 6,9
Pubmed
JKNet
7.11 0.9
76.1 1.0
76.6
0.9
IncepGCN
1.5 1.7
1.1
1.3 1.2
77.9 + 1.0
GCN
90.2
91.6
91.9 0.7
83.5 2.2
86.3 1 1.8
85.2 2.3
Physics
JKNet
9.76
0.9
91.5
90.4 = 1.5
91.5
91.7 = 0.6
IncepGCN
91.0 1.1
91.4 0.5
91.5 0.3
90.5 = 0.8
91.4 0.8
91.5 0.6
Backbone Finite
16-layer DropEdge
32-layer DropEdge
Dataset
Original
C-DropEdge
Original
C-DropEdge
GCN
36.3 + 13.8
55.1 55.1:5. 5.2
58.5 3.9
20.1 + 2.4 22.1 2.0
24.7 + 1.8
Cora
JKNet
79.9 1.6
82.2 0.7
82.4 1 0.8
80.4 1.4
0.5
82.6 1 0.9
IncepGCN
78.7 1.0
80.2
1.3
82.0 1.00:00 0.8
78.5 1.8
8.8
81.6 0.9
GCN
30.8 2.2
36.6 3.9
21.7
2.01
25.2 0.9
Citeseer
JKNet
69.2 1.2
68.8 1.6
69.5 + 1.0
68.1 2.3 69.9
70.1
0.6
IncepGCN
68.4 1.2
70.7
1.0 71.0
68.6 + 1.9 70.2 0.8
70.7
0.9
GCN
39.5
10.3
37.0 9.6
42.6
6.4
36.3 3.84
38.5 6.1
Pubmed
JKNet
76.6 0.9
76.1 + 0.8
76.9
0.9
77.1 + 0.8 77.0 77.0+0.99 0.9
77.2 1.0
IncepGCN
76.5 + 1.5
76.7
77.2 + 1.0
77.0 + 1.4
77.2 1.3
77.8 1.0
GCN
41.6 6.2
45.8 + 6.3
46.2 5.7
28.8 + 9.4 31.1 8.8
36.2
8.4
Physics
JKNet
90.3 1 1.0
91.2 0.5
91.5 + 0.4
90.6 + 1.0 91.3 +13+0.88
91.6 + 0.6
IncepGCN
91.4
92.0
92.0 + 0.4
OOM
OOM
0OM
OOM means Out-Of-Mennt Memoer...
G.2 PERFORMANCE OF USING DIFFERENT BACKBONES
The results presented in Table are the best across different backbones. Table further compares the results of vanilla GNN, DropEdge and C-DropEdge for three different backbones (GCN, JKNet and IncepGCN), From the table we can conclude that Critical DropEdge consistently outperforms DropEdge and vanilla GNNs.
G.3 TRAINABILITY OF GNTK WITH CRITICAL DROPEDGE
We implement deep GCNs with/without DropEdge and C-DropEdge to compare the training per- formance. The results are shown in Figure 4. The training loss of GCN and GCN with DropEdge has a slower convergence rate and converges to a larger error compared to GCN with C-DropEdge. achieve better trainability compared to GCN and GCN with
This indicates that C-DropEdge DropEdge. Besides, the convergence results of GNTKs with C-DropEdge are shown in Figure 5. Compared to residual connection, find that the normalized GNTK elements would not converge to single value, and the convergence rate curve does not depend on the depth. This implies that residual connection mitigates the trainability loss by slowing down the exponential convergence rate, while C-DropEdge directly changes the convergence results.
25

---

Published as a conference paper at ICLR 2022
(a) Cora GCN-8
(b) Citeseer GCN-12
2.0
2.0
NoDrop
DropEdge
1.5
DroppEdde
1.5
Traiting
1.0
1.0
NoDrop
0.5
M
DropEdge
DropEddee
0.0
0.0
100
300
400
100
200
Epochs
Epochs
Figure 4: Training loss as a function epochs. (a) We implement 8-layer GCN, GCN with DropE- dge, GCN with C-DropEdge Cora. (b) 12-layer GCN, GCN with DropEdge, GCN with C- DropEdge on Citeseer. The training loss of GCN and GCN with DropEdge has a slower convergence rate and converges larger error compared to GCN with C-DropEdge.
(a) C-DropEdge GNTK Collapse
(b) C-DropEdge Convergence Rate
1.0
Element Wise Distance of GNTK
10P
0.8
Normalized GNTK
0.6
10-2
0.4
0.2
10-4
e=exp(- exp(-0001 (001110x)
0.0
0
200
400
600
800
200
400
600
800
Depth
Depth
Figure 5: Convergence rate of GNTK with C-DropEdge. (a) Elements of the normalized (residual connection) GNTK as a function of the depth, defined as RI + r. Different elements tend to have different value as depth grows (b) The element-wide distance of the normalized GNTK function of the depth. The converge rate is no longer bounded by an exponential function. Instead, remains parallel to the horizontal depth axis.
26


Reviews:
[{"review_id": "yYY9Ec8uIna", "reviewer": "Reviewer_CDt6", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Strengths\n\n1. The investigation of the trainability of the ultra-wide GCNs via the GNTK view has its novelty for the graph machine learning community and provides new perspective for the over-smoothing problem.\n2. The Proposition 1 provides more information on the power of the DropEdge method and motivates the derivation of C-DropEdge.\n3. Detailed experimental analyses (Fig 1, Table 2) are provided.\n4. Both the Sec 2 and the Sec 6 are well written and provide clear and fruitful preliminary knowledge on this work.\n\n### Weaknesses\n\n1. About the derivation of the C-DropEdge\n\n   (1). The authors make extrapolation from the connected component size to information flow and show the information transforms in the critical random graph at a polynomial rate rather than an exponential rate. It would be better to further analyze the convergence rate of the GNTK in the critical random graph and show that the exponential drop of the trainability is mitigated by the proposed technique.\n\n2. About the experimental results: \n\n   (1). To validate that the C-DropEdge can better mitigate the loss of the trainability of deep GNNs, the training performance should be provided besides Table 1. Moreover, the convergence results of GNTKs with C-DropEdge should also be provided to compare the mitigating effect between residual connection and C-DropEdge.\n\n   (2). Suggestions for the next version of this paper: there can be more baseline methods to verify the C-DropEdge. Different model architectures [1, 2] and normalization mechanisms [3, 4] can be tested to provide more general insight on the effect of the C-DropEdge for the methods in use in the graph ml community.\n\n3. Minor issues:\n\n   (1) In the theorem 2, the readers can only get that the original base $\\alpha$ of the exponential convergence rate term is replaced by a new base $\\tilde\\alpha$ (it is even not defined), and the second largest eigenvalue of the transition matrix under the residual connection setting is larger. It is not straightforward to conclude that the \"slow down\" effect of the residual connection, especially for those who do not have enough theoretical background knowledge.\n\n   (2) The wording \"residual connection-resemble technique\" is perplexing.\n\n[1]. Chen et al, Simple and Deep Graph Convolutional Networks. ICML 2020\n\n[2]. Li et al, Deepergcn: All you need to train deeper gcns. arxiv preprint.\n\n[3]. Zhao et al, Pairnorm: Tackling oversmoothing in gnns. ICLR 2020.\n\n[4]. Zhou et al, Towards Deeper Graph Neural Networks with Differentiable Group Normalization. NeurIPS 2020.", "summary_of_the_paper": "This paper aims at tackling the well-known over-smoothing problem of deep graph neural networks (GNNs) from a theoretical perspective. Specifically, the authors exploit the Graph Neural Tangent Kernel (GNTK) and use it to analyze the trainablility of GNTK in the large depth, which provides insight for the reason of the over-smoothing problem. According to the theoretical analysis, the trainablility of wide and deep GNNs drops exponentially in the optimization process, and the residual connection can only mildly mitigate this problem. Based on the analysis, the authors modify the DropEdge method and propose the Critical DropEdge (C-DropEdge). Both numerical and real experiments are provided to demonstrate the validity of the theoretical analysis and the proposed C-DropEdge.", "summary_of_the_review": "The over-smoothing problem of deep GNNs is a well-known problem in the graph ml community, which impedes the researchers to fully unlock the power of the GNNs due to the limits of the model capacity. The authors try to provide a new perspective via the GNTK view. However, there exists logical gap between the theoretical results and the claims and the derivation of the proposed C-DropEdge algorithms. Detailed experimental results are also necessary to better demonstrate the effect of the proposed method. **Thus, my recommendation for this paper is \"weak rejection\".** If the authors can address the questions in the above \"Weakness\" section well, I am willing to consider raising my scores.\n\n********* After Rebuttal *********\n\nThe authors have addressed by concerns and I am willing to raise my scores to \"Weak Accept\".", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "spm33NRidi", "reviewer": "Reviewer_Bi6F", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "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": "### Strengths:\n1. The idea of using GNTK to understand the over-smoothing issue is interesting. I think this approach opens up new viewpoints and directions on understanding GNNs and should be interesting to the community.\n2. The experiment results aligned with the theoretical claims and insights very well and showed that the messages in the paper are sound.\n3. Dropping edges following the critical connectivity theorem is insightful. Although it is a sample add-on to the DropEdge method (Rong et al., 2019), this extra piece of information is important.\n\n### Questions:\n1. I am curious whether this critical drop rate would still be the best on some denser graphs? It seems that the three node classification benchmarks considered are all relative sparse graphs whose average node degree is less than 5. The critical drop rate leads to a graph whose average node degree is equal to 1. And this might be too sparse for some denser input graphs (i.e., dropping too much information)? I found this critical DropEdge also provides some insights on improving the Message Passing architecture. Thus some further exploration might be interesting.\n2. The insights behind critical DropEdge is to break the connectivity. However, it is unclear how this would affect the theoretical results (Corollary 1). Do you think there are other possible methods to get rid of the exponential decay without affecting the connectivity?\n\n### Weaknesses:\n1. The baseline methods considered in the paper are limited. I agree that DropEdge should be the most relevant baseline, but it would be better to discuss some other methods (e.g., normalization-based approaches). I also find the related work section insufficient. It would be interesting if the new theoretical framework could provide some insights on the other research on understanding/solving the over-smoothing issue.", "summary_of_the_paper": "This paper provided a novel viewpoint to understand the over-smoothing of deep GCNs by analyzing the asymptotic behavior of the Graph Neural Tangent Kernel (GNTK), which governs the optimization trajectory under gradient descent for wide GCNs. It is shown the trainability of GNTK (and thus wide and deep GCNs) drops at an exponential rate in the optimization process. It is also found that residual connection-resemble techniques can only help slow down the exponential decay of trainability but cannot overcome the problem. Following the \"Critical Connectivity in Random Graph\" by (Erdos & Renyi, 2011), the paper also provided insights on what critical edge-drop rate should be used in DropEdge. Experiments verify the theoretical results, and the critical DropEdge can consistently outperform other drop rates.", "summary_of_the_review": "This paper tries to understand the over-smoothing problem of deep and wide GCNs using the theoretical framework provided by GNTKs. The results on the exponential decay of trainability, residual connections, and critical connectivity are insightful and should be interesting to the community. The experimental results are well-aligned with the claims and show the soundness of theoretical findings. Given the novelty and significance of the findings, I am happy to recommend this paper for acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "rEaORI_kRju", "reviewer": "Reviewer_UKok", "summary": "", "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": "The theoretical perspective presented is interesting. However, I have the following comments:\n\n1) In Corollary 1 it is claimed that there exists some L_0 for which for all L > L_0 the GNTK at depth L is singular. In the proof of the corollary, the authors say that this follows from Theorem 1. However, I do not see exactly why this is the case. The fact that the limit of the GNTK is singular does not imply that there exist some finite L_0 for which this is singular. Is this right?\n\n2) In Theorem 2, I presume that there is some implicit relation between \\tilde{\\lambda_2} and \\tilde{\\alpha}, otherwise the last sentence about the relation of the second eigenvalue of \\mathcal{A}(G) is irrelevant to the rest of the result and to the discussion after the Theorem. In other words, for the Theorem 2 to imply that “residual connection can slow down convergence rate”, I imagine that the authors are referring to the fact that \\tilde{\\alpha} in Theorem 2 is larger than \\alpha in Theorem 1, but this is never stated.\n\n3) The \\alpha in Theorem 3 has to be the same as the \\alpha in Theorem 1 for the story to make sense. I understand that this is the case, but this is never mentioned.\n\n4) The solution proposed by the authors not to converge to a singular GNTK is to break the connectivity in the graph by dropping edges. However, this brings up a few natural follow-up concerns that are not addressed:\ni) Wouldn’t you still have the same problem within each connected component of the new graph?\nii) Is really destroying information (deleting edges) present in your graph the best way to shield against the effect of deeper networks?\niii) Can something be said either theoretically or empirically about the GNTK of such networks? One would expect a Theorem like 1, 2, or 3 but for this new case showing that in the limit this architecture converges to something useful for classification, but there is no discussion in this direction.\n\n5) The empirical results of Critical-DropEdge are not too much better than the baseline which suffers from exponential convergence. For example, the vanilla GCN in CORA goes from an accuracy of 79.8% with 4 layers to 20.1% with 32 layers, a massive decay. However, with the technique presented here this drop goes from 82.0% to 24.7%, which is in the same order of a massive drop. Moreover, for GCN, even with the proposed critical DropEdge, the architecture with 4 layers outperforms all of the deeper alternatives across the three datasets studied. In this sense, it seems like the proposed methodology mildly slows down the deterioration with depth, but cannot leverage depth since shallow GCNs are still performing better.\n\n6) There are several typos and inconsistencies that should be addressed. E.g., if we only focus on page 6: \n- in Theorem 2 the first appearance of \\alpha should be \\tilde{\\alpha}\n- in Theorems 2 and 3 the authors refer to v and v’ as matrices when they are vectors\n- the probability p=|E|/E_t is not the probability of dropping an edge but the probability of retaining an edge.\n- the sentence “the probability that there is an open path from some fixed point (say the origin) to a distance decreases polynomially” seems to be taken from somewhere else and copied out of context. What is an “open path” here? What is the “origin” in a graph? What “distance” are we referring to?\n- Maybe it might be better to cite the original paper from Erdos-Renyi using the actual date. This is a paper from the 60s and it might be misleading to present this result as something from 2011 even if this paper was included in some more modern collection of papers. ", "summary_of_the_paper": "This paper uses a GNTK formulation to show how the performance of a deep GCN decays for node classification tasks with increasing depth. The authors show that in the infinite-width settings (where NTKs are valid) a very deep network amounts to a constant GNTK, meaning that the kernel value between any pair of nodes converges to the same value. Consequently, node classification performance degrades drastically with depth. Based on this analysis, the authors then propose a workaround to mitigate this decay by dropping edges in the original graph.\n", "summary_of_the_review": "The authors present an interesting perspective to justify the decay in performance of deep GCNs. On the downside, the provided solution is not studied within the same theoretical framework and does not show promising empirical results.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Z2EKctgitS6", "reviewer": "Reviewer_KNdY", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Strength: \n(a) They are the first to focus on the trainability of deep GCNs through GNTK, instead of expressive power. \n(b) Analysis and proof of the exponential convergence rate of the GNTK and that of residual techniques. \n\nWeakness:\n (a) An error in and equation 6 when formulating GCNs. Graph Convolutional Networks do not have such decoupled formulations.\n (b) A fundamental error in and equation 1, 7 when formulating GNNs or GCNs. The non-linear activation function phi appears at the most INNER place in equation 1, 7, before the transformation. But neural networks usually have their activation after the transformation. Note that the activation functions are NON-LINEAR functions. All the analyses based on such an equation may be rechecked.\n(c) Their experiments are based on only three citation datasets, which are limited both in fields and scales. \n(d) No detailed information such as data splits is provided.\n", "summary_of_the_paper": "They first investigate the trainability of deep GCNs through GNTK, instead of expressive power, and theoretically prove that the convergence rate of the GNTK is exponential. A similar analysis is given to residual techniques in GCNs, which shows residual techniques can alleviate such a problem to some extent but cannot solve it. Finally, based on their findings and analysis, they propose an edge-based sampling method named Critical DropEdge, to overcome the exponential decay of trainability.", "summary_of_the_review": "The paper's insights are good, but the theoretical analysis seems based on a wrong equation, so they may need to recheck the results. Experiments conducted on more types of datasets in different fields and scales are required.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "ENbMRWPOoXd", "reviewer": "Reviewer_sX4L", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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. Previous methods only explore the expressivity of GCN and this work focuses on a more fundamental problem, whether gradient descent can find a good solution for deepGCN.\n\n2. This paper has a solid and detailed mathematical derivation of the proposed theory. The experiments actually show that the residual connection doesn’t solve the problem but slows down the collapse speed during training and the distance between elements drops exponentially, which corresponds to the exponential decay of trainability.\n\nComments:\n1. The proposed solution edge drop has been widely applied in many models. The optimal dropout rate is not a significant breakthrough. It could be easily found by the hyperparameters search. \n\n2. The experimental setting still has some problems. There is only one baseline which is published in 2020. Maybe the author could incorporate more methods that aim to train a deep graph convolutional model to show their solution's superior performance. \n\n3. The comparison is not fair. The hyperparameters for the baseline have been set the same as the original paper. But the train/validation/test set may not be the same. Because this paper reported results for the baseline are not consistent with the original paper. For example for 8 layers, the Cora dataset reported by the original paper on GCN and JKNet model is 85.80 and 87.80. The corresponding result in this paper is 75.1,  82.0.\n", "summary_of_the_paper": "This paper utilizes the latest technology called GNTK to explore the trainability of deep graph convolutional networks. They prove that the trainability will decay exponentially as layers go deeper and residual connection only mitigates this phenomenon. They proposed to utilize drop edge methods to solve this problem. The dropout rate is determined by the theory. And the experimental result shows that their solution is better than the baseline.", "summary_of_the_review": "The experimental results prove the consistency between the theory and reality.\nFor the weakness of this paper, the proposed solutions to solve this problem are far less attractive and the comparison with the baseline is not fair.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this paper, the authors established interesting theoretical results regarding the behavior Graph Neural Tangent Kernel (GNTK). They also provide sufficient evidence (some of which during rebuttal) that their approach is valid. We have had many discussions and I suggest that the authors apply reviewers' comments to the final version of their paper.
Decision: Accept (Poster)