Learning Theory Can (Sometimes) Explain Generalisation in Graph Neural Networks
Year: 2021

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.

heading: 1 Introduction
text: Neural networks have found tremendous success in a 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 in understanding generalization and other theoretical properties of neural networks in the theoretical machine learning community (Feldman 2020; Arora et al. 2019a; Ma et al. 2017; Nagarajan et al. 2019; Theisen et al. 2020; Ghorbani et al. 2020). Most of the existing theory literature focuses on the supervised learning problem, or 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 (NeurIPS 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; Veličković et al. 2018; Xu et al. 2019). While some GNNs focus on the transductive setting, sometimes referred to as semi-supervised node classification,1 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-theoretic 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 et al. 2007), and derive VC Dimension and Rademacher complexity for transductive classification (Tolstikhin et al. 2016; El-Yaniv et al. 2009). Generalisation error 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 learning-theoretic 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 a 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 to 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. (2020a). 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/boosting 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-theoretic bounds since they do not adequately capture the behaviour of deep models (Neyshabur et al. 2017). 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 et al. 2016; Gilmer et al. 2017) 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 a theoretical analysis, it is difficult to infer the implications of these results for finite GNNs.
1In semi-supervised learning, the learner is given a 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 measures to analyse GNNs, with a specific focus on explicitly characterising the influence of 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 under a 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.

heading: 2 Statistical Framework for Transductive Learning on GNN
text: For a rigorous analysis, we introduce a statistical learning framework for graph based transductive 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 3, we show that it can provide meaningful bounds under certain distributional assumptions.

heading: 2.1 Framework for Transductive Learning
text: We briefly recall the framework for supervised binary classification. Let X = Rd be the domain or feature space and Y = {±1} be the label set. The goal is to find a predictor h : X → Y based on m training samples S , {(xi, yi)}mi=1 ⊂ X ×Y and a loss function ` : Y ×Y → [0,∞). In a statistical framework, we assume that S consists independent labelled samples from a distributionD = DX ×η, that is, xi ∼ DX and yi ∼ η(xi), where η(·) governs the label probability for each feature. The goal of learning is to find h that minimises the risk / generalisation error LD(h) , E(x,y)∼D[`(h(x), y)]. Since, LD(h) cannot be computed without the knowledge of D, one minimises the empirical risk over the training sample S as LS(h) , 1m ∑m i=1 ` (h (xi) , yi) .
Transductive learning. In transductive inference, one restricts the domain to be X , {xi}ni=1, a finite set of features xi ∈ Rd. Without loss of generality, one may assume that the labels y1, . . . , ym ∈ {±1} are known, and the goal is to predict ym+1, . . . 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 yi ∼ η(xi) for some unknown distribution η. Hence D := Unif([n])× η is the joint distribution on X × Y , and the goal is to find a predictor h : X → Y that minimises the generalisation error Lu(h) , 1n−m ∑n i=m+1 ` (h(xi), yi). In addition we define
the empirical error of h to be L̂m(h) , 1m ∑m i=1 ` (h(xi), yi) and the full sample error of h to be
Ln(h) , 1n ∑n i=1 ` (h(xi), yi), 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
Lu(h) ≤ L̂m(h) + complexity term.
The complexity term is typically characterised using learning-theoretic terms such as VC Dimension and Rademacher complexity. For the transductive setting see Tolstikhin et al. (2016), El-Yaniv 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 x1, . . . ,xn, and edge (i, j) denoting similarity of vertices i and j. For ease of exposition, we define the matrix X ∈ Rn×d with rows being the n feature vectors of dimension d. We also abuse notation to write a predictor as h : Rn×d → {±1}n. Furthermore, typically neural networks output a soft predictor in R, that is further transformed into labels through sign or softmax functions. Hence, much of our analysis focuses on predictors h : Rn×d → Rn, and corresponding hypothesis class
HG = { h : Rn×d → Rn : h is parametrized by G } ⊂ R[n].
When applicable, we denote the hypothesis class of binary predictors obtained through sign function as sign ◦HG = {sign(h) | h ∈ HG}. Note that sign ◦HG ⊂ HG , 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 k denoted by gk(H) : Rdk−1 → Rdk with layer wise input matrix H ∈ Rn×dk−1 . Consider a class of GNNs defined over K layers, with dimension of layer k ∈ [K] being dk and S ∈ Rn×n the graph diffusion operator. Let φ denote the point-wise activation function of the network, which we assume to be a Lipschitz function with Lipschitz constant Lφ. We assume φ to be the same throughout the network. We define the hypothesis class over all K-layer GNNs as:
HφG , { hφG(X) = gK ◦ · · · ◦ g0 : R n×d → {±1}n }
(1)
with gk , φ (bk + Sgk−1 (H)Wk) , k ∈ [K], g0 ,X. (2)
where (2) defines the layer wise transformation withWk ∈ Rdk−1×dk as the trainable weight matrix and bk ∈ Rdk the bias term. Here, the graph is treated as part of the hypothesis class, as indicated by the subscript in HφG . 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:
Sloop , A+ I self loop
Snor , (D + I)− 1 2 (A+ I)(D + I)− 1 2 , degree normalized (Kipf et al. 2017)
whereA denotes the graph adjacency matrix andD is the degree matrix. However, most results are stated for general S.

heading: 2.2 Generalisation Error-bound using VC Dimension
text: The main focus of this paper is the notion of generalisation, that is, understanding how well a GNN can predict the classes of an unlabelled set given the training data. We start with one of the most fundamental learning-theoretical concepts in this context which is the Vapnik–Chervonenkis (VC) dimension of a hypothesis class, a measure of the complexity or expressive power of a space of functions learned by a binary classification algorithm. The following result bounds the VC Dimension for the hypothesis classHφG , and use it to derive a generalisation error bound with respect to the full sample error Ln, which is close to the generalisation error for unlabelled examples Lu when m n.
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 ◦HlinearG ) = min { d, rank ( S ) , min k∈[K−1] {dk} } .
Similarly, the VC Dimension for the hypothesis class of GNNs with ReLU non-linearities and binary outputs, can be bounded as VCdim ( sign ◦HReLUG ) ≤ min {rank(S), dK−1}.
Using the above bounds, it follows that, for any δ ∈ (0, 1), the generalisation error for any h ∈ sign ◦HG satisfies, with probability 1− δ,
Ln(h)− L̂m(h) ≤
√ 8
m
( min {rank(S), dK−1} · ln(em) + ln ( 4
δ
)) . (3)
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 on the graph information (that we are primarily interested in) is preserved. There are two situations that arise. If dK−1 ≤ rank(S), then, from Proposition 1, the graph information is redundant and one could essentially train a fully connected network without diffusion on the labelled features, and use it to predict on unlabelled features. The graph information has an influence for rank(S) < dK−1. While general statements on the influence of the graph information are difficult, by considering specific assumptions on the graph we can characterise the generalisation error further.
For linear GNN on graph G, one can bound the VC Dimension between those for empty and complete graphs, that is, VCdim ( sign ◦Hlinearcomplete ) ≤ VCdim ( sign ◦HlinearG ) ≤ VCdim ( sign ◦Hlinearempty ) . Moreover, for disconnected graphs, rank(S) is related to the number of connected components. Similar observations hold for upper bounds on VC Dimension for ReLU GNNs. Based on this observation for simple settings, it holds that considering graph information in comparison to a fully connected feed forward neural network leads to a decrease in the complexity of the class, and therefore also in the generalisation error. However, the graph G is connected in most practical scenarios, and even under strong assumptions on the graph, for example under consideration of Erdös-Rényi graphs or stochastic block models, rank(S) = O(n) (Costello et al. 2008). Therefore, for the case
dK−1 > rank(S) = O(n), Proposition 1 provides a generalisation error bound of O (√ n·lnm m ) ,
which holds trivially for 0-1 loss as n > m. Furthermore, rank(S) is often similar for both self-loop Sloop and degree-normalised diffusion Snor, and hence, the VC Dimension based error bound does not reflect the positive influence of degree normalisation—a fact that can be explained through stability based analysis (Verma et al. 2019).

heading: 2.3 Generalisation Error-bound using Transductive Rademacher Complexity
text: Due to the triviality of VC Dimension based error bounds, we 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 1 (Transductive Rademacher complexity (El-Yaniv et al. 2009)) Let V ⊆ Rn, p ∈ [0, 0.5] and m the number of labeled points. Let σ = (σ1, . . . , σn)
T be a vector of independent and identically distributed random variables, where σi takes value +1 or −1, each with probability p, and 0 with probability 1− 2p. The transductive Rademacher complexity (TRC) of V is defined as
Rm,n(V) , ( 1
m +
1
n−m ) · E σ [ sup v∈V σ>v ] .
The following result derives a bound for the TRC of GNNs, defined in (1)–(2), and states the corresponding generalization error bound. The bound involves standard matrix norms, such as ‖ · ‖∞ (maximum absolute row sum) and the ‘entrywise’ norm, ‖·‖2→∞ (maximum 2-norm of any column).
Theorem 1 (Generalization error bound for GNNs using TRC) Consider Hφ,β,ωG ⊆ H φ G such that the trainable parameters satisfy ‖bk‖1 ≤ β and ‖Wk‖∞ ≤ ω for every k ∈ [K]. The transductive Rademacher complexity (TRC) of the restricted hypothesis class is bounded as
Rm,n(Hφ,β,ωG ) ≤ c1n
2
m(n−m) ( K−1∑ k=0 ck2 ‖S‖ k ∞ ) + c3c K 2 ‖S‖ K ∞ ‖SX‖2→∞ √ log(n) , (4)
where c1 , 2Lφβ, c2 , 2Lφω, c3 , Lφω √ 2/d and Lφ is Lipschitz constant for activation φ.
The bound on TRC leads to a generalisation error bound following El-Yaniv et al. (2009). For any δ ∈ (0, 1), the generalisation error for any h ∈ Hφ,β,ωG satisfies
Lu(h)− L̂m(h) ≤ Rm,n(Hφ,β,ωG ) + c4 n √ min{m,n−m} m(n−m) + c5 √ n m(n−m) ln ( 1 δ ) (5)
with probability 1− δ, where c4, c5 are absolute constants such that c4 < 5.05 and c5 < 0.8. The additional terms in (5) are O ( max {
1√ m , 1√ n−m
}) , and hence, we may focus on the upper
bound on TRC (4) to understand the influence of the graph diffusion S as well as its interaction with the feature matrixX . The bound depends on the choice of ω, and it suggests a natural choice of ω = O(1/‖S‖∞) such that the bound does not grow exponentially with network depth. The subsequent discussions focus on the dependence on ‖S‖∞ and ‖SX‖2→∞, ignoring the role of ω. 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 ‖Sloop‖∞ = 1 + dmax, where dmax denotes the maximum degree, and hence, for fixed ω, the bound grows as O(dKmax). In contrast,
for degree normalisation, ‖Snor‖∞ = O (√
dmax dmin
) , and hence, the growth is much smaller (in fact,
‖Snor‖∞ = 1 on regular graphs). It is worth noting that, in the supervised setting, Liao et al. (2021) derived PAC-Bayes for GNN with diffusion Snor, where the bound varies as O(dKmax). Theorem 1 is tighter in the sense that, for Snor, the error bound has weaker dependence on dmax, mainly through ‖SX‖2→∞. From spectral radius to ‖SX‖2→∞. Previous analyses of GNNs in 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(‖S‖22), where ‖S‖2 is the spectral norm. In contrast, Theorem 1 shows TRC = O(‖S‖∞ ‖SX‖2→∞). This is the first result that explicitly uses the relation between the graph-information and the feature information explicitly via ‖SX‖2→∞. One may note that without node features, that is X = I, we have ‖S‖2→∞ ≤ ‖S‖2 ≤ ‖S‖∞ and hence, a direct comparison between (5) and O(‖S‖22) bound of Verma et al. (2019) is inconclusive. However, in presence of featuresX , Theorem 1 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 1 in terms of spectral components by considering ‖SX‖2→∞ = maxj ‖(SX)·j‖2 ≤ maxj ‖S‖2 ‖X.j‖2 ≤ ‖S‖2‖X‖2→∞ and ‖SX‖2→∞ which can be bound as 1√ n ‖S‖∞ ≤ ‖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 ‖S‖k2 , k ∈ [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.

heading: 3 Generalization using TRC under Planted Models
text: The discussion in previous section shows that TRC based generalisation error bound provides some insights into the behaviour of GNNs (example, Snor is preferred over Sloop), but the bound is too general to give insights into the influence of the graph information on the generalisation error. The key quantity of interest is ‖SX‖2→∞, 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 (Dasgupta 1999), and graph is independently generated from a 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 matrixX or adjacency matrixA, respectively. Our interest, however, is to quantitatively analyse the influence of graph information when the latent classes in featuresX and graphA 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.

heading: 3.1 Model and Bounds on TRC
text: We assume that the node features are sampled latent true classes, given a z = (z1, . . . , zn) ∈ {±1}n. The node features are sampled from a Gaussian mixture model (GMM), that is, feature for node-i is sampled as xi ∼ N (ziµ, σ2I) for some µ ∈ Rd and σ ∈ (0,∞). We express this in terms ofX as
X = X + ∈ Rn×d, where X = zµ> and = ( ij)i∈[n],j∈[d] i.i.d.∼ N (0, σ2). (6)
We refer to above as X ∼ 2GMM. On the other hand, we assume that graph has two latent communities, characterised by y ∈ {±1}n. The graph is generated from a stochastic block model with two classes (2SBM), where edges (i, j) are added independently with probability p ∈ (0, 1] if yi = yj , and with probability q < [0, p) if yi 6= yj . In other words, we define the random adjacency A ∼ 2SBM as a symmetric binary matrix withAii = 0, and (Aij)i<j indenpendent such that
Aij ∼ Bernoulli(Aij), where A = p+ q
2 11> + p− q 2 yy> − pI. (7)
The choice of two different latent classes z,y ∈ {±1}n allows study of the case where the graph and feature information of do not align completely. We use Γ = |y>z| ∈ [0, n] to quantify this alignment. Assuming y, z are both balanced, that is, ∑ i yi = ∑ i zi = 0, one can verify that
‖(A+ I)X‖2→∞ = ‖µ‖∞ ( n(1− p)2 + 14n(p− q) 2Γ2 − (p− q)(1− p)Γ2 )1/2 , (8)
which indicates that, for dense graphs (p, q 1n ), the quantity ‖SX‖2→∞ 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, assumingX ∼ 2GMM andA ∼ 2SBM.
Theorem 2 (Expected TRC for GNNs under SBM) Let c1, c2 and c3 as defined in Theorem 1 and Γ , |y>z|. Let c6 , (1 + o(1)), c7 , (1 + ko(1)), c8 , (1 + Ko(1)). Assuming p, q (lnn) 2 n we can bound the expected TRC forA as defined in (7) andX as defined in (6) as follows:
Case 1, Degree normalized: S = Snor
E X∼2GMM A∼2SBM
[ Rm,n(Hφ,β,ωG ) ] ≤ c1n 2
m(n−m) ( K−1∑ k=0 c7c k 2 ( p q ) k 2 ) + c8c3c K 2 ( p q )K 2 √ ln(n) ×
( c6 ‖µ‖∞ 1 + ( p−q 2 )2 Γ2(
p+q 2
)2 + c6 √ ln(n)
q ‖µ‖∞ + c6
√ σ(1 + 2 ln(d))
q
) (9)
Case 2, Self Loop: S = Sloop
E X∼2GMM A∼2SBM
[ Rm,n(Hφ,β,ωG ) ] ≤ c1n 2
m(n−m) ( K−1∑ k=0 c7c k 2(np) k ) + c8c3c K 2 (np) K √ ln(n) ×
( c6 ‖µ‖∞ n ( 1 + ( p− q
2
)2 Γ2 ) + n √ p+ q
2 ‖µ‖∞ + c6n
√ pσ √ 1 + 2 ln(d) ) (10)
We note that although the above bounds are stated in expectation, they can be translated into high probability bounds. Furthermore the non-triviality 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 2 can be also translated into bounds on the generalisation gap Lu(h)− L̂m(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 [ ‖Sloop‖k∞ ] = c7(np) k with
E [ ‖Snor‖k∞ ] = c7 (p/q) k/2 and observe that by normalising we lose the n term. In addition we
can consider E [‖SX‖2→∞] which is bound by the second line in (9)–(10). Again in the first, deterministic, term we observe that the self loop version contains an additional dependency on n. For the two noise terms we can characterize the behaviour in terms of the density of the graph. Let
ρ = O(p), O(q) and ρ 1n then we can characterise the dense setting as ρ Ω(1) and the sparse setting as ρ O ( ln(n) n ) and observe that in both case the normalised case grows slower with n:
Dense: E [ ‖SloopX‖2→∞ ] = O(n) and E [‖SnorX‖2→∞] = O( √ ln(n)) (11)
Sparse: E [ ‖SloopX‖2→∞ ] = O( √ n ln(n)) and E [‖SnorX‖2→∞] = O( √ n) (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 no graph information is considered, S = I and Snor. We define the corresponding hypothesis classes asHφ,β,ωI andHφ,β,ωnor . Considering the deterministic case (S = S,X = X ) we can observe Rm,n(Hφ,β,ωI ) > Rm,n(Hφ,β,ωnor ) if Γ > O ( n√ nρ+n ) . Therefore the random graph setting allows us to more precisely characterize under what conditions adding graph information helps.

heading: 3.2 Experimental Results
text: 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 to real world, multi-class data on the example of the Cora dataset (Rossi et al. 2015). The results are presented in Figure 1. For the SBM we consider a graph with n = 500,m = 100 as default. We plot the mean over 5 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, 1) 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 observations2. Details on the experimental setup are given in the Appendix.
We can first look at the feature and graph alignment as characterised through Γ2 in the TRC based bound (8)–(9) and observe that with an increase in the latent structure the generalisation error
2Generalisation error bounds, even for simple machine learning models, can exceed 1 due to absolute constants that cannot be precisely estimated. Hence, the point of interest is the dependence of key parameters; for instance, in a supervised setting, the bounds are O(1/ √ m) and typically exceeds 1 for moderate m. This problem is inherent to the bound given in El-Yaniv et al. (2009) that we base our TRC bounds on, as the slack terms can already exceeds 1 and therefore further research on general TRC generalisation gaps is necessary to characterise the absolute gap between theory and experiments.
increases. While this seems to be counterintuitive a possible explanation could be that reduced alignment 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 a change in the feature structure by adding noise to the feature vector asX + where i· is i.i.d. distributed N (0, σ2FeatI) 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 in the previous section, especially through (11)–(12) and illustrate it in Figure 1 (middle). Empirically for both, SBM and Cora, the generalisation error stays mostly consistent over varying n. Finally for the number of observed points we consider a realistic setting of m n−m where we see a sharp decline in the setting of few observed points but then the generalisation error converges which corresponds to the influence of m as described in (9). Practically such an observation can 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 a given level of accuracy.

heading: 4 Influence of Depth and Residual Connections on the Generalisation Error
text: 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 a left multiplication of the diffusion operator and we can therefore observe an over-smoothing effect (Li et 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 et al. 2020), such that by adding connections from previous layers the network retains some feature information. In this section we investigate this approach in the TRC setting. In Section 4.1 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.

heading: 4.1 Model and bounds on TRC for GNN with Residual connections
text: 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 as defined in (2) is extended by an interpolation over parameter α 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− α) (bk + Sgk (H)Wk) + αg0 (H)) , with α ∈ (0, 1). (13) We can now derive a generalization error bound similar to Theorem 1 for the Residual network.
Theorem 3 (TRC for Residual GNNs) Consider a Residual network as defined in (13) and Hφ,β,ωG ⊂ H φ G such that the trainable parameters satisfy ‖bk‖1 ≤ β and ‖Wk‖∞ ≤ ω for ev-
ery k ∈ [K]. Then with α ∈ (0, 1) and c1 , 2Lφβ, c2 , 2Lφω, c3 , Lφω √
2/d the TRC of the restricted class or Residual GNNs is bounded as
Rm,n(Hφ,β,ωG ) ≤ ((1− α)c1 + α2Lφ ‖X‖∞)n2
m(n−m)
( K−1∑ k=0 (1− α)ck2 ‖S‖ k ∞ ) + α2Lφ ‖X‖∞ + (1− α)c3c K 2 ‖S‖ K ∞ ‖SX‖2→∞ √ log(n) (14)
However observing the bound isolated does not provide new insights beyond Theorem 2 into the behaviour of the generalisation error and therefore we focus on the comparison between GNNs with and without residual connections.
For readability assume β = ‖X‖∞. Under this setup we can note that the generalisation error-bound increases with decreased alpha and in extension it 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 α, the network architecture
is closer to the one of an one hidden layer network. Having good performance in shallow networks is something that is observed in our experiments as well as in previous work (e.g., (Kipf et al. 2017)). Therefore it appears that using the skip connection to obtain a deep network that resembles a shallow one leads to the performance increase.

heading: 4.2 Experiments on depth and Residual networks
text: 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 3.2 we start by considering the vanilla GNN version and focus on the influence of depth where Figure 2 (left) illustrates Theorem 2, more specifically an exponential increase of K as shown in (9)–(10) (similar to Liao et al. (2021)). 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 a deviation from the theoretical bound. The rate of growth decreases, which is to be expected as the absolute values of Lu,Lm are bound by construction. Future work with a focus on depth is necessary to refine this component of the bound. Extending the analysis of depth we now consider the residual connections as defined in (13). By (14) we can still observe the exponential dependency on K and 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 as for Cora. ii) Focusing on the Resnets, Theorem 3 predicts an ordering in the generalisation error given by α 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 K as given in Theorem 3, the ordering of the generalisation error-bound described by α is observed empirically. While this does not give us a complete picture we can 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.

heading: 5 Conclusion
text: Statistical learning theory has proven to be a successful tool for a 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 on the data to 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 in the previous section the TRC bound predicts an exponential dependency on network depth K which can only partially be observed empirically and therefore a study without relying on a recursive proof structure will be necessary to refine this dependency onK. As it is not the focus of this paper we consider the bounds on the norms of trainable parameters, ω, β, 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 on generalisation we suggest that the idea of analysing GNNs under planted models can be extended to other learning-theoretical measures such as stability or model selection as well as the supervised (graph-classification) setting.

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

Review summaries:
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.

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.  

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.