Representation Power of Graph Convolutions : Neural Tangent Kernel Analysis
Authors: Mahalakshmi Sabanayagam
Pascal Esser
Debarghya Ghoshdastidar
Venue: Submitted to ICLR 2023 (2023)
Keywords: Graph Neural Networks
Neural Tangent Kernels
Node classification
Stochastic Block Model

Abstract: The fundamental principle of Graph Neural Networks (GNNs) is to exploit the structural information of the data by aggregating the neighboring nodes using a `graph convolution’. Therefore, understanding its influence on the network performance is crucial. Convolutions based on graph Laplacian have emerged as the dominant choice with the symmetric normalization of the adjacency matrix $A$, defined as $D^{-1/2}AD^{−1/2}$, being the most widely adopted one, where $D$ is the degree matrix. However, some empirical studies show that row normalization $D^{−1}A$ outperforms it in node classification. Despite the widespread use of GNNs, there is no rigorous theoretical study on the representation power of these convolution operators, that could explain this behavior. In this work, we analyze the influence of the graph convolutions theoretically using Graph Neural Tangent Kernel in a semi-supervised node classification setting. Under a Degree Corrected Stochastic Block Model, we prove that: (i) row normalization preserves the underlying class structure better than other graph convolutions; (ii) performance degrades with network depth due to over-smoothing, but the loss in class information is the slowest in row normalization; (iii) skip connections retain the class information even at infinite depth, thereby eliminating over-smoothing. We finally validate our theoretical findings on real datasets.

Under review as a conference paper at ICLR 2023
REPRESENTATION POWER OF GRAPH CONVOLUTIONS NEURAL TANGENT KERNEL ANALYSIS
Anonymous authors Paper under double-blind review
ABSTRACT
The fundamental principle of Graph Neural Networks (GNNs) is to exploit the structural information of the data by aggregating the neighboring nodes using a 'graph convolution'. Therefore, understanding its influence the network per- formance is crucial. Convolutions based on graph Laplacian have emerged as the dominant choice with the symmetric normalization of the adjacency matrix A, de- fined D 1 AD- 1, being the most widely adopted one, where D is the degree matrix. However, some empirical studies show that row normalization A outperforms in node classification. Despite the widespread use of GNNs, there is no rigorous theoretical study on the representation power of these convolution operators, that could explain this behavior. In this work, we analyze the influence of the graph convolutions theoretically using Graph Neural Tangent Kernel in a semi-supervised node classification setting. Under Degree Corrected Stochastic Block Model we analyze different graphs that have homophilic, heterophilic and core-periphery structures, and prove that: (i) row normalization preserves the un- derlying class structure better than other convolutions; (ii) performance degrades with network depth due to over-smoothing but the loss in class information is the slowest in row normalization; (iii) skip connections retain the class information even at infinite depth, thereby eliminating over-smoothing. We finally validate our theoretical findings numerically and on real datasets.
INTRODUCTION
With the advent of Graph Neural Networks (GNNs), there has been a tremendous progress in the development of computationally efficient state-of-the-art methods in various graph based tasks, in- cluding drug discovery. community detection and recommendation systems (Wieder et al.) 2020) Fortunato & Hric 2016 van den Berg al. 2017). Many of these problems depend on the struc- tural information of the entities along with the features for effective learning. Because GNNs exploit this topological information encoded in the graph, it can learn better representation of the nodes or the entire graph than traditional deep learning techniques, thereby achieving state-of-the-art perfor- mances. In order accomplish this, GNNs apply aggregation function to each node in a graph that combines the features of the neighboring nodes, and its variants differ principally in the methods of aggregation. For instance, graph convolution networks use mean neighborhood aggregation through spectral approaches (Bruna et al., 2014; Defferrard et al. 2016 Kipf & Welling, 2017) spatial approaches (Hamilton et al.) 2017 Duvenaud al. [015]] Xu et al. 2019). graph attention networks apply multi-head attention based aggregation (Velickovic et al. 2001 8) and graph recurrent networks employ complex computational module (Scarselli et al. 2008| et al. 2016). Of all the aggregation policies, the spectral approach based on graph Laplacian is most widely used in practice, specifi- cally the one proposed by Kipf & Welling (2077) owing to its simplicity and empirical success. In this work, focus on such graph Laplacian based aggregations in Graph Convolution Networks (GCNs), which we refer to as graph convolutions or diffusion operators.
Kipf & Welling (207)) propose GCN for node classification, semi-supervised task, where the goal is to predict the label of a node using its feature and neighboring node information. This work suggests symmetric normalization Seym D- AD - as the graph convolution. Ever since its in- troduction, S sym remains the popular choice. However, subsequent works (Wang al.) 2018 Wang al. 2021) explore normalization Srow D and partieu-
& Leskovec 2020 Ragesh

---

Under review as a conference paper at ICLR 2023
larly, Wang et al. (018)) observes that Srow outperforms Seym for two-layered GCN empirically. Intrigued by this observation, and as both S sym and Srow are simply degree normalized adjacency matrices, we study the behavior over depth and observe that Srow performs better than S Sym in this case as well, as illustrated in Figure |
(Details of the experiment in Appendix B.T..
Furthermore, another striking observation from Figure 1 is that the performance of GCN without skip connections decreases considerably with depth for both Seym and Srow- This contra- dicts the conventional wisdom about standard neural networks which exhibit improvement in the performance as depth in- creases, Several works (Kipf & Welling 2017; [Chen et al.)
Recursey of clss obon
70-
2018 Wu et al. 2019) observe this behavior empirically and attribute it to the over-smoothing effect from the repeated ap- plication of the diffusion operator, resulting averaging out of the feature information to degree where it becomes uninforma- tive (Li et al. 2018; Oono & Suzuki, 2019 Esser et al., (02T). As a solution to this problem, Chen et al. (2020) and Kipf & Welling (017) propose different forms of skip connections that
60-
55-
50
of
Figure 1:
Performance of GCN over depth with and without skip connections using S Saym and Srow evaluated on Cora dataset.
overcome the smoothing effect and thus outperform the vanilla GCN. Extending it to the comparison of graph convolutions, our experiment shows Srow is prefer- able to S sgm over depth even in GCNs with skip connections (Figure D Naturally, we ask: what characteristics of Srow enable better representation learning than Saym in GCNs?
Rigorous theoretical analysis is particularly challenging in GCNs compared the standard neural networks because of the graph convolution. Adding skip connections further increase the complexity of the analysis. To overcome these difficulties, we consider GCN in infinite width limit wherein the Neural Tangent Kernel (NTK) captures the network characteristics very well (Jacot et al. 2018). The infinite width assumption not restrictive for graph convolution analysis as the convolution operates on the graph and not the network directly, thus showing same observations as trained GCN (Fig- ure 5). Morcover, NTK enables the analysis to be parameter-free and hence climinating additional complexity induced for example by optimization. Through the lens of NTK, we study the impact of different graph convolutions under a specific data distributional assumption - Degree Corrected Stochastic Block Model (DC-SBM) (Kareer & Newman, 2011). sparse random graph model. The node degree heterogeneity induced in DC-SBM allows us to analyze the effect of different types of normalization of the adjacency matrix, thus revealing the characteristic difference between Saym and Srow- Additionally, this model enables analysis of graphs that have homophilic, heterophilic and core-periphery structures. In this paper, we present formal approach to analyze GCNs and, specifically, the representation power of different graph convolutions, the influence of depth and the role of skip connections. This significant step toward understanding GCNs as facilitates for more informed network design choices like the convolution and depth, as well as development of more competitive methods based on grounded theoretical reasoning rather than heuristics.
Contributions. This paper provides rigorous theoretical analysis of the discussed empirical observa- tions in GCN under DC-SBM distribution using graph NTK, leading to the following contributions.
(i) In Section 2.
we derive the NTK for GCN in infinite width limit considering node classification setting. Using the NTK for linear GCN and under DC-SBM data distribution, we show in Section 3 that Srow preserves class information by computing the population NTK for different graph convo- lutions. We also present numerical validation of the result in homophilic and heterophilic graphs.
(ii) We prove the convolution operator specific over-smoothing effect in vanilla GCN by showing the degradation in class separability with depth in Section 3.1 and also illustrate it experimentally.
(iii) In Section 4 we leverage the power of NTK to analyze two different skip connections (Kipf & Welling. 2017 Chen et al., 2020). We derive the corresponding NTKs and show that skip connec- tions retain class information even at infinite depth along with numerical validation.
(iv) We show that S.ym maybe preferred over Srow in absence of class structure in Section 5 and validate the theoretical results on real datasets Cora in Section a and Citeseer in Appendix B.5
We finally conclude in Section 7 with the discussion on the impact of the result and further possibil- ities, and provide all the proofs, experimental details and additional experiments in the appendix.
2

---

Under review as a conference paper at ICLR 2023
Related Work. While GNNs are extensively used in practice, their understanding is limited, and the analysis is mostly restricted to empirical approaches (Bojchevski et al. 2018: Zhang et al. 2018
Ying et al., 2018, Wu et al. 2020). Beyond empirical methods, ngorous theoretical analysis using learning theoretical boundy such as VC Dimension, [Scarselli et al. (0018) or PAC-Bayes [ Liao et al. (202T) propounded. Rademacher Complexity bounds (Garg et al. 2020 Esser al.) 2021) show that normalized graph convolution is beneficial, but those works do not provide insight on the different normalizations, and their influence on the GCN performance. Another possible tool is the NTK using which interesting theoretical insights in deep neural networks are derived (e.g. (Du et al., 2019a)). In the context of GNNs, Du et al. (2019b) derives the NTK in the supervised setting (each graph is a data instance to be classified) and empirically studies the NTK performance, however does not extend it to a theoretical analysis. In contrast, we derive the NTK in the semi- supervised setting for GCN with and without skip connections, and use it to further theoretically analyze the influence of different convolutions with respect to over-smoothing. Thcoretical studies OOono& & Suzuki, 2019 Cai & Wang 2020) show that over-smoothing causes the expressive power of GNNs to decrease exponentially with depth, while Keriven (2022) proves that in linear GNNs finite number of convolutions improves learning before omor-smoo kicks in. While over- smoothing and role of skip connections in GNNs are theoretically analyzed in some works (Esser al., 2021). the influence of different convolutions that causes over-smoothing and their interplay with skip connections is not studied. For a comprehensive theory survey see Jegelka (022).
Notations. We represent matrix and vector by bold faced uppercase and lowercase letters, respec- tively, the matrix Hadamard (entry-wise) product by @ and the scalar product by (...). We use M to denote Hadamard product of matrix M with itself repeated times. Let (H,, Σ) be Gaussian distribution with mean μ and co- co-variance E. We use o.) to represent derivative of function a(), Inx for the n X matrix of ones, I, for identity matrix of size n x n, 1[.] for indicator function, [-] for expectation, and [d] {1, dJ.
2 NEURAL TANGENT KERNEL FOR GRAPH CONVOLUTIONAL NETWORK
Before going into a detailed analysis of graph convolutions we provide a brief background on Neu- ral Tangent Kernel (NTK) and derive its formulation in the context of node level prediction using infinitely-wite GCNs. Jacco et al. (2018): Arora et al. (2019); Yang (201)) show that the behav- ior and generalization properties of randomly initialized wide neural networks trained by gradient descent with infinitesimally small learning rate is equivalent to a kernel machine. Furthermore, [Ja-] cot et al. (2018) also show that the change in the kernel during training decreases the network width increases, and hence, asymptotically, one can represent an infinitely wide neural network by a deterministic NTK, which is defined by the gradient of the network with respect to its parameters as
{ KOP(W OW
x) aF(W, x') OW
xx,x'))=
E
(-
Here F(W, x) represents the output of the network at data point x parameterized by W and the ex- pectation is with respect to W, where all the parameters of the network are randomly sampled from Gaussian distribution. Although the 'infinite width' assumption is too strong to model real (finite width) neural networks. and the absolute performance may not exactly match, the empirical trends of NTK match the corresponding network counterpart, allowing us to draw insightful conclusions. This trade-off's is worth considering as this allows the analysis of pree-parrmeterisee neural networks without having to consider
tuning and training.
Formal GCN Setup and Graph NTK. We present the formal setup of GCN and derive the corre- sponding NTK, using which we analyze different graph convolutions. Given a graph with n nodes and set of node features )a R/, we may assume without loss of generality that the set of observed labels {y.)m correspond to first nodes. We consider K classes, thus y; {0, 1]k We represent the observed labels of m nodes as Y E 10 x K and the node features as X E IRaxf with the assumption that entire X is available during training. We define E "xn be the graph convolution operator as an expression of the adjacency matrix A and the degree matrix D. The GCN of depth d is given by
and the goal is to predict the n m unknown labels
-ooSo So hd
(v..o(/)u) So (SXW1) Wo)...) Wa-1 h1
Fw Fw((
(2)
V
3

---

Under review as a conference paper at ICLR 2023
where W (W; Rh ) 1d+1 is the set of learnable weight matrices with ho and hd+1 = K. h, is the size of layer E [d] and σ R R is the point- wise activation function. We initialize all the weights to be ii. (O, 1) and optimize it using gradient descent. We derive the NTK for the GCN in infinite width setting, that is, h,,-.., ha - oc. While this setup is similar Kipf & Welling (2017). it is important note that consider linear output layer that NTK remains constant during training (Liu et al. 2020) and additionally add normalization V Ca /hg
for layer i ensure that the input norm is approximately preserved and ci
IE w~N(0.1)
(similar to Du et al. (2019a)) The following theorem states the NTK between every pair of nodes, as n X n matrix that can be computed once, as shown below.
Theorem (NTK for Vanilla GCN) For the vanilla GCN defined in the NTK O at depth d is
d+1
d+1-k
Σ Σ o (SS7) old+1-k) ①
(3)
k=1
k'=k
Here Σg E Rax is the co-variance between nodes of layer k, and is given by Σ1 SXX"ST, (FF) and Eş Co
Σx = SE with Eg = Co
E (0,)()
E
6 (FF)
E~)
Comparison to Du et al. (2019b). While the NTK in 3 is similar to the graph NTK in Du et al. (2019b), the main difference that NTK in our case is computed for all pairs of nodes in graph as we focus on semi-supervised node classification, whereas Du et al. (2019b) considers supervised graph classification where imput is many graphs and the NTK is evaluated for all pairs of graphs.
CONVOLUTION OPERATOR Srow PRESERVES CLASS INFORMATION
We use the derived NTK in Theorem D to analyze different graph convolutions for S defined in Definition by making the following assumption on the network.
Assumption (Linear GCN with orthonormal features) GCN in said to be linear with or- thonormal features if the activation function (xx x and XX_ In--
Remark Assumption 1 The linear activation does not impact the performance of a GCN sig- nificantly as Wu et al. (2019) empirically demonstrates that the linearized GCN performance is at par with the non- non-lineat models with much reduced complexity. Additional orthonormal features assumption eliminates the influence of the features and facilitates identification of the influence of different convolution operators. Besides, the evaluation of our theoretical results without this as- sumption on real datasets is presented in Section Appendix B.5 that substantiate our findings.
Therefore, the NTK for linear GCN with orthonormal features of depth is,
(d)
Σx
(SS @(d+1-k) with Σ, **""*"
(4)
Definition 1 Symmetric degree normalized Saym D D AD 4 row normalized Syow D
A,
column normalized Scot = AD and unnormalized Sodj 1 A convolutions.
While the NTK in gives precise characterization of the infinitely wide GCN, we can not directly draw conclusions about the convolution operators without further assumptions on the input graph. Therefore, we consider planted graph model as described below, that helps in establishing the exact representation power of each operator.
Random Graph Model. We consider that the underlying graph is from the Degree Corrected Stochastic Block Model (DC-SBM) (Karrer & Newman 2011) since it enables us to distinguish between Saym. Srow, Scot and Sadj by allowing non-ume pon-uniform degree distribution on the nodes. The model is defined follows: Consider set of nodes divided into K latent classes (or com- munities), C, E [1, The DC-SBM model is characterized by the parameters p. q E [0, governing the edge probabilities inside and outside classes and the degree correction vector
4

---

Under review as a conference paper at ICLR 2023
(Ti,..... ........ "T.....TT)............... E J0, 1]"h with E, ग. = 1. A random graph on nodes, generated from DC- spaecfff SBM, has mutually independent edges with edge probabilities specified by the population adjacency matrix M E [A] Rax", where
PRITT
if C C2 if if c2
M
T
This allows us to model different graph types: Homophilic graphs: 0 g < S 1, Hcterophilic q (no assumption on class structure)
graphs: 0 S p < q S. 1 and Core-Periphery graphs: and π encode core and periphery. It is evident that the NTK is a complex quantity and computing its expectation is challenging given the dependency of terms from the degree normalization in S, its powers S and SS" To simplify our analysis, we make the following assumption on DC-SBM,
Assumption 2 (Population DC-SBM) The graph has weighted adjacency A M.
Remark on Assumption []] Assuming A M equivalent to analyzing DC-SBM in expected setting and it further enables the computation of analytic expression for the population NTK instead of the expected NTK. Moreover, we observe empirically that this analysis hold for random DC-SBM setting as well. In addition, this consideration also implies addition of self loop with probability p.
In the following theorem, we state the population NTK for graph convolutions Saym Srow. Scot and Sadj for K 2 with Assumption ] and 2 appendix.
The result extends to K 2 as discussed in the
Theorem (Population NTKs è for the four graph convolutions S) Let Assumption and 2-4
hold, K = 2 and r
p+g' d.j- (-1) Furthermore, π is chosen such that > T. IC
k] = k and Σi= Ic = k] = Vk,, where oy is a constant. Then Vi population NTKS + sym. row. coo and add of depth d for S Saym Scot and Sudh respectively. are,
1 y
+ 5ggr2) d+1
+ +5,, 2(d+1) 1 (ViTTT
Seyr2)
r d+1
a (d)
= mj
sym
1 v T (1 + d)))²)
1 Te (1 + dig r-
(2 (1 + ),y d+1
+ dign 2(4+1) 1- (27 (1 ),, )
1
r r-2) r-2) dt
(d)
= 27
YOW
1j
2x (1 + 81yr(2)
1- 1-27 27 (1 + dig 12) prrr)rr 2-
(n (1 + )x5r2)) 0+1
+ 21d51((d-1) - (nTTTT (1 + 51g r d+1
(d)
cnl
15
TJ
Wi (1 d:rr22
nTtz (1 deg
d+1
72 t
(5(d)
(d)
(1 1] (p² + +2) ) + 168 -1] (2pq)) d+1-k
adj
4j
122k
--
166; 1]
(2h) 21
2222-21
= 21 21 1186
-11(
2
12* 21
2141
27 +
1=0
Note that the two assumptions on are only to express the kernel in simplified, easy comprehend format. It is derived without the assumptions on π in Appendix [A.22 Furthermore, the numerical validation of our result is without both these assumptions (Section 3.2
Comparison of graph convolutions. The population NTKs e (d)) of depth d in Theorem describes the information that the kernel has after d convolutions with S. To classify the nodes perfectly, the kernel should ideally have a block structure that aligns with the DC-SBM (p and q blocks) unaffected by degree correction म, showing class separability, that is, gap between in-class and out-of-class blocks proportional to p q. On this basis, only θ row exhibits a block structure unaffected by the degree correction π., and the gap is determined by p" and d, making Srow preferable over S. S.ym ② @.ym. @cot and @adj are influenced by the degree correction which obscures the class information especially with depth. Although @. and Ô... seem similar, @cot is additionally influenced by the number of nodes in the graph, making it undesirable over Sym-- As result, the preference order from the theory is 6 row sym > Acot aadj-
Sadj and Scot- On the other hand,
5

---

Under review as a conference paper at ICLR 2023
DC-SBM
1e-3
1ex2
Avg. In-class & out-of-cass ml)
Heterophily --. Homophily
1.5
10-
0.5
0.0
Depth
Figure 2: Numerical validation of Theorem 2 using homophilic (g < p) and heterophilic (p 4) DC-SBM (Column 1). Columns and illustrate the exact NTKs of depth=2 for Saym and Srow respectively. Column 4 shows the average gap between in-class and out-of-class blocks from theory.
3.1 IMPACT OF DEPTII IN VANILLA GCN
Given that r P- 1, Theorem shows that the difference between in-class and out-of-class pig
blocks decreases with depth monotonically which in turn leads to decrease in performance with depth, therefore explaining the observation in Figure The kernel in the limit is stated below.
Corollary (Population NTK θ (10) d + 00) From Theorem 2
(@) (10)) ig
0 and V v, for
conv E {sym, row, col).
coWn
(x0)
- Viy (1 + 81GT2)
Vij
where Viz = T for sym, Vij =
2ny for row and Vyj T j for col.
From the corollary, infer that the class separability infinite depth 0 for Sudj. and O(r2) for Sym,, Srow and Scot showing that the large depth GCN has very little to zero class information. To further understand this, we plot the average in-class and out-of-class block difference for homophilic and heterophilic graphs using the theoretically derived population NTK (4) for depths [1, 10] in well separated DC-SBM (Column of Figure 2). It clearly shows the rapid degradation of class sep- arability with depth and the gap goes to for large depths all the four convolutions. Additionally, the gap in 6 row is the highest showing that the class information is better preserved, illustrating the strong representation power of Srow- Consequently, large depth is undesirable for all the four graph convolutions in vanilla GCN and the theory suggests Srow as the best choice for shallow GCN.
3.2 NUMERICAL VALIDATION FOR RANDOM GRAPHS
Theorem and Corollary T show that Srow has better representation power under Assumption and 2. that is, for the linear GCN with orthonormal features and population DC-SBM. We validate this on homophilous and heterophilous random graphs generated from DC-SBM shown column 1 of 1000 nodes with equal sized classes is sampled from each DC-SBM,
Figure 2 A graph of respectively. The heatmaps for depth=2 in the case of both homophily and heterophily graphs show that the class information for all the nodes is well preserved in Srow there is clear block structure than S sym in which each node diffused unequally due to the degree correction. Thus validating the results derived from population NTK. Appendix BB. presents the results for Sadj and Soot where both are uninformative and behave as derived theoretically.
4 SKIP CONNECTIONS RETAIN INFORMATION EVEN AT INFINITE DEPTH
Skip connection the most common way to overcome the performance degradation with depth in GCNs. but little is known about the effectiveness of different skip connections and their interplay with the convolutions. While our focus is to understand the interplay with convolutions, we also include the impact of convolving with and without the feature information. Hence, consider the

---

Under review as a conference paper at ICLR 2023
following two variants: Skip-PC (pre- core-oonvluuion), where the skip is added to the features before applying convolution (Kipf & Welling 2017); and Skip-a, which gives importance to the features by adding it to each layer without convolving with S (Chen et al. 2020). To facilitate skip connections, we need to enforce constant layer size, that is, h; = h4-1- Therefore, we transform the input layer using a random matrix W Ho XW of size h where Wij ~N(00 and h is the hidden layer size, Let H. be the output of layer i.
Definition PS) In a Skip-PC (pre-convolution) network, the transformed input Ho is added the hidden layers before applying the graph convolution S, that is, H, V (H to, (Ho)) W, vi E (d. where o,(.) can be linear or ReLU.
The above definition deviates from Kipf & Welling (017)) the fact that we skip to the input layer instead of the previous layer. The following defines the skip connection similar Chen et al. (2020).
Definition 3 (Skip-a) Given an interpolation coefficient E (0, 1), a Skip-a network is defined such that the transformed input Hg and the hidden layer are interpolated linearly, that is, H, V E ((1 a) SH,-1 + ao, (Ho)) W, vi E [d], where os o.(.) can be linear or ReLU.
4.1 NTK FOR GCN WITH SKIP CONNECTIONS
We derive NTKs for the skip connections Skip-PC and Skip-a by considering the hidden layers width h - oc. Both the NTKs maintain the form presented Theorem with the following changes to the co-variance matrices. Let Eg F~N(O.E.) [o. [F=(F)oFFF)
Corollary 2 (NTK for Skip-PC) The NTK for an infinitely wide Skip-PC network is presented in Theorem where Eg is defined as in the theorem, but Eg defined as
= = TXT,
E = SE,ST
and
= SE =E
E1.
Corollary (NTK for Skip-a) The NTK for an infinitely wide Skip-a network as presented in Theorem where Eg defined in the theorem, but Eg is defined with En XX".
Σ a)² SEOST + + a:) (SE EOS") + a a²Ep and Σg = (1 SE + a a2E..
4.2 IMPACT OF DEPTH IN GCNS WITH SKIP CONNECTION
Similar to the previous section we use the NTK for Skip-PC and Skip-a (Corollary and 3 and analyze the graph convolutions Saym and Sadj under the considerations detailed Section Since, Sadj and Scol are theoretically worse and not popular in practice, we do not consider them for the skip connection analysis. The linear orthonormal feature NTK, O (4), for depth d is same as with changes to Σ5 as follows,
Skip-PC: Σg S + SST
k-1 +
Skip-a: Σg (1 a) s aa a)) 2k-1 1 (S+ S*- k--1"
Σ (1 a)² s's
1=0
We derive the population NTK (d)) and, for convenience, only state the result as d + oo in the following theorems.
Theorem (Population NTK for Skip-PC 6 (Oo) Under the assumptions of Theorem 2
Tem (2 82
27 + 01yr2)
(00) PC.csym)
and (6 (00)
PC..row) )a= = 1-2 8,772)
(5)
Tojy (1 + 6,)r2)'

---

Under review as a conference paper at ICLR 2023
Avg. In in-class & out af class
block blockailrene aifrerence soncefeer 6'
10
0
Sym
Pc.5pm
20
155
10"4
1.0
05
10
Verilla GEN S.n Skip
5mm
Venilla GCN
Skip-PC
True class separabiliy
Figure 3: Left: average in-class and out-of-elass block difference at oo (in log scale) for different true class separability. Heatmaps: (8) for Saym and Srow for vanilla GCN and Skip-PC.
Theorem (Population NTK for Skip-a O.:²) Under the assumptions of Theorem
a²
6ij
((0))
+
and
a,stym
1-
T (1 d,rr?)
1 - 11(1- - a)²
aa)
1- a) 2)2
(6(ec) a.row
= 1 1j
27 (1 + )1
2
+ (1 a)²
1
(1 - a)) p2
ōij
(6)
in above theorems is to simplify the results. To understand the role of skip connections, we plot the gap between in-class and out-of-class blocks at infinite depth for different values of true class separability for vanilla GCN, Skip-PC and Skip-a using Corollary [ Theorems 3 respectively (Figure 3). The plot clearly shows that the gap is away from for both the skip connections given a reasonable true separation, unlike vanilla GCN. This implies the class information is retained in skip connections even at infinite depth.
Similar to Theorem assumptions
4.3 NUMERICAL VALIDATION FOR RANDOM GRAPHI
We validate our theoretical result using the same setup detailed Section 3.2 without the assump- tions, and compute the exact NTKs for Skip-PC and Skip-a for both S Saym and Spow. We show result on homophilic graphs but they equally extend to the heterophilic case. While Saym has no class information for depth=8 in vanilla GCN (Figure 3 middle), it is retained well in Skip-PC (right plot). In the case of Soow. we clearly observe the blocks in both cases with more prevalent gap in Skip-PC PC illustrating our theoretical results. Similar observation is made for Skip-a despite sidering xx" = I as the model interpolates with the feature, and is discussed in Appendix B.3] While both S Sam and Srow retain the class information in larger depths, we observe that the degree correction plays significant role in S.ym as elucidated in our theoretical analysis.
5 S sym MAYBE PREFERRED OVER Srow IN ABSENCE OF CLASS STRUCTURE
While we showed that the graph convolution Srow preserves the underlying class structure, it is natural to wonder about the random graphs that have communities (p 9). One such case is graphs with core- core-periphery structure where the graph has core nodes that are highly interconnected and periphery nodes that sparsely connected to the core and other periphery nodes. Such graph can be modeled using only the degree correction π such that < т, Vj E periphery, E core (similar to Jia & Benson (201)). Extending Theorem 2] we derive the following Corollary 4 and show that the convolution Seym contains the graph information while Srow is a constant kernel.
Corollary 4 (Population NTKs θ for q) Let Assumption 7 and hold, K 2 and p q. Furthermore, π is chosen such that Eiecore प. = X and Exeperiperry ". = p. Then Vi and j, the population NTKs ② sym and ② Trww of depth d for Soym and Srow, respectively, are,
d+1
= (1+ 1 (A μ1) 2+1
(a(d) #gm
and
+ (d) row
1 (
8

---

Under review as a conference paper at ICLR 2023
O .yym
( rDw
θ (BI
O
[g]
LB! 4. k..yym
1e-3
Rym
Fc.row
1e:2
row
le:3
Vonilia GCN
1.5
Skip-PC
Skip-a
1.0
0.5
Figure 4: Evaluation on Cora dataset. Heatmaps show results of vanilla GCN, Skip-PC and Skip-a where a min and max threshold of 10 and 90 percentile is set for better visualization.
From Corollary 4 it is evident that the S Srym has the graph information and hence could be preferred when there is no community structure. Furthermore, interestingly even skip connections prove be of no use for Srow and it remains a constant kernel in this case as well. We validate experimentally and discuss the results in Appendix [3.3 (Figure TO). While Srow results in a constant kernel for core- periphery without community structure, it is important to note that when there exists a community structure and each community has core-periphery nodes, then Srow is still preferable over Ssym is simply special case of homophilic networks. This is demonstrated in Appendix B.3 (Figure
EMPIRICAL ANALYSIS ON REAL DATA
In this section, we explore how well the theoretical results translate to real dataset Cora with features, that is, XXT * I, and A of M. We also provide experimental details and additional experiments on Citeseer Appendix [3. We consider multi-class node classification for Cora (K- 7) using GCN with linear activations and provide the results for ReLU activations in Appendix The NTKs for vanilla GCN, GCN with Skip-PC and Skip-a are illustrated in Figure We make the following observations from the experiments that validate the theory even in much relaxed setting, (i) clear block structures show up in both GCN with and without skip connections for Srow. thus illustrating that the class information well retained by Srow than S.ymi (ii) while we cannot compare the skip connections, is still evident that Symo is better than Saym for both Skip-PC and Skip-a as block structures emerge even in the case of large depth. Thus, although the theoretical result is based on DC-SBM with mild assumptions, the conclusions hold well in real settings on real datasets as well.
CONCLUSION
Graph convolution operators significantly influence the performance GCNs, but existing learning theoretic bounds for GCNs do not provide insight into the representation power of the operators. We present a NTK based analysis that characterizes different convolutions, thereby proving the strong representation power of Srow in community detection and explaining why Srow. and to some extent Saym, are preferred in practice (Theorem 2}. In contrast to applying spectral analysis of explicit characterization of the network provides
the convolutions explain over-smoothing, more exact quantification of the impact of over-smoothing in deep GCNs (Corollary [] see Figure 2). In addition, the NTKs for GCNs with skip connections enable precise understanding of skip connections in countering the over-smoothing effect (Theorems 3 While the DC-SBM assumption may seem restrictive, experiments on Cora and Citeseer show that our theoretical results hold beyond DC-SBM, although formally characterizing such behavior could be difficult without model assumptions. We note that our analysis could be extended by considering feature information (XXT * I,) or random samples from DC-SBM, which would require more involved analysis but could provide further insights into GCNs, such as interplay between graph and feature information.
the role
The present NTK based setup allows for the analysis of different graphs having homophilic, het- crophilic and core-periphery structures, and can be extended to other graph generating processes. Furthermore, the general formulation of NTK for vanilla GCNs (Theorem [} and with skip connec- tions (Corollaries 2 can be used for analyzing any new convolutions like topological structure preserving convolutions, for obtaining rigorous understanding of GCNs by deriving statistical consistency results or information theoretic limits, as well as for thcoretical analysis other graph learning problems, such link prediction.

---

Under review as a conference paper at ICLR 2023
8 ETHICS STATEMENT
Our work focuses on understanding some characteristics of the graph neural network theoretically and hence it doesn't 't have direct implications on the ethical and fairness aspects.
REPRODUCIBILITY STATEMENT
The assumptions for the theory are stated clearly in Assumptions T+ and all the theoretical results, Theorems h Corollaries I are proved in detail in Appendix A The implementation of GCN and NTK for GCNs with and without skip connections are provided in ntk gen conv. zip as supplementary material. Datasets used in the experiments are publicly available and also provided in data folder available in the zip. The experimental results can be reproduced by following the instructions in readme. md.
REFERENCES
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. In Conference on Neural Information Pro- cessing Systems, 2019.
Aleksandar Bojchevski, Oleksandr Shehur, Daniel Zügner, and Stephan Günnemann. Netgan: Gen- erating graphs via random walks. In International Conference on Machine Learning, 2018.
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and deep locally connected networks on graphs. In International Conference on Learning Representations, 2014.
Chen Cai and Yusu Wang. A note on over-smoothing for graph neural networks. arXiv preprint vrXiv:2006.13316 2020.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph con- volutional networks. In International Conference Machine Learning, pp. 1725 1735. PMLR, 2020.
Zhengdao Chen, Lisha Li, and Joan Bruna. Supervised community detection with line graph neural networks. In International Conference on Learning Representations, 2018.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Conference Neural Information Processing Systems, 2016.
Pedro Domingos. Every model learned by gradient descent is approximately kernel machine. arXiv preprint arXiv:2012.00/52, 2020.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learning, pp- 1675- 1685. PMLR, 2019a.
Simon S Du, Kangcheng Hou, Barnabás Póczos, Ruslan Salakhutdinov, Ruosong Wang, and Keyulu Xu. Graph neural tangent kernel: Fusing graph neural networks with graph kernels. Conference on Neural Information Processing Systems, 2019b.
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguiree, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan P Adams. Convolutional networks on graphs for learning molecular fingerprints. Neural Information Processing Systems, 28, 2015.
Pascal Mattia Esser, Leena C. Vankadara, and Debarghya Ghoshdastidar. Leaming theory can (sometimes) explain generalisation in graph neural networks. In Proceedings of the 34th In- ternational Conference on Neural Information Processing Systems, 2021.
Santo Fortunato and Darko Hric. Community detection in networks: user guide. Physics reports, 659: 199:1-40 2016.
10

---

Under review as a conference paper at ICLR 2023
Vikas Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. In International Conference on Machine Learming, pp. 3419-3430. PMLR, 2020.
William L Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning large graphs. In Conference on Neural Information Processing Systems, pp. 1025-1035, 2017.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: convergence and gen- eralization in neural networks. In Conference on Neural Information Processing Systems, pp. 8580-8589, 2018.
Stefanie Jegelka. Theory of graph neural networks: Representation and learning, 2022.
Junteng Jia and Austin R Benson. Random spatial network models for core-periphery structure. In Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining, pp- 366-374, 2019.
Brian Karrer and Mark EJ Newman. Stochastic blockmodels and community structure in networks. Physical review E, 83(1):016107, 2011.
Nicolas Keriven. Not too little, not too much: theoretical analysis of graph (over) smoothing. arXiv preprint arXiv:2205./22 /2/56, 2022.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In International Conference on Learning Representations (ICLR), 2017.
Jaehoon Lee, Yasaman Bahri, Roman Novak, Samuel Schoenholz, Jeffrey Pennington, and Jascha
Sohl-Dickstein. Deep neural networks as gaussian processes. In International Conference Learning Representations, 2018.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-superee supervised learning. In Proceedings of the AAAI Conference Artificial Intelligence, volume 32, 2018.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. In International Conference Learning Representations, 2016.
Renjie Liao, Raquel Urtasun, and Richard Zemel. A pac-bayesian approach generalization bounds for graph neural networks. In International Conference on Learning Representations, 2021.
Chaoyue Liu, Libin Zhu, and Misha Belkin. On the linearity of large non-linear models: when and why the tangent kernel is constant. In Conference on Neural Information Processing Systems, volume 33, pp. 15954-15964, 2020.
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In International Conference on Learning Representations, 2019.
Rahul Ragesh, Sundararajan Sellamanickam, Arun Iyer, Ramakrishna Bairi, and Vijay Lingam.
Hetegen: Heterogeneous graph convolutional networks for text classification. In Proceedings of the 14th ACM International Conference on Web Search and Data Mining, pp. 860-868, 2021.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini.
The graph neural network model. IEEE transactions neural networks, 20(1):61-80 2008.
Franco Scarselli, Ah Chung Tsoi, and Markus Hagenbuchner. The vapnik-chervonenkis dimension of graph and recursive neural networks. Neural Networks, 108:248 259, 2018
Rianne van den Berg, Thomas N Kipf, and Max Welling. Graph convolutional matrix completion. arXiv preprint arXiv: 1XXv:1700.0220 022600,..23,.... 2017.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Lio, and Yoshua Bengio. Graph attention networks. stat, 1050:4, 2018.
Hongwei Wang and Jure Leskovec. Unifying graph convolutional neural networks and label propa- gation. arXiv preprint arXiv:2002.06755 2020.

---

Under review as a conference paper at ICLR 2023
Xiaoyun Wang, Minhao Cheng, Joe Eaton, Cho-Jui Hsich, and Felix Wu. Attack graph convolutional networks by adding fake nodes. Proceedings of Woodstock 18: ACM Symposium on Neural Gaze Detection, Woodstock, NY, 2018.
Oliver Wieder, Stefan Kohlbacher, Mélaine Kuenemann, Arthur Garon, Pierre Ducrot, Thomas Sei- del, and Thierry Langer. A compact review of molecular property prediction with graph neural networks. Drug Discovery Today: Technologies, 37:1-12, 2020.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Sim- plifying graph convolutional networks. In International Conference Machine Learning, pp- 6861-6871. PMLR, 2019.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S Yu. A comprehensive survey graph neural networks. In IEEE transactions on neural networks and learning systems, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? International Conference on Learning Representations, 2019.
Greg Yang. Scaling limits of wide neural networks with weight sharing: Gaussian process behavior, gradient independence, and neural tangent kernel derivation. arXiv preprint arXiv:1902.04766. 2019.
Rex Ying. Jiaxuan You, Christopher Morris, Xiang Ren, William L. Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. In Advances in Neural Information Processing Systems, 2018.
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. AAAI Conference on Artificial Intelligence, 2018.
Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applica- tions. Al Open, 1:57-81, 2020.
12

---

Under review as a conference paper at ICLR 2023
A MATHEMATICAL DERIVATIONS AND PROOFS
We first derive the NTK (Theorem T for GCN defined in (2) and prove Theorem by considering linear GCN and computing the population NTK ( for different graph convolutions. We use 1 to denote a vector of r dimension with all 1s and i,, for vector of n dimension with 1 as first / entries and +1 as the remaining entries.
A.I THEOREM 1 NTK FOR VANILLA GCN
We rewrite the GCN Fw (X. S) defined in (2) using the following recursive definitions:
Co So (F Vi
G. = SX,
G: V
F; d++
Wi (7)
h
Thus, (X 5) = F d+1 and using the definitions in (7). the gradient with respect to W, is
OFw(X,
G B; with B841 las
B, B W
(F.)).
OW;
We derive the NTK, as defined in using the recursive definition of Fw (X, S) in and its derivative in (8)
Co-variance between Nodes. We will first derive the co-variance matrix of size n x for each layer comprising co-variance between any two nodes and v. The co-variance between and in F1 and F; are derived below. We denote u-th row of matrix Z as Z., throughout our proofs.
(F1) (F1) = [(G Wi (G1
(W)..,-(0..))
E
(1)
(W1)
Σ (G1) (W1)sk
;if + #
ho
[F1)uk (Fi)
(G1 (G1) (W1)
k=k
ho
(Wi) ((0.1)
(G1 (G1) = (G (G1)
(9)
h (G:) (Gi) (Wi)
E ((F) (Fi)
k=k
h-r
(W (W (1011)
Σ (G.). (Gi).r
(10)
Evaluating 9 and 10) terms of the graph in the following,
(G ). (G.),.) (SX),, (SX)..) S,, "X"xx" (Et)...
(11)
Co
10
(G.).. (Gi),.)
(So(FFF)))
h4-1
hi-1 (F=)F; (So (F:
Co
h
h1-1
Co
E (((Oo(F,-1)))
(So(Fi-
law of large numbers
E.E
Σ
S Surd (Fi-1)rs
Σ
Suso (F (Fr-1)
E.E
S S (F (Fi-1)ma (Fi-1)ek
13

---

Under review as a conference paper at ICLR 2023
Sur (E.-1)s S Sv. - (Ex)
(12)
(a): using E ()) a1 (2;-1)rs and the definition of E,-1 in Theorem
NTK for Vanilla GCN. Let first evaluate the tangent kernel component from W; respective to nodes u and c. The following two results are needed to derive it.
Result 1 (Inner Product of Matrices). Let and b be vectors of size d1 and d2 1, then
(ab", abb") = (ab² (abaab (ab")²)
(ab" (ab"ba") tr (a"ab aaabb)) (a''a) ② (b"b) (a, C (b.
(13)
Result 2 ((B,)u. (Brr).) We evaluate ((B,).. (Br),.) = (B,B,) appearing in the gradient.
hr
(B,B,) =
Co
S W1 o(F))uk BS" WT W à (FF))ot
hr
k=1
hr nuhip4s
R,br++1
Co
Σ
Sau (Br+1)ig (W++1)k O(F))ut (Fr)
Syv (Brtiley (Wr+1) Σ fndt
h4
2
a.h44
n.h++
he
Co
Σ
Σ
(Br+t)is (Br+t)sg StuSpe
( Wr+1)ag ō OFFr)u (Wr+1)yg
hr
is
kri1.
hr
Σ
(S Br+1) (S Bs4B)))) o3' hr
Co
(W (Wr+1)sg (FF)) (Wr+1)gg
3
km
hr+1
h 00
SS (r+r)) (STB)))) ColEE (W> a(Fr)uto(FF)
for j # #
(S B,+1) (S .. co (6 (u)
13
(SST) uu
(Br+1. B Br+1) co
(SS" uu (B Br+ 1 un
E,) ux
(14)
(b): (W, (Wr+1)ky is independent and E (W21)) =1]
=1].
Now, lets derive
((ow.) (ow, and ( (ow,)
(00r OF
oww,
using the above results.
OF ((WW))
OF OW
= (G+) (Be) (Gx) (Bx)..)
((G)).. (G&) O (BB)... (Bx)..)
En Ju (SS uu (Br+1, Br+1)un
E,
mv
dd+1-k
(c) EE)un un ((SST).. d+1-k
II
Ess
(B441, B841)
d++
(kx)oo ((SS")..
d+1-k
EN
(15)
W=
14

---

Under review as a conference paper at ICLR 2023
(c): repeated application of 14).
(d): definition of Bu+1-
Extending (15) to all nodes which will result in matrix,
OF OF OW
Σx o (SST) @d+1-A
d+1-k
Eg
OW
:==k
OF OW
OF
ow ) = Σ o (SS") od+1-k
(
d+1
E
Eg
(16)
W
Finally, NTK θ is.
d+1
OF
OF
θ
WR
E
aW
OW
d+1
d+1-k
Σg (SS7)
(((+1-))
Exp
(17)
k'=k
with definition Eg and Eg mentioned the theorem.
A.2 THEOREM AND COROLLARY 1 POPULATION NTK G FOR DIFFERENT S
We consider Assumption] I that is, linear GCN with orthonormal features and Assumption 2 without assumption on y. We first prove it for K and then extend to K classes. We consider that all nodes are sorted per class for ease of analysis which implies A is X matrix with pT; entries in [1, n1 [1, 2 2 blocks. Therefore,
2² and [ + n] + 1, n| blocks and T entries in [1, 2112 + 1. n] and 2 +1, n|[1, 2
A -
(
11
p 9 iiT)
2
p+ q
p-q A
2 n
(18)
2
where the entries of क are -; Vi [1, 3) and +n, Vie n
1,n].
D be the degree matrix of A
and D 2 diag((T))
A.2.1 SYMMETRIC DEGREE NORMALIZED ADJACENCY S sym Now, lets compute S Ssym using A
18 and its degree matrix D.
Sym D
diag(T))
p q π n
p q n +
diag(T))
p+g
2
n Z T
#2 7
+
p 9
T
-VTi T
VTI
/ π
1 0
p-
0
2x2
ir
p+0 4
V Ta
Tn
+
na
nx2
2xn
T
(19)
Note that T π
T = म T Φ
and U I,, thus
19 is the singular value decomposi-
tion of S.ym-
15

---

Under review as a conference paper at ICLR 2023
To compute the population NTK
(d) sgm
in
4
need S
syy sym
S
Using
19p
S* sym
S
SKT sym
UA
U
11
TT
V T1
1
0
0
y.26
vn
+ +v nn
V Tn
+v Tn
ax2
2xn
S sym eymm
= (1 + )igr22)
;ōi = (-1)2(c(*C,)
(1 + n2h)
(1 - 22h) J
Sk sym
SkT
mairix notation
(20)
(1 2k mj
+ 2k m
nXR
f
entries
Consequently, population NTK ② sym for nodes and j using (20) is as follows,
a (d) sym
T (1 desr (VTTTT (1 + (1+5))
ij
d+1
d+1
( T
d+2-k k (1 Sey )
d+1-k
+ 8.j
d+2-k
2 (1+ (1gr)) 2+
k=1
( (1 + dirt²)
d+1
/ [
/ V (1 + dzym2)
Wi + 8, r 2-
+ big / 2(d+))
2(d+1)
(21)
1 TT (1 + )2)72) r-
Since we consider Eiec, n. 1/K, the maximum of Tryyy < 1/4 for K = 2. This implics Men r2) 1. Therefore, NTK at d oo is
(00) sym
T
(22)
M (1 62)
prove the population NTK + (d) sym and + (.00) Theorem and Corollary
Equations 21 and 22 respectively.
A.2.2 Row DEGREE NORMALIZED ADJACENCY Srow
The assumption on y in Assumption is only to simplify the expression of population NTK for Spow- We derive it without this assumption in the following. We first derive S SKT
row
S Srow
D--AA
D D AD-
= !UAUUD
S Srow
D D'
Sk
SkT row row
D -'
= -(D-AUA'U'D- D D+ (D-LAA'U'D
-(ÜA-07) D² (U^+0T) (CCNOO"D((OA'OT)
2
D-D
1
p
10
nx2
16

---

Under review as a conference paper at ICLR 2023
(1 + pk)
x +
P r²) (2 + 1t)
if and j E class 1
3
Ske (st row Srow Kj
if and j & same class; ; X
x (1 + )²)² p
if and j E class? 2
7
(1+ - (1- (1+ (1-
S
KT Yow row
matrix not.
(23)
(1+ (1- (A+
(1- (1-rd)² x + (1 + (1+
nxn
entries
entries
Note that each block is a constant and independent of individual Ty. Using 23 NTK in (4) for i and j belonging to class 1 is,
d+1
(1+r*)² ( m) (11 (1 m)² d+1-k
(u)) 6
row
A=1
d+1
Σ (A + vb) (1++)) (1 (1 -+1- +
Σ 2 2(--)) w) (1++))> + (1 (1- -))² p))
d+1
d+1-k
d+1
(A 1) 2* (1++))*+(11- (1 d+1=
Σ A=1
(1- r)² u) d+1
1- (1++)) (
= (A+
+ 1 (1++)) x (1 (1-r)² m)
2(A 11-1) (1) d+1 1 (1+ ( (1-r)² (1) d+1 (d++)
1- ((++))*+(1 x+
H1 r-1
+ (1 (1-1))²² )
(1++)) x
d+1 (d(+1)
(A + (()
(24)
1- (1+ x (1 (1-))² r-
Similarly for and j in class 2,
d+1
(1 x d-1-k
a (d) row
(1-
x
1=
1- x x1 d+1
= (A++1))
1- x
d+l
1 -
r (d+1)
2 2(-X+ 11) r+11
1- (1-r)) x (1+1)² 11) p-1
1- (1--)² (1+r)² 1+1
((d(+))
(A + p)) 2(d-1)
(25)
- (1 r)² > + (1 r1)+ 1)) r-
17

---

Under review as a conference paper at ICLR 2023
When and j are in different classes.
1+1
6
(d) row
Σ (1- (A (1) ((1- (1) (A + 11) at1=
d+1
Σ k=
() + W1) 1)) (1 (1- o+= - - () 2) (1- d2)
(A+ + 11) d+1
(1 11)
(1- 72) d+1
(A + 11)
1 (A+ (1) (1 - x2)
- -(A+ 16) 2((+1) (A+ (1) d+1 (1- 22) d+1 2-1(41
(26)
1- (A + (1) (1 r2)m~
A μ < 4. (1+ x+ (1 - r) / < 2 + r²) <1, population NTK &row at d + oo is
(A + 11)
i and j E class
(1 + r)² X + (1 (1-r)² k)
(A *+H1 14)
b (oc)
i and j E different class
(27)
ig
(A + 11) (1 - x2)
(A [1)
i and j E class? 2
(1 (1-r)² A + (1 (1+ (1+r)² 1
When the assumption on is introduced, yys.t. > Tf = k] = yVk, X 2 and
X = 0. Hence, equations (44.. (25 and (26) of the population NTK 6.0) and (27 of 6 (cc)
reduce to the expressions in Theorem and Corollary respectively.
A.2.3 COLUMN NORMALIZED ADIACENCY Scol
In this section we derive the population NTK 6(d) col
Seol AD
= D D-
S = D D
RT S cot col
D D*AUAA D AUA'U'
(ÜA*OT) D-2 (ÜA*0*
Ü -
p p+ g
π
2
AT
nx2
NT (1+ 2h) IT (1 + 22k
ny; (1 2k)
matrix not.
(28)
IT (1- 2k
n 22k)
nXR
Therefore, 6
((i) col
is
entries
entries
1+1
a
(d)
Wy (1 + 2 (nVTTTy (1 + +.6rr22) 2)
coll
ij
k=1
d+1
d+1
(n ) d+2-k (1 + 6,577) d+1-k )d + +8
(noT:TT)) ( d+2-k 22 (1 + 12) 12) d+1-k
-- (nيzTTy (1 + p22) d+1
2 - (nTTTTTy (1 + 72) r -22
nm
(29)
nTt (1 + 22)
nT + 22) r-2
18

---

Under review as a conference paper at ICLR 2023
Since Eg n, O(2). So, nT: (1+ r²) < 1. Therefore, using (29
(
(30)
ij
IT (1 d
Hence, equations (29 and 30 prove the population NTK ② (d) lary
col and (Do) ool in Theorem 2 and Corol-
respectively.
A.2.4
UNNORMALIZED ADIACENCY Sadj
We can rewrite A follows,
nxn
3 entries
entries
T
p
(31)
TT
p
Tn.
nxn
nxn
We consider y assumption for the analysis of unnormalised adjacency to simplify the computation. But the result holds without this assumption.
(p² +2))
2pqy
2
31
TT
2pgy
(p² + q2) 7
T
(p* + 9 + 6p² g3
(4p2 4pg²) 73
A
Tn
(4p2q + 4pn²) 73
(p² + + 6p2 73
np
Note that the above shown 2k is the even powers of binomial expansion of (p + q) in same class whereas it is the odd powers for i not in the same class. We compute the filter Sadj using this fact.
2 for i.j
1
Sadj
A
π 1
Sk
adj
Sk
S adj
A 2h
n2
24-1
T
2h
22
21
2 -21
21
if and j same class
2 24
)
if and j E different class 21 -21-1, -21-1
d+1
2k +
(p² + 92) d+1-+ (2)
24-1
Σ
22 22
2
p2
if and same class
2h
21
(d) adj
d+1
72 2z +
24 1 1_1
(2pd) d+1-k
Σ
2
2
-21 1
if and different class
2k
21+1
19

---

Under review as a conference paper at ICLR 2023
The above form is not simplified as it is not interesting where the gap between the two blocks disappears rapidly and (oc) Theorem 2 and Corollary I
O. There is no information in the kernel proving both
edii
A.2.5 NUMBER OF CLASSES K
From the above derivation for K = 2. it can be seen that once S sym sgm is computed, the popula- tion NTK for all the graph convolutions can be derived using it. Therefore, derive it for K > and it suffices to show the conclusions of Theorem 2 and Corollary [
We denote the vector Ti
with Vi E [1, R +TVViE
E
nik-11 K
nk and O for the rest. With this definition, is K
p K 1)4
P K
A
(32)
K
D for K classes is p+(K- 1)
(ia from
32
We can compute Saym using and as follows,
K
S Ssym = D AD
K ----
K
p (K 1)9
= + (K 1)g
diag(T (+)
π
T
+
Σ मा
diag(T +))
K
K 1=2
p p-
T 11
p (K- -1) 1=2
K
(S (Sym))s = TT
1+ dij
P-9
Σ
K 12
p+ (K - 1)g
l
1=2
K
(st (8sy)) is
1 dij
p-9
K
p+ (K 1)g
1=2 1+
(sk sym Sgym)
1+ dij
p-9 p + (K
2A
K
(33)
ij
1)g
1+
is noted that the equation (33) is very much similar to 20 for K 2. The further derivations of the population NTKs for all the convolutions are similar and the theoretical results extend without any issues.
A.3 NTK FOR GCN WITH SKIP CONNECTIONS (COROLLARY' 2 AND
We observe that the definitions G; Vi E [1, d+1] are different for GCN with skip connections from the vanilla GCN. Despite the difference, the definition of gradient with respect to W, (8) does not change as G; in the gradient accounts for the change and moreover, there is no new learnable parameter since the input transformation H, X XW, where (Wo)ay is sampled from (00 1) is not learnable in our setting. Given the fact that the gradient definition holds for GCN with skip connection, the NTK will retain the form from NTK for vanilla GCN as evident from the derivation of NTK for vanilla GCN in Section A.1 The change in G; will only affect the co-variance between nodes. Hence, we will derive the co-variance matrix for Skip-PC and Skip-a in the following.
Skip-PC: Co-variance between nodes. The ca-vinnacce between nodes and v in F1 and F; are derived below.
(F (Fi) ((G)),.,
Co h
(Soo (Ho)) (So, (Ho))..
(So, (Ho)) (So, (Ho))
20

---

Under review as a conference paper at ICLR 2023
10000
og E (So, (So,(HH))...
law of large numbers
S., E
Eo
Co
E
( [F,(F)o,(F)))
B~N(0.XX"))
(Ei)ue
(34)
E (FFiuk (Fi)
;
h
Co
(So(F (F; So, (H,))) (F; So, (Ho))
h 2 c, [F So, (Ho) (So (F; + So (og) (Ha))
law of large numbers
co +
(So, (Ho))
+B (L))) [d) ((S (So, (Ho))
(So
E, + e, (F. (S (So,(X
+ + [So, (XWo), XWo)) (F.
+
San O. U, (XWo) as (XWo)
( S, E. S C, E XW r) 0, (XW (W S
S, E, S. + S., EAST = E. ST + (E)),.. (Ei)
(35)
(f): [(((o(F (So, (Xo,(XW))),k and E (X (So((F,1))oo) evaluate to by conditioning on Wo first and rewriting the expectation based on this conditioning. The terms within expectation independent when conditioned on Wo. and hence it is
(F- [W)] E Ii,,Wo [(So, [W]] by taking h Wo going to (XWo)) [Wo] = 0.
Wo E
infinity first. Here, I
We get the co-variance matrix for all pairs of nodes Eg = SE.ST and E; = -SE,-S" + E, from 34 and (35).
Skip-a: Co-variance between nodes. Let u and u be two nodes and the co-variance between u and v in F1 and F, are derived below.
((1)). (F1),t) = ((G)).. (G1)..)
h (1 (l-aa)So,HHL, + ao, (Ho)) ((1 So, (Ho) + ao, (Ho)))
Co
h
k=1
C (1[([aa)Ss]l]
a) (H)) ao (Ho)) ((1 ((1-a)So,(th) + ao, (Ho))
(1 a) (So, (H,) m/ Soo, [z)
co
(1 - a)a (So, (Ho) mi (a. (Ho)) (So,,HH)) (o.(H)))
a=E [a, (Q)) ub (a. (Hu))
(1 a S ST (1 a)a Smm. En v
+ En
+EE)
+ a²
Eg
=(E) (E)),..
u.
uv
(36)
21

---

Under review as a conference paper at ICLR 2023
(FF). (Fi)ol) ((Gi),. (G.)).
Co ((1 + ((1 -F))((F))))) 00, (Ho))
A = co [[(1
00, (1- 00, (Ha))
co (1 - a [SS (So(F:
+ a ((ax((H)))) (Ho)) muk (ax (H)))))) (Ho))
+ (1 a)a (So uk (Ho)) + (o, (So (F; (Fi-
@ (1 a) 1S + a² Eo = (Ei)uv
(37)
(g): same argument as (f) in derivation of E, in Skip-PC.
We get the co-variance matrix for all pairs of nodes Σ₁ (1 -1-00 ( + a(1
a) (Eo + EOST) + E and Σ, = (1 - SE + a 2 from (36) and 37
A.4 THEOREM 3
POPULATION NTK θ FOR SKIP-PC
NTK at depth d, PC for Skip-PC with linear activations is
d+1
+ (d)
+SS") o (SST) @d+1-N
d+1
Σ
@ (SS") @d+1-k
(SS od+2-k
(38)
k=1
In 38
I is NTK without skip connection and II is computed for Srow and S sym follows.
Computing II for population NTK (d) for S Saymi for nodes and j.
d+1
d+1
S Say ST sym
)1) 0d+2-k
(Viiiyy (1 + )eyr²)) d+2-k
Vnsii (1 85gr22 - (TTT (1 + 6eg7?) d+1
Mitjy (1 + 8zGm2)
T (1 + 8eyr2)
d-300
(39)
Miy (1 + 62)r2)
It converges to (39 as d + ao since
V V
(1+ 0 < 1 according to our setup. Therefore,
using (39 and we get the population NTK PC. for Skip-PC at - oc,
(00)
/ + 8err²)
(00) PC.sym
Menyy (1 + deyr2)
hence deriving Theorem 3
Similarly, computing II for Srow without assumption on 7, and j in class
d+1
S SSow row
@d+2-k
(1+r)**++1- (1-r)² [)) d+2-k
1=1
1 (1 (1+ A (1- d+1
= =(1+))**+(11ンング
1 (1+ x r1= 11)
22

---

Under review as a conference paper at ICLR 2023
(1+r)² X+ x (1-1)))²
d
(40)
For and j class 2,
Srow ST @d+2-k = (11 -)) + (1 (1=r)² 1 A (1 (1++++++++++0 +)+ d+1
d+
A+
row
1 - (1- (1 r)+))pp) pl)
1=1
(1-r) (1++)
d=
(41)
1- (
For i and j in different class,
-1 r2) (A+ + 11) 1- ((1 (A + RJ) d+1
Srow ST @d+2-k kow)
1- (2 (A+ 11)
(1-r)) (A + 14)
d=
(42)
1- (1)
Therefore, the population NTK θ (ec) and x
aroo with y assumption is obtained by substituting 1 2
= 0 in (40). (41 and 44
27(2+ + 5zgr²)
(oc) arrow
1- 27 (1 d:r
hence deriving Theorem
A.5 THEOREM
4 POPULATION NTK θ FOR SKIP-a
We expand ES and Σ of Skip-a first to derive the population NTK.
Σ₁ (1- (ll-a)"s5 SS a (1 a) S*) II
Σ = (1 - a)² SEk ST In
k-
= (1-a) 2k S + a (1)-))
2k sh-1 (S+)" Sh-1"
+ +a²
Σ
(1-a) 21 s's (43)
1=0
Exact NTK of depth d for Skip-a is expanded using the above follows.
d+1 1
(d)
Σ ① (SST)
1d+1-k
k=
d+1
(1 a) 2h SkggT c (SST) 3dt1-k+
(1 a) 2 2h-1 (S+ Sh-1" (SST) Od+I-k
a)
11
k-1
24 S'S'T (SST)
Od+l-k
(44)
111
23

---

Under review as a conference paper at ICLR 2023
We compute I, II and III of (44) for population NTK 6 (00) using Saym focusing on d oo.
(iita (1 + 8,gT2) (1 - a)- -2) d+1
bg = (1 10-00 aa) (1-aa 2(0+1)
1
1 v J (1 + 6egr (1 a)-
2
1 - g (1 + 6eyr2) r- (1 a) -2 d+1
2((+1)
d= 0
(45)
/ (1 + 8igr2) 2 r (1 a) 2
d+1
11 (1 (K)
2k-1 25 o (Say S )lmm
@d+1-k
S sym -Syy
d-1
11y = 20
Σ
(1 - a) 2 1 (vTSTT) d+h (1 + 0igr ( d +
k=1
(1= 2
(v d+k (1 + ) (1572) ,2 15a5 653
1+1
T (1 - a)) 2d+1 1 + ( ((TT)T))
(1 -a) -2 (1 + 819121
= =2a
1 + (v (
-1 (1-a) -2 (1 + )egr2)
8. (T (1 - (1)))) 2d11 1 + ((v ((vTTT))
(r (1 - a1)))) -2 (1
)1rr2)
1+p
d d=200 (46)
1+ (vT:Th))
(r (1 a)) (1 + 0zrr2)
4+1 1-1
111 a
Σ
Σ (1 a)² S sym sym
StT
+ (S sym sTymm) @d+l-k
d+1
m = o2
Σ (1 ا)20 (1 + 21
+ (1++dggr) VTi
VT:TTT) d+1-k
k=
8zg
(1+ degr?) (TTT,) d+1-k
1 (1 a)²
1- (1 a)² 22²²2 y2
a) 2k
(1 a) a)2k 22
(1+ )igr2) / (TT d+1-A
1 1 o)3
5ūj
1 1 (1 a) 2 222
(v ( (1 + 8:g d+1
0² (..
1
8z
(1 - aa)² +
1 1 (1 a) p2
vi (1 + 8,yr2)
d+1
(1 - a) 2(d+1) 1- (VIVTTT (1 + )2)r2) (1 - -ax)
aa)-2) -2)
1 (1 - a)² 1- (VTTety (1 + degr2) (1 - (x)
x)- -2)
di (1 a) 2(d+1) ,((44]) /i (1 + 88yr2) (1 a) -2 x2 d+1
1 - a)²² 2 2
1 Viryy (1 + 61TT2)
(1 a)=
2 2
a² K
5zj
d=+00
(47)
J (1 + 8,
1 (1
1 (1 a)²²² ,2
Therefore the population NTK as d + is obtained by combining
45
46
and (47
(00)
a² T
1
8,3
a.sym
i5 1 j (1 + 0err2)
1 (1 - 0)²
+
1 (1
- 2)
72
24

---

Under review as a conference paper at ICLR 2023
proving Theorem
We now compute I, II and III for population NTK (000) using S For nodes i and j in class 1:
(A+ -a)) 222((11)) 1 1- (1+1) A (1 (1 d+1 (1 (1-a)) (1-a) -2(4+)
1 1 1 (1-1))
+
(1) (1 aa) 2
1- (1 x+ +2+ (1- (11)) d+1 r-(d+1) (1 aa) -a-- -((4+1)
2(A- - 1)) (1 (1--100 (1 2(d+1) ,t
1- (1 (1+r)² A + (1 - -n) 11) p- (1 a)-
(A + (1 - (0)0-aa)((t)1) a))(d+1), ,2(441) 1- (1++))* X + (1 -r}²11) 11) d+1 -2(d++)) (1 ax) -2(d+1)
1 (1 2 A + (1 -)²² 11) r r-2 (1 - -a) -2
aa-
d0000
0
(48)
Similarly for nodes i and j in class 2 and different classes by = 0 as d + co. Likewise, 1ly as d + co for any i and j. This is similar to S sym.
For i and j in class 1,
d+1
2
Σ
Σ
(1 - a)² 20 Sow S/T you
Stow
3 (SoowSTow)
@d+l-k
I[ = a²
Σ
d+1
k-1
Σ
(1 a)² 21 ((> + 11) (1+ (A - 11) 2r))
( (1+ x - ((11+))) (1-r))²1 11)
d+1-k
k=
1=0
d+1
1- (1 2k
1- a1 2# 22
1 1- -1-100 )² pk
a²
Σ
(A+ 11)
+ +(1 m)
x
1 1- a))
1 1- (1 - a) 2 p2
1- (1 - a)² 2 r
1=1
d+1-k
(1+r)²x x (1 - (1-r)²² 11
2
A+
X+ 1
A- μ
Σ
d+11
(1 (1+r)² 2 x (1-r)² 1)
d+1-k
(1 a)²
1- (1 - (1))²² 22
1 1 (1 a}²r)
a²
A P
Σ (1 o)2h 2k (1++)) x+ (1 - r)² 1n)
d+1
d+l-
1 (1 (1)))
h=1
2
X+
Σ (1- a) 2k 2k ((++))> x=0))2=(12) (1-r)² x=(=)))>=1>)>>>>>>>>>>) 11)
d+1
d+I-k
1 (1 ?3²r 7
a²
A- P
Σ (1 a)) 26 * (1+ + (1 (1-r2²/) 11)
d+1
d+l-k
1 (1 a)²r
k=1
1 (1 X + (1 (1--)²/ p)) d+1
X μ
A+ /
A P
0²
1 (1 a)² 2 +
1- (1
a)² 22
1 (1 - -)²r
1- (1++)) 2 X + (1 (1-r)² 14)
11 (1-))² d+l
(1 -((41))
(1-a)2(d+1) 1-
A ++M P
a²
1- (1 a)² 3
1
(1 (1+))) A + (1 (1-1)² 11) (1 - (1-a)- a)- -2
(1++)) ( x d+1
((1 - aa)r)
-2(d11))) 2(d+1)
a²
A + 1
((1 - (1-
1 (1 a)² 72
1 1- (1+r)) x (1 (1-r)² 11) a)))) 22
25

---

Under review as a conference paper at ICLR 2023
x+ (1 d+l (11-a)²))
-(d+1)
(1-a))+) (dt1) 1-
a²
1 (1 - a)² -a))) (11
1
- (1 r)+ x (1 (1-))² R) (1-a)²
d= a
A+
A+ 4 1- (1 a1
A-P
1
+
(1-
(1 a)
1 (1+ (1 -)²
(49)
Similarly for and j in class 2,
( 11 a1)
1116 d= a²
A ++# μ
X+ μ
A- p
1
+
1- - xx) p2
(1 a)²
1 (11 r) x + (1 + r) 11
(50)
For and j in different classes,
my 20 a² ( x+ a)² ())
X+ R
(51)
1 - (1 - a))
11
((c) and (51) the population NTK or as d + 00 is,
Thus, applying assumption to 49
50
(ol00)
2ya²
1
1j
27 + dzyr2)
1 (1-
a)²
1 1 (1 a) p2
hence proving Theorem
4
B EMPIRICAL ANALYSIS
B. EXPERIMENTAL DETAILS OF FIGURE
We use the code for GCN without skip connections from githubl Kipf & Welling 2017) and skip connection from github2/Chen et al. 2020). The following hyperparameters are used for GCN without skip connections: learning rate 0.01, weight decay is 5e 4, hidden layer width is 64 and epochs is 500, 1500, 2000 for depths 2, 4, respectively, For the skip connections, we used GCNII model, same parameters as vanilla GCN with = 0.1. The performance is averaged over 5 runs.
B.2 COMPARISON OF GCN AND NTK
Although theoretically clear that the infinite width assumption should not affect the observa- tions made on performance of GCN with Saym and Srow in Figure [1, we illustrate the same using graph NTK. Figure shows that the observation is seen in graph NTK as well, thus supporting our theoretical argument.
Accuracy 06
GCN Sco
GCN
Depth
Figure 5: Comparison the accuracy of a trained finite width GCN and the corresponding NTK.
26

---

Under review as a conference paper at ICLR 2023
B.3 NUMERICAL VALIDATION FOR DC-SBM FOR VANILLA GCN AND SKIP-Q
Experimental Details. For the experiments, we fix the size of the sampled graphs to n = 1000, p 0.8 and q 0.1 for homophily DC-SBM, p 0.1 and q 0.8 for heterophily DC-SBM and p = for core-periphery DC-SBM. π is sampled uniformly [0, 1] for homophily and heterophily, and π. Un., 1)vi E core and x, Unif(O, 0.5) E periphery for core- periphery DC-SBM.
Illustration of impact of depth in Vanilla GCN using Homophity DC-SBM. We show the impact of depth in Vanilla GCN using homophily DC-SBM in Figure 6 The DC-SBM is shown in the first column and columns and show the exact NTK for depth=1 and 8 for symmetric and row normal- ization, respectively. The plots clearly illustrate the complete loss of class information in symmetric normalization with depth (column 2). While the prevalence of block difference has decresed row normalization over depth (column 3), the block/community structure is still retained. Thus showing the strong representation power of S
DC-SBM
(
[d]
1e.3
Spm
1.5
1.0
Aug. ii--laass & out-of-class
block difference 6im
1e-2
depth-1
depth-1
1e22
0.2
Syy
Scal
depth-8
depth-8
Depth
Figure 6: Numerical validation of Theorem using DC-SBM shown in the first plot of column Columns 2 and 3 illustrate the exact NTKs of depth=1 and for Skym and Srows respectively. Second plot in column 1 shows the average gap between in-class and out-of-class blocks from theory.
Illustration Sew and Sadj in Vanilla GCN using Homophily DC-SBM. We extend the exper- iments on numerical validation for random graphs using vanilla GCN described in Section 3.2 to column normalized adjacency Scol and unnormalized adjacency Sadj here. We use the same setup described in Section 3.2 and Figure illustrates the results. We observe that even for depth 1 both the convolutions are influenced by the degree correction and there no class information in the kernels for higher depth. Thus, this validates the theoretical result in Theorem 2
1e-3
1e-6 6
7.5
88
5.0
2
2.5
depth=1
depth=8
depth=8
depth=8
Figure 7: Numerical validation of DC-SBM for Vanilla GCN. The first two heatmaps show the exact
(d) for column normalized adjacency convolution Scot and the other two for unnormalized adjacency Sadj for depths d = and 8.
NTK (d)
Illustration of impact of depth in Skip-PC and Skip-a using Homophily DC-SBM. We present complementary result Section 4.3 here. We use the same setting described in Section 4.3 and
27

---

Under review as a conference paper at ICLR 2023
plot the exact NTKs of depths 1 and 8 for symmetric and normalization. Figure shows the results for Skip-PC and we observe that the gap between in-class and out-of-class blocks decreases for both Srow and S Sym with depth, but the class information is still retained for larger depth and the gap doesn't t vanish. Between Srow and S Syy. the heatmaps show that Srow retains the block structure better than S Sym and devoid of the influence of the degree corrections.
+ (d)
O /oW
O (
O
sym
1e-2
Sym
row
1e-2
1.0
Skip-PC
0.5
depth=1
depth=1
8
depth=8
Figure 8: Numerical validation of DC-SBM for Skip-PC showing the exact NTKs ( for Saym and Srow for depths 1 and 8.
In the of Skip-a, we are derived from the experiment. Although we consider XX" I, for Skip-a which fundamentally relies on the feature information interpolate, the results are still meaningful and demonstrate the theoretical findings.
0.1 obtain the result illustrated in Figure D Similar conclusions
(d)
(d) /OW
(d) sym
( row
sym
1e:3
1e-4
Skip-x
depth=1
depth=1
depth=8
depth=8
(d) Figure 9: Numerical validation of DC-SBM for Skip-a showing the exact NTKs (d)) for S Sym and Srow for depths and 8.
Numerical Validation of Core-Periphery DC-SBM. In this section, we validate the two scenar- ios discussed in Section 5 core-periphery without community structure and core-periphery with community structure. For the firsr case, we consider vore-periphery DC-SBM with n/4 nodes as and the rest periphery as shown in the first heatmap of Figure TO We plot the exact NTKs of depth 2 for symmetric and row normalization using Vanilla GCN as shown in the second and third heatmaps of Figure [0] This clearly demonstrates the theoretical result presented Corol- lary 4 where the symmetric normalization exhibits the graph structure and the row normalization is a constant kernel.
DC-SBM
!21
(2)
Core-Peri phery
-2
1
Figure 10: Numerical validation of Core-Periphery DC-SBM showing the exact NTKs (d) for S. Saym and S for depth 2.
28

---

Under review as a conference paper at ICLR 2023
In the second setting, consider two communities of equal size n/2 with core- core-periphery in each, and the link probabilities between cores the communities is higher than core- pere-perph periphery-peripher of the two communities as shown in the first heatmap of Figure [T] The exact NTKs of symmetric and row normalization are illustrated in the second and third heatmaps of Figure where see that row normalization retains the community structure again.
DC-SBM
!?!
(2)
sym
row
1e-3
Core-Periphery in community
Figure 11: Numerical validation of Core-Periphery DC-SBM with community structure showing the exact NTKs @ (d)) for Ssym and Srow for depth 2.
B.4 EXPERIMENTS ON REAL DATASET: CORA
Orthonormal Feature XX" I, Assumption. In this section, present additional experiments on Cora. Since our theory assumed orthonormal features XX" I,, we validate experimentally in similar setup described in Section 6 Figure T2 shows the result for Saym and Srow for depth and 8, The conclusions derived from real setting hold here as well and shows Srow preserves the class information better than S sgmm
S sym
Srow
sym
0.3
0.1
depth=1
depth=1
depth=8
depth=8
Figure 12: Evaluation on Cora with XXT
In for S Seym and Srow for depths 1 and 8.
ReLU GCN. We present the result for ReLU GCN in this section. Figure 13 shows the result where the conclusions derived in Section 6 holds very well. Additionally, we plot the average in-class of vanilla GCN (line plots in first we observe that the average in-class and out-of-class block difference degrades with depth for each class in Cora, showing the negative impact of depth which aligns well with the theoretical result.
and out-of-class block difference in the
of Figure [3),
Avg. In-class out-of-class block diff.
per depth
@
0 V111
(
FCM
16-2
Vanilla GCN
1.0
5ED8003
3.5
depth-8
depth-8
Skip-PC PC
Skipa
depth=8
depth=8
depth=8
depth=8
Figure 13: Evaluation on Cora dataset. Heatmaps show results of vanilla GCN and the decrease in class separability with depth for S sym and Syow- Last two show NTKs of Skip-PC where min and max threshold of 30 and 70 percentile is set for better visualization. Skip-a results Appendix.
29

---

Under review as a conference paper at ICLR 2023
Another experimental study is understand how easy it is to learn the classes that showed good in-class and out-of-class gap preservation from the above experiment. The line plot in Figure 13 shows class C2 and C5 are well represented by both Ssyn and Srow- To study how well this holds in the trained GCN, we considered depth vanilla GCN with ReLU activations and used the same hyperparameters mentioned in Section B.I The results are shown in Figure 14 where we observe that C2 and C5 are well learnt. On the other hand, other classes that showed small gap are also well learnt by the trained GCN. This needs further investigation as has to do with the data split and some classes are poorly represented in the training data, for instance C6. Thus, we leave it for further analysis.
Corn
Figure 14: Class wise performance of trained GCN of depth 4.
Linear GCN. We present the result for linear GCN with the same setup as described in Section 6 to check the goodness our theory. The results are illustrated in Figure [5] where we observe that the theory holds very well for linear GCN than ReLU GCN. The class information is better preserved in Srow than S sym especially for higher depth in the case of both GCN with and without skip connections. All the conclusions derived in the main section hold here well.
(d)
165
(/4
Vanilia GCN
0.04
0.02
depth=1
depth=1
depth=8 8
depth=8
162
Skip-PC
8.01
5400-
0.10
0.02
0.01
depth-8
depth-8
depth-8
depth-8
Figure 15: Evaluation on Cora using linear GCN. First row shows the results for vanilla GCN for depths and 8. Second row shows the result for Skip-PC and Skip-a for depth 8
B.5 EXPERIMENTS REAL DATASET: CITESEER
e SN17
e
G
@ rOW
1ea
symm
Vanilla GCN
8.5
0.10
0.01
0.05
depth=1
depth=1
depth= B
depth=8
0.20
Skip-PC
000-0
0.50
0.10
0.25
0.05
depth=8
depth=8
depth
depth=8
Figure 16: Evaluation on Citeseer dataset using linear GCN. First row shows the results for vanilla GCN for depths and 8. Second row shows the result Skip-PC and Skip-a for depth 8.
30

---

Under review as a conference paper at ICLR 2023
In this section, validate our theoretical findings Citeseer without much of the assumptions. We consider multi-class node classification (K 6) using GCN with linear activations and relax the orthonormal feature condition, so XX" # In- The NTKs for vanilla GCN, GCN with Skip-PC and Skip-a for depths d = 1, 1.2. 4, 8, 16 are computed and Figure [6 illustrates the results. All the observations made in Section [ hold here as well and clear blocks emerge for Srow making it the preferable choice as suggested in the theory.
31


Reviews:
[{"review_id": "uczsZ57fu6F", "reviewer": "Reviewer_CyLz", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 1, "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": "", "summary_of_the_paper": "I am not in good position to review", "summary_of_the_review": "I am not in good position to review", "strength_and_weaknesses": "I am not in good position to review", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "qK5wDU3sBC7", "reviewer": "Reviewer_aSCc", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_paper": "This paper attempted to explain the superiority of row-normalized adjacency matrices as the graph convolution operator for node classification in GNNs from the viewpoint of graph neural tangent kernels (GNTK). This paper derived GNTKs for GNNs with finite and infinite layers (and with an infinite number of units) for various adjacency matrices when the underlying graph is a populated Degree-corrected SBM (DC-SBM), and the input matrix is orthogonal. By comparing the GNTKs, this paper showed that the row-normalized adjacency matrix is more capable of identifying nodes than the other design choices (symmetrized, raw, and column-normalized adjacency matrices). In addition, this paper considered GNTK for GNNs with initial residuals and showed that GNTK could identify nodes even with an infinite number of layers, provably avoiding over-smoothing.", "summary_of_the_review": "Although the choice of the adjacency matrix is one of the design choices, the significance of the research question is questionable, considering the line of previous studies. Also, unless I missed it, the reason for making that assumption about the theoretical analysis is not discussed qualitatively or experimentally, and its validity is questionable.\n", "strength_and_weaknesses": "Strengths\n- Few studies have investigated the impact of the design choice of adjacency matrices as a graph convolution operator. \n\nWeakness\n- I have a question about the significance of the research question that this paper addressed (see Novelty section). \n- The theoretical analysis needs to discuss the validity of the assumptions more (see Quality section).\n- The interpretation of the results of the theoretical analysis is questionable\n- It is desirable to clarify the relationship between the theoretical analysis and the numerical experiments more.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "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": {}}, {"review_id": "aaSwOsZ7ZS1", "reviewer": "Reviewer_mpKm", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "The paper investigates the effects of different normalizations of the adjacency matrix as the convolution operator in graph neural networks. In particular, they present a theoretical investigation of GNNs in the Neural Tangent Kernel (NTK) limit (very wide limit where training the GNN is equivalent to kernel regression on the NTK – without the need to optimize hyperparameters). They study the effects of four different convolution operators with different normalizations on SBMs, and show that some normalizations (row norm) preserve the ‘block’ structure better than others even at (relatively) large depths of 5 or more. They show empirically that row normalization is the most likely to preserve this structure, while other operators diffuse information over the graph as the network gets deeper. The authors also investigate two types of skip connections and show theoretically that they retain the structural information of the SBM even at infinite width.", "summary_of_the_review": "The paper presents an interesting study on the expressive power of GNNs. It presents theoretical results (under certain orthonormality of features conditions), but shows that some of the results hold empirically in a more general case.\nGraph NTKs have been introduced before…the novelty of this work is in the study of different normalizations of the convolution operator. Overall, while I have some questions on the generality of their results to other random graph models (if the results are general, this would strengthen their results), I believe the results are informative and interesting, and would recommend for publication, especially with additional discussion and testing for generality. ", "strength_and_weaknesses": "Strength: Results are clear, novel, and interesting, the math seems correct, and the paper brings a new perspectives on GNNs in the NTK limit.\n\nComments:\nThe results, although compelling, are restricted to one example, i.e., preserving class structure in one model of graphs (DC SBMs). I would be interested in seeing if this holds true more generally for other models of random graphs. For instance if one considered a graph with a few core nodes and some peripheral structure, is row normalization the best choice to preserve such ‘importance’ structure here as well (where one could look at the difference between core-to-core and core-to-periphery as a metric) – this should generally hold I think, since diffusion operators capture notions of ‘importance’? Classes here could be defined as communities analogous to the authors’ suggestion, but the degree distribution within each class is bimodal.\n How about graphs with many triangles, versus graphs that are locally tree-like? Does the analysis extend just as easily to signed graphs (positive and negative weights)? Even if not, a discussion on assumptions of graph structure considered here would be very useful. \nA question of particular interest to me (which may be beyond the scope of this paper), is if there exists a normalization (perhaps one of the four proposed) that best preserves the ‘topological’ structure of the graph, i.e., holes in graph, in addition to the class structure. \n\nCould one define a metric for ‘distance’ between graphs. One might define two graphs to be ‘structurally’ similar if the have equivalent ‘mixing’ between classes after d layers. A GNN with improved expressive power should be better for defining better distance metrics, I think.\n\nWhat is the conclusion from the section on skip connections? Is one type of skip connection supposed to work better with row norm, and another with sym? This was not clear to me. Panels on second row of Fig 4 (comparison between skip-PC and skip-alpha) look very similar to me. \n", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "KapBWJFjte", "reviewer": "Reviewer_nvrd", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_paper": "This paper defines a graph neural tangent kernel (NTK) in a semi-supervised node classification setting. Under the degree-corrected stochastic block model (SBM), it then uses the graph NTK to explain, theoretically and empirically, why (i) row normalization performs better than symmetric normalization; (ii) with row normalization, performance degrades more slowly with the network depth; and (iii) skip connections improve performance for both types of normalization.", "summary_of_the_review": "The problem addressed by the paper---understanding the effect of design choices such row/symmetric normalization, depth, and residual connections---is timely and important. However, the motivation for the proposed approach is ill-defined, the modeling assumptions restrict the applicability of the analysis, and the numerical experiments are limited.", "strength_and_weaknesses": "Strengths:\n\n- The problem addressed by the paper---understanding the effect of design choices such row/symmetric normalization, depth, and residual connections---is timely and important.\n- The empirical results in Figure 3 (left) are convincing in showing the effect of skip connections on class separability in node classification problems.\n\nWeaknesses:\n\n- The motivation of the paper is somewhat ill-defined. The motivation for analyzing the effect of depth comes from the observation, in Figure 1, that the performance of GCNs with symmetrically normalized adjacency matrices degrades faster with depth than that of GCNs with row normalized adjacency matrices. However, if the best accuracies in this figure are achieved for 2 layers, and the difference between symmetric and row normalization in the 2-layer case is small, why are we concerned with what happens for a larger (or even infinite) number of layers?\n- The modeling assumptions restrict the applicability of the analysis, as it is likely that the SBM model used to conduct the NTK analysis and the specific task (community detection/separability of communities) are biased towards the row normalized adjacency matrix (also known as the random walk matrix). It is well known that community detection methods based on random walks (e.g., node embeddings such as DeepWalk; spectral methods based on the non-backtracking operator) fare better than methods based on symmetric aggregations. Moreover, not every node classification problem can be modeled as detecting communities, especially when considering heterophilous graphs. This is for instance suggested by [r1] below, where it is noted that the row-normalized adjacency is more limited in the amount of topological information that it carries. \n- Although the result in Theorem 2 agrees with the numerical results, i.e., it explains why the row normalized adjacency does better than the symmetrically normalized adjacency in practice, the result itself gives no intuition as to why that is the case, and an interpretation is not given by the authors.\n- Although the NTK analysis is only accurate in the infinite width limit, the paper uses it to justify behaviors observed in the finite width limit. The justification for doing so is that the infinite width of the GCN does not affect the graph convolutions. However, infinite width certainly affects performance, as it corresponds to an overparameterized regime.\n- The numerical experiments are limited. Specifically, they are restricted to class separability on SBMs and node classification on citation networks. Neither of these problems are adequate choices to analyze the effect of GCN depth, as both are relatively simple, consensus-like problems in which shallow and linear models have been shown to achieve very good performance. Additionally, the classification accuracy, which is the evaluation metric of interest for Cora, is not reported for this dataset.\n\nMinor:\n\n- The **Remark on Assumption 1**, particularly that \"the linearized GCN performance is at par with the non-linear models with much reduced complexity\", is misleading. This may be true in consensus-like problems like Cora and Citeseer, but it is not the case in problems where the relevant information lies in high graph frequencies. See, e.g., Fig. 3c in [r2].\n- It is not \"conventional\" wisdom that GCNs \"exhibit improvement in performance as depth increases\" (third paragraph of the introduction). Overly increasing the depth may lead to overfitting.\n\n[r1] Jeong, Sowon, and Claire Donnat. \"Tuning the Geometry of Graph Neural Networks.\" arXiv preprint arXiv:2207.05887 (2022).\n[r2] Ruiz, Luana, Luiz FO Chamon, and Alejandro Ribeiro. \"Transferability Properties of Graph Neural Networks.\" arXiv preprint arXiv:2112.04629 (2021).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "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": {}}, {"review_id": "7nlGe7a7DIx", "reviewer": "Reviewer_vkDP", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_paper": "This paper utilizes the graph neural tangent kernel to theoretically prove the superiority of row normalization in a semi-supervised node classification setting. It is proven that row normalization can preserve the class structure better, and work better at reducing over-smoothing, especially when combined with skip connections,", "summary_of_the_review": "By theoretically proving that row normalization and skip connection work better in semi-supervised node classification tasks, this paper serves as a good suggestion for how to implement GCNs. However, it lacks a further discussion on what we can do differently from the current existing approaches.", "strength_and_weaknesses": "Strength:\nThis paper provides a theoretical analysis of why row normalization is better than symmetric normalization, which is absent from current research. Thus, it provides insight and potential research direction.\n\nWeakness:\n1. Graph neural tangent kernel is presented by others before.\n2. The observations are discovered previously by others empirically.\n3. The underlying reasons for the observations have been discussed or at least inferred somewhere else.\n4. No further proposal is made based on the proof.", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject