Generalization Analysis of Message Passing Neural Networks on Large Random Graphs
Authors: Sohir Maskey
Ron Levie
Yunseok Lee
Gitta Kutyniok
Venue: NeurIPS 2022 Accept (2022)
Keywords: graph neural networks
message passing
generalization
convergence
large random graphs

Abstract: Message passing neural networks (MPNN) have seen a steep rise in popularity since their introduction as generalizations of convolutional neural networks to graph-structured data, and are now considered state-of-the-art tools for solving a large variety of graph-focused problems. We study the generalization error of MPNNs in graph classification and regression. We assume that graphs of different classes are sampled from different random graph models. We show that, when training a MPNN on a dataset sampled from such a distribution, the generalization gap increases in the complexity of the MPNN, and decreases, not only with respect to the number of training samples, but also with the average number of nodes in the graphs. This shows how a MPNN with high complexity can generalize from a small dataset of graphs, as long as the graphs are large. The generalization bound is derived from a uniform convergence result, that shows that any MPNN, applied on a graph, approximates the MPNN applied on the geometric model that the graph discretizes.

Generalization Analysis of Message Passing Neural Networks on Large Random Graphs
Sohir Maskey*
Ron Levie*
Ludwig-Mon Maximilaa University of Munich maskeydmath. 1mu de
Technion Israel Institute of Technology
levieron@technion. atw.chhnion.c......... ac
Yunseok Lee Ludwig-Man Maximilian University Munich ylee@math. llmm de
Gitta Kutyniok
Ludwig-Min Maximiliia University of Munich" University of Tromsø kutyniok@mate lmu
Abstract
Message passing neural networks (MPNN) have seen a steep rise in popularity since their introduction generalizations of convolutional neural networks to graph structured data, and are now considered state-of-the-art tools for solving large variety of graph-focused problems. We study the generalization error of MPNNs graph classification and regression. We assume that graphs of different classes are sampled from different random graph models. We show that, when training MPNN on a dataset sampled from such distribution, the generalization gap increases in the complexity of the MPNN, and decreases, not only with respect to the number training samples, but also with the average number of nodes the graphs. This shows how MPNN with high complexity small dataset of graphs, as long as the graphs are large. The generalization bound is derived from uniform convergence result, that shows that any MPNN, applied on graph, approximates the MPNN applied on the geometric model that the graph discretizes.
generalize from
Introduction
graph is an abstract structure that represents a set of objects along with the connections that exist between those objects. In many important fields, such chemistry, biology, social networks, computer graphics, data can be described by graphs. This has led to tremendous interest in the development of machine learning models for graph-structured data in recent years. A ubiquitous tool for processing such data are graph convolutional neural networks (GCNNs), which extend standard Fuclidean convolutional neural networks (CNNs) to graph-structured data.
Most GCNNs used in practice can described using the general architecture of Message Passing Neural Networks (MPNNs). MPNNs generalize the convolution operator to graph domains by neighborhood aggregation or message passing scheme. By r ((t-1) denoting the feature of node in layer - 1 and e denoting edge features from node j to i, one layer in message passing graph
'The first two authors contributed equally to this work
I Department of Mathematics, LMU Munich, 80333 Munich, Germany
Faculty of Mathematics, Technion Israel Institute of Technology, 32000 Haifa, Israel Department of Physics and Technology, University of Tromse, 9019 Tromso, Norway
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

neural network is given by
p = = ( 1/--1
, seNo)
where (1) is the set of nodes connected to node i, AGG denotes a differentiable and permutation invariant function, e.g., sum, mean, or max, and ()(() and d(() denote differentiable functions such as MLPs (Multi-Layer Perceptrons) [Fey and Lenssen, 2019].
MPNNS have shown state-of-the-art performance in many graph machine learning tasks such as node or graph classification. As such, MPNNS had tremendous impact to the applied sciences, with promising achievements such as discovering a new class of antibiotics [Stokes et al., 2020], and has impacted the industry with applications in social media, recommendation systems, and 3D reconstruction, among others (see, e.g.. (Ying et al., 2018, Wang et al., 201 8a,b, Monti et al., 2019, Fan al., 2019]). The practical success of MPNNS led to significant boost in research aimed at understanding the theoretical properties of MPNNs. See, e.g. the variational inference point of view of MPNNs [Dai et al., 2016], and algorithmic alignment of MPNNs with combinatorial algorithms [Xu et al., 2019, Morris et al., 2019].
In this paper study the generalization capabilities of MPNNs with mean aggregation in graph classification task. Previous works developed generalization bounds that do not depend on any model of the data, namely, graphs in these works can be generated and labeled in any arbitrary way [Scarselli et al., 2018, Garg et al., 2020, Liao et al., 2021] In this work, we consider a generative model for the graphs which is theoretically powerful and general on the one hand, and allows much tighter generalization bounds on the other hand.
Formally, we are given pairs of graphs and graph signals x = (G, f) and target output y, where (x, are jointly drawn from a distribution jlg (x, The goal is to learn a MPNN θ that approx- imates y by (x)). For this, one uses loss function L, which measures the discrepancy between the true label y and the output of the MPNN (xx). The aim of a machine learning algorithm is to minimize the statistical loss (also called expected loss)
Reep ( = -(x [(((()).))
In (data-driven) machine learning one has only access to training set instead of knowing the distribution jg-- Namely, we consider a multi-graph setting, where the training set 'T (x* (G', ("),"") is collection of m samples drawn i.i.d. from the distribution (x( Then, instead of minimizing the statistical loss, one minimizes the empirical loss, given by
m
Remp (0)
m Σ 2(0(')),
The optimized MPNN then depends on the dataset, and is hence denoted by Oy. The generalization error is defined to be
GE(@r) Reep Remp(OT) (θT)l-
(2)
One then usually bounds (2) by the uniform generalization error
GE = sup (e) - Reepp (e)),
(3)
where the supremum is taken over some space MPNNs. Bounds of GE typically take the form Th (NN,, where C' is a constant that describes the complexity of the model class (e.g., number
GF < C of parameters), m is the size of the training set, and (NN) is a constant that depends on the (average) size of the graphs. For such bounds, see, e.g., VC-dimension based bounds [Scarselli al., 2018], Rademacher complexity based bounds [Garg et al., 2020], and PAC-Bayesian based bounds [Liao et al., 2021].
While in previous bounds from the literature (NN) either increases in N or in the average degree, in this paper we develop generalization bound that decays in the average number of nodes N. The idea is to treat the nodes of each graph as randomly sampled from some random graph model. In this point of view, not only the different graphs x are seen random samples, but the union of all nodes of all graphs comprise together the random samples of the empirical loss. In the spirit of Monte Carlo theory, such a point of view should lead decay of the error between the empirical

---

and statistical losses as N increases. As opposed to graphs, nodes cannot be seen as independent. due to the correlations entailed by the graph structure. Hence, our analysis focuses on developing Monte Carlo error bounds in correlated nodes regime.
Since in our approach we model graphs as randomly sampled from underlying continuous models, we define the application of message passing neural networks, not only on graphs, but also on the underlying space from which graphs are sampled. We then formulate and prove the following convergence result, that we write here informally. Let x = (G,f) be drawn from the model X, then with high probability, we have for all MPNNs
[x(()) - (x)] = O(N
where NN is the number of nodes in and 0. Based on this convergence result, we able prove a generalization bound that decays in N.
1.1 Validity of the Proposed Model
The random graph models in our work are graphons [Lovász, 2012] with associated graphon signals (see Definition 2.3). The main assumption in our analysis is that graphs that sampled from the same graphon belong to the same class. While this may seem like a limitation, it is actually a very mild and reasonable assumption. It is well known that equivalence classes of isomorphic graphs can be characterized by homomorphism densities [Lovász, 1967]. Namely, given two graphs G1, G2, if (and only if) for every simple graph F the number of homomorphisms from F to G1 is equal to the number of homomorphisms from F to G2, then 11 is isomorphic to G2. Graphon analysis relaxes this observation to a continuous similarity measure. A sequence of graphs {G, JeN is said to converge in the graphon sense, if for every simple graph F the homomorphism densities of F in the graphs (Gjbee converge to some value. Graphs from such a sequence can be thought of as being similar in some sense which relaxes the combinatorial notion of graph isomorphism. Moreover, for each such converging sequence, there is a unique (up to some symmetry) limit object, called graphon. This graphon is also seen as generative model for graphs in the respective sequence, where graphs are generated by randomly sampling the graphon (see Definition 2.3). Now, since is well known that MPNNs cannot distinguish between isomorphic graphs, it is also unreasonable to expect them to separate two graphs that are sampled from the same graphon. We hence assume that two graphs that are sampled from the same graphon belong to the same class (but not necessarily vice versa). This assumption allows us to derive a generalization bound that is much tighter than previously proposed bounds (see Figure for comparison).
From a practical stance, our graphon assumption is reasonable since many graph models are special cases of graphons, like Erdös-Rényl stochastic block model, and random geometric graphs [Penrose, 2003]. Moreover, the decoder of graph variational autoencoder [Kipf and Welling, 2016] can be seen as graphon.
1.2 Related Work
In this subsection we briefly survey different approaches for studying the convergence and generaliza- tion capabilities of GCNNS that were introduced in previous contributions. We give a comparison with our results in Section 3.
Levie et al. [2021] introduce the notion of GCNN transferability - the ability to transfer GCNN between different graphs, which is closely related to generalization. For example, Levie et al. [2019], Gama et al. [2020], Kenlay et al. [2021] show that the output of spectral-based GCNNs linearly stable with respect to perturbations of the input graphs. Levie et al. [2021] prove that spectral-based methods are transferable under graphs and graph signals that are sampled from the same latent space. Keriven et al. [2020], Ruiz et al. [2021a,b), Maskey et al. [2021] show that spectral-based GCNNs are transferable under graphs that approximate the same limit object - the so called graphon. Cervino et al. [2021] show that gradients of spectral-based GCNNs are transferable under graphs that approximate the same graphon.
Scarselli et al. [2018] provide generalization bounds that are comparable to VC-dimension bounds known for CNNs. These bounds are improved by Garg et al. [2020], who provide the first data depen- dent generalization bounds for MPNNs with sum aggregation that are comparable to Rademacher bounds for recurrent neural networks. Liao et al. [2021] derive generalization bound via a PAC- Bayesian approach that is governed by the maximum node degree and spectral norms of the weights
3

---

Verma and Zhang [2019a] consider generalization abilities of single-layer spectral GCNNs for node- classification task and provide generalization bound that directly proportional the largest eigenvalue of the graph Laplacian. Another work along these lines comes from Yehudai et al. [2021], who show that certain MPNNs (with sum aggregation) do not generalize from small to large graphs.
1.3 Main Contributions
We follow the route of Keriven et al. [2020] and consider graphs as discretizations of continuous spaces in our analysis, called random graph models (RGM, see Definition 2.3). We introduce a continuous version of message passing neural networks the realization of MPNNs on random graph models, which we call cMPNNs. Such cMPNNs are seen as limit objects of graph MPNNs, when the number of graph nodes goes to infinity. We prove, up to our knowledge, the first convergence result of the graph MPNN to the corresponding cMPNN as the number of nodes increases, which is uniform in the choice of the MPNN.
For the generalization analysis, we assume that the data distribution Pg represents graphs which are randomly sampled from a collection of template RGMs, with random number of nodes. Using our convergence results, we can then prove that the generalization error between the training set and the true distribution is small. Here, we give the following informal version of Theorem 3.3.
Theorem 1.1 (Informal version of Theorem 3.3). Consider a graph classification task with m training samples (x' (').. T= y") drawn i...d. from the data distribution pg yx) on metric-measure space x of dimension xx- Suppose that the size N of each graph in T is drawn from a distribution v. Then
sup (Remp( ReepRRep REEp (0)))
C E [N
ET-ug
The constant C' represents the complexity of the hypothesis space of the network, via the Lipschitz constants of the message and update functions and the depth of the MPNNs.
Theorem 3.3 shows how we can fewer graphs m than model complexity C' when training MPNNs if the graphs are sufficiently large.
2 Preliminaries
weighted graph G = (V. W. E) with N nodes is a tuple, where V [1, is the node set. The edge set is given by E c V x V. where (i.j) E E if node and j are connected by edge. W = (W,,)),, is the weight matrix, assigning the weight Wa, to the edge (i. E E, and assigning zero if (i,j) is not an edge. The degree d; of a node i is defined as d; Σーー waj. If G is simple graph, i.e., weighted graph with W E 10,
the degree d; the number of nodes connected to node by an edge. We define graph signal f: V - IR* as function that maps nodes to their features in R. where F E N is the feature dimension. The signal can be represented by matrix f f= (f. fx) E NXF,, where f; R is the feature at node i. We also call f a (graph) feature map.
For a random variable Y distributed according to k. and a function F Y,, we denote by (F(x)((())) the expected value of F(Y). Similarly, we denote by (arr) the variance of F(Y).
2.1 Message Passing Graph Neural Networks
Message passing graph neural networks (gMPNNs) are defined by realizing an architecture of message passing neural network (MPNN) on a graph. MPNNs are defined independently of particular graph.
Definition 2.1. LerT N denote the number of layers. Fort = L...., T, let p(t) 22 + 4 and ((t) 1 > R. be functions that we call the message and update functions, where F. N. is called the feature dimension of layer t. The corresponding message passing neural network (MPNN) θ is defined to be the sequence
θ (()()))
1==1 (1)()) )

---

The message and the update function in Definition 2.1 are often defined as multi- latiiillye---peee perceptrons (MLPs). MPNNs, messages are sent between nodes and aggregated. An aggregation scheme is permutation invariant function that takes the collection of features in the edges of each node and computes new nodes feature. this paper, we consider MPNNs with mean aggregation. Then, gMPNN processes graph signals by realizing a MPNN on the graph as follows.
Definition 2.2. Let G = (V, W) be a weighted graph and è be MPNN, as defined in Definition 2.1. For each t {T)....T},
define the gMPNN (0) the mapping that maps input graph signals f = ((0) E Nx to the features in the 1-th layer by
C PRNX f p()) (1
where p(t) NxFt are defined sequentially by
1 N
wis ( (P(1 p11-11)
m
d;
(()) = (T()
(1)
m )
for every E V. We call Og = 0 message passing graph neural network (gMPNN).
Given a MPNN @ as defined in Definition 2.1, the output @g(f) WxFr is graph signal. In graph classification or regression, the network should output single feature for the whole graph. Hence, the output of gMPNN after global pooling is single vector @[()) E R.r,, defined by
1 Σ @c()..
(
N
For brevity, in this paper we typically do distinguish between a MPNN and its realization on graph.
2.2 Random Graph Models
Let (x, d, μ)) be a metric- space, where x is set, d is metric and μ is probability Borel measure.
A kernel (also called graphon), is measurable mapping W X + R. The points E X of the metric space are seen as the nodes of a continuous model, and the kernel is seen as a continuous version of weight matrix. Kernels are treated as generative graph models using the following definition.
Definition 2.3. A random graph model (RGM) (x, d, μu) is defined a pair (W, f) of kernel W: X x - R and a measurable function f : X + R called a metric-space signal. We define random graph with corresponding node features (G, by sampling N i.i.d. random points X1,...,X from with probability density as the nodes of G. The weight matrix W (Wis))is of G is defined by wi. W (X,, for i, =1,..., N. The graph signal f is defined by f, = -(X.). We say that (G, is drawn from W, and denote (G, ~ (W,
2.3 Continuous Message Passing Neural Networks
Given MPNN, we define continuous message passing neural networks (cMPNNs) that act on kernels and metric-space signals f X + Rf ff by replacing the graph node features and the aggregation scheme in (2.2) by continuous counterparts. Let W be a kernel. We define the kernel degree of W x E X by
dw (x) = / W(x, vddp(y).
(4)
Consider a message signal U x X + " where ((x y) is interpreted message sent from the point to the point x in X. We define the continuous mean aggregation of U by
Mw(U)(2) /
W(x,)) v) U(. v)dp(y).
(x) )
5

---

Given the messages U(x,y) - ((f(z), f(U)), where @b R - *R", we have (w) = (Mw(((())))()))))
W(x, v) (())) dw(x)
By abuse of notation, we often denote in short $ f) = (f)))))((ffff))))))) (((),
By replacing mean aggregation by continuous mean aggregation in Definition 2.2, the same message and update functions that define a graph MPNN can also process metric-space signals.
Definition 2.4. Let W be kernel and @ be MPNN, as defined in Definition 2.1. For each t E (T)....TT, we define @W as the mapping that maps the input signal to the signal the t-th layer by
o :3: + L3) f 1(h)
(5)
where f()) are defined sequentially by
(x)) = Mw ( (x)
(6)
(x) v((1) (sit=1) (1))
and ( / Fo is the input metric-space signal. We call Ow == = continuous message passing neural network (cMPNN).
(2)
As with graphs, the output of cMPNN Ow metric-space signal f + F is another
metric-space signal (w()) X + Pr. The output of a cMPNN after global pooling is a single vector 6 W (J) E Fr, defined by 6 J (f)a)))du)
2.4 Data Distribution for Graph Classification Tasks
In the following, we consider a training data T (x' = (Gi,
of graphs G., graph signals f', and corresponding values y" that can represent the classes of the graph-signal pairs. The training data is assumed to be drawn i.i.d. from a distribution Ag (x. y) that we describe next.
f'), = y")
In this paper, we focus on classification tasks. More precisely we have classes = 1,....,, each represented by RGM (W', f²) on metric-measure space (x", d' (u²). In fact, suppose that each class corresponds to a set of metric spaces. For example, a graph representing a chair can be sampled from a template of either office chair, garden chair, bar stool, etc., and each of these is represented by a metric space. For simplicity of the exposition, we however treat every template metric space its class. This does affect our analysis.
The distribution 4g(x, y) is defined via the following procedure data sampling. For sampling one graph, first, choose class with probability 7, i... for (x. .y jag and j 1,... ... P(y j). Independently of the choice of the class, choose the number nodes ~ 1/ where v/ is a discrete distribution N N. After choosing class y {1, (1...., r} and the graph size N, random graph (G. f) ~ (W) with N nodes is drawn from the space x with probability density of the nodes (
The notation T ~ pl describes a dataset T consisting of m samples ,k',y"),... (x",, ym drawn i..d. from Mg.. We refer to Subsection C. in the appendix for detailed definition of the distribution .g..
3 Convergence and Generalization of MPNNs
In this section, we provide our main results on convergence (Subsection 3.1) and generalization (Subsection 3.2) of MPNNs. For E RRF, we define | = mmaxjmt....FF ||zyl Given a metric space ()), dy), we define the infinity norm of a vector valued function g ) + R$ by l|glloc = maxj=1..... ess sup (g(()))l The function is called Lipschitz continuous if there exists constant Lg IR such that for all y. 1/ eV,
ll al Lody(u.

---

If the domain y is Euclidean, we always endow it with the L -metric.
We measure the emor between the output of continuous MPNN and a gPNNN after pooling as follows. Given a graph signal f E N= and a metric-space signal f f - RR both the graph and the continuous MPNN map to the same output space, i.e, O (f), ( R Namely, the output dimension of @ is independent of the random graph model it is realized the graph. Hence, we define the error to be the supremum norm [ (f) We define the e-covering numbers of the metric space X, denoted by C(x, e, d), as the minimal number of balls of radius e required to cover
and also independent of
For every = ,,...,, r, we make the following assumptions, which hold for the remainder of the paper. We assume that there exist constants Cx2, > such that
e, S Cxp E
for every O. Denote Dx max, D and Cx max, Czs. Such constants exist for every metric space with finite Minkowski dimension (see Appendix A). We assume that diam(x') := supz.gexi [d(ar, y)} S 1. Further, we only consider kernels W such that there exists a constant dmiu >> 0 satisfying
dws (I) 2 dmnin
(8)
where the kernel degree dws is defined in (4). We moreover assume that (zx -) and (',
are Lipschitz continuous (with respect its second and first variable, respectively) with Lipschitz constant Lws for every z X. We also assume that the metric-space signal fa X + R is Lipschitz continuous. Since the diameter of x" is finite, this means that f E L (x). We consider the following class of MPNNs
Lip =
{0 (( (E))))))) 1I = 1,...,.., T1))
F ti and vp(t) Fi+H + R
satisfy Liges Lip I L and | (0, 0) | (0,0)) s B).
3.1 Convergence
In this subsection we show that the error between the cMPNN and the according gMPNN decays when the number of nodes increases.
Theorem 3.1. Let W. x² + IR be Lipschitz continuous kernel with Lipschitz constant Lw, where the metric space X satisfies (7) with respect the constants Cx: Dx > O, and W satisfies (8). Consider a graph (G, ~ (W, f) with N nodes X1...., XN drawn i.i.d. from x with probability density μ.. Then, for every Lipschitz continuous f f:x + R
log(N)
s c" ( + L,7 N1/(Dx+1i + O(N-1)
Ex Ex.....Nsppt
sup @ETiPL.B
where C' is defined in Subsection B.2 of the appendix.
Remark 3.2. The constant in Theorem 3. depends polynomially on the Lipschitz constants Lage and Logen of the messuge and update functions (!!)) and (((), the culled formal biases [1 (0, loo and (1 (0, O)]l on [|W]| on the Lipschitz constant Lw of W. vlog(Cx) Dxx, and on -n.. where the degree of the polynomial is T. A regularization of these constants can alleviate the exponential dependency of the bound on T.
The proof of Theorem 3.1 is given in Subsection B.2 of the appendix.
Discussion and Comparison other Convergence Results The work closest related our convergence results is by Keriven et al. [2020], where the authors show convergence of a fixed spectral GCNN to its continuous counterpart with comparable regularity assumptions as in Theorem 3.1. Our result holds for MPNNs, which are more general than spectral GCNNs. Moreover, our bound uniform the choice of the MPNN O This last property is essential for leveraging the convergence result to derive generalization bound. Indeed, using the bound from Keriven et al.
7

---

[2020], for each MPNN θ there is a different high probability event &g where the convergence error small. However, the trained MPNN θ θ depends on the dataset T and cannot be fixed in the analysis. Hence, we would need to intersect all events Ne & to guarantee small convergence error of the trained network ④, which would not result in an event of high probability.
3.2 Generalization
In this subsection, we state the main result of our paper, which provides a non-asymptotic bound on the generalization error of MPNNs, as defined in (3). We consider graph classification task with a training set T = (x' (G', (. )= and P classes. The graphs and graph features in T are y
drawn i.i.d. from a probability distribution Ag xx, y) as described in Subsection 2.4. We recall that the distribution that samples the size of the graph is denote by v.
Given MPNN with pooling, OP, and its output dimension Fr, consider a non-negative loss function L: Fr x (1...., [] + [0, oo). Additionally, we assume that L is Lipschitz continuous with Lipschitz constant Lg. Note that although the cross-entropy loss, popular choice for loss function in classification tasks, is not Lipschitz-contimuuus cross-entropy composed on softmax is.
Theorem 3.3. There exists a constant > O such that
2 28811118
(Ramp((P) Rexp((P))
sup BELipı,,
m
2T I.2.C (1+ + Lz+)
N N /12 +1) + +0 (exp(- (exp(-N)..3+=)
+ + log(N)
+
m
where C' is specified in Subsection C.2 of the appendix.
The proof of Theorem 3.3 is given in Subsection C.2 of the appendix.
Remark 3.4. The constant C in Theorem 3.3 represents the complexity of the class LipL,B and can be bounded similarly to the constant C' from Theorem 3.1, as described in Remark 3.2. We summarize its dependencies on the parameters of the MPNN and the RGM by vC S 2T क0 maxx==1....I' (Vlog(Cxz) (Dxi Lws [|W Il's and refer to Subxection C.3 of the ap- pendix for more details. Similarly to Remark 3.2 the exponential dependency the the constant C in Theorem 3.3 on the depth T and the polynomial dependency on the uniform Lipschitz bound L can be alleviated by regularizing the latter. We also note that the exponential dependency on the number of classes I' in Theorem 3.3 can be eliminated by assuming that the data is representative, i.e., if the number of training samples that fall into class j 1,..., is deterministically m,
The term 2" 2' in Theorem 3.3 does not depend on the model complexity and typically much m
smaller than the second term. Hence, it does not affect bias varianee tradeoff considerations, and can
be ignored in the situation where m > C'E [log(N)))))))) (N) = > 1. Theorem 3.3 allows to think not just about graphs as samples, but also about individual nodes as samples. However, nodes are correlated with their neighbors, and the higher the dimension Dx is, the larger the neighborhoods
are. This is why the dependency on the number of nodes is N क and 1 Still, this dependency of the bound on N explains one way in which we train on less graphs than model complexity and still generalize well. Another insight is that the generalization bound becomes smaller the smaller the Lipschitz constants of the message and update functions (see Remark 3.4). This indicates that regularization methods like weight decay promote generalization.
Comparison to other generalization bounds in graph classification We compare our generaliza- tion bound with other generalization bounds derived by bounding the VC-dimension [Scarselli et al., 2018], the Rademacher complexity [Garg et al., 2020], and using a PAC- PAC-Bayesian approach [Liao al., 2021]. We do not compare with Verma and Zhang [2019b] since they derive generalization bounds for single-layered MPNNs in node-classificatt Furthermore, their bound scales as O(A2Txx/m the largest eigenvalue of the graph Laplacian. Hence, the generalization bound can increase monoton- ically for increasing (see [Liao et al., 2021] for more details). We summarize the comparison in Table 1 and provide more details, specially on the comparability, in Subsection C.4 of the appendix.
tasks. Hence, the role of depth is unexplored. where
the number of SGD steps and Amax is
8

---

Table 1: Comparison of generalization bounds for GNNs. We consider the following formula for generic generalization bound: GF < m-1/2 A(d, ())CC + Fm where m is the samples size, T is the depth, L is the bound of the Lipschitz constants of the message and update functions, h is the maximum hidden dimension, d is the average node degree and N is the graphs size and E' is a term that does not depend on the model complexity.
N)
B(h)
C(L)
VC-Dimension [Scarselli al., 2018]
((log(N)N)
O(h²)
Rademacher
Vlog(d(T33)
0 ((g(To(()))
Complexity [Garg et al., 2020]
PAC-Bayesian [Liao et al., 2021]
1(d
0 V log(h))
O(L
Ours
O ((ENoollo(N)) (N)N (
0(1) 0
Our analysis derives a generalization bound on MPNNs that has essentially the same dependency on the sample size m (up to a logarithmic factor), but does not directly depend on the number of hidden units. We emphasize that our bound depends on negative moments of the expected node size N. In contrast, the VC-dimension based bound [Scarselli et al., 2018] scales as (N))) the Rademacher complexity based bound [Garg et al., 2020] scales as Odd Vlogo /log(d2T-3) and the PAC-Bayesin Bayesian approach based bound [Liao et al., 2021] scales as O(dT-1). where d denotes the maximum node degree.
Numerical Experiments
We give empirical evaluations of our generalization bound in comparison to the PAC-Bayesian based bound [Liao et al., ] and the Rademacher complexity based bound [Garg et al., 2020]. We note that the VC dimension bound by Scarselli al. [2018] is written in O notations and hence cannot be quantitatively evaluated. We experiment on a synthetic dataset of 100K random graphs of 50 nodes, sampled from three different RGMs: the Erdös-Rényi model (ERM) with edge probability 0.4, a smooth version of a stochastic block model (SBM), based on the kernel K(2, y) sin(2 sin(nn))n2))) exp(-1x - y/²). The corresponding signals are given in Appendix D.2.1. 1. Each RGM represents one class in three binary classification problems, comparing all pairs of RGMs. For the MPNN we consider GraphSAGE [Hamilton et al., 2017] with mean aggregation, and number of layers T = 1,2 or 3, implemented using Pytorch Geometric [Fey and Lenssen, 2019]. We consider maximal hidden dimension of 128. In Appendix D we give more details and also consider synthetic data sampled from additional RGMs.
0.25 on [0, 1]2- and a geometric graph with kernel K (xx,)) y)
Our generalization bound becomes smaller the smaller the Lipschitz constants of the message and update functions are. To control the Lipschitz constants, we consider two learning settings. First, train with weight decay regularization, which decreases the Lipschitz bounds, and second, we train with no regularization. For each setting (each choice of the number of layers and regularization) we train the MPNN, and read the resulting Lipschitz constants of the network. We then plug all constants into our generalization bound formula (see Theorem C.7 in the appendix for the full formula), and into the generalization bound formulas of the PAC-Bayes and Rademacher bounds (see Appendix C.4 for the formulas). The results are reported Figure 1. We observe that our generalization bounds are orders of magnitude smaller than the other works. In fact, theoretical generalization bounds typically teach us about the asymptotic behavior of generalization, and about the hyperparameters that affect generalization, but rarely give realistic numerical bounds (less than 1) that guarantee generalization. Nevertheless, in one of the scenarios (one layer MPNN) our theory gives the bounds 0.08837 and 0.15 (respectively in the two datascts of Figure 1), which guarantees generalization in practice.

---

Ours
Bound Value
PAC Bayes
logi: Bound Value
PAC Bayes
Rademacher
Rademacher
W/O w/o We
WD
Figure 1: Generalization bounds given by our theory, PAC-Bayes [Liao et al., 2021] and Rademacher complexity [Garg et al., 2020] on binary classification problem over Erdös-Rény: and SBM (left) and Erdös-Rényi and geometric graph (right). Training is done with weight decay (WD) and without weight decay (wo WD), and on three models with 1, and layers.
Conclusion
In this paper we proved that MPNNs with mean aggregation generalize from training to test data in classification tasks, if the graphs are sampled from RGMs that represent the different classes. This follows from the fact that the MPNN on sampled graphs converges to the MPNN on the RGM when the number of nodes goes to infinity. Our generalization bounds become smaller the larger the graphs, which gives one explanation to how MPNNs with high complexity can generalize well from relatively small dataset of large graphs. observe two main limitations our current model. First,
the dependency of the generalization bound the size of the graph N is O(N IDxx-T), which is typically slower than the observed decay in experiments (See Appendix D.1). One potential future direction is improve this dependency using more sophisticated models of the trained network and of the message and update functions. Secondly, our model of the data is somewhat limited. One future direction is to allow deformations of the RGMs, consider continuum of RGMs instead of finite set, and to consider sparse graphs.
Acknowledgments
S.M acknowledges partial support by the NSF-Simons Research Collaboration the Mathematical and Scientific Foundations of Deep Learning (MoDL) (NSF DMS 2031985) and DFG SPP 1798, KU 1446/27-2.
Y.L. acknowledges support by DFG-SPP-2298, KU 1446/32-1.
G.K. acknowledges support from the ONE Munich Strategy Forum (LMU Munich, TU Munich, and the Bavarian Ministery for Science and Art). the Konrad Zuse School of Excellence Reliable AI (DAAD), the Munich Center for Machine Learning (BMBF) as well as the German Research Foundation under Grants DFG-SPP-220 KU 1446/31-1 and KU 1446/32-1 1 and under Grant DFG- SFB/TR 109, Project C09 and the Federal Ministry of Education and Research under Grant MaGriDo.
References
Michael M. Bronstein, Joan Bruna, Yann LoCun, Arthur Szlam, and Pierre Vandergheynst. Geometric deep learning: Going beyond euclidean data. IEEE Signal Processing Magazine, 34(4):18-44 42, Jul 2017. ISSN 1558-0792. doi: 10. 10..100/mp.2211.262225
Juan Cervino, Luana Ruiz, and Alejandro Ribeiro. Learning by transference: Training graph neural networks on growing graphs, 2021. URL https://arxiv org/ abs/2106 03693.
Hanjun Dai, Bo Dai, and Le Song. Discriminative embeddings of latent variable models for structured data. In Proceedings of the 33rd International Conference International Conference on Machine Learning Volume 48, ICML'16 16, page 2702-2711 JMLR.org. 2016.
Wenqi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin. Graph neural net- works for social recommendation. In The World Wide Web Conference, WWW 19, page 417-426.
10

---

New York, NY, USA, 2019. Association for Computing Machinery. ISBN 9781450366748, doi: 10.114553308555833B..4. URL https://doi. org.i..rg/.... 1t.../0...1///308555555.31 11w.1133333358.... 3313488.
Matthias Fey and Jan Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
Fernando Gama, Joan Bruna, and Alejandro Ribeiro. Stability properties of graph neural networks. IEEE Transactions on Signal Processing, 68:5680-5695, 2020. ISSN 1941-0476. doi: 10.1109/ts 0,2020.3026980 URL http: dx doi otg/10. 110.//..111SPPPPP 2020 2... 3026980.
Vikas Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. In Hal Daumé III and Aarti Singh, editors, Proceedings the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 3419-3430. PMLR, 13-18 Jul 2020. URL https: httts:t/: http://///ccceeeeeeeeeee/eo/ mlr, pres s/v119/garg200 wtrg//r.gthaaa//
William L Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Proceedings of the 3 1st International Conference on Neural Information Processing Systems, pages 1025-1035, 2017.
Henry Kenlay, Dorina Thanou, and Xiaowen Dong. Interpretable stability bounds for spectral graph filters. In Proceedings of the 38th International Conference Machine Learning. PMLR, 2021. URL pttt:://proceediine
mlr press/vlll http///v1///eeeeaaa /knlay22 httmllllaa.mm...
Nicolas Keriven, Alberto Bietti, and Samuel Vaiter. Convergence and stability of graph convolutional networks on large random graphs. star, 1050:23, 2020.
Thomas N Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint arXiv:1611.07300 2016.
Ron Levie, Elvin Isufi, and Gitta Kutyniok. On the transferability of spectral graph filters. In 13th International conference on Sampling Theory and Applications (SampTA). IEEE, 2019. doi: 10. 109/SampTA4568 203999033932.
Ron Levie, Wei Huang, Lorenzo Bucci, Michael Bronstein, and Gitta Kutyniok. Transferability of spectral graph convolutional neural networks. Journal of Machine Learning Research, 22(272): 1-59, 2021.
Renjie Liao, Raquel Urtasun, and Richard Zemel. A PAC-bayesian approach to generalization bounds for graph neural networks. In International Conference on Learning Representations, 2021. URL
http:/forrmmddd-----.o 626xx2....
L. Lovász. Operations with structures. Acta Mathematica Academiae Scientiarum Hungarica. 18(3): 321-328, 1967. doi: 10.1007/BF02280091. URL
10. 10tp://000.000/8F22200911
László Lovász. Large networks and graph limits. Colloquium Publications, Budapest, 2012.
Sohir Maskey, Ron Levie, and Gitta Kutyniok. Transferability of graph neural networks: an extended graphon approach. arXiv preprint ar 100-1009,, 2021.
Federico Monti, Fabrizio Frasca, Davide Eynard. Damon Mannion, and Michael M Bronstein. Fake news detection on social media using geometric deep learning. arXiv preprint arXiv:1902.0660 2019.
Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe Weisfeiler and leman go neural: Higher-order graph neural networks. Proceedings of the AAAI Conference Artificial Intelligence, 33(01):4602 4609, Jul. 2019. doi: 10. wt3.9//a....3301.33333333 vie#/4384.
URL attps://ojas aaai weng/index... www.:.hpppppaa. hmp/AAAI/article////
Mathew Penrose. Random Geometric Graphs. Oxford Scholarship Online, 2003. ISBN 9780198506263.
Luana Ruiz, Luiz F. O. Chamon, and Alejandro Ribeiro. Transferability properties of graph neural networks, 20 URL https: //tp///axvvv/.//////i//////aaaaa org/abs abs/2112 04629.

---

Luana Ruiz, Fernando Gama, and Alejandro Ribeiro. Graph neural networks: Architectures, stability, and transferability. Proceedings of the IEEE, 109(5):660-66)) 682, 2021b. doi: 10.1 10.1109//PRCC .3055400.
Franco Scarselli, Ah Chung Tsoi, and Markus Hagenbuchner. The vapmik-chervonenkk dimension of graph and recursive neural networks. Neural Networks, 108:248 259, 2018.
Jonathan M. Stokes, Kevin Yang, Kyle Swanson, Wengong Jin, Andres Cubillos-Ruiz Nina M. Donghia, Craig R. MacNair, Shawn French, Lindsey A. Carfrae, Zohar Bloom-Ackermann, Victoria M. Tran, Anush Chiappino-Pepe, Ahmed H. Badran, Ian W. Andrews, Emma J. Chory, George M. Church, Eric D. Brown, Tommi S. Jaakkola, Regina Barzilay, and James J. Collins. A deep learning approach to antibiotic discovery. Cell, 180(4))688-702.113 2020. ISSN 0092-8674. doi: http///oo.rrr/1.1111........./// ience/ article/ wwtticeeppi///oseeeeeeeeee /11/50092867220000022
.021. URL ttttps://wett wwwp://wwwwiiiiiee.c.ccc.......e wwwpeeettcoc...eeeeeeeeeeeeeeeee
Aad W. Vaart and Jon A. Wellner. Weak Convergence and Empirical Processes. Springer New York, NY, 1996.
Saurabh Verma and Zhi-Li Zhang. Stability and generalization of graph convolutional neural networks. In Proceedings of the 25th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pages 1548, 2019a.
Saurabh Verma and Zhi-Li Zhang. Stability and generalization of graph convolutional neural networks, 2019b.
Roman Vershynin. High- DiggenDimesion Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics, Cambridge University Press, 2018. doi: 10.1017/978 108231596.
Jizhe Wang, Pipei Huang, Huan Zhao, Zhibo Zhang, Binqiang Zhao, and Dik Lun Lee. Billion- scale commodity embedding for e-commerce recommendation in alibaba. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, KDD '18, page 839-848, New York, NY, USA, 2018a. Association for Computing Machinery. ISBN 978 1503555555 doi: 10.1145/221981993229988 URL huttp:://dot org/10/ httg//..1155.00 1144//211/219.. 3219869.
Nanyang Wang, Yinda Zhang, Zhuwen Li, Yanwei Fu, Wei Liu, and Yu-Gang Jiang. Pixel2mesh: Generating 3d mesh models from single rgb images. In Proceedings of the European Conference Computer Vision (ECCV), pages 52-67, 2018b.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019. URL https: //openreview...mmm/
1dryGGe615Kk.. ottp://rr....eeeoooooooororrraa.
Gilad Yehudai, Ethan Fetaya, Eli Meirom, Gal Chechik, and Haggai Maron. From local structures to size generalization in graph neural networks. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 1 11975- 11986. PMLR, 18-24 Jul 2021. URL httppa:/ppooceeeeee html.
mlr, wwwppprsssiiiee vatass//v3//yeeuaaaia /ehddai2la.
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 the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD '18, page 974-983, New York, NY, USA, 2018. Association for Computing Machinery. ISBN 978 150355552. doi: 10. 10.1145/32198119.22228 321 9890.
URL hnttps:/ddot org/10 10. 1145/3219119.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See the conclusion in Subsection
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This is theoretical work with foreseeable societal consequences
(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 of assumptions all theoretical results? [Yes] Yes
(b) Did you include complete proofs of all theoretical results? [Yes] The appendix includes complete proofs.
3. If you ran 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 URL)? [N/A] The experiments are very simple which is why we decided to not include the code.
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [N/A] We did not perform training
(c) Did you report error bars (e.g., with respect to the random seed after running ex- periments multiple times)? [Yes] We report the standard error with respect to the randomness of our experiments.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A] We did perform training, i.e., the experiments were toy examples and not computation heavy.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] We refer to [Fey and Lenssen, 2019] for using Pytorch Geometric. We do not use any existing code, data or model.
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A] We not use real data. Only toy experiments on synthetic data.
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A] We do not use real data. Only toy experiments on synthetic data.
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] We did not crowdsource or conduct research with human subjects. (b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "p9hGjQHMY2S", "reviewer": "Reviewer_6gwZ", "summary": "This paper talks about the generalization error of message passing neural networks. \n\nBy assuming graphs are sampled from random graph models (RGM), the authors define continuous MPNN (cMPNN), and prove in Theorem 3.1 that the error between cMPNN and the corresponding graph MPNN decreases as the number of nodes in the graph increases, which is the main contrinution of this paper. With such results, the paper further proves a generalization bound in Theorem 3.3. \n\nNumerical results confirm the correctness of the theoretical analysis. ", "questions": "* Citation format is not consistent with NeurIPS 2022, need to follow the template provided. \n\n* This paper builds its theoretical results with several assumptions. It would be great to see some discussions about which assumptions are reasonable, and which assumptions might be too strong to deviate from reality. ", "limitations": "As mentioned by the authors, this is a theoretical work with no clear negative social impact.\n\nThe two limitations in this work are concluded in section 5 of the paper. ", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n* The theoretical analysis in this paper is quite solid, which first builds the relationship between graph MPNN and continuous MPNN, then states the convergence and generalization results. Even though this paper is very theoretical and not easy to read, the definitions and preliminary knowledges in this paper are written clearly, which provides backgrounds to readers not very familiar with the theory involved in this paper. \n\n* The convergence bound, which decreases as number of nodes increases, seems novel compared with previous bounds. \n\n\nWeakness:\n\n* One of the main contributions of the paper is that the generalization bounds becomes smaller as the number of nodes in the graphs becomes larger. This is indeed an improvement over previous bounds. However, as a practitioner, it is not clear to me what insights such theoretical work could bring to reality. For example, how could we utilize the theories in this paper to guide the design of MPNNs with lower generalization error? \n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "czjRsq4wufM", "reviewer": "Reviewer_tNHF", "summary": "A novel generalization bound for a class of message passing neural networks (MPNNs) on graphs is derived. The generalization gap decreases with the average number of nodes of graphs sampled from the data distribution. This is in contrast to other generalization gaps in the literature, which typically increase in the number of nodes or degree. This result relies in part on a convergence result that the authors prove, which bounds the expected difference of an MPNN output on sampled graphs and the output of a newly-defined continuous MPNN on the underlying random graph model.\n", "questions": "1. In Appendix D, it is mentioned that you approximate the continuous MPNN with an MPNN on a large graph (lets call this output $Y \\in \\mathbf{R}^F$), which is then subsampled to smaller graphs, for which the ''finite'' MPNN outputs (call these $Z_1, \\ldots, Z_{50} \\in \\mathbf{R}^F$) are compared. This may make it easier for the ''finite'' MPNNs to be close to $Y$. Perhaps it would be better to sample several large graphs, giving outputs $Y_1, \\ldots, Y_{a} \\in \\mathbf{R}^F$, and then measure how close ''finite'' MPNNs are to $\\frac{1}{a} \\sum_{i=1}^a Y_i$ on independently sampled small graphs.\n\n2. Perhaps mention in Section 1 that your analysis holds for mean aggregation (apologies if I have missed the mention).\n", "limitations": "Yes, limitations are mentioned in the conclusion.\n", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The derived generalization error contains a term that decreases in the size of the  graph, in contrast to previous results in which error increases in the size of the graph. This is novel, and may have important implications.\n2. The paper defines a continuous analogue of message passing neural networks with mean aggregation, an important class of GNNs. Previous work has done this for spectral GNNs that use polynomial filters of the normalized graph Laplacian. Unlike previous work, this work develops convergence bounds that are uniform in the choice of model, which is important for deriving useful generalization bounds.\n3. The assumptions and data distribution mostly seem reasonable to me.\n\nWeaknesses:\n1. Minor:  numerical experiments are a bit lacking, and it may be interesting to consider things like Lipschitz continuous graphons of varying constants, or other GNNs. See also the questions section.\n\nNote: I did not have time to check the proofs of this paper, which are very long and full of calculations.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "TfcXzoDUE1a", "reviewer": "Reviewer_zvEs", "summary": "In this work, a new generalisation bound for MPNNs is proposed. Specifically, studying MPNNs over graphs and their continuous-space counterparts, it is showed that the uniform generalisation error can be upper-bounded by a formula that improves, not only by increasing the number of training graphs, but also by increasing the number of nodes in these graphs. This forms the foundation of a useful 'peace-of-mind' result: a MPNN-based graph classifier should generalise well even over small numbers of training graphs, provided those graphs are sufficiently large. The bound is verified empirically by training MPNNs on a random geometric graph model.", "questions": "Q1. Could you concisely clarify the practical implications of your work? Could you make this discussion clear in your paper from an early stage?\n\nQ2. Could you provide additional experimental evidence for your bounds? Either on a wider variety of generative distributions, or (ideally) on several 'points' corresponding to sizes / distributions of existing graph classification datasets in the literature.", "limitations": "No concerns.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Originality**:\nThe derived bounds appear novel, and compared to prior art (Table 1), they feature for the first time a term that decays as the graph size increases. This is enabled through an original Monte Carlo lens of analysis, which allows to treat individual nodes as samples, even though the task is specified on the graph level. Specially, a novel mathematical apparatus is developed to handle the correlations between the nodes' neighbourhoods (since the nodes cannot be assumed to be provided i.i.d.).\n\n**Quality**:\nI find the mathematical results in this work to be solid. However, I believe the experimental evaluation could benefit from some aspects of real-world analysis -- see the significance section for more details.\n\n**Clarity**:\nThe paper is, for the most part, well-written and somewhat easy to follow. However, I find that the paper could really benefit with making its aims (and practical implications) clear significantly earlier. As it stands, it takes until halfway of page 2 before it is even slightly clear what the implications of this work would be for the GNN practitioner, and even then the link feels a bit loose and 'left to the reader'. It would be highly beneficial to provide a clearer discussion on what the work's main contributions and its implications are, way earlier in the paper.\n\n**Significance**:\nWhile the obtained bounds are clearly of significance compared to earlier work in the area, I find the experimental evaluation to be fairly limited in comparison---focusing only on one specific generative model of graphs. It will strengthen the results of the paper significantly if we could connect them to 'real-world' distributions of graphs.\n\nFor example, one might perform a similar experiment to Section 4, over the various graph classification datasets in the TU Dataset benchmark (https://chrsmrrs.github.io/datasets/). For any one of those datasets, we can observe the (average) number of nodes, and compare the observed generalisation error w.r.t. an (empirically built) RGM over the graphs in the dataset. This would correspond to a particular 'point on the curve' of Figure 2, specialised on a particular dataset's generative distribution.\n\n**Overall**:\nAll things taken into account, I think this has potential to be a strong paper, and a few more improvements would be needed before it would pass the bar of acceptance. Theoretically, it appears very solid (though I will remark I did not check the proofs in the Appendix at great length), but practically it is somewhat lacking in evaluation and motivation.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept