A Convergence Analysis of Gradient Descent on Graph Neural Networks
Authors: Pranjal Awasthi
Abhimanyu Das
Sreenivas Gollapudi
Venue: NeurIPS 2021 Poster (2021)
Keywords: Learning Theory
Graph Neural Networks
Convergence Analysis

Abstract: Graph Neural Networks~(GNNs) are a powerful class of architectures for solving learning problems on graphs. While many variants of GNNs have been proposed in the literature and have achieved strong empirical performance, their theoretical properties are less well understood. In this work we study the convergence properties of the gradient descent algorithm when used to train GNNs. In particular, we consider the realizable setting where the data is generated from a network with unknown weights and our goal is to study conditions under which gradient descent on a GNN architecture can recover near optimal solutions. While such analysis has been performed in recent years for other architectures such as fully connected feed-forward networks, the message passing nature of the updates in a GNN poses a new challenge in understanding the nature of the gradient descent updates. We take a step towards overcoming this by proving that for the case of deep linear GNNs gradient descent provably recovers solutions up to error $\epsilon$ in $O(\text{log}(1/\epsilon))$ iterations, under natural assumptions on the data distribution. Furthermore, for the case of one-round GNNs with ReLU activations, we show that gradient descent provably recovers solutions up to error $\epsilon$ in $O(\frac{1}{\epsilon^2} \log(\frac{1}{\epsilon}))$ iterations. 


A Convergence Analysis of Gradient Descent on Graph Neural Networks
Pranjal Awasthi Google Research pranjalawasthhi@gogg com
Abhimanyu Das Google Research abhidas@google..om com
Sreenivas Gollapudi Google Research
sgollapu@google. com
Abstract
Graph Neural Networks (GNNs) powerful class of architectures for solving learning problems on graphs. While many variants of GNNs have been proposed in the literature and have achieved strong empirical performance, their theoretical properties are less well understood. In this work we study the convergence prop- erties of the gradient descent algorithm when used train GNNs. In particular, we consider the realizable setting where the data is generated from network with unknown weights and our goal is to study conditions under which gradient descent on a GNN architecture can recover near optimal solutions. While such analysis has been performed in recent years for other architectures such as fully connected feed-forward networks, the message passing nature of the updates in GNN poses new challenge in understanding the nature of the gradient descent updates. We take step towards overcoming this by proving that for the case of deep linear GNNs gradient descent provably recovers solutions up to error e in (log((1/e) iterations, under natural assumptions on the data distribution. Furthermore, for the case of one-round GNNs with ReLU activations, we show that gradient descent provably recovers solutions up error in O log(? ()) iterations.
Introduction
In the last decade, deep neural networks have been successfully used for variety of machine learning tasks. In particular, optimization of various deep neural network architectures using gradient descent has been empirically (and in some cases, theoretically) shown work surprisingly well, with an ability to obtain small training error on a variety of problems and datasets. In this paper, we focus on particular class of neural network architectures known Graph Neural Networks (GNNs).
Graph Neural Networks (GNNs) have become a popular choice for machine learning tasks with graph structured data [Hamilton et al., 2017, Kipf and Welling, 2016, Veličković et al., 2017]. Computation in GNNs is performed by each node sending and receiving messages along the edges the graph, and aggregating messages from its neighbors to update its embedding vector. After a few rounds of message passing, the computed node embeddings from all the nodes are aggregated to compute the final output [Gilmer et al., 2017]. This leads to simple and elegant architecture for variety of graph-related problems in practice.
While theoretically understanding the optimization, learning, and generalization properties of deep neural networks is challenging task in itself, our current understanding GNNs lags significantly behind their more popular counterparts such fully connected feed-forward networks and convo- lutional neural networks (CNNs). the context of GNNs recent theoretical works have focused on questions such as the representation power of various GNN architectures [Xu et al., 2019b,a, Loukas, 2020a,b] and establishing generalization bounds [Garg et al., 2020], However, the optimiza- tion properties of GNN architectures are less explored. These involve identifying conditions under which algorithms like gradient descent can shown to be provably effective in optimizing GNNs.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Such analysis has been carried out in recent years for fully connected feed-forward networks and CNNs, mainly restricted to depth-2 2 non-linear networks or deep linear networks |Ge al., 2017, Andoni et al., 2014, Bartlett et al., 2017, Arora et al., 201 8a, Hardt and Ma, 2016]. However, the message passing nature of GNNs makes it harder to theoretically analyze the optimization problem in GNNs, compared to other neural network architectures.
We provide the first convergence analysis of gradient descent for GNNs, and provably show that gradient descent can recover near optimal solutions. We first consider the case of a one-round (or one hidden-layer) GNN with ReLU activations. This scenario already captures much of the complexity of the problem, in particular allowing for multiple local optima. Following standard assumptions made in the case of analyzing feed-forward networks, we show that when the input data distribution the standard Gaussian distribution, and the training objective is to minimize least square regression loss, gradient descent converges to the population error of E in O 1 log())) iterations. In particular, our analysis applies to the standard practice of initializing the network with weights from a Gaussian distribution, and we do not perform any complicated pre-processing step to initialize the network.
We then extend our result to the multi-round (or multi-layer) case, but for the case of linear activations (analogous the setting for deep linear networks [Arora al., 2018a, Bartlett et al., 2018)). In this case, we show a Stronger convergence result; gradient descent converges to an error e in (log(1 [))) iterations. All our results are for the realizable setting, i.e, we assume that the data is indeed generated by an (unknown) underlying GNN, as is typical in analysis of gradient descent for other network architectures (see the discussion of related work in Section A). The rest of the paper is organized as follows. In Section 2 we set up notation and discuss the model of GNNs that we consider. In Section 3 we present our first main convergence theorem for the case of one layer/round GNNs with ReLU activations. This is followed by our second main result on analyzing deep linear GNNs in Section 4. We conclude with discussion and open problems in Section 6. We discuss the most relevant related works in individual sections (Section 3 and Section 4), and provide more comprehensive survey of related work in Section A.
2 Preliminaries
Graph Neural Networks operate via passing and aggregating messages among the nodes of a graph. Given an undirected unweighted graph G = (V, E), let n = |V] be the number of nodes in the graph and m = |F]] be the number of edges. Initially each node i E [m] is initialized with its own private embedding I; E IR", where r denotes the embedding size. Then the computation in a GNN proceeds in number of rounds where at round l, the new embedding æf for vertex is obtained via a combination of aggregate and combine steps Gilmer et al. [2017] shown below.
= AGGREGATE(12) (La) R-1 8-1 (()))
(1)
COMBINE (6-1) ..)).
(2)
Here N(1) is the neighborhood of vertex i. When comparing to standard architectures such as foed-forward networks, it useful think of a round of message passing as computation performed by one layer of a more standard architecture. Hence an f-round GNN shouldbe thought of as a network with hidden layers. Different choices of the aggregate and combine operations lead to different versions of GNNs such as graph convolutional networks (GCNs) [Kipf and Welling, 2016], GraphSAGE [Hamilton et al., 2017], and graph isomorphism networks (GINs) [Xu et al., 2019b] to name few. The aggregate operation is typically a simple pooling operation such as the sum or average, and the combine operation is implemented via low depth neural network. Furthermore, in the most popular implementation, i.e, GCNs, the network parameters are shared across the different rounds. This setting will also be the focus of study our work. In particular we consider two problem settings. In the first case (Section 3) we assume that the number of rounds in the GNN is one (i.e. one hidden layer) and that the combine operation is a depth one network with ReLU activations. In the second setting (Section 4) we consider arbitrary round L GNNs but restrict the combine operation to be a linear network. In both the settings we will assume that the aggregate operation is a sum, and that the initial input embeddings for the nodes are drawn from the standard Gaussian distributions, i.e., N No, I, Finally, our analysis for the case of ReLU activations will rely crucially on the notion of dual activations and their properties that we recap below.

---

will assume that [[w]]] |I = and again our results extend Definition ([Daniely et al., 2016)). The dual activation of is the function ē [-1, H R defined as
( = =
(3)
where X and Y are jointly Gaussian random variables with mean, zero variance one, and covariance p.
The work of Daniely et al. [2016] showed that dual activations satisfy many nice properties such as continuity [-1, 1] and the fact that they are convex [0, 1]. For more extensive list of the properties of the dual activations please refer to Lemma 11 in Danicly et al. [2016].
3 One round GNNs with ReLU activations
In ths section we present our main result on convergence of gradient descent for learning an unknown one round GNN with ReLU activations. We consider a graph G = (V, F)) with nodes and maximum degree d. Furthermore, we assume that there is an unknown GNN generating outcomes as
y
(W R.),
(4)
where ã; = B E() Iy and each x, is drawn i.i.d from (0, Irxr), and (t) = 22 max(t, 0). In other words, the aggregate operation is a sum, and the combine operation is depth-1 neural network with ReLU activations that produces an h-dimensional embedding for each node, where is the number of hidden units (inner dimensionality of W*). Finally, the embeddings of all the nodes are summed up to produce an h-dimensional output for the graph G.
The /2 factor multiplication to the ReLU function is for technical convenience and does not affect our results. The ground truth matrix W* is an h x r matrix where we denote wi,- w,, to be the rows of W Without loss of generality easily to the case when ||w with unknown parameter matrix W to minimize the following loss via gradient descent.
|I is bounded for all, j (see Appendix B). We train another one round GNN
L(W)- 2
[110 =
(5)
2 Bll
Σ (Wa:) - Σ oW |1
(6)
h Σ
n
n
r [w) m.)
Σ
r (wj =I
j=1
We will analyze the following gradient descent updates.
W+1 = W. v/V).
Here VL(W) denotes the gradient of the population loss and as is common in practice, we assume that the entries of the matrix W are initialized i..dd from a Gaussian distribution. We are now ready state main theorem below.
Theorem 1. Let W be the unknown parameter for one-round GNN in Eg. (4) with ||z = 1 for j E [M], and let L(W) denote the population loss at W as defined in Eq. (5). If the degree d of the graph is o() then for any 1). Wf NO, with probability at least 1 - h e wee have that L(Wr) < è² provided T 2 c. (d+3(d+1)
log( nh for absolute constants c, c' > 0.
Several remarks are in order regarding the above theorem. Note that the convergence rate is 0 log( !) as function of the desired error, and is polynomial in the other problem param- eters such as the number of nodes, the maximum degree of the graph, and the dimensionality of the W* matrix. In the context of feedforward neural networks, gradient descent based algorithms have been analyzed primarily in the Neural Tangent Kernel (NTK) regime where an unknown target is leamned by performing gradient descent a highly over-parameterized network [Jaott et al., 2018.
3

---

Du et al., 2018, Daniely, 2017, Allen- et al., 2019]. The advantage of such an analysis is that it can be carried out for large depth neural networks (at least for smooth activations). However. due to the massive overparameterization the gradient descent updates move extremely slowly and the dynamies correspond to performing kernel regression a very high dimensional space [L.ee et al., 2019b, Arora et al., 2019b]. This is quite far from the behavior of gradient descent in realistic settings. We, on the other hand are interested in the setting where there is an unknown network generating the data and one would like to learn it via gradient descent with only mild pere-prraettrizationn. In particular, even the simple problem setting we consider in this section captures important aspects of the complexity of the general problem, in particular allowing for multiple local minima.
There have been recent efforts in going beyond the NTK regime for the case of feed-forward networks. Similar to our setting, these works assume that the input is generated from the Gaussian distribution. Furthermore, these works still either need some over-parameterization to argue convergence [Li et al., 2020], or need to add appropriate regularizers to the squared loss objective [Ge et al., 2017].
In contrast, an interesting aspect of our result is that we do not need any additional over- parameterization and learn the unknown GNN using another network of the same size. The recent work of Zhang et al. [2020] studied model for GNNs similar to our setting in Eq. (4) and designed a learning algorithm that first initializes the network weights based on a tensor decomposition subrou- tine, followed by an accelerated gradient descent procedure. We on the other hand do not perform any special initialization based on techniques such as spectral methods and analyze gradient descent updates starting from Gaussian initialization. The model of GNN we consider in Eq. (4) also bears similarity to the model of overlapping patches considered in the work of Du et al. [2017] in the context of convolutional neural networks. The authors analyze the convergence of gradient descent under certain strong assumptions on the correlation among the different patch distributions. We on the other hand make no such assumptions. Furthermore, even in the case of feed-forward networks, current analysis in the non-NTK regime do not extend beyond one hidden layer. Hence our work brings the understanding of gradient descent for GNNs on par with that of feed-forward networks.
We next present the main ideas and key lemmas behind the proof of Theorem 1.
3.1 Expressions for loss and gradients
In this section we first compute simplified expressions for the loss and the gradients that will be useful in subsequent analysis. We first begin by writing an equivalent expression for the population loss. We have
1 Ly( = _ E 2
(wy T=))a=] + E (wy T a.)) - E Σ oww T 2.)o(w; a.
Notice that each wi evolves independently and hence we can simply focus on the convergence of (wy) to L3 (xxz). To simplify the above expression we will make use of the dual activation function of (-) from the work of Daniely et al. [2016] re-stated in Definition 1. For simplicity in this section we assume that the degree of each node is exactly d. The case when degree is at most d follows with minimal changes and is presented in Appendix B. Notice that each H; is a sum of d + 1 messages, one involving the node and the other messages involving neighbors of Hence, I; is a random variable distributed as N NO, (d + 1)7). Furthermore, for any i + define di,j to be the number of common messages between Z; and Zy. If = j. then we define di,j = di = d d++ 1. We next compute expressions for each of the three terms above.
o (w, 21)) E
Σ
olu, (w,))(w,, Ta,))
i=1
1-==
= [dd [ 1)]| wy
Σ a
w; T x
wj Z Vid 1)1lwal
Vid + 1)|
i-==
0( dis d d+1
= -d 11)][/1b1/
Σ
(definition of the dual activation in Eq. (3)).
(9)

---

Similarly we get that,
n
di,j
E (w) x,)) = (d+ - 1))3 112
Σ
5
(10)
d+1
s-=1
Finally we simplify the last term.
w T
E
a(wy "1)o(("3" 2,)] = E [d+ 1ylاا|lllu
o(
wj I;
10(
Vid + 1) 1)112051 |1
(d + 1) 10g
1
d W w
= (d + 1) ||ااا||
Σ
6(
(1I)
d 1 || 103
w=
Combining the (9), (10), and (11), we have
1 L(w;)) 2 (d + 1)]lwy1 11
dij
++ 1
0( dig
2 dd+ + 1)||wu311
d+1
d+1
i,j=1
di
Wj =
(d + 1) 1)]1 ||w|||
(12)
+
1
||0, |l|
1,=1
is easy to see that if wo,, is the initial value of wy then each subsequent iteration will be linear combination of wo,, and w.. Hence we can assume that W/ = aw3 + fBwtt, where w, is a fixed unit vector (depending a, B and recalling that ||w || = 1 we get the simplified expression:
the initialization) orthogonal to wj. Then re-writing the loss in terms of
n
dis ) + 1 (d+
n
0( di
3) = (d 1)(a² + 82)
Σ
d+1'
d+1
f,1=1
i-=1
- -dd+1) 02 + fa
de,j
a
(13)
d+1
Va² + 32
41=1
In the rest of the section we will analyze the evolution of the updates of and 3. Furthermore we will use (t,, 3r to denote the parameters a, 3 associated with the iterate Wzet at time I. We first compute the gradient of the objective w.r.t. w or equivalently w.r.t. a, 3.
aL B) da
α
Σ δ di.j
a
11)+1)
(d+1)
d+1
Va2+30
d
1+1
1
v
a + 3
11=1
i==1
B2
dij
8'( dij
(d 1)
a²
+ 32
d+1 d+I a2 32
dij
1l
Σ
(d+1)
Σ 0
d
V az + 3
i-
B2
di
dij
Saep
(14)
a² + 32
d+1
d V
a² 3
Here in the last equality we have used the fact that à' â' and that d' d'(x) 221 2 0) = s (z), where sup (x) is the step function. See [Daniely et al., 2016) for a proof. Similarly we get that
aL(a, B) 1(d+1)
3
d
(d+1)
03
d
d+1
Va² +
32
d+1
a² + p
j-
aB
(d 1)
Σ
dij
step
dij
a
(15)
3
d d+1
d
V
T,==
5

---

3.2 Bounding the iterates.
In this section we show that if the initial weight Wo,j is drawn from 2(0,0²1) then with high probability, the iterates remain bounded for all subsequent time steps. We first analyze how the length of w. i.c., | behaves over period of time, In the rest of the proof we will often use the shorthand A, Be, Ct to denote the following key quantities that depend on the structure of the graph.
di
A =
d++
ff=1
dij
B.
Σ
d d+1 14
iJ=1
dii at step
C
+ 1 l
Here & denotes the length of the iterate wy time i.e., |||l| Voz 3 The above quantities satisfy useful inequalities that will be used throughout the analysis. For example, we note that A, B, are always non-negative when = olv and ar 2 O. We also have I - [B A and
|C,| = ((A). See Appendix for the proof.
Lemma 1. If Wo.j ~ ((0 o²1) and E li6n(d1]A oτ(d+1āa then with probability at least
1 e O()) it holds that for all t 2 0, & S 2T + 4m + 1, and & 2 36s for all t 2 1.
3.3 Establishing smoothness and analyzing initial updates
We first show that if the condition Lemma holds, then throughout the trajectory of the iterates, the loss function is smooth. This is formalized in the lemma below.
Lemma 2. If the degree d of the graph of on) and the conditions in Lemma I hold, then for all t t 1 and any 7 E [0, 1] such that (a, B) = (1 ()),, Br) + 1, Be41), we have that
Amax (LL((,))) S 4(d 1)A(1+ 22 + 4x +1 +1+ o(1)
Here Amax is the maximum eigenvalue of the population Hessian denoted by VLL(a, 3). Our overall proof strategy is to show that the that the squared norm of the gradient lower bounds the loss value any iterate. This will let us easily analyze convergence of gradient descent via standard arguments. However challenge is that since we are starting from random initialization, the condition does not hold true at the beginning. result we separately analyze an initial phase of the algorithm and show that gradient descent very quickly escapes region where the PL. condition does hold. This formalized below.
(PL) condition [Polyak. 1963] holds, namely
Lemma 3. If wo.j ~ o0),o21) and 1 E [om(d41)A 6*(d+1)A then with at least 1 - 1/h², it holds that for all 2 clog(a log h)) o 2 100 and l, o(1), where
is an absolute constant.
3.4 Establishing the PL-condition
Finally, using the above lemma show that under the conditions of Lemma the iterates w. (on, Br) satisfy the Polyak-L.ojasievin inequality [Polyak, 1963].
Lemma 4. If the degree d of the graph is of ni) and the conditions in Lemma I hold then there is
an absolute constant e > 0, such that for all 2 clog(a log h) and e E (0, 1), either [3:] S Thn and
||e, -1ll < + have that
(TL(a1,))1122 p¹ L(ar,
where 11" 380[2+1]k

---

3.5 Putting everything together
Finally, we combine the analysis from the previous sections prove the main theorem, i.e., Theo- rem 1.
Proof of Theorem I. We will analyze an arbitrary [h] and the evolution of the corresponding wy vector. By setting a we have from Lemma 2 that the smoothness parameter of the loss function is
L + 1)A(+))1(1 + 4T + +3+
Hence we get that for any t 2 0,
Ly(w,,+1)) & (,(W,,)) VL,(w5,)) -wj.e) + I, 110,,041 - w0,ell
S LاWير))) - 7/ (1,,, 72L VL, (wW,,)))
(,(,,,) - (w) nL
(16)
2
From the range of 7 in Lemma we get that n2 - 1. Furthermore, using Lemma we can write
Li(10,+11) 1) (,(w,)) (L wgs1) + |100,411 worll
$ (,( (1-1F²)
$ Ly(,,,)) 7/12
(17)
(d log( mb) time steps we will either have Ls(W)e) S e/hh, or that |3,1 S Thn and [|: 1|| Thn The latter implics that
Hence after T 2 c.
||w5,
- [wjje-w31
v 2hn
Furthermore, it is easy to see that
(y(w;,)) S n(n - 1) |1,,, wz 11
Hence if the latter happens then again, (uW,,) - e² thereby implying that L(Wr)) S e.
Deep linear GNNs
In the previous section analyzed one round GNNs with ReLU activations. Analyzing the dynamics of gradient descent beyond one layer (in the non NTK regime) with non-linear activations is a challenging problem, even for standard network architectures. Hence, in this section consider deep linear GNNs in order to analyze the dynamics of gradient descent in deeper message passing architectures. Linearity has been a commonly studied setting in recent years for analyzing deep feed-forward networks [Hardt and Ma, 2016, Bartlett et al., 2018, Arora et al., 2018a].
We assume the existence of unknown L-round GNN characterized by dositive-definite symmetric matrices Wf, W e R' xr, Given node inputs Z1,..., In (0, Ixxr) the embedding of node at round > 1 is defined
(6) AGGREGATE (10 :JE ((N()) W a:
Σ ((-1) 2.
(18)
JEN(()
COMBINE((("
Wi (L-1) a
(19)
Notice that this is a more general setting than the case of ReLU network studied in the previous section where the aggregate was simple summation operation. In this section case where both the aggregate and combine operations have their own set of parameters WT and W3. Finally, the output of the network input J (I), ( Fn is defined
analyze the

---

As in the case of ReLU activations from the previous section, we will analyze the non- overparameterized case where another architecture of the same size used to learn the unknown ground truth network. Given another L-round GNN defined by parameters W1, W2 we define the population loss as
L(W, W2)
2 E
[IIC -3]
(20)
E III (L)
(21)
2
1=1
We will analyze the gradient descent updates defined as
W1,++1 11,1 LWW,,, W2,e)
(22)
W2.+1= = W2.2 WWW... W2,1).
(23)
For ease of interpretation, we state our main theorem below for the case when each node in the graph has degree exactly d. The general theorem is stated in Appendix C and achieves similar rate of convergence. The theorem below shows that if the network parameters are initialized at identity, i.c. W1,0, 22 = I, then gradient descent minimizes the population loss at polylogartimmic rate.
Theorem 2. Let the initialization of W1, 1,0, W2 be identity. Then, 1.W,T W2,r & e if.
1
-Iu;((1-o;)) (1-0,00)
T2 max
iE[ni 7o (d + 1)62L-2 log(
(24)
(1- min(1, (o,))(-))
n = no S min
(25)
2n.2(0.)) 1)u 3 w:)
Here of is the ith smallest singular value of W1 + dW2,, and u, Eg and o, depend only on of
We make a few comments about the theorem above. Notice that unlike the case of ReL.U networks
we do not assume any bound on the maximum degree of the graph and the theorem applies generally. Furthermore, the convergence rate is logarithmic in 1 and exponential in the depth 7. of the network. The dependence degree d is polynomial and appears via the bound on the maximum singular value of the matrix Wi + dW: Our analysis for the case of equal degrees proceeds by showing that it is enough to track the evolution of the singular values og, of the matrix M, = W1, + dW2,1 at each time step. We then show that is is sufficiently small then the singular values da., will converge to the singular values of of the true unknown matrix Wi + dW2. Handling the case of unequal degrees is along similar lines but is technically more challenging values of W1, and W2, separately. See Appendix C for details.
the number of nodes in the graph is linear and the dependence on the maximum
need separately track the evolution of the singular
5 Experiments
In this section we verify our theoretical results via simulations. Our first goal is to understand whether the 1 rate of convergence obtained for the case of one round ReLU GNNs is tight, or whether in practice we can obtain polylog( { rates even for the ReLU setting. Secondly, we understand via experiments the regime where the degree of the graph d exceeds vnt and hence our theoretical results for the case of ReLU GNNs do not hold. In order to do this we generate random d-regular graphs over 100 nodes. For the case of one round GNNs with ReLU activations size r = 10, and h- = 10 (number of hidden units in the ReLU GNN), We use the same value of r for the case of deep linear GNNs, where equals the input dimensionality and also the dimensionality of the matrices WT, and Wg-
set the embedding
We generate an unknown ground truth network in the case of ReLU GNNs by choosing each column of W to be a random unit length vector. For the case of linear networks we generate positive definite matrices W W by picking random Gaussian entries, and then adding small multiplicative factor of 0.001 times the identity matrix. As dictated by our theory, we initialize network weights from standard Gaussian for the case of ReLU networks, and to the identity matrix for the linear case.
8

---

0-10
Loss
350
50-
200
400
500
500
1002
Mum Itrrations
Figure 1: Loss vs, number of iterations of gradient descent for one round GNN with ReLU activations.
20
1003
lteration
Figure 2: Loss vs. number of iterations of gradient descent for deep linear GNNs.
We simulate population gradient descent and implement our networks using the JAX programming language [Bradbury et al., 2018J. Our experiments are run using one GPU. See Section D for further details.
For the case of ReLU networks we run gradient descent on instances with varying values of the degree d. In particular we vary the depth L. in (1, 2, 3). Finally, in each case we plot the loss value (&2 loss) vs. the number of iterations. The results are shown in Figure and Figure 2. We make few remarks about the experiments. Note that the convergence rate for the case of linear networks is indeed much better than the case of ReLU GNNs and hence we, in general, do not expect significantly better rates of convergence than the ~ - bound that we prove. An interesting observation is that as d increases and close the regime of ((n). the rates of convergence of gradient descent for the case of one round GNN with ReLU activations, become much better. This is along expected lines, since if d = - 1, i., the graph a complete graph, then the network in Eq. (4) boils down to h independent single ReLU units with standard Gaussian inputs. It is known for this extreme setting that gradient descent has a logarithmic convergence in 1 [Soltanolkotabi, 2017]. Hence, extending our existing theoretical analysis beyond the vn degree setting is an interesting open question.
present results for d (5, 10, 30, 80, 99). For the of linear networks
Conclusions
The main question left open by our work is analyze the gradient descent updates for multi-round GNNs with ReLU activations. Given the difficulty of analyzing gradient descent for multi-layer networks beyond the NTK setting, the above seems like a challenging problem. It would also be interesting to explore whether the convergence rate for the case of one round GNNs can be improved via over-parane pver-paramtterzzaionn Finally, it would also be of interest to extend our results to more general distributions going beyond the Gaussian setting. Another fascinating question is to analyze gradient descent the agnostic setup. the best one round GNN with ReLU activations (or deep linear GNN) achieves an error of OPT on the data distribution, can gradient descent recover network of error (OPT)? This style of analysis has recently been carried out the case of a single ReL.U unit [Frei et al., 2020].

---

Acknowledgments and Disclosure of Funding
Funding in direct support of this work: Google Research.
References
Z. Allen-Zhu and Li. Backward feature correction: How deep learning performs deep learning. arXiv preprint arXiv:2001.044133 2020.
7. Allen-Zhu, Y. Li, and Z. Song. A convergence theory for deep learning via over-parametteriaaton. arXiv preprint arXiv: /8/ /.0962,, 2018.
7. Allen-Zhu, Y. Li, and 7. Song. A convergence theory for deep learning via over-parameterizztion.. In International Conference on Machine Learning, pages 242-252. PMLR, 2019.
A. Andoni, R. Panigrahy, G. Valiant, and L. Zhang. Learning polynomials with neural networks. In International conference on machine learning, pages 1908-1916. PMLR, 2014.
Arora, Cohen, Golowich, and Hu. A convergence analysis of gradient descent for deep linear neural networks. arXiv preprini arXiv: (xXiv:///000228/ 201 8a.
Arora, N. Cohen, and E. Hazan. On the optimization of deep networks: Implicit acceleration by overparameterization.. In ICML, pages 244-253, 2018b.
S. Arora, N. Cohen, W. Hu, and Y. Luo. Implicit regularization in deep matrix factorization. In Advances in Neural Information Processing Systems, pages 7411-7422, 2019a.
S. Arora, S. Du, W. Hu, Z. Li, and R. Wang. Fine-grained analysis optimization and generaliza- tion for overparameterized two-layer neural networks. In International Conference Machine Learning, pages 322-332. PMLR, 2019b.
S. Arora, S. S. Du, W. Hu, Z. Li, R. Salakhutdinov, and R. Wang. On exact computation with an infinitely wide neural net. In NeurlPS, 2019c.
A. Bakshi, R. Jayaram, and P. Woodruff. Learning two layer rectified neural networks in polynomial time. In Conference on Learning Theory, pages 195-268. PMLR. 2019.
Bartlett, D. Helmbold, and P. Long. Gradient descent with identity initialization efficiently learns positive definite linear transformations by deep residual networks. In International conference machine learning, pages 521 521-530. PMLR, 2018
P. L. Bartlett, D. J. Foster, and M. J. Telgarsky. normalie margin bounds for neural networks. In Advances in Neural Information Processing Systems, pages 6240- (2000-624,,00 2017.
J. Bradbury, R. Frostig. P. Hawkins, M. Johnson, C. Leary, D. Maclaurin, G. Necula, A. Paszke,
J. VanderPlas, S. Wanderman-Milhg and Q. Zhang. JAX: composable transformations of Python+NumPy programs, 2018. URL http: / //gg/ttttbuu/..// com/google//
S. Chen, A. R. Klivans, and R. Meka. Learning deep relu networks is fixed parameter tractable. arXiv preprint ar 0rXiv:2009.1335 13512, 2020.
L. Chizat and Bach. On the global convergence of gradient descent for over-parameterized models using optimal transport. arXiv preprint arXiv: 080500955, 2018.
A. Daniely. Sgd learns the conjugate kernel class of the network. arXiv preprint arXiv: 2017.
A. Daniely, R. Frostig, and Y. Singer. Toward deeper understanding of neural networks: The power of initialization and dual view on expressivity. arXiv preprint arXiv: 1602.00877 2016.
I. Diakonikolas, D. M. Kane, V. Kontonis, and N. Zarifis. Algorithms and sq lower bounds for pac learning me-hhddee-llaer relu networks. Conference on Learning Theory, pages 1514-1539. PMLR, 2020.
10

---

S. S. Du. J. D. Lee, and Y. Tian. When is a convolutional filter easy to leam? arXiv preprint arXiv:1709.06/29, 2017.
S. S. Du, X. Zhai, B. Poczos, and A. Singh. Gradient descent provably optimizes over-parameterized neural networks. arXiv preprini urXi::181000204, 2018.
Frei, Y. Cao, and Q Gu. Agnostic learning of single neuron with gradient descent. arXiv preprint 20X1::2005.14426, 2020.
V. K. Garg, S. Jegelka, and Jaakkola. Generalization and representational limits of graph neural networks. ICML, 2020.
R. Ge, J. D. Lee, and T. Ma. Learning me-hidden-layee neural networks with landscape design. arXiv preprint arXiv: 1.Xiv:/711..000111 2017.
R. Ge, R. Kuditipudi, 7. Li, and X. Wang. Learning two-layer neural networks with symmetric inputs. 2018.
arXiv preprint 1
J. Gilmer, S. S. Schoenholz, P. F. Riley. O. Vinyals, and G. E. Dahl. Neural message passing for quantum chemistry, arXiv preprint 17Xiv:170..01222, 2017.
Goel and A. R. Klivans. Learning neural networks with two nonlinear layers in polynomial time. In Conference Learning Theory, pages 1470-1499. PMLR, 2019.
W. Hamilton, Z. Ying, and J. Leskovec. Inductive representation learning on large graphs. In Advances in neural information processing systems, pages 1024-1034, 2017.
M. Hardt and T. Ma. Identity matters in deep learning. arXiv preprini arXiv: 2016.
A. Jacot, F. Gabriel, and C. Hongler. Neural tangent kernel: Convergence and generalization neural networks. arXiv preprint 1rXi::1806.07555 2018.
M. Janzamin, H. Sedghi, and A. Anandkumar. Beating the perils of non-convexity: Guaranteed training of neural networks using tensor methods, arXiv preprint arXiv:/506.000m 08443, 2015.
T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint
2016.
J. Lee, L. Xiao, S. Schoenholz, Y. Bahri, R. Novak, J. Sohl-Dickstein, and J. Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. In NeurlPS, pages 8570-8581. 2019a.
Lee, L. Xiao, S. Schoenholz, Y. Bahri, R. Novak. J. Sohl-Dickstein, and Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. arXiv preprint arXiv:1902.067200 2019b.
Y. Li and Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data. In NeurlPS, pages 8168-8177, 2018.
Y. Li and Yuan. Convergence analysis of two-layer neural networks with relu activation. In Advances in neural information processing systems, pages 597-607, 2017.
Y. Li, T. Ma, and H. R. Zhang. Learning over-para two-layer relu neural networks beyond ntk. arXiv preprint arXiv:2007.04596 2020.
A. Loukas. What graph neural networks cannot learn: depth width. ICLR, 2020a.
A. Loukas. How hard is distinguish graphs with graph neural networks? Technical report, 2020b.
E. Malach and S. Shalev-Shwartz. Is deeper better only when shallow is good? In Advances in Neural Information Processing Systems, pages 6426-6435, 2019.
S. Mei, Montanari, and P.-M. Nguyen. mean field view the landscape of two-layer neural networks. Proceedings of the National Academy of Sciences, 1 11563)) 2018.

---

S. Oymak and M. Soltanolkotabi. Towards moderate overparameeteriiation:: global convergence guarantees for training shallow neural networks. CoRR, abs/ 1902.04674, 2019.
B. Polyak. Gradient methods for minimizing functionals. Zhurnal Vychislitel noi Matemariki i Matematicheskot Fiziki, 3(4):643 6536,333,,,,- 1963.
G. Rotskoff and E. Vanden-Eijnden. Parameters interacting particles: long time convergence and asymptotic error scaling of neural networks. In Advances in neural information processing systems, pages (114--155, 2018.
Sirignano and K. Spiliopoulos. Mean field analysis of neural networks. arXiv preprint arXiv:1805.01053, 2018.
M. Soltanolkotabi. Learning relus via gradient descent. arXiv preprint arXiv: (705::/700 2017.
M. Soltanolkotabi, Javanmard, and Lee. Theoretical insights into the optimization landscape of over-parameterizee shallow neural networks. IEEE Transactions on Information Theory, 65(2): 742-769, 2018.
L. Su and P. Yang. On learning over-parameterized neural networks: A functional approximation perspective. In NeurlPS, pages 2637-2646, 2019.
Veličković, G. Cucurull, A. Casanova, Romero, P. Lio, and Y. Bengio. Graph attention networks. arXiv preprint arXiv:1110.
2017.
S. Vempala and J. Wilmes. Gradient descent for one-hidden-layer neural networks: Polynomial convergence and sq lower bounds. arXiv preprint arXiv: /00..8805002.2 2018.
C. Wei, J. D. Lee, Q. Liu, and T. Ma. Regularization matters: Generalization and optimization of neural nets vs their induced kernel. In Advances in Neural Information Processing Systems, pages 9709-9721, 2019.
K. Xu, W. Hu, J. Leskovec, and S. Jegelka. How powerful are graph neural networks? ICLR, 2019a.
K. Xu, J. Li, M. Zhang, S. S. Du, K.-i. Kawarabayashi, and S. Jegelka. What can neural networks reason about? arXiv preprint arXiv: 0111999513333 13211, 2019b.
S. Zhang, M. Wang, S. Liu, P.-Y. Chen, and J. Xiong. Fast learning of graph neural networks with guaranteed generalizability: mne-hidden-layer case. In International Conference on Machine Learning, pages 11268-1122 1277. PMLR, 2020.
D. Zou and Q Gu. An improved analysis of training over over-parameterizee deep neural networks. In NeurlPS, 2019.
Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] to [Yes], [No] or [N/A]. You are strongly encouraged to include justification to your answer, either by referencing the appropriate section of your paper or providing a brief inline description. For example:
Did you include the license the code and datasets? [Yes] See Section ??.
Did you include the license the code and datasets? [No] The code and the data are proprictary.
Did you include the license the code and datasets? [N/]]
Please do not modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
1. For all authors...
12

---

(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes] See Section and Section
(b) Did you describe the limitations of your work? [Yes] See Section 5 and Section 6.
(c) Did you discuss any potential negative societal impacts of your work? [No] Our work theoretical in nature and do not anticipate any negative societal impact.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section and Section 4.
(b) Did you include complete proofs of all theoretical results? [Yes] See the Appendix.
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] See supplemen-
tary material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section D.
(c) Did you report eπror bars (e.g., with respect to the random seed after running exper- iments multiple times)? [No] We ran gradient descent on population loss and the variance due to random initialization was negligible.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Section
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]] See Section 5.
(b) Did you mention the license of the assets? [Yes] See Section D.
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you'ne using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "oONh5NWB2G", "reviewer": "Reviewer_iYkN", "summary": "In this paper, the authors analyze the convergence of gradient descent on message-passing Graph Neural Networks in the realisable case. They consider two settings: one-layer GNN with ReLU, and deep, linear, recurrent GNNs. They show that, if the input node features are drawn from iid Gaussians and the graph is sparse enough (degrees are bounded by the square root of the number of nodes), then minimizing the expected square loss will lead to convergence toward the true weights of the GNN. Explicit rate are given with respect to the various parameters of the problem.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This is an interesting paper, that extends to (simple) GNNs a now well-furnished line of works on the convergence of deep NNs in the realizable case. The paper is well-written and includes a sketch of proof. The proof method is (as far as I know) rather classic, the graph only appearing mostly through its degrees, but some computations are non-trivial.\n\nMy main comment is that, while the authors make an appreciable effort to discuss the simplifications made for this analysis, the most striking one is not discussed: unless I am missing something, the authors minimize the *expected* risk, with the expectation taken with respect to the random node features. At first glance, I was wondering why the authors don't extend the analysis to the minimization of the empirical risk as is usually done, but in fact this is here highly unrealistic: it would assume that, for each sample graph, the graph structure is the same ! This deserves at least a highly emphasized remark in the paper.\nA potential solution would be to \"create\" an empirical risk by dividing the coordinates of the Gaussian node features into subgroups, create each sample graph with a different subgroup of coordinates, and average over them. This would effectively correspond to having several copies of the same graph structure but with several independent node features, which would allow approaching the expected risk. Do the authors think that this could be feasible, via classical concentration arguments ?\nAnother possibility would be to assume that, for each sample, the graph structure itself depend on the node features like in the random graph literature (see eg the works of Ruiz, Ribeiro et al, or Keriven, Bietti and Vaiter for links between GNN and random graphs) but the analysis seems fairly different in this case, and probably significantly more involved.\nWith this in mind, the numerical experiments do not make much sense. The minimized risk involves only one graph sample, and is probably very far from the expected risk. Is there an argument that allows to go from one to the other ?\n\nOther comments/typos:\n- The deep linear GNN seems to have the same weights at each layer, being effectively a \"recurrent\" network. Is there a reason for this ?\n- in the sketch of proof of the one layer case, additional efforts could be dedicated to \"high-level\" explanations of the proof rather than hand-on computations. After all, the GNN is just $ sigma(W*A*X) $, with adjacency matrix A and iid Gaussians X, and the graph structure appears only through the d_ij (which are just the entries of A^2).\n- in section 3.1 (at least), the index j is used both for the weight and as a summation index, while it should be a different index. This is very confusing.\n- two spurious parenthesis in the first line of eq (9).\n\nTo conclude, this paper has merits, but a very significant blind spot on the expected/empirical risk aspect. My note may change quite a lot after discussion.\n\n**===== Edit after rebuttal =====**\n\nI thank the authors for their clear response. Although the \"fixed graph\" settings still remain a big limitation of their work, they acknowledge it and put forth convincing arguments. I am confident that they will clarify these limitations in the paper, as well as emphasize future directions to alleviate them. I thus believe that this paper might be an interesting first step. I increased my score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See above for limitations, which is my main comment.\n\nThis is a very theoretical work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "eq3OyaaEZ1i", "reviewer": "Reviewer_iGLS", "summary": "This paper analyzed the optimization performance of two types of GNNs. Specifically, this paper derived the convergence rate to a global optimum with gradient descent in the realizable case for ReLU-GNNs with one hidden layer and deep linear-GNNs. This paper showed that the former achieves a linear rate, and the latter achieves the $\\varepsilon$ error with $O(1/\\varepsilon^2 \\log(1/\\varepsilon))$  iterations. Furthermore, this paper experimentally verified the behavior of loss function with respect to model parameters and hyperparameters such as the number of nodes and number of layers.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Strength\n\n- [S1] To the best of my knowledge, this is the first paper to show the global convergence of non-linear GNNs at a linear rate by exploiting the realizability condition.\n- [S2] The paper is well-written and easy to follow.\n\n### Weakness\n\n- [W1] The problem is setting is different from usual node prediction tasks (see the Soundness section).\n- [W2] In addition, there are substantial restrictions on data distribution and GNN architecture. (For example, deep GNNs are linear and use weight-sharing.)\n- [W3] I have some questions about the soundness of the experiment (see the Soundness section).\n\n### Soundness (Do theorems and experiments answer research questions, assuming they are correct?)\n\n- [So1] I think the problem setting considered in this paper is different from the usual node prediction tasks. Therefore, we cannot directly apply the results of this paper. Specifically, in this paper, the model can observe teacher signal y of all nodes. However, we usually cannot see the teacher signal (y) of test nodes in node prediction tasks. Is it possible to apply this method to the partially observed setting?\n- [So2] The deep linear GNN used in this paper shares weights across layers. l.79 pointed out that GCN is such an architecture. But I think this is not true -- GCN uses different weights for each layer. It is OK to analyze the weight-sharing GNNs. However, I believe it is necessary to clarify that this architecture is different from the usual GCNs.\n- [So3] I have a question about whether the discussion in the experiment section is appropriate. This paper wrote that one of the experiment's objectives is to see whether the rate of ReLU GNN is tight or not (l.246.) and concluded that it is practically tight. However, I think it is difficult to evaluate the rate quantitatively just by comparing the loss curves of deep linear GNNs and ReLU GNNs with a single hidden layer.\n- [So4] Regarding the second objective of the experiment (behavior of GNNs in the regime of $d=O(n)$), I recognized its soundness.\n\n### Correctness (Are derivation of theorems and experiments correct?)\n\n- [C1] As far as I checked, there were no major errors in the proof.\n- [C2] I have one question about the proof of Theorem 1. Lemma 4 showed that either (1) the conditions on $\\beta_t$ and $\\ell_t$ or (2) the condition on $\\nabla L$ held for each $t$. However, it seems that the proof of Theorem 1 implicitly assumed that the condition (2) held for any $t\\leq T$ up to a given $T$.\n\n### Novelty and Significance (Do the paper have novel points? If so, are they significant?)\n\n- [N1] The strategy of using the PL condition to show linear convergence is a standard one. However, the proof has novelty in proving the satisfiability of the PL condition.\n- [N2] As far as I know, this is the first paper that showed the linear convergence of non-linear GNN to a global optimum under realizability conditions. Indeed, the architecture and data distribution of GNNs are different from those of real-world applications (e.g., realizable setting, random input, observability of teacher signals.) With that being said, I think this paper is significant as this paper is a good first step toward understanding the optimization perspective of GNNs.\n- [N3] For GNN optimization, [Oono & Suzuki, NeurIPS2020] and [Xu et al., ICML2021] considered the optimization performance of GNNs. However, this paper has novelty compared with these papers. Specifically, these papers analyzed multi-scale GNNs, while this paper single-scale GNNs. In addition, existing papers made assumptions other than realizability (weak-learning condition for [Oono & Suzuki, NeurIPS2020], the positivity of the (submatrix of) adjacency matrix for [Xu et al., ICML2021].)\n- [N4] This paper claimed that there is no convergence analysis of gradient descent for feed-forward NNs with more than two hidden layers in the non-NTK regime (l.146.) However, [Pham & Nguyen, ICLR2021] analyzed of NNs with two hidden layers in the mean-field regime. Therefore, the claim does not seem correct, judging solely from this sentence.\n- [Oono and Suzuki, NeurIPS2020] https://proceedings.neurips.cc/paper/2020/hash/dab49080d80c724aad5ebf158d63df41-Abstract.html\n- [Xu et al., ICML2021] http://proceedings.mlr.press/v139/xu21k.html\n- [Pham & Nguyen, ICLR2021] https://openreview.net/forum?id=KvyxFqZS_D\n\n### Clarity (Is the paper clearly written?)\n\n- [Cl1] The paper is easy to read. I was able to understand the proof without much difficulty.\n- [Cl2] I would suggest the overview of the proof strategy for the proof for deep linear GNNs in the main paper.\n\n### Other comments\n\n- l.73: shouldbe → should be\n- l.108 : Eq. (5) I would like you to clarify with respect to which probability distribution the expectation $E$ in (5) takes. Is it the expectation value for the distribution of $x$ and not for the initial distribution of $W$?\n- l.128: We, on the other hand are interested in ... → We, on the other hand, are \n- l.176: $\\sigma$ is used for both the variance of the Gassian distribution and the activation function.\n- l.206: $L_j(w_{j, t}) \\leq \\varepsilon^2/h$ → $L_j(w_{j, T}) \\leq \\varepsilon^2/h$\n- l.206: $|\\beta_t| \\leq \\frac{\\varepsilon}{4hn}$ → $|\\beta_T| \\leq \\frac{\\varepsilon}{4hn}$\n- l.206: $\\|\\ell_t-1\\| \\leq \\frac{\\varepsilon}{4hn}$ → $\\|\\ell_T-1\\| \\leq \\frac{\\varepsilon}{4hn}$ \n- l.289, l.291: Same reference with different versions.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "- [L1] This paper discussed the limitations of the analysis. Specifically, the analysis is only applicable to $d=o(\\sqrt{n})$ (l.273.) Also, it is not applicable to non-linear deep GNNs (l.276.)\n- [L2] See [W1] for the other possible limitations to be addressed.", "review_text": "", "extra_scores": {"ethical_concerns": "N.A.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "QIm9eS4H8tq", "reviewer": "Reviewer_3AyB", "summary": "This is a theoretical paper analyzing the optimization of graph neural networks (GNN). It assumes that the data is generated from a GNN with unknown weights, and tries to recover it by the gradient descent on the population loss. The convergence rate is established for two settings: one-layer GNNs with ReLU activations, and deep linear GNNs.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: Previous optimization analysis usually consider fully connected networks or residual networks, and this paper considers GNNs that are proposed from applications with few theoretical results.\n\nQuality: The theorems in the paper are supported by mathematical proofs. The authors consider some simplified settings: there exists a set of true weights; the gradient descent is taken on the population loss instead of empirical loss. Nevertheless, I think the proofs are not just trivial extension of fully connected networks, and it is a good starting point in this direction.\n\nClarity: The statements of the theorems and proofs are clear to me.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "- As mentioned in the conclusions part, the extension of this approach to more general settings is still challenging.\n- It would be better if Section 4 could show some proof sketch of the deep linear GNNs.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "JVOnKt1OD-A", "reviewer": "Reviewer_jXXp", "summary": "This paper analyzes the convergence of gradient descent (GD) on graph neural networks (GNNs). More specifically, the authors derive convergence rates for GD on a 1-layer GNNs with ReLU activation function, and on a multi-layer GNN without nonlinearities.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: This paper presents an original convergence analysis for GD on GNNs. The analysis builds on a similar convergence analysis developed for fully connected neural networks.\n\nQuality/Significance:  While the contribution has some significance and the analysis seems to be technically sound, the quality of the paper is limited by the fact that the authors don't discuss the limitations of the models they consider. I also find it strange that they do not discuss convexity. The first limitation that I see is that the analyzed models are not very useful in practice. Multi-layer GNNs without nonlinearities are just linear (over)parametrizations that could be written much more simply as one linear layer, and 1-layer ReLU GNNs are too small for most applications. I understand that analyzing multi-layer GNNs with nonlinearities is not trivial, but the authors should have better stressed the limitations of their approach. I also think it important to mention that the ERM problem with quadratic loss is convex for the 1-layer ReLU GNN. This alone implies convergence of gradient descent. \n\nClarity: The writing is clear but the organization of the paper could be improved. The authors discuss related work in Section 2, but also include some of it in Section 3 where they put more emphasis on contrasting their results with prior work than on discussing Theorem 1.  The content of Sections 3 and 4, which contain the paper's contributions (the convergence analyses for the 1-layer and multi-layer GNNs respectively), is extremely imbalanced: Section 3 is long and contains too many technical details, reading more like a proof than a paper; in contrast, Section 4 is short and looks rushed. This would be expected if the analysis is Section 4 were an extension of the analysis of Section 3, but this is not the case. I also wish the authors had discussed the Polyak condition in more detail; that would have been helpful for a high-level understanding of the proof strategy. Finally, there is a slight problem with notation---\\sigma is used in three different places to mean three different things---and a few typos here and there (e.g., lines 90 and 116; lowercase o for big oh notation in line 115).\n\n*** Update after rebuttal ***\n\nThank you for the clarification, indeed convexity would only hold if the labels were zero or negative. Subject to a more detailed discussion on the limitations of the models considered and on improvements in the organization of the paper (as per my original review), I am increasing my score to a 6.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3h"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper analyzes convergence properties of gradient descent for graph neural networks by using the neural tangent kernel technique. More specifically, it shows convergence with iteration complexity $\epsilon^{-2}\log(1/\epsilon)$ for one hidden layer ReLU-GNNs and shows linear convergence for deep linear GNNs. The theory is verified through a numerical experiment.

In the previous researches, NTK is analyzed mainly for FNNs, but this paper extends it to GNN settings. This requires some technical novelty and is not trivial. The second analysis for the deep linear model is a bit restrictive because it requires linear activation and the parameters in all layers are the same. However, this also requires some technical novelty to extend the proof for FNNs to GNNs. In that sense, this paper has novelty.   
The numerical experiments justify the theoretical results, but I recommend the authors that they present the graphs in log-log scale or semilog scale to see the correctness of the convergence rate given in the theorems.  

Although there are some concerns as I stated above, this paper still possesses novelty and the convergence analysis for GNNs is an important issue in the literature. Hence, I recommend this paper for acceptance. 
Decision: Accept (Poster)