Spectral Adversarial Training for Robust
Graph Neural Network

To reduce the effect of adversarial behaviors, a straightforward way of defense is to detect and remove potential perturbations in a graph. Based on this insight, Wu et al. [25] propose to inspect the graph and recover the suspicious connections via Jaccard similarity scores of features between connected nodes. Xu et al. [26] propose a different approach to detect malicious edges with a filter-and-sample framework. Beyond these edge-based methods, Entezari et al. [27] propose to use Singular Value Decomposition (SVD) to form a low-rank approximation of graph adjacency matrix, and thus reduce the adversarial effects.

Rather than directly inspecting poisoned graph structures, such as edges or nodes before inputting to the models, several works attempt to design more robust architectures for GNNs. Specifically, Zhu et al. [22] adopt Gaussian distributions as node representations and employ attention mechanisms to dynamically adjust the propagation of adversarial attacks in GNNs. As the vulnerability of GNNs is mostly attributed to the non-robust aggregation scheme [28], Jin et al. [29] propose Similarity Preserving GCN (SimPGCN) that preserves node similarly and adaptively capture the graph structure during the aggregation process. Chen et al. [28] adopt robust aggregation schemes, median and trimmed mean, instead of weighted mean to enhance the robustness of GNNs.

While adversarial perturbations are initially used to construct adversarial examples and fool the neural networks, the same sword can be utilized by defenders to improve the robustness of their models against adversarial attacks [23]. Adversarial training (AT) on graph data is inspired by research in computer vision, where the perturbations are constructed in continuous input domains. So far, a variety of works [14, 30, 31] employ virtual adversarial training on node features, to enforce the smoothness of the models’ output distributions against adversarial inputs. In particular, Deng et al. [30] propose batch virtual AT to smooth the outputs of GNNs, Feng et al. [14] devise a dynamic regularizer encouraging GNN models to learn representations that are robust to perturbations. In the ensuing work, Hu et al. [32] design neighbor perturbations to restrict the perturbation directions on node features and prevent the propagation of perturbed neighbors. Jin et al. [31] apply AT on the latent representations of the nodes to improve the robustness and generalization ability of GNNs.

The aforementioned works are typically feature-based AT. However, the structural information has not been fully exploited during training. The structure-based AT perturbs the graph by adding or dropping edges or nodes, which is also an effective way to defend against attacks. Dai et al. [8] propose to randomly drop edges during each training step. Such a simple strategy has shown its effectiveness in improving the GNNs’ robustness. One step further, Xu et al. [13] design an optimization-based AT, where adversarial edges are generated by a topology attack. The presented work has demonstrated the effectiveness of employing structural AT on graph data. To facilitate adversarial training via practical adversarial examples, a growing number of researchers [33, 13] seek to employ attack-oriented perturbations, which are generated based on existing network adversarial attacks of PGD [13] and Metattack [9].

Although these works attempt to handle similar problems, i.e., improving the robustness of GNNs via practical adversarial training, they either require substantial costs to construct adversarial examples in the discrete graph domain (structure-based AT) or discard the graph topology that is crucial for GNNs (feature-based AT). In light of these challenges, our work attempts to employ AT on the graph spectrum. Specifically, it is able to approximate the structure perturbations in terms of the changes of the eigenpairs. Thus, the discrete optimization problem is transformed into a continuous one and the computational overhead is greatly alleviated.

Graph Convolutional Network (GCN) [20] is one of the classical models in graph-based learning, which has been broadly used in many tasks. The purpose of the GCN is to leverage the geometrical properties into the neural network by an iterative message aggregation scheme. Under the setting of semi-supervised node classification, the $(l+1)$-th hidden output of GCN can be formulated as follows:

Here, $\mathbf{\widetilde{A}}=\mathbf{A}+\mathbf{I}$ is the adjacency matrix of the graph $G$ with self-connections, $\mathbf{I}\in\mathbb{R}^{n\times n}$ is the identity matrix, and the $i$-th diagonal element of $\mathbf{\widetilde{D}}$, $\mathbf{\widetilde{D}}_{ii}=\sum_{j}\mathbf{\widetilde{A}}_{ij}$, is degree of node $i$ plus 1. $\mathbf{W}^{(l)}\in\mathbb{R}^{d\times d^{\prime}}$ is the trainable weight matrix of layer $l$ which learns useful features and transforms the embedding size from $d$ to $d^{\prime}$. Here we omit the bias terms in each layer for the sake of simplicity. $\sigma(\cdot)$ denotes the activation function, such as ReLU [34] in this paper. Initially, $\mathbf{H}^{(0)}=\mathbf{X}$. In particular, a two-layer GCN with ReLU as hidden activation and softmax as output is widely adopted. Thus the semi-supervised classification model can be described as:

where $\mathbf{\hat{{A}}}=\mathbf{\widetilde{D}}^{-\frac{1}{2}}\mathbf{\widetilde{A}}\mathbf{\widetilde{D}}^{-\frac{1}{2}}$ is the normalized Laplacian matrix of graph $G$.

The vanilla GCN recursively but repeatedly computes the aggregated messages from the nodes’ neighborhoods, resulting in excessive computation during training. To reduce the computation overhead, Wu et al. [21] theoretically analyze the architecture of GCN and propose to linearize it. Specifically, the resulting linear model, SGC, removes the nonlinear activation function in the hidden layers and collapses the weight matrices between consecutive layers. Therefore, the output of the GCN is simplified as:

where $\mathbf{W}=\mathbf{W}^{(0)}\mathbf{W}^{(1)}$ is the redefined weight matrix, and $K$ is the number of hidden layers and often set as 2. SGC captures structural information from the $K$-hop neighborhoods of the nodes in the graph, by simply applying the $K$-th power of the transition matrix $\mathbf{\hat{A}}$ in a single neural network layer. It is worth mentioning that the term of $\mathbf{\hat{A}}^{K}\mathbf{X}$ is usually a constant and can be pre-computed, which reduces the computation overhead during training.

Inspired by the previous works [21, 35], $\text{S}^{2}$GC [22] has been recently proposed as a state-of-the-art model. Similar to SGC, $\text{S}^{2}$GC is a linear learner which seeks to address the issues of over-smoothing and high computational costs encountered in the literature. $\text{S}^{2}$GC adopts a simple but effective graph filter that aggregates the neighborhoods with various sizes, and is beneficial for capturing the global and local information of each node in the graph. Typically, $\text{S}^{2}$GC generalizes the output of SGC as:

where $a\in[0,1]$ is a scalar to balance the aggregations of the nodes and their neighborhoods. Similar to SGC, the graph filter can be also pre-computed and the resulting model represents a good trade-off between classification accuracy and computation overhead.

The structure-based AT mainly focuses on the graph structure denoted by $\mathbf{A}$. Unlike on non-graph structured data, e.g., image or text data, AT cannot be directly employed on the graph structure due to its discreteness. Naturally, there must be constraints on the adversarial perturbations, which ensure the discreteness of the graph structure. Specifically, we define the structure-based AT on top of Equation (5), as:

where $\delta_{s}$ denote the structural perturbations.

Although generating adversarial examples based on randomly dropping is quite cheap to implement, there is little performance gain against adversarial attacks with such a strategy [36]. Currently, the mainstream structure-based AT methods are attack-oriented, that is, the adversarial perturbations are generated by powerful attackers. However, adversarial attacks on graph data are frequently insufficient, and generating such adversarial examples comes at a high cost, which limits their usability.

The feature-based AT generates adversarial examples in a different way. The perturbations are added on the node features, either the original input features or the transformed ones in the latent space. Similar to structure-based AT, we define the feature-based AT as:

where $\delta_{f}$ and $\delta_{l}$ are the perturbations added on the node input feature and the latent representations, respectively. Because the features are often in the continuous domain, the generated perturbations can have any values and are confined by a tiny constant.

Existing feature-based AT methods, however, assume that the nodes are independently distributed across the graph and the relationships between the samples are less considered or even disregarded. As a result, they often fail to facilitate AT on the graph structure and are insufficient to withstand more powerful adversarial attacks, particularly structure-based ones (See Section 5.3).

To evaluate the model performance and robustness on the semi-supervised node classification task, we conduct comprehensive experiments on four widely used datasets: Cora, Cora-ML, Citeseer, and Pubmed [41, 42]. We follow the previous work [7, 43] and randomly split each dataset into training (10%), validation (10%), and testing (80%) sets. The statistics of datasets are summarized in Table II. Here only the largest connected component of each graph is considered, same as [7, 43].

To comprehensively compare our proposed approach with several state-of-the-art methods, we consider the following four categories of methods: (i) Random and GCN-PGD from structured-based AT methods; (ii) BVAT, GraphVAT, and LAT from feature-based AT methods; (iii) Jaccard and SVD from adversarial purification methods and (iv) SimPGCN and MedianGCN from methods with robust architectures.

• •

  Random [8]: it is the simplest structure-based AT that randomly drops edges during each training step to generate adversarial examples.

• •

  GCN-PGD [13]: it is an attack-oriented AT that generates adversarial examples on the discrete graph structure based on projected gradient descent (PGD) attack.

• •

  BVAT [30]: it is a batch virtual AT that promotes the smoothness of GNNs by generating virtual adversarial perturbations.

• •

  GraphVAT [14]: it proposes a dynamic regularization technique based on virtual AT, to smooth the output and learn a robust GNN over adversarial examples.

• •

  LAT [31]: it proposes to employ AT on the first latent representation of GNNs and make GNNs more robust against adversarial perturbations.

• •

  Jaccard [25]: since attackers tend to connect nodes with large differences to achieve a better attack effect, it uses Jaccard similarity to preprocess the graph and filter out edges between nodes with low feature similarity.

• •

  SVD [27]: it adopts a truncated SVD to form a low-rank approximation of graph adjacency matrix to alleviate the adversarial behaviors. SVD is similar to our method, but it does not incorporate adversarial training into the learning phase.

• •

  SimPGCN [44]: it is an improved GNN with a feature similarity preserving aggregation, which effectively preserves node similarity while exploiting graph structure.

• •

  MedianGCN [28]: it is a state-of-the-art defense method, adopting median as the aggregation function of GNNs to enhance their robustness.

For the proposed SAT approach, we have five important hyperparameters to tune: (i) $\varepsilon_{1}$ and $\varepsilon_{2}$: the scales of adversarial perturbations on eigenvectors and eigenvalues, respectively; (ii) $\alpha$ and $\beta$: the weights for the two graph adversarial regularizers; (iii) $r$: the rank of the approximated graph. Particularly, we perform grid-search within a range of values and carefully tune the hyperparameters to balance classification power and model robustness. In this experiment, we set $\varepsilon_{1}=\varepsilon_{2}=0.1$, $\alpha=\beta=0.5$ for all datasets, while $r=30$ for small-scale datasets Cora, Cora-ML, and Citeseer, and $r=150$ for large-scale dataset Pubmed (see detailed discussion in Section 5.5). We employ SAT on three well-established GNNs, i.e., GCN, SGC and $\text{S}^{2}$GC detailed in Section 3.2. The resulting models are named GCN-SAT, SGC-SAT, and $\text{S}^{2}$GC-SAT, respectively. For SGC and S²GC, $K$ is set as 2 and 5 across all datasets, respectively. Additionally, we set $a=0.2$ for S²GC. The number of training epochs is set to 100 and Adam optimizer [45] is adopted to learn the model, with an initial learning rate of 0.01, 0.2, and 0.01 for GCN-SAT, SGC-SAT, and S²GCN-SAT, respectively. It is worth noting that SAT is not limited to the above-mentioned three GNNs and that the technique can be straightforwardly generalized for other GNNs.

For Random, we set the edge dropping ratio as 0.5 during training; For GCN-PGD, we use PGD attack [13] to generate adversarial examples, with perturbations rate set as 5% of the edges and the optimization step set as 10 in each epoch. For BVAT, GraphVAT and LAT, we tune the scale of adversarial perturbations on the (hidden) features in the range {0.01, 0.03, 0.05, 0.07, 0.1} to achieve the best performance. For Jaccard and SVD, we empirically tune the threshold of dropping dissimilar edges from {0, 0.01, 0.05, 0.08, 0.1} and the approximation rank from 30 to 500. We finally set the threshold as 0.01 and the approximation rank the same as SAT across all datasets. All the baselines are trained with Adam optimizer with an initial learning rate of 0.01. We train them for 200 epochs with early stopping, where we stop training if there is no further improvement on the validation accuracy during 50 epochs. All these baselines use GCN as the backbone model according to the authors’ implementations. For other hyperparameters, we empirically follow the default parameters in the original literature and fine-tune the model to achieve the best performance.

To evaluate the model robustness, we report the accuracy on the test set under the adversarial targeted attacks NETTACK [7] and PGD³³3Note that PGD is an untargeted attack method, we adapt the code provided by the authors to fit the targeted attack setting. [13], for which 1,000 nodes are randomly selected as targeted nodes from the testing set. For PGD attack, the iteration step is set as 100 to achieve the best performance. Both methods take GCN as the surrogate model to conduct attacks. We employ direct attacks where the perturbations are directly applied to connections of targeted nodes. We exactly follow the experimental settings in [43], which focus on the evasion attack scenario. Specifically, the perturbation budget is set as the node degrees. For all methods, we report classification accuracy averaged over 10 runs with different initial weights. We implement SAT with open-sourced software GraphGallery [46]. Code to reproduce the experiments is publicly available at https://github.com/EdisonLeeeee/SAT.

To empirically validate the effectiveness of our proposed SAT, we first investigate if the proposed algorithm will hinder the performance of standard GNNs on the clean datasets, i.e., the unperturbed datasets. In Table III, we report the classification results of three GNNs, GCN, SGC, and S²GC, on which standard training, SAT and SVD defense are employed, respectively. From the results, we have the following observations:

• •

  Although SAT adopts the rank-$r$ approximation of the graph structure and jointly optimizes the model with adversarial perturbations on the graph spectrum, the classification performance is not negatively affected in most cases. Note that SAT approximates the graph structure in a low-dimensional space, and thus leads to certain information loss. In general, the highest degradation is less than 2%, which is acceptable in practice.

• •

  Compared to SVD, a similar defense strategy that simply employs SVD as a low-rank preprocessing on the input graph, SAT achieves a better performance on the clean graphs. This suggests that although utilizing low-rank reconstruction would sacrifice the performance of the model on the graph, combining it with adversarial training can largely reduce such negative effects.

• •

  SAT is also beneficial to promoting the generalization performance of GNNs. For instance, the results on SGC with SAT have demonstrated the effectiveness, in which the classification accuracy has a slight improvement in all datasets. It indicates that slight perturbations indeed help to improve the generalization ability, which is consistent with previous studies [14, 30, 32].

We further investigate the robustness of GNNs with SAT against adversarial attacks. We plot the results in Figure 3. The experimental results are obtained by conducting NETTACK and PGD, two strong adversarial structural attacks, on the targeted nodes with direct attack setting. According to the results, we have the following observations:

• •

  Different GNNs show various robustness against adversarial attacks. Specifically, SGC slightly underperforms GCN since it drops the nonlinearity between hidden layers, and a linear model is more vulnerable against attacks [6]. We can also find that S²GCN outperforms GCN and SGC across the four datasets. The main reason for this might be that NETTACK and PGD both take GCN as a surrogate model, leading to better attack performance on GCN than its linear variant SGC.

• •

  A high level of robustness against the adversarial attack is achieved for GNNs with SAT. As can be seen, SAT remarkably improves the robustness of standard GNNs across all cases. We can find that the improvement of SAT is significant under both attacks, particularly PGD. Overall, the results affirmatively validate the claim that SAT does contribute to improving the robustness of GNNs. More specifically, the highlight of our approach is that SAT can greatly improve the robustness of GNNs while still maintaining classification accuracy.

Recall that SAT has a set of hyperparameters: $\varepsilon_{1}$, $\varepsilon_{2}$, $\alpha$, $\beta$, and $r$, we next study the effects of different values of hyperparameters on the performance of the proposed SAT. We take GCN employed with SAT as our base model in the ablation study.

We first investigate the effects of $\varepsilon_{1}$, $\varepsilon_{2}$, $\alpha$, and $\beta$, a GCN employed with SAT as our base model in the ablation study. Note that we only select GCN to tune the hyperparameters as SGC and S²GC yield similar trends, and the results are omitted for brevity. Figure 5 shows the model performance on Cora and Cora-ML, including the accuracy on the clean graph and the robustness against NETTACK on the perturbed graph. We use clean accuracy (clean Acc.) to refer to standard test accuracy (no adversarial perturbations) while adversarial accuracy denotes accuracy under attacks. For each hyperparameter, we vary the value in a range while the other hyperparameters are fixed with optimal values.

Firstly, $\varepsilon_{1}$ and $\varepsilon_{2}$ control the magnitudes of perturbations on eigenvector and eigenvalue perturbations, respectively. In Figure 5, the clean accuracy and adversarial accuracy of GCN-SAT first increase and then decrease as $\varepsilon_{1}$ and $\varepsilon_{2}$ are increased from 0 to 0.5. It is reasonable since small perturbations may be beneficial for the model generalization ability, while larger perturbations would have the opposite effect. For the model robustness, enlarging $\varepsilon_{1}$ consistently leads to better robustness, but overlarge $\varepsilon_{2}$ would degrade the performance. Considering both clean accuracy and model robustness together, we set $\varepsilon_{1}=\varepsilon_{2}=0.1$ as optimal values.

Secondly, $\alpha$ and $\beta$ are two trade-off hyperparameters to balance the regularization terms. Observed from Figure 5, it is clear that both clean accuracy and model robustness achieve an increase in performance when $\alpha\leq 0.5$ and $\beta\leq 0.5$, which means that the two regularizers are important for training. However, with the growth, the overall performance of the model would be negatively affected. Taking both clean accuracy and model robustness into account jointly, we set $\alpha=\beta=0.5$ as optimal values.

In addition to the above hyperparameters, $r$ is another important one to adjust for the model. The graph is approximated by the eigenpairs, where $r$ determines the richness of structural information. As demonstrated in [27], imposing high-rank changes to the graph can be greatly alleviated by discarding the high-rank components of the graph. Following this insight, we adjust $r$ to achieve better classification performance as well as high robustness.

To demonstrate the importance of different $r$, we run an ablation study by varying $r$ in four datasets w.r.t. NETTACK, and the results are displayed in Figure 6. As can be seen, with different values of $r$, GCN-SAT has a highly different sensitivity on the scale of the graph. In Cora, Cora-ML, and Citeseer, of which the graph is relatively small, we can see that a small number of $r$ is sufficient to capture the structural information and model the relationship between the nodes. Typically, a relatively good clean performance is achieved for $r=30$ and $r=50$ on the above three datasets. For a large-scale graph in Pubmed, a large $r$ is required to approximate the graph structure to avoid underfitting. The clean accuracy has a significant increase when $r$ is increased from 50 to 350.

As a coin has two sides, increasing $r$ has limitations as well as advantages. A large $r$ will lead to low robustness of the model since the perturbations are often high-rank [27]. As shown in Figure 6, the robustness of the model is decreased, despite the classification accuracy being increased with larger $r$. The results in Cora demonstrate a clear trend especially when $r$ is greater than 90. For the Pubmed dataset, the robustness of the model could benefit from a relatively large $r$ as the classification performance has simultaneously improved. But when $r$ is greater than 250, the robustness is also slightly degraded due to being affected by the high-rank perturbations.

In addition to the model robustness, training efficiency is also important. A larger $r$ indicates more computational overhead is required in the two additional forward-propagations. Therefore, a trade-off needs to be made for our proposed approach. Thus, we choose $r=30$ for Cora, Cora-ML and Citeseer, while $r=150$ for Pubmed.

To evaluate the contribution of low-rank approximation and spectral adversarial training, we first conduct ablation studies on SAT built upon GCN with $\alpha=\beta=0$, i.e., performing SAT with only low-rank approximation. As shown in Table V, the clean accuracy of SAT has decreased without adversarial training. When adversarial attacks are performed, the robustness of GCN is still improved by SAT even without incorporating spectral adversarial training. In this regard, it achieves a similar performance with SVD. Indeed, the low-rank approximation contributes significantly to the robustness of GNNs, as suggested in [27]. When incorporating with the spectral adversarial training, the performance of GCN-SAT can be also boosted against attacks, especially the adaptive attack PGD. Overall, the results reveal that although the low-rank approximation is important for improving the adversarial robustness of GNNs, the adversarial training can improve the generalization performance of GNNs and is beneficial for defending against adaptive attacks such as PGD.

In addition, we can also observe from Table V that SAT can also benefit SimPGCN, an improved GNN with robust architecture. The results demonstrate that combining different strategies with SAT further improves the model performance. Therefore, we believe that SAT can work as a general defense strategy when applied to different GNNs.