Deeper Insights into Deep Graph Convolutional Networks: Stability and Generalization

Let $\mathcal{G}=(\mathcal{V},\mathcal{E},\mathbf{A})$ denote an undirected graph with a node set $\mathcal{V}$ of size $N$, an edge set $\mathcal{E}$ and the adjacency matrix $\mathbf{A}\in\mathbb{R}^{N\times N}$. As usual, $\mathbf{L}:=\mathbf{D}-\mathbf{A}$ is denoted as its conventional graph Laplacian, where $\mathbf{D}\in\mathbb{R}^{N\times N}$ signifies the degree diagonal matrix. Furthermore, $g(\mathbf{L})\in\mathbb{R}^{N\times N}$ represents a graph filter and is defined as a function of $\mathbf{L}$ (or its normalized versions). We denote by $C_{g}=\|g(\mathbf{L})\|_{2}$ the maximum absolute eigenvalue of a symmetric filter $g(\mathbf{L})$ or the maximum singular value of an asymmetric $g(\mathbf{L})$.

We denote by $\mathbf{X}=(\mathbf{x}_{1},\mathbf{x}_{2},\dots,\mathbf{x}_{N})^{\top}\in\mathbb{R}^{N\times d_{0}}$ the input features ($d_{0}$ stands for input dimension) and $\mathbf{x}_{j}\in\mathbb{R}^{d_{0}}$ the node feature of node $j$, while $C_{\mathbf{X}}=\|\mathbf{X}\|_{F}$ represents the Frobenius norm of $\mathbf{X}$. For the input feature $\mathbf{X}$, a deep GCN with $g(\mathbf{L})$ updates the representation as follows:

where $\mathbf{X}^{(k)}\in\mathbb{R}^{N\times d_{k}}$ is the output feature matrix of the $k$-th layer with $\mathbf{X}^{(0)}=\mathbf{X}$, the matrix $\mathbf{W}^{(k)}\in\mathbb{R}^{d_{k-1}\times d_{k}}$ represents the trained parameter matrix specific to the $k$-th layer. The function $\sigma(\cdot)$ denotes a nonlinear activation function applied within the GCN model. For simplicity, we set a final output in a single dimension, that is, the final output label of $N$ nodes is given by

where $\mathbf{y}\in\mathbb{R}^{N}$ and $\mathbf{w}\in\mathbb{R}^{d_{K}}$.

As defined above, the deep GCN (1) with learnable parameters

is a $K+1$ layers GCN with $K$ hidden layers and a final output layer, and in the case of $K=0$, it degenerates into the single-layer GCN studied in [36].

We denote by $\mathcal{D}$ the unknown joint distribution of input features and output labels. Let

be the training set i.i.d sampled from $\mathcal{D}$ and $\mathcal{A}_{\mathcal{S}}$ be a learning algorithm for a deep GCN trained on $\mathcal{S}$. For a deep GCN model (1) with parameters $\theta=\{\mathbf{W}^{(1)},\dots,\mathbf{W}^{(K)},\mathbf{w}\}$, denote $\mathcal{A}_{\mathcal{S}}(\mathbf{x})=f(\mathbf{x}|\theta_{S})=\sigma\big{(}\boldsymbol{\delta}_{\mathbf{x}}^{\top}g(\mathbf{L})\mathbf{X}^{(K)}\mathbf{w}\big{)}$ as the output of node $\mathbf{x}$, where $\theta_{S}$ is the corresponding learned parameter and $\boldsymbol{\delta}_{\mathbf{x}}$ is the indicator vector with respect to node $\mathbf{x}$. For a loss function $\ell:\mathbb{R}\times\mathbb{R}\to\mathbb{R}_{+}$, the generalization error or risk $R(\mathcal{A}_{\mathcal{S}})$ is defined by

where the expectation is taken over $\mathbf{z}=(\mathbf{x},y)\sim\mathcal{D}$, and the empirical error or risk $R_{emp}(\mathcal{A}_{\mathcal{S}})$ is

When considering a randomized algorithm $\mathcal{A}_{\mathcal{S}}$,

gives the generalization gap between the generalization error and the empirical error, where the expectation $\mathbb{E}_{\mathcal{A}}$ corresponds to the inherent randomness of $\mathcal{A}_{\mathcal{S}}$.

In this paper, $\mathcal{A}_{\mathcal{S}}$ is considered to be the algorithm given by the SGD algorithm. Following the approach employed in [36], our analysis focuses solely on the randomness inherent in $\mathcal{A}_{\mathcal{S}}$ arising from the SGD algorithm, while disregarding the stochasticity introduced by parameter initialization. The SGD algorithm for a deep GCN(1) aims to optimize its empirical error on a dataset $\mathcal{S}$ by updating parameters iteratively. For $t\in\mathbb{N}$ and considering the parameters $\theta_{t-1}$ obtained after $t-1$ iterations, the $t$-th iteration of SGD involves randomly drawing a sample $(\mathbf{x}_{t},y_{t})$ from the dataset $\mathcal{S}$. Subsequently, parameters $\theta$ are iteratively updated as follows:

with the learning rate $\eta>0$.

For the sake of estimating the generalization gap $\epsilon_{gen}(\mathcal{A}_{\mathcal{S}})$ of $\mathcal{A}_{\mathcal{S}}$, we invoke the notion of uniform stability of $\mathcal{A}_{\mathcal{S}}$ as adopted in [52, 36].

Let

be the dataset obtained by removing the $i$-th data point in $\mathcal{S}$, and

the dataset obtained by replacing the $i$-th data point in $\mathcal{S}$. Then, the formal definition of uniform stability of a randomized algorithm $\mathcal{A}_{\mathcal{S}}$ is given in the following.

As shown in Definition 1, $\mu_{m}$ indicates a bound on how much the variation of the training set $\mathcal{S}$ can influence the output of $\mathcal{A}_{\mathcal{S}}$. It further implies the following property:

where $\mathbf{z}=(\mathbf{x},y)\sim\mathcal{D}$, $\hat{y}=f(\mathbf{x}|\theta_{S})$ and $\hat{y}^{\prime}=f(\mathbf{x}|\theta_{\mathcal{S}^{i}})$.

Moreover, it is shown that the uniform stability of a learning algorithm $\mathcal{A}_{\mathcal{S}}$ can yield the following upper bound on the generalization gap $\epsilon_{gen}(\mathcal{A}_{\mathcal{S}})$.

First, we make some assumptions about the considered deep GCN model (1), which are necessary to derive our results.

Assumption 1. The activation function $\sigma:\mathbb{R}\rightarrow\mathbb{R}$ is assumed to satisfy the following:

1. 1.

   $\alpha_{\sigma}$-Lipschitz:

   $$|\sigma(x)-\sigma(y)|\leq\alpha_{\sigma}|x-y|,~{}~{}\forall~{}x,y\in\mathbb{R}.$$

2. 2.

   $\nu_{\sigma}$-smooth:

   $$|\nabla\sigma(x)-\nabla\sigma(y)|\leq\nu_{\sigma}|x-y|,~{}~{}\forall~{}x,y\in\mathbb{R}.$$

3. 3.

   $\sigma(0)=0$.

With these assumptions, the derivative of $\sigma$, denoted by $\nabla\sigma$, is bounded, i.e., $|\nabla\sigma|\leq\alpha_{\sigma}$, and thus $\|\nabla\sigma(\mathbf{X})\|_{F}\leq\alpha_{\sigma}\|\mathbf{X}\|_{F}$ holds for any matrix $\mathbf{X}$. It can be easily verified that activation functions such as ELU and tanh satisfy the above assumptions.

Assumption 2. Let $\hat{y}$ and $y$ be the predicted and true labels, respectively. We denote the loss function $\ell:[y_{\min},y_{\max}]\times[y_{\min},y_{\max}]\rightarrow\mathbb{R}$ by $\ell(\hat{y},y)$. Similar to [37], we adopt the following assumptions for $\ell$.

1. 1.

   The loss function $\ell$ exhibits continuity with respect to the variables $(\hat{y},y)$ and possesses continuous differentiability with respect to $\hat{y}$.

2. 2.

   The loss function $\ell$ satisfies $\alpha_{\ell}$-Lipschitz with respect to $\hat{y}$:

   $$|\ell(\hat{y},y)-\ell(\hat{y}^{\prime},y)|\leq\alpha_{\ell}|\hat{y}-\hat{y}^{\prime}|,~{}~{}\forall~{}\hat{y},\hat{y}^{\prime},y\in[y_{\min},y_{\max}].$$

3. 3.

   The loss function $\ell$ meets $\nu_{\ell}$-smooth with respect to $\hat{y}$:

   $$\bigg{|}\frac{\partial\ell}{\partial\hat{y}}(\hat{y},y)-\frac{\partial\ell}{\partial\hat{y}}(\hat{y}^{\prime},y)\bigg{|}\leq\nu_{\ell}|\hat{y}-\hat{y}^{\prime}|,~{}~{}\forall~{}\hat{y},\hat{y}^{\prime},y\in[y_{\min},y_{\max}].$$

With these assumptions, $|\frac{\partial\ell}{\partial\hat{y}}(\hat{y},y)|\leq\alpha_{\ell}$, and $\ell$ is bounded, i.e., $0\leq\ell(\hat{y},y)\leq M$.

Assumption 3. The learned parameters $\{\mathbf{W}^{(1)},\dots,\mathbf{W}^{(K)},\mathbf{w}\}$ during the training procedure with limited iterations satisfies

This section presents the main results of this paper. For convenience, the notations used in the result are summarized in Table 1. Under the assumptions made in Section 4.1, the bound on the generalization gap of deep GCNs is provided in the following theorem.

A fundamental correlation between the generalization gap and the parameters governing deep GCNs is induced by Theorem 1. This correlation implies that the uniform stability of deep GCNs, trained using the SGD algorithm, exhibits an increase with the number of samples when the upper bound approaches zero as the sample size $m$ tends to infinity. Specifically, it is observed that if the value of $C_{g}$ (presenting the largest absolute eigenvalue of a symmetry $g(\mathbf{L})$ or the maximum singular value of an asymmetry $g(\mathbf{L})$) remains unaffected by the size $N$, a generalization gap decaying at the order of $O(1/\sqrt{m})$ is obtained. To compare with the result in [36], let us discuss at length the role of $g(\mathbf{L})$ and the hidden layer number $K$ on the generalization gap.

According to (7) and (8), $\kappa_{1}=O\Big{(}C_{g}^{2K+2}\Big{)}$ and $\kappa_{2}=O\Big{(}C_{g}^{2K+1}\Big{)}$. Therefore, the bound on the generalization gap of deep GCNs in Theorem 1 is

When $K=0$, the GCN model (1) degenerates into the single-layer GCN model considered in [36]. At this point, according to (9), we have

which is the same as the result of [36].

Remarks. Based on (9), we present certain observations regarding the impact of filter $g(\mathbf{L})$ and the hidden layer number $K$ on the generalization capacity of deep GCNs in (1).

• 1.

  Normalized vs. Unnormalized Graph Filters: We examine the three most commonly utilized filters: 1) $g_{1}(\mathbf{L})=\mathbf{A}+\mathbf{I}$, 2) $g_{2}(\mathbf{L})=\mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{-1/2}+\mathbf{I}$, and 3) $g_{3}(\mathbf{L})=\mathbf{D}^{-1}\mathbf{A}+\mathbf{I}$. For the unnormalized filter $g_{1}$, its maximum absolute eigenvalue is bounded by $O(N)$. Consequently, as the value of $m$ approaches the magnitude to $N$, the upper bound indicated by (9) tends towards $O(N^{p})$ for some $p>0$, leading to an impractical upper bound when $N$ become infinitely large. On the contrary, for two normalized filters $g_{2}$ and $g_{3}$, their largest absolute eigenvalues are bounded and independent of graph size $N$. Therefore, both filters yield a diminishing generalization gap at a rate of $O(\frac{1}{\sqrt{m}})$ as $m$ goes to infinity. This discovery underscores the superior performance of normalized filters over unnormalized counterparts in deep GCNs. This observation is consistent with the findings in [36, 37].

• 2.

  The Role of Parameter $K$: It is evident that, when the values of $C_{g}$ and $T$ are fixed, the upper bound (9) exhibits an exponential dependence on parameter $K$. This observation implies that a larger value $K$ leads to an increase in the upper bound of the generalization gap, thereby offering valuable insights for the architectural design of deep GCNs. This finding diverges from the ones presented in [36, 37], as these studies do not account for generic deep GCNs and overlook the significance of the parameter $K$.

Furthermore, based on Theorem 1, we give a brief analysis of the impact of $d_{k}$ (width of the $k$-th layer) on the generalization. Actually, the impact of $d_{k}$ on the generalization is reflected in its impact on $B$. More specifically, let us consider the case where parameters $\{\mathbf{W}^{(1)},\dots,\mathbf{W}^{(K)},\mathbf{w}\}$ belong to the set $\mathcal{X}_{\xi}$, where

i.e., $\mathcal{X}_{\xi}$ is the collection of all matrices whose elements’ absolute values are all less than $\xi$. At this point, for $\mathbf{W}^{(k)}\in\mathbb{R}^{d_{k-1}\times d_{k}}$, we have

Therefore, a larger $d_{k}$ (i.e., width of the $k$-th layer) results in a larger upper bound of $\|\mathbf{W}^{(k)}\|_{2}$, which implies that a larger $d_{k}$ results in a larger $B$ (see Assumption 3 in Section 4.1). Finally, Theorem 1 indicates that a larger $B$ leads to a larger bound on the generalization gap, thus we conclude that a larger $d_{k}$ leads to a larger bound on the generalization gap. To justify this argument, we add some experimental studies in Section 5. The empirical results are consistent with our analysis.

Table 2 offers a concise summary of various upper bounds on the generalization gap, derived through the application of uniform stability. From Table 2, we can see that all the works derive a generalization gap decaying at the order of $O(1/\sqrt{m})$. However, compared to the other three works which only consider shallow GCNs, our work explores the case of deep GCNs. We should point out that the generalization of single-layer GCNs into deep GCNs is not trivial. To derive the results for deep GCNs, we tackle two significant challenges that arise specifically in the context of deep GCNs, which are unique to deep GCNs and are non-existent in single-layer models. The first challenge is the derivation of the gradient of the final output with respect to the learnable parameters across multiple layers, which requires determining how the gradient of the overall error of a GCN is shared among neurons in different hidden layers. In particular, in Appendix A.1, we provide a recursive formula to compute the related gradients. The second challenge is the evaluation of gradient variations between GCNs trained on different datasets. In the single layer case, since the input feature is the same, the variation of the related gradient is only dependent on the variations of learnable parameters. While, in the case of deep GCNs, the variation of the related gradients is also dependent on the variations of the gradients of the final output with respect to the hidden layer outputs. Please see Lemma 7 and its proof for details.

In this subsection, we establish the uniform stability of SGD for deep GCNs, which is the key to further proving Theorem 1.

With a straightforward calculation, one can see that

which decays at the rate of $\frac{1}{m}$ as $m$ tends to infinity. Together with Lemma 1, it yields the result of Theorem 1.

Proof Sketch for Theorem 2. We prove Theorem 2 in the following two steps.

• 1.

  Step 1: We begin by bounding the stability of deep GCNs with respect to perturbations in the learned parameters caused by changes in the training set. The result is given in Lemma 2.

• 2.

  Step 2: Next, we provide a bound for the perturbation of the learned parameters. The result is presented in Theorem 3.

Consider $\mathcal{A}_{\mathcal{S}}$, a set of deepGCNs defined by (1), trained on the dataset $\mathcal{S}$ using SGD for $T$ iterations. Let $\theta_{t}=\{\mathbf{W}^{(1)}_{t},\dots,\mathbf{W}^{(K)}_{t},\mathbf{w}_{t}\}$ and $\theta^{\prime}_{t}=\{\mathbf{W}^{(1)^{\prime}}_{t},\dots,\mathbf{W}^{(K)^{\prime}}_{t},\mathbf{w}^{\prime}_{t}\}$ denote the parameters of two GCNs trained on $\mathcal{S}$ and $\mathcal{S}^{i}$ after $t$ iterations, respectively. We set $\Delta\mathbf{w}_{t}=\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}$ and $\Delta\mathbf{W}^{(k)}_{t}=\mathbf{W}^{(k)}_{t}-\mathbf{W}^{(k)^{\prime}}_{t}$ to be the perturbation of learning parameters and define

In the following lemma, it is shown that the stability of $\mathcal{A}_{\mathcal{S}}$ can be bounded by $\|\triangle\theta_{T}\|_{*}$.

We provide the proof of Lemma 2 in A.2.

Combining (5) and (13), the stability of $\mathcal{A}_{\mathcal{S}}$ has a bound

So, to estimate the uniform stability of $\mathcal{A}_{\mathcal{S}}$, we need to bound $\mathbb{E}_{\mathcal{A}}\big{[}\|\triangle\theta_{T}\|_{*}\big{]}$. Now, let us recall (3) for parameter updating, for training on $\mathcal{S}$,

$k=1,2,\dots,K$, and for training on $\mathcal{S}^{i}$,

$k=1,2,\dots,K$, where $(\mathbf{x}_{t},y_{t})\in\mathcal{S}$ and $(\mathbf{x}^{\prime}_{t},y^{\prime}_{t})\in\mathcal{S}^{i}$ are the samples drawn at the $t$-th SGD iteration. Therefore, $\triangle\theta_{t}=\{\triangle\mathbf{W}^{(1)}_{t},\dots,\triangle\mathbf{W}^{(K)}_{t},\triangle\mathbf{w}_{t}\}$ has the following iterations:

and for $k=1,2,\dots,K$,

Then, we provide two Lemmas to bound

and

in two cases of $(\mathbf{x}_{t},y_{t})=(\mathbf{x}^{\prime}_{t},y^{\prime}_{t})$ and $(\mathbf{x}_{t},y_{t})\neq(\mathbf{x}^{\prime}_{t},y^{\prime}_{t})$, as shown in Lemma 3 and Lemma 4.

The proofs of Lemma 3 and Lemma 4 are given in A.3. Using Lemma 3 and Lemma 4, we now provide a bound for $\mathbb{E}_{\mathcal{A}}\big{[}\|\triangle\theta_{T}\|_{*}\big{]}$.

The proof of Lemma 2 is provided in A.4. Combining (14) and Theorem 3, we obtain that the uniform stability $\mu_{m}$ of $\mathcal{A}_{\mathcal{S}}$ has a bound as

which completes the proof of Theorem 2.