Stability and Generalization of $\ell_{p}$-Regularized Stochastic Learning for GCN

Graph Neural Networks (GNNs) have emerged as a family of powerful model designs for improving the performance of neural network models on graph-structured data. GNNs have delivered remarkable empirical performance from a diverse set of domains, such as social networks, knowledge graphs, and biological networks Duvenaud et al. (2015); Battaglia et al. (2016); Defferrard et al. (2016); Jin et al. (2018); Barrett et al. (2018); Yun et al. (2019); Zhang et al. (2020). In fact, GNNs can be viewed as natural extensions of conventional machine learning for any data where the available structure is given by pairwise relationships.

The architecture designs of various GNNs have been motivated mainly by spectral domain Defferrard et al. (2016); Kipf and Welling (2016a) and spatial domain Hamilton et al. (2017); Gilmer et al. (2017). Some popular variants of graph neural networks include Graph Convolutional Network (GCN) Bruna et al. (2013), GraphSAGE Hamilton et al. (2017), Graph Attention Network Veličković et al. (2017), Graph Isomorphism Network Xu et al. (2018), and among others.

Specifically, inherited excellent performances of traditional convolutional neural networks in processing image and time series, a standard GCN Kipf and Welling (2016a) also consists of a cascade of layers, but operates directly on a graph and induces embedding vectors of nodes based on properties of their neighborhoods. Formally, GCN is defined as the problem of learning filter parameters in the graph Fourier transform. GCNs have shown superior performances on real datasets from various domains, such as node labeling on social networks Kipf and Welling (2016b), link prediction in knowledge graphs Schlichtkrull et al. (2018), and molecular graph classification in quantum chemistry Gilmer et al. (2017).

Notably, a recent study Ma et al. (2021) has proven that GCN, even for general messaging passing models, intrinsically performs the $\ell_{2}$-based graph smoothing signal, which enforces smoothness globally, and the level and smoothness are often shared across the whole graph. As opposed to $\ell_{2}$-based graph smoothing, $\ell_{1}$-based methods tend to penalize large values less and thus preserve discontinuity of non-smooth signal better Nie et al. (2011); Wang et al. (2015); Liu et al. (2021). Essentially, $\ell_{1}$-based methods are equivalent to soft-thresholding operations for iterative estimators and guarantee statistical properties (e.g., model selection consistency). Owning to these advantages, trend filtering Tibshirani (2014), and graph trend filter Wang et al. (2015); Verma and Zhang (2019) indicate that $\ell_{1}$-based graph smoothing can adapt to the inhomogeneous level of smoothness of signals and yield estimator with $k$-th piecewise polynomial functions, such as piecewise constant, linear and quadratic functions, depending on the order of the graph difference operator.

To enhance the local smoothness adaptivity of GCNs, a family of elastic-type GCNs with a combination of $\ell_{2}$ and $\ell_{1}$-based penalties are proposed by Liu et al. (2021), which demonstrate that the elastic GCNs obtain better adaptivity on benchmark datasets and are significantly robust to graph adversarial attacks.

Under the regularized learning framework, this paper further studies a class of $\ell_{p}$-regularized learning approaches $(1<p\leq 2)$, in order to trade-off the local smoothness of GCNs and sparsity between nodes. To be precise, it has been shown that an extreme case for $\ell_{p}$-regularized learning with $p\rightarrow 1$ tends to generate soft-sparsity of solutions Koltchinskii (2009). In analogy to elastic-type GCNs, general $\ell_{p}$-regularization can be interpreted as an interpolation of $\ell_{1}$-regularization and $\ell_{2}$-regularization. However, in contrast with the elastic-type GCNs, $\ell_{p}$-regularized GCNs only involve a regularized parameter but leads to some additional technical difficulties in optimization and theoretical analysis.

The generalization performance of an algorithm has always been a central issue in learning theory, and particularly the generalization guarantees of GNNs has attracted a considerable amount of attention in recent years Verma and Zhang (2019); Garg et al. (2020); Liao et al. (2020); Oono and Suzuki (2020).

It is worth noting that, although $\ell_{1}$-regularization possesses a number of attractive properties such as “automatic” variable selection, the objectiveness with $p=1$ is not a strictly convex smooth function, which has been proved not to be uniform stability Xu et al. (2011). On the other hand, it is known that for $p>1$, the penalty is a strictly convex function over bounded domains and thus enjoys robustness to some extent. As a bridge of sparse $\ell_{1}$-regularization and dense $\ell_{2}$-regularization, $\ell_{p}$-based learning allows us to explicitly observe a trade-off between sparsity and smoothness of the estimated learners.

Although this idea is natural within the framework of regularized learning, it still faces many technical challenges when applied to GCNs. First, to address the problem of uniform stability of an SGD algorithm that can induce generalization performance Bousquet and Elisseeff (2002), existing related analysis for SGD Verma and Zhang (2019); Hardt et al. (2016) required that the first derivative of the objectiveness is Lipschitz continuous, which is not applicable to $\ell_{p}$-based GCN. Second, to derive an interpretable generalization bound, it is important to know how such a result depends on the structure of the graph filter and the regularized parameter $p$, as well as the network size and the sample size.

Overall, our principal contributions can be summarized as follows:

• •

  We introduce $\ell_{p}$-regularized learning approaches for one-layer GCN to provide an explicit theoretical characterization of the trade-off between local smoothness and sparsity of the SGD algorithm for GCN. Crucially, we analyze how this trade-off between the graph structure and the regularization parameter $p$ affects the generalization capacity of our SGD method.

• •

  We propose a novel regularized stochastic algorithm for GCN, i.e., Inexact Proximal SGD, by integrating the standard SGD projection and the proximal operator. For our proposed method, we derive interpretable generalization bounds in terms of the graph structure, the regularized parameter $p$, the network width, and the sample size.

• •

  To our knowledge, we are the first to analyze the generalization performance of $\ell_{p}$-SGD in GNNs, which is quite different from existing stability-based generalization analysis for a second derivative objectiveness Verma and Zhang (2019); Hardt et al. (2016). We also have to overcome additional challenges in understanding the nature of the stochastic gradient for GCN, posed by the message passing nature in GCN. We conduct several numerical experiments to illustrate the superiority of our method to traditional smooth-based GCN, and we also observe some sparse solutions through our experiments as $p$ is sufficiently close to $1$.

In this section, we first describe basic notation on graph and standard versions of GCN. Then we introduce the structural empirical risk minimization for a single-layer GCN model under i.i.d. sampling process, and thus our $\ell_{p}$-regularized approaches is naturally formulated to estimate the graph filter parameters.

A graph is represented as $G=(V,E)$, where $V=\{\nu_{1},\nu_{2},...,\nu_{n}\}$ is a set of $n=|V|$ nodes and $E$ is a set of $|E|$ edges. The adjacency matrix of the graph is denoted by $\mathbf{A}=(a_{ij})\in\mathbb{R}^{n\times n}$, whose entries $a_{ij}=1$ if $(\nu_{i},\nu_{j})\in E$, and $a_{ij}=0$ otherwise. Each node’s own feature vector is denoted by $\mathbf{x}_{i}\in\mathbb{R}^{d}$, $i\in[n]$, where $d$ is the dimension of the node feature. Let $\mathbf{X}\in\mathbb{R}^{n\times d}$ denote the node feature matrix with each row being $d$ features. The $1$-hop neighborhood of a node $\nu_{i}$ is defined as the set $\{\nu_{j},(\nu_{i},\nu_{j})\in E\}$, and denote by $N_{(i)}$ the set that includes the node $\nu_{i}$ and all nodes belonging to its $1$-hop neighborhood. The main task of graph models is to combine the feature information and the edge information to perform learning tasks.

For an undirected graph, its Laplacian matrix $\mathbf{L}\in\mathbb{R}^{n\times n}$ is defined as $\mathbf{L}:=\mathbf{D}-\mathbf{A}$, where $\mathbf{D}\in\mathbb{R}^{n\times n}$ is a degree diagonal matrix whose diagonal entry $d_{ii}=\sum_{j}a_{ij}$ for $i\in[n]$. The semi-definite matrix $\mathbf{L}$ has an eigen-decomposition written by $\mathbf{L}=\mathbf{U}\bm{\Lambda}\mathbf{U}^{T}$, where the columns of $\mathbf{U}$ are the eigenvectors of $\mathbf{L}$ and the diagonal entries of diagonal matrix $\bm{\Lambda}$ are the non-negative eigenvalues of $\mathbf{L}$.

For a fixed function $g$, we define a graph filter $g(\mathbf{L})\in\mathbb{R}^{n\times n}$ as a function on the graph Laplacian $\mathbf{L}$. Following the eigen-decomposition of $\mathbf{L}$, we get $g(\mathbf{L})=\mathbf{U}g(\bm{\Lambda})\mathbf{U}^{T}$, where the eigenvalues are given by $\lambda_{i}^{(g)}=\{g(\lambda_{i}),1\leq i\leq n\}$. We define $\lambda^{max}_{G}=\max\{|\lambda_{i}^{(g)}|\}$ as the largest absolute eigenvalue of the graph filter $g(\mathbf{L})$.

In this paper, we are concerned with node-level semi-supervised learning problems over the graph $G$. Let $\mathcal{X}\subset\mathbb{R}^{d}$ be the input space in which the node feature is well defined, and accordingly $\mathcal{Y}\subset\mathbb{R}$ be the output space. In the semi-supervised setting, one assumes that only a portion of the training samples are labeled while amounts of unlabeled data are collected easily. Precisely, we merely collect a training set with labels $D=\{\mathbf{z}_{i}=(\mathbf{x}_{i},y_{i})\}_{i=1}^{m}$ with $m\ll n$. For statistical inference, one often assumes that these pairwise sample are independently drawn from a joint distribution $\rho$ defined on $\mathcal{X}\times\mathcal{Y}$. In such case, our studied model belongs to node-focused tasks on graph, as opposed to graph-focused tasks where the whole graph can be viewed as a single sample.

The most simple graph neural network, known as the Vanilla GCN, was proposed in Kipf and Welling (2016a), where each layer of a multilayer network is multiplied by the graph filter before applying a nonlinear activation function. In a matrix form, a conventional multi-layer GCN is represented by a layer-wise propagation rule

where $\mathbf{H}^{(k+1)}\in\mathbb{R}^{n\times m_{k+1}}$ is the node feature representation output by the $(k+1)$-th GCN layer, and specially $\mathbf{H}^{(0)}=\mathbf{X}$ and $m_{0}=d$. $\mathbf{W}^{(k+1)}\in\mathbb{R}^{m_{k}\times m_{k+1}}$ represents the estimated weight matrix of the $(k+1)$-th GCN layer, and $\sigma$ is a point-wise nonlinear activation function. Under the context of GCN for performing semi-supervised learning, the sampling procedure of nodes from the graph $G$ is conducted by two stages. We assume node data are sampled in an i.i.d. manner by first choosing a sample $\mathbf{x}_{i}$ or $\mathbf{z}_{i}$ at node $i$, and then extracting its neighbors from $G$ to form an ego-graph.

To interpret learning mechanism clearly for GCN, this paper focuses on a node-level task over graph with a single layer GCN model. In such case, putting all graph nodes together, the output function can be written in a matrix form as follows,

where $\mathbf{w}\in\mathbb{R}^{d}$ and $f(\mathbf{X},\mathbf{w})\in\mathbb{R}^{n}$. Some commonly used graph filters include a linear function of $\mathbf{A}$ as $g(\mathbf{A})=\mathbf{A}+\mathbf{I}$ Xu et al. (2018) or a Chebyshev polynomial of $\mathbf{L}$ Defferrard et al. (2016).

Under the context of ego-graph, each node contains the complete information needed for computing the output of a single layer GCN model. Given node with the feature $\mathbf{x}$, let $N_{\mathbf{x}}$ denote a set of the neighbor indexes at most $1$-hop distance neighbors, which is completely determined by the graph filter $g(\mathbf{L})$. Thus we can rewrite the predictor (2.2) for a single node prediction as

where $e_{\cdot j}=[g(\mathbf{L})]_{\cdot j}\in\mathbb{R}$ is regraded as a weighted edge between node $\mathbf{x}$ and its neighbor $\mathbf{x}_{j}$, and particularly it still holds $j\in N_{\mathbf{x}}$ if and only if $e_{\cdot j}\neq 0$.

Let $\ell(\cdot,\cdot)$ be a convex loss function, measuring the difference between a predictor and the true label, a variety of supervised learning problems in machine learning can be formulated as a minimization of the expectation risk,

where $\mathcal{F}$ is a hypothesis space under which an optimal learning rule is generated. The standard regression problems correspond to the square loss given by $\ell(u,v)=(u-v)^{2}$, and the logistic loss is widely used for classification. The optimal decision function denoted by $f_{0}$ is any minimizer of (2.4) when $\mathcal{F}$ is taken to be the space of all measurable functions. However, $f_{0}$ can not be computed directly, due to the fact that $\rho$ is often unknown and $\mathcal{F}$ is too complex to compute it possibly. Instead, a frequently used method consists of minimizing a regularized empirical risk over a computationally-feasible space

where $\Omega(f)$ is a penalty function that regularizes the complexity of the function $f$, while $\mathcal{H}$ is the space of all predictors which needs to be parameterized explicitly or implicitly. For instance, the neural network is known as an efficient parameterized approximation to any complex nonlinear function. In the work, all the functions within $\mathcal{H}$ consist of the form in (2.3).

In order to effectively solve non-convex problems with massive data, practical algorithms for machine learning are increasingly constrained to spend less time and use less memory, and can also escape from saddle points that often appear in non-convex problems and tend to converge to a good stationary point. Stochastic gradient descent (SGD) is perhaps the simplest and most well studied algorithm that enjoys these advantages. The merits of SGD for large scale learning and the associated computation versus statistics tradeoffs is discussed in detail by the seminal work of Bottou and Bousquet (2007).

A standard assumption to analyze SGD in the literature is that the derivative of the objective function is Lipschitz smooth Verma and Zhang (2019); Hardt et al. (2016), however, the $\ell_{p}$-regularized learning does not meet such condition. To address this issue, we propose a new SGD for (2.6) with an inexact proximal operator, and then develop a novel theoretical analysis for an upper bound of uniform stability Bousquet and Elisseeff (2002), which is an algorithm-dependent sensitivity-based measurement used for characterizing generalization performance in learning theory.

Given that a positive pair $(p,q)$ satisfies the equality $\nicefrac{{1}}{{p}}+\nicefrac{{1}}{{q}}=1$, then the norms $\|\mathbf{w}\|_{p}$ and $\|\mathbf{w}\|_{q}$ are dual to each other. Moreover, the pair of functions $(1/2)\|\mathbf{w}\|^{2}_{p}$ and $(1/2)\|\mathbf{w}\|^{2}_{q}$ are conjugate functions of each other. As a consequence, their gradient mappings are a pair of inverse mapping. Formally, let $p\in(1,2]$ and $q=p/(p-1)$, and define the mapping $\Phi:\mathrm{E}\rightarrow\mathrm{E}^{*}$ with

and the inverse mapping $\Phi^{-1}:\mathrm{E}^{*}\rightarrow\mathrm{E}$ with

The above conjugate property on $\ell_{p}$-space and $\ell_{q}$-space is very useful for bounding uniform stability without the help of strong smoothness, while the latter is a standard assumption in optimization.

In this section, we provide algorithm-dependent generalization bounds via the notion of stability for $\ell_{p}$-regularized GCN. To this end, we first introduce the notion of algorithmic stability and thereby present a generalization bound associated with the algorithmic stability.

Let $\mathcal{A}_{D}$ be a learning algorithm trained on dataset $D$, which can be viewed as a map from $D\rightarrow\mathcal{H}$. For GCN, we set $\mathcal{A}_{D}=f(\mathbf{x},\mathbf{w}_{D})$. The overall learning performance of $\mathcal{A}_{D}$ is measured by the following expected risk:

Accordingly, the empirical risk of $\mathcal{A}_{D}$ with the loss $\ell$ is given as

Even when the sample is fixed, $\mathcal{A}_{D}$ may be still a randomized algorithm due to the randomness of algorithm procedure (e.g. SGD). In this context, we define the expected generalization error as

where the expectation $\mathbb{E}_{\mathcal{A}}$ is taken over the inherent randomness of $\mathcal{A}_{D}$.

For a randomized algorithm, to introduce the notation of its uniform stability, we need to define two datasets as follows. Given the training set $D$ defined as above, we introduce two related sets in the following:

Removing the $i$-th data point in the set $D$ is represented as

and replacing the $i$-th data point in $D$ by $\mathbf{z}^{{}^{\prime}}_{i}$ is represented as

By the triangle inequality, the following result on another uniform stability associated with $S^{i}$ holds

Stability is property of a learning algorithm, roughly speaking, if two training samples are close to each other, a stable algorithm will generate close output results. There are many variants of stability, such as hypothesis stability Kearns and Ron (1999), sample average stability Shalev-Shwartz et al. (2010) and uniform stability. This paper will focus on the uniform stability, since it is closely related to other types of stability.

The following lemma shows that a randomized learning algorithm with uniform stability can guarantee meaningful generalization bound, which has been proved in Verma and Zhang (2019).

We now give some smooth assumptions on loss function and activation function used for analyzing the stability of stochastic gradient descent. The following assumptions are very standard in optimization literature.

We now present an explicit stability bound for GCN with $\ell_{p}$-regularizer via stochastic gradient method.

The proof procedure of Theorem 1 will be given in Appendix. The key step of our proof is that in such a scenario, the error caused by the difference in the nonconvex empirical risk of GCN grows polynomially with the number of iterations.

Substituting Lemma 3 into Theorem 1 above, we obtain the generalization bounds with uniform stability for a single layer GCN with $\ell_{p}$-regularizer.

In this section, we conduct experiments to validate our theoretical findings. In particular, we show that there exists a stability-sparsity trade-off with varying $p$, and the uniform stability of our GCN depends on the largest absolute eigenvalue of its graph filter. To do it, we first introduce the experimental settings. Then we assess the uniform stability of GCN with semi-supervised learning tasks under varying $p$. Finally, we evaluate the effect of different graph filters on the GCN stability bounds.

In this paper, we present an explicit theoretical understanding of stochastic learning for GCN with the $l_{p}$ regularizer and analyze the stability of our regularized stochastic algorithm. In particular, our derived bounds show that the uniform stability of our GCN depends on the largest absolute eigenvalue of its graph filter, and there exists a generalization-sparsity tradeoff with varying $p$. It is worth noting that previous generalization analysis based on stability notation assumed that objectiveness is a second derivative function, which is no longer applicable to our $l_{p}$-regularized learning scheme. To address this issue, we propose a new proximal SGD algorithm for GCNs with an inexact operator, which exhibits comparable empirical performances.

Lv’s research is supported by the “QingLan” Project of Jiangsu Universities. Ming Li would like to thank the support from the National Natural Science Foundation of China (No. U21A20473, No. 62172370) and Zhejiang Provincial Natural Science Foundation (No. LY22F020004).

Linsen We and Ming Li contributed equally to this work.