Scalable Adversarial Attack on Graph Neural Networks
with Alternating Direction Method of Multipliers

We first define the notation in this paper, as summarized in Table 2. We consider an input graph $G=(A,X)$, where $A\in\{0,1\}^{N\times N}$ is the adjacency matrix on the edge connection between nodes, $X\in\mathcal{R}^{N\times D}$ is the associated node features, $N$ is the number of nodes in the graph, and $D$ is the feature dimension of each node. Here, only a portion of nodes $V_{GT}$ are labeled and the goal of node classification is to predict labels for remaining nodes. Following the common practice in the field (Xu et al. 2019a; Zügner, Akbarnejad, and Günnemann 2018), we focus on the well-established work that utilizes graph convolutional layers (Kipf and Welling 2017) for node classification. Formally, the $i^{th}$ layer is defined as

where $\tilde{A}=\tilde{D}^{-\frac{1}{2}}(A+I_{N})\tilde{D}^{-\frac{1}{2}}$ to achieve numerical stability, $D$ is a diagonal matrix with $D_{ii}=\sum_{j}(A+I_{N})_{ij}$, and $W^{(k)}$ is the weights for the $k^{th}$ layer. Since the memory and the computation complexity generally increase as the number of layers increases, we focus on a single layer GCN that is tractable and still captures the idea of graph convolutions:

Here, the output $Z\in\{1,2,...,c\}^{N}$ is the predicted labels for individual nodes. The parameter $W$ is learned by minimizing the cross-entropy on the output of labeled nodes.

where $Y_{v}$ is the ground truth label for node $v$. Our experiments show that adversarial examples on this single layer GCN model transfer well to GCNs with various layers and other GNN models such as GAT. Besides, recent studies (Zügner, Akbarnejad, and Günnemann 2018) show that a L-layer GCN can also be treated as $\sigma(A^{L}XW^{L})$ to generate adversarial attacks with tractable computation.

In this paper, SAG aims to generate a perturbed adjacency matrix $\tilde{A}\in\{0,1\}^{N\times N}$ and a perturbed feature matrix $\tilde{X}\in\mathcal{R}^{N\times D}$ satisfying a pre-defined perturbation budget. Similar to (Xu et al. 2019a), we use a Boolean matrix $S\in\{0,1\}^{N\times N}$ to record the edge perturbations that $S_{ij}=1$ indicates the perturbation of edge between node $i$ and node $j$. Given the original adjacency matrix $A$ and its supplement matrix $\bar{A}$ (i.e., $\bar{A}_{i,j}=\neg A_{i,j}$), we can generate the perturbed adjacency matrix as $\tilde{A}=A+(\bar{A}-A)\circ S$, where $\circ$ is the Hadamard product. Formally, given the edge perturbation budget $\epsilon_{A}$ and the feature perturbation budget $\epsilon_{X}$, SAG aims to solve the following optimization problem

For notation simplicity, we use $\ell(S,\tilde{X})$ to represent the cross-entropy loss $\ell(S,\tilde{X};W,Y_{GT})$ when the context is clear. Following the common practice (Zügner, Akbarnejad, and Günnemann 2018; Xu et al. 2019a) in the field, we consider two threat models – the evasive attack and the poisoning attack. The evasive attack assumes that the GNN model is fixed and targets the test data. The poisoning attack targets the training data and performs the model training phase on the perturbed data after the attack.

There are several challenges in solving this optimization problem. First, the popular stochastic gradient descent (SGD) methods cannot effectively solve optimization problems under constraints and usually require ad-hoc modification on the gradients to satisfying such constraints. Second, the discrete modification on the edge perturbations makes it a combinatorial optimization problem. (Zügner, Akbarnejad, and Günnemann 2018) attacks the graph topology by changing one edge at one time and selecting the edges that achieve the maximum loss. However, this approach needs to trial-and-error on all edges, leading to prohibitive time cost. (Xu et al. 2019a) takes gradient on the $S$ matrix by releasing the requirement $S\in\{0,1\}^{N\times N}$ to be $S\in[0,1]^{N\times N}$. However, this approach takes $N\times N$ memory to store the gradient matrix, which is prohibitive for large graphs with tens of thousands of nodes. Besides, (Xu et al. 2019a) only supports topology attack and cannot conduct joint attack on the node features. We detail ADMM-based SAG on solving the optimization problems under constraints in later sections.

SAG achieves a scalable attack on graph data by splitting the matrix $S$ into multiple partitions and consider one partition at each time, as illustrated in Figure 1. Supposing we split the graph into $M$ partitions, we only need to take gradient on a small matrix with shape $\frac{N}{M}\times N$ that can easily fit into the memory. Similar to (Xu et al. 2019a) and the probabilistic view of node classification problem, we first release the discrete constraints $S\in\{0,1\}^{N\times N}$ to continuous constraints $S\in[0,1]^{N\times N}$, where $S_{ij}$ indicates the probability that an edge needs to be perturbed for attack. Since the impact between node $i$ and node $j$ may be asymmetry (i.e., the impact of node $i$ on node $j$ is higher than the reverse one), we do not apply symmetry constraint on $S$. Then, we split $S\in[0,1]^{N\times N}$ into $M$ sub matrix such that $S_{i}\in[0,1]^{(N/M)\times N}$, where $S_{i}$ considers the nodes with index between $[\left\lfloor i*\frac{N}{M}\right\rfloor,\left\lfloor(i+1)*\frac{N}{M}\right\rfloor]$. Due to the cumulative property in cross-entropy loss, we can attack by solving the following optimization problem

Here, $\epsilon_{i}$ represents the allowed number of edges to change in each graph partition $S_{i}$ and we set it to be $\frac{\epsilon_{A}}{M}$ for simplicity.

Ideally, we can split the problem 6 into $M$ sub-problems and solve them independently for memory efficiency. However, problem 6 still has interaction between $M$ sub-problems on the $\tilde{X}$ term. To this end, we further reformulate the problem 6 into the following problem by substitute $\tilde{X}\in\mathcal{R}^{N\times D}$ with a duplicated feature matrix $\tilde{X}_{i}\in\mathcal{R}^{N\times D}$

For notation simplicity, we use $\tilde{X}_{M+1}$ to represent $\tilde{X}_{1}$. $I_{C}(x)$ is an indicator function such that $I_{C}(X)=0$ if $X\in C$, otherwise $I_{C}(X)=\infty$. $C_{Si}$ and $C_{Xi}$ are feasible sets

Here, the popular SGD cannot be easily applied to the optimization problem 7 under constraints, especially the equality ones. To this end, we can adopt the ADMM framework to systematically solve the problem. First, we have the Lagragian function $$\begin{split}L_{\rho}(\tilde{X}_{i},S_{i},\mu_{i})=&-\sum_{i=1}^{M}\ell(S_{i},\tilde{X}_{i})+\sum_{i=1}^{M}I_{C_{Xi}}(\tilde{X}_{i})+\sum_{i=1}^{M}I_{C_{Si}}(S_{i})\\ &+\frac{\rho}{2}\sum_{i=1}^{M}||\tilde{X}_{i}-\tilde{X}_{i+1}||^{2}+\sum_{i=1}^{M}\mu_{i}^{T}(\tilde{X}_{i}-\tilde{X}_{i+1})\end{split}$$ (9) where $\rho>0$ is a hyper-parameter and $\mu_{i}\in\mathcal{R}^{N\times D}$ is the dual variable.

Following the ADMM framework, we can solve the problem 7 by repeating for $k\in\{1,2,...,K\}$ iterations and, in each iteration, solving each $S_{i}$ and $\tilde{X}_{i}$ individually

which is respectively the feature update, topology update, and dual update. We stress that we only need to solve the minimization problem for a single graph partition $S_{i}\in\mathcal{R}^{\frac{N}{M}\times N}$, leading to much reduced memory consumption compared to (Xu et al. 2019a), which requires solving the whole graph $S\in\mathcal{R}^{N\times N}$ at the same time. Here, the main memory overhead comes from the duplicated feature $\tilde{X}_{i}\in\mathcal{R}^{N\times D}$. However, the feature dimension $D$ is usually a fixed number around $1000$, which is much smaller than the number of nodes $N$ that may reach tens of thousands, or even millions.

In this section, we present how to efficiently solve the above problem and derive closed form formula for individual minimization problems.

After $K$ iterations, $\tilde{X}_{i}$ will be identical to each other and can be directly used as the feature perturbation $\tilde{X}$. Recalling that $S_{i}$ is a probability whether an edge needs to be perturbed for attack, we use Bernoulli distribution to sample a $0\text{-}1$-valued edge between each pair of nodes. We repeat this sample procedure for $20$ times and select the one with minimal loss for the final perturbed topology $S\in\mathcal{R}^{N\times N}$.

The memory complexity of SAG is

for storing graph partition $S_{i}$ and feature perturbation $\tilde{X}_{i}$, respectively, since we only need to optimize one graph partition at each iteration. We store only the current graph partition in the limited GPU memory (around 10 GB) and offload the remaining graph partitions to the large host memory (more than 50 GB). Note that the same implementation strategy cannot be applied to (Xu et al. 2019a) which requires attacking the whole graph $S\in\mathcal{R}^{N\times N}$ at each iteration.

Table  4 shows the overall performance comparison between SAG and existing adversarial attacks under the same setting of topology ratio and feature ratio. Following the most common setting used by many previous papers (Zügner, Akbarnejad, and Günnemann 2018; Xu et al. 2019a), we select the same topology attack ratio of $5\%$ and feature attack ratio of $2\%$, and leave the study on diverse ratios to the ablation study. On PGD and FGSM, we only attack the topology and features, respectively, due to their limits in attacking capability. In SAG, we stick to M=2 and will exhibit the impact of M in the ablation study. We observe that SAG consistently outperforms the state-of-the-art attack approach, such as FGSM, PGD, and Nettack on evasive attack (up to $14.82\%$ accuracy drop) and poisoning attack (up to $41.26\%$ accuracy drop) across different datasets. On Pubmed dataset, SAG achieves $14.82\%$ accuracy drop in evasive attack and $41.26\%$ in poisoning attack. The major reason for such success is that SAG enables the gradient-based joint optimization on both the features and topology while incorporating global reasoning on the interaction between attacking different nodes. By contrast, FGSM and PGD attack only the feature or topology, and Nettack considers only one edge at each time, failing to reason the global interaction across edges and nodes.

Across different datasets and settings, we notice that Nettack always comes with the highest time cost. The reason is that, at each iteration, it selects only one edge or feature to attack by examining all edges and node features, and repeats the procedure until reaching the topology ratio and the feature ratio. Moreover, we observe that PGD usually has the highest memory consumption, since it requires a floating-point $N\times N$ matrix to store the edge gradients between each pair of nodes, where $N$ is the number of nodes. For Pubmed, a single matrix of this shape requires at least $1.5$ GB to store and PGD processes the whole matrix at each iteration, instead of processing only a small partition as the case in SAG. Besides, in the time and memory comparison among these implementations, we notice the significant strength of SAG, which achieves up to $254\times$ speedup and $3.6\times$ memory reduction. This is largely due to our effective algorithmic and implementation optimizations that can reduce the runtime complexity meanwhile amortizing the memory overhead to great extent.

In this ablation study, we will focus on two representative datasets – Cora and Pubmed – for the performance of SAG on a small graph dataset and a large graph dataset.

ADMM Convergence Behavior We show the ADMM convergence behavior in Figure  2. Here, we adopt the same number of epochs as $T=200$ and show only the first $70$ epochs in Figure 2(b) and Figure 2(c) since SAG converges fast on $||\tilde{X}_{i}^{(k)}-\tilde{X}_{i+1}^{(k)}||_{2}$ and $||\tilde{X}_{i}^{(k+1)}-\tilde{X}_{i}^{(k)}||_{2}$. We only present the result for $i=1$ since various $i$’s show similar results. Overall, SAG converges gracefully as epoch increases, demonstrating the effectiveness of our method. In Figure 2(a), with the increase of the epoch number, SAG gradually increases the attack loss by perturbing the features and the topology. In Figure 2(b), $||\tilde{X}_{i}^{(k)}-\tilde{X}_{i+1}^{(k)}||_{2}$ starts from 0 since we initialize both $\tilde{X}_{i}$ and $\tilde{X}_{i+1}$ to the node features on clean graph dataset. Compared across different datasets, Pubmed converges faster than Cora since Pubmed contains much smaller feature dimension than Cora.

Topology and Feature Perturbation For poisoning attack on Cora dataset (Table 5), the increase of feature perturbation and topology perturbation would both lead to the accuracy drop compared with the original clean data. Besides, we observe that, at the same level of topology perturbation, $8\%$ feature perturbation can lead to $3.6\%$ extra accuracy drop on average. On Pubmed dataset, we observe that $8\%$ feature perturbation can lead to $9.4\%$ extra accuracy drop, averaged over various topology perturbation ratio. These results show the benefit of attacking both topology and features.

M-value Impact We also evaluate SAG for poisoning attack on Pubmed to show the impact of the hyperparameter M (i.e., the number of graph partitions) on memory saving. As shown in Table 6, with the increase of the M value, the memory size reduction becomes significant, since splitting the graph into M partitions and attacking individual partitions at each time essentially reduce the memory requirement. We also observe similar accuracy drop under different M since SAG converges gracefully and hits similar optimal points for diverse M. Meanwhile, we also observe that the increase of value M also brings the runtime overhead in terms of time cost, for example, M=8 setting is 33 minutes slower than M=4 setting. This slowdown happens since we need to attack individual split graphs at each time, leading to a small portion of system overhead on memory access. This also leads to a tradeoff among these factors when selecting the value of M. We also observe that the memory consumption does not decrease linearly as K increases. The main reason is that, as M reduces, memory consumption from other sources (e.g., loading PyTorch framework and the features) becomes the dominant component.

Transferability To demonstrate the transferability of SAG, we further evaluate our attacked graphs (Cora and Pubmed) on GCNs (with 1, 2, and 4 layers) and GATs (with 1, 2, and 4 layers), respectively. We generate adversarial examples on a 1-layer GCN model and conduct poisoning attack on other models by targeting the training data and training these models on the perturbed data. As shown in Table 7, SAG can effectively maximize the accuracy drop on Cora (up to 13%) and Pubmed (up to 42%). The major reason for such success in launching the poisoning attack is that the adversarial attack on 1-layer GCN effectively captures the intrinsic property on the graph data that is agnostic to the models. We want to stress that, even on models with different layers (i.e., 2 and 4), the poisoned graph data can still achieve $8\%$ and $9\%$ accuracy drop on Cora and Pubmed, respectively. These results demonstrate the transferability of SAG towards models with diverse architectures and the number of layers.