Learning Theory Can (Sometimes) Explain Generalisation in Graph Neural Networks
Authors: Pascal Esser
Leena Chennuru Vankadara
Debarghya Ghoshdastidar
Venue: NeurIPS 2021 Poster (2021)
Keywords: Learning Theory
Generalisation
Graph Neural Networks
Transductive Learning
Rademacher Complexity

Abstract: In recent years, several results in the supervised learning setting suggested that classical statistical learning-theoretic measures, such as VC dimension, do not adequately explain the performance of deep learning models which prompted a slew of work in the infinite-width and iteration regimes. However, there is little theoretical explanation for the success of neural networks beyond the supervised setting. In this paper we argue that, under some distributional assumptions, classical learning-theoretic measures can sufficiently explain generalization for graph neural networks in the transductive setting. In particular, we provide a rigorous analysis of the performance of neural networks in the context of transductive inference, specifically by analysing the generalisation properties of graph convolutional networks for the problem of node classification. While VC-dimension does result in trivial generalisation error bounds in this setting as well, we show that transductive Rademacher complexity can explain the generalisation properties of graph convolutional networks for stochastic block models. We further use the generalisation error bounds based on transductive Rademacher complexity to demonstrate the role of graph convolutions and network architectures in achieving smaller generalisation error and provide insights into when the graph structure can help in learning. The findings of this paper could re-new the interest in studying generalisation in neural networks in terms of learning-theoretic measures, albeit in specific problems.

Learning Theory Can (Sometimes) Explain Generalisation in Graph Neural Networks
Pascal Mattia Esser Technical University of Munich
Leena C. Vankadara University of Tübingen
esser dum.de
leena. chenmurr--annkddarrauuu-
Debarghya Ghoshdastidar Technical University of Munich Munich Data Science Institute
ghoshdas@in, tum. de
Abstract
In recent years, several results in the supervised learning setting suggested that classical statistical learning-theorete measures, such VC dimension, do adequately explain the performance of deep learning models which prompted a slew of work in the infinite-width and iteration regimes. However, there is little theoretical explanation for the success of neural networks beyond the supervised setting. this paper we argue that, under some distributional assumptions, classical learning-theen theoreticeicc measures can sufficiently explain generalization for graph neural networks in the transductive setting. In particular, we provide a rigorous analysis of the performance of neural networks in the context of transductive inference, specifically by analysing the generalisation properties of graph convolutional net- works for the problem of node classification. While VC Dimension does result in trivial generalisation error bounds in this setting as well, we show that transductive Rademacher complexity explain the generalisation properties of graph convolu- tional networks for stochastic block models. We further use the generalisation error bounds based on transductive Rademacher complexity to demonstrate the role of graph convolutions and network architectures in achieving smaller generalisation error and provide insights into when the graph structure findings of this paper could re-new the interest in studying generalisation in neural networks in terms of learning- -thorrettt measures, albeit in specific problems.
help in learning. The
Introduction
Neural networks have found tremendous success in wide range of practical applications and, in the broader society, it is often considered synonymous to machine learning. The rapid gain in popularity has, however, come at the cost of interpretability and reliability of complex neural network architectures. Hence, there has been an increasing interest understanding generalization and other theoretical properties of neural networks in the theoretical machine learning community (Feldman 2020 Arora et al. [019a] Ma et al. 2017; Nagarajan et al. 2019; Theisen et al. 20200 Ghorbani et al. 2020 Most of the existing theory literature focuses the supervised learning problem, more precisely, the setting of inductive inference. In contrast, there is a general lack of understanding of transductive problems, in particular the role of unlabeled data in training. Consequently there has also been little progress in rigorously understanding one of widely used tools for transductive inference- Graph neural networks (GNN).
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Graph neural networks. GNNs were introduced by Gori et al. (2005) and Scarselli et al. (2009). who used recurrent neural network architectures, for the purpose of transductive inference on graphs. that is, the task of labelling all the nodes of a graph given the graph structure, all node features and labels for few nodes. Broadly, GNNs use a combination of local aggregation of node features and non-linear transformations to predict on unlabelled nodes. In practice, the exact form of aggregation and combination steps varies across architectures to solve domain specific tasks (Kipf et al. 2017 Bruna et al. 2014) Defferrard et al. 2016; Veličković et al. 2018 Xu et al. 2019). While some GNNs focus on the transductive setting, sometimes referred to as semi-supervised node classification! ! GNNs have also found success in supervised learning, where the task is to label entire graphs, in contrast to labelling nodes in a graph. While the understanding of GNNs is limited, there are empirical approaches to study GNNs in the transductive (Bojchevski et al. 2018)) and supervised setting (Zhang et al. 2018 Ying et al. 2018). For an extensive survey on the state of the art of GNNs see for example Wu et al. (2020).
Leaning theoretical analysis of GNNs. While empirical studies provide some insights into the behaviour of machine learning models, rigorous theoretical analysis is the key to deep insights into a model. The focus of this paper is to provide a learning-theoreti analysis of generalisation of GNNs in the transductive setting. Vapnik first studied the problem of transductive inference and provided generalisation bounds for empirical risk minimization (Vapnik 1982; Vapnik 1998). Subsequent works further analysed this setting in transductive regression (Cortes al. 2007). and derive VC Dimension and Rademacher complexity for transductive classification (Tolstikhin et al. 2016; E1- Yaniv et al. 2009). Generalisation eπror bounds for 1-layer GNNs have been derived in transductive setting based on algorithmic stability (Verma et al. 2019). In contrast, the focus of the current paper is on leariin-thhoortic measures, which have been previously used to analyse GNNs in a supervised setting. In Scarselli et al. (2018). VC Dimension is derived for a specific class of GNNs and generalisation error bound is given using node representations. However, their approach of subsuming the graph convolutions under Pfaffian functions does not allow for an explicit representation in terms of the diffusion operator which is important our presented analysis. Garg et al. (2020) derives the Rademacher complexity for GNN in a supervised setting with the focus of the equivariant structures of the input graphs and does not allow for an explicit inclusion and analysis of the graph information. Liao et al. (2021) provides PAC-Bayes bounds for GNNs that are tighter than the bounds in Garg et al. (2020).
In the context of this work, especially relevant is Oono et al. (2020b) and Oono et al. (020a).. Oono et al. (2020a) describes the effect of oversmoothing with increasing number of layers. A more detailed comparison to our work is presented in section 2.3 Oono et al. (2020b) analyzes GNNs in the transductive setting. However, they consider a multiscale GCN, and therefore, the analysis is based in a weak-learning/boosiin
framework where the focus is mostly on exploring the weak learning component, whereas this paper focuses on the specific analysis of the generalization bound and the influence of it's individual components. In addition, we provide a detailed analysis of its dependence on the graph and feature information and provide a more expressive bound by considering generalization under planted models.
Infinite limit analysis. In the broader deep learning, there has been a growing call for alternatives to standard learning-theone theoretic bounds since they do not adequately capture the behaviour of deep models (Neyshabur et al. (017)) To this end, different limiting case analysis have been introduced. In the context of GNNs, it is known that GNNs have a fundamental connection to belief propagation and message passing (Dai al. 2016: Gilmer et al. (017) and some theoretical analyses of GNNs have been based on cavity methods and mean field approaches for supervised (Zhou et al. 2020) and transductive settings (Kawamoto et al. 2019 Chen et al. 2019). The central idea of these approaches is to show results in the limit of the number of iterations. In another limiting setting, Du et al. (2019) study GNNs with infintiely wide hidden layers, and derive corresponding neural tangent kernel (Jacot et al. 2018, Arora et al. 2019b) that can provide generalisation error bounds in the supervised setting. Keriven et al. (2020) derive continuous versions of GNNs applied to large random graphs. While limiting assumptions allow for theoretical analysis, it is difficult to infer the implications of these results for finite GNNs.
In semi superviuee learning, the learner is given training set of labeled and unlabeled examples and the goal is to generate a hypothesis that generates predictions on the unseen examples. In transductive learning all features are available to the learner, and the goal is to transfer knowledge from the labeled to the unlabeled data points. The focus of graph- based semi- supervised learning aligns more with the latter setting.

---

Contributions and paper structure. We reconsider classical learning-theoretic theoretic measures to analyse GNNs, with a specific focus on explicitly characterising the influence the graph information and the network architecture on generalisation. In the process, we show that, under careful construction of the complexity measure and distributional assumptions on the graph data, learning theory can provide insights into the behaviour of GNNs. The main contributions are the following:
1) We introduce a formal setup for graph-based transductive inference, and in Section 2.2 we use this framework to show that VC Dimension based generalisation error bounds are typically loose, except for few trivial cases. This observation is along the lines of existing evidence for neural networks.
2) In Section 2.3 we derive generalization bounds based on the transductive Rademacher complexity, Our results show that these bounds are more informative, suggesting that the correct choice of complexity measure is important.
3) We further refine the generalisation error bounds in Section 3 Junder planted model for the graph and features. Such an analysis, under random graphs, is rare in GNN literature. We empirically show that the test error is consistent with the trends predicted by the theoretical bound. Our results suggest that, under distributional assumptions, learning-theoretic bounds can explain behaviour of GNNs.
4) In addition, we consider GNNs with residual connections in Section 4 and demonstrate how the above analysis can be extended to other network architectures. We prove that residual connections have smaller generalisation gap in comparison with vanilla GNN, and also empirically show that the theoretical bounds explain (to a limited extent) the influence of network depth on performance.
We conclude in Section 5 All proofs and an overview of the notation are provided in the appendix.
2 Statistical Framework for Transductive Learning on GNN
For rigorous analysis, we introduce statistical learning framework for graph based transduc- tive inference in Section 2.1 Based on this, we derive generalisation error bounds based on VC Dimension in Section 2.2 and demonstrate that the bounds have limited expresitivity even under strong assumptions. To overcome this problem we consider transductive Rademacher complexity in Section 2.3 While without further assumptions this bound also gives limited insight, the bound is more expressive and, in Section we show that it can provide meaningful bounds under certain distributional assumptions.
2.1 Framework for Transductive Learning
We briefly recall the framework for supervised binary classification. Let X' = R2d be the domain or feature space and y = { be the label set. The goal is to find a predictor h X + y based on m training samples S é {(,,, ys) ))) X' x y and a loss function E: y x 3 - 00, oc). In a statistical framework, assume that S consists independent labelled samples from distribution D = Dx n, that is, x; ~ Dx and y: n)xx)), where ny(-) governs the label probability for each feature. The goal of learning is to find / that minimises the risk / generalisation error LD - (( (((((())) y)]. Since, Co (h) cannot be computed without the knowledge of D. one minimises the empirical risk over the training sample S as (h) A m Em (h (x:)).y))
Transductive learning. In transductive inference, one restricts the domain to be X' {xx Hr a finite set of features o, E TRd.. Without loss of generality, one may assume that the labels .i..... V/m {+1} are known, and the goal is predict ym+11...2 Yn- The problem can be reformulated in the statistical learning framework as follows. We define the feature distribution Dx to be uniform over the n features, whereas y; Tπ(æ;) for some unknown distribution 7). Hence D: = (n)) x is the joint distribution on X' x Y, and the goal is to find a predictor h : X' + y Dmmm- (h((:)) ys). In addition we define the empirical error of h to be Z. (h) 1 E (h(rr), y:) and the full sample error of h to be ET_ É (h(x;), vi). which is defined over both labelled and unlabelled instances. The purpose of this paper is to derive generalisation error bound for graph based transduction of the form
that minimises the generalisation error f., (h) A
& (h)
(h( S Lm (h) + complexity term
3

---

The complexity term is typically characterised using learning -theorritt terms such as VC Dimension and Rademacher complexity. For the transductive setting see Tolstikhin al. (2016), Yania et al. (2009). and Tolstikhin et al. (2014).
Graph-based transductive learning. A typical view of graph information in transductive inference is as a form of a regularisation (Belkin et al. 2004). In contrast, we view the graph as part of the hypothesis class and derive the impact of the graph information on the complexity term. We assume access to a graph G with n vertices, corresponding to the respective feature vectors ....... En. and edge (i.j) denoting similarity of vertices i and j. For ease of exposition, we define the matrix X E R with rows being the feature vectors of dimension d. We also abuse notation write a predictor as h : R + [+1]". Furthermore, typically neural networks output a soft predictor in IR, that is further transformed into labels through sign or softmax functions. Hence, much of our analysis focuses on predictors h Rxd - IR", and corresponding hypothesis class
Hig { Rxd + +F" h is parametrized by 9} C R!").
When applicable, we denote the hypothesis class of binary predictors obtained through sign function as sign oHg = (sign(h) h E Hgg. Note that sign o'gg C Hgg and hence, VC Dimension or Rademacher complexity bounds for the latter also hold for the hypothesis class of binary predictors. We also note that the presented analysis holds for both sign and sigmoid function for binarisation.
Formal setup of GNNs. We next characterise the hypothesis class for graph neural networks. Consider graph-based neural network model with the propagation rule for layer l denoted by 9u. (H) : Rd - Rd with layer wise input matrix H E R Consider a class of GNNs defined over K layers, with dimension of layer & [K] being dę and S E R=x= the graph diffusion operator. Let & denote the point-wise activation function of the network, which we assume to be Lipschitz function with Lipschitz constant LG. We assume @ to be the same throughout the network. We define the hypothesis class over all K K-layer GNNs as:
HS a hgg x = 9K o
Raxd + {+1]"}
(1)
with 9k - (bx S (H) Wh), & E [K], 9u A
where 2 defines the layer wise transformation with We E Rda-1xds as the trainable weight matrix and by dd the bias term. Here, the graph is treated part of the hypothesis class, as indicated by the subscript in Hg. For ease of notation we drop the superscript for non-linearity where it is unambiguous. For the diffusion operator S, we consider two main formulations during discussions:
Shop A +1
self loop
nor
(D+T) (A+1((+D)
degree normalized (Kipf et al. 2017)
where A denotes the graph adjacency matrix and D is the degree matrix. However, most results are stated for general S.
2.2 Generalisation Error-bound using VC Dimension
The main focus of this paper is the notion of generalisation, that is, understanding how well GNN can predict the classes of an unlabelled set given the training data. We start with one of the most fundamental Garning-theoreticn
concepts in this context which is the Vapnik-Chervonenkiss (VC) dimension of a hypothesis class, a measure of the complexity or expressive power of a space of functions learned by binary classification algorithm. The following result bounds the VC Dimension for the hypothesis class Hg. and use it to derive a generalisation error bound with respect to the full sample error L., which is close to the generalisation error for unlabelled examples L. when m <
Proposition 1 (Generalisation error bound for GNNs using VC Dimension) For the hypothesis class over all linear GNNs, that is Φ(x) := x. with binary outputs, the VC Dimension is given by
VCdim sign o HH = min { rank
min kE[K-1]
{dp} }.
Similarly, the VC Dimension for the hypothesis class of GNNs with ReLU non-linearities and binary outputs, can be bounded as VCdim sign ReUL I min (rank(S), dk-1).
4

---

Using the above bounds, it follows that, for any 8 E (0, 1), the generalisation error for any h sign o'g satisfies, with probability 1.
8 min (rank(S), In((m)) In ( )
4
(h) Lm. (h) v
To interpret Proposition 1 we note that, by introducing the non-linearity we lose the information about the hidden layers, except the last one and therefore also on the feature dimension. Nevertheless, the information are two situations that arise. dx-1 S vank(S), then, from Proposition [ the graph information is redundant and one could essentially train a fully connected network without diffusion on the labelled features, and use to predict on unlabelled features. The graph information has an influence for rank(S) < dx-1- While general statements the influence of the graph information are difficult, by considering specific assumptions on the graph we can characterise the generalisation error further.
the graph information (that we are primarily interested in) is preserved. There
For linear GNN graph G, one can bound the VC Dimension between those for empty and com- plete graphs, that is, VCdim sign (ompleee)) S VCdim (sign g S &VCdim (iign o o' Moreover, for disconnected graphs, rank(S) is related to the number connected components. Similar observations hold for upper bounds VC Dimension for ReLU GNNs. Based on this observation for simple settings, holds that considering graph information in comparison to a fully connected feed forward neural network leads to decrease in the complexity of the class, and there- fore also in the generalisation error. However, the graph 9 is connected in most practical scenarios, and even under strong assumptions the graph, for example under consideration of Erdös-Rényi graphs or stochastic block models, rank S) = (n) (Costello et al. 2008). Therefore, for the case
122 which holds trivially for 0-1 loss as n > m. Furthermore, rank(S) (S) often similar for both self-loop Shoop and degrec-normalised diffusion S and hence, the VC Dimension based error bound does not reflect the positive influence of degree n fact that can be explained through stability based analysis (Verma et al. 2019).
dx-1 > rank(S) = On)), Proposition provides a generalisation error bound of O
2.3 Generalisation Error-bound using Transductive Rademacher Complexity
Due to the triviality of VC Dimension based enror bounds, consider generalization error bounds based on transductive Rademacher complexity (TRC). We start by defining TRC that differs from inductive Rademacher complexity by taking the unobserved instances into consideration.
Definition (Transductive Rademacher complexity (El-Yaniv al. 2009)) Let V C
[0, 0.3] and m the number of labeled points. Let o (oI...., )n)) be vector of independent and identically distributed random variables, where d; takes value +1 or 11, each with probability 2p. The transductive Rademucher complexity (TRC) V is defined as
and O with probability
(1 m
1
Rm, (V) 2
E
sup o LVEV
The following result derives bound for the TRC of GNNs, defined in (-2 and states the corresponding generalization error bound. The bound involves standard matrix norms, such as || lloe (maximum absolute row sum) and the 'entrywise' norm, 11 (maximum 2-norm of any column).
Theorem (Generalization error bound for GNNs using TRC) Consider H C H such
that the trainable parameters satisfy ||bılll < 3 and [|Walloo S w for every k E [K]. The transductive Rademacher complexity (TRC) of the restricted hypothesis class bounded
cnn?
Ā-1
Rm,n (HL
Σ k=D
c3ch
||S|
|XX
2-000 Vlog(n). (4)
m(n
m))
where C1 - 2L 0a A 2Low, C3 Low / 2/d and Lo is Lipschitz constant for activation d.
5

---

The bound on TRC leads to generalisation error bound following El- EI-Yaniv et al. (2009). For any
5 E (0, 1), the generalisation error for any h E "HO'. satisfies
(h( - (m)) S Rm (Hg) nV mi/m m, n m)
n
In 1
+ V m(n m)
(5)
m(n m)
with probability 8, where ca, cs are absolute constants such that e4 < 5.05 and C5 < 0.8.
The additional terms in (5) are O (max vn-m and hence, we may focus on the upper bound on TRC to understand the influence of the graph diffusion S as well as its interaction with the feature matrix X. The bound depends on the choice of w, and it suggests natural choice of w = 011/1 a() such that the bound does not grow exponentially with network depth. The subsequent discussions focus on the dependence on |S and ||S 122-00 ignoring the role of w. Few observations are evident from 4. which are also interesting in comparison to existing works.
Role of normalisation. In the case of self-loop. it is easy to see that ||Stoopleec = - dmax. where dmax denotes the maximum degree, and hence, for fixed w. the bound grows as O(d In contrast, for degree normalisation, |/ O
(v daus
duin and hence, the growth is much smaller (in fact, ||Suor| = 1 on regular graphs). It is worth noting that, in the supervised setting, Liao et al. (2021) derived PAC-Bayes for GNN with diffusion Suar, where the bound varies as (dd Theorem is tighter in the sense that, for Spor: the error bound has weaker dependence on dmax. mainly through ||S||| ||XX|22-00
12+00* From spectral radius to ||SX] | Previous analyses GNNs transductive setting rely on the spectral properties of S. For instance, the stability based generalisation error bound for 1-layer GNN in Verma et al. (2019) is O(ISS)
where ||S||| 22 is the spectral norm. In contrast, Theorem | shows TRC = [[ S o0 [X]] || 200) This is the first result that explicitly uses the relation between the graph-information and the feature information explicitly via 15XIl22- One may note that without node features, that is X = I, we have | < S S ||S| and hence, direct comparison between (5) and [[ S bound of Verma et al. (2019) is inconclusive. However, in presence of features X. Theorem shows that the bound depends on the alignment between the feature and graph information.
In the presence of graph information we can still express Theorem T in terms of spectral components by considering ||SX|] 12-ro0 = max, (SX) )اار < max, ||S] X,ll I
|||||||| X| Il2 22000 and
||X || 12-00 which can be bound as vx | I |S||2-
Oversmoothing. While the above bound provides a weaker result than 4 it allows to directly connect to the oversmoothing (Li et al. 2018) effect as the diffusion operator in now only included as || k E [K] Therefore with an increasing number of layers (and especially in the setting considered in Oono et al. (2020a) where the number of layers goes to infinity), the information provided by the graph gets oversmoothed and therefore, a loss of information can be observed.
3 Generalization using TRC under Planted Models
The discussion in previous section shows that TRC based generalisation error bound provides some insights into the behaviour of GNNs (example, Sncr is preferred over Stoop). but the bound is too general to give insights into the influence of the graph information on the generalisation error. The 11
key quantity of interest is | - which characterises how the graph and feature information interact. To understand this interaction, we make specific distributional assumptions on both graph and node features. We assume that node features are sampled from a mixture of two d-dimensional isotropic Gaussians (Dasguptal 1999), and graph is independently generated from two-community stochastic block model (Abbe 2018). Both models have been extensively studied in the context of recovering the latent classes from random observations of features matrix X or adjacency matrix A, respectively. Our interest, however, is to quantitatively analyse the influence of graph information when the latent classes in features X and graph do not align completely. In Section 3.1 we present the model and derive bounds on expected TRC, where the expectation is with respect to random features and graph. We then experimentally illustrate the bounds in Section 3.2 and demonstrate that the corresponding generalisation error bounds indeed capture the trends in performance of GNN.

---

3.1 Model and Bounds on TRC
We assume that the node features are sampled latent true classes, given z (21...., 2n) E {=1}". The node features are sampled from a Gaussian mixture model (GMM), that is, feature for node-i is sampled as 2; N22jt IfI) for some μ R and E (0, co). We express this in terms of as
X = X Randd where x== ===11 zjz and (cg))e(t)JeEL) 1edd (0,
(6)
We refer above as X 2GMM. On the other hand, we assume that graph has latent communities, characterised by y E [=1]". The graph is generated from a stochastic block model with two classes (2SBM), where edges (i,j) are added independently with probability p E (0, 1] Y Vy, and with probability < [0.p) if ys & y,, In other words. we define the random adjacency A 2SBM as a symmetric binary matrix with A;; 0, and (A.))cc indenpendent such that
Aij ~ Bernoulli(A..),
where A = P q 11
P-q 2
yy pI.
The choice of two different latent classes 2, y E {=1}" allows study of the case where the graph and feature information of do not align completely. We use I' ly 00= [0, nl] to quantity this alignment.
Assuming y, z are both balanced, that is, Ex V4 = E; 24 = 0, one can verify that
[I(A + 12 = M1 (n(1 - p)2 2 + =n(p -2 - (p- (1 ()(1)))(1pp)))))p))) p))
(8)
which indicates that, for dense graphs (p. > !),, the quantity || 11 should typically increase if the latent structure of graph and features are more aligned. This intuition is made precise in the following result that bounds the TRC, in expectation, assuming X 2GMM and A 2SBM.
Theorem 2 (Expected TRC for GNNs under SBM) Let C1, C2 and es defined in Theorem 7 and
é Ty 2). Let c. & (1 + o(1)), e7 _ (1 ko(1)) Cs & (1 + Ko(1)). Assuming p. q >
we can bound the expected TRC for A as defined in 7 and X defined in (6) as follows:
Case I, Degree normalized:
Snor
E X- XM2GGM A-28BM
Rmm (H
<
cin2
K-1 Σ
C70
P
+ 0sc
p
Vnn(n) x
m(n 12 ml)
k=
1
(2-
r
In(n)
a 2ln(d))
cs 1lellloo
C6
Mell + co1
(9)
p+g
g
2
Case 2, Self Loop: S Stoop
K Σ crcs(np) k=0
EE X-2GMM A A-2SBM
Rm.n (Hgg <
cnni
+ (occac((mpp" VIn(m) x
m(n m)
2
ca IlAllloo n2
111+
1+
P- 2
r2
+
p p+0 V
|1 + can / 2nn(d)
(10)
2
We note that although the above bounds are stated in expectation, they can be translated into high probability bounds. Furthermore the non- -riviiiialtty of the proof of Theorem 2 stems from bounds on the expectations of matrix norms, which is more complex than the computation in (8). Theorem
be also translated into bounds on the generalisation gap C. (h) 2. (h). By considering a planted model we can now further extend the observations of Section 2.2 and 2.3
Role of normalisation. In the following, we can show that by normalising, the generalisation gap grows slower with increasing graph size. First we compare E || li = c>(np)* with
[[|S ] = Cr (p//)*/2 k/2 and observe that by normalising we lose the n term. addition we can consider [||SX] ooo which is bound by the second line in 9 ( Again in the first, deterministic, term we observe that the self loop version contains an additional dependency on n. For the two noise terms can characterize the behaviour in terms of the density of the graph. Let
7

---

Feature / Adjacency matrix Alligrment
Graph size
Observed Points
0.30
Gondraltaatin
0.30
0.25
0.6
VC
TRC
0.15
0.20
0.10
1000
1500
2000
0.01
0.02
0.05
F/n
m/n
2.5
calcralttton Eroor
2.0
1.5
1.5
Emgincall max
Empircial
90% quanttlc
0.00
0.02
0.04
1750
20000
2250
2500
2750
0.1
0.16 0.21
Figure Top row shows experiments for SBM and bottom row for Cora. (left) Change in the alignment of the features and adjacency matrix. (middle) Change of the graph size n. (right) Change number observed points m.
= O(), and > 1 then we can characterise the dense setting as p x (1(1) and the sparse setting as = In(n) and observe that in both case the normalised case grows slower with n:
Dense:
E
S loop
2000 = (m))
and IE Smee X 2 01 ((vIn(n))
(11)
Sparse:
E
Stop
[1 Ol =0(nnn(()) and TE [1 2- (vn
(12)
Influence of the graph information. We consider the idea from Section 2.2 to analyse the influence of graph information by comparing the TRC between the case where graph information is consid- ered, S I and Sace- We define the corresponding hypothesis classes H,0,8.. and H. Con-
sidering the deterministic case (S = S, X = X) we can observe Rm, (Hl (H Rm,, n (H))
if 0 Vaptn Therefore the random graph setting allows us to more precisely characterize under what conditions adding graph information helps.
3.2 Experimental Results
While we focus on the theoretical analysis of GNNs, in this section we illustrate that the empirical generalization error follows the trends given by the bounds described in Theorem 2 The bounds in Section 3.1 are derived for binary SBMs so we therefore focus on this setting but in addition also show that those observations extend real world, multi-class data on the example of the Cora dataset (Rossi et al. 2015). The results are presented in Figure [ For the SBM we consider graph with 500, m 100 as default. We plot the mean over random initialisation and over several epochs. Note that the range for Cora exceeds (0. 1) as the dataset is multi class and we consider a negative log likelihood loss. For plotting the theoretical bound we can only plot the trend of the bound as the absolute value is out of the (0. )) range. While this does not allow us to numerically show how tight the bound is in practice, we can still make statements about the influence of the change of parameters, where the experiments validate the constancy between theory and empirical observations Details on the experimental setup are given in the Appendix.
We can first look at the feature and graph alignment as characterised through 1 in the TRC based bound g 9 and observe that with an increase in the latent structure the generalisation error
"Generalisation enror bounds, even for simple machine learning models, can exceed 1 due to absolute constants that cannot be precisely estimated. Hence, the point of interest the dependence of key parameters; for instance, in supervised setting, the bounds are ( /m) and typically exceeds for moderate m. This problem is inherent to the bound given El- Yaniv et al. (2009) that we base our TRC bounds on, as the slack terms can already exceeds 1 and therefore further research general TRC generalisation gaps is necessary to characterise the absolute gap between theory and experiments.

---

increases. While this seems to be counterintuitive possible explanation could be that reduced aligmment helps to prevent overfitting and we observe that the slope matches the empirical results. In addition we note that the VC dimension bound (3) does not allow us to model this dependency. For Cora we do not have access to the ground truth for the alignment and therefore can not verify this trend directly. Therefore we simulate change in the feature structure by adding noise to the feature vector as X + where eg. is i.i.d. distributed N (0, teall) and again observe a similar behaviour to the SBM. To be able to apply the bound to arbitrary graphs an important property is that the bound does not increase drastically with growing graph size. We theoretically showed this the previous section, especially through [I] 12) and illustrate it in Figure [I (middle). Empirically for both, SBM and Cora, the generalisation error stays mostly consistent over varying n. Finally for the number of observed points consider a realistic setting of < m where we see sharp decline in the setting of few observed points but then the generalisation error converges which corresponds to the influence of as described in (9). Practically such observation be useful as labeling data can be expensive and such results could be useful to determine a necessary and sufficient number of labeled data to obtain given level of accuracy.
4 Influence of Depth and Residual Connections on the Generalisation Error
While for standard neural networks increasing the depth is a common approach for increasing the performance, this idea becomes more complex in the context of GNNs as each layer contains left multiplication of the diffusion operator and we can therefore observe an over-smoothing effect (Li al. (2018) the repeated multiplication of the diffusion operator in each layer spreads the feature information such that it converges to be constant over all nodes. To overcome this problem, empirical works suggest the use of residual connections (Kipf et al. 2017 Chen 2020), such that by adding connections from previous layers the network retains some feature information. In this section we investigate this approach the TRC setting. In Section 4.] we provide the TRC bound for GNN with skip connections and show that it improves the generalisation error compared to vanilla GNNs. In Section 4.2 we illustrate this bounds empirically.
4.1
Model and bounds on TRC for GNN with Residual connections
While there is a wide range of residual connections, introduced in recent years we follow the idea presented in Chen et al. (2020) where a GNN defined in (2) is extended by an interpolation over parameter a with the features. This setup is especially interesting as it captures the idea of preserving the influence of the feature information more than residual definition that only connect to the previous layer. Formally we can now write the layer wise propagation rule as
gk+1 & ((1 a) (by + Sgs (H) W&) + agu (H)),
with a E (0,
(13)
We can now derive generalization error bound similar to Theorem foor the Residual network.
Theorem (TRC for Residual GNNs) Consider a Residual network as defined in (13) and Hig H....a C Hg such that the trainable parameters satisfy [lball, S B and [ I w for ev- ery k [K]. Then with E (0, 1) and eı & 2T e2 - 2T C3 A Law / 2/d the TRC of the restricted class or Residual GNNs is bounded as
((1 - (11-a)a + a2L m(n m)
X 1oo )n
K-1
Rm,
(HQ Rm.n(Ho.8
<
Σ k=0
(1- a) |
+ a2 || |X| + (1 Dogech
||S||
|
|| 2 Vlog(n)
(14)
However observing the bound isolated does not provide new insights beyond Theorem into the behaviour of the generalisation error and therefore we focus the comparison between GNNs with and without residual connections.
For readability assume 3 = || bo Under this setup we can note that the generalisation brund increases with decreased alpha and in extension follows that the generalisation error-bound for a GNN with skip connection is lower then the one without. This implication is in line with the general notion that residual connections improve the performance of networks (Chen et al. 2020, Kipf et al. 2017). Our general intuition behind this behavior is that with increasing a, the network architecture

---

Thelretical bound
SBM
Cora
(max)
(max)
Generalbaten Erorr
Res, am0.2
GMN (meen)
GNN (mean)
0.3
Bes, am2.5
dm0.2 (mwan)
0.2 (maa))
(max)
2.5
2.0
a-0.2 (max)
0-0 (neen)
(mean)
a=0.2 (mcan)
a-0.5 (max]
0.05
1.0
0.00
Figure 2: (left) Theoretical bounds corresponding to Theorem (middle) Influence of depth K under SBM. (right) Influence of depth K for Cora.
is closer to the one of an one hidden layer network. Having good performance in shallow networks is something that observed in our experiments well as previous work (e.g.. (Kipf al. (2017)) Therefore it appears that using the skip connection to obtain a deep network that resembles a shallow one leads the performance increase.
4.2 Experiments on depth and Residual networks
The above observation suggests that including residual connections is beneficial with increasing depth
which is consistent with the initial reason of introducing residual connections (Chen et al. 2020
Kipf
et al. 2017). We further illustrate this in the context of the trend in (14). Similar to Section
we
start by considering the vanilla GNN version and focus on the influence of depth where Figure (lett)
illustrates Theorem 2 more specifically an exponential increase of K as shown in 99) 10 (similar
to Liao al. p). Empirically from Figure 2 (middle, right) we note that with increasing depth
the generalisation error indeed increases for the first three layers significantly but then we observe
deviation from the theoretical bound. The rate of growth decreases, which is to be expected as the absolute values of Cu, C. are bound by construction. Future work with focus on depth is necessary to refine this component of the bound. Extending the analysis of depth we now consider the residual connections defined in B By 14 we can still observe the exponential dependency therefore focus on two main aspects: i) Theoretically the generalisation error for the Resnet is upper bound by GNN, which empirically is observed for both the SBM as well for Cora. ii) Focusing on the Resnets, Theorem predicts an ordering in the generalisation error given by a which is again observed for both the SBM as well as for Cora. Therefore while there seems to be deviation in the exponential behaviour of as given in Theorem 33 the ordering of the generalisation error-bound described by is observed empirically. While this does give us a complete picture we note that the remarks on oversmoothing suggest that shallower networks are preferable and we again note that the VC dimension bound (3) does not provide any useful insights to the influence of depth.
K and
Conclusion
Statistical learning theory has proven to be successful tool for complete and rigours analysis of learning algorithms. At the same time research suggests that applied to deep learning models these methods become non-informative. However on the example of GNNs, we demonstrate that classical statistical learning theory can be used under consideration of the right complexity measure and distributional assumptions the data provide insight into trends of deep models. Our analysis provides first fundamental results on the influence of different parameters on generalization and opens up different lines of follow up work. As noted the previous section the TRC bound predicts an exponential dependency on network depth K which can only partially be observed empirically and therefore study without relying on recursive proof structure will be necessary to refine this dependency on K. As it is not the focus of this paper we consider the bounds on the norms of trainable parameters, w, B, fixed. However loosening this assumption would allow us to analyse the behaviour of the generalisation error during training and under different optimization approaches. Considering the current setup we can also extend the theoretical analysis to more advanced architectures such as dropout or batch normalisation. Finally while our analysis focuses generalisation we suggest that the idea of analysing GNNs under planted models can be extended to other marming-theoretica. measures such as stability or model selection well as the supervised (graph-Classifictton setting.
10

---

Acknowledgement
This work has been supported by the German Research Foundation (Priority Program SPP-2298, project GH-257/2-1) and the Baden- Wüntemberg Stiftung (Eliteprogram for Postdocs project "Clus- tering large evolving networks").. The authors thank the International Max Planck Research School for Intelligent Systems (IMPRS-IS) for supporting Leena Chennuru Vankadara.

---

References
Abbe, Emmanuel (2018). "Community Detection and Stochastic Block Models: Recent Develop- ments". In: Journal of Machine Learning Research.
Arora, Sanjeev, Nadav Cohen, Noah Golowich, and Wei Hu (2019a). "A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks". In: International Conference on Learning Representations.
Arora, Sanjeev, Simon S. Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Ruosong Wang (2019b). "On Exact Computation with an Infinitely Wide Neural Net". In: Advances in Neural Information Processing Systems.
Belkin, Mikhail,, Irina Matveeva, and Partha Niyogi (2004). "Regularization and semi-supervised learning on large graphs". In: International Conference on Computational Learning Theory. Bojchevski, Aleksandar, Oleksandr Shchur, Daniel Zügner, and Stephan Günnemann (2018). "Net
GAN: Generating Graphs via Random Walks". In: International Conference on Machine Learning. Bruna, Joan, Wojciech Zaremba, Arthur Szlam, and Yann Lecun (2014). "Spectral networks and locally connected networks on graphs". In: International Conference on Learning Representations. Burges, Chris J.C. (1998). "A Tutorial on Support Vector Machines for Pattern Recognition", In: Chen, Ming, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li (2020). "Simple and Deep Graph Convolutional Networks". In: International Conference on Machine Learning.
Chen, Zhengdao, Joan Bruna, and Lisha Li (2019). "Suupervised community detection with line graph neural networks". In: International Conference on Learning Representations.
Cortes, Corinna and Mchryar Mohri (2007). "On Transductive Regression". In: Advances in Neural Information Processing Systems.
Costello, Kevin P. and Van H. Vu (2008). "The rank of random graphs". In: Random Structures & Algorithms.
Dai, Hanjun, Bo Dai, and Le Song (2016). "Discriminative Embeddings of Latent Variable Models for Structured Data". In: International Conference on Machine Learning. Dasgupta, Sanjoy (1999). "Learning mixtures of Gaussians". In: Annual Symposium on Foundations of Computer Science.
Defferarrd Michaäl, Xavier Bresson, and Pierre Vandergheynst (2016). "Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering". In: International Conference on Neural Information Processing Systems.
Du, Simon S. Kangcheng Hou, Russ R Salakhutdinov, Barnabas Poczos, Ruosong Wang, and Keyulu Fusing Graph Neural Networks with Graph Kernels". In: Advances Neural Information Processing Systems.
Xu (2019). "Graph Neural Tangent Kernel:
Yaniv, Ran and Dmitry Pechyony (2009). "Transductive Rademacher Complexity and its Applica- tions". In: Journal of Artificial Intelligence Research.
Feldman, Vitaly (2020). "Does Learning Require Memorization? A Short Tale about Long Tail". In: Annual ACM SIGACT Symposium on Theory of Computing.
Garg. Vikas, Stefanie Jegelka, and Tommi Jaakkola (2020). "Generalization and Representational Limits of Graph Neural Networks". In: International Conference on Machine Learning. Ghorbani, Behrooz, Song Mei, Theodor Misiakiewicz, and Andrea Montanari (2020). "When Do
Neural Networks Outperform Kernel Methods?" In: Advances in Neural Information Processing Systems.
Gilmer, Justin, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl (2017).
"Neural Message Passing for Quantum Chemistry". In: International Conference Machine Learning.
Gori, Maria Cristina, Gabriele Monfardini, and Franco Scarselli (2005). "A new model for learning in graph domains". In: IEEE International Joint Conference on Neural Networks.
Jacot, Arthur, Franck Gabriel, and Clement Hongler (). "Neural tangent kernel: Convergence and generalization in neural networks". In: Advances in neural information processing systems. Kawamoto, Tatsuro, Masashi Tsubaki, and Tomoyuki Obuchi (2019). "Mean-field theory of graph neural networks in graph partitioning". In: Journal of Statistical Mechanics: Theory and Experi- ment.
Keriven, Nicolas, Alberto Bietti, and Samuel Vaiter (2020). "Convergence and Stability of Graph Con- volutional Networks on Large Random Graphs". In: Advances in Neural Information Processing
Systems.
Kingma, Diederik and Jimmy Ba (2015). "Adam: A Method for Stochastic Optimization". In: International Conference on Learning Representations.
12

---

Kipf, Thomas N. and Max Welling (2017). "Semi-Supervisee" Classification with Graph Convolutional Networks". In: International Conference on Learning Representations.
Li, Qimai, Zhichao Han, and Xiao ming Wu (2018). Deeper Insights Into Graph Convolutional Networks for Semi-Supervised Learning.
Liao, Renjie, Raquel Urtasun, and Richard Zemel (2021). "A PAC-Bayesian Approach to Generaliza- tion Bounds for Graph Neural Networks". In: International Conference on Learning Representa- tions.
Ma, Siyuan and Mikhail Belkin (2017). "Diving into the shallows: a computational perspective on large-scale shallow learning.. In: Advances in Neural Information Processing Systems.
Nagarajan, Vaishnavh and J. Zico Kolter (2019). "Uniform convergence may be unable to explain generalization in deep learning". In: Advances in Neural Information Processing Systems. Neyshabur, Behnam, Srinadh Bhojanapalli, David Mcallester, and Nati Srebro (2017). "Exploring Generalization in Deep Learning". In: Advances in Neural Information Processing Systems.
Oono, Kenta and Taiji Suzuki (2020a). "Graph Neural Networks Exponentially Lose Expressive
Power for Node Classification". In: International Conference on Learning Representations. (2020b). "Optimization and Generalization Analysis of Transduction through Gradient Boosting and Application to Multi-scale Graph Neural Networks". In: Advances in Neural Information Processing Systems.
Rossi, Ryan A. and Nesreen K. Ahmed (2015). "The Network Data Repository with Interactive Graph Analytics and Visualization". In: AAAI Conference on Artificial Intelligence.
Scarselli. Franco, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini (2009). "The Graph Neural Network Model".. In: IEEE Transactions on Neural Networks. Scarselli, Franco, Ah Chung Tsoi, and Markus Hagenbuchner (2018). In: The Sapnik-Chervonenkee dimension of graph and recursive neural networks.
Shalev-Shwartz, Shai and Shai Ben-David (2014). Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press.
Theisen, Ryan, Jason M. Klusowski, and Michael W. Mahoney (2020). "Good linear classifiers are abundant in the interpolating regime". In: Computing Research Repository. Tolstikhin, Ilya, Gilles Blanchard, and Marius Kloft (2014). "Localized Complexities for Transductive Learning". In: Conference on Learning Theory.
Tolstikhin, Ilya O. and David Lopez- Paz (2016). "Minimax Lower Bounds for Realizable Transductive
Classification". In: ArXiv. Vol. 1602.03027,
Vapnik, V. N. and A. Ya. Chervonenkis (1971). "On the Uniform Convergence of Relative Frequencies
of Events to Their Probabilities". In: Theory of Probability & Its Applications. Vapnik, Vladimir (1982). "Estimation of Dependences Based on Empirical Data". In: Springer Series in Statistics.
Vapnik, V.N. (1998). "Statistical Learning Theory". In: A Wiley-Interscience publication. Veličković, Petar, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liō, and Yoshua Bengio (2018). "Graph Attention Networks". In: International Conference on Learning Represen- tations.
Verma, Saurabh and Zhi-Li Zhang (2019). "Stability and Generalization of Graph Convolutional
Neural Networks". In: Computing Research Repository.
Wu, Zonghan, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S Yu (2020).
" "A Comprehensive Survey on Graph Neural Networks". In: IEEE transactions on neural networks and learning systems.
Xu, Keyulu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka (2019). "How Powerful are Graph Neural Networks?" In: International Conference on Leurning Representations.
Ying, Rex, Jiaxuan You, Christopher Morris, Xiang Ren, William L. Hamilton, and Jure Leskovec (2018). "Hierarchical Graph Representation Learning with Differentiable Pooling". In: Advances in Neural Information Processing Systems.
Zhang, Muhan, Zhicheng Cui, Marion Neumann, and Yixin Chen (2018). "An End-to-Ene End Deep Learning Architecture for Graph Classificatiin". In: AAA/ Conference on Artificial Intelligence. Zhou, Pengfei, Tianyi Li, and Pan Zhang (2020). "Phase transitions and optimal algorithms for semisupervised classifications on graphs: From belief propagation to graph convolution network". In: Physical Review Research.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]] General setup provided Section 2.T All further assumptions are provided in the specific sections and theorems
(b) Did you include complete proofs of all theoretical results? [Yes] All proofs are provided in the supplementary material
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material or URL)? [No] But we the official GCN implementation of Kipf et al. (2017) (linked the supplemental material) for the GNN implementation and all experimental details provided in the
supplemental material.
(b) Did you specify all the training details (c.g., data splits, hyperparameters, how they were chosen)? [Yes] See supplemental material
(c) Did you report error bars (c.g.. with respect to the random seed after running experi- ments multiple times)? [Yes] Specifically for out type of experiments are interested in mean, max and quantifies and therefore report those quantities
(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, or cloud provider)? [No] Experiments intensive
computationally
4. If you are using existing assets (e.g., code, data, models) or curating/releusing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [No]
(c) Did you include any new assets either in the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "zBieWIt5_2u", "reviewer": "Reviewer_n6fM", "summary": "The problem addressed in this paper is an important area in theoretical understanding graph convolution networks. This paper discusses the transductive learning using the Rademacher complexity analysis with VC-dimensions and data dependent bounds. Further, the paper analyzes the special setting of the GCNII which is known to be robust against oversmoothing. Overall, a good paper, however, some of the interpretations of bounds are not clear, which require further clarifications.  ", "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": "The study of generalization bounds for GCN is an important problem which has been recently studied by several researchers. This paper further adds insights to the study of generalization bounds using tranductive Rademacher complexity, VC dimensions, and residual networks. \n\nThe study of transductvie Rademacher complexity for GCN has also been studied under restricted conditions in  Kenta Oono, and Taiji Suzuki: Optimization and Generalization Analysis of Transduction through Gradient Boosting and Application to Multi-scale Graph Neural Networks (NeurIPS 2020). This reference is missing in the paper. It would be helpful to have some insight into how the  bounds given in the above paper are related to the proposed work. \n\nIn general, the paper is written well. However, there are several typos. \nIt is very useful to have a notations section to introduce mathematical notations. Otherwise, it is difficult to follow notations without searching through the paper. \nIn line 684: Should dual be  \\| \\sigma S X\\|_1 ?\nLine 797: Line before the eq. 30, is it  s1?\nLine 840 d_m in ?\n\nOversmoothing is an important aspect of GCN model that has gained theoretical attention. This paper also addresses this problem with the setting of GCNII. It is not convincing to use depth of 4 to explain the effect of oversmoothing in figure 2. It would be more clear if larger depths are considered as in [Che+20] where they considered depth from 2,4,...,64.\nFurther, it is not clear about the interpretation of the effect of oversmoothing from the bounds for plain GCN or the GCNII [Che+20] setting since the theory and experiments disagree as depth increases. Can authors elaborate possible improvements to bounds that can be made to obtain better interpretation in oversmoothing? \n\nSpectral analysis has been employed to explain oversmoothing in Kenta Oono and Taiji Suzuki: Graph Neural Networks Exponentially Lose Expressive Power for Node Classification, ICLR2020. In their paper, it has been shown that as the number of layers increases higher orders of eigenvalues quickly decrease to zeros leading to information losses. Can the generalization bounds be expressed with spectral components (e.g. eigenvalues)?\n\nFinally, it is nice if the inductive setting can also be included in the paper. Is it possible to extend generalization bounds in the paper for the inductive setting?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Lack of usage of spectral analysis could be a limitation in interpretations of oversmoothing. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "vfGeFa8Gb5b", "reviewer": "Reviewer_d7vj", "summary": "This paper analyzed the generalization performance of GNNs based on statistical learning theory. First, this paper derived the VC dimension-based generalization error bounds. It showed that graph structures affected the upper bound of the generalization performance gap via the rank of the adjacency matrix (and its normalized version). This paper also argued that these gaps are vacuous for some random graphs. For a more precise evaluation, this paper next derived generalization error bounds based on the notion of Transductive Rademacher Complexity (TRC). The effect of the normalization of the adjacency matrix S on the generalization bounds is explained for the general and planted model case. Finally, this paper derived the generalization bounds based on TRC for GNNs with residual connections. It argued that residual connections reduced the generalization gap.", "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": "### Soundness (Do theorems and experiments answer research questions, assuming they are correct?)\n\n- [So1] The research question of this paper is to analyze the generalization performance of GNNs in a transductive problem setting (l.43) from the viewpoint of statistical learning theory. This paper claimed that although classical learning theory cannot explain the behavior of deep learning models for FNNs, while it can, to some extent, for GNNs. I think this paper certainly answers this question for the following reasons.\n  - [So1.1] This paper analyzed how the empirical generalization performance of GNNs behaves when we change several parameters such as miss alignment value of labels, graph size, and the number of observed points. This paper confirmed that the empirical generalization performance is consistent with theoretically derived generalization bounds.\n  - [So1.2] In addition, the generalization bounds explain the benefit of the normalization of adjacency matrices.\n- [So2] I have a question about the soundness of the experiment in Figure 1. The motivation for the TRC-based generalization bounds was that the VC-dimension-based bounds could be vacuous (l.179). However, in Figure 1, the theoretical bounds are outside (0, 1) (l.277). It raised the question of whether TRC bounds can truly also overcome the shortcomings of the VC-dimension-based bounds.\n\n### Correctness (Are derivation of theorems and experiments correct?)\n\n- [C1] I have questions about the correctness of Theorem 3 and Corollary 1 due to the lack of proof. In particular, I could not understand how I can derive Corollary 1. Since Theorem 3 derived only the \"upper bound\" of the generalization bound, it is unclear how we can compare generalization errors.\n\n### Novelty and Significance (Do the paper have novel points? If so, are they significant?)\n\n- [N1] The derivation is based on the theory of TRC in [EY09]. The central part of the proofs was to evaluate TRC. I would say that the proof did not have much technical novelty because it is a combination of characteristics of TRC. We can prove the characteristics similar to those of the usual Rademacher complexity.\n- [N2] In addition, since [Oono and Suzuki, 20] derived the TRC-based generalization bounds for GNNs\n- [N3] However, this paper differs from [Oono and Suzuki, 20] in the following three points. First, [Oono and Suzuki, 20] analyzed multi-scale GNNs, while the target of this paper was single-scale GNNs with possibly residual connections. Second, [Oono and Suzuki, 20] evaluated the SX norm but did not go further than that. On the contrary, this paper explained the effect of normalization by evaluating its order (eq. 10, 11). Third, this paper derived the dependence of generalization bound for the Planted model on the cluster-label miss-alignment ratio (Theorem 2). In addition, this paper verified the dependence experimentally. Considering these points, although these derivations are a combination of classical tools, I can recognize the significance of the results of this paper.\n\n[Oono and Suzuki, 20] https://proceedings.neurips.cc/paper/2020/hash/dab49080d80c724aad5ebf158d63df41-Abstract.html\n\n### Clarity (Is the paper clearly written?)\n\n- [Cl1] The organization of this paper is OK. I can understand this paper without much difficulty.\n\n\n### Other Comments\n\n- l.54: derive→derives\n- l.55: provide→provides\n- l.79: This paper wrote that the situation considered in Section 2.2 is a \"realistic case.\" However, I think it is somewhat difficult to say that the Erdos-Renyi graph and SBM are realistic. That being said, I agree with this paper in that being vacuous is a problem of the VC dimension-based bounds.\n- l.105 I have a question about the problem setting. When this paper described the transductive learning setting, it took over the notation from the supervised learning setting. Therefore, it looks to me at first sight that we i.i.d. draw $m$ points from $\\mathcal{D}_X = {\\rm Unif}[n]$. However, it is not true as we draw data points without replacement in a transductive setting. So, I would like to suggest to reconsider the description.\n- l.249: μ should be capitalized.\n- Figure 1: In the figure, 90% quantile is shown. Since the experiment was run 5 times, does it mean that 90 % quantile is in fact the second value from the top?\n- Figure 1 (Bottom center): In Cora, the sample size n is varied.\n- l.256: In the following we can show ... → In the following, we can show ...\n- l.258: loos → lose\n- l.261: I think the notation $\\rho=O(p), O(q)$ is not appropriate. Does it mean $\\rho=O(\\min(p, q))$ ?\n- l.285: vary → verify\n- l.299: Cite the over-smoothing effect, as it was coined by existing works e.g., [Li et al., AAAI2019].\n\n[Li et al., AAAI2019] https://aaai.org/ocs/index.php/AAAI/AAAI18/paper/view/16098\n\n\n### Post-rebuttal comments\n\nI thank the authors for answering my questions sincerely. The approach of this paper is classical as the main tool is the (transductive version of) Rademacher complexity. Therefore, the novelty is limited in that respect (cf. [N1] of my review comment.) Considering that, I keep my score. However, However, since I acknowledge the significance of the conclusions drawn from the analysis (cf. [N3] of my review comment), I will not oppose to accepting the paper.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "- [L1] This paper discussed the limitation of the analysis in terms of model architectures (e.g., not applicable to the models with dropout or batch normalization)\n", "review_text": "", "extra_scores": {"ethical_concerns": "N.A.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "Qxt_BiKzLMh", "reviewer": "Reviewer_16pJ", "summary": "The paper studies generalisation bounds of GNNs from the classical statistical learning point of view. Under some specific distribution assumptions, the authors show that, while VC Dimension does result in trivial generalisation error bounds,  transductive Rademacher complexity can explain the generalisation properties of graph convolutional networks for the specific case of stochastic block models. Experimental results on synthetic data generated from SBM graphs, and the CORA dataset quantify the validity of the bound. Finally, the influence of depth and residual connections is studied.  ", "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": "This is a very interesting and well-presented paper, with respect to different aspects. \n\nOriginality: Generalisation bounds of GNNs are definitely worth investigating, and it is a topic of great interest to the research community. The proposed approach is relevant and interesting. Specifically, the authors focus on transduction settings that have been largely underlooked in the literature. Studying Rademacher complexity seems to provide some insight on the generalisation properties, at least on stochastic block models.   \n\nQuality: The paper is of very good quality, and technically sound. Proofs are provided. Experimental results are informative. A more extensive evaluation on different type of graph models and well as different feature distribution would significantly increase the contribution. \n\nClarity: The paper is well written. Despite being a heavy and very technical paper, the authors did a good job in terms of the presentation of the results. A few comments are the following: \n\nTypos: \nLine 50: is on 'a' learning: remove 'a'\nLine 58: deep learning 'learning' repeated twice\nLine 112: to be instead of is\nLine 145: 'can' is repeated twice \nLine 198: it suggests instead of suggest \nFigure 1: first subfigure: alignment instead of allignment \nLine 256: loose instead of loos\nLine 294: remove a\nLine 311: more than \n\nExplain a bit definition 1. \nRemind what K is in the conclusions. \n\nSignificance: The obtain results are theoretically interesting and I expect them to generate more research in the topic. Although the current results are specific to some cases of graph models and feature distributions, they are definitely relevant and a useful step towards understanding theoretically GNNs. I would expect the authors to extend the bounds to terms that are related to the graph characteristics/distribution, as well as some more interpretable features. \n\nAfter rebuttal: \nThe authors should include a more extensive discussion about the existing literature (e.g.,Oono&Suzuki (2020)) and position their work with respect to that. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors clearly state the limitations of their framework in the conclusion part. One additional limitation is the extension to weighted graphs and more labels (not simply binary classification). ", "review_text": "", "extra_scores": {"ethical_concerns": "I do not see important ethical concerns with this paper. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "2_4VROTmdrT", "reviewer": "Reviewer_Mq8Q", "summary": "The aim of the paper is to provide generalization bounds for graph neural networks (GNNs) in the transductive setting. Several results are presented where the deviation between the expected loss on unlabeled data and empirical loss on labeled data is bounded using the Rademacher complexity of GNN hypothesis classes. ", "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": "The paper is well-written and rigorous. While the presented results seem helpful towards obtaining a better understanding of the performance of GNNs, the authors may find it useful to discuss the following points more clearly:\n\n1. My major concern about the results in this paper is about the bound in Theorem 1. \n\na. The result in Theorem 1 (and the following results) suggest that the generalization error should increase with the number of unlabeled samples n, due to the terms of O(n^2/(m(n-m))) and O(sqrt(log(n))) in the Rademacher complexity expression. However, none of the experimental results indicate an increase in the generalization error as n increases. I'm wondering whether the increase in the error with n as predicted by the theorems is a side effect of the proof techniques used in the paper, or there may potentially be certain graph topologies where such an increase can indeed be experimentally observed. \n\nb. In the bound in Theorem 1 and the following bounds, the error is seen to include a term of O(n^2/(m(n-m))). Regarding the distribution of labeled vs. unlabeled samples, this result implies that the error takes its smallest value when half of the samples are labeled (m=0.5n). This seems surprising, as one would expect the generalization error to be smaller if more samples are labeled. Is there an intuitive interpretation of this?\n\n2. Theorem 2 suggests that the Rademacher complexity tends to increase with Gamma, which is also supported by the experimental results. Given that Gamma represents the alignment between the graph and the feature information, could the authors provide some interpretation about why the complexity of the GNN hypothesis family is higher when the information provided by the graph topology and the graph features are more aligned? I would intuitively expect the hypothesis function complexity to be smaller when the \"intrinsic dimensionality\" of the data space is smaller.\n\n3. Corollary 1 and the results in Figure 2 suggest that as alpha increases, the generalization error decreases. However, considering the balance between the feature information propagating from the previous layers and the residual feature information coming from the first layer, one would normally expect the optimal value of alpha to be an intermediate value between 0 and 1 (i.e. one would not expect to obtain the best results at alpha=1). Some additional explanations would be useful here. \n\n\n4. Minor comments:\n- In the bound in Proposition 1, what does the parameter \"em\" mean?\n- I recommend that the authors proofread their paper to check for typos. There are several typos in the paper (e.g. \"Randemacher complexity\" in Theorem 1, \"In the broader deep learning learning\" in page 2, and several others).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations of the work could be discussed in more detail.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5-6 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper analyzed the generalization gap of GNNs based on statistical learning theory. First, this paper gives an upper bound of the generalization gap by using the VC dimension of the model, which is characterized by the rank of the adjacency matrix. However, it is shown that such a bound is vacuous. To overcome this issue, the authors give a tighter Transductive Rademacher Complexity (TRC) which is bounded by norms of $S$ and $SX$. They gave detailed discussions about the derived bound in some specific situations. They also discussed benefit of residual connections which reduce the generalization gap. 

Overall, this paper is well written, and the problems that the paper is analyzing is indeed important. This paper gives a detailed analysis on the issue of generalization ability of graph neural networks, which is valuable to the community.  
One of the biggest weakness of this study is that evaluating TRC is not new because it has already been addressed by Oono and Suzuki (2020). Unfortunately, this paper does not cite Oono and Suzuki (2020) nor give discuss relation to it. On the other hand, there are several interesting insights that were not indicated by Oono and Suzuki (2020). In that sense, this paper has novelty.

In summary, this paper gives an instructive theoretical analysis for GNNs and it can be accepted by NeurIPS.   
On the other hand, I definitely recommend the authors to include Oono and Suzuki (2020) and discuss relation to it.  
Decision: Accept (Poster)