Are Gradients on Graph Structure Reliable in Gray-box Attacks?

Introduction

Graph Neural Networks (GNNs) demonstrate excellent performance on various applications with structural, relational data (Zhou et al. 2020), such as traffic (Wang et al. 2020), recommendation systems (Guo et al. 2020), and social networks (Wang et al. 2019). As the prospects for the applications of GNNs expand rapidly, their reliability and robustness are beginning to be of interest. Several works have presented experimental evidence that GNNs are vulnerable to adversarial attacks (Zügner et al. 2018; Zügner and Günnemann 2019; Dai et al. 2018). They design undetectable perturbations which successfully mislead GNNs’ prediction of targeted nodes or degrade the performance on a global scope. Subsequently, many works have been carried out around the graph adversarial attack and defense (Xu et al. 2020; Sun et al. 2018).

Gray-box attacks allow attackers to access the training labels from the victim model. The attacker aims to damage the prediction of the victim model by injecting indistinguishable perturbations into the graph. The attacker should search for vulnerable edges and attack them by modifying the graph. In the field of adversarial attack, gradients are widely-used for attacking attributes that are spatially continuous (Xu et al. 2020). However, for graphs, the sparseness and discreteness of the graph structure make it challenging to perturb the graph structure in the way of Fast Gradient Sign Method (FGSM) (Goodfellow et al. 2015) or Projected Gradient Descent (PGD) (Madry et al. 2018). To solve this problem, Zugner et al. (Zügner and Günnemann 2019) firstly introduce the meta-gradient on the graph structure to determine the perturbation. The attacker chooses one edge at a time to perturb based on the saliency of the gradient and iterates this step until the entire attack budget is consumed. Subsequent works focus on improving the attack strategy after deriving the gradient and the surrogate model (Lin et al. 2020; Liu et al. 2022). However, few works focus on whether the saliency of the gradient on the graph structure is reliable.

Meta-gradients are demonstrated to be noisy in attribution problems (Sundararajan et al. 2017). The gradients on the graph structure originate from the aggregation of node features, which means noises are equally propagated into the structural gradients. Moreover, edge flipping changes the value of edges across a considerable step size (i.e., adding edges are from 0 to 1 and deleting edges are from 1 to 0). Existing methods select the edge to be flipped based on the saliency of the gradient. It is worth noting that, during the edge flipping, the structural gradient varies since the aggregation of node features is influenced by the edge value. We consider edge perturbation to be a problem of modeling continuous gradient distributions rather than a discrete problem. However, the structural gradients are imprecisely assumed to be constant, ignoring the variance in the edge-flip interval.Corresponding author: Stan Z. Li.

This paper points out the gradient errors that negatively affect the untargeted gray-box attacks on graph structure. The discreteness of edges leads previous works to consider edge perturbation as a discrete problem about gradients. However, the gradient at the current edge state commonly used in previous works is inaccurate for describing the gradient over the edge-flip interval. We propose to transform the edge perturbation from a discrete problem to an approximation of a continuous problem and propose edge discrete sampling to reduce this error. Edge discrete sampling calculates the gradient of the transition process between the edge-flip interval in batches. It reduces the error from the discrete approximation to the continuous gradient distribution, which performs a more accurate structural gradient estimation. Since the space of edge perturbations is about the square of the number of nodes, the computational cost is unacceptable if the edge discrete sampling is performed for the whole space. Hierarchical candidate selection is then proposed to reduce the computational complexity. It retains a bag of candidate edges that are more likely to be effective than processing the whole space. In this step, we exploit the saliency of the gradient on the graph structure while the error still exists. The random initialization of parameters leads to variance in surrogate model training, which affects the structural gradients via back-propagation. Besides, the error occurs in gradient fluctuations on semantically identical graph augmentations. These two errors are to be considered since gray-box attacks focus on attack transferability, so the gradient information from the surrogate model is expected to be more general and representative. To address these errors, we first propose momentum gradient ensemble to mitigate the instability of the structural gradients provided by the surrogate model at each attack iteration. Then, we propose surrogate semantic invariance based on graph augmentation in a limited semantic range. These two methods of reducing the error on the gradient of the graph structure allow hierarchical candidate selection to provide better quality edge candidates. Candidate selection ensures that the computational cost of edge discrete sampling does not grow exponentially, allowing the attacker to perform poisoning attacks.

The contributions of this paper are summarized as follows:

We analyze the errors in structural gradients caused by model instability and the discreteness of graph structure in untargeted gray-box attacks.

We propose edge discrete sampling to approximate the continuous distributions of gradient over the edge-flip interval. Hierarchical candidate selection is proposed to ensure that the computational complexity does not explode.

We propose semantic invariance and momentum gradient ensemble to address the gradient fluctuation on semantic graph augmentation and the instability of the surrogate model.

We demonstrate the improvement of our approach and prove each module’s effectiveness in the ablation study.

Preliminaries

Before presenting the methodology and demonstrating the experiments, we first introduce the notations and backgrounds in this section. The notations used in the following sections can be referenced in Subsection 2.1. Subsection 2.2 introduces how to obtain the gradient on the graph structures by attacking loss in a generic attack strategy with edge perturbations.

2. Edge Perturbations

In the case of untargeted edge perturbation, the attacker is restricted to perturbing only by modifying the adjacency matrix (i.e., flipping edges). The $l_{0}$ norm of the changes in the perturbed adjacency matrix with respect to the original one is bounded by the attacker’s budget $\Delta$. For an undirected graph, $\Delta$ is set as:

where the budget $\Delta$ is generally equal to or less than 5% of the number of edges in the original graph.

Gradient-based attack models now become mainstream methods of edge perturbations on the graph structure (Zügner and Günnemann 2019; Xu et al. 2019; Lin et al. 2020). In contrast to the gradient-based attacks widely used in computer vision (Yuan et al. 2019), the discrete graph structure restricts the gradient from being added directly to the adjacency matrix. The gradient on the adjacent matrix (i.e. graph structure) (Zügner and Günnemann 2019) $A^{grad}$ can be derived by the following equations:

where $\mathcal{L}_{atk}$ is the attack loss function and $f_{\theta^{*}}$ is the properly trained surrogate model. To facilitate understanding, we elaborate in a more intuitive way of deriving $A^{\,grad}$. First, a GNN surrogate model $f_{\theta^{*}}$ is trained until it fits the training samples. Subsequently, the attack loss is backpropagated through the surrogate model generating gradients on the input adjacency matrix. The attack loss is expressed as $\mathcal{L}_{atk}=-\mathcal{L}_{CE}$, which is a negative cross-entropy loss. For the edge between nodes $v_{i}$ and $v_{j}$, if $A_{i,j}=1$ and $A^{grad}_{i,j}<0$, or if $A_{i,j}=0$ and $A^{grad}_{i,j}>0$, then flipping edge $E_{i,j}$ is considered as a perturbation that has the potential to negatively affect the victim model. Among these edges, the one with the most significant gradient value is considered the most desirable perturbation for the current graph. The process of perturbing the graph using the gradient information can be represented as:

where $\phi$ denotes the strategy for choosing the edge to be attacked. The factors that influence the perturbation include the attack loss $\mathcal{L}_{atk}$ as well as the strategy $\phi$ and the surrogate model $f_{\theta^{*}}$.

Methodology

This section introduces the errors of the gradient on the graph structure and the methods to solve these errors. Section 3.1 first analyzes the error caused by interpreting edge perturbations as a discrete problem and proposes the solution edge discrete sampling. To rationalize the computational cost, we propose hierarchical candidate selection. It selects a bag of edge candidates based on the meta-gradient on the graph structure so that edge discrete sampling requires only a small number of edges to be processed in batches. When we rethink the meta-gradient on the graph structure, we find room for improving the reliability of the structural gradient. We analyze and discuss this part in Sections 3.2 and 3.3 and give the corresponding solutions. Section 3.4 describes the overall attack flow.

As indicated by Eq.2&3, the gradient on $A_{ij}$ is the partial derivative of the attack loss $\mathcal{L}_{atk}$ to the adjacent matrix. In the existing approaches, the attackers treat the gradients on graph structure as a discrete problem of choosing the perturbations directly based on the saliency of the gradient (Zügner and Günnemann 2019; Lin et al. 2020). This means that the previous approach assumes that the gradient value is maintained at its value on the original state of the edge during the edge flipping (i.e., the state of an edge turns from 0 to 1 or from 1 to 0). We give an example of the gradient approximation error introduced by this approach in Fig.1. In contrast, we consider the gradient used to determine the edge perturbation as a continuous problem with continuous distribution approximation.

where function $top_{\,C}$ extracts $C$ edge candidates of high saliency from the gradient matrix. For these candidates, we reduce the time complexity to $O(C/\delta)$, where $C<<N^{2}$. Up to this point, the time complexity of the algorithm is still enormous because $\delta$ is tiny. Therefore, in order to reduce the error while being able to ensure computational efficiency, we propose a discrete sampling method to approximate the continuous gradient distribution. The expression of the this approximation is:

where $g_{uv}^{int}$ represents the integral gradient as the edge flips from 0 to 1 and $f_{\theta^{*}}(A_{uv}=s\lambda,X)$ is the result of modifying $A_{uv}$ to a transitional value $s\lambda$ without retraining. The solid thick green line in Fig.1 indicates the approximation by our algorithm, and the area in the thin green slash indicates the error caused by ours. Compared with the error of the previous method indicated by the blue shading, our method substantially reduces the error generated in the edge-flipping process. Based on the above algorithm, the time complexity of our method decreases to $O(C/\lambda)$. Considering that a perturbation can add or delete an edge, we adopt the one with the highest saliency of integrated gradient as a perturbation:

where $e^{\prime}$ denotes the selected edge to be perturbed, $(1-2A_{uv})$ is to invert the value of $g_{uv}^{int}$ for those candidates to delete an edge.

To further increase the computational efficiency, we introduce batch processing of candidates. A batch contains batch size $bs$ candidates. Since the gradients on the adjacent matrix come from the aggregation of node features, for a general 2-layer graph neural network, the state of one edge will influence the gradient on the other when the same node joints two edges. In other words, simultaneously changing the states of both edges causes a small amount of error. However, for a batch of candidates selected from $N^{2}$ space, the probability that the candidates happen to be connected is minimal. Therefore we adopt batch processing which reduces the time complexity to $O(C/(\lambda*bs))$.

The method mentioned in Section 3.1 has a high dependence on the gradients on the adjacency matrix $A^{\,grad}$. Hierarchical candidate selection selects $C$ from the $N^{2}$ space, which requires strong reliability and stability of the gradients. In Sections 3.2 and 3.3, we discuss the errors present in $A^{\,grad}$ as well as their solutions.

2. Error Caused by Uncertainty of Model Optimization

When the samples are not dense enough to describe the manifold of the data, the model is prone to fall into local optima. The local optima of a model based on backpropagation optimization is related to the initialization of the mapping function of the neural network (i.e., the initialization of the learnable weights). For the surrogate model, it tends to perform differently after retraining with different parameter initializations (i.e., in Equation 2 different $\theta$ leads to different $\theta^{*}$). We give an example to verify the uncertainty of structural gradients $A^{\,grad}$, shown in Fig.2.

Fig.2 shows the gradients on two edges of the consistent graph after retraining the surrogate model with different weight initializations. We can see that the gradient expectation of Edge 2 is around 0.007, which is higher than 0.004 of Edge 1. We conduct experiments showing that attacking Edge 2 is more effective than attacking Edge 1. However, due to the randomness of weight initialization, the gradient of Edge 1 is possible to be higher than that of Edge 2, thus misleading the attacker to make a wrong judgment.

To enhance the reliability of $A^{\,grad}$ at each attack iteration, we expect each structural gradient obtained from the surrogate model to be as close as possible to its expectation in such distribution shown in Fig.2. To this end, there is an easy way to solve this problem using an ensemble algorithm. We sample several weight initializations and integrate the gradients from retrained surrogate models to approximate the expectations of the structural gradients, reducing the probability of the gradient being sampled to outliers. The expression of the gradient ensemble is:

where $\theta^{*}_{i}$ represents the parameters of the surrogate model after training under initialization $\theta_{i}$ and $k$ denotes the number of integrations. This is an ensemble-based method that randomly initializes the model parameters with the identical uniform distribution between $$. However, retraining the surrogate model is unacceptable, for it causes$k$ times the computational cost to be spent.

Considering that the attack on graph edges is a perturbation-by-perturbation iterative process, we propose a momentum gradient ensemble as a more efficient solution. The variation between perturbed graphs $G^{{}^{\prime}}_{t}$ and $G^{{}^{\prime}}_{t-1}$ is limited. The structural gradient $A^{\,grad}_{t}$ at iteration $t$ can reduce the instability of the gradient brought by each retraining of the surrogate model by fusing the structural gradient at previous iterations. The derivation of the structural gradient at attack iteration $t$ is redefined as:

where $p$ is the coefficient of the momentum term. Compared with the ensemble method in Equation 8, our momentum-based method consumes no additional computational cost. It makes full use of the structural gradients from previous iterations and avoids retraining the surrogate model multiple times in a single iteration.

3. Error Caused by Model’s Unrobustness

The gradients of continuous data features are demonstrated to be noisy (Sundararajan et al. 2017). Similar to data features, the graph structure is explicitly involved in the forward process in GNNs. Taking a 2-layer GCN as an example, the expression of the forward process of graph neural network and the structural gradient is shown below.

where $\hat{A}$ is the normalized adjacent matrix, $\tau$ is the activation function, $W$ is the weight matrix, $\mathcal{L}_{atk}$ equals to $-\mathcal{L}_{ce}$ and $P(y^{\prime}_{i}|f_{\theta})$ represents the prediction at label class $y_{i}$. It can be seen from Eq.10,11&12 that the derivation of the structural gradient involves the features of the nodes (which is related to the message passing mechanism in GNNs), resulting in the noise on the features being able to be propagated to the structural gradient. The graph structure explicitly participates in the forward process of the model, so both input features and model parameters are influencing factors of the structural gradient. Therefore, similar to the sample features, the structural gradient is noisy.

Fig.3 is an example which shows the gradients on an example edge on Citeseer (Sen et al. 2008). It is a citation network in which $10^{-3}$ can be considered as a non-disturbing semantic perturbation for node attributes. We inject Gaussian noise on the attributes of nodes $v_{i}$ and $v_{j}$ and their 1-hop neighbors, where the horizontal axis of Fig.3 is the expectation of Gaussian noise and the vertical axis is the value of the gradient. As can be seen in Fig.3, Gaussian noise with a standard deviation of $10^{-3}$ can make the gradient noisy. Considering the need for transferability for gray-box attacks, the instability of the surrogate model in the semantic range will affect the attacker’s estimation of the retrained victim model.

It is worth noting that the noise is added to the node attributes rather than the graph structure. We consider adding noise to the graph structure would harm the graph homophily. For multi-class tasks, the majority of the noises are added between inter-class edges while the minority are added between intra-class edges. This leads to the fact that adding Gaussian noise to the graph structure means decreasing the homophily ratio of the graph. Therefore, adding Gaussian noise on the node attributes is relatively reasonable than the graph structure.

In order to maintain the consistency of gradients in semantic graph augmentations, we propose a semantic invariance strategy based on graph augmentation. Computing the expectation of gradient over a high-dimensional augmentation space is intractable, so we approximate this expectation by averaging sampled augmentations in the local space of the original graph. The semantic invariance is expressed mathematically as:

where $n$ is the number of samples, and $\mathcal{N}(0,\sigma^{2})$ represents a matrix of Gaussian noise with variable standard deviation $\sigma$. This method preserves the invariance of gradients on semantically consistent augmented graphs. The variance of Gaussian noise is a hyperparameter specific to the dataset. We empirically select the hyperparameter with the optimal performance on the validation set for testing based on grid search. For example, on Citeseer, the variance of the Gaussian noise is set to 5e-4. We verify that Gaussian noise at this variance has little effect on the classification accuracy of GNN, and that is how we define the noise as semantically non-disturbed.

4. The Overall Attack Model

This section describes the implementation of the above three error reduction methods in the attack model. Algorithm 1 is used to illustrate the whole flow of our proposed attack.

The whole attack process is decomposed into $\Delta$ iterations, with one edge perturbed in each iteration. At the beginning of each iteration, a surrogate model is trained using the perturbed graph $G^{\prime}$ (Equation 2) to simulate the victim model under poisoning attacks. With the trained surrogate model, we derive the semantic invariance structural gradient $A^{\,grad}_{si}$ following Equation 13. Then we add the momentum term onto the structural gradient to minimize the error arising from the model’s local optima (Equation 9). Line 6-7 in the Algorithm describe the hierarchical candidate selection, which is to choose candidate set $S_{t}$ from the $N^{2}$ space. Line 8-11 in Algorithm perform edge discrete sampling (Equation 6) to approximate the continuous gradient distribution for each edge in $S_{t}$. Afterward, we select the edge with the most significant integral gradient $g^{int}_{mn}$ as the perturbed edge at the $t$-th iteration. Finally, The perturbed graph structure is updated, and the $t+1$ iteration is started.

This algorithm ensures that the surrogate model needs to be trained only once in each iteration. Therefore, it achieves high computational efficiency while reducing the errors in structural gradients.

Experiments

We present experiments to demonstrate the effectiveness of our proposed attack model, named AtkSE https://github.com/Zihan-Liu-00/AtkSE (Attacking by Shrinking Errors). The experimental settings are detailed in Section 4.1. In the following two sections, we compare our approach with other gray-box untargeted poisoning attack methods and provide ablation studies to verify our proposed improvements’ validity. In Section 4.4, we provide the gradients’ distribution on the edges’ values between 0 and 1 to prove the necessity for our proposed approximation method for continuous gradient distribution.

In this paper, we use the citation networks Citeseer (Sen et al. 2008), Cora (McCallum et al. 2000) and Cora-ML (McCallum et al. 2000) as well as the social network Polblogs (Adamic and Glance 2005) as the datasets. Consistent with the experimental setup of baselines, we randomly divide the dataset into 10% of labeled nodes and 90% of unlabeled nodes. The labels of the unlabeled nodes are not provided to the attacker or the victim model, and they are only used when evaluating the performance of the victim model.

1.2. Victim Models

The widely-used victim model is GCN (Kipf and Welling 2017) used in baseline papers. This paper extends GraphSage (Hamilton et al. 2017) as a more advanced GNN victim model. It is worth noting that there are some gray-box attacks, such as (Lin et al. 2020) and (Liu et al. 2022), where the network architecture of the victim model is considered to be known. The attack scenario in this paper considers that the victim model’s architecture is unknown to study the poisoning attack’s transferability better. Therefore, the GCN victim model differs from the surrogate model in linearity and number of neurons.

We uniformly use a 5% perturbation rate as the attack budget for imperceptibility needs. We repeat the experiments ten times for each experimental scenario and present the mean and variance of each set of experiments in the results. To ensure the fairness of the experiments, we test the perturbed graphs generated by each method with uniform and independent test files.

1.3. Baselines

Random, DICE (Waniek et al. 2018), EpoAtk (Lin et al. 2020), Meta-Train & Meta-Self (Zügner and Günnemann 2019) are used as baselines in the experiments.

DICE randomly removes edges between nodes from the same class or adds edges between nodes from different classes.

EpoAtk is originally a white-box attack model, transferred to the gray-box attack in our experiments. It proposes an exploration strategy where the attacker chooses edges from a set of candidates.

Meta-Self and Meta-Train consider the adjacent matrix as hyper-parameters to optimize via meta-learning. Two attack models differ in the node subset used to calculate attack loss.

1.4. Hyperparameters

In the implementation of our attack model, the interval of edge discrete sampling $\lambda$ is set to $0.2$, the number of edge candidates $C$ is set to $64$, the batch $bs$ is set to $16$, the momentum coefficient is set to $0.8$, and $n$ in semantic invariance is $5$.

2. Performance of AtkSE

Table 1 shows the comparison of our approach with baselines on various datasets and victim models. Among the eight experiments, our proposed AtkSE outperforms baselines in seven of them. Meta-Self is the most effective baseline in other gradient-based baselines, followed by Meta-Train and EpoAtk. The randomness-based methods DICE and Random are the worst. Our method ranks second behind the best effect in Polblogs/GraphSage. When the victim models are GraphSages, our method improves the attack success rate over the second-best method by 1.6%, 0.9%, and 0.1% on datasets Cora, Cora-ML, and Citeseer, respectively. On Polblogs, our method ranks second, below the first place by 1.5%. This result may be due to the independence of victim models’ representation learning and the difficulty of transferring attacks. When the victim models are GCNs, our method is better than other methods across the board. The attack performance of our method improves 2.1%, 1.8%, 0.9%, and 4.3% on Cora, Cora-ML, Citeseer, and Polblogs, compared to the second-place method Meta-Self.

Averaged over experiments, the attack effect of our method is 1.275% higher than that of Meta-Self. Our proposed AtkSE outperforms the second-ranked model by more than 1% in four experiments and 2% in two experiments. Experiments prove that our attack model, AtkSE, is more effective than other methods. It proves that errors exist in the previous methods and that reducing these errors can improve the effectiveness of the attack model.

3. Ablation Study

To verify the effectiveness of each error reduction module, we conduct the ablation study. We ablate the three error reduction modules in Sections 3.1 (Hierarchical candidate selection and edge discrete sampling), 3.2 (Momentum gradient ensemble), and 3.3 (Semantic invariance), respectively. The ablated attack models are denoted as AtkSE-H, AtkSE-M, and AtkSE-S. Table 2 shows the results of the ablation study.

In the ablation experiments, the worse the attack of the ablated model is, the more critical the ablated module is. AtkSE-M has the best accuracy on Cora, Citeseer/GraphSage, and Polblogs/GraphSage. It ranks second on Cora-ML/GraphSage and Citeseer/GCN and worse than the other scenarios. AtkSE-H has the highest accuracy when the dataset is Cora-ML, Citeseer and Polblogs, and the victim model is GCN. AtkSE-H ranks second on four experiments and worse on Cora-ML/GraphSage. AtkSE-S ranks first on Cora-ML/GraphSage, while it ranks lower on five experiments. AtkSE-M has the highest accuracy on four experiments, while AtkSE-H and AtkSE-S have three and merely one, respectively.

Overall, the momentum gradient ensemble is the module that enhances the attack model the most. The results indicate that the modules are ranked from highest to lowest importance as the momentum gradient ensemble, the hierarchical candidate selection and edge discrete sampling, and the semantic invariance. By comparing ablated models with AtkSE, the experiments prove the effectiveness of each module in AtkSE.

4. Gradient between the Edge-flip Interval

In this paper, graph edge perturbation is considered a problem of modeling a continuous distribution of gradients on edges. A possible challenge for our approach is whether the problem is worthy of being solved as a continuous problem over the edge-flip interval. To answer this question, we give examples of continuous gradient distributions of edge candidates in Fig.4. We can see that the gradients of the edges are continuous and smooth on the interval. We use the blue slash to indicate cases where the estimate is above the actual distribution and the red slash to indicate cases where the estimate is below the actual distribution. Referring to the error analysis in Section 3.1, in Fig.4, the previous methods adopt a gradient value higher than the integral of the continuous distribution on the (a,b,c) plot and lower than the integral on the (d) plot. Our approach considers the variation of gradients and transforms the edge perturbation from a discrete problem to a continuous gradients modeling problem. The error observed in Fig.4 proves the necessity for modeling continuous structural gradients. It also demonstrates why our approach improves the effectiveness of the attack.

Related Works

Graph adversarial attacks aim to disrupt the performance of graph neural networks using imperceptible attacks. There are three ways to attack graph-structured data: modifying the node features, modifying the graph structure, and injecting nodes (Jin et al. 2021; Chen et al. 2020). Among the researches in this field, more studies focus on modifying the graph structure (Dai et al. 2018; Waniek et al. 2018), and node injection (Sun et al. 2020), due to the specificity of graph data compared to general data. Among the general imperceptibility measures, attacks on graph structure are constrained by the L0 norm (Zügner and Günnemann 2019), and node injections are constrained by the number of manual nodes and their degrees (Sun et al. 2020). Depending on the attacker’s knowledge, attacks are classified as white-box attacks, gray-box attacks, and black-box attacks. White-box attacks (Xu et al. 2019; Wu et al. 2019) open all the information of victim models. Gray-box (Lin et al. 2020; Liu et al. 2022) attacks open labels of training set. Black-box attacks (Xu et al. 2020; Ma et al. 2019) allow the attackers to query the predictions of the victim models. If the victim model is retrained, the attack is referred to as a poisoning attack, otherwise, it is referred to as an evasion attack. This paper studies the gray-box poisoning attacks. We aim to transfer the attack from the surrogate model to an unknown victim model, also referred to as the study of attack transferability.

2. Graph Edge Perturbation

This paper investigates attackers which globally perturb the graph structure. Mainstream approaches are based on the gradient derived from the loss function by backpropagation on the graph structure (or the adjacent matrix). Metattack (Zügner and Günnemann 2019) is the first gradient-based edge perturbation work on graph networks. It is a global poison attack model with a gray-box setting and the basis of other gradient-based edge perturbation methods. The attack strategy of Metattack is to search for the edge with the most significant gradient by the gradient on the adjacency matrix for modification, modifying one edge per iteration until an upper limit of the budget is reached. Another work (Xu et al. 2019) makes use of PGD (Madry et al. 2018) to search for an optimal perturbation matrix $S\in\{0,1\}^{n}$. EpoAtk (Lin et al. 2020) tries to add exploration to the attack model. EpoAtk has a small probability of not directly perturbing the edge with the most significant gradient, but instead of generating a perturbation from many candidate edges based on the loss values. These three works ignore whether the gradients they use are reliable. They only use the gradient derived from the current state of the graph and do not take into account the variation of the gradients on edges over the perturbation interval from 0 to 1. A method of integrated gradient on edges (Wu et al. 2019) is proposed to solve this problem. It requires traversing the adjacency matrix to score all edges and multiple gradient calculations to score each edge. It needs to traverse the adjacency matrix to score all edges, which has an exploded computational complexity $O(N^{2})$. Moreover, it requires a massive amount of computing resources to perform a single time gradient calculation on all edges, limiting it to be used only in evasion attacks of small graphs, not any of the other scenarios. In addition, these efforts do not consider the gradient instability during the model optimization process. The above problems are addressed in our proposed method.

Conclusion

This paper proposes that the gradient on the graph structure in graph adversarial attack is subject to errors. This paper aims to illustrate these errors and propose corresponding modules to reduce them and implement them into our proposed attack model AtkSE. This paper first analyzes the error caused by treating graph structure attacks as a discrete problem with respect to gradients. We propose edge discrete sampling to reduce this error by approximating the continuous distribution of gradients over the edge flipping interval . To ensure the computational cost of this step, we propose hierarchical candidate sampling based on the gradient saliency of the graph structure to select a small bag of edges as the candidates to be attacked rather than the entire $N^{2}$ space. Subsequently, we discuss the errors present in the gradient of the graph structure, including GNNs’ unrobustness on the semantic space of the graph and the instability of the GNNs’ representations due to the randomness of the parameter initialization. We propose semantic invariance and momentum gradient ensemble to solve these two errors, respectively. We integrate the above error reduction modules and propose the attack model AtkSE. In the experiments, we validate the effectiveness of our proposed method by comparing it with state-of-the-art baselines and showing the ablation study in untargeted poisoning gray-box attacks. The results demonstrate that our approach improves the attacker’s performance, proving the reliability of our discussion on the error analysis and the effectiveness of our approach.

Acknowledgement

This work is supported in part by Ministry of Science and Technology of the People´s Republic of China (No. 2021YFA1301603) and National Natural Science Foundation of China (No. U21A20427).

References