A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networks
Authors: Renjie Liao
Raquel Urtasun
Richard Zemel
Venue: ICLR 2021 Poster (2021)
Keywords: PAC Bayes
Generalization Bounds
Graph Neural Networks
Graph Convolutional Neural Networks
Message Passing GNNs

Abstract: In this paper, we derive generalization bounds for two primary classes of graph neural networks (GNNs), namely graph convolutional networks (GCNs) and message passing GNNs (MPGNNs), via a PAC-Bayesian approach. Our result reveals that the maximum node degree and the spectral norm of the weights govern the generalization bounds of both models. We also show that our bound for GCNs is a natural generalization of the results developed in \citep{neyshabur2017pac} for fully-connected and convolutional neural networks. For MPGNNs, our PAC-Bayes bound improves over the Rademacher complexity based bound \citep{garg2020generalization}, showing a tighter dependency on the maximum node degree and the maximum hidden dimension. The key ingredients of our proofs are a perturbation analysis of GNNs and the generalization of PAC-Bayes analysis to non-homogeneous GNNs. We perform an empirical study on several synthetic and real-world graph datasets and verify that our PAC-Bayes bound is tighter than others. 

Published as a conference paper at ICLR 2021
A PAC-BAYESIAN APPROACH TO GENERALIZATION BOUNDS FOR GRAPH NEURAL NETWORKS
Renjie Liao 1,2 Raquel Urtasun 1,2.3, Richard Zemel 1.2.3
University of Toronto', , Vector Institute", Canadian Institute for Advanced Research {rjliao, urtasur, 2eme1] toronto.edu
ABSTRACT
In this paper, we derive generalization bounds for two primary classes of graph neural networks (GNNs), namely graph convolutional networks (GCNs) and mes- sage passing GNNs (MPGNNs), via a PAC-Bay AAC-Bayesian approach. Our result reveals that the maximum node degree and the spectral norm of the weights govern the generalization bounds of both models. We also show that our bound for GCNs is natural generalization of the results developed in (Neyshabur et al., 2017) for fulny-con and convolutional neural networks. For MPGNNs, our PAC- Bayes bound improves over the Rademacher complexity based bound (Garg et al., 2020), showing tighter dependency on the maximum node degree and the maxi- mum hidden dimension. The key ingredients of our proof's are a perturbation anal- ysis of GNNs and the generalization of PAC-Bayes analysis to non- non-homogen non-homogeneous GNNs. We perform an empirical study on several synthetic and woal-world graph datasets and verify that our PAC-Bayes bound is tighter than others.
INTRODUCTION
Graph neural networks (GNNs) (Gori et al., 2005; Scarselli et al., 2008; Bronstein et al., 2017; Battaglia al., 2018) have become very popular recently due to their ability learn powerful data, and have achieved state-of-the-an art results in variety
representations from graph-structure of application domains such as social networks (Hamilton et al., 2017; Xu al., 2018), quantum chemistry (Gilmer et al., 2017; Chen et al., 2019a), computer vision (Qi et al., 2017: Monti et al., 2017), reinforcement learning et al., 2019; Liang et al., 2020), and physics (Henrion et al., 2017). Given a graph along with node/edge features, GNNs learn node/edge representations by propagating information on the graph via local computations shared across the nodes/edges. Based the specific form of local compu- tation employed, GNNs can be divided into two categories: graph convolution based GNNs (Bruna et al., 2013; Duvenaud al., 2015; Kipf & Welling, 2016) and message passing based GNNs (Li et al., 2015; Dai et al., 2016; Gilmer et al., 2017). The former generalizes the convolution operator from regular graphs (e.g., grids) ones with arbitrary topology, whereas the latter mimics message passing algorithms and parameterizes the shared functions via neural networks.
Saanhez-GGnzzllee et al., 2018; Wang et al., 2018), roboties (Casas
Due to the tremendous empirical success of GNNs, there is increasing interest in understanding their theoretical properties. For example, some recent works study their expressiveness (Maron al., 2018; Xu al., 2018; Chen al., 2019b), that is, what class of functions can be represented by GNNs. However, only few works investigate why GNNs generalize so well to unseen graphs They are either restricted to a specific model variant (Verma Zhang, 2019; Du et al., 2019; Garg et al., 2020) or have loose dependencies on graph statistics (Scarselli et al., 2018).
On the other hand, GNNs have close ties to standard feedforward neural networks, egg., multi-layer perceptrons (MLPs) and convolutional neural networks (CNNs). In particular, if each i.i.d. sample is viewed as a node, then the whole dataset becomes a graph without edges. Therefore, GNNs can be seen as generalizations of MLPs/CNNs since they model not only the regularities within a sample but also the dependencies among samples as defined in the graph. It is therefore natural to ask if we can generalize the recent advancements 2017: Neyshabur et al., 2017: Bartlett et al., 2017: Dziugaite & Roy, 2017; Arora et al., 2018; 2019) to GNNs, and how would graph structures affect the generalization bounds?
generalization bounds for MLPs/CNNs (Harvey et al.,

---

Published as a conference paper at ICLR 2021
In this paper, we answer the above questions by proving generalization bounds for the two primary classes of GNNs, i.e. graph convolutional networks (GCNs) (Kipf & Welling, 2016) and message- passing GNNs (MPGNNs) (Dai et al., 2016; Jin et al., 2018).
Our generalization bound for GCNs shows an intimate relationship with the bounds for MLPs/CNNs with ReLU activations (Neyshabur et al., 2017; Bartlett al., 2017). In particular, they share the same term, i.e,, the product of the spectral norms of the learned weights at each layer multiplied by factor that is additive across layers. The bound for GCNs has an additional multiplicative factor d(1-1//2 where d 1 is the maximum node degree and l is the network depth. Since MLPs/CNNs are special GNNs operating on graphs without edges (i.e., d- = 0), the bound for GCNs coincides with the ones for MLPs/CNN, with ReL.U activations (Neyshabur et al., 2017) on such degenerated graphs. Therefore, our result is a natural generalization the existing results for MLPPs/CNNs.
Our generalization bound for message passing GNNs reveals that the governing terms of the bound are similar to the ones of GCNs, i.e., the geometric series of the learned weights and the multiplica- tive factor d The geometric series appears due to the weight sharing across message passing steps, thus corresponding to the product term across layers in GCNs. The term d' encodes the key graph statistics. Our bound improves the dependency on the maximum node degree and the maximum hidden dimension compared to the recent Rademacher complexity based bound (Garg et al., 2020). Moreover, we compute the bound values on four real-world graph datasets (e.g., social networks and protein structures) and verify that our bounds are tighter.
In terms of the proof techniques, our analysis follows the PAC-Bayes framework in the seminal work of (Neyshabur et al., 2017) for MLPs/CNNs with ReLU activations. However, we make two distinctive contributions which are customized for GNNs. First, a naive adaptation of the pertur- bation analysis in (Neyshabur et al., 2017) does not work for GNNs since ReLU is not I-Lipschitz under the spectral norm, i.e., [|ReLU(X]]l I ||x||2 does not hold for some real matrix X. Instead, construct the recursion on certain node representations of GNNs like the one with maximum l2 norm, so that we can perform perturbation analysis with vector 2-norm. Second, in contrast to (Neyshabur al., 2017) which only handles the homogeneous networks, i.e., f(a)) (xx) when 2 O, we properly construct a quantity of the learned weights which 1) provides a way to satisfy the constraints of the previous perturbation analysis and 2) induces finite covering on the range of the quantity so that the BAC-Bayes bound holds for all possible weights. This generalizes the analysis to non-homogeneous GNNs like typical MPGNNs.
The rest of the paper is organized as follows. In Section 2, we introduce background material necessary for our analysis. We then present our generalization bounds and the comparison existing results in Section 3. We also provide an empirical study to support our theoretical arguments in Section 4. At last, we discuss the extensions, limitations and some open problems.
2 BACKGROUND
In this section, we first explain our analysis setup including notation and assumptions. We then describe the two representative GNN models in detail. Finally, we review the PAC-Bayes analysis.
2.1 ANALYSIS SETUP
In the following analysis, we consider the K-llass graph classification problem which is common in the GNN literature, where given a graph sample 2, we would like to classify it into one of the predefined K classes. We will discuss extensions to other problems like graph regression in Section 5. Each graph sample is triplet of an adjacency matrix A, node features X E x and output label y E | i.e. z = (A, X, y). where n is the number of nodes and ho is the input feature dimension. We start our discussion by defining our notations. Let NŽ be the first l positive integers, 1pp the vector p-norm and || I| the operator norm induced by the vector p-norm. Further, || || denotes the Frobenius norm of matrix, e the base of the natural logarithm function log, Alt.Ji the (th element of matrix A and A the i-th row. We use parenthesis to avoid the ambiguity, e.g., (i.)). means the (i,j)-th element of the product matrix AB. We then introduce some terminologies from statistical learning theory and define the sample space as Z, (A, X,y) y) E 2 where X E X' (node feature space) and A E g (graph space), data distribution
i..,, No = 2,, 2,.., k).
1pp
2

---

Published as a conference paper at ICLR 2021
D. 2 sid D. hypothesis (or model) fw where fw E H. (hypothesis class), and training set S with size m, S {z1, 2m ). We make the following assumptions which also appear in the literature:
A1 Data, i.e., triplets (A, x)),, are i.i.d. samples drawn from some unknown distribution D.
A2 The maximum hidden dimension across all layers is h.
A3 Node feature of any graph is contained in 22-ball with radius B. Specifically, have Vi E Nr. the i-th node feature [ύ,
=] E X {a | شزر 2z B²).
A4 We only consider simple graphs (i.e., undirected, no loops' and multi-edges) with max- imum node degree as d 1.
Note that it is straightforward to estimate and d empirically on real-world graph data.
2.2 GRAPH NEURAL NETWORKS (GNNs)
In this part, we describe the details of the GNN models and the loss function we used for the graph classification problem. The essential idea of GNNs is propagate information the graph so that the learned representations capture the dependencies among nodes/edges. We now review two classes of GNNs, GCNs and MPGNNs, which have different mechanisms for propagating informa- tion. We choose them since they are the most popular variants and represent two common types of neural networks, i.e.. feedforward (GCNs) and recurrent (MPGNNs) neural networks. We discuss the extension of our analysis to other GNN variants in Section 5. For case of notation, we define the TR where w is the vectorization of all model parameters.
model be fw E : X
Graph convolutional networks (GCNs) (Kipf & Welling, 2016) for the K-elass graph clas- sification problem can be defined as follows,
GCNs:
H On [.H&-IWa.
(k-tth Graph Convolution Layer)
H1 =
(Readout Layer),
(I)
where & E N 1. H2 Raxh, are the node representations/statess, 1,, R xm is all-one vector, / the number of layers.? and W, is the weight matrix of the j-th layer. The initial node state the observed node feature Ho X. For both GCNs and MPGNNs, we consider 7 1 since otherwise the model degenerates to a linear transformation which does not leverage the graph and is trivial analyze. Due to assumption A2, W, of size at most h h, i.e., ha I h, vk N The graph Laplacian L is defined as, À = I + A, L D AD where D is the degree matrix of A. Note that the maximum eigenvalue of L is in this case. We absorb the bias into the weight the node feature. Typically, GCNs use ReLU as the non-linearity, ie., a. (x) ma æ), Vi = 1.... . - 1. We use the common mean-readout to obtain the graph representation where H E Baxhi- Wi E RA--IX and Hi E RIXX
by appending constant
MPGNNs: There are multiple variants of message passing GNNs, egg., (Li et al., 2015; Dai al., 2016: Gilmer et al., 2017), which share the same algorithmic framework but instantiate few com- ponents differently, e.g., the node state update function. We choose the same class of models as in (Garg et al., 2020) which are popular in the literature (Dai et al., 2016; Jin et al., 2018) in order to fairly compare bounds. This MPGNN model can be written in matrix forms as follows,
M₁ = ((CTHHR-)
(k-th step Message Computation)
M₁ = Mn
(k-th step Message Aggregation)
H₂ = á (XW1 + p (Ma) W2)
(k-tth step Node State Update)
H1 = - n2
-1,,,,
(Readout Layer),
(2)
'erre loop means an edge that connects a vertex to itself, a.k.a., self-loop.
We count the readout function layer he consistent with the existing analysis of ML.Ps/CNNs.
3

---

Published as a conference paper at ICLR 2021
where & E Ni_1. H& Rnxha are node representatioons/tates and H1 R R is the output representation. Here we initialize Ho- O. W.l.o.g., we assume Vk N H3 R and MR E Raxh since h is the maximum hidden dimension. Cin E R and Cout E Raxe (c is the number of edges) respectively, Specifically, rows and columns of Cin and Cout correspond to nodes and edges respec- tively. Cm = indicates that the incoming node of the j-th edge the i-th node. Similarly, Coutli. [ = indicates that the outgoing node of the j-th edge is the i-th node. 9. G. P are non- linear mappings, e.g., ReLU and Tanh. Technically speaking, 9 R + RA, Φ R - R², and p: IR - A operate on vector-state of individual node/edge. However, since we share these func- tions across nodes/edges, we can naturally generalize them to matrix-states, e.g., é Raxh - IRaxh where (i)) | ((X(i,))) :]). By doing so, the same function could be applied to matrices with varying size the first dimension. For simplicity, we use 9, Φ, P to denote such generalization to matrices. We denote the Lipschitz constants of g, o, p under the vector 2-norm as C. Co. Cp respec- tively. We also assume g(0) = O, 6(0) = O, and p(0) = 0 and define the percolation complexity as C CyC&C 22/l ll2 following (Garg et al., 2020).
the incidence matrices corresponding to incoming and outgoing nodes'
Multiclass Margin Loss: We use the multi-class y-margin loss following (Bartlett et al., 2017; Neyshabur al., 2017). The generalization error is defined as,
LD.
Pe 2nD [xu(X, 5 max fw A))ii
(3)
where y > and (X, A) is the 1-th layer representations, i.e, Hi fw, A). Accordingly, we can define the empirical error as,
(sn( = -1'
11( [m A)lu S max So A)(i)
(x((,))(j) jFy
(4)
ZIES
2.3 BACKGROUND OF PAC-BAYES ANALYSIS
PAC-Bayes (McAllester, 1999; 2003; Langford & Slawe-Taylor 2003) takes a Bayesian view of the probably approximately correct (PAC) learning theory (Valiant, 1984). In particular, it assumes that we have a prior distribution P over the hypothesis class H and obtain posterior distribution Q over the same support through the learning process on the training set. Therefore, instead of having deterministic model/hypothesis as in common learning formulations, we have distribution of models. Under this Bayesian view, we define the generalization error and the empirical error as,
Ls (Q) (l
(Q, Em
Since many interesting models like neural networks are deterministic and the exact form of the posterior Q induced by the learning process and the prior is typically unknown, it is unclear how one can perform PAC-Bayes analysis. Fortunately, we exploit the following result from the PAC-Bayes theory.
Theorem 2.1. (McAllester, 2003) (Two-sided) Let P be a prior distribution over H. and let ô e (0, 1). Then, with probability - 5 over the choice of an i.i.d. size-m training set S according to D, for all distributions Q over and any y > O, we have
(0, + /
In 2m 8
2(m
Here DKL is the KL-divergence. The nice thing about this result that the inequality holds for all possible prior P and posterior Q distributions. Hence, we have the freedom to construct specific priors and posteriors so that we can work out the bound. Moreover, McAllester (2003); Neyshabur et al. (2017) provide general recipe to construct the posterior such that for a large class of models, including deterministic ones, the PAC-Bayes bound can be computed. Taking a neural network as an example, can choose prior distribution with some known density, e,g., fixed Gaussian,
For undirected graphs, we convert each edge into directed edges.
4

---

Published as a conference paper at ICLR 2021
over the initial weights. After the learning process, weights from another known distribution as long as the KL-divergence permits an analytical form. This converts the deterministic model into a distribution of models while still obtaining tractable KI. divergence. Leveraging Theorem 2.1 and the above recipe, Neyshabur et al. (2017) obtained the following result which holds for large class of deterministic models.
add random perturbations to the learned
Lemma 2.2. (Neyshabur al., 2017)* Let [w)(:) X RR be any model with parameters w, and let P be any distribution on the parameters that is independent of the training data. For any w, we construct posterior Q(w + u) by adding any random perturbation
w, S.t., P(maxsex (f+t(()) (x)) < 2) > 2- Then, for any y, 5 > O, with probability at least 1 6 over an i..d size-m training set S according to D, for any w, we have:
22KI. + u) P) log 8m
LD,O(fu) LSn +
2(m - 1)
This lemma guarantees that, as long as the change of the output brought by the perturbations is small with large probability, one can obtain the corresponding generalization bound.
3 GENERALIZATION BOUNDS
In this section, present the main results: generalization bounds of GCNs and MPGNNs using PAC-Bayesian approach. We then relate them to existing generalization bounds of GNNs and draw connections to the bounds of MLPs/CNNs. We summarize the key ideas of the proof in the main text and defer the details to the appendix.
3.1 PAC-BAYES BOUNDS GCNS
As discussed above, in order to apply Lemma 2.2, we must ensure that the change of the output brought by the weight perturbations is small with large probability. the following lemma, we bound this change using the product of the spectral norms of learned weights at each layer and term depending on some statistics of the graph.
Lemma 3.1. (GCN Perturbation Bound) For any B 0,1 1, let fu E H: X x g l-layer GCN. Then for any w, and x XB. and any perturbation vi Nr. ||Ul|2 ||WWall2. the change in the output of GCN is bounded as,
vec({U.)) such that
Ullle W
Ifu+u (X, -) (x, A)l2
Iialle
The key idea of the proof is to decompose the change of the network output into two terms which depend on two quantities of GNNs respectively: the maximum change of node representations max; - =]
[i, and the maximum node representation max; H1 [i, :||2- Here the superscript prime denotes the perturbed model. These two terms can be bounded by an induction on the layer index. From this lemma, we can see that the most important graph statistic for the stability of GCNs is the maximum node degree, i.e., d - 1. Armed with Lemma 3.1 and Lemma 2.2, now present the PAC-Bayes generalization bound of GCNs as Theorem 3.2.
Theorem 3.2. (GCN Generalization Bound) For any B > 0, > 1, let fwr E H:: X x G - RRK be layer GCN. Then for any 6, " O, with probability least 1 - 8 over the choice an i.i.d. size-m training set S according to D. for any w, we have,
Bag 1 11h log(th) II 1 1 Σ ( + log
Lpp(Jw)) S (s)
2
"The constants slightly differ from the original paper since two-sided version of Theorem 2.1.
5

---

Published as a conference paper at ICLR 2021
Since it is easy to show GCNs are homogeneous, the proof of Theorem 3.2 follows the one for MLPs/CNNs with ReLU activations in (Neyshabur et al., 2017). In particular, we choose the prior distribution P and the perturbation distribution to be zero-mean Gaussians with the same diagonal variance a. 'he key steps of the proof are: 1) constructing a quantity of learned weights , = [T [Will)) 2) fixing any 3, considering all 3 that are in the range |3 33 31 S B/1l and choosing which depends on B so that one apply Lemma 3.1 and 2.2 obtain the PAC-Bayes bound; 3) taking a union bound of the result in the 2nd step by considering multiple choices of 3 so that all possible values of 3 (corresponding to all possible weight w) are covered. Although Lemma 2.2 and 3.1 have their own constraints on the random perturbation, above steps provide a way to set the variance a which satisfies these constraints and the independence w.r.t. learned weights. The latter important since a is also the variance of the prior P which should not depend on data.
3.2 PAC-BAYES BOUNDS OF MPGNNS
For MPGNNs, we again need to perform perturbation analysis to make sure that the change of the network output brought by the perturbations on weights is small with a large probability. Following the same strategy adopted in proving Lemma 3.1, we prove the following Lemma.
Lemma 3.3. (MPGNN Perturbation Bound) For any B > 0,1 > 1, let fu E H: X - RK be a 1-step MPGNN. Then for any w, and XB, ha and any perturbation u vec([U1. U2, Ui}) such
that 17 max
||0 [1aal22
[
S t. the change in the output of MPGNN is bounded as,
Will
Walla"
Will
(dC)'-1- -1
If fx( A)12 S eBin) Will///l
dc -
where C = CgC,C, 1
The proof again involves decomposing the change into two terms which depend on two quantities respectively: the maximum change of node representations max, [[[_][;::] Hi - [á,:11,
and the maximum node representation max, | 1ē. :112- Then we perform an induction on the layer index to obtain their bounds individually. Due to the weight sharing across steps, we have a form of geometric series ((dC)'-1 1)/ (dC 1) rather than the product of spectral norms of each layer as in GCNs. Technically speaking, the above lemma only works with dC & 1. We refer the reader to We now provide the generalization bound for MPGNNs.
the appendix for the special case of dC
Theorem 3.4. (MPGNN Generalization Bound) For any B > 0, 1, let fw H. X G - R be a I-step MPGNN. Then for any 8, > O, with probability at least 1 over the choice of an i.idd size-m training set S according D. for any w, have,
LD.olf)) S (f,)(())++ (V
1 (max (1-1+1), (2E) 2 h2h log(th) w/ + log " 5
m(l+1)
72m
where Ç min
min (1 Wille ll, 1/22,,2 (111))) |ue13 = ||W || C
A = |Will/|Will.. and E = C [dc) [dc)'-1-1
dc-1
The proof also contains three steps: 1) since MPGNNs are typically non-homogeneous, e.g., when any of é, p, and g is bounded non-linearity like Sigmoid Tanh, we design a special quantity of learned weights /3 max(ç-1, (Ag)=/t). 2) fixing any B, considering all that are in the range |B 18- - < B/(l + 1) and choosing a which depends on so that one can apply Lemma 3.3 and 2.2 to work out the PAC-Bayes bound; 3) taking a union bound of the previous result by considering multiple choices of 3 so that all possible values of 8 are covered. The case with dC = is again included in the appendix. The first step is non-trivial since we do not have the nice construction as in the homogeneous case, ie., normalizing the weights so that the spectral norms of weights across layers are the same while the network output is unchanged. Moreover, the quantity vital to the whole proof framework since it determines whether one can 1) satisfy the constraints on the random perturbation (so that Lemma 2.2 and 3.3 are applicable) and 2) simultaneously induce a finite covering its range (so that the bound holds for any w). Since it highly depends on the form of the perturbation bound and the network architecture, there seems to be no general recipe on how to construct such quantity.

---

Published as a conference paper at ICLR 2021
Max Node Degree
Max Hidden Dim
Spectral Norm of Leurned Weights
Statistics
d
h
VC-Dimension (Scarselli et al., 2018)
o (h*)
Rademacher Complexity (Garg et al., 2020)
(Ny/oog log
o (AC5 Sogyyoo (Wall2>22)) o (x
Ours
(d'
o (Vhlogh)
/l 1 Walls Wills
Table I: Comparison of generalization bounds for GNNs, s." means inapplicable. is the network Co (dc)'='-1
depth. Here C 1,C,,,,lWallee &
min (lIWi I|,, [|aall2 [Will2), and WWilla|Willl More details about the comparison can be found in Appendix A.5.
3.3
COMPARISON WITH OTHER BOUNDS
In this section, we compare our generalization bounds with the ones in the GNN literature and draw connections with existing MLPs/CNNs bounds.
3.3.1 COMPARISON WITH EXISTING GNN GENERALIZATION BOUNDS
We compare against the VC-dimension based bound in (Scarselli et al., 2018) and the most recent Rademacher complexity based bound in (Garg et al., 2020). Our results are not directly comparable to (Du et al., 2019) since they consider "infinite-wide class of GNNs constructed based on the neural tangent kernel (Jacot et al., 2018), whereas we focus on commonly-used GNNs. Comparisons to (Verma & Zhang, 2019) are also difficult since: 1) they only show the bound for one graph convolutional layer, i.., it does not depend on the network depth l; and 2) their bound scales as O (Amax/m) where T' the number of SGD steps and Amax is the maximum absolute eigenvalue of Laplacian T, D - A. Therefore, for certain graphs", the generalization gap is monotonically increasing with T, which cannot explain the generalization phenomenon. We compare different bounds by examining their dependency on three terms: the maximum node degree, the spectral norm of the learned weights, and the maximum hidden dimension. We summarize the overall comparison in Table and leave the details such as how we convert bounds into our context to Appendix A.5.
Max Node Degree 1d=1); The Rademacher complexity bound scales as (d' Vlo d2
whereas ours scales as (6 Many real-world graphs such as social networks tend to have large hubs (Barabási et al., 2016). which lead to very large node degrees. Thus, our bound would be significantly better in these scenarios. It is noteworthy that if one further introduces some as- sumption, e.g., á is a squashing function like tanh as shown in (Garg et al., 2020), then one can improve the above exponential dependency on the network depth 7 for both Rademacher complexity and PPC-Bayes bounds.
Max Hidden Dimension h: Our bound scales as h(yhlogh) which is tighter than the Rademacher complexity bound O (hvlog h) and the VC-dimension bound O(h)).
Spectral Norm of Learned Weights: As shown in Table 1, we cannot compare the dependencies on the spectral norm learned weights without knowing the actual values of the learned weights. Therefore, we perform an empirical study in Section 4.
3.3.2 CONNECTIONS WITH EXISTING BOUNDS OF MLPS/CNNS
As described above, MLPs/CNNs be viewed special cases of GNNs. In particular, have two ways to show the inclusion relationship. First, we can treat each i.i.d. sample as a node and the whole dataset node-level tasks (e.g., node classification) on this graph. Second, we can treat each i.i.d. sample as single-node graph. Then conventional tasks (e.g., classification) becomes graph-level tasks (e.g., graph classification). Since we focus on the graph classification, we adopt the second view. In
graph without edges. Then conventional tasks (e.g., classification) become
$ SSince Amax = ma (D - A)u)/(e T u). we have Amax 2 (D A)(i, i] by choosing v = Eis iec.
the i-th standard basis. We can pick any node which has more than 1 neighbor to make Amax 1.
"Our bound actually scales O (2(++1(22)/(1 which is upper bounded by O (d'-1).
7

---

Published as a conference paper at ICLR 2021
20.0
PAC Bayes
40
PAC Bayes
Rademacher
Rademacher
17.5
35
Log Bound Value
Log Bound valus
30
25
10.0
20
7.5
15
5.0
10
2.5
5
0.0
PROTEINS
IMDB-M
IMDB-B
COLLAB
PROTEINS
IMDB-M
IMDB-B
COLLAB
(a) MPGNNs with = 2.
(b) MPGNNs with 4.
Figure 1: Bound evaluations on real-world datasets. The maximum node degrees (i.e., d d- 1) of four datasets from left right are: 25 (PROTEINS), 88 (IMDB-M), 135 (IMDB-B). and 491 (COLLAB).
particular, MLPs/CNNs with ReLU activations equivalent to GCNs with the graph Laplacian L = I (hence d 1). We leave the details of this conversion to Appendix A.6. We restate the PAC-Bayes bound for MLPs/CNNs with ReLU activations in (Neyshabur et al., 2017) as follows,
(BrPhooog II W. Σ (I (1w.B/// + log
ml
LD.o(fu) S (f.
/
8
Comparing it with our bound for GCNs in Theorem 3.2, it is clear that we only add factor d' to the first term inside the square root which is due to the underlying graph structure of the data. If we apply GCNs to single-node graphs, the two bounds coincide since d = 1. Therefore, our Theorem 3.2 directly generalizes the result in (Neyshabur et al., 2017) to GCNs, which a strictly larger class of models than MLPs/CNNs with ReLU activations.
4 EXPERIMENTS
In this section, we perform empirical comparison between our bound and the Rademacher com- plexity bound for MPGNNs. We experiment on synthetic datasets of random graphs (correspond- ing to random graph models), social network datasets (COLLAB, IMDB-BINARY IMDB- MULTI), and a bioinformatics dataset PROTEINS from (Yanardag & Vishwanathan, 2015). In particular, create synthetic datasets by generating random graphs from the Erdós-Rént model and the stochastic block model with different settings (i.e., number of blocks and edge probabili- ties). All datesets focus on graph classifications. We repeat all experiments 3 times with different random initializations and report the means and the standard deviations. Constants are considered in the bound computation. More details of the experimental setup, dataset statistics, and the bound computation are provided in Appendix A.7.
As shown in Fig. and Fig. 2, our bound is mostly tighter than the Rademacher complexity bound with varying message passing steps I on both synthetic and real-world datasets. Generally, the larger the maximum node degree is, the more our bound improves' over the Rademacher complexity bound (cf.., PROTEINS vs. COLLAB). This could be attributed to the better dependency d of our bound. For graphs with large node degrees (e.g., social networks like Twitter have influential users with lots of followers). the gap could be more significant. Moreover, with the number of steps/layers increasing, our bound also improves more in most cases. It may not be clear to read from the figures since the y-axis is in the log domain and its range differ from figure to figure. We also provide the numerical values the bound evaluations in the appendix for an exact comparison. The number of steps is chosen be no larger than 10 GNNs steps/layers (Kipf & Welling, 2016; Jin et al., 2018). We found dC > 1 and the geometric series ((dC)--1-1) (dC-1) > all datasets which imply learned GNNs not contraction mappings (i.e.. dc < 1). This also explains why both bounds becomes larger with more steps. At last, we can see that bound values are much larger than 1 which indicates both bounds are still vacuous, similarly to the cases for regular neural networks in (Bartlett et al., 2017; Neyshabur et al., 2017).
generally shown to perform well with just few
Note that it may not be obvious from the figure as the y axis is in log domain. Please refer to the appendix where the actual bound values are listed in the table.
8

---

Published as a conference paper at ICLR 2021
35
PAC
PAC
20.0
Rademacher
Rademacher
30
17.5
Log Bound Value
Log Bound Value
25
20
10.0
15
7.5
10
5.0
2.5
0.0
ER-1
ER-2
ER-3
ER-4
SBM-1
SBM-2
ER-1
ER-2
ER-3
ER-4
SBM-1
SBM-2
(a) MPGNNs with / 2.
(b) MPGNNs with 4.
50
PAC Bayes
PAC Bayes
Rademacher
Rademacher
Log Bound Value
Log Bound Value
20
10
ER-1
ER-2
ER-3
ER-4
SBM-1
SBM-2
ER-1
ER-2
ER-3
ER-4
SBM-1
SBM-2
(c) MPGNNs with / 6.
(d) MPGNNs with 8.
Figure 2: Bound evaluations synthetic datasets. The maximum node degrees (iee. 1) of datasets from left to right are: 25 (ER-1), 48 (ER-2), 69 (ER-3), 87 (ER-4), 25 (SBM-1), and 36 (SBM-2). 'ER-X' and 'SBM-X' denote the Erdös-Rényi model and the stochastic block model with the 'X'tth setting respectively. Please refer to the appendix for more details.
DISCUSSION
In this paper, we present generalization bounds for two primary classes GNNs, i.e., GCNs and MPGNNs. We show that the maximum node degree and the spectral norms of learned weights govern the bound for both models. Our results for GCNs generalize the bounds for MLPs/CNNs (Neyshabur et al., 2017), while our results for MPGNNs improve over the state-of-the-arr Rademacher complexity bound in (Garg et al., 2020). Our PAC-Bayes analysis can be general- ized to other graph problems such as node classification and link prediction since our perturbation analysis bounds the maximum change of any node representation. Other loss functions (e.g., ones for regression) could also work our analysis as long as they are bounded.
However, we are far from being able to explain the practical behaviors of GNNs. Our bound values are still vacuous as shown the experiments. Our perturbation analysis in the worst-case sense which may be loose for most cases. We introduce Gaussian posterior in the PAC-Bayes framework to obtain an analytical form of the KL divergence. Nevertheless, the actual posterior induced by prior and the learning process may likely to be non Gaussian. We also do not explicitly consider the optimization algorithm in the analysis which clearly has an impact on the learned weights.
This work leads to few interesting open problems for future work: (1) Is the maximum node degree the only graph statistic that has an impact on the generalization ability of GNNs? Investigating other graph statistics may provide of novel models and algorithms.
insights the behavior of GNNs and inspire the development (2) Would the analysis still work for other interesting GNN ar- chitectures, such as those with attention (Veličković al., 2017) and learnable spectral filters (Liao et al., 2019)? (3) Can recent advancements for MLPs/CNNs, e.g., the compression technique in (Arora et al., 2018) and data-dependent prior of (Parrado- Hernández al., 2012), help further im- prove the bounds for GNNs? (4) What is the impact of the optimization algorithms like SGD on the generalization ability of GNNs? Would graph structures play role in the analysis optimization?

---

Published as a conference paper at ICLR 2021
REFERENCES
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via a compression approach. arXiv preprint / 2018.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. arXiv preprint arXiv:/901.08884 2019.
Albert-Láázzóó Barabási al. Network science. Cambridge university press, 2016.
Peter L Bartlett, Dylan Foster, and Matus Telgarsky. Spectrally margin bounds for neural networks. In NIPS, pp. 6240-6249, 000.6629,22011 2017.
Peter Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-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 1806. 2018.
Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Piere Vandergheynst. Geomet- ric deep learning: going beyond euclidean data. IEEE Signal Processing Magazine, 34(4):18 2017.
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. arXiv preprint arXiv: 13/2: 2203, 2013.
Sergio Casas, Cole Gulino, Renjie Liao, and Raquel Urtasun. Spatially-aware graph neural networks relational behavior forecasting from sensor data. arXiv preprint arXiv: 00.08333, 2019.
Guangyong Chen, Pengfei Chen, Chang- Yu Hsieh, Chee-Kong Lee, Benben Liao, Renjie Liao, Weiwen Liu, Jiezhong Qiu, Qiming Sun, Jie Tang, al. Alchemy: A quantum chemistry dataset for benchmarking ai models. arXiv preprint
09427,, 2019a.
Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph iso- morphism testing and function approximation with gnns. In NeurlPS, pp. 15894-15902, 2019 bb.
Hanjun Dai, Bo Dai, and Le Song. Discriminative embeddings of latent variable models for struc- tured data. In International conference on machine learning, pp. 2702-2711, 2016.
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. In NeurIPS, pp. 5723-573333 2019.
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzia and Ryan P Adams. Convolutional networks graphs for learning molecular fingerprints. In NIPS, pp. 2224-223,, 2015.
Gintare Karolina Dziugaite and Daniel M Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. arXiv preprint arXiv:1703.11008 2017.
Vikas K Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. arXiv preprint arXiv:2002.061555 2020.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George Dahl. Neural message passing for quantum chemistry. arXiv preprint arXiv: 1704.0121.... 2017.
Marco Gori, Gabriele Monfardini, and Franco Scarselli. new model for learning in graph domains. In Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005., volume 2, pp. 729-734. IEEE, 2005.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NIPS, pp. 1024-1034, 2017.
10

---

Published as a conference paper at ICLR 2021
Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight vc-dimension bounds for piece- wise linear neural networks. In Conference on Learning Theory, pp. 1064-1068, 2017.
Isaac Henrion, Johann Brehmer, Joan Bruna, Kyunghyun Cho, Kyle Cranmer, Gilles Louppe, and Gaspar Rochette. Neural message passing for jet physics. NIPS Workshop on Deep Learning for Physical Sciences, 2017.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and gen- eralization in neural networks. In NeurlPS, pp. 8571 -8580, 2018.
Wengong Jin, Kevin Yang, Regina Barzilay, and Tommi Jaakkola. Learning multimodal graph-to- graph translation for molecular optimization. arXiv preprint arXiv: /1/x./:///2.000000 2018.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint arXivv 2016.
John Langford and John Shawe-Taylor. Pac-bayes & margins. In NIPS, pp. 439 436,446, 2003.
Yujia Li, Daniel Tarlow, Mare Broekschmidt, and Richard Zemel. Gated graph sequence neural networks. arXiv preprint arXi:: 2015.
Ming Liang, Bin Yang, Rui Hu, Yun Chen, Renjie Liao, Song Feng, and Raquel Urtasun. Learning lane graph representations for motion forecasting. In ECCV, 2020.
Renjie Liao, Zhizhen Zhao, Raquel Urtasun, and Richard Zemel. graph convolutional networks. In ICLR, 2019.
Lanczosnet:
Multi-scale deep
Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. arXiv preprint arXiv: 18X2,019112 2018.
David McAllester. Simplified pac-bayesian margin bounds. In Learning theory and Kernel ma- chines, pp. 203-215. Springer, 2003.
David A McAllester. Pac-bayesian model averaging. In Proceedings of the twelfth annual confer- ence on Computational learning theory, pp. 164-170, 1999.
Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M Bronstein. Geometric deep learning on graphs and manifolds using mixture model cnns. In CVPR, pp. 5115-5124, 2017.
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A pac-bayesian approach to spectrally-normalizedd margin bounds for neural networks. arXiv preprint 177:5:1707.09564, 2017.
Emilio
Amiran Ambroladze, John Shawe-Taylor, and Shiliang Sun. Pac-bayes bounds with data dependent priors. The Journal of Machine Learning Research, 13(1):3507- 3531,2014 2012.
Xiaojuan Qi, Renjie Liao, Jiaya Jia, Sanja Fidler, and Raquel Urtasun. 3d graph neural networks for rgbd semantic segmentation. In ICCV, 2017.
Alvaro Sanchez-Gonzalez, Nicolas Heess, Jost Tobias Springenberg. Josh Merel, Martin Riedmiller, Raia Hadsell, and Peter Battaglia. Graph networks as learnable physics engines for inference and control. arXiv preprint arXiv: 1806.080000000 02200.0222....... 2018
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions Neural Networks. 20(1) 2008
Franco Scarselli, Ah Chung Tsoi, and Markus Hagenbuchner. The vapnik-chervonenkis dimension of graph and recursive neural networks. Neural Networks, 108:248-259, 2018.
Joel Tropp. (isendfr tail bounds for sums of random matrices. Foundations of computational mathematics, 12(4):389 434, 2012.
Leslie G Valiant. A theory of the learnable. Communications of the ACM, 27(1 11: 134-11441 142, 1984.

---

Published as a conference paper at ICLR 2021
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv:/710.10003, 2017.
Saurabh Verma and Zhi-Li Zhang. Stability and generalization of graph convolutional neural net- works. In KDD, pp. 1539-1548, 2019.
Tingwu Wang, Renjie Liao, Jimmy Ba, and Sanja Fidler. Nervenet: Learning structured policy with graph neural networks. In ICLR, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovee and Stefanic Jegelka. How powerful graph neural networks? arXiv preprint 1rXiv:1810.00826, 2018.
Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In KDD, pp. 1365-1374, 2015.
12


Reviews:
[{"review_id": "o_xgnWjtSX6", "reviewer": "AnonReviewer3", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper, by PAC-Bayesian approach, proves the generalization bounds for the two primary classes of graph neural networks—graph convolutional networks and message passing GNNs. By experiments on four datasets, it shows that the generalization bound in this paper is tighter than the existing Rademacher complexity bound. \n\nThis is an interesting question about generalization bound, especially, such a discussion by  PAC-bayesian approach for graph neural networks is lacking. However, there are a few issues/comments with the work:\n\n1.The proof techniques in this paper are mainly from Neyshabur et al., 2017. The theoretical contribution and novelty are limited;\n\n2.For the generalization bounds, they are exponential dependence on depth. So for $d>1$, it means that the deeper it is, the worse it is for the graphical neural network. Is that so?\n\n3.It will be better to use more empirical experiments  to verify the relationship between the generalization bounds, node degrees, and depth;\n\n4.For Assumption 4 in this paper, it assumes that “no loop”, for the practical application of graph neural networks, loop generally exists. This will limit the potential application of this theory. in this paper;\n\n5.According to the theory established in this paper and the # graphs and max # nodes of the datasets provided in APPENDIX, PROTEINS and IMDB-BINARY should have more similar log bound value than IMDB-BINARY and MDB-MULTI. In Figure 1, it seems to be the opposite, why? Is it because the feature dimension also plays an important role in the log bound value? \n\n6.The format of mathematical equations is inconsistent, for example, equation (1) without punctuation,  but equation (3) with punctuation.\n\nOverall, I think this is an interesting piece of work that might interest researchers to explore the  questions around graph neural networks. However, I think the results need to be analyzed more carefully, especially on the depth. Moreover, the novelty of the technology is relatively limited.", "extra_scores": {}, "extra_text": {}}, {"review_id": "jLvKR85QTD", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors propose generalization bounds for GNNs, both convolutional and standard message passing variants. The result is a generalization of those for CNN/MLP architectures with relu activation functions. The analysis method closely follows those established in the former settings as well. The specific setting they consider is where each sample in the dataset is a graph. The proof relies on ensuring small perturbations in the GNN weights don't cause large deviations in output distributions. The resulting PAC-Bayes bound is shown to be tighter than corresponding Rademacher Complexity bounds. \n\nThe paper is well written and the results look reasonable (though I didn't check the proofs). A couple of minor comments/questions:\n\n1. Does assumption A4 cause things to be a lot looser than needed? Consider a star graph, then d ~ number of nodes in the graph. But this is just for one node. \n\n2. How would things change if your data is actually not iid ~ D, but the entire dataset is the graph (so you just have one graph), and you need to classify the nodes? I'm guessing there's parts in the proof where the iid assumption is necessary. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "ODoOHfashBE", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "# Summary\n\nThe paper presents PAC-Bayesian generalization bounds for two classes of graph neural networks: graph convolutional neural networks and message passing graph neural networks. The paper essentially adapts Neyshabur et al. (2017) PAC-Bayesian margin bounds for neural networks to graph neural networks and expectedly the bounds contain terms that depend on the degree of the underlying graph. The main technical contribution of the paper is a perturbation bound for GNNs from which the main results follow. \n\n# Strengths\n\n1. The paper presents the first PAC-Bayesian generalization bound for GNNs and the authors show that their bounds are tighter than the Rademacher based generalization bounds developed by Garg et al (2020) ignoring constants.\n\n# Weakness\n\n1. The bounds do not necessarily give important insights into generalization performance of GNNs. Bounds are still vacuous: bounds become exponentially large with number of layers and degree.\n2. For a theory paper that purely focuses on obtaining generalization bounds for GNNs, the technical contributions are weak. The only technical contribution is the derivation of perturbation bounds for GNNs which are pretty easy to obtain. If this is not the case, then this needs to be highlighted.\n3. It is not sufficient to compare bounds on real world data at some fixed sample size for empirical comparison with Rademacher based bounds, especially given that constants are dropped. Synthetic experiments with varying samples, graph families (e.g. Erdos Renyi graphs) and different degree distribution are needed to show how the bounds compare against Rademacher based bounds.\n\n# Justification for rating\n\nThe generalization bounds themselves provide very limited insights into generalization performance of GNNs especially given recent results that show that uniform convergence bounds may not be able to explain generalization of deep neural networks. While this is an issue with existing theoretical results for deep neural networks, the paper does not significantly improve the state-of-the-art in theoretical understanding of GNNs in terms of new tools and proof techniques. For a theory paper that purely focuses on generalization bounds, this is a significant shortcoming.\n\n# Other comments\n\n1. Misleading use of the word \"statistics\" throughout the paper. Statistics are quantities that can be computed only from the data. The paper repeatedly refers to functionals of parameters as \"statistics\".\n2. What do you mean by: \"actual posterior distribution induced by learning process may be very different from Gaussians\" ? PAC-Bayesian analysis is done for Gibbs classifiers and Neyshabur et al. provide a way to convert these convergence bounds for deterministic classifiers. The learning process does not induce a posterior distribution over weights (assuming deterministic initialization and removing randomness like dropout).\n3. D is overloaded to denote both data distribution and diagonal degree matrix.", "extra_scores": {}, "extra_text": {}}, {"review_id": "G8xFKZN3M", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##########################################################################\nSummary:\nThis paper provides results of generalization bounds for two types of GNNs: GCN and MPGNN. The presented analysis follows the framework of Neyshabur 2017 to construct posterior by adding random perturbations so that the PAC-Bayesian technique can be applied. The main contributions are the perturbation analysis for GCN and MPGNN, which results in a bound depending on the graph statistics. The paper compares the derived bounds with existing results, and examines the bounds numerically through experiments.  \n\n##########################################################################\nI find the paper well-written and overall technically sound. I vote for accept.\n##########################################################################\n\nStrength:\n\nThis paper studies an important problem, as GNNs are popular learning models.\n\nWhile the overall idea follows directly from Neyshabur 2017, the presented perturbation analysis is not trivial, making the current work a good advance.\n\nThis paper is well-organized, with nice discussions on the state-of-the-art as well as on the overall technical review. It is appreciated that the paper is self-contained, and the preliminary results are provided in the appendix (though they can be found in earlier papers).\n\nThe paper provides a detailed comparison between the derived bounds with the existing bounds. The results of this paper are natural in the sense they generalize that the results in Neyshabur 2017 for MLPs.\n\n\nSome concerns:\n\nFor the proofs of Theorem 3.2 and 3.4, I would suggest decomposing it into several lemmas, by first identifying the covering (and the weight-independent variance) and then plugging the values into Lemma 3.3 (and Lemma 3.1) and further into Lemma 2.2\n\nTo avoid ambiguity, using D_KL(u+w||P) is better than D_KL(Q||P) in this paper.\n\nGiven the heavy notations, having a notation table in the appendix could be very helpful.\n\nWhat are the key difficulties in applying the proposed framework to other GNN architectures? \n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper gives a new PAC-Bayesian generalization error bound for graph neural networks (GCN and MPGNN). The bound improves the previously known Rademacher complexity based bound given by Garg et al. (2020). In particular, its dependency on the maximum node degree and the maximum hidden dimension is improved.

This paper gives an interesting improvement on the generalization analysis of GNNs. The writing is clear, where its connection to existing work and its technical contribution are well discussed. 
The biggest concern is its technical novelty. Indeed, the proof follows the out-line of Neyshabur et al. (2017). Given that the technical novelty would be a bit limited, however, the analysis should properly deal with the complicated structure specific to GNNs which makes the analysis more difficult than usual CNN/MLP and requires subtle and careful manipulations. 
In addition to that, the improvement of the generalization bound is valuable for the literature (while the improvement seems a bit minor for graphs with small maximum degree). 

For these reasons, I recommend acceptance for this paper.
Decision: Accept (Poster)