Increase and Conquer: Training Graph Neural Networks on Growing Graphs
Authors: Juan Cervino
Luana Ruiz
Alejandro Ribeiro
Venue: ICLR 2022 Submitted (2022)
Keywords: Machine Learning
Graph Neural Networks

Abstract: Graph neural networks (GNNs) use graph convolutions to exploit network invariances and learn meaningful features from network data. However, on large-scale graphs convolutions incur in high computational cost, leading to scalability limitations. Leveraging the graphon --- the limit object of a graph --- in this paper we consider the problem of learning a graphon neural network (WNN) --- the limit object of a GNN --- by training GNNs on graphs sampled Bernoulli from the graphon. Under smoothness conditions, we show that: (i) the expected distance between the learning steps on the GNN and on the WNN decreases asymptotically with the size of the graph, and (ii) when training on a sequence of growing graphs, gradient descent follows the learning direction of the WNN. Inspired by these results, we propose a novel algorithm to learn GNNs on large-scale graphs that, starting from a moderate number of nodes, successively increases the size of the graph during training. This algorithm is benchmarked on both a recommendation system and a decentralized control problem where it is shown to retain comparable performance, to its large-scale counterpart, at a reduced computational cost.

Under review as a conference paper at ICLR 2022
INCREASE AND CONQUER: TRAINING GRAPH NEURAL NETWORKS ON GROWING GRAPHS
Anonymous authors Paper under double-blind review
ABSTRACT
Graph neural networks (GNNs) use graph convolutions to exploit network invari- ances and learn meaningful features from network data. However, on large-scale graphs convolutions incur in high computational cost, leading to scalability lim- itations. Leveraging the graphon - the limit object of a graph - in this paper we consider the problem of learning graphon neural network (WNN) the limit object of a GNN - by training GNNs on graphs sampled Bernoulli from the graphon. Under smoothness conditions, we show that: (i) the expected distance between the learning steps on the GNN and on the WNN decreases asymptoti- cally with the size of the graph, and (ii) when training on sequence of growing graphs, gradient descent follows the learning direction of the WNN. Inspired by these results, we propose novel algorithm learn GNNs on large-scale graphs that, starting from a moderate number of nodes, successively increases the size of the graph during training. This algorithm is benchmarked on both a recom- mendation system and a decentralized control problem where it is shown to retain comparable performance to its large-scale counterpart at a reduced computational cost.
INTRODUCTION
Graph Neural Networks (GNNs) are deep convolutional architectures formed by a succession of layers where each layer composes a graph convolution and pointwise nonlinearity (Wu et a [021]] Zhou et al. 2020). Tailored to network data, GNNs have been used in variety of applications such as recommendation systems (Fan et al., 2019 Tan al. 2020 Ying et al., 2018, Schlichttrull al.,
2018 Ruiz et al., 2019a) and Markov chains (Qu et al.) [019]] Ruiz et al. 20T9h; Li et al.) 2015]
and fields such as biology (Fout et al. 2017 Duvenaud et al. 2015 Gilmer et [017) Chen et al. 2020) and robotics (Qi et al. 2018 Gama & Sojoudi 2021 Li et al. 2019). Their success in these fields and applications provides ample empirical evidence of the ability GNNs to generalize to
unseen data. More recently, their successful performance has also been justified by theoretical works
showing that GNNs are invariant to relabelings (Chen et al.] [2019] Keriven & Peyré 2019). stable graph perturbations (Gama al. 2020) and transferable across graphs (Ruiz et al. 2020a).
One of the most important features of a GNN is that, because the linear operation is a graph convo- lution, its number of parameters does not depend on the number of nodes of the graph. In theory, this means that GNNs can be trained on graphs of any size. In practice, however, if the graph has large number of nodes training the GNN costly because computing graph convolutions involves large matrix operations. While this issue could be mitigated by transferability - training the GNN on smaller graph execute on the large graph -, this approach does not give any guarantees on the distance between the optimal solutions on the small and on the large graph. In other words, when executing the GNN on the target graph we do not know if its error will be dominated by the transferability error or by the generalization error from training.
In this paper. we address the computational burden training a GNN on large graph by progres- sively increasing the size of the network. We consider the limit problem of learning an "optimal" neural network for a graphon, which is both a graph limit and a random graph model (Lovász) 2012). We postulate that, because sequences of graphs sampled from the graphon converge to it, the so-called graphon neural network (Ruiz et al., (2000a) can be learned by sampling graphs of growing size and training GNN these graphs (Algorithm []. We prove that this is true in two steps. In

---

Under review as a conference paper at ICLR 2022
Theorem [ we bound the expected distance between the gradient descent steps the GNN and on the graphon neural network by a term that decreases asymptotically with the size of the graph. A consequence of this bias bound is that it allows us quantify the trade-off between more accurate gradient and one that could be obtained with less computational power. We then use this theorem to prove our main result in Theorem 2
which is stated in simplified form below.
Theorem (Graphon neural network learning, informal) Let W be a graphon and let {G,)) be a sequence of growing graphs sampled from W. Consider the graphon neural network ((W) and assume that it is learned by training the GNN (G.,) with loss function E(y,, a ((G.)) on the sequence {Gn]. Over finite number of training steps, we obtain
VV&(Y, (()) S with probability 1.
The most important implication of this result is that the learning iterates computed in the sequence of growing graphs follow the direction of the graphon gradient up to a small ball, which provides the- oretical validation to our cost efficient training methodology. We also validate our algorithm in two numerical experiments. In the first, we learn a GNN-based recommendation system on increasingly large subnetworks of a movie similarity graph, and compare it with the recommendation system trained on the full graph. In the second, we consider the problem of flocking and train GNNs to learn the actions agents need to take flock. We compare the results obtained when progressively increasing the number of agents during training and when training directly on the target graph.
2 RELATED WORK
GNNs are data processing architectures that follow from the seminal works in the areas of deep learning applied to graph theory (Bruna et al., 2013] Defferrard et al. 2016; Gori et al. [0055] Lu & Getoor 2003). They have been successfully used in wide variety of statistical learning problems (Kipf & Welling 2016) Scarselli et al.) 2018), where their good performance is generally attributed
the fact that they exploit invariances present in network data (Maron al. 2019 Gama et al.
2018
Chami et al. 202T).
More recently, number of works show that GNNs be transferred across graphs of different sizes (Ruiz et al., 2020a Levie et al.] 2019; Keriven et al.) 2020). Specifically, (Ruiz et al. (2020)) leverages graphons to define families of graphs within which GNNs can be transferred with an eгror bound that decreases asymptotically with the size of the graph. The papers by Levie et al. (2019) and Keriven al. (2020) offer similar results by considering the graph limit topological space and a random graph model respectively. In this paper, we use an extension of the transferability bound derived Ruiz et al. (2020a) to propose a novel learning algorithm for GNNs.
generic
3 PRELIMINARY DEFINITIONS
3.1 GRAPH NEURAL NETWORKS
Graph neural networks exploit graph symmetries extract meaningful information from network
data (Ruiz et al. 2020c Gama et al. 2020). Graphs are represented as triplets G, = (V, E, W), where V. | n. the set of nodes, & C V V is the set of edges and W E R is a map assigning weights to each edge. The graph G, can also be represented by the graph shift operator (GSO) S E R=x=, a square matrix that respects the sparsity of the graph. Examples of GSOs include the adjacency matrix A, the graph Laplacian L = diag( A1) A and their normalized counterparts Gama et al. (018)). In this paper we consider the graph G, to be undirected and fix S A/n.
Graph data is represented in the form of graph signals. A graph signal is a vector whose i-th component corresponds to the information present at the i-th node of graph G A basic data aggregation operation can be defined by applying the GSO S to graph signals x. The resulting signal z = Sx is such that the data at node i is a weighted average of the information in the 1-hop neighborhood of 2; ΣjeNs [S] Slyyyy where M₁ {j [S] + 0). Information coming from further neighborhoods can be aggregated by successive applications of the GSO, also called shifts. Using this notion of shift, graph convolutions are defined by weighting the contribu- tion of each successive application of S to define polynomial in the GSO. Explicitly, the graph
[æ1...., x²," e R
2

---

Under review as a conference paper at ICLR 2022
convolutional filter with coefficients h [hu,.............. hx-11 a is given by
K-1
y = h 'g x
Σ
S
(I)
k=0
where *g denotes the convolution operation with GSO S.
Since the adjacency matrix of an undirected graph always symmetric, the GSO admits an eigen- decomposition S = VAV# The columns of V are the graph eigenvectors and the diagonal el- ements of A are the graph eigenvalues, which take values between -1 and 1 and are ordered as -1 A=1 X-2 ... 0 S < X2 I À I 1. Since the eigenvectors of S form an orthonormal basis of IR" we can project ① onto this basis to obtain the spectral representation of the graph convolution, which is given by
K-1
k(A) = Σ had
Note that (2) only depends on the h2 and on the eigenvalues of the GSO. Hence, as consequence of the Cayley-Hamitton Hamilton theorem, convolutional filters may be used to represent any graph filter with spectral representation (x(A) f()) where / is analytic (Strang) 1976).
Graph neural networks are layered architectures where each layer consists of a graph convolution followed by pointwise nonlinearity p. and where each layer's output is the input to the following layer. At layer I, GNN
output multiple features x/, 1 S f S Fi which we stack in matrix X, = [x] , x E gaxE, Each column of the feature matrix is the value of the graph signal at feature f. To map the Fi-1 features coming from layer I - 1 into Fi features, Fi-1 x Fj convolutions need to be computed, one per input-output feature pair. Stacking their weights in K matrices Hug R - we write the 1-th layer of the GNN as
K Σ K=U
X, = p
S
S H
(3)
In an L-layer GNN, the operation in 3 is cascaded times to obtain the GNN output Y X,, At the first layer, the GNN input is given by Xo X R=*F., In this paper we assume Fo Fr. so that Y = and X x. A more concise representation of this GNN can be obtained by grouping all learnable parameters H4s in a tensor H. {Hi L.A and defining the map y = o S) Due to the polynomial nature of the graph convolution, the dimensions of the learnable parameter tensor H are independent from the size of the graph (K typically much smaller than n.). Ergo, a GNN trained on a graph G, can be deployed on network Gm,. with m f
3.2 GRAPHON INFORMATION PROCESSING
A graphon is a bounded, symmetric, and measurable function W [0, + [0, which has two theoretical interpretations it is both graph limit and a generative model for graphs. In the first interpretation, sequences of dense graphs converge to graphon in the sense that the densities of sejaacency-preeerving graph motifs converge the same densities on the graphon Lovász (0012). In the second, graphs can be generated from a graphon by sampling points u4 Uy from the unit interval and either assigning weight W(u,, uj) edges (i,j). sampling edges (i.j) with probability W (ui, uz)) In this paper, we focus on stochastic graphs G, where the points uy are defined as u. 1)/n for S i S n and where the adjacency matrix S,, is sampled from W
[S Bernoulli (W (u, u;)).
(4)
Sequences of graphs generated in this way can be shown to converge to W with probability one [ováász] [Ch2tth 11].
In practice, the two theoretical interpretations of a graphon allow thinking of it as an identifying object for family of graphs of different sizes that are structurally similar. Hence, given network we can use its family's identifying graphon as a continuous proxy for the graph. This is beneficial because it is typically easier to operate in continuous than in discrete domains, network is large. We will leverage these ideas to consider graphon data and graphon neural networks as proxies for graph data and GNNs supported graphs of arbitrary size.
more if the
3

---

Under review as a conference paper at ICLR 2022
3.2.1 GRAPHON NEURAL NETWORKS
Graphon data is defined functions X L (2, 1J). Analogously to graph data, graphon data can be diffused by application of a linear integral operator parametrized by W and defined as
Tw [ (u,, v).X
(5)
The operator Tw is called graphon shift operator (WSO).
The graphon convolution is defined as a weighted sum of successive applications of the WSO. Explicitly, the graphon convolutional filter with coefficients h = [Mo.-..; is given by
Y == ho X
Σ
hu (TW (K) w X)) with
k=0
(6)
(TW) x)()== L W(,, v) (TW (T(k-1) (u)du
where TW is the identity (Ruiz et al., 2020b). Since W is bounded and symmetrie, Tw is self-adjoint Hilbert-Schmidt operator (Lax 2002). Hence, W can be written as ((u, Eiezy(0) (v))(());;()) where A are the graphon eigenvalues and Pi the graphon eigenfunctions. The eigenvalues have magnitude at most one and are ordered as -1 A-1 X-2 ... S 0 S x S λ < 1. The eigenfunctions form orthonormal basis of ( 1J). Projecting the filter onto this basis, we see that the graphon convolution admits a spectral representation given by
M(AA
hgd#.
Like its graph counterpart, this spectral representation only depends the eigenvalues of the graphon.
Graphon neural networks (WNNs) the extension of GNNs graphon data. In the WNN, each layer consists bank of graphon convolutions (6) followed by a nonlinearity p. Assuming that layer 1 maps F/-1 features into Fi features, the parameters of the Fi-1 Fi convolutions (6 can be
stacked into K matrices (H Ri-11 This allows writing the fth feature at layer as
x/=p
ΣΣ
Σ
(k) ( x2_1 Hukk
(8)
for 1 < f S Ft. For an L-layer WNN, is repeated for 1 S l S L. The WNN output is given by and X is given by the input data X for 1 S Fo. We assume Fz Fo 1 so that X = and Xo = X. A more succinct representation of this WNN is the map = ( W),
Y = X f.
where the tensor H.- {Hu.). groups the filter coefficients at all layers.
3.2.2 SAMPLING GNNS FROM WNNs
From the representation of the GNN and the WNN as maps (xx H, S) and : W), we see that these architectures can share the same filter coefficients H. Since graphs can be obtained from graphons as in 44) we can similarly use the WNN & X; H. W) to sample GNNs
yr (x,; H. S,,)) where [Snli Bernoulli (annoulll(((u,,,) (W,, 4y))
[x,] X (u:)
ie., the WNN can be seen as a generative model for GNNs (x,,; H.S
Conversely, a WNN ca be induced by GNN. Given GNN y, (xx; S.), the WNN induced by this GNN is defined as
Yn (X,; H. W.) where W. Wn) = Σ>
ΣD S SalsT(u T,)T(( E 75)
1-1
(10)
(n) = Σ (u 1,)
4

---

Under review as a conference paper at ICLR 2022
where II denotes the indicator function and the intervals I are defined as I, (ii--)nn,ij for 1 $ Σ n - 1 and In = [(n - 1)/n, 1]. The graphon W,, is called the graphon induced by the graph G and X,, and Y,, are called the graphon signals induced by the graph signals x,, and yn-
4 GRAPHON EMPIRICAL LEARNING
On graphons, the statistical loss minimization (or statistical learning) problem is given by
minimize Eppr,x))e(X, H W))]
(1I)
H
where p(Y. X) is the joint distribution of the data, is an instantaneous loss function and + H. W) is a function parametrized by the graphon W and by a set of learnable weights H. In this paper, we consider positive loss functions 8 R x R - R+ The function 4 is parametrized as graphon neural network [ef. (8). Because the joint probability distribution p(Y, is unknown, we are unable to derive a closed-form solution of (11), but this problem can be approximated by the empirical risk minimization (ERM) problem over graphons.
4.1 GRAPHON EMPIRICAL RISK MINIMIZATION
Suppose that have access to samples of the distribution D {(X*, Y*) p(X, 1....,/2)) Provided that these samples are obtained independently and that [D] is large enough, the statistical loss in (11) can be approximated
minimize H
Σ E0Y5, (X'; W))
(12)
giving way to the ERM problem (Hastie et al.) 2009 Shalev-Shwarde Ben-David, 2014, Vapnik] 1999 Kearns et al.) [194). To solve this problem using local information, we could adopt some flavor of gradient descent GGooffellw et al. 2016). The learning iteration at step & is then
H4-11 H4 7h V nlY',, ( W))
(13)
where ks = 1,2, ... denotes the current iteration and n7x E (0, 1) the step size at iteration k.
In practice, the gradients the right hand side of 13 cannot be computed because, being a theoret- ical limit object, the graphon W is unknown. However, we can leverage the fact that the graphon is a random graph model to approximate the gradients V + (X*; H. W)) by sampling stochastic : H. S,)). where x², and y are in (9) In this case, the graphon empirical learning step (13) becomes
graphs G, with GSO S, [ef. 4 and calculating V ( n + (x
Ha+1 = He Me (
4 (x); He, S..))
(14)
and we have to derive an upper bound for the expected error made when using the gradient calculated on the graph to approximate the gradient on the graphon. In what follows, we give a closed-form expression of this bound, and use it stepping stone develop an Algorithm that increases n, the graph size, over regular intervals during the training process of the GNN. We then prove that our Algorithm converges neighborhood of the optimal solution for the WNN.
4.2 GRADIENT APPROXIMATION
To state our first convergence result, we need following definition.
Definition 1 (Lipschitz functions). A function f(u1, U2, ua) is A-Lipschitz on the variables
Ui...., ua if it satisfies [f .2,..., va) f(u1, U2..... ua)l < A Di i1 u,, If A 1, we say that this function is normalized Lipschitz.
We also need the following Lipschitz continuity assumptions (AST AS4 as well assumption on the size of the graph S,, (AS5).
AS1. The graphon W and the graphon signals X and Y are normalized Lipschitz.
AS2. The convolutional filters h are normalized Lipschitz and non-amplifying, i.e. [[(Aa]] < 1.
5

---

Under review as a conference paper at ICLR 2022
Algorithm Increase and Conquer: Growing Graph Training
1: Initialize Ho. and sample graph G,,, from graphon W repeat for epochs 0, 1,... for kl [D] do
2:
3:
4:
Obtain sample (X ~ 5: Construct graph signal Yn, [cf. 9
6: Take learning step H4++1 = He aa Vilyn. ((x,; Hk. Sn))
7:
end for
8: Increase number of nodes n and sample s, Bernoulli from graphon W [cf.
9:
until convergence
AS3.
The activation functions and their gradients are normalized Lipschitz. and p(0) 0.
AS4. The loss function Ê IR X R and its gradient are normalized Lipschitz, and E(x, x)) O.
AS5. For fixed value of (0, 1), n is such that πt - log((2n (2//22n/)))) (2n//)/m/// /w 2/ 2/dw where dw denotes the maximum degree of the graphon W, i.e., dw max, Jo (uu, v)du.
AST are normalized Lipschitz smoothness conditions which can be relaxed by making the Lipschitz constant greater than one. A$3 holds for most typical activation functions. AS can be achieved by normalization and holds for most loss functions in a closed set (c.g., the hinge or mean square losses), AS5 is necessary to guarantee O (VVlog n/n) rate of convergence of S, to W
(Chung & Radcliffe 2011).
Under A AS5] the following theorem shows that the expected norm of the difference between the graphon and graph gradients (13) and (14) is bounded. The proof deferred to the appendices.
Theorem 1. Consider the ERM problem in (2) and let (XX; H. W) be an L-layer WNN with Fo Ft 1, and Fi F for < L- Let c (0, 1] and assume that the graphon
convolutions in all layers of this WNN have K filter taps [cf. (6)). J. Let 4 (xx,; H. S.) be GNN
sampled from 4 (X;;H W) as in ( Under assumptions A ASS it holds that
Elll Vxl(Y, ((:HH, W)) Vxl(Y,. 4(X.; W.)) S 3c+ ( log(n8/22
(15)
n
where Yn is the graphon signal induced by [yn]i = (us) ) lcf. (00). and oy is a constant that depends the number layers L, features F, and filter taps K of the GNN [ef. Definition in the Appendix).
The bound in Theorem I the maximum distance between the learning steps the graph and on the graphon as a function of the size of the graph. This bound controlled by two terms. On the hand, have the approximation bound, term that decreases with n. The approximation bound is related to the approximation of W by S.. On the other, we have the nontransferable bound, which is constant and controlled by c. This term related the convolutional filter h. Since graphons W have an infinite spectrum that accumulates around zero, convergence of all spectral components the filtered data on W n can only be shown in the limit of (Ruiz et al. 2020a). Hence, given that n is finite we can only upper bound distances between spectral components associated with eigenvalues larger than some e E (0, 1] that we fix. Meanwhile, the perturbations associated with the other spectral components are controlled by bounding the variation of the filter response below c.
threshold that we impose on
The bound in Theorem gradient steps not on the graphon, but on the graph data. Although we cannot take gradients on the function that we want to learn Icf. [13]], by measuring the ratio between the norm of the gradient of the loss on the GNN, and the difference between the two gradients, we can expect to follow the direction of the gradient graphon ERM problem (12) Nonetheless, we are only able to decrease this approximation bound down the value of the nontransferable bound.
important because allows us quantify the error incurred by taking
the WNN. This is instrumental for learning a meaningful solution of the

---

yC + o (V 1og(n0/2) Under review as a conference paper at ICLR 2022
4.3 ALGORITHM CONSTRUCTION
Since the discretization error depends on the number of nodes of the graph, we can iteratively in- crease the graph size at every epoch. Even if a bias is introduced in the gradient we will be able to follow the gradient direction of the graphon learning problem (13). At the same time, we need to keep the computational cost of the iterates under control. Note that the norm of the gradient is larger at first, but it decreases as we approach the optimal solution. Exploiting this behavior, we may progressively reduce the bias term as iterations increase. The idea here is to keep the discretization of the gradient small so as to closely follow the gradient direction of the graphon learning problem, but without being too conservative as this would incur in high computational cost.
In practice, in the ERM problem the number of nodes that can be added is upper bounded by the available data, which defined nodewise on the graph. Hence, we can arbitrarily decide which and how many nodes to consider for training. The novelty of Algorithm iis that we do not use the largest graph available in the dataset at every epoch to train the GNN. Instead, we set a minimum graph size no and progressively increase it up the total number of nodes. The main advantage of Algorithm I is thus that it allows reducing the computational cost of training without compromising GNN performance. In what follows, we will provide the conditions under which Algorithm T converges to neighborhood of the optimal solution on the graphon.
4.4 ALGORITHM CONVERGENCE
We have shown that the learning step on the graphon and on the graph are close. Now, remains to show the practical implications of Theorem [ for obtaining the solution of the graphon ERM problem (12). If the expected difference between the gradients is small, the iterations generated by 14 will be able to follow the direction of the true gradient the graphon learning problem. But because the distance between gradients is inversely proportional to n, we need to strike a balance between obtaining good approximation and minimizing the computational cost. In Theorem 2 we show that Algorithm [ converges if the rate at which the graph grows is chosen to satisfy the condition given in (T6).
AS6. The graphon neural network (X; H. W) is Aq AipLihchhizz and its gradient V V H. W) is - Lipschitz, with respect to the parameters H. [cf. Definition[]]
Theorem 2. Consider the ERM problem in (12) and let (Xx; H. W) be an L-layer WNN with Fo = F2. = 1, and F; = F for 1 < S I. 1. Let E (0. E (0, A and assume that the graphon convolutions in all layers of this WNN have K filter taps [ef. (6)). Let (xx,; H. S.)
be GNN sampled from (b[x: X:; H. W) as in (.. Consider the iterates generated by equation (6
Under Assumptions AS7 ASO
if at each step k the number of nodes n verifies
1 Aven - C IV (Xnn HR. W.)l
(16)
n
2
then in finite time will achieve an iterate k. such that the coefficients Hy- satisfy
Blll LY, ((X; Hy. W) S 27c after at most k- = O(1/e)
(17)
where 7 is a constant that depends on the number of layers L, features F, and filter taps K of the GNN lef. Definition
7 in the Appendix].
Theorem 2 presents the conditions under which Algorithm I converges. Intuitively, the condition in (16) implies that the rate of decrease in the norm of the gradient of the loss function computed on the graph neural network needs be slower than roughly 1/2 If the norm of the gradient does not vary between iterations, the number of nodes does not need to be increased. Note that (I15) is equal to twice the bias term obtained in equation 15). We can keep increasing the number of nodes and thus decreasing the bias until the norm of the GNN gradient is smaller than the nontransferable constant value. Once this point is attained, there is no gain in decreasing the approximation bound any further (Ajalloeian & Stich 2020). Recall that the constant term can be made as small as desired by tuning c, at the cost of decreasing the approximation bound. To conclude, observe that assuming smoothness of the GNN is a mild assumption (Scaman & Virmaux 2018 Jordan & Dimakis 2020 Latorre et al., 2020 Fazlyab et al. 2019: Tanielian & Biau][202] Du et al. of the Lipschitz constant is
2019). A characterization interesting research question but is out of the scope of this work.
7

---

Under review as a conference paper at ICLR 2022
5 NUMERICAL RESULTS
5.1 RECOMMENDATION SYSTEM
We consider a social recommendation problem given by movie ratings, for which we use the Movie- Lens 100k dataset Harreer & Konstan (2015) The dataset contains 100, 000 integer ratings between and 5, that were collected between = 943 users and
1682 movies. We consider the prob- lem of predicting the rating that different users would give to the movie "Contact". To exploit the social connectivity of the problem, we build the movie similarity graph, by computing the pairwise correlations between the different movies in the training set Huang al.] (2018). Further details about training splits, and hyperparameter selection can be found in the supplementary material.
For the experiment, we started the GNNs with 200, and at 300 nodes and added {25,50, 50, 75, 100} nodes per epochs. The total number of epochs of the GNN trained on 1000 nodes with which compare, is given by the maximum number of epochs that the Algorithm can be adding 25 nodes per epoch. In Figure [ we are able to see the empirical manifestation of the benefit of Algorithm [T] Namely, regardless of the number of nodes added per epoch, in all four cases, using relative RMSE as figure of merit, we achieve a comparable performance to that of a GNNs trained on 1000 nodes for larger number of epochs. This reinforees the fact that training on a growing number of graphs can attain similar performance, while requiring a lighter computational cost.
5.2 DECENTRALIZED CONTROL
In this section we consider the problem of coordinating a set of n agents initially flying at random to avoid collisions, and to fly at the same velocity. Also known flocking, at each time agent i knows its own position r; (t) E IR? and speed 0; (t) E TR2 and reciprocally exchanges with its neighboring nodes if a communication link exists between them. Links are govern by physical proximity between agents forming a time varying graph G, = (V, 8). A communication link exists if the distance between two agents i, satisfies riy = [t):(t) - (t)l I R 2m. We assume that at each time l the controller sets acceleration u, E [-10, 10j2, and that remains constant for time interval T. = 20mss The system dynamics are govern by. r2(4+ +1) uz uz()T?// (;(T), + (()),, (t + 1) u, (t)T,, + (t). To avoid the swarm of robots reach null common velocity, we initialize the velocities at random v(t) = [t) 2, (t)), by uniformly sampling a common bias velocity UBIAS -1-3,33 3,3), 3). and then adding independent uniform noise 4(-3, 3] to each agent. The initial deployment is randomly selected in circle always verifying that the minimum distance between two agents larger than 0.1. On the one hand, agents pursue a common average velocity v (I/n) >i =i=1 vi()), thus minimizing the velocity variation of the team. On the other
Adiad (Staning Noino
Adhidd (Barting Nallo
Nodos Adlied (Staning 200 Nolme)
Notes Addidd (Sartic 200 Noin)
25 Nodos Adboe (Starting 300 Natee) Nodos Added (louting Nodww)
To Noves Added (Statinn Natm)
Nodes Added (Soutlog Nodw)
Dalative ROAE
10*
0..0
00.0
21.0
711
00.0
00.3
(a)
(b)
Figure 1: Relative RMSE of a recommendation system trained on MovieLens 100k for 20 independent par- titions measured over the test set (a) starting with GNNs of 200 nodes, compared to a GNN trained on 1000 nodes for 37 epochs (b) starting with GNNs of 300 nodes, compared to GNN trained 1000 nodes for 29 epochs.
8

---

Under review as a conference paper at ICLR 2022
20.0
nodes per epoch 10 spochs)
20.9
2 nodes per epoch
Controllar
Controller
epochst
Trained 100 rodes (30 spachs)
Thained 100 modes [30 epache)
100
10t
8.0
8.0
7.0
7.0
6.0
6.0
5.0
4.0
4.0
3.0
3.0
2
3
10 11 Number of Epochs
12
14
16
27
10 11
13
14
16
17
Number of Epochs
Figure 2: Velocity variation of the flocking problem for the whole trajectory in the testing set relative to the centralized controller starting with 10 nodes and (b) starting with 20 nodes.
hand, agents are required to avoid collision. We can thus define the velocity variation of the team (v()) = - (l),(() (1) and the collision avoidance potential
CA(r,rr)) (t) (t)]1 log(()):(t)--)())))])) 11/Bcs Log(RA..)
- (t((1 if ()((()))((((((()
RcA (18)
otherwise.
with RCA 1m. A centralized controller can be obtain by uz(() -n(e v) + E CA(r,))))))))) TTnner et al. 2003).
Exploiting the fact that neural networks are universal approximators (Barron 1993 Hornik 1991).
Imitation Learning can be utilized as framework to train neural networks from information pro- vided by an expert (Ross et al., 201 T Ross Bagnell 2010). Formally, we have a set of pairs {Xm; J m = 1,... M, and during training we minimize the mean square error between the optimal centralized controller, and the output of our GNN | - (xx; S)Il2 Denoting (t()) the neighborhood of agent i at time t, the state of the agents x(t) (I(t),, (t) (t( RR
is given by (t) E (oj [va (t) (t),), Tiy (t)/Ir, (t)l miy (1)(()) Note that state na (t), gets transmitted between agents if a communication link exists between them.
In Figure 2 we can see the empirical manifestation of the claims we put forward. First and foremost, we are able to learn a GNN that achieves comparable performance while taking steps on smaller graphs. As seen in Figure? 2 GNNs trained with no {10, 20) agents in the first epoch and adding 10 agents per epoch (green line) are able to achieve similar performance when reaching 100 agents than the one they would have achieved by training with 100 agents the same number of epochs. Besides, if we add less nodes per epoch, we are able to achieve similar performance that we would have achieved by training on the large network for 30 epochs.
6 CONCLUSIONS
We have introduced a learning procedure for GNNs that progressively grows the size of the graph while training. Our algorithm requires less computational cost as the number of nodes in the graph convolution smaller than training on the full graph without compromising performance. Leveraging transferability results, we bounded the expected difference between the gradient on the GNN, and the gradient on the WNN. Utilizing this result, we provided the theoretical guarantees that our Algorithm converges to neighborhood of first order stationary point of the WNN in finite time. We benchmarked our algorithm on recommendation system and a decentralized control problem, achieving comparable performance to the one achieve by GNN trained on the full graph.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Ahmad Ajallocian and Sebastian U Stich. Analysis of sgd with biased gradient estimators, arXiv preprint arXiv:2008.0000 2020.
Andrew R Barron. Universal approximation bounds for superpositions of a sigmoidal function. IEEE Transactions Information 390))930993 1993.
Dimitri P Bertsekas and John N Tsitsiklis. Gradient convergence in gradient methods with errors.
SIAM Journal on Optimization, 10(3):627-642, 2000.
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. arXiv preprint arXiv:1312.6203. 2013.
Ines Chami, Sami Abu-EI-Haija, Bryan Perozzi, Christopher Ré, and Kevin Murphy. Machine learning graphs: A model and comprehensive taxonomy, 2021.
Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. arXiv preprint arXiv: 190.:::990..200000 /2560, 2019.
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? arXiv preprint 2002::200.. 2020.
Fan Chung and Mary Radcliffe. On the spectra of general random graphs. the electronic journal of combinatorics, pp. P215-P215, 2011.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In D. Lee, M. Sugiyama, U. Luxburg, Guyon, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 29. Curran Associates, Inc., 2016.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. International Conference on Machine Learning, pp. 1675- 1685. PMLR, 2019.
Rick Durrett. Probability: Theory and Examples. Cambridge University Press, 2019.
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alan Aspuru-Guzik, and Ryan P Adams. Convolutional networks on graphs for learning molecular fingerprints. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015.
Wenqi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin. Graph neural networks for social recommendation. In The World Wide Web Conference, pp. 417-426, 2019.
Mahyar Fazlyab, Alexander Robey, Hamed Hassani, Manfred Morari, and George Pappas. Efficient and accurate estimation of lipschitz constants for deep neural networks. Advances in Neural Information Processing Systems, 32: 1447-11424438 2019.
Alex Fout, Jonathon Byrd, Basir Shariat, and Asa Ben-Hur. Protein interface prediction using graph convolutional networks. In Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vish- wanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
Fernando Gama and Somayeh Sojoudi. Distributed linear-quadratic control with graph neural net- works. arXiv preprint arXiv:2103.08411 2021.
Fernando Gama, Antonio G Marques, Geert Leus, and Alejandro Ribeiro. Convolutional neural network architectures for signals supported on graphs. IEEE Transactions on Signal Processing, 67(4)1033-1004, 2018
Fernando Gama, Joan Bruna, and Alejandro Ribeiro. Stability properties of graph neural networks. IEEE Transactions Signal Processing, 68:5680-5695. 2020.
10

---

Under review as a conference paper at ICLR 2022
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 1263-1272.
PMLR, 06-11 Aug 2017.
Ian Goodfellow, Yoshua Bengio, Aaron Courville, and Yoshua Bengio. Deep learning, volume 1.
MIT press Cambridge, 2016.
M. Gori, G. Monfardini, and F. Scarselli. A new model for learning in graph domains. Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005., 2:729-734 vol. 2. 2005.
F Maxwell Harper and Joseph A Konstan. The moviclens datasets: History and context. Acm transactions on interactive intelligent systems (ris), 5(4):1-19, 2015.
Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The elements of statistical learning: data mining, inference, and prediction. Springer Science & Business Media, 2009.
Kurt Hornik. Approximation capabilities of multilayer feedforward networks. Neural networks, (2)2551-257, 1991.
Weiyu Huang, Antonio G Marques, and Alejandro R Ribeiro. Rating prediction via graph signal processing. IEEE Transactions on Signal Processing, 66(19):5066-508 2018.
Matt Jordan and Alexandros Dimakis. Exactly computing the local lipschitz constant of relu networks. arXiv preprint arXiv:2003.01219, 2020.
Michael Kearns, Umesh Virkumar Vazirani, and Umesh Vazirani. An introduction to computational learning theory. 1994.
Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neural networks. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Nicolas Keriven, Alberto Bietti, and Samuel Vaiter. Convergence and stability of graph convolu- tional networks on large random graphs. arXiv preprint wwXiv:2006.01868. 2020.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. CoRR, abs/1412.69800, 2015.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint arXiv: 1609.02977 2016.
Fabian Latorre, Paul Rolland, and Volkan Cevher. Lipschitz constant estimation of neural networks via sparse polynomial optimization. arXiv preprint arXiv:2004.08688, 2020.
D. Lax. Functional Analysis. Wiley, 2002.
Ron Levie, Wei Huang, Lorenzo Bucci, Michael M Bronstein, and Gitta Kutyniok. Transferability of spectral graph convolutional neural networks. arXiv preprint arXiv 12972, 2019.
Qingbiao Li, Fernando Gama, Alejandro Ribeiro, and Amanda Prorok. Graph neural networks for decentralized multi-robot path planning. arXiv preprint arXiv: 2019.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. arXiv preprint arXiv: 15/ 1.05493, 2015.
László Lovász. Large networks and graph limits, volume 60. American Mathematical Soc., 2012.
Q. Lu and Getoor. Link-based classification. In JCML 2003, 2003.
Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks, 2019.
Siyuan Qi, Wenguan Wang, Baoxiong Jia, Jianbing Shen, and Song-Chun Chun Zhu. Learning human- object interactions by graph parsing neural networks. In Proceedings of the European Conference Computer Vision (ECCV), pp. 401-417, 2018.

---

Under review as a conference paper at ICLR 2022
Meng Qu, Yoshua Bengio, and Jian Tang. Gmnn: Graph markov neural networks. In International conference on machine learning, Pp. 5241-5250. PMLR, 2019.
Stéphane Ross and Drew Bagnell. Efficient reductions for imitation learning. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pp. 661-668. JMLR Workshop and Conference Proceedings, 2010.
Stéphane Ross, Geoffrey Gordon, and Drew Bagnell. A reduction of imitation learning and struc- tured prediction to no-regret online learning. In Proceedings of the fourteenth international con- ference on artificial intelligence and statistics, pp. 627-635. JMLR Workshop and Conference Proceedings, 2011.
Luana Ruiz, Fernando Gama, Antonio García Marques, and Alejandro Ribeiro. Invariance- preserving localized activation functions for graph neural networks. IEEE Transactions Signal Processing, 68:127-141, 2019a.
Luana Ruiz, Fernando Gama, and Alejandro Ribeiro. Gated graph convolutional recurrent neural networks. In 2019 27th European Signal Processing Conference (EUSIPCO), pp. 1-5, IEEE, 2019b.
Luana Ruiz, Luiz Chamon, and Alejandro Ribeiro. Graphon neural networks and the transferabilityy of graph neural networks. Advances Neural Information Processing Systems, 33, 2020a.
Luana Ruiz, Luiz FO Chamon, and Alejandro Ribeiro. The graphon fourier transform. In ICASSP 2020-2020 IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP), pp. 5660-5664. IEEE, 2020b.
Luana Ruiz, Fernando Gama, Antonio García Marques, and Alejandro Ribeiro. Invariance- preserving localized activation functions for graph neural networks. IEEE Transactions on Signal Processing, 68:127-141, 2020c.
doi: 10.1 00.1099/SP.2209.295555
Luana Ruiz, Zhiyang Wang, and Alejandro Ribeiro. Graph and graphon neural network stability. arXiv preprint arxiv:2010.1222 12529,, 2020d.
Kevin Scaman and Aladin Virmaux. Lipschitz regularity of deep neural networks: analysis and efficient estimation. In Proceedings of the 32nd International Conference Neural Information
Processing Systems, pp. 3839-3848, 2018
Franco Scarselli, Ah Chung Tsoi, and Markus Hagenbuchner. The chniik-chervonenkis dimension of graph and recursive neural networks. Neural Networks, 108:248-231 2018. ISSN 0893-6080.
Michael Schlichtkrull, Thomas N. Kipf. Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. In The Semantic Web 15th International Conference, ESWC 2018, Proceedings, pp. 593-607. Springer/Verlag, 2018.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory algo- rithms. Cambridge university press, 2014.
Gilbert Strang. Linear Algebra and Its Applications. New York: Academic Press, 1976.
Qiaoyu Tan, Ninghao Liu, Xing Zhao, Hongxia Yang, Jingren Zhou, and Xia Hu. Learning hash with graph neural networks for recommender systems. Proceedings of The Web Conference 2020, pp. 1988-1998, 2020.
Ugo Tanielian and Gerard Biau. Approximating lipschitz continuous functions with groupsort neu- ral networks. In International Conference on Artificial Intelligence and Statistics, pp. 442-450. PMLR, 2021.
Herbert Tanner, Ali Jadbahaie, and George Pappas. Stable flocking of mobile agents part dynamic topology. In 42nd IEEE International Conference Decision and Control (IEEE Cat. No. 03CH37475), volume 2, pp. 2016-2021. IEEE, 2003.
Vladimir Vapnik. The Nature of Statistical Learning Theory. Springer Science & Business Media, 1999.
12

---

Under review as a conference paper at ICLR 2022
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 32(1):4 24. 2021.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 974 983, 2018.
Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applica- tions. Al Open, 1:57-81, 2020. ISSN 2666-6510.
13

---

Under review as a conference paper at ICLR 2022
A APPENDIX
B NUMERICAL RESULTS PARAMETERS
All experiments were done on computer with 32gb of RAM, CPU Intel Core i9-9900K @3 @3.60GHz x 16, a GPU GeForce RTX 2080 Ti/PCIe/SSE2, and Ubuntu 18.04.4 LTS.
B.1 RECOMMENDATION SYSTEM
We split the dataset with 90% for the training set, and 10% for the testing set, and we run 20 independent random partitions. For the optimizer, used 5 samples for the batch size, and ADAM algorithm Kingma & Ba 2013), with learning rate 0.005, 31 = 0.9, 32 0.999, and without learning rate decay. For the loss, used the smooth L1 loss. For the GNN, we used ReLU as non-linearity, we considered F 32 features, K filter taps, and
layers.
We used the graph neural networks library available online http:://github.cco/alallaabauuuu houpc///wwwaalbloooosssss/ssssse and implemented with PyTorch.
B.2 DECENTRALIZED CONTROL
We run the system for 7 2s, and used 400 samples for training, 20 for validation, and for the test set. For the optimizer, we used 20 samples for the hatch size, and ADAM algorithm Kingma & Ba (2015) with learning rate 0.0005, 31 = 0.9, Bg 0.999, without learning rate decay. We used one layer Graph Neural Networks with F' 64 hidden units and K filter taps, and used the hyperbolic tangent as non-linearity p. We run 10 independent realizations of each experiment.
We used the graph neural networks libbary available online at https://giiuub.com/alkkk htt..///lllllaabuuumggrappppphp upenn/graph
neural- hwt.://wwww../oooooooco/ooooooon and implemented with Py Torch.
14

---

Under review as a conference paper at ICLR 2022
C PROOF OF THEOREM
Definition 2 (Template graphs). Let {ui)e be the regular n-partition of [0, 11, i.e.
(19)
for 1 Sisn The n-node template graph G. whose GSO we denote S,, is obtained W
[aly W(u,, uz)
(20)
for 1 1.w1s &i.J
Definition 3 (Graphon spectral representation of convolutional filter response). As the graphon W bounded and symmetric. Tw is a self adjoint Hilbert- Schmidt operator, which allows to use the operator's 's spectral basis W (u,
Liezço) Act's ( (w))s(v). Eigenvalues X are ordered in
decreasing order of absolute value i.e., 1> \ 2 X2 Z
A-2 A-1 2 1, and their only accumulation point is 0 (Lax 2002 Theorem 3, Chapter 28). Thus, we define the spectral
representation of the convolutional filter Tu (cf. (o) as,
K-1
R(A)= = Σ h
(21)
k=
Definition 4 (c-band cardinality of W). The c-band cardinality, denoted Biy, is the number of eigenvalues whose absolute value is larger than c.
BW = #(A IAll
(22)
Definition (e-eigenvalue margin W W,). The c-eigenvalue margin of W W, is defined as the minimum distance between two different eigenvalues of the integral operator applied to W, and to Wn as follows.
ww. = min (Il: (Tw...)l III [[A 2
(23)
Definition (Graphon Convolutional Filter). Given a graphon W, graphon signal X, and filter coefficients h = .ho...., hx-1] the graphon filter Th L2( 1)) - L2((0, 1)) is defined as,
K-1
(THX) = Σ h2 hT ())..
(24)
R=
Proposition 1. Let X E (20,,, 1]) be normalized Lipschitz graphon signal, and let Xn be the graphon signal induced by the graph signal Xn obtained from on the template graph Gn [cf. Definition 24 i.e., [x,]; = X(i 1)/n) for < sis n. It holds that
1
| - Xallia S n
(25)
Proof. Let 1, = ( i/n) for Sig n - and Ln [(n - 1)/n, n, 1]. Since the graphon is normalized Lipschitz, for any u E 7,, S Sis n, we have
[x(u) - (x)ll < max
u
<
(26)
n
7
We can then write
|| X111 =
[X(u)
2x)
(27)
1
1
du
(28)
n2
n1
which completes the proof.
15

---

Under review as a conference paper at ICLR 2022
Proposition 2. Let W [0. 1]2 - [0. be normalized Lipschitz graphon. and let W. Wa be the graphon induced by the template graph Gn generated from W as in Definition holds that
2
WW
Wn
S
(29)
n
[(n - 1)/n, 1]. Since the graphon is Proof. Let 1, = [(2 1),n, i/n) for <i n - and Ln
Lipschitz, for any u 4, 1, 1 1 1, S n. we have
i
i
[Wu, v) - Wn w) < max
u j 1
(30)
j
+ max
|
(31)
1
(32)
71
71
n
We can then write
W Wnl
[Wu,,) v) -Wn(u, (T) dude
(33)
< 1
2
2
2 n
dudv
(34)
which concludes the proof.
Proposition 3. Consider the L-layer WNN given by Y (X; H. W), where Fo = Ft = and
F; F' for 1 { 1. Let E (0, and assume that the graphon convolutions in all layers of this WNN have K filter taps [cf. (6)]. Under Assumptions 7 through) 3 the norm of the gradient of the WNN with respect its parameters H (Hu Ji, can be upper bounded by.
| 25 HX;H, Will S F2L
(35)
Proof. We will find an upper bound for any element (H / of the tensor H. We start by the last layer of the WNN, applying the definition given equation
V gett (X: w)ll =
X
(36)
RIKI Σ
W X Hrr,los
(37)
By Assumption 3 the non-linearity is normalized Lipschitz. i.e. (p) < for all u. Thus, aplying the chain rule for the derivative, and the Cauchy-Schwartz inequality, the right hand side of the previous expression can be rewritten as,
F K
I
V te Φ(X; H. WIll
Vp
X2 (eells W
(-1
k=1
(T(h) H
(38)
B-1K-1
<
ΣΣ g=1
(T (k)
H
(39)
Note that the larger bound will occur if < I 1, then by linearity of derivation, and the triangle inequality we obtain,
F
K
V Ha H(
W
<
V
Haallg tt X2 H H
(40)
w
16

---

Under review as a conference paper at ICLR 2022
By Assumption 2 the convolutional filters non-amplifying, thus it holds that,
F
I Ma (X;;H, w S Vi X
Xp-1
(41)
g=1
Now note that as filters are non-amplifying. the maximum difference the gradient will be attained at the first layer (I (I=] 1) of the WNN. Also note that the derivative of convolutional filter Th [cf.
Definition 6 at coefficient k = i, is itself a convolutional filter with coefficients h, The values of h, are [bas] if and 0 otherwise. Thence,
V H patlen H WIll p h w.
(42)
F
|
(43)
To complete the proof note that tensor H has FL-1K elements, and each individual gradient upper bounded by (43). and || is normalized by Assumption [
Lemma 1. Let H W) be a WNN with Fo = Fb, = 1, and Fi = F for 1 < 5 Let
c (0, 11, and assume that the graphon convolutions all layers of this WNN have filter taps
Icf. ( Let (xxn; S.) be a GNN sampled from (XX; H. W) as in 9 Under assumptions
and (5) with probability & holds that,
2
1 +
n log( )
T Biw
(X;H, W) (D W STFL-1
11
1
ww.
n
+ 4LFL-1C
(44)
n
The fixed constants Bey and diw are the e-band cardinality and the c-eigenvalue margin of W and W, respectively [cf. Definitions 45
Proof. We start by writing the expression on the left hand side, using the definition of WNN [ef. 81 we can write,
(X;H, W)
$ (XX,: H. W = [XL - Xnull
(45)
FL K
X Xi-i) )
FL-1 K
X X H
=
w
Since the non-linearity p normalized Lipschitz by Assumption 3 using the triangle inequality, obtain
F
K-1
- X
Σ
(T Σ
(K) X
Σ
(T.. X9 [Heeles
(46)
==1
Using the triangle inequality once again, we split the last inequality into two terms as follows,
F2-1
K-
X - Nnall
<
Tik) W
(X
X29
(1)
K
Σ
(T())
((k) W
X2
H
H
(2).
(47)
W
Where we have split 47) into terms (1), and (2). On the one hand, by assumption convolutional filters are non-an com-lliliy thus using Mauchy-Schwarte inequality, term (1) can be bounded by.
F
K-1
F1
Σ
Σ
X 1-1
X X
|| - X9 x
(48)
g=1
17

---

Under review as a conference paper at ICLR 2022
To bound term (2), denoting higf the spectral representation of the convolutional filter applied to - at feature f of layer [cf. Definition 3), we will decompose the filter as follows,
h (1) 10
if X if A cc
(49)
(LLg(()) hLgs(c) if | <C if if 2 c.
{ (2) (L)
h higs())
(50)
Note that hLof Lgf with filter function h Las on graphons W, and W, respectively [cf. Definition 6] Note that filter
hec "ggl" Let T Halle and T "Hu,llrs' be the graphon convoutional filters
he varies only in the interval c), and since filters normalized Lipschitz by Assumption 2
LLgf" it verifies
| X--1 - -T XL_1 s ([(hog((e) + + - (c) - -e)l(x
(51)
[Hazlar
s 2cll
(52)
Now we need to upper bound the difference in the high frequencies hig Let T [He]er and T 2 "Hadlor"
be the graphon filters with filter function hig on graphons W, and W,, respectively. Let S,,
denote the template graph sampled from the graphon W [ef. definition 2 We denote W,, the
induced graphon by template graph S as in [10.. By introducing T "Hanler" the graph filter with
filter function hāg on graphon Wn, we can use the triangle inequality to obtain,
| Xi-1
2 H. X s Hilb X T
[1in1 X (2.1)
+ F Xh-1
T
(HnLlss X%
(2.2).
(53)
Under assumptions 5 bound term (2.1) we can use (Ruiz al.) 2020a Theorem 1), and to bound term (2.2) we can use (Ruiz et al. 2020d Lemma 2). Thus, with probability - &. the previous expression can be bounded by,
2 1 n log( 2n
Bww Oww.
THE H4 X The Haubb Xi_1
$ 1+
X
(54)
Where the fixed constants Bw and 8ww, are the e-band cardinality and the c-eigenvalue margin of W and W, respectively (ef. Definitions 455) Henee, coming back to (47), we can use (48) to upper bound (1), and we can use (52) and (54), to upper bound (2) as follows,
|| X S
Σ gm1
X9 x 2cllX%
2 2(1 1 + n Io log( 2n E
n BB Bi (1+
||
(55)
dw..
n
Now, we arrive at recursive equation that we can compute for the L layers, with F features per layer, to obtain,
|X Xnull SFo 1Xo
X
+2F
-c|lol
2 1+
log(
L.L-1 ( n BBW.
1
|
(56)
ge ww.
n
Using Proposition [ noting that Fo = 1 by construction, and using Assumption | concludes the proof.
18

---

Under review as a conference paper at ICLR 2022
Lemma 2. Let H W) be WNN with Fu FL 1, and Fi = 1 Let
c E (0, 11, and assume that the graphon convolutions in all layers of this WNN have filter taps lef. J Let (xx, S.) be GNN sampled from (XX; H. W) as in Under assumptions
and (5) with probability - it holds that,
V (X:HH W) VH (X,: H. W..)ll
2 1+ V
log 2m ?
x TBw.. Oww.
S WKL--
2L 222
1+
2F + FT,2
n
Proof. We will first show that the gradient with respect to any arbitrary element bg R of H can be uniformly bounded. Note that the maximum attained if /' = 1. Without loss of generality, assuming / > (- 1, we can begin by using the definition given in equation ( of the
output of the WNN as follows,
I Waaaly (X;H, W)
V Haa ((xn: H. W..]l
V Haatle
X
VIH feetat Xhall
(57)
F 1-1
(TW) xi_ [Hules
(k)
Py-1 K-1
Ha
(T X x Hulls
(58)
g=1 R=1
Taking derivatives by applying the chain rule, and applying the triangle incquality yields,
| (ittihhh XL ViH X
(T (k) X2 x [ ))
(T (k) w x Husles -vp
vp
k=1
Fi 1-11
V VHaatbe
(T (k)
w x (Hulls
(59)
Pi
vp
(T w X al [ixl
(60)
F
F K-1
)|
V W
(T (k) w H
ViHanll
(I (k) w. X X [Hukles
X9
We can now use Cauchy-Schwartz inequality, Assumptions and Proposition to bound the terms regarding the gradient of the non- non-linearity p, the loss function f, and the WNN respectively, as follows.
I 1
X
V H
XL
(61)
Fi
K-
F 1-1
Hiklaf
(T((k)
x x (Hkls
pL- 1l
W
W.
k=1
F
K-1
V Hautlyy
Σ
(T X
[ (T(() x
19

---

Under review as a conference paper at ICLR 2022
We can apply the triangle inequality the second term of the previous bound to obtain,
| itttlet
X V WHe
X
(62)
F1-1 K-
11-1
(T (k) X H
(w. x Hus
1)
F X|ol
9=
(T (1) (Hinlar (T (.....Hn [Huulas) X X
g=1
P1-
TW X - X [Hndar)
Now note that as we are considering the case in which 4 < 11-11 using Cauchy- Schwartz inequality, the same bound for the first and second term of the right hand side of the previous inequality. Since filters are non-expansive by Assumption 3 it yields
|V Mattha XL yt X
(63)
P
K-1
F11K-1
2
2
(k) (TW) xi_1) [Hulos
( (b) w. X
Hin
1 X
F
V
X2_ - X x
Now notice, that the only term that remains to bound is the exact same bound we obtained in equation (7). but on the previous layer L Hence, we conclude that by applying the same steps times, the WNN has L layers, we will obtain a bound for any element [Hr Ig of tensor H.
V (attt xt
V
(H x
(64)
F K
F K
< 22F
(TW) (k)
X2_ HHHll
(k) (
X
H1 1 |
F; ViHhnatb
X9 8P-Xy x3 (x--
Note that the derivative convolutional filter Th at coefficient kt i, is itself a convolutional filter with coefficients h; [ef. Definition The values of h; are hhl;; if j i and otherwise. As h; is itself filter that verifies Assumption 2 as graphons are normalized. Thus, considering 1 O, and using Propositions 2 obtain,
(Chung & Radcliffe 2011 Theorem 1) and the triangle inequality,
(II W.ll + I| Wall) ||ool| + || Xoll
hi Xno - hi.wXo
<
(65)
2 1+ na log( 2m)
π Biw Kww.
1
(66)
71
with probability 1- E. In the previous expression, W. h is the template graphon [cf. Definition Now, substituting (64) into (65), and using Lemma [ with probability 1 E. it holds that,
2n n log
p2L-2 ( | Haallg X Ha X 2212
1 BB.
www
2FL-11 + 8L2 2 2LL-2 n
(67)
To achieve the final result, note that tensor H. has KFT-1 elements, and each individual gradient is upper bounded by (67).
20

---

Under review as a conference paper at ICLR 2022
Lemma 3. Ler H, W) be WNN with Fu FL 1, and Fi 3 Let
c E (0, 11, and assume that the graphon convolutions all layers of this WNN have filter taps lef. J. Let (x,;; S,S,, S,) be GNN sampled from &b (X;; H. W) as in 9 Under Assumptions
with probability Ç holds that,
Vul(Y, H W)) Vul(Y, (X H. W.))
2 1
2n { n noog
π BBw
S KFL-1
3T12
1
0 oww.
4FL-1L
F2L22
n
Proof. In order to analyze the norm of the gradient with respect to the tensor H. start by taking the derivative with respect to a single element of the tensor, [H Igt st- By deriving the loss function l using the chain rule it yields,
V H {(Y, (X; H, W)) - V "pall, <(Y,, (X H. W.))
=IVE H. Wm $(X; W)
- -VE(Y,, ((X,: H. W.)) Hatlyy Φ(X,; H. W.)
(68)
By Cauchy-Schwartz, and the triangle inequality it holds,
IV Waaulll <(Y, ( H. W)) V (aaltt l(Y,, (X,,: H. W.))
VE(Y, (X; W)) VI(Y, (Xx,; H. W W ((X; H. W)
(69)
+ ||VE(Y, (X,, H. W.)) 7 ( H. W) V Haattt $ (X,; H. W.)
By the triangle inequality and Assumption follows,
V H : <(Y, (Y; W)) - (H E(Y,, (X,,; H. W,))
S VV((Y, 4(X; H. W)) VA(Y, (XX,, H. W, V mall (Xx; H. W)ll
(70)
VE(,Y, (X,,; H, W.)) Ve(Y, (Xx: H. W.)) w,)) Ha ((X W)ll
(71)
+ [[[HH,ttt) (X;H, W) V V|H (X,, HH W,)ll
& (I)Y, - Y [Xx,; H. W,)) - (X: H. W) W) (XXHH, W)ll
(72)
+ || [[ H W)
VHH $ (X,: H. W.)]l.
Now we can use Lemmas Propositions and 3 and Assumption to obtain,
V Hatt ((Y, (X; (X;HH W)) Hrutlatst ((Yn, (X H, W.
(73)
2n { 1+ log
$ 3I.2 F2L-2 (1 BBw
&ww,
n
4 L + n
11122 1 21
Noting that tensor H. has KFL- elements, and each individual term can be bounded by (73). the desired result is attained.
Definition 7. We define the constant 7 as,
12VKFF-112
(74)
where is the number of features, L is the number of layers, and is the number of filter taps of the GNN.
21

---

Under review as a conference paper at ICLR 2022
We will present more comprehensive statement of Theorem 1 where include all the smaller order terms in (5).. Notice that the statement of Theorem [ these terms in order to simplify the exposition of the main result. In practice, these smaller order terms vanish faster as n. increases.
in the main body of the paper omits
Theorem 1. Consider the ERM problem in 112 and let o(X; H. W) be an L-layer WNN with Fo = Fr. 1, and Fi F for S I L-11 Let c (0, 1] and assume that the graphon
convolutions in all layers of this WNN have K filter taps fcf. (60). Let 4 (xxn; H.) be GNN sampled
from from (X; H. W) as in ( Under assumptions AS ASS it holds that
ElI, x (X; H. W)) - Vul(Yn, (Xx,: H. WII
1+ v log (2g(223/2)
BBW. Oww.
VKFL-1
6.2. 11..1.2-22
1
71
4FL-11 n where Yn is the graphon signal induced by [ynl: = Y (u4), us (i- 1)/n2 for 1 isisn Icf: (0) The fixed constants Bey and 8iww.. are the c-band cardinality and the c-eigenvalue margin of W and W, respectively [ef. Definitions 4 5
2 2F /
+ 12T. 121.2
(75)
Vn
in the supplementary material].
Proof of Theorem I. We begin by considering the event A, such that,
An = (IVH)(X HH,;H, W)) - VHl(Yng 4 (Kni H. W.))
(76)
2 + n log 2n
BBW. Kww.
KKFL-I
31.2 p2
1
4F
12L" 12L 221-22222)) )
Thus, by considering the disjoint events An, and AG, and denoting 1(:) the indicator function, the expectation can be separated as follows,
e(), 4 H. W)) V ((Xn; H. W.))
E CY (X; H. W)) - Vwl(Kn, ((x,; H. (A))
E V CY, (X; H. W)) Vul(Y,, (X,,, H. (.))
(77)
We can bound the term regarding A using the chain rule, Sannchy-Schwarte incquality, Assumption and Proposition 3 as follows,
V (YY ((X; H. W)) V (X,: H. W.
Vul(Y, ((X; H. W)) + Vw ((X,; H. W.
(78)
< ((X; W)
WI
+ VIVE(Y, 4(X.; H, W Vx H, W.)ll
(79)
< V (X; H. W)l+ V (X,; H, W.)l
(80)
< 2F VK
(81)
Returning equation (77). can substitute the bound obtained in equation 81 and by taking P(A,) = 1 E. and using Lemma 3 it yields,
E||l V (Y, 1 H. W)) Vul(Y,. $ (X H. W.))
1 n log 2n
BBwn
<(1 - 1VV
31,2 22.22
oww.
n
4F L n
+
12L2
+ 22F2LVR
(82)
To complete the proof, set 1
vn.
22

---

Under review as a conference paper at ICLR 2022
W)) - VHL(Y, 2(x,: H. W.))
V p(x,5 n5 H, w)
Figure 3: In order to satisfy the property that the inner product between the gradient on the GNN VHL(Y,, (Xxn; H, w)) and the gradient the graphon Vxe(Y, (X;; W)) positive, rely the condition provided Theorem
D PROOF OF THEOREM
Definition 8 (Stopping time). We define the stopping time k* as.
k A20
x W.)ll & VKFT- 12I p21-2 2c..
(83)
Definition (Constant v/)).
Lemma 4. Under Assumptions and 6 parameters of the GNN H is Ave-iipschirz
the gradient of the loss function with respect to the
|V 40 A W))
( w) S AvellA- BB|
(84)
where Ave = (Av4 + A FeL KK).
Proof. To begin with, apply the chain rule obtain,
IV (X; W)) V V B, W))l
= VV((Y (X; & W) V((Y, ( (X) B))
(85)
By applying the triangle inequality, and Cauchy-Schwartz it yields,
V& ( W)) V= W))l
Vi((Y ((X;A, W )) W V V B, w)ll
4 + V A W)) ((,, (X; X; B, W)) (X; W)ll
(86)
We can now use Assumptions
and as well as Proposition to obtain
VV (X;A, W)) VH (X; W))l S (Ave A 2L VKIAA BI)
(87)
Completing the proof.
Lemma 5. Consider the ERM problem in 12 and let o(X; H. W) be L-layer WNN with
Fo Fr. 1, and F; F for < 1. Let (0, 1] and assume that the graphon
convolutions in all layers of this WNN have K filter taps fcf. (60) Let o 4(x,; H.S.) be GNN
sampled from & (X;H, W) as D.. Under assumptions A ASO let the following condition be satisfied for every k.
1 VntVvllogii log(22333/)
VKI.L-1 (6.. x BW. www.
4FL-1L
+ 121-2
7
n
2F2L +
1- A
Vn (Xx,: He. W.)ll.
(88)
Vn
then the first ke iterates generated by equation (4. 1(k < k)) O H4. W.) form a positive super-martingale with respect the filtration F& generated by the history of the Algorithm up step [i.e., {X,Y, X,N. Yn, W. W.ee (X, Y, X,, Y,, W W.ik-i.... {X, Y, X Y,, W hol- Where k is the stopping time defined in Definition and 1() the indicator function.
23

---

Under review as a conference paper at ICLR 2022
Proof. To begin with, 1(k k=) (X;HH, W)) FR, where Fis is the filtration generated by the history of the Algorithm up to k. Note that the loss function l is positive by Assumption 4 remains to be shown the inequality expression of the super- supermartingale. For k > k", the inequality trivially verified as the indicator function (k I k*) = for k > k². For k S k", as in [erttekas & Tsitsiklis (2000), define continuous function g(c) that takes the value of the loss function the Graphon data on iteration & + at e = 1, and on iteration & on = 0 as follows,
g(() E(Y, ((;; en V (Xx; HR. W,)), W)).
(89)
Note that function g(t), is evaluated on the graphon data Y, X, W, but the steps are controlled by the induced graphon data Y,, Xn, W,, Applying the chain rule, the derivative of g(t) with respect to can be obtain as follows,
dc g(()=
(90)
Vu((Y, -7 Vul(Y, (H4; Wa: X,)),, V (Xxn H4: W.)).
Now note that the difference in the loss function between iterations k + and & can be written as the difference between g(c= = 1) and g(c 0) as follows,
((1) - (0)) EYY 4 (x;; H4+1, W)) E(Y, (X; Ha. W)).
(91)
Computing the integration of the derivative of g(t) between [0, 1] it yields
E(Y, (X; W)) ((Y, (X:;Ha W)) - 9 - -((0) = (/a00)/((///
de gl
(92)
= - VHl(Y, (xx H4 - erj VHl(Yn, (X,; Hs. W.)), W))
Vx)(H, (X,: H4. W. d.))
(93)
Note that the last term of the previous integral does not depend on Besides, we can sum and subtract VX,(Y, (HH, W, X)) inside the integral, to obtain,
A(Y (X; HA+1, W)) {(Y, ((X; (xHHe, He, W))
= (-) Vel(Yn (X,n; He, W.))
L VullY, (X; H4 eT V V ((X,, HR. Wt)), W))
VHl(Y, (X: Hr. W)) Vxl(Y, Φ(X; H4, W))de
(94)
- V (Xn; H4. W W.)) 4XX; Hr. W)) S de
Th VN (X,; Hr. W.)) / VHl(Y, ( co Vul(Y,, ((,,; H4. W.)), W, X))
Vul(Y. + (X: Hd. W))de.
(95)
We can now apply the Sauchy-Schwarc inequality to the last term on the previous inequality, and take the norm of the integral, which is smaller that the integral of the norm to obtain,
E(Y, (XX; H4+1, W)) I(Y, (X; Hs, W)) -7 Vxe(Y, 4 (H4; Wx; X..) HEY,, ((H,, W,
+ (His W X,,)II L. Vul(Y, (HH, cT Vul(Y, *HHs W.;X,)), W, X)))
Vxe(Y, W, x))x)
(96)
24

---

Under review as a conference paper at ICLR 2022
Under Lemma 4 take the Lipschitz bound the gradient on the loss function with respect to the parameters, using Ave. to obtain,
{(Y, (X; W)) E(Y, ( H4, W))
x mm VHe(Y, (X Hu, w.)) V W))
Avens VHl(Y, $ ( Hk. W.)) ["
The VeVeee D(Xni He, W.))
(97)
- 7 H (X HR. W (X;;4,, W))
T VHe(Y, (X,,: NR. W,))
(98)
Instead of evaluating the internal product between the gradient on the graphon, and induced graphon, we will use Theorem [ to bound their expected difference (cf. Figure for intuition). We can add and subtract the gradient of the loss function on the induced graphon V vvl(Yn, (HH,; W.; X,)), and use the
Schwartz inequality to obtain,
<(Y, (XX; W)) - ((Y, -() ( W)) m VuL(( (X, H4, W,)) (V 1 (X; H4. W)) + Vx((Yn, ( Hr. W.)) Vul(Yn P(X,i H4, W.)))
+ n2A
VH (X Hv. Wx))
(99)
Th V 1 (Nni Hr. wn))
Tkl VnL(Yn, 1 (Xn: H4. W. Ill VH ( W)) Vnl(Yn, D(X.: H4. W,))
A
VH 1 nx Hr. 3
(100)
2
We can rearrange the previous expression, to obtain,
7h V 4XX.; He. W., 1 Avelk
2
VHl(Y, (X; HAs W)) - VHl(Yn, (X.s H4. W Wx)) [V 4 4(X,; H4, W.)
S ((Y, (X;H4, W)) {(Y, H4 W)).
(101)
We can now take the conditional expectation with respect the filtration F, to obtain,
B[e(Y, (XX; H4+1, W]][FF]]
< mil VnllVxe((,, 10 (X.i He, W.) Avelk 2
V VY 2 (X; HR. W)) Vul(Y,, ( Hr. W.)) VV (Xx; H4, W.)
E
Fj
+((Y, (XX; H4, W)).
(102)
As step size 7is > 0, and by definition norms are non-negative, using Theorem I as condition (8 holds for k < k*, then
E(e(Y, (X; W)) < ((Y, (X; W)).
(103)
By definition of maren-nat in Durrett 2019). we complete the proof.
Lemma 6. Consider the ERM problem in 12 and let ((X; H. W) be L-layer WNN with
F, = F,. = 1, and Ft F for < 1 S 1. Let c E (0, 1] and assume that the graphon convolutions in all layers of this WNN have K filter taps [cf. (6). Let (xx,; H.S., S.) be GNN
25

---

Under review as a conference paper at ICLR 2022
sampled from (X; H. W) as in ( Under assumptions AS6 for any E (0, - Aven), if the iterates generated by (14) satisfy,
1 + wn log((28/2)
π TBw.
4F + + x22-2c
VKLL-1
66 222222222
1+
8 oww.
n
2F
VK
AveTTs
VVel( (X Ha, W.)
(104)
Vn
2
then the expected value of the stopping time k2 Icf. Definition 8y. is finite, i.e.
011/e)
(105)
Proof. Given the iterates at k*, and the initial values at O, we can express the expected difference between the loss E, the summation the difference of iterates follows,
E Ho W)) - E(Y, ( W))]
E
E(Y, (X; W)) E(Y, (X; W)
(106)
Taking the expected value with respect the final iterate k-, we get,
E (Y, (X;; H4m))
E(V, (XX; Hxx)))
k'
H4 - (x; w) k3
= Es
E
E(Y,
(107)
E
{YY, H4-1, W)) - E(Y, He. w)
P(k" =t)
1=0
(108)
Using condition (104. and Lemma for any k < k*, it verifies
E ((Y x Hx-1, w)) E(Y, (X; HA. w)) 2 nnVisFt-112 22 2
(109)
Thus, coming back to (188).
E (YY (XX; H40 w)) ((Y, (e; w)) 2 2 222 Σ IP(k =
(110)
2 n(v 1 2c
(111)
Note that as the loss function is non-negative,
E ((X; W))
2 B[k"]
(112)
ry( (V k/VKFL-11222 P2L-222222222000001 -
Thus concluding that 1- - O(1/e).
Theorem 2. Consider the ERM problem in 12) and ler x(X; H. W) be an L-layer WNN with F, Ft 1, and F; F for < 1 1. Let (0. 1 and assume that the graphon convolutions in all layers of this WNN have K filter taps [cf. (6). Let x(x,; S..) be a GNN sampled from (X; (XH, H. W) in 19. Consider the iterates generated by equation 14 Under
26

---

Under review as a conference paper at ICLR 2022
Assumptions ASO for any fixed (0,1 Aver), if each step l the number of nodes is picked such that it verifies
+ Vn
VKLL-1
6L2
1+
a TBw.
4F
+ 1212222222
oww,
2F2"/KK
Avens
Vue(Y (x Hy, W.)l
(113)
Vn
2
then in finite time we will achieve an iterate k* such that the coefficients Hy satisfy
Bel (X; w)) - 24v KF
with probability 1
(114)
where Aven = (Av4 + Ag. F21, F2 ).).
Proof. We can use Lemma
6 to conclude that it must be the case that P(k 00) 0, which
implies that, P(k* < <00) Using stopping time k* condition [ef. Definition and the triangle inequality, yields,
VlIVv (X; w)lll S VCl(Y, @Xnn HK. W,))
(115)
+B VHl(Y, ((X; Ha, W.)) VHl(Y, D(0,; Ha, w.))
Note that the iterates are constructed such that, for every k
E| vel (XX; H4, W.)) Vue(Y, 4 nK HR. W,)) S VV ( Hk. W.
(116)
Using the stopping time condition, the final result is attained as follows
EYY (XX; He- W))ll 2 V Vul(Y, (X; H4' W,))
(117)
<2N
(118)
27


Reviews:
[{"review_id": "KKBd6DJJ4g", "reviewer": "Reviewer_n2bA", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros. \n1.\tThe writing of this paper is clear. It is easy to follow the idea and algorithm details proposed by the authors.\n2.\tThe theoretical guarantee of the algorithm is solid. \n3.\tThe convergence performance on the small datasets in the experimental part seems effective.\n\nCons.\n1.\tMotivation. This paper seems to lack a good elaboration of the motivation on why using graphon neural networks. The authors claim in Section 3.2.2 that graphon neural networks can be seen as a generative model for GNN. Can we understand that the graphon neural network is only used to generate a small subgraph from the original graph? If yes, then it would be better for the authors to further explain why other simple generative methods are not chosen as the way to generate the subgraph. If not, can the author further explain what are the superior characteristics of applying graph neural networks?\n2.\tPrevious work. I think some previous works [1,2,3] were also proposed to address the issue of scalability of training a graph neural network model. How is the proposed method compared to them?\n3.\tExperiments. The settings for the experiments are not convincing to me. First, the authors claim that their methods are designed to handle the issue of the scalability of training graph neural networks. However, the size of datasets in the experiments is only ~1k. I think it would be better to conduct some experiments on significantly large datasets. Second, in Fig 2 the authors only show the results of training a normal graph neural network by 10 epochs and 30 epochs. There is no evidence that the training of the graph neural network has already converged by this epoch. As a result, it is not convincing that the algorithm proposed can converge to a normally trained graph networks model. Third, there is no result of previous working methods.\n4.\tFurther discussion of the universality of the proposed model is important. Does this method fit for all kinds of graph neural networks or only some specific models?\n\n\n\n[1] Chiang, Wei-Lin, et al. \"Cluster-GCN: An efficient algorithm for training deep and large graph convolutional networks.\" Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2019.\n[2] Zeng, Hanqing, et al. \"Graphsaint: Graph sampling-based inductive learning method.\" arXiv preprint arXiv:1907.04931 (2019).\n[3] Chen, Jie, Tengfei Ma, and Cao Xiao. \"FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling.\" International Conference on Learning Representations. 2018.\n", "summary_of_the_paper": "This paper proposed an effective and scalable algorithm to train the graph neural network. Their method leverages the framework of graphon neural networks to enlarge the training size of GNN during the training. Specifically, a growing size subgraph is sampled from graphon by a Bernoulli distribution and fed to a graph neural network. A Theoretical guarantee is given for the convergence of the algorithm by proving the absolute value of gradient will decrease to a small value surely.", "summary_of_the_review": "In conclusion, this paper proposed a novel way to handle the issue of scalability of training a graph neural network model. However, the disadvantages of the paper mentioned above, especially the lack of a well-elaborated motivation and the weakness of experimental settings, hurt the value of this work. Thus, a reject is recommended here.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ALYEuMCM-uf", "reviewer": "Reviewer_3Wdv", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths**\n\n1. The paper is easy to follow, and it does a good job of describing the WNN proposed by Ruiz et al., 2020. The introduction to GNNs is similarly clear.\n\n2. The poor scalability of GNNs is an important problem that the community should solve to facilitate the adoption of GNNs in large-scale settings. This work is an attempt to address that problem. \n\n3. The authors do a good job of explaining the theoretical results intuitively, making it easy for the reader to navigate the somewhat complex math derivations. \n\n**Weaknesses**\n\n1. Theorem 1 states a similar thing to Theorem 1 of Ruiz et al., 2020: the distance (in one case of the output, in the other case of the gradients) between the GNN and the WNN is bounded by a term that depends on the number of nodes and a few other hyperparameters. \nThe authors themselves point this out in Section 2, saying that their results are an \"extension\" of the other paper's.\n \n    - Why are the differences between the two theorems significant? Why couldn't the results of Theorem 2 be expressed in light of Theorem 1 by Ruiz et al.? \n\n    - There are also some similarities between the two papers, down to things like notation, (sub)section names, the content of some sections, and one of the two experiments. The authors should highlight better this \"debt\" towards the other paper.\n\n2. How does the theory guide the user in choosing how many nodes to add at each epoch? The authors compare adding 2.5%, 5%, 7.5% and 10% of the full dataset at each epoch: how were these numbers chosen? Isn't the cost reduced only by a constant factor and only for the first few epochs?\n\n    Related to this: it is not clear if the authors want to improve the total training time or the maximum cost in terms of memory/size, and they should make it clearer. \n    In either case, anyway, the algorithm is only a temporary stall that ultimately has the same scalability issues as the typical training procedure.\n\n3. When using real graphs, there may not be enough nodes to satisfy (16) and therefore convergence is not guaranteed. \n    - What happens in that case? \n    - How soon does $k^*$ occur, in practice, when using Algorithm 1? \n    - What is the minimum number of nodes, in practice, that we can add at each iterate while ensuring that the GNN follows the WNN?\n\n    The authors should perform a controlled/synthetic experiment to give a quantitative answer to these questions, which would also alleviate the concerns I raised in the previous comments and provide valuable insight to the reader.\n\n4. How does the proposed method compare to typical subgraph batching? \nBy training on random subgraphs, the cost is fixed and the GNN is exposed to a great diversity of local neighbourhoods structures. \nThis is an essential baseline that cannot be ignored in the analysis of Algorithm 1 (since it also has a lower overall cost than what was proposed by the authors). \n\n5. One of the main objectives of the paper is to \"address the computational burden of training a GNN on a large graph\".\nHowever, the largest graph used in the experiments has 1000 nodes while the other one has 100 nodes.\nThe experiments should be run on one or more large-scale graphs to empirically show that the algorithm works (e.g., some OGB benchmark).\n\n6. Figure 1 seems to indicate that there is no difference in how many nodes are added at each epoch, and that having 200-300 nodes is already more than enough for achieving performance similar to when we have 1000 nodes. \nThis seems like a result about the data efficiency of GNNs more than a result about Algorithm 1. \n\n7. Figure 2 should show the convergence of the GNN trained on the full graph. \nIt could be that the full GNN converges quickly to a low error, meaning that we could stop training much earlier than 10 epochs. \nIf one of the advantages of the proposed method is to reduce the computational cost of training the GNN, then this advantage should be quantified in the experiments.\n\n**Other comments**\n\n8. Figure 2 can confuse the reader because the red and purple horizontal lines are not a function of the epochs, they indicate a constant value. \n\n9. It would have been nice if the authors had included the code to reproduce their experiments with the submission. \n\n10. Sec. 3.1, first paragraph: the citation to Gama et al. 2018 uses the textual format instead of the parenthetical. Also, I'm not sure that a GNN paper from 2018 is the best reference for basic notions of graph theory like the adjacency matrix and the Laplacian. \n\n11. Line 4 of Algorithm 1 assumes that a dataset of graphons is available. This is never the case, so that line/notation should be changed or improved. \n\n**References**\n\nRuiz et al., \"Graphon neural networks and the transferability of graph neural networks\", Neural Information Processing Systems (2020).", "summary_of_the_paper": "This paper shows that a graph neural network (GNN) trained on an increasingly larger graph behaves like a graphon neural network (WNN), the \"limit object of a GNN\", which arises when considering a continuous graphon instead of a discrete graph (the graphon can be seen as a generative model from which the discrete graph is sampled). \n\nThis observation is translated into two theorems that bound the expected distance between the GNN and the WNN as a function of the number of nodes used to train the GNN. \n\nThe authors then propose an algorithm to train a GNN by gradually adding nodes to the training data, leading to a computational advantage compared to training the GNN on the full dataset from the start.", "summary_of_the_review": "In its current state, the paper is not ready for publication: \n\n- The relation with Theorem 1 of Ruiz et al. 2020 is unclear.\n- The theoretical analysis is not sufficient to justify Algorithm 1, since it is based on an assumption that might not hold in practice. \n- The paper does not show evidence of having solved the main problem that it sets out to solve (ie, reducing computational costs).\n- The experimental evaluation is insufficient (not enough experiments, no baselines, and too small graphs) and the results raise some questions.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "8SHBLp99we", "reviewer": "Reviewer_TUDu", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n1) Reducing the computational burden of training a GNN is important, as in practical use cases, e.g., graphs like social networks usually are huge, and cost many resources to train and fine-tune.\n2) Proofs on the feasibility of the proposed method and convergence of algorithms are of great interest and give an intuition for why an algorithm would work.\n3) In general, the main flow of the paper and ideas are clear.\n\nCons/questions needed to be addressed:\n1) I observed that $F_0=1$ is highlighted many times in the paper, which means that the input is $\\bf{x}\\in \\mathbb{R}^n$. Does it mean that the derived proof and conclusion only apply to the case where the input feature at each node has dimension one? Please clarify this.\n2) In Theorem 1 and 2, please mention the definition of $\\bf{W}_n$ or $\\bf{\\Phi}(\\bf{x}_n; \\mathcal{H}, \\bf{W}_n$) to make them self-contained.\n3) Some comments should be added to clarify how Theorem 1 and 2 connect to GNN, i.e., $\\bf{\\Phi}(\\bf{x}_n; \\mathcal{H}, \\bf{S}_n)$. The proofs are done for $\\bf{\\Phi}(\\bf{x}_n; \\mathcal{H}, \\bf{W}_n)$, but to my understanding, Algorithm 1 produces $\\bf{\\Phi}(\\bf{x}_n; \\mathcal{H}, \\bf{S}_n)$ (or $\\bf{S}_n$). Are $\\bf{\\Phi}(\\bf{x}_n; \\mathcal{H}, \\bf{S}_n)$ and $\\bf{\\Phi}(\\bf{x}_n; \\mathcal{H}, \\bf{W}_n)$ asymptotically close to each other in some sense?\n4) For theorem 1, Is (15), i.e., that the learning steps of $\\bf{\\Phi}(\\bf{x}_n; \\mathcal{H}, \\bf{W}_n)$ and $\\bf{\\Phi}(\\bf{x}_n; \\mathcal{H}, \\bf{W})$ are close, sufficient to indicate the $\\bf{W}$ and $\\bf{S}_n$ are \"close\" in some sense? Please clarify this.\n5) In Section 5, Figure 1(b). It seems that the \"25 Nodes Added (blue line)\" case has the best performance as the relative RMSE drops at epoch 2. Is this expected? Further, please give some intuitions/or suggestions for how to choose the number of nodes added in each step.\n6. It could be future work, but to me, the graph sizes in the numerical results are not very large. It would be great to see the results on larger graph sizes, so that the contributions of this paper are well supported.\n\nA minor issue:\n1) Before (10), \"a WNN ca be\" should be \"a WNN can be\".", "summary_of_the_paper": "In this paper, the authors propose a method that learns a large graph neural network (GNN) starting from a relatively smaller GNN which would increase its number of nodes step by step (epoch by epoch). Most importantly, the paper gives mathematical proof to show that the gradient descent steps on GNN are close to the graphon neural network (WNN) which is the limit object of the GNN. This paper also demonstrates its proposed method on a recommendation system and a decentralized control problem and shows reduced computational cost.", "summary_of_the_review": "In general, I think the problem investigated in the paper is important, and learning from smaller GNN to approximate its limit object is of interest. Also, it is great to see the theorems and proofs are well stated in the paper to help understand the algorithm. However, I still hope that the authors could answer the question or make clarifications to some issues mentioned above.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a scalable learning method for GNN that gradually increases the training data size by randomly adding vertexes generated from a graphon. Theoretical justification to the proposed method is given that bounds the difference between the gradients on the sampled network and on the graphon. A numerical experiment was conducted to support the validity of the proposed method. 

Unfortunately, this paper contains several issues as listed below:  
1. Novelty: There are already some existing work  to address the issue of scalability of training a graph neural network model. However, the relation to them is not appropriately exposed.  
2. Experiments: Although the main purpose of this paper is to resolve the scalability of GNN, the numerical experiments are conducted only on a small scale dataset ($\sim$1k).  
3. Practicality: There are several hyperparameters. However, the theory and methodology do not give a practical guideline to determine them (e.g., how many vertexes should be added at each epoch).  
4. Correctness: The proof of the theorems would contain some flaws, which should be resolved by the authors. However, there was no response from the authors.

For these reasons, this paper would not be appropriate to appear in ICLR.
Decision: Reject