Analysis of Convolutions, Non-linearity and Depth in Graph Neural Networks using Neural Tangent Kernel
Authors: Mahalakshmi Sabanayagam
Pascal Esser
Debarghya Ghoshdastidar
Venue: Accepted by TMLR ()

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' in conjunction with a suitable choice for the network architecture, such as depth and activation functions. Therefore, understanding the influence of each of the design choice 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 as the most widely adopted one. However, some empirical studies show that row normalization of the adjacency matrix outperforms it in node classification. Despite the widespread use of GNNs, there is no rigorous theoretical study on the representation power of these convolutions, that could explain this behavior. Similarly, the empirical observation of the linear GNNs performance being on par with non-linear ReLU GNNs lacks rigorous theory.

In this work, we theoretically analyze the influence of different aspects of the GNN architecture using the Graph Neural Tangent Kernel in a semi-supervised node classification setting. Under the population Degree Corrected Stochastic Block Model, we prove that: (i) linear networks capture the class information as good as ReLU networks; (ii) row normalization preserves the underlying class structure better than other convolutions; (iii) performance degrades with network depth due to over-smoothing, but the loss in class information is the slowest in row normalization; (iv) 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 such as Cora and Citeseer.

Published in Transactions on Machine Learning Research (10/2023)
Analysis of Convolutions, Non-linearity and Depth in Graph Neural Networks using Neural Tangent Kernel
Mahalakshmi Sabanayagam
sabonaya@cit.bun bom.iittummdeee...........
School of Computation, Information and Technology Technical University of Munich
Pascal Esser
esserOeit furn
School of Computation, Information and Technology Technical University of Munich
Debarghya Ghoshdastidar
ghoshdas@cit. tum.
School of Computation, Information and Technology Technical University of Munich.
Reviewed on OpenReview: /ttps://openneee optp:///ppeeee...e.oo net/ forum? id- og
Abstract
The fundamental principle of Graph Neural Networks (GNNs) is exploit the structural information of the data by aggregating the neighboring nodes using 'graph convolution' in conjunction with suitable choice for the network architecture, such depth and ac- tivation functions. Therefore, understanding the infiuence of each of the design choice 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 as the most widely adopted one. However, some empirical studies show that row normalization of the adjacency matrix outperforms it in node classification. Despite the widespread use of GNNs, there is no rigorous theoretical study the representation power of these convo- lutions, that could explain this behavior. Similarly, the empirical observation of the lincar GNNs performance being on par with non-linear ReLU GNNs lacks rigorous theory.
In this work, we theoretically analyze the influence of different aspects of the GNN architec- ture using the Graph Newral Tangent Kernel in a semi-supervised node classification setting. Under the population Degree Corrected Stochastic Block Model, we prove that: (i) lincar networks capture the class information as good as ReLU networks; (ii) row normalization preserves the underlying class structure better than other convolutions; (iii) performance degrades with network depth due over-smoothing, but the loss in class information is the slowest in row normalization; (iv) skip connections retain the class information even at infinite depth, thereby eliminating over-smoothing. We finally validate our theoretical findings numerically and on real datascts such as Cora and Citeseer.
1 Introduction
With the advent of Graph Neural Networks (GNNs), there has been tremendous progress in the devel- opment of computationally efficient state-of-the-art methods in various graph based tasks, including drug discovery, community detection and recommendation systems (Wieder et al. 2020 Fortunato & Hric 2016 van den Berg et al. 2017]. Many of these problems depend on the structural information of the data, repre- sented by the graph, along with the features of the nodes. Because GNNs exploit this topological information encoded in the graph, can learn better representation of the nodes or the entire graph than traditional deep learning techniques, thereby achieving taate-of-tho-ars performances. In order to accomplish this, GNNs apply aggregation function to each node in graph that combines the features of the neighboring nodes,

---

Published in Transactions on Machine Learning Research (10/2023)
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 2017p or spatial approaches (Hamilton et al. 2017 Duvenaud et al. 2015 Xu et al. 2019
graph attention networks apply multi-hcad attention based aggregation (Velickovic et al.
2018 and graph recurrent networks employ complex compulational module (Scarselli et al. [008) Li el al.
2016). Of all the
aggregation policies, the spectral graph Laplacian based approach is most widely used in practice, specifically the one proposed by Kippf & Welling (2017) owing to its simplicity and empirical success. In this work, we focus on such graph Laplacian based aggregations in Graph Convolution Networks (GCNs), which we refer to as graph convolutions or diffusion operators.
Kipf& & Welling (2017) propose a GCN for node classification, a semi-suppervsed task, where the goal is to predict the label of a node using its feature and neighboring node information. They suggest symmetric normalization S Seym = D- AD- as the graph convolution, where A and D are the adjacency and degree matrix of the graph, respectively. Ever since its introduction, Saym remains the popular choice. However, subsequent works such Wann et al. (2018): Wang & Leskoved (2020); Ragesh et. al. (2021) explore row normalization Srow= = D-11 A and particularly, Wang et al. (2018) observes that Syow outperforms Saym for two-layered GCN empirically. Intrigued by this observation, and the fact that both S Sam and Srow are simply degree normalized adjacency matrices, we study the behavior over depth and observe that Srow performs better than Soym in general, as illustrated in Figure (Details of the experiment in Appendix C.1
Furthermore, another striking observation from Figure | is that the perfor- mance of GCN without skip connections decreases considerably with depth for both Saym and Srow- This contradicts the conventional wisdom about standard neural networks which exhibit improvement in the performance as depth increases. Several works (Kipf & Welling, 2017 Chen et al.)
Jecusac of class production (9)
2018b; Wu et al. 2019) observe this behavior empirically and attribute it to the over-smoothing effect from the repeated application of the diffusion operator, resulting in averaging out of the feature information to a degree where it becomes uninformative (Li et al.) 2018 Oono & Suzuki 2019 Esser
2021 As solution to this problem, Chen et al. (2020) and Kipf & et al.
of
Figure 1: GCN performance on Cora dataset.
Welling [217)) propose different forms of skip connections that overcome the smoothing effect and thus outperform the vanilla GCN. Extending it to the comparison of graph convolutions, Figure [ shows Srow is preferable to Seym over depth in general for diffcrent GCNs. Naturally, we ask: what characteristics Srow enable better representation learning than Saym in GCNs? Another cont rastingg behavior to the standard deep networks is that linear GCNs perform on par or even better than non-linear GCNs as demonstrated in Wu et al., (2019). While standard neural networks with non-linear activations are proved to be universal function approximator, hence essential component in a network, this behavior of GCNs is surprising.
Rigorous theoretical analysis is particularly challenging in GCNs compared to the standard neural networks because of the added complexity due to the graph convolution. Adding skip connections and non-linearily further increase the complexity of the analysis. To overcome these difficulties, we consider GCN in infinite width limit wherein the Neurol Tangent Kernel (NTK) captures the network characteristics very well (Jacot) et al.) 2018). The infinite width assumption is not restrictive for our analysis as the NTK model shows same general trends as trained GCN. Moreover, NTK enables the analysis to be parameter-free and thus eliminate additional complexity induced, for example, by optimization. Through the lens of NTK, we study the impact of different graph convolutions under a random graph model: Degree Corrected Stochastic Block Model (DC-SBM) (Kareer & Newman 2011). 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 a formal approach to analyze GCNs and, specifically, the effect of activations, the representation power of different graph convolutions, the influence of depth and the role of skip connections. This is significant step toward understanding GCNs as it enables more informed work design choices like the convolution, depth and activalions, as well as development of competitive methods based on grounded theoretical reasoning rather than heuristics.
2

---

Published in Transactions on Machine Learning Research (10/2023)
Contributions. We provide rigorous theoretical analysis of the discussed empirical observations in GCN under DC-SBM distribution using graph NTK, leading to the following contributions.
(1) In Sections 3 we present the NTK for GCN in infinite width limit in the node classification setting and our general framework of analysis, respectively.
(ii) In Section 4 we derive the NTK under DC-SBM and show that linear GCNs capture the class structure similar to ReLU GCN (or slightly better than ReLU) and, hence, linear GCN performs as good as ReLU GCNs. For convenience,
restrict the subsequent analysis to linear GCNs.
(iii) In Section 5 we show that for both homophilic and heterophilic graphs, row normalization preserves the class structure better, but is not useful in core-periphery models. We also derive that there is over-smoothing in vanilla GCN since the class separability decreases with depth.
(iv) In Section 6 we leverage the power of NTK to analyze different skip connections (Kipf & Welling, 2017 Chen al., 2020). We derive the corresponding NTKs and show that skip connections retain class information even at infinite depth along with mumerical validation.
Throughout the paper we illustrate the results numerically on planted models and validate the theoretical results on real dataset Cora in Section 7 and Citeseer in Appendix C.5] and conclude in Section g with the discussion on the impact of the results and related works. We provide all proofs, experimental details and more experiments in the appendix.
Notations. We represent matrix and vector by bold faced uppercase and lowercase letters, respectively, the matrix Hadamard (entry-wise) product by 3 and the scalar product by (---)- M denotes Hadamard product of matrix M with itself repeated k times. We use o(.) for derivative of function o(), [[] for expectation, and [d] {1, (I...
2 Neural Tangent Kernel for Graph Convolutional Network
Before going into detailed analysis of graph convolutions we provide brief background on Newral Tangent Kernel (NTK) and derive its formulation in the context of node level prediction using infinitely-wide GCNs. Jacol et al. 2018); Arora et al. (2019) Yang 2019) show that the behavior 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, Jacot et al. (2018) also shows that the change in the kernel during training decreases as the network width increases, and hence, asymptotically, one can represent an infinitely wide neural network by deterministic NTK, defined by the gradient of the network with respect to its parameters
K (or(W,x) x) OF(W,x)) >
O Oxx,x)
E W-
(1)
aw
aw
Here F(W,x) x) represents the output of the network at data point x parameterized by W and the expectation is with respect to W, where all the parameters of the network are randomly sampled from standard Gaussian distribution (00 1). 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 draw insightful conclusions. This trade-off worth considering as this allows the analysis of over-parameterized neural networks without having to consider hyper-parameter tuning and training.
Formal GCN Setup and Graph NTK. We present the formal setup of GCN and derive the corresponding NTK, using which we analyze different graph convolutions, skip connections and activations. Given a graph with n nodes and a set of node features {x,)/_ C RR,, we may assune without loss of generality that the set of observed labels {y:)m correspond to first m nodes. We consider classes, thus y; E {0, 1] and the goal is to predict the 1-m m unknown labels {y.)/==+1- We represent the observed labels of m nodes as Y E (0, 10 and the node features as X Rnxf with the assumption that entire X is available during training. We define S Rax to be the graph convolution operator using the adjacency matrix A and the
3

---

Published in Transactions on Machine Learning Research (10/2023)
degree matrix D. The GCN of depth d is given by
-
V Go So (.... (V So (SXW1) Wa) Wa+1
Fw =
(2)
where W = (W; E RA dd+1 is the set of learnable weight matrices with hg = and ha41 K, h, is the size of layer i [d] and o: o: RR the point-wise activation function where (xx) := for linear and (x)) max(0, 2) for ReLU activations. Note that linear (xx) is same Simplified GCN (Wu et al.) 2019). We initialize all the weights to be i..d standard Gaussian (0, 1) and optimize it using gradient descent. We derive the NTK for the GCN in infinite width sotting, that is, hı...., ha + co. While this sctup is similar to Kipf & Welling 2017), it is important to note that we consider linear output layer so that NTK remains constant during training (Liu et al. 2020) and a normalization /co/h, for layer to ensure that the input norm is approximately preserved and c₂ = E
(o())))) (similar to Du et al. (2019a)). The following (o.1(
theorem states the NTK between every pair of nodes, as n n matrix that can be computed at once.
Theorem (NTK for Vanilla GCN) For the vanilla GCN defined in [2) the NTK O at depth d is
Σ S ((....((s
(E
[* o Ex) ST BATISS .... Eu
O. ET)
(3)
d+1-k terms
Here Eg _axn is the co-variance between nodes of layer k, and is given by E₁ SXX Eg SE (F))) and Est1 = =1 1nxn.
with Eg =
E
(F)) Es =
E F.N.
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 is that NTK in our case is computed for all pairs of nodes in a graph as we focus on semi-supervised node classification, whereas Du et al. (2019b) considers supervised graph classification where input is many graphs and so the NTK is evaluated for all pairs of graphs. Moreover, the significant difference using the NTK analytically characterize the influence of convolutions, non-lincarity, depth and skip connections on the performance of GCN.
3 Theoretical Framework of our Analysis
In this section we discuss the general framework of analysis that enables in substantiating different empirical observations in GCNs. We use the derived NTK in Theorem ! for our analysis on various aspects
of the GCN architecture and consider four different graph convolutions as defined in Definition 1 with Assumption on the network.
Definition 1 Symmetric degree normalized S Szym == D AD- now normalized Srow = D D-'A. AA column
normalized Seat == AD-1 and unnormalized Sadj A convolutions.
Assumption 1 (GCN with orthonormal features) GCN in 2 is said to have orthonormal features if XX"" :- In, where I, the identity matria of size n.
Remark on Assumption I The orthonormal features assumption eliminates the influence the features and facilitates identification of the influence of different convolution operators clearly. Additionally, helps in quantifying the exact interplay between the graph structure and different activation functions in the network. Nevertheless, the analysis including the features can be done using Contertual Stochastic Block Model (Deshpande et al. 2018) resulting in similar theoretical conclusions detailed in Appendix B.9 Besides, the evaluation of our thcoretical results without this assumption on real datascts is in Scction and Appendix C.5 that. substantiale our findings.
While the NTK in gives a precise characterization of the infinitely wide GCN, we can not di- rectly draw conclusions about the convolution operators or activation functions without further assumptions the input graph. Therefore, consider planted random graph model described below.
4

---

Published in Transactions on Machine Learning Research (10/2023)
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 Ssym; S Srow: Seot and Sudj by allowing non-uniform degree distribution on the nodes. The model is defined as follows: Consider a set of n nodes divided into K latent classes (or communities), C, E [1, K]. The DC-SBM model generales a random graph with n nodes that has mutually independent edges with edge probabilities specified by the population adjacency matrix M = E [A] E R=** where
CF C if IEC+CC,
My
with the parameters p.g E [0, 1] governing the edge probabilities inside and outside classes, and the degree correction Ty E i0, [n] with Σ; ग; en for positive e that controls the graph sparsity. The constant should be [ since the expected number of edges in this DC-SBM is O (cn)² and is bounded by [n,n"] Note that we deviate from the original condition Σ; T. = K in Karrer & Newman (2011), to ensure that the analysis even holds for dense graphs. One can casily verify that the analysis holds for Σ, म; = K as TT) for ease of representation. DC-SBM allows us to model different graphs: Homophilic graphs: 0 S q < p S 1, Heterophilic graphs: 0 S P < q S 1 and Core-Periphery graphs: p- = q (no assumption on class structure) and π encodes core and periphery.
well. We denote π =
is evident that the NTK complex quantity and computing its expectation challenging given the dependency of terms from the degree normalization in S, its powers St and SST To simplify our analysis, we make the following assumption the DC-SBM,
Assumption 2 (Population DC-SBM) The graph has a weighted adjacency A = M.
Remark Assumption| Assuming A M is 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 empirically show that this analysis holds for random DC-SBM setting as well in Figure 5 Furthermore, this also implies addition of self loop with a probability
Analysis Framework. We analyze the observations of different GCNs by dcriving the population NTK for each model and compare the preservation of class information in the kernel. Note that the true class information in the graph is determined by the blocks of the underlying DC-SBM formally by p and q and independent of the degree correction π. Consequently, we define the class separability of the DC-SBM = 8-9 Hence, in order to capture the class information, the kernel should ideolly have block structure ptg that aligns with the one of the DC-SBM. Therefore, we measure the class separability of the kernel as the average difference between in-class and out-of-class blocks. The best case is indeed when the class separability of the kernel is proportional (due to scale invariance of the kernel) to p - and independent of π.
4 Linear Activation Captures Class Information as Good as ReLU Activation
While Kipf & Welling (207)) proposes ReLU GCNs, Wu et al. (2019) demonstrates that linear GCNs perform on par or even better than ReLU GCNs in wide range of real world datasets, seemingly going against the notion that non-linearity is essential in neural networks. To understand this behavior, we derive the population NTK under DC-SBM for linear and ReLU GCNs, and compare the class separability of the kernels (average in-class and out-of-class block difference). Since our objective is in comparing lincar and ReLU GCN, we consider homogeneous degree correction т, that is, V i, := c. In this case, population NTK for symmetric, row and column normalized adjacencies are equivalent, and unnormalized adjacency differ by a scaling that does not impact the block difference comparison. The following theorems state the population NTK for linear and ReLU GCNs of depth d for normalized adjacency S and K =22 The results hold for K > 2 as presented in Appendix B.3.5
Theorem 2 (Population NTK é for linear GCN) Let Assumption I and 2 hold, 1[] be indicator func- tion, K 2, == p-g. diz (-1) (-1)110,4C, and V i, ni == Then V i,j; population NTK for linear GCN of pto'
5

---

Published in Transactions on Machine Learning Research (10/2023)
Accuracy of closs prediction (9)
87
10
16
10-16-
10
Linesr GCN
BuLl GCN
RoE
0.1
0.5
BM
True class sepazability (r)
Depth of GCN
Figure 2: Linear good ReLU activation. Left: analytical plot of in-class and out-of-class block difference of the population NTK ((d) for graph of size n 1000, depths d = {1, 4, 8) and varying class scparability r of linear and ReLU GCNs (in log scale). Right: performance of trained linear and ReLU GCNs on Cora for d (2, 8,
depth d, (()) is lint
C lin
(d)
d d+1 (1 (1+ 2
Theorem (Population NTK θ for ReLU GCN) Let assumptions of Theorem hold and Ko(x)) == arccos (x)) + -i-
A := 1= and 4 ++ )n 1) Furthermore, D and A denote the numerator and denominator of D.. respectively.
1 (TT arccos (z)), Ki (x) == 4 (x
(1-=))(- Then i,j, the
population NTK for ReLU GCN of depth d, ( Ret. is computed using 3 with
(En)s 2 (1[8)) 1,2$ + 180 -1]A;) II
A
k'=1
&
(E&), = 2k-1n (kI (Ax)) 26:,==
A ; (Ex) = (No (1
Comparison of Linear and ReLU GCNs. The left of Figure 2 shows the analytic in-class and out- (d) c, C#c, of the population NTKs of linear and ReLU GCNs with input graph size = 1000 for different depths d and class scparability r. Given the class scparability is large enough, theoretically linear GCN preserves the class information as good or slightly better than the ReLU shown in Appendix B.& With depth, the difference
of-class block difference 3
(d)
GCN. Particularly for 1, the difference is O prevails showing the effect of over-smoothing is stronger in ReLU than linear GCN, however larger depth proves to be detrinental for GCN as discussed in later sections. As a validation, we train linear and ReLU GCNs of depths {2, 4, 8} on Cora dataset for both the popular convolutions Symm and Srow, and observe at par performance as shown in the right plot of Figure 2
5 Convolution Operator Syow Preserves Class Information
In order to analyze the representation power of different graph convolutions S, we derive the population NTKs under DC-SBM with non homogeneous degree correction л to distinguish the operators. We restrict our analysis to lincar GCNs for convenience. In the following thcorem, we state the population NTKs for graph convolutions Ssym; S Srow; Spat and Sadj for = with Assumplion and 2 The result exlends to
K > 2 (Appendix ).3.5).
Theorem 4 (Population NTKs 6 and its class separability Ç for the four graph convolutions S)
and hold, K and 2-g, 8ij [C, is chosen such that
Let Assumption

---

Published in Transactions on Machine Learning Research (10/2023)
Ei=1T k] en Ei=1 VT,1IC; k] -Vk and Eisy mi = k] y where and y are constants. Then V i,j, population NTKs θ sym: Orow: @cal and adj and class separability of the population NTKs (ld) (d) soal and Sach of depth d for S = Ssym: S and Sadj respectively, are,
y on
167 + 1)
(d) +
(d+ 1) (1 + desT 2d4)
(dd)
7 ,2222 n² n²(nn)
sym
1/
27
8y(d + 22d+2
(d)
(d + 1) (1 dey dig 22)
row
(en)²
Srow
(en)²
4(d + 2d+2
((d) col
= (d+ 1) (1 5.g 2
: Soal
(en)²
2
n
-411
2d
(2d+)
6 odd)
(d)
= (d + 1T
n22d2
1 = 11
Σ
21
p
2ut1
21
1=
2d
2d+1
(d (d+1)) 1)e2 24tt1-1 n 2d22
16: = -1]
21 221-1
21+1
Sady
(p 9) 2042
21
+11
1=0
Note that the three assumptions on π are only to express the kornel in a simplifiod, casy to comprehend format. It is derived without the assumptions on π in Appendix B.3 Furthermore, the numerical validation of our result in Section 5.2 is without both these assumptions.
Comparison of graph convolutions. The population NTKs (d) of depth d in Theorem 4 describes the information that the kernel has after d convolutions with S. To classify the nodes perfectly, the kernels should retain the class information of the nodes according to the underlying DC-SBM. That is, the average in-class and out-of-class block difference of the population NTKs (class separability of the kernel) is proportional to p p-o q and independent of π. On this basis, only Grow exhibits a block structure unaffected by the degree correction æ, and the average block difference is determined by y2 and d, making Srow preferable over S Saym: Sady and Scot- On the other hand, θ @xym: &cot and Gedj are inffuenced by the degree correction æ which obscures the class information especially with depth. Although + Daym and @not seem similar, the influence of π for G.o is (xT]) which is stronger compared to O(T.) for ② Daym: making it undesirable over Saym- As
result, the preference order from the theory is Orow θ agm O ① Dadj.
5.1 Impact of Depth in Vanilla GCN
Given that 2=g < 1, Theorem 4 shows that the difference between in-class and out-of-class blocks ptg decreases with depth monotonically which in turn leads to decrease in performance with depth, therefore
explaining the observation in Figurel I Corollary [ characterizes the impact of depth as d + 00.
Corollary 1 (Class separability of population NTK ((x)) as d o ) From Theorem 4 the class separability of population NTKs of the four different convolutions for fired n and as + oo converge to 0.
Corollary 1 presents the class separability of the population NTKs for fixed n and + xo for all the four convolutions Seym: Srow, Scol and Sudj, showing that the very deep GCN has zero class information. From this we also infer that, as - oo the population NTKs converge to a constant kernel, thus 0 average in-class and out-of-class block difference for all the convolutions. Therefore, deeper GCNs have zero class information for any choice of convolution operator S. The class separability of population kernels at depth d for Saym:
Srme and Swxt is O dr ((dr2)) since T and 7 are (n)). Therefore, it shows that the class separation decrenses at the exponential rate in d. This explains the performance degradation of GCN with depth. To further understand the impact of depth, we plot the average in-class and out-of-class block difference for homophilic and heterophilic graphs using the theoretically derived population NTK (d) for depths [1, 10) and n 1000 in well separated DC-SBM (row 2, column of Figure 3 and column 4 of Figure 4 respectively). It clearly
7

---

Published in Transactions on Machine Learning Research (10/2023)
DC-SBM
Hocoophity
6 qq
Avg. In-clex outr-r alt-aa.eloos dilfornne 6
Population
Depti
3
2
6.5 3
1.5
25 5,0
7:5
Figure 3: Numerical validation of Theorem using homophilic (g<p) DC-SBM (Row 1, Column 1). Row 1, Columns illustrate the exact NTKs of depth-2 and a graph of size n 1000 sampled from the DC-SBM for Srows Ssym: Scot and Swdj. Row 2 shows the respective analytic population NTKs from Theorem Row 2, column 1 shows the average gap between in-class and out-of-class blocks from theory,
that is, average of 6 c.=c, C:XC, convolutions.
(4)) This validates that Srow preserves class information better than other
shows the exponential degradation of class scparability with depth and the gap goes to 0 for large depths in all the four convolutions. Additionally, the gap in @,0 is the highest showing that the class information is better preserved, illustrating the strong representation power of Srow- Therefore, large depth is undesirable for all the concolutions in vanilla GCN and the theory suggests Srow the best choice for shallow GCN.
5.2 Numerical Validation for Random Graphs
Theorem 4 and Corollary I ssow that Srow has better representation power under Assumption and that is, for the linear GCN with orthonormal features and population DC-SBM. We validate this on homophilous and heterophilous random graphs of size = 1000 with equal sized classes generated from DC-SBM. Figure 3 illustrates the results for dcpth=2 the homophily case where the DC-SBM is presented in row and column 1. We plot the NTKs of all the convolution operators computed from the sampled graph and the population NTKs as per the theory as heatmaps in rows and 2, respectively. The heatmaps corresponding to the exact and the population NTKs clearly show that the class information for all the nodes is well preserved in Snow there is clear block strueture than the other convolutions in which each node is diffused unequally due to the degree correction. Among Seym: Scot and Sudj Seym retains the class structure better and Suw/ has very small values (scc the colorbar scalc) and no clear structure. Thus, exhibiting the theorctically derived preference order. We plot both the exact and the populations NTKs to show that the population NTKs are a good representative of the exact NTKs especially for large graphs. We show this by plotting the norm of relative kernel difference, (/0)) ((()) [|,, with graph size for d = 2 in Figure 4 shows the analogous result for heterophily DC-SBM. The experimental details are provided in the Appendix C.3
G(d)
5.3
S Sym Maybe Preferred Over Srow in Core Core-Periphery Networks (No 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 no communities (p = q). One such case is graphs with core- periphery structure where the graph has core nodes that are highly interconnected and periphery nodes that are sparsely connected to the core and other periphery nodes. Such a graph can be modeled using only the degree correction π such that n, < n, Vj E periphery, E core (similar to Jia & Benson (2019)). Extending Theorem we derive the following Corollary 2 and show that the convolution Soym contains the graph information while Srow constant kernel.
8

---

Published in Transactions on Machine Learning Research (10/2023)
DC-SBM
+
(2) Fou
(2) Apm
Avg. it- te-chos & out-af- sou--f--cao cecloos block difference for 6lll
1.2
Heturophiit p <
8
NTK
Sw
200 300
Depch
Namber modes
Figure 4: Numerical validation of Theorem using heterophilic (p q) DC-SBM (Column 1). Columns 2-3 illustrate the exact NTKs of depth=2 and graph of size n 1000 sampled from the DC-SBM for Srow and S Say. Column 4 shows the average gap between in-class and out-of-class blocks from theory.
Figure 5: Norm of the
relative kernel difference
@ 100 _ ||2 for depth d
@ 2 with graph size
Corollary 2 (Population NTKs ② for p === q) Let Assumption 1 and hold, K == 2 and p q. Further- more, π is chosen such that Eiecore Tē = X and Eispersphery oi μ. Then V and j, the population NTKs
① @sy and Orow of depth d for S Seym and Srow, respectively, are,
( sym ij
(d (d+1) 1d+
Tz V en
and (E()) rro
= (dd +d x x
(cn)²
From Corollary it is evident that the Saym has the graph information and hence could be preferred when there is no community structure. We validate it experimentally and discuss the results in Figure 18 of Appendix C.3 While Srow results in a constant kernel for core-periphery without community structure, it is important to note that when there exists community structure and each community has core- porepheriphery nodes, then Srow is still preferable over S S.gm as it simply a special case of homophilic networks. This is demonstrated in Figure 19 of Appendix C.3
6 Skip Connections Retain Class Information Even at Infinite Depth
Skip connection is 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, we consider the following two variants: Skip-PC (pre- convolution), where the skip added to the features before applying convolution (Kipf & Welling 2017): and Skip-o, which gives importance to the features by adding it to each layer without convolving with S (Chen al.) 2020). To facilitate skip connections, we need to enforce constant layer size, that is, h; h Therefore, transform the input layer using random matrix W to H, XW of size n where W9 (0, 1) and h is the hidden layer size. Let H, be the output of layer i.
Definition 2 (Skip-PC) In a Skip-PC (pre-coneolution) network, the transformed imput Hn is added to the hidden lagers before applying the graph convolution S, that is, Vi [d] = Tie (H + a, (Ho)) W., where (.). can be linear or ReLU.
Skip-PC definition deviates from Kipf & Welling 2017 in the fact that we skip to the input layer instead of the previous layer. The following defines the skip connection similar to Chen et al. (2020).
Definition 3 (Skip-a) Given an interpolation coefficient such that the transformed input H, and the hidden lager are interpolated linearly, that is, H. := T ((1 at) SH,11 oz, (Hn)) W, vi [d], where ax(.) be linear ReLU.
(0,1), a Skip-a network is defined

---

Published in Transactions on Machine Learning Research (10/2023)
6.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 - 00. Both the NTKs maintain the form presented in Theorem co-variance matrices. Let Eg Fo,().E.)) [o=(F)o,(F)"]
[ with the following changes to the
Corollary 3 (NTK for Skip-PC) The NTK for infinitely wide Skip-PC network is as presented in Theorem 7 where Eg is defined as in the theorem, but Es. is defined us
Σ. = XX",
= SEOS
and Σg = SEK-1S ST + E₁.
Corollary 4 (NTK for Skip-a) The NTK for infinitely wide Skip-o network is presented in Theo- rem where Ej is defined as in the theorem, but En is defined with Eo XX
Σ = a1 SE.S +a - a) (SE EoST) + a²2 Eo and Σx = (1 - a) ST + +a E'
a)²
6.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 4 and analyze the graph convolutions Saym and Srow under the same considerations detailed in Section Since, Sadj and Scot are theoretically worse and not popular in practice, we do not consider them for the skip connection analysis. The lincar orthonormal feature NTK, ( for depth d is same as o (d) follows,
Kn with changes to Σg as
Skip-PC: Σg Sk +SST
k-1
Skip-o: Σg = (1 - a)2* s* + a 2222211200 sh (tt (S+ Sh-1" + + Σ (1 - (1) s's + I
1=1
We derive the population NTK (d) and, for convenience, only state the result as - oo in the following theorems. Expressions for fixed d are presented in Appendices B.5 and B.6
Theorem (Class Seperability of Population NTK for Skip- (lo)) as + oc) Under the as-
sumptions of Theorem
16
8yy
SPC.sy
(1
and
(0o) SPC. = (en)2(1 r2)
(4)
Theorem (Class Seperability of Population NTK for Skip-a c!o0) d o0 Under the as-
sumplions of Theorem
4
16
(1_1²) and (00) Sa,row
8ya²
((0)) Sa.sym (on)m2
(5)
1 1 (1 a1) a)²
(en)2 (1- ax)) (1-(1)))1)
1 -
Theorems and f present the class separability of population NTKs of S and Srow for Skip-PC and in above theorems is to simplify the results.
Skip-a, respectively. Similar to Theorem A assumptions Note that Srow is better than Saym in the case of skip connections well due to the independence on π and the underlying block structures are well preserved in Srow- The theorems show that the class separation in the kernel is not zero even at infinite depth for both Skip-PC and Skip-a. In fact, in the case of large n and d 00, it is O (n)). Furthermore, to understand the role of skip connections, plot in Figure 0 the gap between in-class and out-of-class blocks at infinite depth for different values of true class separability r and small and large graph setting, for vanilla linear GCN, Skip-PC and Skip-a using Corollary [ Theorems
for Skip-PC and Skip-a, respectively, since 7 and 7 are and O [11-(1-)))12)
a²
G respectively. The plot clearly shows that the block difference away from for both the skip connections in both the small and large cases given a reasonable true separation r, wheras the block difference vanilla GCN is zero for small n and large n cases. Thus this analytical plot shows that the class information is retained in ship connections even at infinite depth.
10

---

Published in Transactions on Machine Learning Research (10/2023)
Graph size a 1000
Graph size + oc
(5) +
[9]
Ang in-ilus di nut-<Etlee cet-o blork differeeee (1x)
10
PC..ps
PCjroa
Vixiil SeevPP
True class separabilley
(7)
True class asparability (f)
Figure 6: Skip connection retains class information even at infinite depth. Left:: average in-class and out-of-class block difference at co for small and large and different true class separability r (in log scale). Heatmaps: exact NTKs θ (8) for Saym and Srow for linear GCN and Skip-PC.
6.3 Numerical Validation for Random Graphs
We validate our theoretical result using the same setup detailed Section 5.2 and compute the exact NTKs for Skip-PC and Skip-a for both Sym and Srow- We show the result homophilic graphs but they equally extend to the heterophilic case. While Symm has no class information for depth=8 in vanilla GCN, it is retained reasonably in Skip-PC (right of Figure 0 colurnn 1). In the case of Srow, we clearly observe the blocks in both cases with more prevalent gap in Skip-PC illustrating our theoretical results (right of Figure 0 column 2). Similar observation made for Skip-a despite considering XX = In as the model interpolates with the feature, and is discussed Appendix C.3 Validation of the results for heterophily graphs also included in Appendix C.3 While both S Saym and Srow retain the class information in larger depths, we observe that the degree correction plays significant role in S Saym elucidated in theoretical analysis.
7 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 + M. We consider multi-class node classification for Cora (K 7). The NTKs for linear and ReLU GCNs, and GCN with Skip-PC are illustrated in Figure 7 Experimental details and additional results for Skip-a and Cileseer are in C.4 and Appendices C.5 respectively. 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 Srows thus illustrating that the class information is well retained by Srow than S Seymi (ii) linear and ReLU GCNs show similar class preservation qualitatively. Thus, although the thcoretical result is based on DC-SBM with mild assumptions, the conclusions hold reasonably well in real settings real datasets well.
e
(8) PCCrose
roor
aC
Lincar GON
Dd-4lps
ReLD
Figure 7: Evaluation on Cora dataset. Heatmaps show exact. NTKs ((8) for linear, ReLU and Skip-PC GCNs for both symmetric and row normalized adjacency.
8 Discussion
Related Work. While GNNs are extensively used in practice, their understanding is limited, and the analysis is mostly restricted to empirical approaches (Bojchevski al. 2018 Zhang al. 2018 Ying al.,
2018 Wu et al. 2020
Beyond empirical methods, rigorous theoretical analysis using learning theoretical
11

---

Published in Transactions on Machine Learning Research (10/2023)
bounds such as VC Dimension, Scarselli et al. (2018) PAC-Bayes Liao et al. (2021) Lipschitzness analysis
(Tang & Liu 2023), or sample complexity using graph topology sampling [Li et al. 2022) are propounded. Rademacher Complexity bounds (Garg et al., 2020; Esser et al. 2021) show that normalized graph
convolution is beneficial, but those works do not provide insight on the inffuence of different normalizations
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.) (019a)). In the context of GNNs, Du et al. (2019b) derives the NTK in the supervised setting (each graph is data instance to be classified) and empirically studies the NTK performance, however does not extend it to theoretical analysis, and Krishnagopal & Ruiz (2023) uses Graph NTK to study convergence of large graphs. 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. Theoretical studies (Oono & 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 lincar GNNs finite number of convolutions improves learning before over-smoothing kicks in. On the other hand, Coog al. (202T) argues that over-smoothing does not necessarily happen in practice, and deeper model is provably expressive. While over-smoothing and role of skip connections in GNNs are theoretically analyzed in some works (Esser) ct al. 2021). the inffuence of different convolutions that causes over-smoothing and their interplay with skip connections is not studied. For a comprehensive theory survey see Jegelka (0022).
Conclusion. The performance of GCNs is siguificantly influenced by the architecture choices, but existing learning theoretic bounds for GCNs do not provide insights specifically into the representation power of the graph convolutions and the influence of activation functions. We present 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 Skym: are preferred in practice (Theorem 1. In contrast to applying spectral analysis of the convolutions to explain over-smoothing, our explicit charactorization of the network provides more exact quantification of the impact of over-smoothing in deep GCNs (Corollary [ see Figures 3 and 4 In addition, the NTKs for GCNs with skip connections enable precise understanding of the role of skip connections in countering the over-smoothing effect (Theorems Another value addition of our analysis is the exact quantification of the role of non-linearity [Theorem 3). While the DC-SBM assumption may seem restrictive, it is important to note that the impact of depth is derived for different convolutions exactly, therefore, making our result stronger and more precise than a general comment on the effect of over-smoothing resulting from these convolutions. Moreover, the experiments on Cora and Citeseer show that the general trends of our thcorctical results extend beyond DC-SBM, although formally characterizing such behavior is difficult without model assumptions.
Possible extensions. (i) Theoreticol Analysis. Considering random A would be more precise, but the concentration inequalities for NTK is more complex than those for Laplacians. We note that analysis could be extended by considering feature information (XXT * In) using Contextual Stochastic Block Model as discussed in Appendix B.9 which would require more involved analysis but could provide further insights into GCNs, such as interplay between graph and feature information. (ti) Gruph Models. The present NTK based setup allows for the analysis of different graphs having homophilic, heterophilic and core- periphery structures, and can be extended to other graph generating processes. (ii) GCN Models. Furthermore, the general formulation of NTK for vanilla GCNs (Theorem [] and with skip connoctions (Corollaries 3 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 theoretical analysis of other graph learning problems, such as link prediction. (ix) Analysis. We consider class separability as the main measure to compare different NTKs. However while we empirically observe that this measure captures the overall main trends in the MSE and accuracy, there are also cases where the measure does not capture all the trends. Therefore, we leave analyzing further ways to characterize the connection between changes in the NTK and the performance of the neural network for future study.
12

---

Published in Transactions on Machine Learning Research (10/2023)
9 Acknowledgment
This work has been supported by projects from the German Research Foundation (Research Training Group GRK 2428 and Priority Program SPP 2298, project GH 257/2-1).
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 Processing Systems. 2019.
Alberto Bietti and Julien Mairal. On the inductive bias of neural tangent kernels. In Conference on Neural Informalion Processing Systems, volune 32, pp. 12873 12884, 2019.
Aleksandar Bojehevski, Oleksandr Shehur, Daniel Zügner, and Stephan Günnemann. Netgan: Generating graphs via random walks. In International Conference on Machine Learning, 2018.
Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yamn 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 arXiv:2006. 13318, 2020.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International Conference on Machine Learning, pp. 1725 1735. PMLR, 2020.
Minmin Chen, Jeffrey Pennington, and Samuel Schoenholz. Dynamical isometry and a mean field theory of rmns: Gating enables signal propagation in recurrent neural networks. In International Conference on Machine Learning, pp. 873 882. PMLR, 2018a.
Zhengdao Chen, Lisha Li, and Joan Bruna. Supervised community detection with line graph neural networks. In International Conference on Learning Representations, 2018b.
Weilin Cong, Morteza Ramezani, and Mehrdad Mahdavi. On provable benefits of depth in training graph convolutional networks. Advances in Newral Information Processing Systems, 34:9936-9949, 2021.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Conference on Neural Information Processing Systems, 2016.
Yash Deshpande, Subhabrata Sen, Andrea Montanari, and Elchanan Mossel. Contextual stochastic block models. Advances in Neural Information Processing Systems, 31, 2018.
Pedro Domingos. Every model learned by gradient descent is approximately kernel machine. arXiv preprint 00X1::2012.00152, 2020.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep ncural networks. In International Conference on Machine Learning, pp. 1675-1685. PMLR, 2019a.
Simon S Du, Kangcheng Hou, Barnabás Póczos, Ruslan Salakhurdinov, Ruosong Wang, and Keyulu Xu. Graph neural tangent kernel: Fusing graph neural networks with graph kernels. In Conference on Neural Information Processing Systems, 2019b.
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru- Guzik, and Ryan P Adams. Convolutional networks graphs for learning molecular fingerprints. Neural Information Processing Systems, 28, 2015.
Pascal Mattia Esser, Leena C. Vankadara, and Debarghya Ghoshdastidar. Learning theory can (sometimes) explain generalisation in graph neural networks. In Proceedings of the 34th International Conference on Neural Information Processing Systems, 2021.
13

---

Published in Transactions on Machine Learning Research (10/2023)
Santo Fortunato and Darko Hric. Community detection in networks: A user guide. Physics reports, 659: 1-44, 2016.
Vikas Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. In International Conference on Machine Learning, pp. 3419 3430. PMLR, 2020.
Dar Gilboa, Bo Chang, Minmin Chen, Greg Yang, Samuel S Schoenholz, Ed H Chi, and Jeffrey Pennington. Dynamical isometry and mean field theory of lstms and grus. arXiv preprint arXiv: 1901.0087,, 2019.
William L Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Conference on Neural Information Processing Systems, pp. 1025-1035, 2017.
Soufiane Hayou, Arnaud Doucet, and Judith Rousseau. On the impact of the activation function on deep neural networks training. In International conference on machine learning, pp. 2672 2680. PMLR, 2019.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: convergence and generalization in neural networks. In Conference on Neural Information Processing Systems, pp. 8580-8589, 2018.
Stefanic 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 Pro- ceedings of the Twelfth ACM International Conference on Web Search and Data Mining, pp. 366-30 376-374, 2019.
Brian Karrer and Mark EJ Newman Stochastic blockmodels and community structure in networks. Physical review E, 83(1)00 2011.
Tatsuro Kawamoto, Masashi Tsubaki, and Tomoyuki Obuchi. Mean-field theory of graph neural networks in graph partitioning. Adeances Neural Information Processing Systems, 31, 2018.
Nicolas Keriven. Not too little, not too much: a theoretical analysis of graph (over) smoothing. arXiv preprint Xix:22200. 12156, 2022.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Leurning Representations (ICLR), 2017.
Sanjukla Krishnagopal and Luana Ruiz. Graph neural langent kernel: Convergence on large graphs. arxio preprint arXit:2301.1000, 2023.
Jaehoon Lee, Yasaman Bahri, Roman Novak, Samuel S Schoenholz, Jeffrey Pennington, and Jascha Sohl- Dickstein. Deep neural networks as gaussian processes. In International Conference on Learning Repre- sentations, 2018.
Hongkang Li, Meng Wang, Sijia Liu, Pin-Yu Chen, and Jinjun Xiong. Generalization guarantee of training graph convolutional networks with graph topology sampling. In International Conference on Machine Learning, pp. 13014-13051. PMLR, 2022.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi- supervised learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Yujia Li, Daniel Tarlow, Marc Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. In International Conference on Learning Representations, 2016.
Renjie Liao, Raquel Urtasun, and Richard Zemel. A pac-bayesian approach to generalization bounds for graph neural networks. In International Conference on Learning Representations, 2021.
Chaoyue Liu, Libin Zhu, and Misha Belkin. On the lincarity of large non-linear models: when and why the tangent kernel is constant. In Conference on Neural Information Processing Systems, volume 33, pp. 15954- 15954-15964, 2020.
14

---

Published in Transactions on Machine Learning Research (10/2023)
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classifi- cation. In International Conference on Learning Representations, 2019.
Ben Poole, Subhaneil Lahiri, Maithra Raghu, Jascha Sohl-Dickstein, and Surya Ganguli. Exponential ex- pressivity in deep neural networks through transient chaos. Advonces in neural information processing systems, 29, 2016.
Rahul Ragesh, Sundararajan Sellamanickam, Arun 1yer, Ramakrishna Bairi, and Vijay Lingam. Hetegen: Heterogeneous graph convolutional networks for text classification. In Proceedings of the 14th ACM In- lernalional Conference on Web Search and Dala Mining, pp. 860 868, 2021.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1):61-88) -0,, 2008.
Franco Scarselli, Ah Chung Tsoi, and Markus Hagenbuchner. The aapmik-chervonenkle dimension of graph and recursive neural networks. Newral Networks, 108:248 - 259, 2018.
Samuel S. Schoenholz, Justin Gilmer, Surya Ganguli, and Jascha Sohl-Dickstein. Deep information propa- gation. In International Conference Learning Representations, 2017. URL httpp:://pperreveew..et.
Forum?id=HiW1un
Huayi Tang and Yong Liu. Towards understanding the generalization of graph neural networks. arXiv preprint Xrxe:2230 08048, 2023.
Rianne van den Berg, Thomas N Kipf, and Max Welling, Graph convolutional matrix completion. arXiv 2017.
preprint
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. stat, 1050:4, 2018.
Hongwei Wang and Jure Leskovec. Unifying graph convolutional neural networks and label propagation. arXiv preprint arXim:2002.0000 067555 2020.
Xiaoyun Wang, Minhao Cheng, Joe Eaton, Cho-Jui Hsich, and Felix Wu. Attack graph convolutional net- works by adding fake nodes. In Proceedings of Woodstock 18: ACM Symposium on Newral Gaze Detection, Woodstock, NY, 2018.
Oliver Wieder, Stefan Kohlbacher, Mélaine Kuenemann, Arthur Garon, Pierre Ducrot, Thomas Seidel, 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. Simplifying graph convolutional networks. In International Conference on Machine Learning, pp. 6861-6871. PMLR, 2019.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chenggi Zhang, and Philip S Yu. comprehensive survey on graph neural networks. In IEEE transactions neural networks and learning systems, 2020.
Lechao Xiao, Yasaman Bahri, Jascha Sohl-Dickstein, Samuel Schoenholz, and Jeffrey Pennington. Dynamical isometry and a mean field theory of cnns: How train 10,000-layer vanilla convolutional neural networks. In International Conference on Machine Learning, pp. 5393 5402. PMLR, 2018.
Lochao Xiao, Jeffrey Pennington, and Samuel Schoenholz. Disentangling trainability and generalization in deep neural networks. In International Conference on Machine Learning, pp. 10462-10472. PMLR, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019.
Ge Yang and Samuel Schoenholz. Mean field residual networks: On the edge of chaos. Advances in neural information processing systems, 30, 2017.
15

---

Published in Transactions on Machine Learning Research (10/2023)
Greg Yang. Scaling limits of wide neural networks with weight sharing: Gaussian process behavior, gradient independence, and neural langent kernel derivation. orXiv preprinl ar arXiv:1902, 04760, 2019.
Rex Ying, Jiaxuan You, Christopher Morris, Xiang Ren, William L. Hamilton, and Jure Leskovee. Hi- erarchical graph representation learning with differentiable pooling. Tn 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. In AAAI Conference on Artificial Intelligncce, 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 applications. Al Open, 1:57 81, 2020.
16

---

Published in Transactions on Machine Learning Research (10/2023)
A Other Related Works
In contrast to the infinite width analysis, mean field limit analysis of finitcly wide neural networks is con- ducted for various architectures at initialization (Poole et al., 2016
Schoenholz et al. 2017 Yang & Schoen- Xiao et al. 2020). This analysis resorts to initializing the weights such that the variance of weights in every layer is scaled down by the number of neurons in the layer so that the input contribution of each neuron in the layer from the activations of the previous layer remains O(1). The primary objective of these works to study the trainability, generalization and expressivity aspects of the neural networks. Poole et a.l. (2016) shows that the networks with larger depths have the capacity to express highly non linear functions, rather than larger widths. This is extended to deriving conditions for the trainability of extremely deep neural networks in SSchoenhlzz et al. (017)) Using similar analysis, Yang & Schoenholy (2017) shows exponential input space collapse and vanishing/ hatissiing/xppodingng exploding gradients for deep feedforward networks, whereas it becomes subexponential, even polynomial in some cases for residual connections, and Hayou al.] (2019) derives initialization parameters for different activations to accelerate training. Consequently, better initialization schemes for trainability for extremely deep neural networks based on the conditioning of input-output Jacobian matrix are established for Convolutional Neu- ral Networks (Xiao el al.) 2018), Recurrent Neural Networks and Long Short Term Memory Networks Chen et al. (0188a); Gilboa et al. (2019). Interestingly, Xiao et al. (2020) studies the trainability and generalization of networks using the condition number the NTK and the NTK predictor, and shows that the trainability and generalizability are at odds in very wide and deep networks. In the context of GNNs, Kawamoto et al. (2018) extends the mean field analysis to graph partitioning, however exploring the potential of the analysis is still nascent.
holz 2017 Xiao et al., 2018 Chen et al. 2018a Gilboa et al., 2019
B Mathematical derivations and proofs
and 6 Corollaries We first derive the NTK (Theorem I for GCN defined in 2 and prove Theorems
2 3 and 4 by considering linear GCN and computing the population NTK C for different graph convolutions S. We then derive Theorem 3 for ReLU GCN similar to the analysis of linear GCN. We represent the u-th row of a matrix M as M.., and use 1, to denote a vector of n dimension with all 1s and in for a vector of n dimension with -1 1 as first 2 entries and +1 as the remaining ž entries, and 1xx for the n X n matrix of ones.
B.1 Theorem I NTK for Vanilla GCN
We rewrite the GCN Fw (X, defined in using the following recursive definitions:
Co (o Vie (2...., d+ F, G,W, (i+ hi-1
G = SX,
G, =
(6)
Thus, F = Fa+1- Since all the output neurons behave similarly in the infinite width limit, we consider W Wa41 be x and using the definitions in 6 the gradient with respect W, of node
11))
if = d+1
OFW(X.S) OW;
Co
WT d+1 @ (6(F.))
if d
= (B))) with (B))
h;
WT. O (o(F.)).. (T
ST
if
h4
where (B:),, E RaxA, We derive the NTK, as defined in using the recursive definition of Fw S) in 6 and its derivative in 7 Note that the derivatives in are computed for every node output following the approach in Arora et al. (001)), hence (XFw(X.S) E ER4-1xh, We give the gradients in B.2
aw:
Co-variance between Nodes. We will first derive the co-variance matrix of size n x n for each layer comprising of 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 Zy throughout our proofs.
17

---

Published in Transactions on Machine Learning Research (10/2023)
E (FF (Fi) (G, (GGW)) Wi) (G) (i)w)
ho =
ho
(W. (W)).o/V(a..)
G1)ar (W1). Wi)r Σ
(Gi)ss (Wi)sk)
if # or k
hg
E [(F1).)) (Fi)
(G) (G) (Gi)er (Wi)
k=k
(W (W))ay-(0..
(G) (G1)er ((G1).. (G))..
;G
(8)
h
E [(F))xx (Fi)
=
E
(Gr (Gi) (Wi)pk
k=k
(w (W))ag~(ol.1
h4-1
Σ
(Gr (Gt) ((Gi).. (G.)).))
(9)
Evaluating 8 and in terms of the graph in the following,
((G)).. (G1)..) ((SX).. (SX)..) S. X (E1) u
(10)
(G;;), (G:),.)
(F (So
h4-1
M
Ca
(So(Fi-1)).. (F
h4-1
k=1
1000000
E (So F, (Fi-1)) (So(Fi-1)),
; law of large numbers
n
c E
S S σ (F, (F.-1)rk
Σ
S S (Fi-1)ak)
c
SonO (F (Fi-1)yb (Fi-1)ak
Sur (E,-1),o ST. S., E. (Ei)uv
(11)
(a): using E ((F (F (Fi-1)akl
(E:-)),, and the definition of E;-1 in Theorem
NTK for Vanilla GCN. Let us first evaluate the tangent kernel component from We respective nodes and v. The following two results are needed derive it. To compute the NTK we need evaluate the sum of all parameters gradient dot product between two nodes u and v. To do so, first OF evaluate ow..
) in the following.
OF
OF
OF
BE-1.E Σ
OF TW
OF ij (
OW
OW
Tij=
i5
Σ
(G) (Ba).) (G (Ba)))
R.
Σ
Σ
(G ia ((x))) (G ((Bx)))
18

---

Published in Transactions on Machine Learning Research (10/2023)
he
Σ
ca
(S (BR+1), Wh+1)ay (6 (Fa))as (G+ (5" (Bu+1), Wk+z) (ō (Fw))s
(12)
hk
Ng.he+1. 41
Σ
Σ
Ca (s" (Br+1)a (Wi+1)y (6 (Fa))as (Go (5" (Be+1)a) bm (Wi+1)mm my (o (Fs))
hi
j=1,== a=1,b=1
000
Σ
(S (o
(6 (G& (s (Bs+1)a) (6 (Fx)los
1,601
hot1
Σ
Σ
(5 (BatIla (S" (Ba+1)al (G& Bo (FF(()))) 1
Co
hi+1
(S" (Ba+1)a)² (G& o Ex) (5" (Bx+2)a)) 11
-t((BB+1) S Eg Bx) ST (Ba+1).)
( tr((Ba+1) Th S. (.. S Ex Ex S" Ek+1) S ..... ....)).)) S (Bo+1),)
Sw. ( [E Es)
S" E S .... 2 Ex) S
(13)
(b): c. (F)) (Bs) ab'
ab_
(c): Expanding Bx+1 will result in the expression similar to 12 and repeated expansion until B4+1. The final equation is obtained by substituting (Ba+1), = from its definition in
Extending
13 to all nodes which will result in n x matrix, we get
OF
OF OW k OF OW
S
Ex) ST @ Ee+1) S .... E.. ST
UW
OF
E W.
S ((. E.) 8d o E 8 .... E,) S"
(14)
OW
Finally, NTK θ is,
d+1
OF OF Ow
1
E
Wt
aW
(... (S [E Ex) S" E S o... 2 E.) S"
(15)
with definition of EΦ and Eg mentioned in the theorem.
B.2 Gradients of functions with scalar output
We list here the aggregation of gradients for different functions that enable deriving the equation 7 The
0f
following OW
are derived assuming f R. Hence the derivative will be of same dimension as W.
19

---

Published in Transactions on Machine Learning Research (10/2023)
OXW =X11
@x(WW) xXX(
OW
OW
OXWY
do (XWY = -''6(WWY)1"
X" 1Y"
OW
OW
oZo (
x" 1Y Ok(XW)
OW
(z X
X
x [ Z 0 Z1 (Z
(20 (X)X (
OW
In the above, all are scalars. These derivatives are used derive
B.3 Theorems 2 4 and Corollary Population NTK é for Different Convolutions S
We consider linear GCN with Assumption 1 that is, orthonormal features and Assumption We derive it generally without the assumption on We first prove it for K = 2 and then exlend it to K classes We consider that all nodes are sorted per class for ease analysis which implies A a n x n matrix with pa,y entrics [1, "I[1, 2] and [ 1, nll 1, blocks and qua entries in [1, 2 2112 + 1, n] and [ + 1, blocks. Therefore,
A π ④
p
11
+ p 9 1i
2
p+g nπ²
A
(16)
2
where the entries of are -x, Vi [1, 21 and +m Vi E +1, The degree matrix D
(p+g)en diag(T) n
2
B.3.1 Symmetric Degree Normalized Adjacency Saym
Now, lets compute S sym using A
16 and its degree matrix D.
S San
D AD
2
diag(T))
pptg. q
p 9 #
diag(T)
(p + Q) on
2
1
1T
q
h +
CT
p + q
Ven
Ven
1 0
0
VTn Ven
TTn Ven
2x2
V
y Ven
ax2
Ven
2xm
U
(17)
Note that , A on, A since Eiec, π en value decomposition of S.ym-
and UTT I2, thus
is the singular
K
20

---

Published in Transactions on Machine Learning Research (10/2023)
To compute the population NTK 6eg for linear GCN with orthonormal features, we need S Seym Str
sym Using
17p
S sym
SKT
UA 2k U
spmm
Ven
ven
1
0
cn
V c
0
2k
V Ven
Ven
nx2
Von
2xn
S SKT sym eym
= (1 + 6sgr22) 2k)
v [T
;big (-1)
C7
(1+r21)) Tez
(1- - ,2h
v m
Sk SKT sym
matrix
(en)
(18)
sym notation
2k) mejy
11 + 2k 3
nxn
entries
# entries
Consequently, population NTK +
(d) sgm for nodes and j using
18 is as follows,
d+1
a
(dd) sym
sut1 ((d-1)7 sgm sym
ij
(d+ 1) (1 2d2)) y J
(19)
en
Hence, the average block difference the population NTK which we refer to class separability of the kernel (d) is derived with Σi=1 [T, = k] = A4
n/2 n/2
(d) 1(d+1) Saym n²(cn)
ΣΣ
(1 + r 2d+2)
v T,i
(1+ r 2d+2)
Ti
1=1 j=1
1n/2++
124221
n/2
n
n2/
Σ
Σ 22+2)
Σ
Σ (1-
21- 2d+2)
j=n/2+1
in//2+1j=1
1(d+1)
(1 + 2 (7î + オラ -2 2 2d++2) (21
ncn)
d + 1 ( (TI )2)
2d+2 (ni + T2)²
(20)
In 200
is of same order T2 and Ti T2 for large with Eiec, π on Hence, considering Ti 722 16+))++),,24++ It of O n ((d) ), since (π + To)² has n² terms, each of O(1).
we get the block difference as (=())) Therefore, the block difference of the population NTK ② (d) at d + 00
167 (d+1), ,22+2= lim
1672 d+1 1
lim d+000 n² (en)
d=000 n² (cn) r (2d42]
1672
d n² (cn) (2d42)) log(r) 0
lim
(21)
Apart from the block difference, can also see that the population kernel at ij is proportional to y
en
d + 20, thus converging to a constant kernel. Equations 19 and 21 prove the population NTK e sym
(d)
and
class separability of δ ((x) in Theorem and Corollary respectively. Substituting d and Vi, क Theorem 2 can be derived.
21

---

Published in Transactions on Machine Learning Research (10/2023)
B.3.2 Row Degree Normalized Adjacency Srow
The assumption on y in Assumption derive it without this assumption in the following, We first derive S Sow S
2 is only simplify the expression of population NTK for Syow- We
row
Srow = D
D $ D AD
= D D
S row
= DA
Sk KT
D'
rrw
D U'
D DUAUUA' +) D+ (D-+UA*''D-+
v2
1
= -OAAO"") D² (ÜA*O*)
= D U
17
cnvp p
nx2
[1 pka 2 + (1- -r))² p if and j E class
(Ston (tou)) (en)~²
(1+ rb) (1 p²) (2 n) if i and j & same class; A
(1 pk_ x + (+ (1 )*) p if and j E class 2
8=1
+1
(1+)))2> x (1 2#=) 1 (1+r*) (1 pk) (A+
Sk
row S0 yow
KT
matrix not
(en)~
(22)
(1 (1+r*) (1- (1-r*) (A pi)
11- x (1+
entries
entries
Note that each block is a constant and independent of individual n;. Using 22 and the assumption = /4 = in Theorem 4 the population NTK for nodes and j is,
(d)
Sd+Ig(d+1)1 Tow
2 (cn)²
= 1)+11 6
(23)
Using 23
we derive the class separability of the kernel Slav-
((d) 2y(d + 1) (cn)2
4, 2042
(24)
Similar to 20 clo)
is of O drdd since 7 is Onn), and the class separability of the population NTK 6 (()) 2y
at d + 0o is 0. Likewise, the population kernel at ij is proportional to Jenyz d + oo, thus converging to constant kernel proving Theorem 4 and Corollary respectively.
22

---

Published in Transactions on Machine Learning Research (10/2023)
B.3.3 Column Normalized Adjacency Scol
In this section we derive the population NTK 6 col"
(d))
S Scot = AD
D+
S col
D'
Sk KT col 2 col
DU UAA
= =ÚAA" D (ŪA*
Ü = -
D
p p q
π
#7
2
nx2
Jy (1 + 22k)
Tjj (1 - 22)
matrix
n
(25)
(cn)² ?
2
Tj (1 + 26)
entries
# entries
Therefore, 6 (d) col
for all and j is
d+1
(d)
25
(d+1g(
col
cal
coll
1=1
() (1 8,g 2d-2)
nT; (en)²
(26)
Using 226 and Eiec, the class separability of the kernel
Sool
(d)
4(d + 1) 2442
Seal
(27)
which is of O (
dn and the class separability of the population NTK (d) at d + oc is 0 similar to symmetric and row normalization cases. Likewise, the population kernel at ij is proportional to (en)² as
na,
d co, thus converging to constant kernel. Hence, equations 26 and 27 prove the population NTK c (d) and ((d) in Theorem and Corollary i respectively. col
B.3.4 Unnormalized Adjacency Sadj
We can rewrite A as follows,
P
9
A = ππ
O
q
P
2 entries
5 entries
p
q
π
(28)
Tn_
nXn
g
p
nXn
n
nXn
We consider 7 assumption for the analysis of unnormalised adjacency to simplify the computation. But the result holds without this assumption.
23

---

Published in Transactions on Machine Learning Research (10/2023)
(p² q2)
2pq7
[
A 2
n
Ypg7
(p² + q²) y
nnn
(p² o² + Gppp²) g8
(4p2 4pq2)) 7:3
m
A
Tn_
(4p2 + 4pn y3
(p* + q¹h + +pp 73
Note that in the above shown A 2k it the even powers of binomial expansion of (p + q)² for 2,j in same class whereas it is the odd powers for i not in the same class. We compute the filter Sudj using this fact.
1
Sadj
A
S
A k
n
A 2k
2k
Tz 26-1 1 2k-1
12 -2 q2
if i and j same class
n2
T;
x2
2
Σ
(2t+1)
2
21
if i and j E different class 22-1-
1=0
( odj
= (d + 1)
((d+1)T
adj
Sadj
21 p2a 2412 1- q2
if i and j E same class
2
(d 17
nd2+2
2d
2d
if and j different class 1 -1
2
p
2d+1-1 The class scparability in this case is Ced (d 1)c² nd0+2
(p
9) 2d+2 The above form is not simplified
as it is not an interesting case where the gap between the two blocks disappears rapidly and (0(20) adj i
There is no information in the kernel proving both Theorem and Corollary 1
B.3.5 Number of Classes > 2
From the above derivation for K = 2, it can be seen that once S sky SKT for all the graph convolutions can be derived using Therefore, we derive it for > 2 and it suffices show the conclusions of Theorem and Corollary We denote the vector iie with -M/Vi e [1, R.
sym is computed, the population NTK
+n.Vic E
n) K
nk and for the rest.. With this definition, K
A p (K
-1)q
K
A A
(29)
K
K
1=2
24

---

Published in Transactions on Machine Learning Research (10/2023)
D for K classes is (p+(K-1jp)) diag(n) Rt) from 29 We can compute Ssym using A and D as follows,
K
S syym
= D - AD
K
diag(n πT b)
p+ (K
1)g
p
9 Σ ना
diag(m b)
(p+ (K 1) en
K
π 2 π 12'
K
p
en
(p + (K'
-1)4) en
CN
1=2
K
j
p P-q
K
(S syym)
1 + 5zj
on
p (K 1)q
1+
1=2
j
p q
K
en
+ (K 1)q
1+12
1=2
(Sk SKT sym sym/i5
+ 8i3
P
2h:
K
(30)
(K
1)4
1+
1=2
It is noted that the equation 30 is very much similar to 18 for K = 2. The further derivations of the population NTKs for all the convolutions are similar and the theoretical results extend without any issues.
B.4 Corollary and 4 NTK for GCN with Skip Connections
We observe that the definitions of G, Vi E [1, + 1] are different. for GCN with skip connections from the vanilla GCN. Despite the difference, the definition of gradient with respect to W; in 7 does not change as G; in the gradient accounts for the change and moreover, there is no new learnable parameter since the imput transformation Ho = XWo where (Wok) sampled from 10, 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 evident from the derivation of NTK for vanilla GCN in Section [.] The change in G₁ will only affect the co carraniance between nodes. Hence, will derive the co-variance matrix for Skip-PC and Skip-a in the following.
Skip-PC: Co-variance between nodes. The co-variance between nodes and v in F, and F; are derived below.
E ((F)) Due (Fi).a)= = ((G)),., (GI)..)
Co (( (Ho,(H))),))
h
(So, (Ho)) (So, (So)(H))).k
C, [SSr, (Ho)) mm (So, (Ho))
law of large numbers
S E,ST
Ep co
E (F),, (F)T]
(E)) mm
(31)
25

---

Published in Transactions on Machine Learning Research (10/2023)
E (FF)) uk (Fi)et) =
So (SS (o (S(o(()))) (o,
co
[Fa(F;11) So, (H))) +
h
(So So (H
lla of large numbers
= co (( (BS (So
[S (Ho))) (Sa, (Ho)) E + C. (So (So, (XWo))
+ +E[SS,, (H))
+ ca B. [Sa, (XW()) mk (F
1
+ C.
Σ
S -. S o, (XWu), o. (XWo)
( S. E 1 Su. (XW o) 0, o S
S., E. v
+ + EOST = S, E, + (Et).v
-E,)
(32)
(f): E((So(F;-1)),t (Xo,(XW))).. and (((Ss,(XW))), uk (F-) evaluate by conditioning Wo first and rewriting the expectation based this conditioning. The terms within expectation independent when conditioned Wo, and hence it is
E
w (So Wol E
((So) [o]] by taking h in Wo going to infinity first.
Wo
Wo (So,(XW))), ok Wol 0.
Here,
E
E. 1/W,
We get the co-variance matrix for all pairs of nodes Σ; = SÈ and Σ; SE,-, + Σ from 31 and 32
Skip-a: Co-variance between nodes. Let u and e be two nodes and the co-variance between and F, and F, are derived below.
(F11 utk (Fi)et) ((G1).. (G1)..)
h
Co
((1 (a, + (H,(H))), (H) + aσ, (Ho))
=
h
k=
E [(1 a ao, (H)) ao, (1,a))o,(Ho)) + ao, (Ho))
c. (1 a) (So. (H))) Soo (H)))
+ (1 - a)a (So. (Ho)) u.k (o (Ho)) + (Soo (o.
+ a L [1o, (o)) 1 un (a, (H))) [
(1 S., ST (1 a)a (S.. (Eo) v + (Eo)... ST.) a² (Eo) RM
EE) )
(33)
Using E ((F)) (Fi)esh we recursively evalaue E (FF)) (F.).a) in the following,
26

---

Published in Transactions on Machine Learning Research (10/2023)
E
[ Dak (Fi) (GG)).. (G)
Co
((1 (U1-a)So(f [ - ((-aa)So(P:-)) ao, (Ho))
h
k=1
1=200
Co
+ 40, E(( - to (Ho)) ((1 a 0 (o)
co (1 [(o (So + a (Ho)) (o. (Ho))
+ - a)a E (So (F: La (as (Ho)) + ((ox(Ho)) (So (Fi (Fi
S. E S a² (Eo)... ne (Ei)ae
(34)
(g): same argument as (f) in derivation of Σ, in SKip-PC.
We get the co-variance matrix for all pairs of nodes Σ = - (S + a(1 a)) (SE EAST) + a 2E
and Σ; - -- a E from 33 and 34
B.5 Theorem 5 Class Separability Population NTK θ for Skip-PC
NTK at depth d, o PC
for Skip-PC with linear activations is
d+1
2
(d)
Σ
S sd+1-
k=1
4+1
sd+1-k (5tigT + SST) s(d-1-
k=1
d+1
Σ
sd+1g(d+1y + g4+2-kgld+2-M1
(35)
A=1
In 35
NTK without skip connection and IT computed for Srow and Saym as follows.
Computing II for population NTK (d) for S Saym: for nodes and j:
4+1
d+1
sd+2-*g(d=2-NN) sym
Σ
(1 + 8ig 2d+1 26)
Me (cn)
sym
d+1
= (d+ + 1)
8:3
2h
Rm
(1 ((d+1)
K
= (d + 1)
8.
(36)
Cn
Cn
p2
with 19 the class separability of the kernel Pcm as d + oo is determined only by the last. term in 36 as the other terms give separation. Hence, the influence of skip connection gives
Combining
36
1672,2
(00)
(37)
PC (e( - x2)
where 5 is defined as Thcorem
/ T (2 2. Thus showing class separation information retained even at co depth and graph size.
27

---

Published in Transactions on Machine Learning Research (10/2023)
Similarly, computing II for Srow without assumption on 7 i and in class 1,
d+1
S k row row
(on)
+ 2k 2r x + (1 + n2t 21*h) 1
is
h=1
(d+ y² (1 (1- (1- )2
+ + - 11) r 1 ) -11--))))
= (cn)=2
() (1+
(38)
1 p-
--
For i and j in class 2,
d+1
d+1
= (en)=
Σ
(1 11+2"h-2** -2r x (1 + r + 2n
row
row
k=1
2² (1-
+2(- (
(en) (A (A+ ui)
(d (d+1)
1- 22
1-r
(39)
For i and j in different class,
d+1
-2 d+1
Sd+2 (B22-k((+2-k))))
k))) 1j
(cn)
(1 - ,2h) (A 1+)
1=1
(d+1)- x² (1 22(+11)
= =cnn) (A+
(40)
1-
Therefore, the influence of the skip connection in the class separability of population NTK + (0)) assumption is obtained by substituting X + 27 and
PCrrww with 7
in 38
139
and
40
871²
(00)
PCW
(on)²(1 r2)
hence deriving Theorem
B.6 Theorem 6 Population NTK 6 for Skip-a
We expand ES and Σg of Skip-a first to derive the population NTK.
E, (1 a)² SS + a (1 a) SS) + I²I,
Σx (1 -))² a>" SΣ SS + I
+ k-1
(1 a) 2* s (1 (1- 2k sk- (S+ -
Σ
a)²
s's'
(41)
Exact NTK of depth d for Skip-a is expanded using the above as follows.
d+1
(
k=1
d+1
Σ
a) 2k
g(+1g(++)) + +a a0)kk11 sd (S ST) sa
+ Σ
a)
k=1
1=0
11
111
(42)
We compute the class scparability of the kernel O (o)) d oo for Seym and Srow- From 42 is clear that terms I and II lead to class separation as derived in previous cases. So, we evaluate III of 42) in the following.
28

---

Published in Transactions on Machine Learning Research (10/2023)
d-1 k-1
11 = a
(1 a) s
syym
1mm
1m0
d+1
a)² (1 + 8igT 2d2 2
cn
1=0
1 (1- (1- (11-a)22)) 10
2k p2(d+1-b)
d+1
(1 a
2
+ 8ij
Cn
(1 a)² 2
(1 a)²
#=1
(1 (1-a)² - (1-(1- ( 2))(d+11)
(d ()
en
1 1- (1 =a)
(1 - (1 (1-
a)=
1 1 (1-(1- -a)--)))t 2(d(1))
dij
1- 2((++)
2((d+)
(43)
(1 a) p2
2
1 p2
a)²
The class separability of kernel is non zero only for the last term in 43 Hence, the class separability ch
is
2(d+1) (1 aa) (1 (1 a) 2()(11)))
1672a²
1 -- 2(d4()
(d)
Sa,s
(cn)n² 1 (1 (1-1 p2)
1- r2
(1 a) 2
((oc)
167
1
Sa.sym
(cn)n² (1 (1- (1 - (1-)² (2)2pp) p2)
22
proving Theorem
We now compute III for population NTK (00) using Srow under X A= p =-= 7. The derivation holds without this consideration as well.
d-1k-1
11 = 2
Σ
(1 a)²
21
d+1 h-1
2
(1 - a)² (1 + 2 22+21) 20
2d+2
(en)2
k=1 1=0
(1
2(d+1-b)
(1 (1- ()) 0))))
2y
d+1
- (1 a)
+ +di
(en)2
1 (1 a)²
1 - (1 2)²²² p2
(1 (1-))² (1- a) 2(d-1)
2ya²
(d + 1)
(en)²
(1 a)²
1 - (1-1-a)) 2
(d++) (1- (1-a)² 1 - (1-(1- aaaaa)a 2(d+1)
8ij
- 2(d+1)
(44)
1 1- (1
2
1 p2
1 1- (1 a)
29

---

Published in Transactions on Machine Learning Research (10/2023)
Similar to S agm: the class separability of kernel is non only for the last term in 44 separability Sorrow is
Hence, the class
2((+1) (1 ax) (1 (1 - ax 2((((+1))
8
1 - (((+1)
(()) Sa,,ooe
(en)2 (1 aa) ==)22 y2
- y2
(1 10-0) ox)
8yaa
1
(00) S0,ro
(en)2 1 - - -0) x)²22)
proving Theorem 6
B.7 Theorem Population NTK é for ReLU GCN for normalized adjacency $
We first state the NTK for ReLU GCN using the general NTK Theorem and result from Bietti Mairal (2019) in the following corollary. Note that Co 2 for ReLU activation.
Corollary 5 (ReLU GCN) Consider dxx) == ReLU(x) in FW,X,S). The NTK computed as in 3 where given Eg at each layer, one evaluate the entries of Eg and Eς using result from Bietti & Mairal 2019) a8
(Ek)
Ei = (E)) (Et)is Kn
(Ex)is (E (Ex)as
(Ei)ss
(Bk),; no
(Ex)is (Ex)
1 (x ( arccos (x:) v1 x²).
where No (x) (x arccos (æ)) and K1 (x²)
Using Corollary we derive Theorem the population NTK of the ReLU GCN for depth d, (c)) considering homogencous degree correction π. That is, π = (c, .). Therefore, symmetric, row and column normalized adjacencies are equivalent and is,
S D D ADD
1 111" + +rii")
Therefore, using S, mo()) and k-()) compute Σ,, E, and E₁ as,
1 + 22
2
Σ = =
1 7
1
RXB
E, (1+ + 22)
Kl
1+r
n
K1 Itr
XXX
Kj (A1)
1 - p
(1 2
A
Ki (A1)
1 2
AXB
Ku (A1)
(45)
No (A1)
30

---

Published in Transactions on Machine Learning Research (10/2023)
Now, lets define As - (1+ (1
Furthermore, Ag and Ag denote the numerator and r2) + (1-1)2) k2 (A+-1)
denominator of AR, respectively. With this definition, we compute Ex. Eg and Es recursive as follows to compute the population NTK (())
A
4
A
Σ SE,
S"
2n
A
A
TLX
1
R1
(Az)
Kg (A2)
E2
E2
2n
K1 (A2)
NO (A2)
nxn
Extending to k
A A
4
A
Σ/
2 n
A
k
A
1
Ki (AR)
Ko (Ax)
Eg
Ex
(46)
26-1n In
K1
(AR)
150 (Ax)
nxn
We obtain population NTK for ReLU GCN in Theorem by substituting Σk. ΣS and Eg in the NTK equation in (3.
B.8 Difference between block difference of linear and ReLU GCNs for depth d =
First, lets compute the average in-class and out-of-class block differences for d= 1 linear and ReLU GCNs. To do so, lets consider homogeneous degree correction as in Section B.7 Therefore, population NTKs for linear and ReLU GCNs (1) and Ô (1) ReLU are,
2
1 1+r² x2
1- p²
(47)
n
1 p2
1+
mxn
+ (1)
(1 21+ (1 -2) Ko (Ai)
(1-r4) + (1-14) K0 (A1)
A
A
A
ReLU
2n
(1 - rd) + (1 (1- rr) mi()
(1++2)* + (1 - Ko (1)
2n
A3
A
nxn
mxn
(48)
Let the average block difference for linear and ReLU GCNs of depth be denoted by Stin and ÇReLU, respectively. Using (47 and 48 we get
8r2
= 0 1
Gin
n
4
(72 + 1 +
(r2
mo()
4r (1- (Ai)))
SRELU
2n
2n
Therefore, theoretically linear GCN and ReLU GCN of depth retains similar class information for large graphs and hence they perform similarly.
B.9 Analysis without orthonormal feature assumption XXT * In
To include the features so that T + I,, we consider Contertual Stochastic Block Models (Deshpande 2018) in which the features of node i, x; z: -N, where μ E R and 2; +1 if node C, -1 if E C2 for K 2. The analysis be extended to K > as well. Under this model, the
31

---

Published in Transactions on Machine Learning Research (10/2023)
population version of XX" is zμ² pz" = ||||| where z (21, 2n) R". For simplicity, we present
the average in-class and out-of-class block difference of linear (Gim) and ReLU GCNs (SRELV) for depth d = 1. Ctin = || (2r*) and GReLU = || (4r"(1 + 1/n)), respectively. Consequently, Stin I CR E [0, 1], n. However, both are of O(r*). As the population NTK for depth will be a more complex expression under
Contextual SBM, we show the result for d = for simplicity. But, we note that. the result will extend to general d.
C Empirical Analysis
We provide the code for NTK and the block model in https://ggtthb..cmmm
GCN.
C.1
Experimental Details of Figure
We use the code for GCN without skip connections from githubl Kipf & Welling 2017 and skip connection
from [hen et al. 2020 The following hyperparameters are used for GCN without skip connections: learning rate is 0.01, weight. decay is 5e - 4, hidden layer width is 64 and epochs is 500, 1500, 2000 for depths 2, 2,4,8 respectively. For the skip connections, we used GCNII model, same parameters as vanilla GCN with a 0.1. The performance is averaged over 5 runs.
2500
In Figure we showcase the performance degradation of GCN with depth. The right plot shows the zoomed in version of the left plot to show the performance drop more clearly. Note that depth refers to the nunber of hidden layers in the definition of GCN 2 Hence, depth= 0 means there is no hidden layer.
Accuracy of clas prrdictan (10)
2
Desth of GCX
Depth of GCX
Figure 8: Performance of GCN with depth on Cora. Depth= 0 refers to no hidden layer in GCN. The right plot shows the zoomed in version of the left plot.
C.2 Comparison of GCN and NTK
Although it is theoretically clear that the infinite width assumption should not affect the obsorvations made on performance of GCN with S.ym and Srow in Figure [ we illustrate the same using graph NTK. Figure g shows that the observation is in graph NTK well, thus supporting our theoretical argument.
32

---

Published in Transactions on Machine Learning Research (10/2023)
A4-
GCN 8um
GCN S.m
NTK Bcce
NTK
16
Depth
Figure Comparison of the accuracy of a trained finite width GCN and the corresponding NTK. NTK captures the performance trend of the GCN, although the exact performance doesn't 't match.
C.3 Numerical Validation for DC-SBM for Vanilla GCN and Skip-a
Experimental Details. For the experiments, we fix the size of the sampled graphs to 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 q= 1 for core- periphery DC-SBM. is sampled uniformly [0, 1] for homophily and heterophily, and क. Unif(0.5, 1)vi e core and Unif(O, 0.5)Vi E periphery for core-periphery DC-SBM.
Illustration of impact of depth in Vanilla GCN using Homophily DC-SBM. We show the impact of depth in Vanilla GCN using homophily DC-SBM in Figure 10 The DC-SBM is shown in the first column and columns 2 and show the exact NTK for depth=1 and for symmetric and row normalization, 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 in normalization depth (column 3), the block/ commuityyyyt structure is still retained. Thus showing the strong representation power of Srow.
DC-SBM
(d) stymI
O
(d) YON
x10
Avg. in-class & aut-of-class block difference for (1
depth=1
depth=1
S Sam
2-
S.st
S.i
depth 8
depth-
Depth
Figure 10: Numerical validation of Theorem 4 using DC-SBM shown in the first plot of column 1. Columns 2 and 3 illustrate the exact NTKs depth=1 and 8 for S S.ym and Srow, respectively. Second plot in column shows the average gap between in-class and out-of-class blocks from theory.
Illustration of Scot and Sad in Vanilla GCN using Homophily DC-SBM. We extend the experiments on numerical validation for random graphs using vanilla GCN described in Section 5.2 to column normalized adjacency Scot and unnormalized adjacency Sody here. We use the same setup described in Scction 5.2 and Figure 11 illustrates the results. We observe that even for depth 1 both the convolutions are influenced by
33

---

Published in Transactions on Machine Learning Research (10/2023)
the degree correction and there is no class information in the kernels for higher depth. Thus, this validates the theoretical result in Theorem
10
x10
33 0
depth-1
depth
depth=1
depth=8
Figure 11: Numerical validation of DC-SBM for Vanilla GCN. The first two heatmaps show the exact NTK (d)) for column normalized adjacency convolution Scol and the other two for unnormalized adjacency Sadj for depths d and 8.
Validation of the theoretical filter ordering based on the population kernel block difference. We validate the theoretical finding of the filter O row > sgm e > O based on the population kernel block diffcrence by sampling a graph from a DC-SBM and measuring the Mcan Squared Error (MSE) of the prediction from the exact kernel for various depth of GCN. Figure illustrates the order of convolution filters obtained theoretically holds very well in practice.
AVL in closs & ort--f-- claes difffrence 6)
Siee
MSSE of kocuel prodiction of sumpled graph
Sal
Depth
Depth
Figure 12: Numerical validation of the theoretical filter ordering based on the kernel class scparability, Left plot shows the result from theory based on the block difference of the population NTK. The right plot shows the Mean Squared Error (MSE) of the prediction from the exact kernel of sampled graph. The order of convolutions based on MSE clearly validates the theory.
Illustration of impact of depth in SKip-PC and Skip-a using Homophily DC-SBM. We present a complementary result Section 6.3 here. We use the same sctting as described in Section 6.3 and plot the exact NTKs of depths 1 and for symmetric and row normalization. Figure 13 shows the results for Skip-PC and observe that the gap between in-class and out-of-class blocks decreases for both Srow and S with depth, but the class information is still retained for larger depth and the gap doesn't vanish. Between Srow and S Sym, the heatmaps show that Srow retains the block structure better than Saym and is devoid of the influence of the degree corrections.
(d)
(d)
(d)
(d) Poir
10
X10
Skip-PC
1.0
5.0
0.5
depth=1
depth=1
depth
depth=8
Figure 13: Numerical validation of DC-SBM for Skip-PC. It shows the exact NTKs e (d) for S Saym and Srow for depths d = 1 and 8.
34

---

Published in Transactions on Machine Learning Research (10/2023)
In the case of Sk 0.1 to obtain the result illustrated in Figure 14 Similar conclusions are derived from the experiment. Although we consider Xx" = I, for Skip-a which fundamentally relies on the feature information to interpolate, the results are still meaningful and demonstrate the theoretical findings.
(d) SUgm7
(d) rou
sggn
YOU
x10-6
Skip-
depth=1
depth=1
depth=8
depth=8
Figure 14: Numerical validation of DC-SBM for Skip-a. shows the exact NTKs ( for Ssym and Srow for depths d d= and 8.
Numerical analysis of the results using Heterophily DC-SBM. We extend the analysis to heterophily setting by sampling graph of size n 1000 and validate our theoretical results on the impact of depth in Vanilla GCN, Skip-PC and Skip-a. We plot the NTKs for depth = 1 and d for symmetric and row normalized adjacency matrices and linear GCN for all the cases. Figure 15 illustrates the results for Vanilla GCN where the plot in the first column shows the heterophilic DC-SBM from which the graph sampled. Observations are similar the homophilic setting, validating our theoretical results from Theorem
DC-SBM
θ stm
(d)
row
0.005
Avg. in-class & out-of-class
depth=1
depth=1
block difference for θ
x10
x
a-
syme Scl
S.dj
10
depth=8
depth=8
Depth
Figure 15: Numerical validation of Theorem 4 using DC-SBM shown in the first plot of column 1. Columns 2 and 3 illustrate the exact NTKs of depth=1 and 8 for Saym and Srow, respectively. Second plot in column shows the average gap between in-class and out-of-class blocks from theory.
Validation of the theoretical filter ordering based on the population kernel block difference. Similar to the homophily case, we validate the theoretical finding of the filter θrow > 3 3ym θcot > @adj basod on the population kernel block difference by sampling a graph from a DC-SBM and mcasuring the Mean Squared Error (MSE) of the prediction from the exact kernel for various depth of GCN. Figure 16 illustrates the order of convolution filters obtained theoretically holds very well in practice.
35

---

Published in Transactions on Machine Learning Research (10/2023)
invelion eotanttte deberveee Sir
MSC of keroll pooiition sampled
Depth
Figure 16: Numerical validation of the theoretical filter ordering based the kernel class separability. Left plot shows the result. from theory based on the block difference of the population NTK. The right plot shows the Mean Squared Error (MSE) of the prediction from the exact kernel of sampled graph. The order of convolutions based on MSE clearly validates the thcory.
Figure 17 shows the impact of depth for symmetric and row normalized adjacency in Skip-PC and Skip-a GCNs. Again, we observe similar results homophilic and also the thcoretic results hold such as the class information is still retained for larger depth and the gap doesn't vanish, and between Srow and S Semm: the heatmaps show that Srow retains the block structure better than Skym and is devoid of the influence of the degree corrections.
Agjin
+
You
x10
Agent
(
idl
x
Skip-PC
0.5
depth=1
depth=1
depth=8
depth=8
X10
x
Skip-
depth=1
depth=1
depth=8
depth=8
Figure 17:
Numerical validation of DC-SBM for Skip-PC and Skip-a. It shows the exact NTKs (d) for S Sam and Srow for depths and 8.
Numerical Validation of Core-Periphery DC-SBM. In this section, validate the two scenarios discussed in Section 5.3 core-periphery without community structure and core-periphery with community structure. For the firsr case, we consider coro-periphery DC-SBM with n/4 nodes as core and the rest as periphery as shown in the first heatmap of Figure [8] We plot the exact NTKs of depth 2 for symmetric and row normalization using Vanilla GCN as shown the second and third heatmaps of Figure I8 This clearly demonstrates the theoretical result presented in Corollary where the symmetric normalization exhibits the graph structure and the row normalization is constant kernel.
DC-SBM
(2)
Core- Periphery
Figure 18: Numerical validation of Core-Periphery DC-SBM. It shows the exact NTKs (d) for S Saym and Srow for depth 2.
36

---

Published in Transactions on Machine Learning Research (10/2023)
In the second setting, consider two communitics of equal size n/2 with core-periphery in each, and the link probabilities between cores of the communities is higher than core-periphery or periphery-periphery of the two communities as shown in the first heatmap of Figure 19 The exact NTKs of symmetric and row normalization are illustrated in the second and third heatmaps Figure normalization relains the community structure again.
19
where we see that row
DC-SBM
(2)
Yow
Periphery in communit
Figure 19: Numerical validation of Core-Periphery DC-SBM with community structure. shows the exact NTKs (d) for Saym and Srow for depth 2.
C.4 Experiments Real Dataset: Cora
Orthonormal Feature XX" In Assumption. In this section, present additional experiments
Cora. Since our theory assumed orthonormal features XX" = In we validate it experimentally in similar setup described in Section 7 Fig Figure 20 shows the result for Saym and Syow for depth and 8. The conclusions derived from real setting hold here as well and shows Srow preserves the class information better than S sym.
Jgm
Syou
Say
S
0,000
0M
degith11
depth-1
ILEC0
degith88
depth-8
Figure 20: Evaluation Cora with XX In. Plot shows S Saym and Srow for depths d and 8.
ReLU GCN. We present the result for ReLU GCN in this section. Figure 21 shows the result where the conclusions derived in Section 7 holds very well. Additionally, we plot the average in-class and out-of-clat block difference in the case of vanilla GCN (line plots in first row of Figure 21). 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.
TmU
2.0
Venilla GCN
3295903
1.5
1.0
0.5
depth=8
depthm88
0482
8.p-a
Skipp
2.20
0008
0a16
depth=88
depth=88
depth=8
depth-88
Figure 21: Evaluation on Cora dataset. Heatmaps show results of vanilla GCN and the decrease in class separability with depth for Semm and Srow- Last two show NTKs of Skip-PC where a min and max threshold of 30 and 70 plrcentile is set for better visualization.
37

---

Published in Transactions on Machine Learning Research (10/2023)
Another experimental study is to 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 21 shows class C2 and C5 are well represented by both Sam and S Srow- To study how well this holds in the trained GCN, we considered depth 4 vanilla GCN with ReLU activations and used the same hyperparameters mentioned in Section C.1 The results are shown in Figure 22 where 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 it has to do with the data split and some classes are poorly represented the training data, for instance C6. Thus, we leave it for further analysis.
Areuracy
C3
Classess in Coca.
Figure
Class wise performance of trained GCN of depth 4.
Linear GCN. We present the result for linear GCN with the same setup described in Section to check the goodness of our theory. The results are illustrated in Figure 23 where observe that the theory holds very well for linear GCN than ReLU GCN. The class information is better preserved in Srow than S Ssym 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 as well.
(d
aymm
200
Vanilla GCN
Ang. Indlaa ant-r--ue Hinoe
1.5
1/00
1.0
1.75
Lilfarane pc: tlao
0.50
0.
degth-l
depth-1
depph
depth-88
x10
0.000
Stepp PC
Saipa
0.010
degth-88
8epth-8
deppth-8
degtin-8
Depli
Figure 23: Evaluation on Cora using linear GCN, First row shows the results for vanilla GCN for depths 1 and 8. Second row shows the result for Skip-PC and Skip-a for depth 8. The last column shows the average in-class and out-of-class block difference per class of both the symmetric and row normalized adjacencies.
C.5 Experiments on Real Dataset: Citeseer
(r) Apro
e
e Aum
e.40
Vauiila GCN
0301
0000
depth:11
depta=1
depth:
deptlus8
Skip PC
Skipa
0,000
deptht-8
depti=8
deptt=-8
depth-88
Figure 24: Evaluation on Citeseer dataset using linear GCN. First row shows the results for vanilla
GCN for depths 1 and Second row shows the result for Skip-PC and Skip-a for depth 8.
38

---

Published in Transactions on Machine Learning Research (10/2023)
In this section, we validate theoretical findings on 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.2, 4, 8, 16 are computed and Figure 24 illustrates the results. All the obscrvations made in Section 7 hold here as well and clear blocks emerge for Srow making it the preferable choice as suggested the theory.
39


Reviews:
[{"review_id": "0E7v46HRue", "reviewer": "Reviewer_A2PN", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Disclaimer: I am not an expert on literature and did not verify the mathematical details.\n\n### Strengths:\n\n* The idea of analysis of nonlinearity and aggregation mechanism using population NTK under DC-SBM appears novel and well-executed. The theoretical results appear robust.\n\n* The paper is overall well-written and clear.\n\t\n\n### Weaknesses:\n\n* The presentation does not fully convince me that presented theory indeed explains empirical performance of GNNs. There is only one experiment (Figure 1/2) measuring actual accuracy of GNNs and the trends on it aren't robust enough (large error bars) or don't always match theory predictions. For example:\n\n\t* Section 4 predicts ReLU to do more over-smoothing at large depth than linear networks, but Figure 1/2 shows the opposite trend for row normalized networks.\n    \n    * Figure 3 predicts that row normalization will outperform symmetric most at shallow depths, but Figure 1/2 doesn't really show such a trend for linear networks (and the ReLU trend is inverted).\n    \n    * Section 6 predicts better performance of skip connections at large depth, but it's not visible on Figure 7 (leftmost vs rightmost heatmaps; in general, it's hard to analyze this Figure visually).\n    \n    * Minor: one of the conclusions of section 5.1 is that depth is detrimental to GCNs. Degenerating NTK at infinite depth is a common observation for most architectures, but it isn't actionable for depth selection and unlikely to explain the downward trend in Figure 1/2, as these depths are still too small (see more on this in Requested Changes).\n    \n\n\t* See more actionable concerns in Requested Changes.\n    \n\nOn the whole I find the paper to study a very interesting theoretical setting with robust theoretical findings, but I think that it lacks actual experiments (GNN and GNTK accuracy, real-world and toy) to convince me that this setting is relevant to real-world GNN tasks. As such, I find this work to be of interest to the TMLR audience, but the claims and evidence are only convincing within the specific theoretical setting; extensions to real GNNs / datasets aren't very compelling.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper analyzes deep ReLU or linear GNNs in the Neural Tangent Kernel (NTK) regime under the Degree Corrected Stochastic Block Model (DC-SBM). The authors measure class separability of the NTK (mean absolute difference between in- and out-of-class entries) which is suggested to be indicative of the respective GNN, and establish that\n\n* Linear GNTK has class separability equal or better to those of the ReLU GNTK;\n\n* Row normalization aggregation has better class separability than other alternatives;\n\n* Class separability degrades slowest with depth for row normalized aggregation GNTK (yet degrades to random chance at infinite depth).\n\n* Skip connections allow GNTK to not degenerate at infinite depth and preserve class separability.\n\nThe authors perform some preliminary experiments to establish the claims on two real datasets, suggesting that presented theory could explain why in prior works linear GNNs have performed on par with ReLU GNNs, and why row normalization sometimes empirically outperforms symmetric normalization.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "* To demonstrate best agreement with theory, I believe Figure 1 and 2 should include results for depth $d = 1$. It is common for any dataset and architecture combination to have a depth sweet spot where accuracy falls off monotonically to both sides of the ideal depth (see for example https://arxiv.org/pdf/2010.09610.pdf), and I wonder if $d = 2$ could just happen to be the best accuracy for *Cora* for reasons unrelated to the theory.\n\t\n    * Highly-optionally: results would look even more robust if full range of depth up to 8 were evaluated.\n    \n* Moreover, could you extend your analysis and all experiments to depth $d=0$ NTK / GCN? My potential concern is that at $d = 0$ class separability of the kernel might be good, while empirical performance of such shallow GCNs may be lacking, which also risks invalidating the theory.\n\n* I wish all plots demonstrating kernel class separability were accompanied by the actual performance (accuracy, mean squared error) of the respective exact / population NTK(s) (and, optionally, even GNNs) on the graph(s). In addition or alternatively, I wish it was spelled out in more detail / more formally why the kernel class separability as defined in section 3 is the metric most predictive of performance (i.e. why look at the in-out class entries absolute difference and not say their ratios, squared distance or some other properties of these matrices).\n\n\t* Further, could class separability of the kernel be measured on the Cora dataset, to plot along Figures 1 and 2 to further validate the theory?\n\n* Page 10, \"Infact\" -> \"In fact\"", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "X0TLf1xSIV", "reviewer": "Reviewer_X5F1", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper appears to cite a good amount of relevant literature.\n- The problem and content of this paper is likely to be of interest to the TMLR community.\n- The results and flow of the paper are mostly well presented, and the theorem statements are relatively clear. I did not check the proofs in the appendix.\n\nWeaknesses:\n- Precision can generally be improved. For example, the notation $\\dot{\\sigma}$ is used for the derivative in the notation section. However, the ReLU activation, which does not admit a classical derivative, is mentioned earlier and throughout the text. Then, in Theorem 1, a statement is made iinvolving $\\dot{\\sigma}$. It is not clear whether the authors intend to claim that this theorem applies to the ReLU, since no qualification on $\\sigma$ is provided in the theorem conditions. If the authors are claiming that this theorem applies, how should one understand $\\dot{\\sigma}$?\n- Assumption 1 seems very strong to me. If $X \\in \\mathbb{R}^{n \\times f}$, does $X X^\\top = I$ require that $f \\geq n$, i.e. the dimension of the node feature is greater than the number of features? Even under this requirement, one still then requires the features to be orthogonal, which seems implausible and also not expressive. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors use the machinery of the neural tangent kernel to attempt to understand the influence of convolutions based on graph Laplacian with row normalisation. Specifically, they prove that linear networks capture class information as well as ReLU,row normalisation preserves underlying class structure better than other convolution choices, performance decreases with network depth and skip connections retain class information even for infinitely deep models. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please address the weaknesses I mentioned above.", "broader_impact_concerns": "I do not have any immediate broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "phtATcpXMc", "reviewer": "Reviewer_K9MK", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. This analysis is quite novel, from my understanding. The contributions are significant and attractive to the graph neural network community.\n2. The analysis seems solid, and the conclusions look correct.\n3. The framework is general because it can cover homophilous/heterophilous graphs, graphs with skip connections, and different GCNs. \n\nWeaknesses:\n1. Some claims and discussions are not clear or rigorous. For example, in the paragraph on page 7 titled \"Comparison of graph convolutions\", it is very unclear how you make the comparison by saying whether the kernels are affected by $\\pi$ or not. Actually, whenever you want to have some discussions by comparing kernels, I feel the reasoning is not very rigorous, although there are supportive experiments. Another example is right below Figure 4 on page 8; what does it mean by \"the population NTKs converge to a constant kernel, **thus** 0 class separability for all the convolutions\"? I thought the class separability r should be a given condition for the analysis. Why does it read like a result by \"thus 0 class separability\"?\n2. It is interesting to cover the analysis of heterophily. However, it seems the experiments are only implemented on Cora and Citeseer, which are homophilous graphs. Why not verify the effect of heterophily, even if you use synthetic graphs?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "1. This paper provides a more general result of NTK of GCN for node classification settings. The analysis covers multi-layer GCNs for multi-community, homophilous and heterophilous graphs.\n2. Theoretically and empirically, The paper studies the comparisons between linear GCN and Relu GCN and between different graph convolutions. It also shows an explanation of over-smoothing from the NTK perspective.\n3. This work also covers the analysis of skip connections of GCNs using NTK.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I will consider a higher final score if the following can be addressed.\n\n1. Please examine the logic in Section 5 and improve the presentation.\n\n2. The introduction to the random graph model in Section 3 also needs improvement. For example, I don't understand what \"degree correction vector\" means.\n\n3. Linear GCN is confusing to me at first. Later I realized it refers to SGC. If you want to give it a new name, please clarify it.\n\n4. Some related works of generalization or NTK analysis for GNNs are missing. Please include them in the related works. \n[1] Cong et al., 2021, \"On Provable Benefits of Depth in Training Graph Convolutional Networks.\"\n[2] Li et al., 2022, \"Generalization guarantee of training graph convolutional networks with graph topology sampling.\"\n[3] Tang et al., 2023, \"Towards Understanding Generalization of Graph Neural Networks.\"", "broader_impact_concerns": "There are no concerns on the ethical implications of the work. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper cites a good amount of relevant literature, but I think there is still room for improvement. A novel contribution of the paper is to apply signal propagation (propagation of NTK from layer to layer) to analyze properties (e.g., expressivity) of graphical neural networks. There is a line of work, dating back to 2016, that uses this technique (signal propagation) to analyze expressivity, spectrum, and trainability of neural networks. A partial list of them includes: 1. MLP (https://arxiv.org/abs/1606.05340, https://arxiv.org/abs/1611.01232), 2. residual networks (https://arxiv.org/abs/1712.08969), 3. CNN (https://arxiv.org/abs/1806.05393), 4. RNN & LSTM (https://arxiv.org/abs/1806.05394, https://arxiv.org/abs/1901.08987). 5 general deep networks (https://arxiv.org/abs/1912.13053), 6. Tensor programs  (https://arxiv.org/abs/1910.12478, cited in the paper). It would be good to discuss the connection between the current work and the above work, bridging the two communities.
Decision: Accept (poster)