Adversarial Training for Graph Convolutional Networks: Stability and Generalization Analysis

1 Introduction

GCNs have demonstrated superior ability to process graphstructured data and learn both node and graph representations [Kipf and Welling, 2017; Zhu et al., 2021]. As one of the most widely employed tasks of GCNs, node classification has garnered significant attention due to its extensive real-world applications, such as natural language processing [Liu and Wu, 2022; Wang et al., 2024], recommendation systems [Sun et al., 2021; Gao et al., 2023], and computer vision [Zhou et al., 2021; Hu et al., 2023]. However, GCNs are vulnerable to some small but intentional perturbations on node features or graph structures that can mislead the classifiers to make erroneous predictions [Zhu et al., 2019; Bojchevski and G¨unnemann, 2019].

Several approaches have been proposed to enhance the robustness of models against adversarial attacks [Sun et al., 2022]. Among these, adversarial training is formulated as a min-max problem. The training procedure targets minimizing the classification error against an adversary who perturbs the input data and maximizes the classification error [Huang et al., 2015]. Numerous studies of adversarial training on GCNs have shown excellent performance in node classification tasks [Xue et al., 2021a; Xu et al., 2020; Deng et al., 2023]. However, a significant problem was observed in adversarial training, i.e., robust overfitting [Yin et al., 2019; Rice et al., 2020]. The network performs well on the training data but has poor adversarial generalization ability on the test set. This motivates the need for a generalization guarantee from the theoretical perspective.

∗Corresponding author.

Previous studies investigate adversarial generalization using different statistical analytical techniques, including covering number [Tu et al., 2019; Mustafa et al., 2022], Rademacher complexity [Yin et al., 2019; Gao and Wang, 2021], and stability analysis [Farnia and Ozdaglar, 2021; Xing et al., 2021a]. Unfortunately, the aforementioned works are confined to adversarial generalization analysis based on non-graph data. As the adversarial attacks to graph-structured data could modify both node features and graph structure, which poses more challenges in adversarial generalization analysis than [Gao and Wang, 2021; Mustafa et al., 2022; Xiao et al., 2022]. Specifically, in GCNs, node-based attacks affect the entire feature matrix rather than individual samples, due to the message-passing mechanism inherent to GCNs. This interaction between nodes creates an intricate interplay of perturbations, complicating the analysis of the stability of GCNs under such attacks. Additionally, structurebased attacks modify the graph's edges by altering the adjacency matrix (i.e., flipping discrete connection signals 0 or 1), making standard techniques for adversarial loss inapplicable to graph-structured data.

To overcome these difficulties, we derive the approximate smoothness properties for the adversarial loss function in GCNs and investigate the adversarial generalization of GCNs through the lens of uniform stability. Our analysis is applicable to both node-based and structure-based attacks. The main contributions are listed as follows:

• We establish a stability-based adversarial generalization bound in expectation for general GCNs to provide theoretical support for adversarial training. Our theoretical results demonstrate that the configuration of the graph model architecture and optimal algorithm significantly impacts GCNs' generalization performance.

• We address the impact of the information interaction between perturbed nodes on the adversarial generalization by utilizing the contraction technique of graph convolution, which is based on graph filters. We exploit the properties of graph filters to avoid operating directly in the discrete perturbation domain under structure-based attacks.
• Our experimental results on benchmark datasets provide evidence that the established theoretical findings facilitates improving the robust generalization of GCNs.

2 RelatedWork

Adversarial attacks for node classification. For node-based attacks, Takahashi et al. (2019) impose adversarial attacks by searching small perturbations on a single node, which leads to misclassification into the node far more than one-hop from the perturbed node. Ma et al. (2020) investigate black-box attacks under realistic constraints, where attackers have access to only a subset of nodes and can only target a limited number of nodes. Finkelshtein et al. (2022) propose a singlenode indirect gradient adversarial evasion attack, focusing on the more realistic scenario where a single attacker node is involved. For structure-based attacks, Xu et al. (2019) propose a gradient-based attack method that perturbs a small number of edges, which leads to a noticeable decrease in classification performance. Geisler et al. (2021) develop two sparsityaware first-order optimization attack methods to attack graph models at scale. Fan et al. (2023) introduce a novel attack framework to jointly attack graph models and their explanations via inserting adversarial edges.

Adversarial training on GCNs. For node-based attacks, Feng et al. (2019) introduce Graph Adversarial Training (GraphAT), which generates perturbations by maximizing the divergence between the predictions of two connected nodes. Xue et al. (2021a) analyze GCNs by examining weight and feature loss landscapes, and apply alternating adversarial training (Co-AT) to mitigate the risk of sharp local minima. Dend et al. (2023) design Batch Virtual Adversarial Training (BVAT), which promotes output smoothness of GCNs by applying virtual adversarial perturbations to independent subsets of nodes or all nodes. For structure-based attacks, Xu et al. (2020) develop Zeroth-Order Greedy Topology Attack

(ZO-GTA), a gradient-free adversarial training method aimed at obtaining robust models in a more generic manner. Li et al. (2022) construct adversarial perturbations in the spectral domains and design Spectral Adversarial Training (SAT), which is applicable to both node-based and structure-based attacks. Gosch et al. (2024) improve the robustness of GNNs against structural perturbations by leveraging a learnable graph diffusion model to approximate any graph filter. We summarize the above works in Appendix C. Although the empirical effectiveness of the above adversarial training methods has been validated, their theoretical foundations have not been investigated.

Stability-based generalization analysis. Uniform stability is a classical approach for measuring the generalization gap [Bartlett and Mendelson, 2002]. Verma and Zhang (2019) first apply uniform stability on one-layer GCN to derive a generalization bound. Their work demonstrates a high relationship between generalization and the maximum absolute eigenvalue of the graph filters. Zhou and Wang (2021) extend their results to multi-layer GCNs and show a exponential dimensional dependence of the generalization gap on the number of layers. Additionally, uniform stability has a wide range of applications in adversarial learning. Farnia and Ozdaglar (2021) analyze the adversarial generalization properties of minimax models through the lens of algorithmic stability. Similarly, Xing et al. (2021a) develop an adaptive algorithm and apply uniform argument stability to solve the min-max problem. It is important to note that the stability bounds in these studies are ϵ-independent, where ϵ is the adversarial perturbation. Xiao et al. (2022) address this limitation by introducing a modified smoothness assumption, enabling the derivation of adversarial generalization bounds that depend on ϵ. We summarize the main results of studies using uniform stability in Table 1. Though widely used in neural networks, the stability-based adversarial generalization has been unexplored in GCNs.

3 Problem Setting

Notations. We denote a matrix by the boldface uppercase letters (e.g., X) and a vector by the boldface lowercase letters (e.g., x). For a matrix X, we denote its ∥ · ∥∞-norm by ∥X∥∞ = ∥X∥ = maxi ∑j |Xij|, where Xij is an element in matrix X. For a vector x, we denote its ∥ · ∥2-norm by ∥x∥2 = √∑i x2i , and its ∥ · ∥∞-norm by ∥x∥∞ = ∥x∥ = maxi |xi|, where xi is an element in vector x.

A graph is represented as G = {A,X} with N nodes, where A ∈ RN×N is the adjacency matrix and X = {xi}Ni=1 ∈ RN×d is the node feature matrix. Each node is an instance zi = (xi, yi) containing feature xi and label yi from space Z = X ×Y. Let n ≤ N be the number of training samples zi. In this paper, we focus on the node classification task, which is based on a typical K-layer GCN model. The update rule with j = {1, 2, . . . , K} is represented by

where Xj ∈ RN×dj represents the output of the j-th layer with X0 ∈ RN×d and XK ∈ RN×|Y| denoting the input and output matrix of the model, respectively. Similarly, Wj ∈ Rdj-1×dj represents the learning parameters of the j-th layer with d0 = d and dK = |Y|. Moreover, the function σ(·) denotes the activation function, and g(A) ∈ RN×N represents the graph filter, which is a function of the adjacency matrix A, such as the unnormalized filter g(A) = A+I, the symmetric normalized filter g(A) = (D + I)-1/2 (A + I)(D + I)-1/2 [Kipf and Welling, 2017], and the random walk normalized filter g(A) = (D+ I)-1 (A+ I) [Zhang et al., 2019]. For a node xi, we utilize an indicator pxi ∈ RN to obtain the corresponding output label yi. Thus, the output function of the node x is defined as

where W = {W1,W2, . . . ,WK} is the learning parameters. For a K-layer GCNs, the learning algorithm is defined as AS = f(W,A, x), where the training set S = {zi}ni=1 is sampled from an unknown distribution D. Denote the loss function on sample z = (x, y) by ℓ(AS , z) or ℓ(f(W,A, x), y), the population risk is defined on distribution D as RD(AS ) = EDℓ(f(W,A, x), y), and the empirical risk is defined on the training set S as RS(AS ) = 1n ∑ni=1 ℓ(f (W, A, xi), yi).

In this paper, we focus on the ℓ∞ adversarial attack. The adversary is allowed to attack the graph with some ℓ∞ balls by perturbing the node feature matrix or adjacency matrix. We impose the attacks by maximizing the standard loss

where ˜ f(·) denotes the perturbed graph model by node or structure attacks. Then, to improve the robustness of GCNs against adversarial attacks, we perform adversarial training by minimizing the adversarial loss ˜ ℓ(f(W,A, x), y) [Shaham et al., 2018].

To better explain the generalization under the framework of adversarial training, we define the adversarial population risk function as

It represents the worst-case risk of the model under adversarial perturbations. Since the distribution D is unknown, we estimate the min-max objective by using the adversarial empirical risk function defined as

We are interested in the difference between the population risk and the empirical risk in adversarial settings as the generalization error, which is represented by

4 Main Result

The main results are presented in Theorem 2 and 3, which provide the adversarial generalization gap for K-layer GCNs. We first give the definition of uniform stability. Next, we give some essential assumptions and critical lemmas. Finally, we establish the stability bound of GCNs in adversarial settings.

4.1 Uniform Stability

For a dataset S, we consider replacing the ith data point zi with a new point z′i . The resulting dataset can be represented as

As shown by Bousquet and Elisseeff (2002), the generalization gap is closely related to uniform stability. Specifically, Definition 1 provides an upper bound on the difference in loss resulting from a small change in the training set, applicable to all possible sample combinations z.

Definition 1 (Uniform Stability). A randomized learning algorithm AS trained on dataset S with n samples is βuniformly stable with respect to a loss function ℓ, if it satisfies

According to Hardt, Recht, and Singer (2016), a randomized learning algorithm with the above uniform stability can yield the following bound on the generalization gap.

Theorem 1 (Generalization in Expectation). A uniform stable randomized algorithm (AS , β) satisfies the following generalization bound

Theorem 1 demonstrates that if a randomized algorithm is uniformly stable, then its generalization error is small. For the randomized algorithm, we use SGD on the adversarial loss to search for the optimal solution for the worst-case scenario. At each iteration t, for 1 ≤ j ≤ K, the update rule is defined as:

where ηt > 0 is the step size in iteration t, and Wj,t are the parameters generated by the j-th layer GCNs running on SGD at t-iteration. We take the expectation over the risks in Theorem 1 based on the internal randomness of AS . Note that SGD generates randomness as it selects examples randomly to compute batch loss gradients. Hence, we focus on this randomness and ignore the randomness introduced by parameter initialization. We will use ESGD instead of EA in subsequent analysis.

4.2 Assumptions

Next, we give some assumptions of the loss function ℓ(·) and activation function σ(·).

Assumption 1. Assume that the loss function ℓ(W,V) satisfies the following Lipschitzian smoothness conditions, where W represent the weight of GCNs, and V = z or V = A.

Assumption 2. Assume that the activation function σ(·) satisfies the following Lipschitzian smoothness conditions.

Assumption 3. Assume that there exists a constant Cx such that ∥x∥2 ≤ Cx holds for all x ∈ X .

Assumption 4. Assume that there exists a constant Cw > 0 such that max1≤j≤K ∥Wj∥ ≤ Cw holds.

Remarks. Assumption 1 is commonly found in the stability literature and holds for most gradient-based attacks [Farnia and Ozdaglar, 2021; Xing et al., 2021b]. Some common loss functions satisfy the above conditions, such as the cross-entropy loss and log loss. And a majority of activation functions like Sigmoid, Tanh, and ELU satisfy the Assumption 2. Assumption 3 can be satisfied by applying normalization to the input features [Verma and Zhang, 2019; Tang and Liu, 2023]. Assumption 4 reflects the common requirement in generalization analysis of GCNs that parameters are bounded during the training process [Garg et al., 2020; Cong et al., 2021].

4.3 Stability Generalization Bounds

We then utilize uniform stability to analyze the generalization of multi-layer GCNs under two adversarial scenarios: nodebased and structure-based attacks.

Node Perturbations

We first impose adversarial attacks on node features x to find the most effective adversarial examples ˜x. They are generated from a noise set B∞ ϵx = {˜x : ∥˜x - x∥ ≤ ϵx}, where ϵx represents the perturbation budget, typically set to small values to ensure that the feature distribution of adversarial examples remains close to clean examples. The adversarial loss in formulation (1) can be rewritten by

Then, we have the following properties of the adversarial loss function against the node perturbations.

Lemma 1. LetWrepresent the training parameters of SGD running on GCNs, and the adversarial loss function ˜ ℓ(W, z) satisfies Assumption 1. For any z ∈ Z, the following properties hold.

Remarks. In Lemma 1, the first inequality shows that the adversarial loss also satisfies the Lipschitz continuous properties. Nevertheless, the second item demonstrates that the maximization operation on loss hurts the continuity of its gradient, and the smoothness of the adversarial loss is controlled by the perturbation constraint ϵx.

Then we state the adversarial generalization bound for Klayer GCNs, which controls the generalization error against the node attacks by measuring the stability of the SGD algorithm.

Theorem 2 (Adversarial Generalization Gap of Multi-layer GCNs). Let AS be the function learned by K-layer GCNs after training on the dataset S with n samples using the SGD algorithm for T iterations. With Assumptions 1, 2, 3 and 4 hold, we have the following expected generalization bound.

where η = max{η1, η2, . . . , ηT } and

Remarks. For K-layer GCNs, due to the termCG, the generalization bound would increase exponentially with the number of layers K, which deteriorates the performance of deep GCNs. Theorem 2 reveals that CG is affected by some Lipschitz coefficients (e.g. vσ and ασ) and norm constraints (e.g. Cx and Cw). Thus, we can choose ELU activation and cross-entropy loss to eliminate the effect of those Lipschitz constants. And the norm constraint Cx of node x can be controlled by applying the batch-normalization in GCNs [Verma and Zhang, 2019]. As ∥g(A)∥ = 2dmax + 1 if g(A) = A + I is selected, we can choose the normalized filter with ∥g(A)∥ = (2dmax +1)/dmin, where dmax and dmin represent the maximum and minimum degree of the adjacency matrix, respectively. Besides, one could mitigate the exponential growth by applying a regularization on the weight norm ∥W∥ to reduce the value of Cw, especially when the number of layers increases.

Remarks. In the context of the SGD training procedure, the choice of learning rate η is crucial. A larger number of iterations T may result in a wider gap, potentially signaling overfitting. More importantly, compared to Zhou and Wang (2021), our bound takes account of the adversarial robustness, which is reflected in the term αxϵx. The adversarial coefficient αx hurts the robust generalization even though the perturbation ϵx is small for their multiplicative relation.

Structural Perturbations

We now consider the structure attacks on GCNs, i.e., perform subtle perturbations on the graph structure by adding or deleting a small number of edges. Followed by previous studies [Geisler et al., 2021; Fan et al., 2023], we assume that the adversarial adjacency matrix ˜A is generated by B∞ ϵA = {˜A : ∥˜A-A∥ ≤ ϵA}, where ϵA is the perturbation budget to constrain the changes to A. The adversarial loss in formulation (1) can be rewritten by

Different from the node attacks, the relation between the perturbed adjacency matrix ˜ A and adversarial generalization is difficult to handle. We explore the impact of ˜ A on the generalization by operating the graph filter, which is reflected on ϵg = ∥∥g(A) - g(˜A)∥∥. Similar to Lemma 1, the structure attacks also satisfy the Lipschitz properties of adversarial loss that ˜ ℓ(W, g(A)) is vw-Lipschitz continuous and αw-Lipschitz 2αgϵg-approximately smooth. Based on these properties, we can derive the generalization bound of K-layer GCNs against the structure attacks in the following theorem.

Theorem 3 (Adversarial Generalization Gap of Multi-layer GCNs). Let AS be the function learned by K-layer GCNs after training on the dataset S with n samples using the SGD algorithm for T iterations. With Assumptions 1, 2, 3 and 4 hold,

• (a) if g(A) is unnormalized, we have

• (b) if g(A) is normalized, we have

where η is as stated in Theorem 2 and

Remarks. Obviously, the adversarial generalization of GCNs under the structure attack is also susceptible to the model structure and optimization algorithm. And our bound can cover the standard training setting when the perturbation budget ϵA = 0. We find that the structural perturbations cause more damage to the generalization due to the perturbation budget ϵA. However, ϵA ≪ N is set as a sufficiently small budget to reduce the unavoidable damage to robust generalization, especially when the number of nodes is large, resulting in ϵA/N → 0. Furthermore, the relationship between ϵg and ϵA is relevant to the choice of graph filter. It's noteworthy that g( ˜ A) shares the same norm constraint as g(A). Following the suggestion of Theorem 2, we choose the normalized filter, and can mitigate the impact of ϵg ≤ 2 dmin ϵA by attacking a denser graph.

5 Experiments

According to the theoretical results, we observe that the adversarial generalization bound is related to the graph filters, the number of layers, the iterations of SGD, etc. In this section, we perform experiments on the node classification task to evaluate the effect of these factors on adversarial generalization. We provide the designed training objective and training procedure in Algorithm 1 and 2, respectively. We consider node attacks there, and the experiments of structure attacks are presented in Appendix D.

Experimental Setup. We adopt several widely-used benchmark datasets, including Cora, Citeseer, Pubmed, DBLP, CS, and CoraFull [Yang et al., 2016; Bojchevski and G¨unnemann, 2017; Xue et al., 2021b]. An overview is given in Table 2. We adopt two-layer GCNs with 16-unit hidden layers and symmetric normalized filters. The adversarial training is conducted with the ℓ∞-PGD algorithm, which is attacked with perturbation budget ϵx. We choose the cross-entropy loss and the SGD algorithm for training, where the learning rate η is set as 0.1 with a momentum of 0.9. The regularization coefficient λ is fixed to 0.01. The adversarial generalization gap is approximately calculated by

|adversarial train accuracy-adversarial test accuracy|,

which is the absolute difference between the train accuracy and test accuracy of adversarial training. Each experiment is independently repeated 10 times to get the average value and the standard deviation. More experimental configurations and results, including the structure attacks and other attack algorithms, are provided in Appendix D.

Algorithm 1 Train a robust graph model under node attacks

• 1: Input: Graph G, dataset S, perturbation budget ϵx, regularization parameter λ, initialization W0, learning rate η, number of iterations T.
• 2: while t < T do
• 3: ˜ S ← ∅.
• 4: for i = 1, 2, . . . , n do
• 5: Perturb each node and get ˜xi,t = argmax˜xi,t∈B∞ ϵx ℓ(f(W,A, ˜xi,t), yi,t).
• 6: Append {(˜xi,t, yi,t)}ni=1 to ˜ St .
• 7: end for
• 8: Update Wt through a new objective L(Wt) = 1n ∑xi,t∈˜ St ℓ(f(Wt, A, ˜xi,t), yi,t) + λ∥Wt∥.
• 9: Wt+1 ←Wt - η∇L(Wt).
• 10: end while
• 11: Output: WT

Graph filters. According to Theorem 2, our theoretical analysis suggests that a bigger ∥g(A)∥ leads to a greater generalization gap. Figure 1 shows that the unnormalized filter g(A) = A+ I with the biggest infinity norm has the largest generalization gap, compared to the other normalized filters. The empirical results align with our theoretical findings. And the comparison between two normalized filters depends on the specific graph data structure.

Number of layers. As shown in Figure 2, the generalization gap generally tends to increase with the increase of K. According to Theorem 2, K controls a variety of the main factors influencing the generalization gap. Our experimental configurations, including applying the normalized graph filters and regularization operations, could help reduce the inevitable increasing trend. The effectiveness of these measures is also demonstrated in Figure 1 and 4.

Number of iterations. Figure 3 illustrates that the generalization gap enlarges as the iterations proceed from the perspective of an overall trend, which is consistent with the results in Theorem 2. After several iterations, the generalization gap tends to be stable as the model converges.

Regularization. Theorem 2 demonstrates that controlling the norm constraint of weights by regularization could help eliminate the damage of exponential growth of generalization. As shown in Figure 4, the regularized model has a better generalization than the model without regularization.

6 Conclusions

In this paper, we propose a theoretical understanding of adversarial robustness for GCNs under node-based attacks and structure-based attacks. More specifically, we first show that the adversarial loss satisfies the approximate smoothness, which is dependent on the perturbation budget. Then we derive the stability-based generalization bounds of multi-layer GCNs for adversarial training. Our results shed new insights into the choice of the graph filters and the number of GCNs' layers. A smaller norm of the graph filters and their product with input features can benefit the performance of the models. And a controllable norm constraint of learning weights by applying the regularization can obtain a better generalization. Our experimental results on benchmark datasets support the theoretical results.

Acknowledgments

This work was supported by the National Natural Science Foundation of China (under Grant Nos. 62276111, 62076041, 62376104, 12426512), and the Open Research Fund of Engineering Research Center of Intelligent Technology for Agriculture, Ministry of Education (No. ERCITAKF002).