Stability and Generalization of lp-Regularized Stochastic Learning for GCN

1 Introduction

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ˇckovi´c et al., 2017], Graph Isomorphism Network [Xu et al., 2018], and among others.

† Corresponding author.

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 ℓ2-based graph smoothing signal, which enforces smoothness globally, and the level and smoothness are often shared across the whole graph. As opposed to ℓ2-based graph smoothing, ℓ1-based methods tend to penalize large values less and thus preserve discontinuity of nonsmooth signal better [Nie et al., 2011; Wang et al., 2015; Liu et al., 2021]. Essentially, ℓ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 ℓ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 ℓ2 and ℓ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 ℓp-regularized learning approaches (1 < p ≤ 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 ℓp-regularized learning with p → 1 tends to generate soft-sparsity of solutions [Koltchinskii, 2009]. In analogy to elastic-type GCNs, general ℓp-regularization can be interpreted as an interpolation of ℓ1-regularization and ℓ2-regularization. However, in contrast with the elastic-type GCNs, ℓ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 ℓ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 ℓ1-regularization and dense ℓ2-regularization, ℓ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 ℓ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 ℓp-regularized learning approaches for onelayer 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 ℓ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 nu-

merical 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.

1.1 Additional RelatedWork

In this subsection, we briefly review two kinds of related works: Generalization Analysis for GNNs and Regularized Schemes on GNNs.

Generalization Analysis for GNNs. Some previous work has attempted to address the generalization guarantees of GNNs, including [Verma and Zhang, 2019; Garg et al., 2020; Liao et al., 2020; Oono and Suzuki, 2020]. However, most of these works established uniform convergence results using classical Rademacher complexity[Garg et al., 2020; Oono and Suzuki, 2020] and PAC bounds [Liao et al., 2020]. Compared to these abstract capacity notations, the stability concept, used recently for GNN in [Verma and Zhang, 2019], is more intuitive and directly defined over a specific algorithm. Although the stability for generalization of GNNs has been considered recently by [Verma and Zhang, 2019], a major difference from their work is that we focus on the trade-off between soft sparsity and generalization of the ℓp-based GCN with varying p ∈ (1, 2]. Moreover, we propose a new SGD algorithm for GCN, under which we provide novel theoretical proof for the stability bound of our SGD.

Regularized Schemes on GNNs. Regularization methods are frequently used in machine learning, especially the prior literature [Wibisono et al., 2009] has studied the influence of ℓp-regularized learning on generalization ability. Note that the previous work only considered the impact of general regularization estimates on stability without a specific algorithm. In addition, their research is based on regular data and does not involve any graph structure. As far as we know, this paper is the first time to consider ℓp-regularized learning in a graph model.

2 Preliminaries andMethodology

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 ℓp-regularized approaches is naturally formulated to estimate the graph filter parameters.

A graph is represented as G = (V,E), where V = {ν1, ν2, ..., ν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 A = (aij) ∈ Rn×n , whose entries aij = 1 if (νi, νj) ∈ E, and aij = 0 otherwise. Each node's own feature vector is denoted by xi ∈ Rd , i ∈ [n], where d is the dimension of the node feature. Let X ∈ Rn×d denote the node feature matrix with each row being d features. The 1-hop neighborhood of a node νi is defined as the set {νj, (νi, νj) ∈ E}, and denote by N(i) the set that includes the node ν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 L ∈ Rn×n is defined as L := D-A, where D ∈ Rn×n is a degree diagonal matrix whose diagonal entry dii = ∑j aij for i ∈ [n]. The semi-definite matrix L has an eigen-decomposition written by L = UΛUT , where the columns of U are the eigenvectors of L and the diagonal entries of diagonal matrix Λ are the non-negative eigenvalues of L.

For a fixed function g, we define a graph filter g(L) ∈ Rn×n as a function on the graph Laplacian L. Following the eigendecomposition of L, we get g(L) = Ug(Λ)UT , where the eigenvalues are given by λ(g) i = {g(λi), 1 ≤ i ≤ n}. We define λmax G =max{|λ(g) i |} as the largest absolute eigenvalue of the graph filter g(L).

In this paper, we are concerned with node-level semisupervised learning problems over the graph G. Let X ⊂ Rd be the input space in which the node feature is well defined, and accordingly Y ⊂ R be the output space. In the semisupervised 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 = {zi = (xi, yi)}mi=1 with m ≪ n. For statistical inference, one often assumes that these pairwise sample are independently drawn from a joint distribution ρ defined on X ×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 H(k+1) ∈ Rn×mk+1 is the node feature representation output by the (k + 1)-th GCN layer, and specially H(0) = X and m0 = d. W(k+1) ∈ Rmk×mk+1 represents the estimated weight matrix of the (k + 1)-th GCN layer, and σ is a pointwise 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 xi or zi 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 w ∈ Rd and f(X,w) ∈ Rn . Some commonly used graph filters include a linear function of A as g(A) = A + I [Xu et al., 2018] or a Chebyshev polynomial of 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 x, let Nx denote a set of the neighbor indexes at most 1-hop distance neighbors, which is completely determined by the graph filter g(L). Thus we can rewrite the predictor (2) for a single node prediction as

where e·j = [g(L)]·j ∈ R is regraded as a weighted edge between node x and its neighbor xj, and particularly it still holds j ∈ Nx if and only if e·j ̸= 0.

Let ℓ(·, ·) 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 F is a hypothesis space under which an optimal learning rule is generated. The standard regression problems correspond to the square loss given by ℓ(u, v) = (u - v)2 , and the logistic loss is widely used for classification. The optimal decision function denoted by f0 is any minimizer of (4) when F is taken to be the space of all measurable functions. However, f0 can not be computed directly, due to the fact that ρ is often unknown and 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 Ω(f) is a penalty function that regularizes the complexity of the function f, while 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 H consist of the form in (3).

2.1 Empirical RiskMinimization with

ℓp-Regularizer

A fundamental class of learning algorithms can be described as the regularized empirical risk minimization problems. This paper considers an ℓp-regularized learning approach for training the parameters of GCN:

where 1 < p ≤ 2 and the ℓp-norm on Rd is defined as ∥w∥pℓp = ∑dj=1 |wj|p . For any 1 < p′ ≤ p ≤ 2, there always holds ∥w∥ℓp ≤ ∥w∥ℓp′ , which means that any learning method with the ℓp′ -regularizer imposes heavier penalties for the parameters than the one with the ℓp-regularizer. Specially when p → 1, the corresponding ℓp-regularized algorithm tends to generate so called soft sparse solutions [Koltchinskii, 2009]. In contrast to this, the commonly-used ℓ2-regularization tends to generate smooth but non-sparse solutions.

Note that we do not require that the minimizer of (6) is unique, catering to non-convex problems. The following lemma tells us that any global minimizer of (6) can be upper bounded by a quantity that is inversely proportional to λ.

This simple conclusion is useful in subsequent sections for designing a constrained SGD and our theoretical analysis with respect to the function ∥w∥pℓp .

Lemma 1. Assume that ℓ(y, σ(0)) ≤ B with some B > 0. For any λ > 0, any global minimizer ̂w of (6) satisfies ∥̂w∥pℓp ≤ B/λ, and furthermore ∥̂w∥ℓ2 ≤ (B/λ)1/p .

Proof of Lemma 1. Since ̂w is a global minimizer of the objective function in (6), this follows that

Moreover, for any 1 < p ≤ 2, it is known that ∥w∥ℓ2 ≤ ∥w∥ℓp for any w ∈ Rd . This completes the proof of the lemma.

Lemma 1 implies that the empirical solutions of (6) are in an ℓp-ball of certain radius which depends on the regularized parameter λ. This shows that it suffices to analyze statistical behaviors of the given estimator projected into this ball.

3 Regularized Stochastic Algorithm

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 ℓpregularized learning does not meet such condition. To address this issue, we propose a new SGD for (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 1/p + 1/q = 1, then the norms ∥w∥p and ∥w∥q are dual to each other. Moreover, the pair of functions (1/2)∥w∥2p and (1/2)∥w∥2q are conjugate functions of each other. As a consequence, their gradient mappings are a pair of inverse mapping. Formally, let p ∈ (1, 2] and q = p/(p - 1), and define the mapping Φ : E → E∗ with

and the inverse mapping Φ-1 : E∗ → E with

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

3.1 SGDwith Inexact Proximal Operator

We write Li(w) := ℓ(yi, f(xi,w)) for notational simplicity, and define a local quadratic approximation of Li at point wD,t

At each iteration t, let it be a random index sampled uniformly from [n] on D. Then replacing 1n ∑ni=1 Li(w) in (6) by the quadratic term Pit,rit (w, wD,t), we propose an inexact proximal method for SGD with the ℓp-regularizer. Precisely, we are concerned with the following iterative to update wD,t for a regularized-based SGD,

In view of the boundedness of ∥̂w∥ℓ2 given in Lemma 1, we adopt the projection technique to execute a constrained SGD over the empirical risk term in (7). To this end, we define the projection onto a set C by

This reveals that the definition of projection is an optimization problem in itself. In our case, the set we adopt is given as

It is well known that, if C = B2(1), i.e., the unit ℓ2 ball, then projection is equivalent to a normalization step

Up to the terms that do not depend on w, summing the objective function in (7) and the projection formulate our proposed algorithm as follows

where η > 0 is the learning rate that depends on rit , and the λt may depend on λ and rit .

Remark 1. The update rule in (9) is seen as a contraction of conventional SGD, see Lemma 2 below for details. We will obtain analytical solutions of (9) for some specific p (e.g. p = 1, 2). Although there is no analytical solutions for general 1 < p ≤ 2, the objective function in (9) is strongly convex over bounded domains and thus a global convergence can be guaranteed. For the ease of notation, we still denote by wD,t+1 the realized numerical solution with ignoring the inner optimization error.

Lemma 2. For 1 < p ≤ 2 and a vector v ∈ Rd is given, we define

Then, we conclude that

We defer the proof of Lemma 2 to the Appendix. Applying Lemma 2 and the projection onto Cλ in (8), we have the following inequality

Consider a function h : R → R defined as h(θ) = |θ|p (1 < p ≤ 2). Note that it holds

Obviously the first derivative of h exists and is continuous for all θ ∈ R. However, we notice that the inexact proximal operator Proλ,p is not Lipschitz, due to the fact that ∥ · ∥pℓp is not strongly smooth. Hence, as mentioned earlier, those conventional technique analysis under strongly smooth condition for objective functions are no longer valid in our case. Fortunately, the function h is strongly convex over bounded domains, as shown in Lemma 1, which enables us to avoid restrictive smooth assumptions by an alternative proof strategy.

4 Stability and Generalization Bounds

In this section, we provide algorithm-dependent generalization bounds via the notion of stability for ℓ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 AD be a learning algorithm trained on dataset D, which can be viewed as a map from D → H. For GCN, we set AD = f(x, wD). The overall learning performance of AD is measured by the following expected risk:

Accordingly, the empirical risk of AD with the loss ℓ is given as

Even when the sample is fixed, AD 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 EA is taken over the inherent randomness of AD.

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 z′i is represented as

Definition 1. A randomized learning algorithm AD is βnuniformly stable with respect to a loss function ℓ, if it satisfies

By the triangle inequality, the following result on another uniform stability associated with Si 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].

Lemma 3. A uniform stable randomized algorithm (AD, βn) with a bounded loss function 0 ≤ ℓ(y, f(x)) ≤ B, satisfies the following generalization bound with probability at least 1 - δ, over the random draw of D, z with δ ∈ (0, 1),

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.

Assumption 1 (Smoothness for loss function and activation function). We assume that the loss function is lipschitz continuous and smooth,

where aℓ and bℓ are two positive constants. Similarly, the activation function also satisfies

where aσ, bσ and B are positive constants as well.

We now present an explicit stability bound for GCN with ℓp-regularizer via stochastic gradient method.

Theorem 1. Suppose that the loss and activation functions are Lipschitz-continuous and smooth functions (Assumption 1). Then a single layer GCN model, trained by the proposed SGD given in (8)-(9) for iteration T, is βn-uniformly stable, precisely

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.

Remark 2. Theorem 1 provides the uniform stability for the last iterate of SGD for ℓp-regularized GCN. It is worth mentioning that the upper bound of this stability depends on the graph structure (i.e. ge and λmax G ) and the regularized hyperparameter p, as well as the sample size and the learning rate in SGD.

Remark 3. More precisely, the result in Theorem 1 shows that the stability bound decreases inversely with the scale of p. It increases as the graph structured parameter λmax G increases.

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

Theorem 2. Under the same conditions as Theorem 1. with a high probability, the following generalization bound holds

Remark 4. Based on the result of Theorem 2, we conclude that ℓp-regularization for 1 < p ≤ 2 generalizes. Note that, when p → 1, the stability bound breaks due to the sparsity of ℓ1-regularization. The smaller p becomes, the greater the stability parameter βn is, but at the same time the obtained parameter ̂w in (6) tends to be sparse, shown in [Koltchinskii, 2009]. These properties are also verified in our experimental evaluation.

Remark 5. Although a small learning rate means a smaller generalization gap, the parameter range in which this SGD searches will be very small, resulting in a larger training error. Such conclusion is also applicable to various SGD for general models.

5 Experiments

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.

5.1 Experimental Setup

Datasets. We conduct experiments on three citation network datasets: Citeseer, Cora, and Pubmed [Sen et al., 2008]. In every dataset, each document is represented as spare bag-ofwords feature vectors. The relationship between documents consists of a list of citation links, which can be treated as undirected edges and help construct the adjacency matrix. These documents can be divided into different classes and have the corresponding class label.

Baselines. We implement several empirical experiments with a representative GCN model [Kipf and Welling, 2016a]. For all datasets, we use 2-layer neural networks with 16 hidden units. In all cases, we evaluate the difference between the learned weight parameters and the generalization gap of two GCN models trained on datasets D and Di , respectively. Specifically, we generate Di by choosing a random data point in the training set D and altering it with a different random point. We also record the training and testing errors gap and the parameter distance √∥ ̂w - ̂w′ ∥2 /(∥ ̂w∥2 + ∥ ̂w′ ∥2 ), where ̂w and ̂w′ are the weight parameters of the respective models per epoch.

Training settings. For each experiment, we initialize the parameters of GCN models with the same random seeds and then train all models for a maximum of 200 epochs using the proposed Inexact Proximal SGD. We repeat the experiments 10 times and report the average performance as well as the standard variance. For all methods, the hyperparameters are tuned from the following search space: (1) learning rate: {1, 0.5, 0.1, 0.05}; (2) weight decay: 0; (3) dropout rate: {0.3, 0.5}; (4) regularization parameter λ is set to 0.001.

5.2 The Effect of Varying p

Generalization gap. In this experiment, we empirically compare the effect of p on the GCN stability bounds using different p ∈ {1.001, 1.149, 1.32, 1.516, 1.741, 2}. We quantitatively measure the generalization gap defined as the absolute difference between the training and testing errors and the difference between learned weights parameters of GCN models trained on D and D′ , respectively. It can be observed that in Figure 1, these empirical observations are in line with our stability bounds (see also results in Figure 3 in Appendix).

Sparsity. Besides the convergence, we have a particular concern about the sparsity of the solutions. The sparsity ratios for lp-based method are summarized in Table 1. Observe that ℓp-regularized learning with p → 1 identifies most of the sparsity pattern but behaves much worse in generalization.

5.3 The Effect of Graph Filters

Different normalizations steps. In this experiment, we mainly consider the implication of our results in following designing graph convolution filters: (1) Unnormalized Graph Filters: g(L) = A + I; (2) Normalized Graph Filters: g(L) = D-1/2AD-1/2 + I; (3) Random Walk Graph Filters: g(L) = D-1A+I; (4) Augmented Normalized Graph Filters: g(L) = (D + I)-1/2 (A + I)(D + I)-1/2 .

In this experiment, we quantitatively measure the generalization gap and parameter distance per epoch. From Figure 2, it is clear that the Unnormalized Graph Filters and Random Walk Graph Filters show a significantly higher generalization gap than the normalized ones. The results hold consistently across the three datasets. Hence, these empirical results are also consistent with our generalization error bound. We note that the generalization gap and parameter distance become constant after a certain number of iterations. More results can be found in the supplementary material.

6 Conclusion

In this paper, we present an explicit theoretical understanding of stochastic learning for GCN with the lp 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 lp-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.

Acknowledgements

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).

Contribution Statement

Linsen We and Ming Li contributed equally to this work.