In-distribution and Out-of-distribution Generalization for Graph Neural Networks
Authors: Emmanuel Sales
Renjie Liao
Nick Harvey
Venue: Submitted to ICLR 2023 (2023)
Keywords: Graph Neural Networks
Generalization Bounds
Out-of-distribution generalization
Learning theory

Abstract: Graph neural networks (GNNs) are models that allow learning with structured data of varying size. Despite their popularity, theoretical understanding of the generalization of GNNs is an under-explored topic. In this work, we expand the theoretical understanding of both in-distribution and out-of-distribution generalization of GNNs. Firstly, we improve upon the state-of-the-art PAC-Bayes (in-distribution) generalization bound primarily by reducing an exponential dependency on the node degree to a linear dependency. Secondly, utilizing tools from spectral graph theory, we prove some rigorous guarantees about the out-of-distribution (OOD) size generalization of GNNs, where graphs in the training set have different numbers of nodes and edges from those in the test set. To empirically verify our theoretical findings, we conduct experiments on both synthetic and real-world graph datasets. Our computed generalization gaps for the in-distribution case significantly improve the state-of-the-art PAC-Bayes results. For the OOD case, experiments on community classification tasks in large social networks show that GNNs achieve strong size generalization performance in cases guaranteed by our theory.

Under review conference paper at ICLR 2023
IN-DISTRIBUTION AND OUT-OF-DISTRIBUTION GENERALIZATION FOR GRAPH NEURAL NETWORKS
Anonymous authors
Paper under double-blind review
ABSTRACT
Graph neural networks (GNNs) are models that allow learning with structured data of varying size. Despite their popularity, theoretical understanding of the generalization of GNNs is an under-explored topic. In this work, we expand the theoretical understanding of both in-distribution and upon the state-of-the-art PAC-Bayes (in-distribution) generalization bound primarily by reducing exponential dependency the node degree a linear dependency. Secondly, utilizing tools from spectral graph theory, we prove some rigorous guarantees about the out-of-distribution (OOD) size generalization of GNNs, where graphs in the training set have different numbers of nodes and edges from those in the test set. To empirically verify our theoretical findings, we conduct experiments on both synthetic and real-world graph datasets. Our computed generalization gaps for the in-distribution case significantly improve the state-of-ther -frtt--rrr PAC-Bayes results. For the OOD case, experiments on com- munity classification tasks in large social networks show that GNNs achieve strong size generalization performance in cases guaranteed by our theory.
generalization of GNNs. Firstly, improve
INTRODUCTION
Graph neural networks (GNNs), firstly proposed in Scarselli et al. (2008), generalize artificial neural net- works from processing fixed-size data to processing arbitrary graph-structured or relational data, which can vary in terms of the number of nodes, the number of edges, and on. GNNs and their modern variants (Bronstein et af.) 2017 [Battaglia et al. 2018) have achieved sfate-of-the-aat results in a wide range of ap- plication domains, including social networks (Hamilton et al. (017), material sciences (Xie & Grossman, 2018), drug discovery (Wieder et al. 2020). autonomous driving (Liang et al. 2020), quantum chemistry Gilmer al. 2020p. and particle physics (Shlomi et al. 2020).
Despite their empirical successes, the theoretical understanding of GNNs are somewhat limited. Existing works largely focus on analyzing the expressiveness of GNNs. In particular, [uu al.) (2018) show that GNNs are as powerful as the Weisfeiler-Lehman (WL) graph isomorphism test (Weisfeiler & Leman 1968) in distinguishing graphs. Chen al, (2019) further demonstrate an equivalence between graph isomorphism testing and universal approximation of sermutation-invarian functions. Loukas] (2019) show that GNNs with certain conditions (e.g., on depth and width) are Turing universal. Chen et al. (2020) and Xu et al. (2020a) respectively examine whether GNNs can count substructures and perform algorithmic reasoning.
the vein of statistical learning theory, generalization analyses for GNNs have been developed to bound the gap between training and testing errors using VC-dimension (Vapnik & Chervonenkis) 1971). Rademacher complexity (Bartlett & Mendelson 2002). algorithmic stability (Bousquet & Elissceff 2002). and PAC- Bayes (McAllester] (2033) (a Bayesian extension of PAC learning (Valiant) 1984)). Depending whether the problem setup is in-distribution (ID) or
(OOD), i.e., whether test data comes from the same distribution training data, categorize the literature into groups

---

Under review conference paper at ICLR 2023
ID Generalization Bounds. Scarselli et al. (011 provide a VC-dimension based generalization bound for GNNs whereas Verma& & Zhang] (2019) present the stability-bassed generalization analysis for single- layer graph convolutional networks (GCNs) (Kipf & Welling, 2016). Both consider node classification and (IID), which conflicts with the common relational learning setup (e.g., semi-supervised node classification) at which GNNs excel. Relying on the neural tangent kernel (NTK) approach (Jacot et al. 2018). Du et al. (2019) characterize the generalization bound of infinite-width GNNs on graph classification, Garg et al. (2020) derive the Rademacher complexity based bound for message passsing GNNs graph classification. Lv (202I) establish results for GCNs on node classification using Rademacher complexity as well. Based on PAC-Bayes, Liao et al. (2020) obtain a tighter bound for both GCNs and message passsing GNNs on graph classification compared to (Garg et al. 2020; Scarselli et al.] 2018). Subsequently, [a et al.] (202I) also leverage PAC-Bayes and show generalization guarantees of GNNs on subgroups of nodes for node classification. More recently, [i et al.
assume the node features are independent and identically-distnne
(0022 study the effect of graph subsampling in the generalization of GCNs.
OOD Generalization Yehudai al.] (2021) study size generalization for GNNs - this is a specific OOD
setting where training and testing graphs differ in the number of nodes and edges. They show negative results that specific GNNs can perfectly fit training graphs but fails on OOD testing ones. [Baranwal et al. (202T) )
consider specific graph generative models, ie., the contextual stochastic block model (CSBM) (Deshpande)
jet al.] 2018), where CSBMs during training and testing are of the same means but different number of nodes, intra-, and inter-class edge probabilities. They present generalization guarantees for single-layer GCNs on binary node classification tasks. Later, Maskey et al. (2022) assume yet another class of graph generative models, i.e., graphons, where the kernel is shared across training and testing but the number of nodes and edges could vary. They obtain generalization bounds of message passing GNNs on graph classification and regression that depend the Minkowski dimension of the node feature space. Relying on a connection of over- weer-parameterized networks and neural tangent kernel. Xu et al. (2020b) find that task- specific architecture/feature designs help GNNs extrapolate to OOD algorithmic tasks.
Wu et al. (2022a) propose cxplore-to-exttee to-extrapolate risk minimization framework, for which the solution is proven to provide optimal OOD model under the invariance and heterogeneity assumptions. Yang al.
(2022) propose a two-stage model that both infers the latent environment and makes predictions to generalize OOD data. Empirical studies suggest works well on real-world molecule datasets. [Wu et al. (2022b) study a new objective that can learn invariant and causal graph features that generalize well to OOD data empirically. All above works follow the spirit of invariant risk minimization (Arjovsky et al. 2019) and focus on designing new learning objectives. Instead, we provide generalization bound analysis from the traditional statistical learning theory perspective.
Our Contributions. In this paper, study both in-distribution and out-of-distribution generalization for GNNs. For in-distribution graph classification tasks, we significantly improve the previous state-of-the-art PAC-Bayes results in (Liao et al., (020) by decreasing an exponential dependency on the maximum node degree to a linear dependency. For OOD node classification tasks, we do not assume any known graph generative models which is in sharp contrast to the existing work. We instead assume GNNs are trained and tested on subgraphs that are sampled via random walks from a single large underlying graph, as an efficient means to generate a connected subgraph. We identify interesting cases where graph classification task is theoretically guaranteed to perform well at size generalization, and derive generalization bounds. We validate our theoretical results by conducting experiments on synthetic graphs, and also explore size generalization on a collection of real-world social network datasets. In the in-distribution case, we observe an improvement of several orders of magnitude in numerical calculations of the generalization bound. In the out-of-distributin case, we validate that, in cases where the theory guarantees that size generalization works well, the prediction accuracy on large subgraphs is always comparable to the accuracy on small subgraphs, and in many cases is actually better.
2

---

Under review conference paper at ICLR 2023
(a) An example of a small expander graph. Any (b) Example of a small barbell graph. If labelling is exactly labelling of its nodes cannot exhibit homophily.
differentiated between the two groups, then exhibits homophily.
2 BACKGROUND INFORMATION
A graph G is an abstract mathematical model for pairwise relationships, with set of vertices V and a set of edges E C V x V. Two vertices U1, U2 are said be connected (vi, v2) E. For a given graph G we also denote its vertices by V(G) and edges E(G). Unless otherwise specified, are undirected and without multi-edges. In machine learning, a graph (or graph-structured data) typically come with set of node features. Common graph based machine learning tasks include node classification (or regression) and graph classification (or regression). We use the following notation.
assume graphs
Graph data {G, = (V,, ==
where the set of all graphs. The neighborhood vertex is denoted (1) = {u E V(G.) (v,u) u) E EGG))
Node feature H, V + X, with X' being the feature space, e.g., X' Rd
Node labels y - V. with y being the set of labels, e.g., [n].
Graph neural networks (GNNs). GNNs generalize regular neural networks to process data with varying structures and dependencies. GNNs achieve this flexibility via message passing computational process. In particular, at the k-th step (or layer) of message passing, we update the representation h (I++) of node u as follows,
(1) This update happens for all nodes in parallel within each message passing step. Moreover, the UPDATE and AGGREGATE operators shared by all nodes, which enables the same GNN process varying- sized graphs. Once we have finished the finite-step message passing process, we can use the output node representations to make predictions nodes, edges, and the graph via additionally parameterized readout functions, This message passing framework is quite general since one can instantiate the UPDATE and AGGREGATE operators by different neural networks. For example, the widely used Graph Convolational Networks (GCNs) (Kipf & Welling 2016), which are the main interest of our work, have the form
h (k+1) = UPDATE(h (8) AGGREGATE(
e (N)))))).
h (x+1)
We Σ
he
2
"EN(W)U(U)
where one applies a linear transformation (W₂) all node representations, weighted-sum over the neigh- borhood, and element-wise nonlinearity (e.g., ReLU activation). Note that the learnable weights W; are different from layer to layer.
Homophily. A concept studied in network science, homophily McPherson al. 2001 is the property that similar nodes group together. For node classification (or node labelling), this means that neighbouring nodes tend to have the same label. Size generalization plausible when the labelling of the nodes exhibits homophily. The presence of a homophilic graph labelling implies that the labels of the nodes are unlikely to change during the course of long random walk the graph.
3

---

Under review conference paper at ICLR 2023
It important to note that homophily is also a concept that relates to the graph topology, as not every possible graph structure can be given a labelling that exhibits homophilic properties. An example of one such topology where homophily impossible is an expander graph (Hoory et al. (006), as shown in Figure la where nodes have either random or random-like edges connected to constant number of other nodes the entire graph. In this case, any labelling of the nodes is far from homophilic, as can be shown using the expansion property. A setting with more homophily is akin to a barbell graph, as shown in Figure [by where there are two densely connected components, and comparatively few edges connecting the two dense regions. If the graph labelling of interest lines up with these divisions inherent in the topology, then it is natural to say that it exhibits a homophilic property.
Cheeger's Inequality. A mathematical description of homophily can be given using concepts from spectral graph theory. Cheeger's 's inequality (Hoory et al.) (2006) is a theorem that pertains to partitions graphs, or equivalently binary-valued labellings on graphs (one side of the partition labelled the other 1). A crucial definition is the conductance, defined by
E(S, S) S
e(S)
ASSA
and
o(G)
min oSS).
s
Here S) is the set of edges connecting a node in S to a node outside of S. Cheeger's inequality states
22/2 S (GG) S V2X2.
where X2 is the second-smallest eigenvalue of the normalized Laplaciar| İ. This inequality links the real- valued quantity Å to the concept of homophily. Aa is small then the conductance of must also be low, by Cheeger's inequality. If a labelling on graph nodes ʃ VG)) + {0, roughly agrees with cow-conductance partition (i.e., one side of the partition is generally labelled and the complement generally labelled 1) then the labelling f exhibits homophily.
3 IMPROVEMENT OF IN-DISTRIBUTION PAC-BAYER BOUND
The state-of-the-art generalization bounds for GNNs in the in-distribution case were formulated by Liao et al. (2020) using the PAC-Bayes theory. Specifically, they build upon the PAC-Bayes theorem in Neyshabur et al. 2018) that pertains to homogeneous feedforward neural networks.
(X, A. y) where X E X, A E G. and ) are the node features, the adja- cency matrix, and the graph label respectively. Each sample is drawn from some unknown data distribution 'D (with support X' x 9 x ))) in an i.i.d. fashion. Since both training and testing samples are drawn from the same distribution, this is the in-distribution setup. Following (Liao et al. 2020). we consider a margin loss for multi-class graph classifications as below,
We denote sample
Lo, (w) PIND (x,(X, S max fwr (x, A)b1
JFy
where y > 0 is the margin parameter and fw is the model (hypothesis) parameterized by weights w. Since D is unknown, is defined on the sampled training set S as below,
not compute this true loss (risk). We instead minimize the empirical loss (risk) that
- Σ
(Fu(X,,A)l) S max for (X,,
Ls.- = (fw)
(4)
jfy
ZES
Here f. - D-1 A)D-1/2 where D is the diagonal matrix of vertex degrees and is the adjacency matrix.
4

---

Under review conference paper at ICLR 2023
where m is the number of training samples, For simplicity, we abbreviate LD.r(fu) and Ls (fw) as LD.t and Ls,, respectively from now on.
Our main in mn-ditrrbbution result bounds the gap between true and empirical risks for GCNs, shown in the following theorem. The proof is in Appendix A.1
Theorem 3.1. For any B 0, 1> 1, let fn E H x G - IR* be an l-layer GCN. Then with probability
- 8 over the choice of an iid size-m training set S from the data distribution D, we have for any
B d
12
(h + lm))
IT
W1 E'= (II W1 + In m 5
LD.0 S Ls. +0
(5)
7
Here d equals to one plus the maximum node degree that can be achieved by the data distribution. is the depth, i.e., the number of layers, of GCNs. W; is the weight matrix of GCNs in the i-th layer. B is the radius of the minimal &y ball that contains all node features, i.e., Vu, ||æ, S B. This improves the bound in Liao jt al. 2020), which is provided below for a better comparison,
B d'
12
(1))
II 1 (I/ [ + log 5
LD.0 S Ls.y +0
(6)
2
The proof of the theorem from (Liao et al. 2020) is an induction over the / layers, in which the spectral norm of the weights and a maximum degree term is multiplied at each step. We observe that it is possible avoid passing the maximum degree term via refined argument. This leads to tightening of one of the main inequalities used in the induction proof, thus in turn resulting in substantial improvements to the overall bound. As can be seen above, we reduce the exponential term d'-1 linear term d, which is a significant improvement for graphs even with small node degrees.
4 TOWARDS DEVELOPING A THEORY FOR SIZE GENERALIZATON
this section, we develop an ofitt--diitributiin (OOD) generalization theory for GNNs. Since we adopt a statistical learning viewpoint, there must necessarily be some assumptions relating the training and testing graphs (otherwise the No-Free Lunch theorem applies). There is a tradeoff between assumptions that are practically relevant, and those for which rigorous guarantees are provable. We have chosen assumptions that we believe strike a balance between those objectives, at least for applications like social networks.
Size Generalization Assumptions. We consider the following setup. First, assume that there exists an extremely large graph G like the user network in Twitter so that one needs to sample subgraphs (e.g.. via random walks) for training and testing machine learning models. This is akin to the practical setups of (Grover & Leskovec 2016 Hamilton et al. (017).. To generate training and testing subgraphs, we run random walks of length N and M respectively on this single large graph, where M >> N, and collect the subgraphs induced by these walks. GNNs are then trained on the subgraphs induced by the shorter (length-NV walks. In testing, we assume procedure where length-M M random walk induced subgraph is sampled from the large subgraph. Random walks are initiated by choosing an initial node uniformly at random from the nodes in the graph, and at each step there an equal probability selecting any of the current node's 's neighbors. This is an interesting OOD problem where training and testing graphs come from different distributions determined by the underlying large graph and the random walk sampling with specific length. We consider the graph classification problem and assume that the graph label is determined by the majority of node labels within the graph, which is reasonable for many applications that involve homophilic graphs. For the node labeling, assume it is binary but have assumptions how labels generated.
5

---

Under review conference paper at ICLR 2023
Crucially, we assume nothing about the underlying large graph. Therefore, our setup has advantages over some OOD setups in the literature where generative model of graphs and labels is explicitly assumed.
Relation with In-Distribution Result. We know the relationship between true error defined on the unknown data distribution D and empirical enror defined on the size-m training set S. Specifically, for any GCN f, with probability at least 6, we have a general bound as follows,
LD,0 S LS, + A(f, 6, m).
(7)
where we abbreviate the bound as A(f 6, m) and omit specific parameters like maximum node degree d. In the size generalization problem, we use random walks with lengths N and M for collecting training and testing subgraphs (data) respectively. We are interested in proving a statement of the following form: for any GCN f, we have with probability at least 1 1-8,
(8) The key detail is that DM is the distribution of subgraphs induced by random walks with length M and SN is the training set of subgraphs induced by random walks with length N. Comparing these two losses is the essence of our OOD result. The final term [ff. 8, m, M, N) is general bound involving these parameters.
LD 0 S LSN + B(f,8, m, N)
Based on the in-distribution result like in Theorem 3.1 we can similarly obtain,
L S LSx + Ox(
(9)
where DN is the distribution of subgraphs induced by random walks with length N and Ay is the general bound. The key question boils down to: what is the relationship between LD u to I.D,, This question will be answered in the following sections.
4.1 A PROBABILITY BOUND FOR PARTITION CROSSES
The above size generalization problem involves the distributions of random-walk-indun subgraphs from a large graph G with two lengths: N for training and M for testing. Also, M is much larger than N. Before we state our results, we would like to explain the simple intuition that motivates our theory:
If the random walk always stays within the same partition, then the graph label of the random-walk-nndnced subgraph can be well predicted, no matter how long the random walk is.
Here a partition means the subset of nodes with the same node label. The goal of this section is to find bounds on M for which we can provide OOD guarantees. We begin by considering a special labelling.
Special Node Labeling: Sparsest Cut. A set S that minimizes ((S) (and has |S| S |V1/2) is called a sparsest cut. For simplicity assume that S is unique. Using Cheeger's inequality, we first prove the following probability bounds related to this sampling procedure, thereby identifying the length M for which a random walk is likely to stay within the sparsest cut for d-regular graphs. The theorems are as follows.
Theorem 4.1. Let UM = [u1, U2, . uns] be length-M M random walk over connected, d-regular graph G. with un chosen from the stationary distribution of the nodes of G. If M S d//25//2//) VX2), then the probability that UM crosses the spursest-cut partition at least once is under 1/2.
Here crossing the sparsest-cut partition S means that there exists an edge (u, v) of the random walk satisfies u E S and v E S. d2 is the second-smalles eigenvalue of the normalized Laplacian. We can easily generalize the previous theorem to an arbitrary probability 8 > as below.
Corollary 4.1.1. If M & (5d)/23/ Vaz, the probability of the above random walk UM crossing over the sparsest-cut partition at least once is at most 6.
6

---

Under review conference paper at ICLR 2023
General Node Labeling. Theorem 4.1 is restrictive in that it requires the partition S to be the sparsest cut. We now modify the proof to yield quantity that can work for any node labelling f. Specifically, let yp be any boolean (i.e., (0, 1 )-valued) labelling on the vertices of the graph. Let the positive node labelling of yo be S = {u E V(G): (p()) 1}. We are interested in bounding the probability that a random walk of length M includes an edge that crosses the positive node labelling S, i.e., an edge (u, v) satisfies u E S and v E S. Theorem 4.2. Let be a boolean labelling on the nodes of a connected, d-regular graph G with positive node labelling S (0-1 valued vector with ppt]] 1 vf E S). Let UM [u1, U2...... u.rl] be a length-M M random walk over G. with u1 chosen from the stationary distribution of the nodes of G. Let X; be the indicator variable of the event that the i-th edge of UM crosses S. i.e. X; 1 [u, E S. u441 E S] and
Yv= Dim1 X; is the number of times that UM crosses S in the first ks steps. Let o' xp 1((S//V)) and 4 L'p' /1//2112. The conclusion is that:
1 2
if
M S 25
then Pr 2
Corollary 4.2.1. M S. (6d)/23/2 Va, the probability the above random walk UM at least crosses over the positive node labelling of once is at most 6, i.e., Pr YYM 21] 6.
The formula for a arises from an alternative formulation of Cheeger's inequality which expresses A2 using a Rayleigh quotient (Spielman 2015), in which y may be viewed as a real-valued labelling on the vertices.
A min Lv)/(y Dy)
y Id
4.2 SIZE GENERALIZATION ERROR
Recall that, in the size generalization setup, we first train GNN model f on subgraphs induced by many length-N random walks on G. Then during testing, given a large testing subgraph Gm induced by a length- M random walk on G. we sample subgraph GN via a length-N random walk on Gas and feed it to f to compute the empirical (classification) error for GM. If all nodes of Gm are within a single positive node labelling, then all of their labels are the same. Therefore, no matter which subgraph GN is sampled, the generalization error (i.e., the probability of making a wrong prediction) for GM should be the same as the one for Gy. Based on this reasoning, we have the following result.
Theorem 4.3 (Size Generalization Error). For any ô E [0, 1). if we restrict M, the size of the large random walk-induced subgraph, such that M < (6d)/23/2 /a, then the in-distribution generalization error LD O. i.e., the probability of a wrong prediction on length- MM -r--ddom-wwlll induced subgraphs, satisfies
LD S 5 + LDw.0-
(10)
where LDx,0 is the in-distribution generalization error of f on length-N random-walk-induee subgraphs.
Note that this theorem explicitly constrains M, whereas the only condition on N is that LDw is small.
Proof. Observe that, for any events F and E, we have [r[F] I Pr|E] + Pr [F]E]. Let E be the event that length-M MM random walk crosses the positive node labelling of the ground truth labels, and let F be the event that we make a wrong prediction on the induced subgraph Gas- Theorem [3. bounds the second term, Pr [F) B). because the generalization error on GM is the same as the one on GN (subgraphs induced by length-N -V random walks) when GM does not cross the positive node labelling. Corollary 4.2.1 bounds the first term. Substituting the values from the previous two theorems yields the claimed inequality.
We already know the bound of the in-distribution generalization error I.x o due to Theorem 3.1
let us
call this quantity 8. Using this we can obtain the final result for GCNs under our OOD setup. Theorem
4.3
simply states that, if the length M < (8d)/28/2 /a, with probability least 1 8, the OOD generalization error on large subgraphs (induced by length-M random walks) is the sum of error 5 and the in-distribution generalization bound on small subgraphs (induced by length-N N random walks).
7

---

Under review conference paper at ICLR 2023
12020
12000
24
20
Norkom 10r-8
NorHom
13
Norelom
10
Var=B
Hom
10r-4
Ham
ER-1
ER-2
BR-3
ER-4
SBM-1
SBM-2
68-1
BR-2
ER.3
6R-4
SBM-1
5B14-2
(a)
(b)
20.0
L2020
L2020
Taln
000 Taxt sor (tangl Fg!
0Co het
GUTS
17.3
22.5
10.0
15-
5.0
IMDB8
MDD-M
PROTEINS
COLLAB
MDD-3
MM9-M
PROTEINS
COLLAB
(d)
(e)
(1)
Figure 2: Log-generallee generalizzaionn gap values for in-distribution experiments: (a) == 4, Synthetic (b) 6,
Synthetic (d) = 4, Real-world (e) 1 = 6, Real-world. Accuracies for OOD experiments: (c) Synthetic (including both homophilic (Homo) and non-homophilic (NonHomo) graphs) (f) Real-world (Twitch data).
5
EXPERIMENTS
5.1
IN-DISTRIBUTION NUMERICAL PAC-BAYES BOUND COMPUTATION
We conduct multi-class graph classification experiments to compare our improved bound to the original PAC-Bayes bound in (Liao al. 2020). We the same GCN model, adopt the same datasets, i.e., 6 synthetic datasets obtained from random graph models and real world graph datasets used in (Yanardag each dataset,
& Vishwanathan, 2015), and follow the same experimental protocol. After training a GCN
we compute the theoretical bounds using final model. The numerical comparisons of log bound values are shown Figure 2 It is clear that our new bounds are significantly tighter and reduce the bound values by several orders of magnitude. The gap is further increased as the depth increases. The tables of bound values and the specific equations compute them are provided in Appendix B.
5.2 OUT-OFF-ISTTIRUUTIO EFFICACY OF SIZE CENERALIZATION
We performed OOD experiments validate the values of the upper bound on the size of large subgraphs M that was set in Theorem 4. and its related theorems, for synthetic graphs. We also performed experiments on synthetic graphs that non-hone non-homophilic with the same values of M and N, to examine size generalization
8

---

Under review as conference paper at ICLR 2023
in this case. We also examined the general feasibility of size generalization in woal-world social network data, For synthetic graphs, we calculated this theoretical value for the upper bound, and selected large subgraph size M and small subgraph size N < M accordingly. For the real-world case, we chose constant values of N = 10 and M = 50. For each subgraph, we assign as its graph label the label observed most often among its nodes. After sampling datasets of subgraphs of sizes M and N, we train GCN models on the dataset with N-length random walks and measure their performance on the training set, the validation set (a smaller data set generated the same way as the train set), and the testing set (a set of subgraphs inuced by length-M random walks). On the test set we record both the performance when inputting the whole large subgraph (Test error), as well as when performing the sampling procedure used for Theorem 4.3 in which we sample an induced subgraph from an N-length random walk for each data item (Sampling- test error).
Synthetic Graphs. We adopt the CSBMs (Deshpande et al. 2018 to generate graphs that exhibit the ho- mophily property. We use two blocks with much higher probability of connections inside the same block than between blocks, which leads to barbell-like graphs. In the non-homophilic case, we set these probabili- ties to be equal. We generate binary node labellings via the sparsest cut. CSBMs generate node features via a Gaussian mixture where individual choices of the component are determined by the node label.
Real-world Graphs. We used social network data for Twitch streamers from (Rozemberezki et al. 2019). Each node is a streamer (Twitch user), and nodes are connected to mutual friendships. Node features are 3, 3,169 different binary indicators of a wide array of attributes, including games liked, location, etc. Each node is labelled with boolean value of whether the livestreamer has indicated that they use explicit language.
In all cases, the GCN model achieves OOD test accuracy on large-subgraph that was comparable to ID accuracy on small-subgraph if not outright better. This is even the case when some of the constraints are violated: no d-regularity constraint was imposed for any of the datasets, and performance was still good for the test error which did not involve further subgraph sampling. This indicates that the theory is promising in practice for more general forms of size generalization. The accuracy on the train set, test set with subgraph sampling, and unaltered test set shown in Figure 2 and the numerical values are in Appendix B.2
For many cases including all roal-world cases, the test accuracy was actually higher than the training accu- racy. This could potentially indicate that in the cases where size generalization can be guaranteed to work well, the GCN model benefits significantly from extra node information. It is also possible that because of the sampling procedure, there is overlap in nodes between the training and test sets, since they come from walk sampling procedures that naively select a uniformly random node as the initial node.
6 DISCUSSION
In this work we have expanded the theoretical understanding of the generalizations of GNNs in both in- distribution and -ut-of-distribution settings, deriving new theoretical guarantees in each setting. The results for in-distribution learning improve upon the state-of-the art PAC-Bayes bounds in (Liao et al. 2020), and the results for out-of -ffo-iitrribution learning provide insight into a practical learning setting under which GNNs are guaranteed to perform effective size generalization. Future directions for the in in-distribution understanding would involve lowering the dependencies of other variables like the spectral norm of weights. Generalizing the results to other problems like node classification would also be interesting. In the out-of-distribution case, a number of different observations in experimentation indicate that the theory can still be very much expanded. We have identified cases in real-world datasets where well beyond the bounds on size set forth the theory, and in all experiments the d-regularity assumption is violated, yet GCN size generalization is still effective in these cases. Expansions to the theory, including generalizing to non-d-regular graphs, can be explored to explain cases like these.
9

---

Under review conference paper at ICLR 2023
REFERENCES
Martin Arjovsky, Léon Bottou, Ishaan Gulrajani, and David Lopez-Paz. Invariant risk minimization. arXiv preprini (eXivv/907.028800 2019.
Aseem Baranwal, Kimon Fountoulakis, and Aukosh Jagannath. Graph convolution for semi-supervised classification: Improved linear separability and dut-of-disttibutiin generalization. arXiv:2102.06966 2021.
arXiv preprint
Peter Bartlett and Shahar Mendelson. Rademacher and Gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463-433 482, 2002.
Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzales Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro. Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv: 180..01261 2018.
Olivier Bousquet and André Elisseeff. Stability and generalization. The Journal of Machine Learning Research, 2:499-526, 2002.
Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geometric deep learning: going beyond euclidean data. IEEE Signal Processing Magazine, 42,:::1882,220111111
Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with GNNs. Advances in Neural Information Processing Systems, 32, 2019.
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? Advances in Neural Information Processing Systems, 33: 13:13331-03395 2020.
Yash Deshpande, Subhabrata Sen, Andrea Montanari, and Elchanan Mossel. Contextual stochastic block models. Advances in Neural Information Processing Systems, 31, 2018.
Simon S Du, Kangcheng Hou, Russ R Salakhutdinov, Barnabas Poczos, Ruosong Wang, and Keyulu Xu. Graph neural tangent kernel: Fusing graph neural networks with graph kernels. Advances in Neural Information Processing Systems, 32, 2019.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop Representation Learning Graphs and Manifolds, 2019.
Vikas Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. In International Conference Machine Learning, pp. 3419-3430. PMLR, 2020.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George Dahl. Message passing neural networks. In Machine learning meets quantum physics, pp. 199-214- Springer, 2020.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 855-864, 2016.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in Neural Information Processing Systems, 30, 2017.
Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bulletin of the American Mathematical Society, 43(4):439-50) 561999561111160 2006.
10

---

Under review conference paper at ICLR 2023
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in Neural Information Processing Systems, 31, 2018.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR (Poster), 2015. URL
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv: 02907, 2016.
Hongkang Li, Meng Wang. Sijia Liu, Pin- Chen, and Jinjun Xiong. Generalization guarantee training graph convolutional networks with graph topology sampling. In International Conference on Machine Learning. pp. 13014-13051. PMLR, 2022.
Ming Liang, Bin Yang, Rui Hu, Yun Chen, Renjie Liao, Song Feng, and Raquel Urtasun. Learning lane graph representations for motion forecasting. In European Conference on Computer Vision, pp. 541-556. Springer, 2020.
Renjie Liao, Raquel Urtasun, and Richard Zemel. A PAC-Bayesian approach to generalization bounds for graph neural networks. arXiv preprint arXiv:2012.07690 2020.
Andreas Loukas What graph neural networks cannot learn: depth vs width. arXiv preprint
arXiv:1907003199, 2019.
Shaogao Lv.
Generalization bounds for graph convolutional neural networks via rademacher complexity. arXiv preprint arXiv:2102.10234 2021.
Jiaqi Ma, Junwei Deng, and Qiaozhu Mei. Subgroup generalization and fairness of graph neural networks. Advances in Neural Information Processing Systems, 34: 1048-1001,,, 2021.
Sohir Maskey, Ron Levie, Yunseok Lee, and Gitta Kutyniok. Generalization analysis of message passing neural networks on large random graphs. arXiv preprint arXiv:2202.00M6 00645, 2022.
David McAllester. Simplified PAC- PAC-Bayesian margin bounds. In Learning theory and Kernel machines, pp- 203-215. Springer, 2003.
Miller McPherson, Lynn Smith-Lovin Lovin, and James M Cook. Birds of feather: Homophily in social networks. Annual review of sociology, pp. 415 444, 2001.
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A PAC-bayesian approach to spectrally- normalized margin bounds for neural networks. In International Conference on Learning Representations, 2018. URL htttts::/
wfbCZ
Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. 2019.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions neural networks, 20(1):61-80, 2008.
Franco Scarselli, Ah Chung Tsoi, and Markus Hagenbuchner. The Ahpnik-Chervonenkis dimension of graph and recursive neural networks. Neural Networks, 108:248-259, 2018.
Jonathan Shlomi, Peter Battaglia, and Jean-Roch Vlimant. Graph neural networks in particle physics. Ma- chine Learning: Science and Technology, 2(2):021011, 2020.
Daniel Spielman, Spectral graph theory course notes, 2015.
www. cs. http://wwwwwaaaaaae/////////////

---

Under review conference paper at ICLR 2023
Leslic G Valiant. A theory of the learnable. Communications of the ACM, 27:11) 1984.
N. Vapnik and A. Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probubility & Its Applications, 16(2):264-22) 280, 1971. doi: 10.1137/1 1177/1116025.. URL htt.sstts:///oi. .or.ioogg/100 http//..11111/11 1037/111622
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in Neural Information Processing Systems, 30, 2017.
Saurabh Verma and Zhi-Li Zhang. Stability and generalization of graph convolutional neural networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1539-1548, 2019.
Roman Vershynin. Hiihh-immessioal probability: An introduction with applications in data science, vol- ume 47. Cambridge University Press, 2018
Boris Weisfeiler and Andrei Leman. The reduction of graph to canonical form and the algebra which appears therein. NTI, Series, 2(9):12-16, 1968.
Oliver Wieder, Stefan Kohlbacher, Mélaine Kuenemann, Arthur Garon, Pierre Ducrot, Thomas Seidel, and Thierry Langer. A compact review of molecular property prediction with graph neural networks. Drug Discovery Today: Technologies, 37:1-12, 2020.
Qitian Wu, Hengrui Zhang, Junchi Yan, and David Wipf. Handling distribution shifts graphs: An invari- ance perspective. arXiv preprint urXiv:220..024000 2022a.
Ying-Xin Wu, Xiang Wang, An Zhang, Xiangnan He, and Tat-Seng Chua. Discovering invariant rationales for graph neural networks. arXiv preprini arXiv:2201.12872 2022b.
Tian Xie and Jeffrey C Grossman. Crystal graph convolutional neural networks for an accurate and inter- pretable prediction of material properties. Physical review letters, 120(14):145301, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks?
arXiv preprint arXiv:1810.00820 2018
Keyulu Xu, Jingling Li, Mozhi Zhang, Simon S. Du, Ken ichi Kawarabayashi, and Stefanie Jegelka. What can neural networks reason about?, 2020a.
Keyulu Xu, Mozhi Zhang, Jingling Li, Simon S Du, Ken-ichi Kawarabayashi, and Stefanie Jegelka. How neural networks extrapolate: From feedforward to graph neural networks. arXiv preprint 1xXiv:2009//8448 2020b.
Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pp. 1365-1374, 2015.
Nianzu Yang, Kaipeng Zeng, Qitian Wu, Xiaosong Jia, and Junchi Yan. Learning substructure invariance for out-of-distribution molecular representations. Advances in Neural Information Processing Systems, 2022.
Gilad Yehudai. Ethan Fetaya, Eli Mcirom, Gal Chechik, and Haggai Maron. From local structures to size generalization in graph neural networks. In Marina Meila and Tong Zhang (cds.), Proceedings of the 38th International Conference Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 11975-11 11986. PMLR, 18-24 Jul 2021. URL htl.htttp://pproeeeeee html
.mr...m.r.... mwr.sprsrs/////
12

---

Under review conference paper at ICLR 2023
A MATHEMATICAL PROOFS
A.1 PROOF OF THEOREM 3.1
The proof is as follows, and makes up the remainder of the chapter.
A.1.1 IMPROVEMENT ON DEGREE DEPENDENCY
(Liao et al. 2020). a generalization bound attained on graph convolutional networks; this bound dependent a bound on the maximum perturbation of the function value when perturbation U is applied to the weights W, presented that paper's ss Lemma 3.1. The bound as follows
(futu(X fx((
eBa' Tiwalle ll2
Σ
| W
(11)
The primary goal this of improvements reduce the factor of d d For each layer, let H₃ E RRI/ be the matrix containing the hidden embeddings of all of the nodes in its rows, with h being the hidden dimension, In the process the proof Theorem 3.1 we are able to show the following:
Φ = max Hy | < d B
Will2
(12)
v, = max [[g]i - H,16,:11
II [Wll2 ) Walll
1/ 11el
1+ 1
j-h
S Bd
(13)
A
n 1n 1a/1111110 (Wi + U1)
1,, H
Wi
2
1
S =
Willa
W l|
We begin to simplify these bounds by removing the dependency on dí, replacing it instead with fixed
power of 1/2 that remains constant for every layer, and thus in the final result of Equation 11 well.
Theorem A.1. For all 1 < - 1, we have:
Φ <
Vd B
Wellz
(14)
1=1
S
(1+
B
va
I
5
[Walle
(15)
Finally.
13

---

Under review conference paper at ICLR 2023
(X fxx A)12 14r2 < (e+1+
2
B
vd
W l2
(16)
1
The proof follows from lemma about the 2-norm of any node representation any layer: Lemma A.I.1. We have, for all k E [n]] aor E [4]=
H, I v deg(u) u)
II [Will2
(17)
Proof. We prove this by induction. By definition Ho[u, :]I2 S B and thus
|oll]] I dde((u) W W2ll2
We assume that for all u, we have
H5-1/u,: S /eg(())) B II Will.
1==1
From these statements able deduce
:l] S Σ
Ll, ul|lii--lo, -lle////ll// 3
vEN
5-1
v Vdeg(v) II
veA, degg())eeg(
A=1
f-1
1
B
[[Wlll
11Will2
deg(u)) veA,
deg(u)
|Well2
k=1 de)
deg(u) W
k=1
(18)
In these inequalities the fact that ][ (A + 1)s// ddeg(i)deg()), and assume the simple case where there are unweighted edges so that (A + T) is and only nodes i and j are connected and () otherwise.
By Lemma A.1.1 we have that +-- = max; H [i. & VdB
II'
[ l1,, which is exactly the result of
equation (4)
14

---

Under review as conference paper at ICLR 2023
Claim A.I. For all U E [n], A S Bydeg(e) (1 + +) (IT' [IW:ll)
(Σi
[wil
Proof. Proof: We use induction assuming this is true for アリー We then have
Σ
Lu u| [1jHHH11,,, [u,
Hy- -122211/ Ugll2+ E
Llu.u|lHH- u||H =1l2211 |211,|
vEA((e)
uEN((v)
Σ
Uulle [Will
< B +
[ill
[ +
B
Will
(19)
Σ (E)(())
Liv, u| deg(u)
f-1
[W, + U,ll (1+ 1
10:112
deg(())
||all
7)
+ ||0|||
|Will
1=1
[W, + U,
1+ 1
||Uall2
||0/12
B /eg(())
7
IW, l12
||all22
IW
<=1
j
(1+ :)
||Ubll2
|1Ul|2
< BB B deg(v)
Wlll
[Wella
WWlll
i=1
< BBddeg ())
IW
(1+
(1+
| llz [W&ll2
(20)
A has a slightly different formulation but it has a very similar bound:
1n [LI + Ui) - I
A
1n InL(H|-1 - + Ui) + 1, IH
"
a
A 16, 112 11 + 02112 + n
Σ
n
W (1+
|ull
< Bvd
|
|
1=1
BVd|Uilla
II |Wall2
2=1
[1+
S Bva
[
+
Will
(1+))
|
S Bvd
[
||
1=1
155

---

Under review conference paper at ICLR 2023
Σ Gull
S eBva W.l |1
(21)
Will
i=1
From this have proven tighter bound the final output of the GNN under perturbation, which we will use to calculate probabilistic and generalization bounds.
A.1.2 IMPROVEMENT ON PROBABILISTIC BOUNDS USING RANDOM MATRIX THIBORY
(Liao et al. 2020), for E [1, with being the number of layers, the prior and the distribution of the perturbations U, E Rd++1xd; where all hidden dimensions d; are upper-bounded by value h, were generated by a normal distribution (O, r²I), and give probabilistic bounds on the operator norms |Uil P (vi, ||&||| I t) with probability greater than 21h exp -t² f2/2ho² We improve these bounds using theorems on random matrices from work on high-dimensional probability, namely (Vershynin) 2018
Theorem A.2 (Theorem 4.4.5 in Vershynin, 2018)). Let A be matrix in Rmx" where the entries Ag are independent, mean-zero, sub- GabbGaassinn random variables. Then, for all t we have
|| & CK(Vm +
with probability 2 exx(-x?))) where K max., || 1v and C is some constant.
the above theorem the norm || is defined as inf : Elexp(X2/e)) < 2]. Example 2.5.8 in (Vershynin 2018), is shown that if X NO, o²) then it has || S Co.
Corollary A.2.1. U E R is a random matrix generated with the distribution N(0, I2 (i.e. all entries are independent and identically distributed Gaussian random variables), then we have
| S alvm vt+
with probability at least 112-xppl 2exp(-(2).
With a change of variable, we are able calculate the following:
P PVVi|U 21) P( Utll 1)
2 Σ P(1U:||> >
2 - 21exp (1: 22
And by setting the right-hand side to 1/2, we obtain:
t= Co(2hh++ (n(l))
Using the above equation combined with our bound able get
16

---

Under review conference paper at ICLR 2023
|uA 1 W
lfu+u(X A) (X,, S eBVd
II
Wella
1=1
||U&ll2
eBVas
B
SeBvas-~>lo vln(4)))
< In(4l))
7
(22)
4
Here is an estimated of 3 such that |B 31 S B/1 that can be generated priori; we discuss this in later subsection.
We can set
4ca B3BBCC (2/T- (2(4+) to satisfy the final inequality. From this we can calculate the
KL-divergence between the posterior and the prior:
16e B2d 321-11 (2vh + vln(4t) 2
3
PL(QI
|Wll
20
272
B²d In(())
W
0
72
32
|W&ll
I
$ 0
d²
+ In))))
(23)
From this we are able to calculate the generalization bound and thus prove the theorem.
B2dP in)) IEEEL
W.ll WIF
+ In M
Lpo S Iss + +
(24)
m
A.1.3 SELECTING PARAMETER 3
The prior normal distribution's 's variance parameter o² is dependent on 3, but 3 cannot used in its calcula- tion because that information is only known after model training. Instead, we can select a parameter & such that | - 3 < } 3 and thus g/ < 3 â1-1 < e (as per equation 33 in (Liao et al. 20200).
As in Liao al. 2020 we only have to consider values of 3 in the range
1/1
T m
3
2B
2Bvd.
otherwise the generalization bound holds trivially because Lp,0 I 1 by definition.
17

---

(F(S,S) Under review conference paper at ICLR 2023
If consider values of 3 that cover this interval then by union bound we are still able get a high probability; the covering C' needs have |C| (m 1).
A.2 PROOFS OF OUT-OF-DISTRIBUTTOO PROBABILITY BOUNDS
A.2.1 PROOF OF THEOREM
Proof. Because u is chosen from the stationary distribution (uniform vertices, because G is connected and d-regular), then for all 2 the distribution for ui, W441 follows the distribution Unif [], where E the edge set of the graph.
Let be the sparsest-cut partition of G. Let X; be the indicator the event that the vertex pair is in the set of edges crossing the partition, namely 1 [[4 u4+1) E E)S, By linearity of expectation, this means that [ = [S, E).
Furthermore, let Y& be the cumulative number of edges crossing the partition along the first & steps of the random walk. This is expressed nicely as Yv Σx X, Thus [[T]] k (E(S,S))
Applying Markov's inequality, we get Pr[Y; 2 ES 5)1/ S. 1/t. Suppose we wish examine under what conditions we can ensure that we do not cross over the partition at all in M steps, i.c. Pr[YM 2 1] s 1/2. From the inequality above, we are able to get that
YM 2 2M
S
E
2
just by setting &o = M and 2. We then the following basic fact: if we have an inequality of the form Pr[Z' 2 =] & 2. then Pr[Z 2 = S 2 for any z' z.
Let FSS) denote the set of edges connected any vertex in S. Because [E(S) F., then have [F(S, F| < (E / E(S) Furthermore, since we assume a connected graph, |E(S) 2 (d/2)[S),
and thus () - (ESS (1/ Thus using the fact above we can deduce
ESS, S) (d/2)|S]
Ym 2 2M
S
Note that (S, S) the conductance of the graph (GG), because was defined to be the sparsest-cut partition of G. Thus we can apply the fact again with Cheeger's inequality to get
YM 2 2M(2/d) - 2
And since we are interested in Pr[YM 2 11, we can thus set 2M /212 S 1 to get a necessary condition for M, from which we achieve
d
M <
25/2 /X2
This completes the proof.
It is important note that this specific dependency of [E(S) on d requires G to be d-regular graph. the theorem is to be expanded to general cases, may use the simple inequality [E(S) 2 [S].
18

---

Under review conference paper at ICLR 2023
A.2.2 PROOF OF THEOREM 4.2
Proef. The quantity yp transformation of yp that retains all the information contained in while still being orthogonal to the all-ones vector 1. so that can apply Cheeger's 's inequality. This orthogonalization is rather standard and can be found in Spiclman 2013).
Let | (G)). Note that E [0, 1J. and without loss of generality we can assume that 1/2.
We observe that the eth coordinate of the vector yp' corresponds to the mapping
1 VE S U&S
('(u)
(25)
This ensures that yp is orthogonal to 1,
p'(()) = |S| (1
|S|
(- |S]
S
+ ([V) - 1S|)
- --S|-
- |V
= 0.
[v]
V
V
We then note that || Σn Di=1 ( is equal to s(1 =) and we can infer |S|/2 < 1441 S |S| the
first inequality holds since 1/22.
The number of edges |E(S, S)1 crossing the chhelling-parttiinn is equal to G L.p', as
T Lip's
Σ
((p(u) - 8) (v(()) - 8))² E{(S
(NN)ER
where L is the Laplacian matrix of G.
Thus the quantity 2M [E(S))) [SS)
(d/2)|s] We are able to get the second inequality because we know [E(S) 2 (d/2))S{. Because we know that |S| 2 ||</'|3, we can then upper bound this
< 2M
L'p Lip' [ETST 2M T
further by 2M 6 Lep' bound for M.
Substituting this quantity the proof of Theorem we achieve the desired
(d/2)
B EXPERIMENTAL METHODOLOGY AND RESULTS
B. IN-DISTRIBUTION EXPERIMENTS
The datasets used a combination of synthetic (Erdos-Renyi and Stochastic Block Model) and real-world graphs (IMDBBINARY and IMDBMULTI of data from the Internet Movie Database, and COLLAB, a dataset of academic collaborations). and a bioinformatics dataset, PROTEINS, from (Yanardag & Vish- wanathan 2015).
Two different GCN network depths of of I and were used.
We use the following formulae for the generalization bound from (iaoo et al. 2020) and our new bound, using an explicit constant factor of 42 from (Liao al. 2020
B2d 12 (n(4
Il_ | |WE
GenGap L, (,.,))
42
(26)
22m
Similarly, the formula used for the new PAC-Bayes generalization bound is
19

---

Under review conference paper at ICLR 2023
(h+
JI: &
G, (W.)))) = 12
V
(27)
7
We remove additive Ollogm) term in the numerator within the square root after validating that it was numerically negligible.
Tables below are for calculated bounds in the case of 4 layers (Table T and 6 layers (Table 2
Dataset ER-1
(iao al. 2020
New bound
14.985735 + 0.071
11.727639 = 0.071
ER-2
15.972616 0.068
12.080796 0.068
ER-3
16.533779 + 0.038
12.285284 + 0.038
ER-4
16.869156 0.000
12.391819
0.000
SBM-1
15.859210 + 0.080
12.030569 + 0.080
SBM-2
15.503044 0.066
11.892126 0.066
IMDEBINARY
17.370839 + 0.079
12.458184 = 0.079
IMDEMULTI
16.466189 + 0.038
11.977553 + 0.038
COLLAB
19.773157 0.009
13.574678 = 0.009
PROTEINS
14.011104 + 0.079
10.753008 = 0.079
Table I: Table of generalization bounds, layers (log values)
Dataset
(Liao et al. 2020
New bound
ER-1
20.123308 + 0.046
13.607115 0.046
ER-2
21.814967 + 0.017
14.031327 = 0.017
ER-3
22.782537 + 0.008
14.285547 = 0.008
ER-4
23.377554 + 0.021
14.422881 + 0.021
SBM-1
21.605130 0.037
13.947847 + 0.037
SBM-2
21,028283 0.047
13.806447
0.047
IMDBBINARY
24.648394 = 0.058
14.823084 = 0.058
IMDBMULTI
23.373624 0.105
14.396352
0.105
COLLAB
28.261012 + 0.106
15.864055 + 0.106
PROTEINS
19.421826 0.059
12.905633 = 0.059
Table 2: Table of generalization bounds, layers (log values)
B.2 OUT-OF-DISTRIBUTIIO EXPERIMENTS
B.2.1 METHODOLOOGY
Experiments were performed to measure the effectiveness size generalization GCN models when applied to the size generalization learning case described in Section where the learning task is classifying the most common node label in sub-communities of a large underlying network.
For each of the synthetic graphs, we calculate upper bound for M set in the out-of-distribution inequalities xe Li we have derived. Since the graphs examined are all not d-regular, we calculate a value a as Di' where is the graph Laplacian matrix and the diagonal degree matrix, to apply to the formula set in Theorem more permissive value of 5 0.75.
Furthermore,
20

---

Under review conference paper at ICLR 2023
Similar upper bounds for M were computed for the real-world cases, but the values were too small for experimental use. In this case, we just set N = 10 and M = 50 to attempt to gain insight about the size generalization task's general feasibility real-world cases.
All experiments were performed with use of the Adam optimizer (Kingma & Ba 2015), with a constant learning rate 0.01. Models were trained for 10 epochs, with a batch size 32 randomly selected.
The models used are different parameterizations of the Graph Convolutional Network as implemented by the library syytoree-eomeet cerometrii (Fey & Lenssen (019). For synthetic experiments, which used smaller graphs with generally smaller degree, the parameterization was 3 layers with hidden dimension of 5, and for the real-world data case, the parameterization was 10 layers with a hidden dimension 32.
For each underlying graph, we generate three train/validation sets (of size N random walks) and test sets (of size M random walks) and we record the loss and accuracy as the average of the three runs.
B.2.2 SYNTHETIC GRAPH EXPERIMENTS
A large underlying synthetic graph was generated using the stochastic block model, with some adjustment ensure that the -egnerrtee graph had single connected component. By controlling the intra- and inter-block connection probability values, we are able control the homophily of the generated graph, which we validate by measuring the value of X2, as well calculating the sparsest cut via "Cheeger rounding" (Spielman 2015) and subsequently the conductance the graph with respect to this partition.
In the experiments, we generated graph with approximately 2000 nodes, with in-block connectivity prob- ability set to 8/ 8/1000 and inter-block connectivity set to 6/10².
Node features are generated from mixture of multivariate Gaussian distributions with dimension 3, mean (-0.5, -0.5, -0.5) for one block, and mean (0.5, 0.5, 0.5) for the other; the covariance matrix a diagonal matrix (each coordinate is independent) of variance either 2, 4, or 8.
Experiments were also performed on non- non-hooophillic synthetic graphs. Like the homophilic synthetic graphs they generated with the stochastic block model with about 2000 nodes, about 1000 of each label, and with the same mixture-of-GGausian node features. However the parameters used for the generation connection are crucially different. The probabilities of connection between nodes of the same block and nodes of different block are set to be equal, with both being set to 8/ 8/1000. These settings ensure that node's label is independent from the labels of its neighbors, so the homophily property
exhibited.
Contrasting with the results shown for the homophilic synthetic graphs, the non-homophilic graph results show that the out-of-distribution test accuracy is less than the training accuracy. This further illustrates the association between homophily and size generalization.
B.2.3 REAL-WORLD GRAPH EXPERIMENTS
Since the node features are indicators, we encoded the node feature information by using the positional encoding mechanism introduced in the Transformer model (Vaswani et al., (017). For each node, each of their integer indicators was encoded via positional embedding and aggregated via sum.
21

---

Under review conference paper at ICLR 2023
Train loss
Train
Val.
Val.
Test
Test
Test
Test
Graphs
22
N
aCc.
loss
acc.
(sampling)
loss
(sampling)
acc.
loss
acc.
CSBM var=2
20.7
10
20
0.005
0.953
0.007
0.943
0.020
0.869
0.003
0.970
CSBM var=4
18.6
10
18
0.014
0.889
0.014
0.897
0.026
0.811
0.009
0.937
CSBM var=8
17.5
10
0.021
0.826
0.022
0.803
0.032
0.745
0.015
0.880
CSBM non-homophilic var=2
5.12
10
0.032
0.723
0.032
0.720
0.049
0.611
0.034
0.704
CSBM non-homophilic var=1
5.14
10
0.036
0,676
0.041
0.643
0.049
0.596
0.038
0.655
CSBM non-homophilic var=8
5.12
10
17
0.042
0.630
0.045
0.570
0.049
0.575
0.043
0.600
Twitch-ENGB
10
50
0.042
0.581
0.044
0.570
0.025
0.764
0.025
0.764
Twitch-FR
10
50
0.013
0.877
0.012
0.887
0,002
0.984
0.002
0,984
Twitch-ES
10
50
0.006
0.944
0.008
0.923
0,000
0.999
0,000
0.999
Twitch-PTRR
10
50
0.010
0.902
0.011
0.893
0.001
0,989
0.001
0.989
Twitch-DE
10
0.035
0.672
0.032
0.690
0.008
0,921
0.008
0.921
Twitch-RU
10
0.003
0.974
0.004
0.973
0.000
1.000
0.000
1.000
Table 3; Experimental data for out-of-distribution experiments
22


Reviews:
[{"review_id": "vDtEMGPNzB", "reviewer": "Reviewer_Lvuo", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this paper, the authors propose theoretical analyses for the generalization of GNNs. For the in-distribution case, the authors propose an improved bound regarding graph classification compared to the existing PAC-Bayes results. For the out-of-distribution generalization, the authors propose an analysis for node classification by using random walks instead of assuming a ground-truth generative model.", "summary_of_the_review": "This paper proposes theoretical analyses for the generalization of GNNs, which is an important topic. My main concerns lie in the reasonability of the assumptions and the paper's relationships compared to the literature.\n", "strength_and_weaknesses": "**Pros:**  \n1. The generalization, specifically out-of-distribution generalization, of GNNs, is an important and trending research direction, and its theoretical analysis is not well studied.  \n2. The proposed in-distribution bound seems to improve over the existing analysis.  \n\n**Cons and questions:**  \n1. For OOD generalization, this paper focuses on a specific setup, i.e., graph classification where the graphs are sampled from a giant graph, and the graph label is determined by homophily. Though I acknowledge that such an assumption may be unavoidable for rigorous theoretical analysis, it seems to be impractical and thus greatly limits the scope of the proposed analysis. For example, many works on OOD generalization for graph classification focus on molecule classification, where training and testing molecules are collected in different environments/with different backbone structures, which is a completely different scenario and the proposed method seems unable to fit.  \n2. Following the above comment, the authors observe in experiments that “the GCN model achieves OOD test accuracy on large-subgraph that was comparable to ID accuracy on small-subgraph if not outright better”, which contradicts previous works such as Yehudai et al. (2021). This may also suggest that the assumed setting is not practical.  \n3. A previous analysis shows that the GNN architectures and downstream graph tasks can greatly affect the generalization of GNNs [1]. I think this work is highly related and a proper discussion should be added.   \n[1] How Neural Networks Extrapolate From Feedforward to Graph Neural Networks, ICLR 2021.  \n4. It would also make the paper stronger if the authors can briefly point out how the proposed analysis can inspire improving GNNs, which is crucial for GNN practitioners.  \n\nMinor:\n(1) Figure 2 is a bit vague (vector graphics are recommended).\n\n===after rebuttal===  \nI have read the rebuttal and thank the authors for the clarifications. Similar to other reviewers, I think the paper makes interesting theoretical analyeses, but rely on very strong assumptions, so I am not entirely sure whether such contributions meet the bar of ICLR. All things considered, I have increased my score to 6, i.e., slightly positive. ", "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": {}}, {"review_id": "DqGiT3oRIAy", "reviewer": "Reviewer_KCgB", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies in-distribution and out-of-distribution generalization with graph convolutional networks. In the former setting, the paper improves on an existing bound in the literature by reducing dependency on maximum node degree to a linear factor. In the latter setting, the paper builds on in-distribution results, and considers the case of homophilic (but arbitrary) graph structures. More specifically, the out-of-distribution setup considers a single very large graph from which smaller training graphs and larger testing graphs are sampled using random walks. Then, the paper considers the majority voting problem, in which the binary label of a graph is the binary label of the majority of its constituent nodes. Using a probabilistic argument, the paper then shows that, for homophilic graphs, the probability of conducting a random walk that crosses the label divide, i.e., from label 0 to label 1 or vice versa, in the original large input graph can be thresholded to a quantity delta with reasonable bounds on the test graph size M and training graph size N. This probability can then be considered jointly with the probability error in the in-distribution theorem to yield an overall error probability for this out-of-distribution setting. Finally, the paper conducts an empirical analysis on a variety of synthetic and real-world datasets, showing performance levels consistent with the theory, and even demonstrating strong performance when certain assumptions are violated (degree regularity for example).", "summary_of_the_review": "All in all, I believe that the paper makes a useful contribution for studying the generalization performance of GCNs. I find the in-distribution result to be strong and potentially impactful. I also appreciate the perspective offered in the out-of-distribution analysis, and how this avoids making assumptions on the graph structure. However, I have concerns about the restriction to the objective function, which in my opinion casts doubts on the general applicability of the approach, particularly its probabilistic argument for scaling the in-distribution theorem to the out-of-distribution setting. All in all, I am learning towards supporting the paper. I am also happy to hear back from the authors about my concerns, and am willing to support the paper more strongly should my concerns be addressed. ", "strength_and_weaknesses": "# Strengths: \n- The improvement of the in-distribution bound is significant and meaningful. The proof of this theorem also appears to be sound\n- The setting proposed for out-of-distribution analysis is interesting and avoids making assumptions on the inherent graph structure, and thus offers a novel approach to studying how graph convolutional networks can generalize to larger graphs. \n\n# Weaknesses: \n- Though the out-of-distribution setup is interesting and avoids assumptions on the structure of the train and test graphs, the assumptions it introduces instead appear to be limiting. In particular, the graph labelling objective seems restrictive and specialized. Typically, graph classification objectives go far beyond node statistics (majority of labels) and explore structural graph properties, which lies outside the scope of this analysis. It is also not at all clear to me how one can move beyond this limitation: The very essence of the probabilistic argument in the paper relies on aggregating over node classes, and thresholding the probability of transitioning between classes in a random walk: Without a node-based objective, such an analysis is not relevant. Therefore, I am afraid this approach cannot be used to develop a more general (objective-agnostic) framework for out-of-distribution generalization. I understand that assumptions inevitably must be made about a connection between the train and test sets (shared structure, or in this case similar walk outcomes with respect to the objective), however I feel that simplifying assumptions on the objective function will not lead to general insights on out-of-distribution learning, as claimed in the paper. I therefore suggest that the authors clarify the limitations and scope of their analysis more extensively.\n\n- On a more minor note, it would be interesting to mention how/if the results extend beyond the GCN architecture. Currently, the result and proof requires a GCN, but it would be useful to provide an intuition as to how such a framework can be applied to other models.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "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": "C8V3TdVqHKc", "reviewer": "Reviewer_y9pP", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper focuses on the generalization ability of graph neural networks and derives the generalization error bound based on PAC-Bayes framework. The new theoretical bound improves the state-of-the-art result, and empirical studies show that the proposed model can help to address size generalization problem on graphs.", "summary_of_the_review": "Overall, I think this paper is well motivated and written. The theoretical results are interesting and reasonable. However, I believe there still exists much room for improvement based on the current version. For example, more discussions on other out-of-distribution settings and distribution shift types are needed to strengthen the contributions. And, more experiments with other OOD settings could also help to increase the impact of this work.", "strength_and_weaknesses": "Pros:\n\nThe paper is well motivated and focuses on an important and active research problem in the graph ML community. The theory results seem correct and reasonable though I didn't carefully check the proof in the appendix. The experiment results verify the theoretical argument.\n\nCons:\n\n1. The analysis is built on several assumptions that may violate the practical settings, like the graph data generation assumption. More discussions and justification are needed.\n\n2. The proposed theory seems to require the homophily assumption of graph structures. How it behaves for heterophilic graphs?\n\n3. The discussed distribution shifts only cover the size variation, which is quite limited in contrast with the various distribution shift types in practice. For example, cross-domain transfer in multi-graph generalization and temporal generalization in dynamic graphs [1], subgroup generalization across majority and minority feature groups [2], motif-structure bias of spurious correlation [3], and substructure-aware distribution shift in molecular property prediction [4], etc. More discussions on how the theory in this paper could shed lights on these practical OOD learning settings can definitely help to strenghthen the paper.\n\n4. The experiments are only conducted on the size generalization task. And, similarly, more experiments to cover the more OOD types, such as the above-mentioned settings, which can be more challenging and closer to the real cases could increase the diversity and strengthen the contributions.\n\n[1] Handling distribution shifts on graphs: an invariance perspective, ICLR22\n\n[2] Subgroup generalization and fairness of graph neural networks, NeurIPS21\n\n[3] Discovering Invariant Rationales for Graph Neural Networks, ICLR22\n\n[4] Learning Substructure Invariance for Out-of-Distribution Molecular Representations, NeurIPS22", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "65IS-9k9gL3", "reviewer": "Reviewer_MGXu", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the PAC-Bayes generalization bound for both IID and OOD generalization on graphs, with a focus on homophilic graphs and graph size shifts. In particular, the authors reduce an exponential dependency on the node degree to a linear dependency for the IID generalization bound. Then they further apply the generalization bound to study random walk sampled graphs with different sizes. Besides, they conduct some experiments to support the derived bounds.", "summary_of_the_review": "Although I appreciate the completeness and clarity of the paper, many overclaims and misleading experiments, plus the limited scope of the paper, make the paper a clear reject.", "strength_and_weaknesses": "While I appreciate the completeness and clarity of the paper, I find the scope of the paper is rather limited, or even overclaimed by the authors.\n\n**Overclaimed improvements in IID generalization bound.**\nThe authors claimed that reduce an exponential dependency on the node degree to a linear dependency for the IID generalization bound. However, they also exacerbate the dependency on **hidden dimensions $h$** from log scale to linear. This essentially establishes a trade-off between their bound and that from [1]. The advantages only exist for graphs with high degrees and GNNs with deep layers. In contrast, many of realistic graphs (e.g., molecules) tend to have a lower degree. Practitioners tend to adopt a shallower and wider GNN due to the memory cost, especially for homophilic graphs where simple MLP with some post-hoc modifications can achieve top performances (cf. leaderboard results in OGB).\n\nWhen demonstrating the advances of the established generalization bound over [1], the authors seem to be conducting **misleading comparisons**. Since the advances only exist for graphs with high degrees and GNNs with deep layers, the authors are using a deeper GNN (4, 6, 10 layers compared to 2, 4, 6, 8 layers in [1]), and small hidden dimension (5, 32 compared to 128 in [1]). This makes the improvements and significance of the IID generalization bound limited.\n\n**Overclaims in assumptions for OOD generalization bound.**\nWhen it comes to the OOD generalization bound, the authors claimed their setup has advantages over some OOD setups in the literature where a generative model of graphs and labels is explicitly assumed [2,3,4,5,6,7,8,9]. In particular, in the paragraph of Size Generalization Assumptions in the paper, the authors are essentially making assumptions about the data generation process. The graphs are sampled from random walks with different lengths, which forms a specific graph family just like graphon [2,3,6,8,9]. The labels are determined by the majority of labels in the training graphs, which essentially have little difference from the causal assumptions made in [2,3,4,5,6,7,8]. I didn’t see the advantages of the assumptions made in the paper. \n\nHowever, this paper introduces additional assumptions that require the graphs to be homophilic, which makes the random walk sampling over the large graphs trivial. As [10] already found that random walks with more steps will converge to some stationary distributions over the original graphs. Therefore, analyzing homophilic graphs sampled using random walks with more steps seems to be less interesting. \n\n\n**Limited scope and poor coverage of the literature.**\nAlthough, as pointed out by other reviewers that this work is limited to graph size shifts and missed discussion with many related works, I still find many missing discussions and comparisons in [2,3,4,5,6,7,8,9]. In particular, [2,3,6,8] studied graph size shifts as well, but I can’t find any discussions in work. Both the theoretical and empirical parts of the work lack a comparison with these works.\n\nReferences:\n\n[1] A PAC-Bayesian approach to generalization bounds for graph neural networks, ICLR21.\n\n[2] From Local Structures to Size Generalization in Graph Neural Networks, ICML21.\n\n[3] Size-Invariant Graph Representations for Graph Classification Extrapolations, ICML21.\n\n[4] Handling distribution shifts on graphs: an invariance perspective, ICLR22.\n\n[5] Discovering Invariant Rationales for Graph Neural Networks, ICLR22.\n\n[6] Invariance Principle Meets Out-of-Distribution Generalization on Graphs, ICML22: Workshop on Spurious Correlations, Invariance and Stability.\n\n[7] Learning Substructure Invariance for Out-of-Distribution Molecular Representations, NeurIPS22.\n\n[8] OOD Link Prediction Generalization Capabilities of Message-Passing GNNs in Larger Test Graphs, NeurIPS22.\n\n[9] Generalization Analysis of Message Passing Neural Networks on Large Random Graphs, arXiv22.\n\n[10] Representation Learning on Graphs with Jumping Knowledge Networks, ICML18.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "6-ownU8E09", "reviewer": "Reviewer_h6gY", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The objective of this paper is to provided bounds on the generalization of GNNs in both the in-distribution and out-of-distribution setting. For the in-distribution case, the authors tighten the bounds provided in Liao et al. (2020) by scaling down two separate terms in the PAC-Bayes bound. For the out of distribution setting, the authors analyze the specific issue of size generalization (GNNs trained and tested on subgraphs of differing sizes); the authors provide a bound on the generalization error motivated by the fact that for homophilous graphs, an increase in size does not affect the graph classification with a certain probability. \n\nThe setup for the in-distribution generalization error is as follows: there exists a distribution over the set of graphs, node features and graph labels. A GCN is trained on m samples from the distribution, and then the task is to bound the gap between the true risk (probability the graph label is off by a margin gamma) and the empirical risk (the training error). \n\nLiao et al. (2020) provides a bound for the above gap. The present paper tightens two terms. First, the authors claim that the gap does not grow exponentially with the maximum degree but linearly. The authors show that when performing induction over the layers of the GCN, due to normalization, it is possible to maintain a linear dependency on degree (pages 13-14). Second, the authors tighten a separate term by utilizing a random matrix theory theorem from (Vershynin, 2018).\n\nThe setup for size generalization (out of distribution) is as follows: there exists a very large graph G. For training, a GCN is trained on subgraphs of G generated by performing random walks of length N and taking the induced subgraph. For testing, however, the test subgraph is generated by a random walk of length M >> N. The goal is still to perform graph classification. Every node in the graph has a label and the subgraph label is simply the most common ground truth or predicted node label. \n\nThe core tool needed to bound the size generalization error is the observation that due to homophily it is possible to bound the probability that a random walk of size M reaches a node of a label differing from the label of the initial node. In the case where the random walk does not reach a node of a differing label, the length of the random walk does not impact the subgraph label. ", "summary_of_the_review": "Overall the paper tackles an important GNN issue and moves the community toward understanding the theoretical generalizability of such models. The paper is also comprehensive in considering both in-distribution and out-of-distribution generalization. The largest areas of improvement, in my opinion, are better placing the significance of these results in context and more thorough experiments. The exact benefit of the tightened in-distribution bounds is not clear (would recommend a more detailed experiment isolating the benefit of the linear degree term) and for out-of-distribution, it is not clear when it would be appropriate to sample the large testing subgraph.", "strength_and_weaknesses": "Pros:\n* The paper tackles an important topic in better understanding the theoretical generalization bounds of GNNs. Further, the paper is comprehensive in looking at both in and out of distribution generalization. \n* The paper is clearly written and understandable for a reader familiar with GNN/GCNs but not with theoretical generalization bounds of these models. \n\nCons:\n* For the in-distribution bounds it is not fully clear what is the significance / level of contribution of tightening the bounds in Liao et al. To me this could be better shown with a more detailed analysis of the experimental results in sec. 5.1 in particular for the real-world graphs. As is the log-generalization gap values are difficult to interpret and put into perspective.\n* It would be helpful to have more specification for when the expression for M in Theorem 4.3 is compatible with the condition that M >> N.  \n* In analyzing the size generalization, it can be argued that the paper translates an out-of-distribution question into an in-distribution one. Specifically the paper largely side steps situations in which it is desirable to test the GNN on the large subgraph itself instead of sampling from the test subgraph, for instance the setting considered in “From Local Structures to Size Generalization in Graph Neural Networks”. \n* It is helpful that the authors explain the surprising findings in Figures 2c and 2f; however, it would be helpful to also include cases where the test accuracy is not higher than the training accuracy. When the test accuracy is always higher the results preclude the need to understand out-of-distribution generalization.\n\nMinor comments: \n* On page five when describing the size generalization setup in the following sentence: “In testing, we assume a procedure where a length-N random walk induced subgraph is sampled from the large subgraph”, it was not clear to me that the large subgraph is the length-M random-walk induced graph until later. ", "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": {}}]

Author rebuttal:

Decision: Reject