Towards Understanding the Generalization of Graph Neural Networks
Graph neural networks (GNNs) are the most widely adopted model in
graph-structured data oriented learning and representation. Despite their
extraordinary success in real-world applications, understanding their working
mechanism by theory is still on primary stage. In this paper, we move towards
this goal from the perspective of generalization. To be specific, we first
establish high probability bounds of generalization gap and gradients in
transductive learning with consideration of stochastic optimization. After
that, we provide high probability bounds of generalization gap for popular
GNNs. The theoretical results reveal the architecture specific factors
affecting the generalization gap. Experimental results on benchmark datasets
show the consistency between theoretical results and empirical evidence. Our
results provide new insights in understanding the generalization of GNNs.
Huayi Tang, Yong Liu
# Towards Understanding the Generalization of Graph Neural Networks

###### Abstract

Graph neural networks (GNNs) are the most widely adopted model in graph-structured data oriented learning and representation. Despite their extraordinary success in real-world applications, understanding their working mechanism by theory is still on primary stage. In this paper, we move towards this goal from the perspective of generalization. To be specific, we first establish high probability bounds of generalization gap and gradients in transductive learning with consideration of stochastic optimization. After that, we provide high probability bounds of generalization gap for popular GNNs. The theoretical results reveal the architecture specific factors affecting the generalization gap. Experimental results on benchmark datasets show the consistency between theoretical results and empirical evidence. Our results provide new insights in understanding the generalization of GNNs.

Machine Learning, Generalization, Generalization, Graph Neural Networks

## 1 Introduction

Graph-structured data (Zhu et al., 2021) exists widely in real-world applications. As one of the most powerful tools to process graph-structured data, GNNs (Gori et al., 2005; Scarselli et al., 2009) are widely adopted in Computer Vision (Qi et al., 2017; Johnson et al., 2018; Landrieu and Simonovsky, 2018; Satorras and Estrach, 2018), Natural Language Processing (Bastings et al., 2017; Beck et al., 2018; Song et al., 2018), Recommendation Systems (Ying et al., 2018; Fan et al., 2019; He et al., 2020; Deng et al., 2022), AI for Science (Sanchez-Gonzalez et al., 2020; Pfaff et al., 2021; Shen et al., 2021; Han et al., 2022), to name a few. There are two main ways to view modern GNNs, _i.e._, spatial domain perspective (Kipf and Welling, 2017; Velickovic et al., 2018; Xu et al., 2018; Xu et al., 2018) and spectral domain perspective (Defferrard et al., 2016; Gasteiger et al., 2019; Liao et al., 2019; Chien et al., 2021; He et al., 2021). The former regards GNN as the process of combining and updating features according to adjacent relationships. The latter treats GNN as a filtering function applied on input features. Recent developments of GNNs are summarized in (Zhou et al., 2020; Wu et al., 2021; Zhang et al., 2022).

Despite the empirical success of GNNs, establishing theories to explain their behaviors is still in its infancy. Recent works towards this direction includes understanding oversmoothing (Li et al., 2018; Zhao and Akoglu, 2020; Oono and Suzuki, 2020; Rong et al., 2020), interpretability (Ying et al., 2019; Luo et al., 2020; Vu and Thai, 2020; Yuan et al., 2020; 2021), expressiveness (Xu et al., 2019; Chen et al., 2019; Maron et al., 2019; Dehmanny et al., 2019; Feng et al., 2022), and generalization (Scarselli et al., 2018; Du et al., 2019; Verma and Zhang, 2019; Garg et al., 2020; Zhang et al., 2020; Oono and Suzuki, 2020; Lv, 2021; Liao et al., 2021; Esser et al., 2021; Cong et al., 2021). This work focuses on the last branch. Some previous works adopt the classical techniques such as Vapnik-Chervonenkis dimension (Scarselli et al., 2018), Rademacher complexity (Lv, 2021; Garg et al., 2020) and algorithm stability (Verma and Zhang, 2019) to provide generalization bounds for GCN (Kipf and Welling, 2017) and more general message passing neural networks. However, in their analysis, the original graph is split into subgraphs composed of central node and its neighbors, which are treated as independent samples. This setting significantly differs from real implementation that training nodes are sampled without replacement from full nodes and the test nodes are visible during training (El-Yaniv and Pechyony, 2007; Oono and Suzuki, 2020), resulting a gap between theory and practice. To tackle this issue, recent works (Oono and Suzuki, 2020; Esser et al., 2021) incorporate the learning schema of GNNs into the category of transductive learning and derive more realistic results. However, there are still some drawbacks of these works. First, the analysis in (Oono and Suzuki, 2020) is oriented to multi-scale GNNs that differ a lot from modern GNNs in network architecture. Besides, their analysis is limited to the AdaBoost-like optimization procedure, and whether the technique can be applied to general optimization algorithms such as stochastic gradient descent (SGD) is unknown. Second, the upper bound in (Esser et al., 2021) is of slow order and fails to
provide meaningful learning guarantee for node classification in large-scale scenarios. Third, (Cong et al., 2021) only consider spectral-based GNNs with fixed coefficients, leaving spectral-based GNNs with learnable coefficients (Chien et al., 2021) unexplored.

Motivated by the aforementioned challenges, under transductive setting, we study the generalization gap of GNNs for node classification task with consideration of stochastic optimization algorithm. First, we establish high probability bounds of generalization gap and gradients under transductive setting, and derive high probability bounds of test error under gradient dominant condition. Next, we provide a comprehensive analysis on popular GNNs including both linear and non-linear models and derive the upper bound of the Lipschitz continuity and Holder smoothness constants, by which we compare their generalization capability. The results show that SGC (Wu et al., 2019) and APPNP (Gasteiger et al., 2019) can achieve smaller generalization gap than GCN (Kipf and Welling, 2017). Besides, the unconstrained coefficients in spectral GNNs may yield a large generalization gap. Our results reveal why shallow models yield comparable and even superior performance from the perspective of learning theory, and provide theoretical supports for widely used techniques such as early stop and drop edge (Rong et al., 2020). Experimental results on benchmark datasets show that the theoretical findings are generally consistent with the practical evidences.

## 2 Related Work

### Generalization Analysis of GNNs

Existing studies on the generalization of GNNs general fall into two categories: graph classification task and node classification task.

**Graph classification task.**(Liao et al., 2021) is the first work to establish generalization bounds of GCN and message passing neural networks by PAC-Bayesian approach. The authors in (Ju et al., 2023) further improve their results and provide the lower bound. Besides, neural tangent kernels (Jacot et al., 2018) are also used to analyze the generalization of infinitely wide GNNs trained by gradient descent (Du et al., 2019). Different from that, this work focus on node classification task that is more challenging.

**Node classification task.** The authors in (Scarselli et al., 2018) analyze the generalization capability of GNNs by Vapnik-Chervonenkis dimension. (Verma and Zhang, 2019) is the first work to provide generalization bounds of one-layer GCN by algorithm stability which is further extended to multi-layer GCNs in (Zhou and Wang, 2021). The work (Garg et al., 2020) converts the graph into individual local node-wise computation tree and bound their generalization bound respectively by Rademacher Complexity. The aforementioned works rely on the assumption that converting a graph into subgraphs, which differs a lot from realistic implementation. Observing that, (Oono and Suzuki, 2020) makes the first step that adopting the transductive learning framework to analyze multi-scale GNNs. This framework originates from (Vapnik, 1998; 2006), and is further developed in (El-Yaniv and Pechyony, 2006; 2007) where the authors propose transductive stability and Transductive Rademacher complexity to measure the generalization capability of transductive learner. The work most related to ours is (Cong et al., 2021) and (Esser et al., 2021), where the authors establish generalization bound for GNNs and its variants by transductive uniform stability and transductive Rademacher complexity respectively. However, the derived bound in (Esser et al., 2021) is of slow order, and whether their technique can be applied on SGD is still unknown. Different from (Cong et al., 2021) that analyzing full-batch gradient descent, we analyze a more complex setting, _i.e._, transductive learning under SGD, due to the involve of randomness in optimization. Besides, there are some works orthogonal to ours, _e.g._, analyzing the generalization capability of GNNs training with topology-sampling (Li et al., 2022) or on large random graphs (Keriven et al., 2020).

### Out-of-Distribution (OOD) Generalization on Graphs

Much efforts are devoted to the study of OOD generalization on graphs (Li et al., 2022) in recent years, due to the occurs of distribution shift in real-world scenarios. An adversarial learning schema (Wu et al., 2022) is proposed to minimize the mean and variance of risks from multiple environments. The authors in (Yang et al., 2022) propose a two-stage training schema to tackle distribution shift on molecular graphs. Energy-based message passing scheme is show to be effective in enhancing the OOD detection performance of GNNs (Wu et al., 2023). Current work (Yang et al., 2023) shows that the spurious performance of GNNs may come from its intrinsic generalization capability rather than expressivity. Besides, there are also some work focus on the reasoning (Xu et al., 2020), extrapolation ability (Xu et al., 2021; Bevilacqua et al., 2021), and generalization from small to large graphs (Yehudai et al., 2021).

## 3 Preliminaries

### Notations

Let \(\mathcal{G}=\{\mathcal{V},\mathcal{E}\}\) be an given undirected graph with \(n=|\mathcal{V}|\) nodes. Each node is an instance \(z_{i}=(\mathbf{x}_{i},y_{i})\) containing feature \(\mathbf{x}_{i}\) and label \(y_{i}\) from some space \(\mathcal{Z}=\mathcal{X}\times\mathcal{Y}\). Let \(\mathbf{X}\) be the feature matrix where the \(i\)-th row \(\mathbf{X}_{i*}\) is the node feature \(\mathbf{x}_{i}\). Let \(\mathbf{A}\) and \(\mathbf{D}\) be the adjacency matrix and the diagonal degree matrix respectively, where \(\mathbf{D}_{ii}=\sum_{j=1}^{n}\mathbf{A}_{ij}\)
Denote by \(\tilde{\mathbf{A}}=(\mathbf{D}+\mathbf{I}_{n})^{-\frac{1}{2}}(\mathbf{A}+\mathbf{I }_{n})(\mathbf{D}+\mathbf{I}_{n})^{-\frac{1}{2}}\) the normalized adjacency matrix with self-loops and \(\sqrt{|\mathcal{Y}|}\) the number of categories. We focus on the transductive learning setting in this work, _i.e._, all features together with the randomly sampled labels are constructed as training set. Let \(S=\{\mathbf{x}_{i},y_{i}\}_{i=1}^{m+u}\) be the set of instances where \(m+u=n\). Without loss of generality (w.l.o.g.), let \(\{y_{i}\}_{i=1}^{m}\) be the selected labels, our task is to predict the labels of samples \(\{\mathbf{x}_{i}\}_{i=m+1}^{m+u}\) by a learner (model) trained on \(\{\mathbf{x}_{i}\}_{i=1}^{m+u}\bigcup\{y_{i}\}_{i=1}^{m}\). This setting is widely adopted in node classification task (Yang et al., 2016; Kipf and Welling, 2017) where the training and test nodes are determined by a random partition.

From now on, we limit the scope of the learner to a given GNN and let \(\{\mathbf{W}_{h}\}_{h=1}^{H}\) be its learnable parameters. Since \(\mathbb{R}^{p\times q}\) and \(\mathbb{R}^{pq}\) are isomorphic, the analysis in this work is oriented to the vector space for concise. To this end, we use a unified vector \(\mathbf{w}=[\operatorname{vec}\left[\mathbf{W}_{1}\right];\dots; \operatorname{vec}\left[\mathbf{W}_{H}\right]]\) to represent the collection of \(\{\mathbf{W}_{h}\}_{h=1}^{H}\), where \(\operatorname{vec}[\cdot]\) is the vectorization operator that transforms a given matrix into vector, _i.e._, \(\operatorname{vec}\left[\mathbf{W}\right]=\left[\mathbf{W}_{*1};\cdots; \mathbf{W}_{*q}\right]\) for \(\mathbf{W}\in\mathbb{R}^{p\times q}\). Here \(\mathbf{W}_{*i}\) is the \(i\)-th column of \(\mathbf{W}\). For \(\mathbf{w}\in\mathcal{W}\), the training and test error is defined as \(R_{m}(\mathbf{w})\triangleq\frac{1}{m}\sum_{i=1}^{m}\ell(\mathbf{w};z_{i})\) and \(R_{u}(\mathbf{w})\triangleq\frac{1}{u}\sum_{i=m+1}^{m+u}\ell(\mathbf{w};z_{i})\) respectively, where \(\ell:\mathcal{W}\times\mathcal{Z}\mapsto\mathbb{R}_{+}\) is the loss function. In this work, we follow previous studies (El-Yaniv and Pechyony, 2007; Oono and Suzuki, 2020b; Esser et al., 2021) and define the transductive generalization gap by \(|R_{m}(\mathbf{w})-R_{u}(\mathbf{w})|\). Since the label of test examples are not available, the optimization process is finding parameters to minimize the the training error \(R_{m}(\mathbf{w})\). Much efforts (Duchi et al., 2011; Kingma and Ba, 2015) are devoted to solve this stochastic optimization problem, and we mainly focus on SGD (Summarized in Algorithm 1) in this work.

Now we introduce notations used in the rest of this paper. Denote by \(\left\|\cdot\right\|_{2}\) and \(\left\|\cdot\right\|\) the \(2\)-norm of vector and spectral norm of matrix, respectively. Let \(\mathbf{w}^{(1)}\) be the initialization weight of model, we focus on the space \(\mathcal{W}=B(\mathbf{w}^{(1)};r),r\geq 1\) in this work, where \(B(\mathbf{w}^{(1)};r)\triangleq\left\{\mathbf{w}:\left\|\mathbf{w}-\mathbf{w} ^{(1)}\right\|_{2}\leq r\right\}\) is the ball with radius \(r\). Denote by \(\nabla\ell(\cdot;z)\) the gradient of \(\ell\) with respective to (w.r.t.) the first argument. Denote by \(b_{g}=\sup_{z\in\mathcal{Z}}\left\|\nabla\ell(\mathbf{w}^{(1)};z)\right\|_{2}\) the supremum of gradient with initialized parameter and \(b_{\ell}=\sup_{z\in\mathcal{Z}}\left|\ell(\mathbf{w}^{(1)};z)\right|_{2}\) the supernum of loss value with initialed parameter. Let \(\hat{\mathbf{w}}\in\operatorname*{argmin}_{\mathbf{w}\in\mathcal{W}}R_{m}( \mathbf{w})\) be the parameters of training error minimizer. We denote by \(\sigma(\cdot)\) the activation function.

```
Input: Initial parameter \(\mathbf{w}^{(1)}\), learning rates \(\{\eta_{t}\}\), training set \(\{\mathbf{x}_{i}\}_{i=1}^{m+u}\cup\{y_{i}\}_{i=1}^{m}\). for\(t=1\)to\(T\)do  Randomly draw \(j_{t}\) from the uniform distribution over the set \(\{j:j\in[m]\}\).  Update parameters by \(\mathbf{w}^{(t+1)}=\mathbf{w}^{(t)}-\eta_{t}\nabla\ell(\mathbf{w}^{(t)};z_{j_{t }})\). endfor
```

**Algorithm 1** SGD for Transductive Learning

### Assumptions

In this part, we present the assumptions used in this paper.

**Assumption 3.1**.: Assume that there exists a constant \(c_{X}>0\) such that \(\|\mathbf{x}\|_{2}\leq c_{X}\) holds for all \(\mathbf{x}\in\mathcal{X}\).

**Assumption 3.2**.: Assume that there exists a constant \(c_{W}>0\) such that \(\|\mathbf{W}_{h}\|\leq c_{W},h\in[H]\) for \(\mathbf{w}\in B(\mathbf{w}^{(1)};r)\).

_Remark 3.3_.: Assumption 3.1 requires that input features are bounded (Verma and Zhang, 2019). This assumption can be satisfied by applying normalization on features. Assumption 3.2 means that the parameters during the training process are bounded, which is a common assumption in generalization analysis of GNNs (Garg et al., 2020; Liao et al., 2021; Cong et al., 2021; Esser et al., 2021). These two assumptions are necessary to analyze the Lipschitz continuity and Holder smoothness of objective w.r.t. \(\mathbf{w}\).

**Assumption 3.4**.: Assume that the activation function \(\sigma(\cdot)\) is \(\tilde{\alpha}\)-Holder smooth. To be specific, let \(P>0\) and \(\tilde{\alpha}\in(0,1]\), for all \(\mathbf{u},\mathbf{v}\in\mathbb{R}^{d}\),

\[\|\sigma^{\prime}(\mathbf{u})-\sigma^{\prime}(\mathbf{v})\|_{2}\leq P\|\mathbf{u} -\mathbf{v}\|_{2}^{\tilde{\alpha}}.\]

_Remark 3.5_.: It can be verified that Assumption 3.4 implies Lipschitz continuity of activation function if \(\tilde{\alpha}=0\). Besides, Assumption 3.4 implies the smoothness of activation function if \(\tilde{\alpha}=1\). Therefore, Assumption 3.4 is much milder than the assumption in previous work (Verma and Zhang, 2019; Cong et al., 2021) that requires the activation function is smooth. For the convenience of analysis while not yielding a large gap between theory and practice, we construct a modified ReLU function (See Appdendrix A) with hyperparameter \(q\in(1,2]\) that satisfies Assumption 3.4 and has a tolerable approximate error to vanilla ReLU function.

**Assumption 3.6**.: Assume that there exist a constant \(G>0\) such that for all \(z\in S\)

\[\sqrt{\eta_{t}}\left\|\nabla\ell(\mathbf{w}_{t};z)\right\|_{2}\leq G\]

holds \(\forall\ t\in\mathbb{N}\), where \(\{\eta_{t}\}_{t=1}^{T}\) is learning rates.

_Remark 3.7_.: A formal definition of \(\nabla\ell(\mathbf{w};z)\) is provided in Lemma A.4 in the Appendix. Assumption 3.6 (Lei and Tang, 2021; Li and Liu, 2021) means that the product of gradient and the square root of learning rate is bounded, which is milder than the widely used bounded gradient assumption (Hardt et al., 2016; Kuzborskij and Lampert, 2018), since the learning rate tends to zero during the iteration.

**Assumption 3.8**.: Assume that there exists a constant \(\sigma_{0}>0\) such that for \(\forall\ t\in\mathbb{N}_{+}\), the following inequality holds

\[\mathbb{E}_{j_{t}}\left[\|\nabla\ell(\mathbf{w});z_{j_{t}})\right\|_{2}\leq\sigma_{ 0}^{2}.\]
_Remark 3.9_.: Assumption 3.8 requires the boundness of variances of stochastic gradients, which is a standard assumption in stochastic optimization studies (Kuzborskij and Lampert, 2018; Lei and Tang, 2021; Li and Liu, 2021).

## 4 Theoretical Results

In this section, we first present the high probability bounds of generalization gap and excess risks under transductive learning in Section 4.1. After that, we turn to specific examples and provide results of some popular GNNs in Section 4.2. Please refer to the Appendix for complete proofs.

### General Results of Transductive SGD

We first analyze properties of the objective function \(\ell\) and provide the following proposition.

**Proposition 4.1** (Informal).: _Suppose Assumptions 3.1, 3.2, and 3.4 hold. Denote by \(\mathcal{F}\) a specific GNN, for any \(\mathbf{w},\mathbf{w}^{\prime}\in\mathcal{W}\) and \(z\in S\), the objective \(\ell(\mathbf{w};z)\) satisfies_

\[|\ell(\mathbf{w};z)-\ell(\mathbf{w}^{\prime};z)|\leq L_{\mathcal{F}}\| \mathbf{w}-\mathbf{w}^{\prime}\|_{2}, \tag{1}\]

_and_

\[\begin{split}&\|\nabla\ell(\mathbf{w};z)-\nabla\ell(\mathbf{w}^{ \prime};z)\|\\ \leq& P_{\mathcal{F}}\max\left\{\|\mathbf{w}- \mathbf{w}^{\prime}\|_{2}^{\tilde{\alpha}},\|\mathbf{w}-\mathbf{w}^{\prime} \|_{2}\right\},\end{split} \tag{2}\]

_with constant \(L_{\mathcal{F}}\) and \(P_{\mathcal{F}}\)._

_Remark 4.2_.: We provide more detailed analysis to \(L_{\mathcal{F}}\) and \(P_{\mathcal{F}}\) in Section 4.2. Both \(L_{\mathcal{F}}\) and \(P_{\mathcal{F}}\) depend on the specific network architecture \(\mathcal{F}\) of GNNs. Thus, the upper bound of generalization gap vary by the architecture.

Our first main result is high probability bounds on the transductive generalization gap, as presented in Theorem 4.3.

**Theorem 4.3**.: _Suppose Assumptions 3.1, 3.2, 3.4, 3.6, and 3.8 hold. Suppose that the learning rate \(\{\eta_{t}\}\) satisfies \(\eta_{t}=\frac{1}{t+\ell_{0}}\) such that \(t_{0}\geq\max\{(2P)^{1/\alpha},1\}\). For any \(\delta\in(0,1)\), with probability \(1-\delta\),_

1. _If_ \(\alpha\in(0,\frac{1}{2})\)_, we have_ \[R_{u}(\mathbf{w}^{(T+1)})-R_{m}(\mathbf{w}^{(T+1)})\] \[= \mathcal{O}\bigg{(}L_{\mathcal{F}}\frac{(m+u)^{\frac{3}{2}}}{mu} \log^{\frac{1}{2}}(T)T^{\frac{1-2\alpha}{2}}\log\bigg{(}\frac{1}{\delta}\bigg{)} \bigg{)}.\]
2. _If_ \(\alpha=\frac{1}{2}\)_, we have_ \[R_{u}(\mathbf{w}^{(T+1)})-R_{m}(\mathbf{w}^{(T+1)})\] \[= \mathcal{O}\bigg{(}L_{\mathcal{F}}\frac{(m+u)^{\frac{3}{2}}}{mu} \log(T)\log\bigg{(}\frac{1}{\delta}\bigg{)}\bigg{)}.\]
3. _If_ \(\alpha\in(\frac{1}{2},1]\)_, we have_ \[R_{u}(\mathbf{w}^{(T+1)})-R_{m}(\mathbf{w}^{(T+1)})\] \[= \mathcal{O}\bigg{(}L_{\mathcal{F}}\frac{(m+u)^{\frac{3}{2}}}{mu} \log^{\frac{1}{2}}(T)\log\bigg{(}\frac{1}{\delta}\bigg{)}\bigg{)}.\]

_Remark 4.4_.: Theorem 4.3 shows that the transductive generalization gap depends on the training/test data size \(m/u\), network architecture related Lipschitz continuity constant \(L_{\mathcal{F}}\), and the number of iterations \(T\). Generally, our upper bounds are of order \(\mathcal{O}\left((\frac{1}{m}+\frac{1}{u})\sqrt{m+u}\right)\), which is much sharper than the bound \(\mathcal{O}\left((\frac{1}{m}+\frac{1}{u})(m+u)+\log(m+u)\right)\) in previous work (Esser et al., 2021). Note that with the increase of data size \(m+u\), the bound in (Esser et al., 2021) become increasing larger and fail to provide a reasonable generalization guarantee. This seriously restricts its application in large-scale node classification scenarios where the order of \(m+u\) is usually millions. Our results address these drawbacks and provide more applicable generalization guarantee for GNNs. Besides, the bound provided in (Esser et al., 2021) does not consider the specific optimization and has difficulty in revealing the influence of \(T\) on generalization gap. Our result shows that the generalization gap becomes larger when the number of \(T\) increases, resulting in the over-fitting phenomenon. Thus, early stop may be beneficial for yielding a smaller generalization gap, which is widely adopted in implementation of modern GNNs (Kipf and Welling, 2017; Chen et al., 2020). It can be seen that the generalization gap is positively related to the Lipschitz continuity constant \(L_{\mathcal{F}}\) determined by specific network architecture \(\mathcal{F}\). Thus, larger \(L_{\mathcal{F}}\) leads to larger upper bounds of generalization gap, showing that the network architecture of GNN also have a significant influence on the generalization gap (See Section 4.2 for more detail). The upper bound of generalization gap in (Cong et al., 2021) also increase with \(T\) when the objective is optimized by full-batch gradient descent. This is not surprise since it can be seen as a special case of SGD where the batch size is equal to the size of traning samples.

Our second main result is high probability bounds of the gradients on training and test data.

**Theorem 4.5**.: _Suppose Assumptions 3.1, 3.2, 3.4, 3.6, and 3.8 hold. Suppose that the learning rate \(\{\eta_{t}\}\) satisfies \(\eta_{t}=\frac{1}{t+\ell_{0}}\) such that \(t_{0}\geq\max\{(2P)^{1/\alpha},1\}\). For any \(\delta\in(0,1)\), with probability \(1-\delta\),_

1. _If_ \(\alpha\in(0,\frac{1}{2})\)_, we have_ \[\Big{\|}\nabla R_{m}(\mathbf{w}^{(T+1)})-\nabla R_{u}(\mathbf{w}^ {(T+1)})\Big{\|}_{2}\] \[= \mathcal{O}\bigg{(}\frac{(m+u)^{\frac{3}{2}}}{mu}\log^{\frac{1}{ 2}}(T)T^{\frac{1-2\alpha}{2}}\log\bigg{(}\frac{1}{\delta}\bigg{)}\bigg{)}.\]
_._
2. _If_ \(\alpha=\frac{1}{2}\)_, we have_ \[\left\|\nabla R_{m}(\mathbf{w}^{(T+1)})-\nabla R_{u}(\mathbf{w}^{(T+ 1)})\right\|_{2}\] \[= \mathcal{O}\bigg{(}\frac{(m+u)^{\frac{3}{2}}}{mu}\log(T)\log\left( \frac{1}{\delta}\right)\bigg{)}.\]
3. _If_ \(\alpha\in(\frac{1}{2},1]\)_, we have_ \[\left\|\nabla R_{m}(\mathbf{w}^{(T+1)})-\nabla R_{u}(\mathbf{w}^ {(T+1)})\right\|_{2}\] \[= \mathcal{O}\bigg{(}\frac{(m+u)^{\frac{3}{2}}}{mu}\log^{\frac{1}{ 2}}(T)\log\left(\frac{1}{\delta}\right)\bigg{)}.\]

_Remark 4.6_.: Theorem 4.5 provides high probability bounds for the generalization gap of gradients under transductive setting. Overall, the generalization gap we derive is still of order \(\mathcal{O}\left((\frac{1}{m}+\frac{1}{u})\sqrt{m+u}\right)\), which is applicable in real-world large-scale graph dataset. Besides, the generalization gap of gradients increases with the increase of \(T\), showing that a smaller number of iterations helps achieving a smaller generalization gap of gradients.

Since the generalization performance is determined by both training error and generalization gap, we provide a upper bound of the test error under a special case that the objective satisfies the following PL condition.

**Assumption 4.7**.: Suppose that there exists a constant \(\mu\) such that for all \(\mathbf{w}\in\mathcal{W}\),

\[R_{m}(\mathbf{w})-R_{m}(\hat{\mathbf{w}}^{*})\leq\frac{1}{2\mu}\left\|\nabla R _{m}(\mathbf{w})\right\|_{2},\]

holds for the given set \(S\) from \(\mathcal{Z}\).

_Remark 4.8_.: Assumption 4.7 is also named as gradient dominance condition in learning theory studies, indicating that the difference between the optimal training error and the current training error can be upper bounded by the quadratic function of the gradient on training instances. This assumption is widely adopted in nonconvex learning (Zhou et al., 2018; Xu and Zeevi, 2020; Lei and Tang, 2021; Li and Liu, 2021), and has been verified in over-parameterized systems including wide neural networks (Liu et al., 2020). This assumption only appears in Theorem 4.9.

**Corollary 4.9**.: _Suppose Assumptions 3.1, 3.2, 3.4, 3.6, 3.8, and 4.7 hold. Suppose that the learning rate \(\{\eta_{t}\}\) satisfies \(\eta_{t}=\frac{2}{\mu(t+t_{0})}\) such that \(t_{0}\geq\max\{\frac{2}{\mu}(2P)^{\frac{1}{\alpha}},1\}\). For any \(\delta\in(0,1)\), with probability \(1-\delta\),_

1. _If_ \(\alpha\in(0,\frac{1}{2})\)_, we have_ \[R_{u}(\mathbf{w}^{(T+1)})-R_{m}(\mathbf{w}^{*})\] \[= \mathcal{O}\bigg{(}L_{\mathcal{F}}\frac{(m+u)^{\frac{3}{2}}}{mu} \log^{\frac{1}{2}}(T)T^{\frac{1}{2}-\alpha}\log\left(\frac{1}{\delta}\right)+ \frac{1}{T^{\alpha}}\bigg{)},\]
2. _If_ \(\alpha=\frac{1}{2}\)_, we have_ \[R_{u}(\mathbf{w}^{(T+1)})-R_{m}(\mathbf{w}^{*})\] \[= \mathcal{O}\bigg{(}L_{\mathcal{F}}\frac{(m+u)^{\frac{3}{2}}}{mu} \log(T)\log\left(\frac{1}{\delta}\right)+\frac{1}{T^{\alpha}}\bigg{)}.\]
3. _If_ \(\alpha\in(\frac{1}{2},1)\)_, we have_ \[R_{u}(\mathbf{w}^{(T+1)})-R_{m}(\mathbf{w}^{*})\] \[= \mathcal{O}\bigg{(}L_{\mathcal{F}}\frac{(m+u)^{\frac{3}{2}}}{mu} \log^{\frac{1}{2}}(T)\log(1/\delta)+\frac{1}{T^{\alpha}}\bigg{)}.\]
4. _If_ \(\alpha=1\)_, we have_ \[R_{u}(\mathbf{w}^{(T+1)})-R_{u}(\mathbf{w}^{*})\] \[= \mathcal{O}\bigg{(}L_{\mathcal{F}}\frac{(m+u)^{\frac{3}{2}}}{mu} \log^{\frac{1}{2}}(T)\log(1/\delta)+\frac{1}{T^{\alpha}}\bigg{)}.\]

_Remark 4.10_.: Theorem 4.9 shows that under Assumption 4.7, the test error are determined by the minimal training error, optimization error and generalization gap. The minimal training error reflects how well the model fits data, which is a measure of the expressive ability. The first and the second term in the slack terms are generalization gap and optimization error, respectively. With the increase of \(T\), the generalization gap increase while the optimization error decrease. Therefore, it is necessary to carefully choose a proper number of iterations in order to balance the trade-off between optimization and generalization. In the implementation of most GNNs studies (Kipf and Welling, 2017; Velickovic et al., 2018; Chien et al., 2021; He et al., 2021), early stop is widely adopted and \(T\) is determined by the performance of model on validation set. Thus, our results are consistent with real implementations.

It is worth point out that although the results in this section is oriented to the case that the objective has two parameters (_e.g._, GCN, APPNP, and GPR-GNN in Section 4.2), results for other cases that the objective has one parameter (_e.g._, SGC in Section 4.2) or three parameters (_e.g._, GCNII in Section 4.2) have the same form when neglecting the constant factors. Meanwhile, the assumptions need to be modified correspondingly. Readers are referred to the Appendix for detailed discussion.

### Cases Study of Popular GNNs

We have established high probability bounds for transductive generalization gap in Theorem 4.3. In this part, we analyze the upper bounds of architecture related constant \(L_{\mathcal{F}}\) and \(P_{\mathcal{F}}\), with that the upper bound of generalization gap can be determined. Five representative GNNs, including GCN, GCNII, SGC, APPNP, and GPR-GNN, are selected for analysis. The loss function \(\ell\) is cross-entropy loss and denote
by \(\hat{\mathbf{Y}}\) the prediction. For concise, we do not consider the bias term, since it can be verified that \(\langle\mathbf{w},\mathbf{x}\rangle+b=\langle\tilde{\mathbf{w}},\tilde{\mathbf{x}}\rangle\) holds with \(\tilde{\mathbf{w}}=[\mathbf{w};b]\) and \(\tilde{\mathbf{x}}=[\mathbf{x};1]\).

**GCN.** The work (Kipf and Welling, 2017) proposes to aggregate features from one-hop neighbor nodes. The feature propagation process of a two-layer GCN model is

\[\hat{\mathbf{Y}}=\mathrm{Softmax}\big{(}g(\tilde{\mathbf{A}})\sigma(g(\tilde{ \mathbf{A}})\mathbf{X}\mathbf{W}_{1})\mathbf{W}_{2}\big{)}, \tag{3}\]

where \(g(\tilde{\mathbf{A}})=\tilde{\mathbf{A}}\) and \(\mathbf{W}_{1}\in\mathbb{R}^{d\times h},\mathbf{W}_{2}\in\mathbb{R}^{h\times |\mathcal{Y}|}\) are parameters.

**Proposition 4.11**.: _Suppose Assumptions 3.1, 3.2, and 3.4 hold, then the objective \(\ell(\mathbf{w};z)\) is \(L_{\mathcal{F}}\)-Lipschitz continuous and Holder smooth w.r.t. \(\mathbf{w}=[\mathrm{vec}\left[\mathbf{W}_{1}\right];\mathrm{vec}\left[ \mathbf{W}_{1}\right]]\). Concretely, the Lipschitz continuity constant \(L_{\mathcal{F}}\) is \(L_{\mathrm{GCN}}=2c_{X}c_{W}\big{\|}\tilde{\mathbf{A}}\big{\|}_{\infty}^{2}\)._

Due to the tedious formulation, we provide the concrete value of \(P_{\mathcal{F}}\) in the Appendix. Proposition 4.11 demonstrates that \(L_{\mathrm{GCN}}\) mainly depends on factors \(\|g(\tilde{\mathbf{A}})\|_{\infty}\), \(c_{X}\), and \(c_{W}\). Let \(\mathrm{deg}_{\min}\) and \(\mathrm{deg}_{\max}\) be the minimum and maximum node degree, respectively. By Lemma A.1 in Appendix A,

\[\big{\|}\tilde{\mathbf{A}}\big{\|}_{\infty}\leq\sqrt{\frac{\mathrm{deg}_{ \max}+1}{\mathrm{deg}_{\min}+1}}. \tag{4}\]

It can be found that the generalization gap decreases with the decrease of the maximum node degree, which could be achieved by removing edges. This explains in some sense why the DropEdge (Rong et al., 2020) technique is beneficial for alleviating the over-fitting problem from the perspective of learning theory. Besides, for GCN trained on sampled sub-graphs \(\{\mathcal{G}_{i}\}_{i=1}^{n}\), the Lipschitz continuity constant is \(L_{\mathrm{GCN}}=2c_{X}c_{W}\max_{i\in[n]}\big{\|}\tilde{\mathbf{A}}^{[i]} \big{\|}_{\infty}^{2}\), where \(\tilde{\mathbf{A}}^{[i]}\) is the normalized adjacency matrix with self-loop of \(\mathcal{G}_{i}\). Since only a portion of neighboring nodes are preserved during sub-graphs sampling (Hamilton et al., 2017; Zeng et al., 2020; 2021), the maximum node degree of each sub-graph is smaller than that of initial graph, implying \(\max_{i\in[n]}\big{\|}\tilde{\mathbf{A}}^{[i]}\big{\|}_{\infty}\leq\big{\|} \tilde{\mathbf{A}}\big{\|}_{\infty}\) holds. Thus, Proposition 4.11 shows that training on sampled sub-graphs are beneficial to achieve smaller generalization gap. Lastly, the spectral norm of learning parameters also has an effect on the generalization gap. Thus, the commonly used \(L_{2}\) regularization technique is beneficial to reduce the generalization gap.

**GCNII.** The authors in (Chen et al., 2020) propose to relieve over-smoothing by initial residual and identity mapping. Denote by \(\mathbf{H}^{(0)}=\sigma(\mathbf{X}\mathbf{W}_{0})\) the initial representation. The forward propagation of a two-layer GCNII model is

\[\mathbf{H}^{(1)} =\sigma\Big{(}((1-\alpha_{1})g(\tilde{\mathbf{A}})\mathbf{H}^{( 0)}+\alpha_{1}\mathbf{H}^{(0)})\Psi(\beta_{1},\mathbf{W}_{1})\Big{)},\] \[\mathbf{H}^{(2)} =\sigma\Big{(}((1-\alpha_{1})g(\tilde{\mathbf{A}})\mathbf{H}^{(1 )}+\alpha_{1}\mathbf{H}^{(0)})\Psi(\beta_{2},\mathbf{W}_{2})\Big{)},\] \[\hat{\mathbf{Y}} =\mathrm{softmax}\big{(}\mathbf{H}^{(2)}\mathbf{W}_{3}\big{)},\]

where \(\Psi(\beta,\mathbf{W})=(1-\beta)\mathbf{I}+\beta\mathbf{W}\) and \(g(\tilde{\mathbf{A}})=\tilde{\mathbf{A}}\). \(\mathbf{W}_{1}\in\mathbb{R}^{d\times h}\), \(\mathbf{W}_{2}\in\mathbb{R}^{h\times h}\), and \(\mathbf{W}_{3}\in\mathbb{R}^{h\times|\mathcal{Y}|}\) are parameters.

**Proposition 4.12**.: _Suppose Assumptions 3.1, 3.2, and 3.4 hold, then the objective \(\ell(\mathbf{w};z)\) is \(L_{\mathcal{F}}\) Lipschitz continuous and Holder smooth w.r.t. \(\mathbf{w}=[\mathrm{vec}\left[\mathbf{W}_{0}\right];\mathrm{vec}\left[ \mathbf{W}_{1}\right];\mathrm{vec}\left[\mathbf{W}_{2}\right];\mathrm{vec} \left[\mathbf{W}_{3}\right]]\)._

_Specifically, denote by \(C_{\ell}=1-\beta_{\ell}+\beta_{\ell}c_{W},\ell\in[2]\) and_

\[B_{1} =c_{X}c_{W}C_{1}\big{(}(1-\alpha_{1})\big{\|}\tilde{\mathbf{A}} \big{\|}_{\infty}+\alpha_{1}\big{)},\] \[B_{2} =\big{(}(1-\alpha_{2})B_{1}\big{\|}\tilde{\mathbf{A}}\big{\|}_{ \infty}+\alpha_{2}c_{X}c_{W}\big{)}C_{2},\] \[L_{1} =2\bigg{(}2+\frac{c_{W}^{2}\beta_{2}^{2}}{C_{2}^{2}}\bigg{)}B_{2}^ {2}, \tag{5}\] \[L_{2} =2(1-\alpha_{2})^{2}\beta_{1}^{2}c_{W}^{2}\big{\|}\tilde{\mathbf{A }}\big{\|}_{\infty}^{2}\bigg{(}\frac{B_{1}^{2}C_{2}^{2}}{C_{1}^{2}}\bigg{)}.\]

_The Lipschitz continuity constant is \(L_{\mathrm{GCNII}}=\sqrt{L_{1}+L_{2}}\)._

Proposition 4.12 shows that \(L_{\mathrm{GCNII}}\) is a function of \(\{\alpha_{i}\}_{i=1}^{2}\) and \(\{\beta_{i}\}_{i=1}^{2}\). Finding the optimal value of \(L_{\mathrm{GCNII}}\) is a quadratic programming problem with constrain \(\alpha_{1},\alpha_{2}\in[0,1]\) and \(\beta_{1},\beta_{2}\in[0,1]\). Now we discuss a special case that \(\alpha_{1}=\alpha_{2}=0\) and \(\beta_{1}=\beta_{2}=0\). In this case, we have \(L_{1}=4c_{X}^{2}c_{W}^{2}\big{\|}\tilde{\mathbf{A}}\big{\|}_{\infty}^{4}\) and \(L_{2}=0\), which implies that \(L_{\mathrm{GCNII}}=L_{\mathrm{GCN}}\). Note that the optimal value of \(L_{\mathrm{GCNII}}\) is no larger than any value of objective function over the feasible region. Therefore, we conclude that the value of \(L_{\mathrm{GCNII}}\) is no higher than \(L_{\mathrm{GCN}}\). This result is not surprise, since GCNII is a special GCN model under this setting. For proper value of \(\{\alpha_{i}\}_{i=1}^{2}\) and \(\{\beta_{i}\}_{i=1}^{2}\), GCNII could achieve smaller generalization gap than GCN. As GCNII can achieve lower training error by relieving the over-smoothing problem, Proposition 4.12 indicates that GCNII can achieve superior performance when hyperparameters are set properly. Due to the involve of \(\{\alpha_{i}\}_{i=1}^{2}\) and \(\{\beta_{i}\}_{i=1}^{2}\), the growth rate of \(L_{\mathrm{GCNII}}\) is much smaller than \(L_{\mathrm{GCN}}\) when propagation depth increases, which makes GCNII maintain generalization capability and achieve stale performance (See Section 5).

**SGC.** The work (Wu et al., 2019) proposes to remove all the nonlinear activation in GCN. To facilitate comparison with GCN, we consider a two layers SGC model, whose propagation is given by

\[\hat{\mathbf{Y}}=\mathrm{softmax}\big{(}g(\tilde{\mathbf{A}})\mathbf{X}\mathbf{W }_{1}\mathbf{W}_{2}\big{)}, \tag{6}\]

where \(g(\tilde{\mathbf{A}})=\tilde{\mathbf{A}}^{2}\). \(\mathbf{W}_{1}\in\mathbb{R}^{d\times h}\) and \(\mathbf{W}_{2}\in\mathbb{R}^{h\times|\mathcal{Y}|}\) is the parameter.

**Proposition 4.13**.: _Suppose Assumption 3.1, 3.2, and 3.4 hold, then the objective \(\ell(\mathbf{w};z)\) is \(L_{\mathcal{F}}\)-Lipschitz continuous and Holder smooth w.r.t. \(\mathbf{w}=[\mathrm{vec}\left[\mathbf{W}_{1}\right];\mathrm{vec}\left[ \mathbf{W}_{2}\right]]\). Specifically, the Lipschitz continuity constant \(L_{\mathcal{F}}\) is \(L_{\mathrm{SGC}}=2c_{X}c_{W}\big{\|}\tilde{\mathbf{A}}^{2}\big{\|}_{\infty}\)._
Since \(\left\|\tilde{\mathbf{A}}^{2}\right\|_{\infty}\leq\left\|\tilde{\mathbf{A}} \right\|_{\infty}^{2}\), we have \(L_{\mathrm{SGC}}\leq L_{\mathrm{GCN}}\). Surprisingly, this simple linear model can achieve better smaller generalization gap than those nonlinear models (Kipf and Welling, 2017; Chen et al., 2020; Gasteiger et al., 2019; Chien et al., 2021), even though its representation ability is inferior than them. Note that the performance on test samples is determined by both training error and generalization gap. If linear GNNs can achieve a small training error, it is natural that they can achieve comparable and even better performance than nonlinear GNNs on test samples. Therefore, Proposition 4.13 reveals why linear GNNs achieve better performance than nonlinear GNNs from learning theory, as observed in recent works (Wu et al., 2019; Zhu and Koniusz, 2021; Wang et al., 2021). Considering the efficiency and scalability of linear GNNs on large-scale datasets, we believe that they have much potential to be exploited.

**APPNP.** Multi-scale features are aggregated via personalized PageRank schema in (Gasteiger et al., 2019). Formally, the feature propagation process is formulated as

\[\hat{\mathbf{Y}}=\mathrm{softmax}\big{(}g(\tilde{\mathbf{A}})\sigma(\sigma( \mathbf{X}\mathbf{W}_{1})\mathbf{W}2)\big{)}, \tag{7}\]

where \(g(\tilde{\mathbf{A}})=\sum_{k=0}^{K-1}\gamma(1-\gamma)^{k}\tilde{\mathbf{A}}^ {k}+(1-\gamma)^{K}\tilde{\mathbf{A}}^{K}\). \(\mathbf{W}_{1}\in\mathbb{R}^{d\times h}\) and \(\mathbf{W}_{2}\in\mathbb{R}^{h\times|\mathcal{Y}|}\) are the parameters.

**Proposition 4.14**.: _Suppose Assumption 3.1, 3.2, and 3.4 hold, then the objective \(\ell(\mathbf{w};z)\) is \(L_{\mathcal{F}}\)-Lipschitz continuous and Holder smooth w.r.t. \(\mathbf{w}=\left[\mathrm{vec}\left[\mathbf{W}_{1}\right];\mathrm{vec}\left[ \mathbf{W}_{2}\right]\right]\). Concretely, the Lipschitz continuity constant \(L_{\mathcal{F}}\) is \(L_{\mathrm{APPNP}}=2c_{X}c_{W}\big{\|}g(\tilde{\mathbf{A}})\big{\|}_{\infty}\)._

The Lipschitz continuity constant in Proposition 4.14 is positively related to the infinity matrix norm of the polynomial spectral filter. According to (Gasteiger et al., 2019), \(\gamma\) is commonly set to be a small number, yielding that \(\big{\|}g(\tilde{\mathbf{A}})\big{\|}_{\infty}<\left\|\tilde{\mathbf{A}} \right\|_{\infty}\) holds. Thus, the Lipschitz continuity constant of APPNP is smaller than that of GCN, indicating that APPNP may achieve smaller generalization gap than GCN. Besides, \(K\) also affects the value of \(\|g(\tilde{\mathbf{A}})\|_{\infty}\), and a larger \(K\) may yield a larger generalization gap. Therefore, \(K\) is usually set as a proper value to guarantee a trade-off between expressive ability and generalization performance.

**GPR-GNN.** Compared with APPNP, the fixed coefficients are replaced by learnable weights in (Chien et al., 2021), in order to adaptively simulate both high-pass and low-pass graph filters. The feature propagation process is

\[\hat{\mathbf{Y}}=\big{(}g(\tilde{\mathbf{A}},\mathbf{\gamma})\sigma(\sigma( \mathbf{X}\mathbf{W}_{1})\mathbf{W}2)\big{)}, \tag{8}\]

where \(g(\tilde{\mathbf{A}},\mathbf{\gamma})=\sum_{k=0}^{K}\gamma_{k}\tilde{\mathbf{A}}^ {k}\). \(\mathbf{W}_{1}\in\mathbb{R}^{d\times h}\), \(\mathbf{W}_{2}\in\mathbb{R}^{h\times|\mathcal{Y}|}\) and \(\mathbf{\gamma}\in\mathbb{R}^{K+1}\) are the parameters.

**Proposition 4.15**.: _Suppose Assumption 3.1, 3.2, and 3.4 hold, then the objective \(\ell(\mathbf{w};z)\) is \(L_{\mathcal{F}}\)-Lipschitz continuous and Holder smooth w.r.t. \(\mathbf{w}=\left[\mathrm{vec}\left[\mathbf{W}_{1}\right];\mathrm{vec}\left[ \mathbf{W}_{2}\right];\mathbf{\gamma}\right]\). Concretely, the Lipschitz continuity constant \(L_{\mathcal{F}}\) is \(L_{\mathrm{GPR}}=\sqrt{L_{1}^{2}+L_{2}^{2}}\), where_

\[L_{1} =\sqrt{2}c_{X}c_{W}^{2}\bigg{(}\sum_{k=0}^{K}\big{\|}\tilde{ \mathbf{A}}^{k}\big{\|}_{\infty}\bigg{)}, \tag{9}\] \[L_{2} =2c_{X}c_{W}\big{\|}g(\tilde{\mathbf{A}},\mathbf{\gamma})\big{\|}_{ \infty}.\]

Note that \(L_{2}\) has similar form with \(L_{\mathrm{APPNP}}\) (the only difference lie on the definition of \(g(\tilde{\mathbf{A}},\mathbf{\gamma})\)). Assume that \(g(\tilde{\mathbf{A}},\mathbf{\gamma})=g(\tilde{\mathbf{A}})\) and note that \(L_{\mathrm{GPR}}=\sqrt{L_{1}^{2}+L_{2}^{2}}\geq L_{2}\), we have \(L_{\mathrm{GPR}}\geq L_{\mathrm{APPNP}}\). Besides, since there is no constraint on \(\gamma\), the value of \(\big{\|}g(\tilde{\mathbf{A}},\mathbf{\gamma})\big{\|}_{\infty}\) may be larger when the norm of \(\mathbf{\gamma}\) is large, resulting in larger generalization gap than APPNP. Therefore, adopting regularization technique on the learnable coefficients to restrict the value of \(\big{\|}g(\tilde{\mathbf{A}},\mathbf{\gamma})\big{\|}_{\infty}\) is necessary.

To summarize, \(L_{\mathcal{F}}\) and \(P_{\mathcal{F}}\) are determined by the feature propagation process and graph-structured data. Estimating these constants precisely is challenging (Virmaux and Scaman, 2018; Fazlyab et al., 2019), and the upper bounds we provided are sufficient to reflect the realistic generalization gap of these models (See Section 5 for more detail). Besides, we have to emphasize that results for GCN and GCNII with more than two layers can be derived by similar techniques, yet it requires more tedious computation. Exploring new techniques to estimate these constants conveniently and precisely are left for future work.

## 5 Experiments

**Experimental Setup.** We conduct experiments on widely adopted benchmark datasets, including Cora, Citeseer, and Pubmed (Sen et al., 2008; Yang et al., 2016). The accuracy and loss gap (_i.e._, the absolute value of difference between the loss (accuracy) on training and test samples) are used to estimate the generalization gap. Following the standard transductive learning setting, in each run, \(30\%\) sampled nodes determined by a random seed are used as training set and the rest nodes are treated as test set. The number of iterations is fixed to \(T=300\). We independently repeat the experiments for \(10\) times and report the mean value and standard deviations of all runs. Please see Appendix C for more detailed settings.

**Experimental Results.** The loss and accuracy comparisons are presented in Table 3 and Table 1, respectively. We have the following observations: (1) SGC and APPNP have smaller loss and accuracy gap than other model including GCN, which is consistent with the analysis in Proposition 4.13. Besides, the test accuracy of SGC surpass GCN on Citeseer. Thus, the reason why linear models sometimes perform is due to their smaller lipschitz continuity constants. (2) Compared with GCN, GCNII achieves smaller loss and
accuracy gap with the same number of layers. We further estimate the generalization performance of GCN and GCNII with six layers (denoted as GCN* and GCNII*). Interestingly, with the increase of the number of hidden layers, the generalization performance of GCN decreases sharply. On the contrary, the loss and accuracy gap of GCNII remain unchanged. The test accuracy of GCNII also remain unchanged or only drops slightly. Therefore, the superior performance of GCNII comes from two perspectives: the first is learning non-degenerated representations by relieving over-smoothing and the second is robust generalization gap against the increase of the number of layers. (3) Although GPR-GNN achieve a competitive test accuracy, it has higher accuracy and loss gap than APPNP. Therefore, the unconstrained learning coefficients improve the fitting ability but also weaken generalization capability. Designing weight learning schema to balance the expressive and generalization could be a direction for spectral-based GNNs. (4) The generalization performance of GAT is slightly worse than GCN. Note that GAT is designed for inductive learning while our experimental setting is transductive. Thus, the superiority of GAT is not so obvious.

Besides, loss value of GCN on training and test samples w.r.t. iterations are presented in Figure 1. It can be seen that the loss gap increases with the increase of iterations, as demonstrated by Theorem 4.3. In general, the theoretical results are supported by the experimental results. It is worth pointing out that our analysis is only oriented to generalization gap. Smaller generalization gap does not necessarily mean better generalization ability, since the performance on test samples are determined by both training error and generalization gap.

## 6 Discussion and Conclusion

In this paper, we establish high probability learning guarantees for transductive SGD, by which the upper bound of generalization gap for some popular GNNs are derived. Experimental results on benchmark datasets support the theoretical results. This work sheds light on understanding the generalization of GNNs and provide some insights in

\begin{table}
\begin{tabular}{l c c c} \hline \hline  & Cora & Citeseer & Pubmed \\ \hline GCN & 9.76\(\pm\)1.15 & 22.11\(\pm\)1.26 & 1.08\(\pm\)0.52 \\ GCN* & 13.45\(\pm\)1.28 & 26.48\(\pm\)1.21 & 1.49\(\pm\)0.63 \\ GAT & 11.00\(\pm\)0.75 & 22.69\(\pm\)0.84 & 1.52\(\pm\)0.43 \\ GCNII & 7.69\(\pm\)1.48 & 14.85\(\pm\)0.80 & 0.88\(\pm\)0.52 \\ GCNII* & 6.24\(\pm\)1.59 & 13.49\(\pm\)1.39 & 0.80\(\pm\)0.50 \\ SGC & 5.33\(\pm\)1.58 & 11.50\(\pm\)1.09 & 0.73\(\pm\)0.54 \\ APPNP & 7.72\(\pm\)1.54 & 9.99\(\pm\)1.17 & 0.85\(\pm\)0.46 \\ GPR-GNN & 8.90\(\pm\)1.22 & 19.08\(\pm\)0.95 & 0.96\(\pm\)0.49 \\ \hline \hline \end{tabular}
\end{table}
Table 1: Accuracy gap comparison of different baseline models on Cora, Citeseer and Pubmed.

\begin{table}
\begin{tabular}{l c c c} \hline \hline  & Cora & Citeseer & Pubmed \\ \hline GCN & 85.91\(\pm\)0.53 & 71.78\(\pm\)0.72 & 85.29\(\pm\)0.19 \\ GCN* & 82.49\(\pm\)0.59 & 66.74\(\pm\)1.07 & 84.21\(\pm\)0.26 \\ GAT & 86.10\(\pm\)0.51 & 72.90\(\pm\)0.65 & 85.45\(\pm\)0.26 \\ GCNII & 82.85\(\pm\)2.17 & 73.61\(\pm\)0.64 & 84.70\(\pm\)0.24 \\ GCNII* & 82.85\(\pm\)2.44 & 72.89\(\pm\)0.96 & 83.67\(\pm\)0.46 \\ SGC & 82.39\(\pm\)2.48 & 74.37\(\pm\)0.56 & 82.00\(\pm\)0.27 \\ APPNP & 79.14\(\pm\)3.17 & 74.12\(\pm\)0.62 & 82.86\(\pm\)0.29 \\ GPR-GNN & 87.24\(\pm\)0.71 & 73.79\(\pm\)0.67 & 85.07\(\pm\)0.34 \\ \hline \hline \end{tabular}
\end{table}
Table 2: Test accuracy comparison of different baseline models on Cora, Citeseer and Pubmed.

Figure 1: The loss value of GCN on training and test samples with the increase of iterations.

\begin{table}
\begin{tabular}{l c c c} \hline \hline  & Cora & Citeseer & Pubmed \\ \hline GCN & 0.30\(\pm\)0.03 & 0.77\(\pm\)0.04 & 0.03\(\pm\)0.01 \\ GCN* & 0.91\(\pm\)0.18 & 2.12\(\pm\)0.16 & 0.05\(\pm\)0.01 \\ GAT & 0.29\(\pm\)0.03 & 0.65\(\pm\)0.02 & 0.03\(\pm\)0.01 \\ GCNII & 0.19\(\pm\)0.03 & 0.43\(\pm\)0.02 & 0.02\(\pm\)0.01 \\ GCNII* & 0.16\(\pm\)0.03 & 0.43\(\pm\)0.03 & 0.02\(\pm\)0.01 \\ SGC & 0.12\(\pm\)0.03 & 0.28\(\pm\)0.02 & 0.01\(\pm\)0.00 \\ APPNP & 0.16\(\pm\)0.03 & 0.25\(\pm\)0.02 & 0.01\(\pm\)0.00 \\ GPR-GNN & 0.24\(\pm\)0.03 & 0.55\(\pm\)0.02 & 0.02\(\pm\)0.00 \\ \hline \hline \end{tabular}
\end{table}
Table 3: Loss gap comparison of different baseline models on Cora, Citeseer and Pubmed.
designing new GNN architecture with both expressiveness and generalization capabilities.

Although we have made efforts in generalization theory of GNNs, there are still some limitations in our analysis, which is left for future work to address: (1) The complexity based technique makes the dimension of parameters appearing in the bounds. Further research should focus on establishing dimension-independent bounds under milder assumption and deriving the lower bound that matches the upper bound. (2) We only analyze vanilla SGD in terms of optimization algorithms. Extending our results to SGD with momentum and adaptive learning rates is worth exploring. (3) Our analysis does not explicitly consider the heterophily of graphs. Deriving heterophily-dependent generalization bounds is an meaningful direction.
