Adversarially Robust Neural Architecture Search for Graph Neural Networks

Despite the wide success of GNNs in various applications [47, 44, 43], GNNs are shown vulnerable to adversarial attacks [33, 53, 4, 2, 3, 39], i.e., slight perturbations to graph can lead to sharp performance decrease. Following the literature, adversarial attacks have various taxonomies according to the attacker’s knowledge (white-box attack and black-box attack), perturbation type (structure attack and feature attack), attack stage (evasion attack and poisoning attack), and targeted nodes (targeted attack and non-targeted attack).

In response to adversarial attacks, several defensive models have been proposed to enhance the robustness of GNNs. Graph pre-processing methods identify and rectify potential structural perturbations before the GNN model training. For example, with the assumption of feature smoothness, GCN-Jaccard [38] removes edges that have a low Jaccard similarity. Observing the high-rank tendency of the adjacency matrix under Nettack, GCN-SVD [8] reconstructs the adjacency matrix via its low-rank approximation. Graph attention methods aim to learn fewer attention weights on susceptible edges/features. For example, RGCN [51] uses Gaussian distribution for hidden layer node representations and calculates attention based on their variance. Pro-GNN [20] jointly learns graph structure and model parameters by keeping a low-rank and sparse adjacency matrix as well as feature smoothness. GNN-Guard [46] learns to focus more on edges between similar nodes and pruning edges between unrelated nodes. VPN [19] defenses by re-weighting edges from graph powering considering $r$-hop neighbors. Besides, graph certificate robustness methods [18, 35] provide a theoretical guarantee for graphs to be certified as robust under perturbation budgets. However, this branch is out of the scope of this work and we leave the comparison as a future work.

All previous studies rely heavily on manual designs and thus cannot adapt to new data, tasks, or adversarial attacks. Besides, existing methods neglect the inherent robustness of GNN architectures. On the contrary, our proposed method with specifically designed search space on graph structure can automatically search for the optimal robust GNN for different data and tasks.

Neural Architecture Search (NAS) is a proliferate research direction that automatically searches for high-performance neural architectures and reduces the human efforts of manually-designed architectures. NAS on graph data is challenging because of the non-Euclidean graph property and special neural architectures [42, 48]. GraphNAS [10] uses the recurrent network as the controller to generate GNN architectures and adopts reinforcement learning to search for optimal architectures. In order to conduct an efficient search, differentiable NAS approaches [26, 14] jointly optimize the model weights and architecture parameters. DSS [24] proposes a differentiable one-shot graph NAS and dynamically updates the search space. SANE [49] also utilizes a differentiable search algorithm and builds GNN architectures with the Jumping Knowledge Network (JK-Net) backbone [41]. GNAS [1] reconstructs GNNs with the designed GNN Paradigm and learns the optimal message-passing depth as well. GASSO [30] uses graph structure learning as a denoising process in the differentiable architecture searching process. Graph NAS is also used in complex graph data such as heterogeneous graphs [7] and temporal graphs [29]. However, the existing graph NAS methods do not consider robustness against adversarial attacks.

Robust neural architecture search exploits NAS to search for adversarially robust neural architectures. Since there is no related work for robust NAS on graph data, we review two remotely related papers on computer vision. RobNets [13] is the first work to explore architecture robustness. Through one-shot NAS, RobNets finetune architecture candidates via adversarial training and then sample more robust architectures. DSRNA [16] proposes two differentiable metrics which help to search robust architectures by a differentiable search algorithm. Our work is neither based on adversarial training nor adopts continuous relaxation for architecture parameters. To conclude, our work differs in that we consider a disparate search space tailored for graph data and leverage a different search algorithm.

Let $\mathcal{G}=(\mathbf{A},\mathbf{X})$ denote a graph with $N$ nodes, where $\mathbf{A}\in\mathbb{R}^{N\times N}$ is the adjacency matrix and $\mathbf{X}\in\mathbb{R}^{N\times D_{0}}$ is the corresponding feature matrix. For node $i$, its neighborhood is denoted as $\mathcal{N}(i)$.

Graph Neural Networks take the graph data as input and output node/graph representations to perform downstream tasks like node classification and graph classification. Typically, for node classification tasks with $C$ labels, we calculate:

where $\mathbf{z}_{i}\in\mathbb{R}^{C}$ is the prediction vector for node $i$, $f_{\bm{\alpha}}$ denotes the graph neural network based on architecture $\bm{\alpha}$. The design of GNNs could be divided into intra-layer design, inter-layer design, and learning configurations [42]. Intra-layer design often follows the message-passing paradigm [11]: nodes representation is updated by aggregating neighborhood information. A general formula for updating node representation in GNNs is denoted as

where $\mathbf{h}_{i}^{(l)}$ denotes the node representation for node $i$ in the $l$-th hidden layer, $e_{ij}^{(l)}$ is the correlation coefficient between node $i$ and $j$, $\tilde{\mathcal{N}}(i)=\{i\}\cup\mathcal{N}(i)$ represents the neighborhood of node $i$ with the self-loop, $\operatorname{Aggr}(\cdot)$ is the function to aggregate neighborhood information, $\operatorname{Comb}(\cdot)$ aims for combining self- and neighbor-information, and $\sigma(\cdot)$ is the activation function.

Besides the GNN layer design, how to connect different hidden layers is also critical. Some GNNs directly use the last hidden layer output as the prediction, while pre-processing layers, post-processing layers, and skip connections could also be added [22]. As for learning configurations, they are hyper-parameters for training GNNs like the learning rate, the optimizer, etc.

In general, graph NAS could be formulated as the following bi-level optimization problem:

where Eq. (3) is the upper-level optimization problem to find the best architecture $\bm{\alpha}^{*}$ in the search space $\mathcal{O}$, and Eq. (4) is the lower-level problem to calculate optimal model weights $\bm{W}$ for one particular architecture $\bm{\alpha}$. $\operatorname{Acc}_{val}$ represents the prediction accuracy on the validation set and $\mathcal{L}_{train}$ is the classification cross-entropy loss on the training set.

Existing graph NAS methods [48, 12, 50, 10, 1] design their search space following the message-passing scheme in Eq. (1). The most commonly used correlation coefficient operations are provided in Sec. B.2. NAS methods can search all components in Eq. (1) such as the aggregation function, correlation coefficients, and activation functions as well as hyper-parameters like hidden size and learning configurations. In this paper, we mainly consider searching for architectural designs.

Given a search space $\mathcal{O}$, we aim to find the optimal architecture $\bm{\alpha}^{*}\in\mathcal{O}$ with both high prediction accuracy and high adversarial robustness. We formulate the problem of robust neural architecture search for GNNs as:

where $\mathcal{R}(\cdot)$ is the robustness metric, and $\lambda$ is a hyper-parameter balancing the model accuracy and robustness.

We design a fine-grained search space following the message-passing paradigm. In total, there are six adjustable components in our GNN architecture: the graph structure mask, the nodes correlation coefficient, the neighbor aggregator, the combine function, the skip connection, and the layer aggregator. The first four components belong to the intra-layer operations, while the rest two components are inter-layer operations.

Inspired by the success of current defensive approaches [33], we conclude the properties of operations on graph structure for robustness and design representative defensive operations in our search space accordingly. In this way, we can choose the most appropriate defensive strategies when confronting perturbed graphs. To our best knowledge, this is the first time the search space to be designed with a specific purpose to enhance the robustness of GNNs. Specifically, we include five graph structure mask operations in the search space. Identity keeps the same graph structure as the previous layer. Low Rank Approximation (LRA) reconstructs the adjacency matrix in the $l$-th layer from the top-$r$ components of singular value decomposition from adjacency matrix in the previous layer. Node Feature Similarity (NFS) deletes edges that have small Jaccard similarities among node features. Neighbor Importance Estimation (NIE) updates mask values with a pruning strategy based on quantifying the relevance among nodes. Variable Power Operator (VPO) forms a variable power graph from the original adjacency matrix weighted by the parameters of influence strengths.

Moreover, more operations like graph structure learning [52] could be integrated into the graph structure mask operations. The formula for mask operations is shown in Table 1. We limit LRA and NFS in the first layer (only for pre-processing) and exploit the other three operations for all layers. It is worth mentioning that the graph structure mask candidates could be easily extended to other methods that deal with the graph structure, like denoising methods. Mask operations will not occlude the later message-passing process. They could be seen as orthogonal operations to other operations like the correlation coefficient.

For the other three components in the intra-layer, our choices for correlation coefficients follow the literature summarized in Table 4 in Appendix. Based on the masked graph structure $\mathbf{A}^{(l)}$ and correlation coefficients $\{e_{ij}^{(l)}\}$, a neighbor aggregator $\operatorname{Aggr}\in\mathcal{O}_{aggr}$ is used to aggregate neighborhood representations. Afterwards, a combine function $\operatorname{Comb}\in\mathcal{O}_{comb}$ merges self- and neighbor-message. Here, we explore two typical approaches to combine self-representation and neighbor-message, namely GraphSAGE [15] and GIN [40]. GraphSAGE conducts different feature transformations for node representation and neighborhood information. GIN first performs weighted sum for self- and neighbor-message, then uses multi-layer perceptron to improve GNN’s expressive power. After combining messages, the activation function $\sigma(\cdot)$ is applied. Overall, the hidden representation for node $i$ in the $l$-th layer is calculated as

The node representation is initialized as node features, i.e., $\mathbf{h}^{(0)}=\mathbf{X}$.

We summarize all components and their candidate operations in Table 2. Our search space is expressive and, more importantly, has improved defense capability. As shown in Table 5 in Appendix, our search space could recover some classic manually designed GNNs and state-of-the-art robust GNNs like GCN-SVD, GCN-Jaccard, GNN-Guard, and VPN.

This part will introduce how to measure the architecture’s robustness and the specific search process using the evolutionary algorithm with our robustness metric.

Intuitively, the performance of a robust GNN should not deteriorate too much when confronting various perturbed graph data. Let $\mathcal{T}_{\Delta}$ denote the attacker of the graph data with perturbation budgets $\Delta$. We define the robustness metric as

where $f$ indicates the GNN, $f(\mathbf{A})_{i}$ is the probability prediction vector for node $i$ and $D_{KL}(p||q)=\sum_{i}p_{i}\log\frac{p_{i}}{q_{i}}$ denotes the Kullback-Leibler (KL) divergence between two distribution $p$ and $q$. Here, we use KL distance to measure the prediction difference given clean and perturbed data. The choice of our attack proxy $\mathcal{T}$ varies from simple random attack [5] or DICE [54] to advanced attack methods like Mettack [54] or Nettack [53]. Within the same perturbation budgets $\Delta$, our attack proxy generates $T$ perturbed graph structure $\{\mathbf{A}^{\prime}_{t}\}_{t=1}^{T}$. Eq. (9) could be approximately computed as

A larger $\mathcal{R}(\mathbf{A},f)$ indicates a smaller distance between the prediction of clean data and the perturbed data, and consequently, more robust GNN architectures.

In order to illustrate the effectiveness of the proposed robustness metric, we randomly choose 300 architectures and calculate their robustness metric value and evaluate their performance decrease after 5% structural perturbations in the Cora dataset (the experimental details are described in Sec. 5.2). Fig. 2(a) displays the distribution of $\mathcal{R}$ in log scale while Fig. 2(b) shows the mean accuracy decrease for different $\mathcal{R}$ intervals. The accuracy decrease could be regarded as a ground-truth measurement of the actual robustness. From Fig. 2(b), we could see that the mean accuracy decrease has a negative correlation with respect to the robustness metric. When the robustness metric is relatively small, the accuracy may be reduced by as large as 10%. However, when the robustness metric is large, the accuracy decrease shrinks to about 3.5%. This phenomenon indicates that our robustness metric could successfully filter robust architectures.

In the semi-supervised node classification task, we perform non-targeted poisoning structural attacks adopting Mettack [54] and evaluate GNN robustness based on perturbed graphs. We vary the proportion of changed edges from 0% to 25% and calculate the retrained accuracy on perturbed graphs. For each setting, we experiment 10 times and report the average results and the standard deviation. The final defense results are summarized in Table 3. More information on searched architectures by G-RNA under attacks is provided in Sec. C.3.

Overall, our G-RNA successfully outperforms all baselines under adversarial attacks. We could see an apparent increase in perturbation performance when confronting heavily poisoning attacks (e.g. when the proportion of changed edges is 15% or more). For instance, the defense performance of G-RNA under 25% structural perturbations exceeds that of vanilla GCN by 23.4%, 20.9%, and 12.1%, respectively. For NAS-based methods, optimal architectures searched on clean data are evaluated on both clean and perturbed graphs to test their robustness and conduct a fair comparison. We could see that there does exist a trade-off between architecture accuracy and robustness. Though GraphNAS shows impressive results on clean graphs, its vulnerability under adversarial attacks is also obvious, e.g. GraphNAS’s performance under adversarial attacks is even worse than that of classic GNNs sometimes. Thus, it’s necessary to make Graph NAS more robust. In CiteSeer, the performance for G-RNA under 20% and 25% structural perturbations are almost twice that of GraphNAS, which shows the strong defense ability of our method.

For understanding the robustness of various GNN components, we randomly sample 300 architectures and evaluate their performance on clean and attacked graphs. To make a fair comparison, we keep the same training configurations for all selected architectures. Specifically, we train each architecture for 200 epochs with a learning rate of 0.005 and a weight decay of 5e-4. We use the decrease in classification accuracy as the measurement and report the results on the Cora dataset under Mettack (5% perturbation rate), while other datasets show similar trends. The less the performance of one architecture decreases, the more robust that architecture is.  Fig. 4(a) and Fig. 4(b) show boxplots for the robustness under various architectural designs. For each subplot, the top figure displays the relationship between the operation choice and model test accuracy on the clean graph, while the bottom one shows the operation robustness via accuracy decreases. We make the following observations.