Projective Ranking-based GNN Evasion Attacks

Graph neural networks (GNNs) offer promising learning methods for graph-related tasks. However, GNNs are at risk of adversarial attacks. Two primary limitations of the current evasion attack methods are highlighted: (1) The current GradArgmax ignores the"long-term"benefit of the perturbation. It is faced with zero-gradient and invalid benefit estimates in certain situations. (2) In the reinforcement learning-based attack methods, the learned attack strategies might not be transferable when the attack budget changes. To this end, we first formulate the perturbation space and propose an evaluation framework and the projective ranking method. We aim to learn a powerful attack strategy then adapt it as little as possible to generate adversarial samples under dynamic budget settings. In our method, based on mutual information, we rank and assess the attack benefits of each perturbation for an effective attack strategy. By projecting the strategy, our method dramatically minimizes the cost of learning a new attack strategy when the attack budget changes. In the comparative assessment with GradArgmax and RL-S2V, the results show our method owns high attack performance and effective transferability. The visualization of our method also reveals various attack patterns in the generation of adversarial samples.


INTRODUCTION
G RAPHS consist of nodes and edges defined between these nodes. As an abstract data type, graphs have powerful modelling capabilities. By extracting attributes from entities and describing their relationships, graphs can represent a range of objects or technical systems in realworld situations, such as drug molecules [1], biological networks [2], and traffic networks [3], [4]. Graph neural networks (GNNs) have proven to be effective graph learning methods [5] for exploring graph data and have demonstrated promising performance on node classification [6], [7], link prediction [8], anomaly detection [9], [10], and graph classification [11]. For example, in biological chemistry, the GNNs are engaged in recognizing the chemical properties of molecules.
In practice, GNNs raise urgent security concerns, although they have garnered considerable attention in the context of complex graph-structured data applications [12], [13], [14], [15]. Generally, graph neural networks are regarded as the generalization of deep neural networks into graph data. However, GNNs inherit the vulnerability of deep neural networks despite possessing adequate expressive power. Several recent studies demonstrate that adversaries can attack GNNs [16], [17], [18], [19], [20], [21]. Among others, evasion attacks [22], [23] are notoriously dangerous. Attackers could perturb test samples to generate adversarial samples of a victim model trained on original clean data. On adversarial samples, the victim model will give incorrect results, different from those of clean samples.
Prior work on GNN evasion attacks has demonstrated that well-designed slight perturbations are able to significantly degrade the performance of the victim models [22].
• H. Zhang  This type of attack is tricky since adversarial samples are similar to clean samples in appearance [17]. Adding a few elaborate adversarial edges can dramatically reduce the classification accuracy of the victim models [23]. To create an adversarial example, attackers can change the features of few nodes or add/remove a few edges in a clean graph. A budget k with positive integer values controls the number of these perturbation operations to make their perturbations stealthy. Moreover, once the models are deployed, it is practical for attackers to launch the evasion attacks at any time [19].
The existing studies of evasion attacks on the GNN models mainly focus on node classification and link prediction, while few of them are designed for graph classification [16], [17], [19]. We note there are some limitations in those methods for graph classification, which need to be solved to improve the attack practicality.
• In the vanilla gradient-based attack method GradArgmax [22], the greedy mechanism uses the gradient on the graph in the perturbation process to make the perturbation decision. Although the gradient information could approximate the attack benefit to some extent, it ignores the long-term benefit of operation at each step [22]. Moreover, GradArgmax is not efficient since it needs the up-to-date gradient information to complete each step of all the perturbation operations.
• Attack methods [22], [24] use reinforcement learning (RL) to perturb clean samples and use the final predicted result on adversarial samples to estimate the attack benefit. When the perturbation budget changes, they have to be retrained to learn an attack strategy suitable for the new budget. In addition, we observe that RL-S2V [22], a known attack method, does not appear to be able to generate adversarial samples in high attack success rates when the perturbation budget increases [24].
Motivated by these observations, we summarize the arXiv:2202.12993v2 [cs.LG] 2 Nov 2022 challenges in building an effective evasion attack against GNNs for graph classification: (1) in the generation of powerful adversarial samples, how to measure the attack benefits of each operation based on the clean graph, and (2) how to adapt the learned attack strategy to changed perturbation settings (e.g., budget) with least effort.
To address these challenges, we first formulate the perturbation space composed of all possible perturbation operations and present four properties of it. Then, we propose an evaluation framework consisting of three principles decomposed from the adversary's expectation. We use these three principles as the design goal of our method and employ them to evaluate typical evasion attack methods. In our evaluation framework, we consider a basic fact in the evasion attack: an intelligent attacker always expects to choose the perturbation operation which will bring the most significant attack benefit at each perturbation step. This fact includes three critical principles for evasion attack: attack benefit, operation ranking and baseline graph. Finally, we propose the projective ranking method as an instantiation under the evaluation framework.
In our method, we expect to find a suitable metric that considers the attack benefits of each operation to rank them and then use this ranking directly to generate adversarial samples under different perturbation budget settings. Towards the first challenge, we employ the mutual information (MI) between elements of perturbation space and attackers' goals as a measure to evaluate the importance of each possible operation. We regard the perturbation space ranking as the learned attack strategy. Inspired by the projected gradient descent method, we propose to project the learned attack strategy into practical attackers' perturbations with the specified budget for the second challenge. Through this projection operation, the adjustment cost of the learned attack strategy is almost zero.
Our contributions are summarized below: • We formulate the perturbation space and its four properties, and we propose an evaluation framework for evasion attack methods and analyze typical methods from the principles of the framework.

•
We propose the projective ranking method. We first employ the mutual information to measure the attack benefits of a perturbation operation towards strong attack performance, then use the projection operation to reduce the cost of the strategy adaptation process by considering the transferability of attack strategies.

•
We conduct evaluations on several real world datasets and a synthesized dataset, and our attack method achieves high attack performance and effective transferability. The visualization of adversarial samples present various attack patterns and reveals the vulnerability of the victim model.
In this paper, we review different attack methods for graph classification in Section 2 and introduce the graph classification and evasion attacks in Section 3. In Section 4, we first formulate the perturbation space and show its four properties. Then we propose the evaluation framework of evasion attack methods and show the instantiation design of our method. Next, we show the detail of the projective ranking method. In Section 5, we use the evaluation frame-work to make a comparison evaluation of typical methods. In Section 6, we experimentally demonstrate the high attack performance and effective transferability of our method, and the attack patterns in our adversarial samples reveal the weaknesses of the victim model. Finally, we show the conclusion and discuss the future works in Section 7.

RELATED WORK
Current research shows that graph neural networks are vulnerable to adversarial attacks. According to the intention of attackers, the adversarial attack methods for graph classification include evasion attacks, backdoor attacks, and poisoning attacks.

Evasion Attack Methods on GNNs
Evasion attacks perturb the inputs of the GNNs during their inference phase and intend to degrade the performance of the victim model. Hence, the more the classification accuracy of the victim model decreases, the better the performance of an attack method. As the most intuitive approach, RandomSampling randomly perturbs the graph structure or nodes' features of clean graphs to generate adversarial samples. However, the attack performance of this method is lower than adding well-designed perturbations. In the GradArgmax method, the attackers own the ability to access the victim model. They first calculate the gradient information of the loss function on each possible perturbation operation, then use the gradient information to choose the perturbation operation that maximizes the loss of the victim model.
To better describe the perturbations on graph data, Dai et al. [22] proposed to employ the Markov decision process to model the whole perturbation process and use reinforcement learning to obtain an attack strategy on current clean samples. The graph data in the perturbation process is modeled as the state of reinforcement learning. The action space comprises all perturbation operations in the current state, and the final attack result defines the reward function. Benefiting from the modelling and learning ability of reinforcement learning, the attack performance of RL-S2V outperforms that of RandSampling and GradArgmax on synthetic data [22].
To improve the stealthiness of attack, Ma et al. proposed ReWatt to redefine the action space of reinforcement learning [24]. The perturbations generated by ReWatt are more unnoticeable since the edge numbers of adversarial samples are equal to those of clean samples. Besides the above attack methods, the attackers could also attack the components of GNNs if they know a specified operation is included in the victim model. For example, some methods introduce hierarchical pooling operations in the models, which selects typical nodes to compress the node number and determine the structure of the coarse graph [25], [26], [27]. Tang et al. proposed to attack the selecting operation in pooling operation [28]. By training a surrogate model with hierarchical pooling on some clean data, the attackers obtain the selecting function that simulates the victim model's hierarchical pooling. Based on this selection function, the attackers could obtain the adversarial samples that invalidate the pooling in the victim model. However, this method may not be available for attacking models that employ global pooling operations. A comparison of representative evasion attack methods are summarized in Table 1.

Differences in Evasion Attacks
In addition to the differences in technical methods, the evasion attack methods also have differences in perturbation space, the definition of imperceptible perturbations, the attacker's knowledge, and the attack goal. In the aspect of perturbation space, the attackers usually make perturbations by adding fake nodes with the fake features [29], modifying node features [30], adding or deleting edges [31]. In graph classification evasion attacks, ReWatt, RL-S2V, RandSampling and GradArgmax only modify graph structure. The attack method in [28] makes perturbations in node features or graph structure.
In the aspect of imperceptible perturbations, the distance between the original clean graph and the modified adversarial graph is usually limited by the perturbation budget, which is defined as the number of nodes modified or distance of feature vectors, or the number of edges modified by adding/deleting/rewriting. In the aspect of attackers' knowledge, based on how much information an attacker knows about the victim model, the attack methods are generally divided into white-box, grey-box, and black-box attack. A white-box attack means the attackers can access all information about the victim model like architecture, parameters, training input, and labels. Grey-box attack indicates that only limited information about the victim model, like training data labels, is available. As the strictest setting, the black-box attack only allows attackers to do queries of samples for output or labels [16].
In graph classification evasion attack, GradArgmax is a white-box attack method, RL-S2V and ReWatt are typical black-box attack methods based on reinforcement learning. In the aspect of the attackers' goal, the attacks are divided into untargeted attacks and targeted attacks. In an untargeted attack, the attackers expect the victim model to classify the adversarial samples into labels different from their original labels. As a more strict attack goal, targeted attacks attempt to fool the victim model by specifying the output categories of the adversarial samples.

Poisoning and Backdoor Attacks on GNNs
Besides evasion attacks, another two typical adversarial attacks on GNN models are poisoning attacks and backdoor attacks. The poisoning attacks [32] suppose the attackers own the ability to poison training data and label. In this way, the performance of the GNN models trained on poisoned data will degrade dramatically on clean samples. In backdoor attacks [33], [34], the attackers inject a fixed or adaptive trigger into clean training data and change their labels to the desired categories. As a result, the models trained on these data performs well on the clean samples but predicts the desired labels once the well-designed trigger is injected into the clean samples.

Graph Classification
Assuming G = {V, E} is a graph, where V = v 1 , . . . , v |V| is the set of nodes, E = e 1 , . . . , e |E| is the set of edges of graph G. The edges set E describes the structural information of G. It can also be expressed as the adjacency matrix A ∈ {0, 1} |V|×|V| , where A ij = 1 means the existence of the edge from v i to v j , otherwise A ij = 0. The features associated with nodes are expressed as matrix X ∈ R |V|×d , where the i-th row of X is the features of node v i and d is the dimension of features. So a graph can also be expressed as G = {A, X}.
In the graph classification, a set of graphs is denoted by G = {G i } N i=1 and a label y i ∈ Y = {1, 2, . . . , Y } is associated with each graph G i , where N is the number of graphs and Y is number of categories. The dataset is composed of pairs of graph and its label. In graph learning, the classifier f ∈ F : G → Y is trained and expected to learn the mapping from graph G to its label y with optimal parameters θ that minimize the below loss function: where L(·, ·) is used to measure the distance between the predicted and ground-truth labels. A general instance of L(·, ·) is the cross-entropy function.

Graph Neural Networks Model
The graph neural networks (GNNs) is a family of architectures of neural networks that are designed to process graph data G = {V, E}. These models iteratively update the expression of nodes by message passing and aggregation as below [35]: where N (v) is the set of neighbours of node v in graph G, h t v means the hidden expression of node v at time t ∈ {1, 2, . . . , T } and e vw is the features of the edge from node v to node w. M t (·, ·, ·) is the message functions and U t (·, ·) is the vertex expression updating functions. After the message passing phase, the expression of whole graph G is obtained by the readout operation: where R(·) is the readout operation, and it is invariant to permutations of the nodes. A general instance of R(·) is the max-pooling or sum-pooling.
In graph classification, the model f θ based on the above architecture is generally trained under an inductive learning setting, in which the classifier learns on training data D train and then make graph label prediction on test data D test .

Problem Formulation
Assuming a GNN model f θ is trained on clean graph samples and then employed to predict the category of graph data D = {G j } M 1 . In evasion attacks, an attacker T attempts to make unnoticeable perturbations on the original G to degrade the performance of this victim model f θ . We use T f (G) to indicate the attacker's perturbation on G which is specifically designed for the classifier f θ . In untargeted evasion attacks, the attackers expect the predicted category of an adversarial sample is different from its true category. More precisely, the objective of untargeted evasion attacks on the victim model f θ is Here G is the adversarial sample generated from the clean sample G, and I(·) is the binary indicator function. k is the perturbation budget of T f . Given specific k, I(·, ·; k) is a similarity measure function whose output is 1 when two input graph samples are semantically the same and 0 otherwise. Particularly, in targeted evasion attacks, the attackers expect the predicted category is a specified category y t , which is different from its true category y j . The objective of targeted evasion attacks is Note. The probability function p(·) can be employed as a substitute of I(·) to describe objective functions [16]. Given G j and budget k, we use O( G j ; k) to denote the value of objective function in equation (5)/(6) when using up all budget k (e.g., in equation (5),

PROPOSED APPROACH
Our projective ranking method mainly includes the ranking module and the projection module. In this section, we first formulate the perturbation space and propose the principles of our evaluation framework. Then we present the detail of the ranking module and the perturbation projection operation. Finally, we give an algorithm to show the generation of adversarial samples.

Attack Setting
In our method, given a victim model f θ , we assume that the attackers can have access to the nodes embedding and predictive probability distribution of f θ to learn the attack strategy. Then, only accessing the embedding of nodes, the attackers may utilize the learned strategy to attack any samples of the victim model under any budget setting.
To further explore the transferability of the learned strategy (in Section 6.5), we assume an intelligent attacker attempts to fool the victim models by accessing the nodes embedding of the target models based on the attack strategy learned from the other source models engaged in the similar data domain. We note that the attacker does not know any other knowledge (like the architecture or parameters of the target models) except for the embedding of nodes. This scenario reflects the vulnerability of the models that use the pre-training models [36].

Perturbation Space
In an evasion attack, an attacker T can perturb a clean sample G to obtain an adversarial sample G. We formulate the process of this perturbation on graph G as where ∆G = {∆A, ∆X} is the perturbation graph. To be more precise, the graph structure and node features of G are expressed as where A ∈ {0, 1} |V|×|V| is the adjacency matrix, X ∈ {0, 1} |V|×d is binary node features matrix, . |V| is the number of nodes in G, and d is the size of node features. m A ∈ {0, 1} |V|×|V| and m X ∈ {0, 1} |V|×d represent the masks of graph structure and node features respectively. I(add)/I(del) is the indicator function to show if adding/deleting edge operation is allowed in generating adversarial samples. is the Hadamard product and · is the scalar multiplication. Therefore, the perturbation graph ∆G = {∆A, ∆X} is actually defined by the combination of specified structure mask m A and feature mask m X . The similarity measure function in (5) and (6) is refined as where ||·|| 1 is the L1 Norm, k is the budget of perturbations. a is a scalar coefficient, and it is 1 if G is a directed graph and 1 2 otherwise since the adjacency matrix of undirected graph is symmetric.
Given the clean sample G, the perturbation space T(G) of G is defined as the set of all possible perturbation graph ∆G = {∆A, ∆X}. The size of a perturbation graph ∆G is defined as: where Z + 0 is the set of non-negative integer. In the perturbation space T(G), the operators and + on perturbation graphs are defined as: where · means the elements of the input matrix is limited Specially, we call ∆G ∈ T 1 (G) an operation element of perturbation space T(G). Given the above definitions and operators, the perturbation space T(G) owns the following properties: Proof : Given the definition of T k (G), the result is a direct consequence of the following calculations. Based on the definitions of + and operation, we have Based on property 3, it is easy to obtain that the perturbation space T k (G) is actually composed of k different operation elements of T(G), which means that and the size of T k (G) is where | · | is the size of a set, and C is the combination operation of two integers.

Design Goals and Principles in Evaluation Framework
Incorporating with the objective in (5)/(6), we also consider a fundamental expectation of the adversary as a design goal of evasion attack methods: An intelligent attacker always expects to choose the perturbation operation which will bring the most significant attack benefit at each perturbation step for achieving stealthy and effective attacks.
The intelligent attackers expect to ranking these k different ∆G i w.r.t B(∆G i ), and at each perturbation step they choose arg max ∆Gi B(∆G i ). Moreover, the objective in (5)/(6) can also be regarded as ranking all operations in the perturbation space and selecting k operations. Therefore, the core question in this paper is how to rank ∆G ∈ T 1 (G) concerning their relative importance to the attack goal.

A. From Design Goals to Evaluation Framework
To achieve the above expectation, we propose an evaluation framework to reveal its core requirements. Our framework composed of three principles, they are: (1) Benefit decomposition. Explaining B(·) is necessary for understanding the three principles. When budget k > 1, perturbations at each step are combined together to function as a whole. Although final attack results come from collab- can be chosen at each perturbation step. This fact requires that the attack benefit B(·) should be felicitously defined on ∆G ∈ T 1 (G) from a global view, i.e., distributing O( G; k) to each ∆G, to support the intelligent attacker making perturbation decision. For example, when using Shapley value φ [37] as the contribution distribution function, B(∆G) = φ(∆G O( G; k)). In this paper, an attack method satisfies the benefit decomposition principle if it considers all perturbations as a whole to evaluate their attack results, and uses some mechanisms to distribute the overall benefit to the perturbations at each step.
(2) Baseline graph. When defining B(·), an implicit ground object is that the baseline graph of attack benefit should be fixed on the clean graph G, i.e., B(·) = B(· G), and B(∆G) = 0 where ||∆G|| = 0. If the baseline graph changes to other graphs, the measure of attack benefit will deviate from the original meaning (see the example of GradArgmax in Appendix B).
(3) Operation ranking. To achieve stealthy and effective evasion attacks, given specific values of B(·) on ∆G ∈ T 1 (G), an intelligent attacker should choose the perturbation with maximal attack benefit in each step. In the above process, the intelligent attacker ranks ∆G ∈ T 1 (G) according to their attack benefits, and then choose top-k different perturbation operations one-by-one. In this paper, an attack method satisfies the operation ranking principle if its perturbation at each step consumes the attack budget by considering the B(·)-based ranking of ∆G ∈ T 1 (G).

B. From Evaluation Framework to Our Method
In this section, we utilise principles in the evaluation framework and additional requirements to guide the design of our Test on clean sample  Fig. 1. Illustration of the projective ranking method. The victim model f θ can make the correct prediction on a clean sample G (shown in hollow arrows). During the scoring module training (shown in the steps 1-9 with solid arrows), the attacker T f employs the mutual information between the perturbation space T(G) and the attacker's goal y G = y G to measure and rank the importance of all elements in T(G). The scoring module needs access node embedding and predictive probability distribution of the victim model. In the evaluation phase (shown in dashed arrows), the attacker T f only needs to access the node embedding to obtain the ranking of the elements in T(G), and then projects the operation ranking to generate adversarial sample G under the specified budget.
method. Generally, an intelligent attacker always attempts to maximise the profits in attacks (see Appendix A). In this paper, we extend the definition of transferability of attack strategies. The transferability means that once attackers learn the attack strategies, they can generate adversarial samples for unseen clean samples under different perturbation budgets. However, if attack strategies are learned from fixed budget k (e.g., RL-S2V), these strategy cannot easily satisfy transferability since they are designed for specific k. Therefore, the evaluation framework and desired transferability practically require an attack method accomplishes B(·)based ranking of ∆G ∈ T 1 (G) without considering specific k in B(·). Inspired by the recent research on GNN explainability [38], [39], we employ all perturbation operation ∆G ∈ T 1 (G) of the clean graph G (i.e., baseline graph) as a whole to attack target GNNs for getting rid of the limitation of specific k. Based on mutual information, the B(·) of each ∆G is then calculated as their importance (see more in Appendix B) for final attack results. In this way, our method satisfies the benefit decomposition principle. To satisfy the operation ranking principle, we first rank ∆G ∈ T 1 (G) according to their importance values (i.e., attack benefit), and then project this ranking into practical attacks with specific k.

Ranking method
Now, given a clean sample G as the baseline graph, attackers attempt to rank all operation elements in perturbation space T(G) with respect to their importance. We measure the importance of elements in T 1 (G) by mutual information (MI) between the modified graph G and the attacker's goal. It can be expressed as: where H(·) is the entropy function. In untargeted evasion attacks, Y = (· · · , p y G = 0, · · · ) is the expected prediction distribution of G, y G is the original category of G. For the clean sample G, the first item in (15) is a constant since the victim model f θ is fixed and Y is also invariant. So the objective in (15) is equal to To reduce the computational difficulties caused by the discrete graph structure, we apply continuous relaxation on ∆G and assume it is a graph variable ∆G ∼ T f (G). Based on Jensen's inequality and H(·) is a concave function, we obtain that where E[·] is expectation function. So the objective (16) is equal to min To be more specific, given the victim model f θ , the objective of the untargeted evasion attacks is where p · G is the predictive probability distribution of f θ on G. The objective of the targeted evasion attacks is where y t is the specified target category. Following the attack setting in previous methods [22], we assume that attackers are only able to add edges when generating G. So we have where ∆A = m A (I A − A), the mask m A is obtained by where h i is the embedding of node i, s(·, ·) is the scoring function which measures the importance of elements in T 1 (G) with respect to the attacker's expectation. In our method, after concating the embedding of nodes v i and v j , a Multi Layer Perceptron (MLP) model and the softmax function are employed to obtain the final score. Since the value of ∆A is a real number rather than a discrete value, we call G is generated by adding continuous structure perturbations ∆G c = {∆A c , 0}.

Perturbation Projection
In our method, the learned attack strategy is embedded in the ranking of ∆G = {∆A, ∆X} ∈ T 1 (G). Due to the discrete structure limitation of graph data, although attackers could obtain the adversarial sample G in (21) where k is the perturbation budget, topk(·, k) is the set of ∆A c;i,j with top-k values, i and j indicate the element at i-th row and j-th column of matrix. By this projection, attackers obtain the adversarial sample G = {A+∆A d , X} from clean sample G under specified budget k. Figure 1 illustrates the pipeline of our projective ranking method. After obtaining the adversarial samples D = { G m } M m=1 , the attacker use them to attack the victim model f θ . Algorithm 1 shows how attackers generate adversarial samples from clean samples D by our projective ranking method. To learn an attack strategy, in line 6, attackers first need to obtain the embedding representation of all nodes h of clean samples in D from the victim model f θ . In the training phase (lines 9-12), attackers use the scoring function in equation (22) to obtain structure mask m A , then obtain the perturbations on graph structure ∆A c by limiting m A with the allowed perturbation operation type. Then, in line 11, attackers add perturbations ∆A c to the clean samples to generate a relaxed adversarial sample G c . In line 12, attackers use the objective (19) to learn an attack strategy embedded in the scoring function. In the evaluation phase (lines 13-18), attackers will obtain the practical adversarial sample G d to evaluate the attack performance of the learned attack strategy. In line 14, attackers project the learned ranking into the practical attack space, in which attackers are only allowed to add edges with the specified budget (k = 1). Then attackers obtain the final adversarial samples in line 15 and attack the victim model in line 17. Attackers will repeat the process (lines 9-18) until the projective ranking method learned a high attack strategy. By replacing the objective in line 12 with objective (20), attackers could obtain the adversarial samples under the setting of targeted attacks.  18 ASR best = ASR current

METHOD ANALYSIS UNDER OUR EVALUATION FRAMEWORK
In this section, we use the three principles in Section 4.3.1 to make an evaluation on our method and three typical attack methods: RandomSampling, GradArgmax and RL-S2V.
The results are summarized in the Table 2. In these methods, RandomSampling only satisfies the baseline graph principle, our method satisfies the attack benefit, operation ranking and baseline graph simultaneously. The other methods are partially consistent with the evaluation framework. The reasons are as follows.
(1) GradArgmax. Similar to the use of gradient descent for training in neural networks, GradArgmax employs the gradient of f θ on all operation elements ∆G cur ∈ T 1 (G cur ) to choose perturbation operation, where G cur is the graph waiting to be modified at the current perturbation step. Hence, GradArgmax neglects the baseline graph principle. To use up all perturbation budget k, attackers need to calculate the gradient information at each perturbation step. Then it will use the real-time local gradient as the measure of attack benefits. Actually, the gradient information is a measure of modification sensitivity (see Appendix B), so GradArgmax does not satisfy the attack benefit principle. To generate adversarial samples, GradArgmax focuses on integrating all perturbation graph ∆G cur ∈ T 1 (G cur ), which owns the biggest local benefit at each perturbation step. Although the operations in GradArgmax have an order, it does not satisfy the operation ranking principle since the local gradient information is not a suitable measure for attack benefits.
(2) RL-S2V. In the generation of adversarial samples, RL-S2V uses the attack benefit of ∆G ∈ T k (G) to decide the perturbation operation ∆G ∈ T 1 (G) of each step in consuming perturbation budget k. The reward function in RL-S2V is designed by considering the outputs of the victim model f θ on G and G, so it satisfies the baseline graph and attack benefit requirements. However, it emphasizes using ∆G ∈ T k (G) as a whole perturbation to attack the victim model f θ with specified budget k, while cares less about the order of the element ∆G ∈ T 1 (G) that composes the perturbation space T(G). Hence, the RL-S2V attack method neglects the attack ranking. Furthermore, we analyze the difference between the measures of attack benefits (sensitivity, long-term benefit, importance) in the Appendix B. We also show the weakness of GradArgmax concerning the attack benefits from three different aspects and empirically demonstrate them in our experimental results.

Datasets and Baselines
We employ several real-world datasets ENZYMES, Mutagenicity, PC-3, NCI109, NCI-H23H [40] and one synthesized dataset BA-2Motifs [39] for graph classification. For the NCI-H23H dataset, we only choose the graphs whose node size is less than 50. Table 3 shows some basic statistics of these datasets.
To evaluate the performance of our method, we select RandomSampling, GradArgmax, and RL-S2V [22] as baselines. In the RandomSampling method, we performed ten times with different seeds and then averaged these accuracy results. In our experiments, the attack performance is measured by the accuracy of the victim model, in which a low accuracy number indicates a high attack performance.

Experimental Setup
In the victim models, we randomly split each dataset into training data (80%), validation data (10%), and test data (10%) to train the victim GAT [41] or GCN [42] models. The victim models have three hidden layers, with 20 as the output feature dimension. We concatenate the maxpooling and sumpooling results of the final embedding of nodes to obtain the expression of the whole graph, then use a fully connected layer to predict the category of the graph. In our projective ranking method, we use a 2-layers MLP to serve as the scoring module.
To evaluate the transferability of our method, we directly project the learned strategy under k = 1 to the generation of adversarial samples under k = 2, 3. The other results are obtained by running corresponding attack methods under a specified budget, respectively.

Untargeted Attacks
The upper half of Table 4 and 5 show the accuracy of the victim model f θ on both clean and adversarial samples generated by different attack methods. The bold numbers indicate the best attack results under the same setting.
In Table 4 and 5, our method achieves the best or competitive attack performance on all datasets with k=1, indicating the projective ranking method owns powerful attack performance. When k=2 or 3, we use the learned attack strategy under k=1 to generate adversarial samples for the changed perturbation budget. The results show our method also obtain the best or competitive attack effect, which shows that the projective ranking method has learned an effective transferable attack strategy under budget k=1.
GradArgmax generates the adversarial examples based on the gradient of the victim model and makes a greedy choice in each step. The attack results of GradArgmax in the Table 4 and 5 empirically prove our discussion about sensitivity in Appendix B. Firstly, the perturbation generated by GradArgmax is sub-optimal since the gradient is the sensitivity measure of the victim model. Although the GradArgmax achieves effective attack performance on the victim GCN model, its ability on the victim GAT model is limited (see Figure 2). Secondly, the result on the NCI109 dataset with k=1 in Table 5 shows the GradArgmax generates samples with negative attack performance. This indicates that its attack performance is limited by the non-linear nature of the GNN model in some situations. Finally, the attack performance of GradArgmax is worse than the RandomSampling on ENZYMES, PC-3 and NCI109 datasets when k=2 and 3, on which GradArgmax shows weak marginal attack performance concerning the budget. Moreover, the GradArgmax does not learn any attack strategy in the attack process. Above results indicate that GradArgmax is not desirable for attackers in some situations since it misses the baseline graph and attack benefit principles in evasion attacks.
Compare with using the "local" gradient in GradArgmax, RL-S2V and our method achieve stable attack performance on both GAT and GCN models since both of them consider the importance of perturbation operation with "global" criteria. We also use RandomSampling as a baseline to evaluate other attack methods. Table 4 and 5 show our method always achieve better attack performance than Random-Sampling. The italic shows unexpected results in the aspect of attack ability, where the performance of RL-S2V is worse than RandomSampling on ENZYMES (k=2, 3) in Table 4 and ENZYMES (k=3), NCI109 (k=3) in Table 5. Moreover, attackers always expect to obtain better attack performance when giving more budgets. If the budget increases, a well-designed attack method should not decrease    its performance. However, like the result in [24], we also observed that the attack performance of RL-S2V degrade when increasing the perturbation budget on Mutagenicity (k=3) in Table 4. This may be due to the less effectiveness of the Q-learning method in RL-S2V, especially for the Markov decision process with a long horizon.

Targeted Attacks
We also conduct targeted attacks on the ENZYME dataset. Without loss of generality, these methods attempt to attack GNN models so that they classify graphs from other classes (i.e., 1-5) as class 0. The upper half of Table 6 shows the attack success rate of different attack methods, and our method far outperforms other baselines in attack perfor-mance. Moreover, in targeted attacks, we also found the same weaknesses of GradArgmax and RL-S2V that they have in untargeted attacks (see italic results).
Remarks. Although the attention mechanism in GAT models introduces more parameters, previous research [43] in imbalanced learning shows that GAT's performance is lower than GCN's because the minority class does not have enough data to train a competent model. When training the GAT model on the NCI-H23H dataset, we employ undersampling on the category with most samples to alleviate the unfavourable effect caused by unbalanced distribution. In the training data, the # of positive samples: # of negative samples = 1:2.
All results in this section are achieved by directly ap-  plying attack methods on the vanilla GNN models. Recently, the randomized smoothing method [44], [45] has been widely employed to improve the robustness of AI models. In this paper, we follow the setting (noise parameter β = 0.9/0.7, sampling number d = 10000) of recent research on certified robustness of GNNs [46] to evaluate the attack performance of our method. Experimental results show randomized smoothing [46] is an effective defence method. However, for GNN models in this paper, randomized smoothing is not applicable because it significantly degrades the performance (i.e., accuracy) of GNNs. For example, as shown in Table 7, although our method almost cannot attack the GCN models on ENZYMES/Mutagenicity after introducing randomized smoothing, the accuracy of GCN equipped with the defence method (β = 0.9) on clean graphs is only 22.29%/53.00%, which is dramatically lower than that of vanilla GCN models suffering attacks with k = 1 (i.e., 52.50%/67.63%).

Transferability on Unseen Samples
To reduce attackers' effort to generate adversarial samples from unseen clean samples, they generally expect a transferable attack strategy. In this section, we use the attack strategies obtained in Section 6.3 to generate adversarial samples for unseen samples and then employ them to attack the victim models.

Untargeted Attacks
The lower half of Table 4 and 5 show the classification accuracy of f θ on both clean and adversarial samples. We consider the RL-S2V and our projective ranking method since only they can learn transferable attack strategies. The bold results indicate the best method under the same setting, and italic show unexpected results in the aspect of transferable attack performance. Firstly, the results in Table  4 and 5 show both RL-S2V and our method could use the learned attack strategy to generate effective adversarial samples under perturbation budget k=1 on all datasets. It indicates that the learned strategy can be transferred to attack unseen samples. Secondly, the results under k=2, 3 further demonstrate that the projective ranking method owns transferable attack performance on unseen samples when the budget changes. Especially, our method obtains the best attack performance on some datasets when k=2 or 3 even if it does not own the best performance when k=1.
Finally, compared with RandomSampling, the transferability of the attack strategy of RL-S2V is limited on most datasets when k=2 or 3, maybe the RL-S2V did not learn a powerful attack policy when k > 1. These results reveal that the victim models make consistent mistakes at both the sample and the budget levels. The attackers can utilize this fact to learn the attack strategy only under a specific budget with limited resources and then use the attack strategies to attack the target classifiers when the attack scenario changes.

Targeted Attacks
The lower half of Table 6 shows attack success rate of attack methods on unseen samples. Attack results show our method observably outperforms RandomSampling and RL-S2V. Moreover, in targeted attacks, the transferability of attack strategy from RL-S2V is also limited (see italic results) when comparing with RandomSampling. Figure 3 shows the attack performance of our method on seen samples under different attack budgets. The perfor-mance curves illustrate our method learned effective and transferable attack strategies in untargeted and targeted attacks. Moreover, Figure 3 also empirically demonstrates that our method satisfies the operation ranking principle in the evaluation framework since smaller budgets own larger marginal attack performance.

Transferability on Victim Model
To further explore the transferability, we use the adversarial samples generated from GCN/GAT model to attack the victim GAT/GCN model. The attack results are shown in Table 8, and these adversarial samples achieve better attack performance than RandomSampling. It indicates these victim models used for the same task on the same dataset may make consistent mistakes to some extend.

Transferability on Data Domain
This evaluation explores the transferability of the attack strategy learned on one dataset to attack the victim models built on other datasets. We visualized the attack results on the victim GCN model in Figure 4. Firstly, the relative attack performance's colour indicates that when the source attacker and the target model have the same dataset, it achieves the best attack performance. Secondly, since the graphs in all datasets are small molecules or come from bioinformatics, the result values in Figure 4 show the domain similarity of these graphs brings non-negative attack performance. These results reveal the potential risk of employing a pre-training model with a freezing setting [36] in the downstream tasks. In Figure 4, we observe that when attacking the NCI-H23H dataset using the attack strategy from the ENZYMES dataset, the accuracy performance drops 8.9%, which is larger than that of RandSampling (4.7%) and GradArgmax (8.6%). Once the adversary knows the victim model f (θ) uses the pre-training model f emb , they could train a classifier f (φ) on graphs G f that come from the same domain of the data G f in f (θ), then use the attack strategy learned on f (φ) and the embedding of G f from f emb to attack the victim models.

Visualization of Attack Patterns
To reveal the attack strategies of the projective ranking method, we visualize the perturbations in adversarial samples on the BA-2Motifs dataset based on the GCN model. BA-2Motifs is a synthetic dataset in which two motifs (House and Pentagon) are attached on random base graphs. Table 9 shows the attack results of different methods.  5. Visualization of adversarial samples. The graphs in the left column are clean samples, and the subgraphs in first/second block composed of green nodes are the motif "Pentagon"/"House". The graphs in the middle and right column are adversarial samples generated by RL-S2V and our method, respectively. In this figure, the attackers attempt to fool the victim models to predict "House"/"Pentagon" on the adversarial samples in first/second block. Both RL-S2V and our method present two attack patterns: imitation of other motifs and collapse of self-motif.
In untargeted evasion attacks, we found two fundamental strategies in the generation of the adversarial samples. They are: (1) placing the adversarial samples in the highconfidence region of the other categories in the victim models, and (2) moving the clean samples to the classification boundary or other low-confidence areas of the victim models. We dive into the adversarial samples and observe some enlightening attack patterns in them: Imitation of other motifs. In the first row of the first block in Figure 5, both RL-S2V and our method add one edge in the Pentagon so that there is a House in the adversarial samples. In this way, the victim GCN model classifies the adversarial samples as House graphs.
Collapse of self-motif. In the second row of the first block and the second block in Figure 5, both RL-S2V and our method attack the victim model by adding one edge in which one node is in the self-motif. In this way, the attackers destroy the self-motif pattern by moving the samples to the low-confidence areas to fool the victim model.
Although the attack results in Table 9 indicate RL-S2V and our method have the same attack performance, we find the attack patterns of RL-S2V are simple and lack variation from the second column in both Figure 5 and 6. However, another two attack patterns are found in our method:

RL-S2V Ours
Coexistence of motifs. In the first block of Figure 6, our method shows a new attack pattern. One edge is added between two nodes that are outside of the self-motif in the clean samples. The exciting part of this edge is that the distance of the two end-nodes of it is 5, and after this perturbation operation, there is a motif Pentagon in these samples. The coexistence of motifs is regarded as one behaviour that belongs to the second strategy in generating adversarial samples, in which the clean samples are moved to the decision boundary of the victim models.
Fake self-motif. In the second block of Figure 6, our method adds one edge between two nodes outside of the selfmotif, resulting in one triangle constructed in the adversarial samples. As a critical part of the House motif, the constructed triangle could confuse the victim models since two "similar" self-motifs exist in current samples. In this way, the samples are moved from the high-confidence region of the victim model to the low-confidence area.
In this section, we visualize the adversarial samples and summarize two basic attack strategies in them. We also found four attack patterns-imitation of other motifs, the collapse of self-motif, coexistence of motifs, and fake selfmotif-of the adversarial samples. Compared with the RL-S2V, the adversarial samples generated by the projective ranking method show various attack patterns. These attack patterns are helpful for the adversary to find the graph pattern differences between different data classes. Based on these observations, the attackers can customize the pattern operation to obtain adversarial samples of the specified type of clean graph samples.

CONCLUSION
In this paper, we present the projective ranking approach to perform an evasion attack for graph classification. We contend that current evasion approaches either do not provide adequate attack performance without considering the perturbations' long-term benefits or require attackers to readjust the attack strategies when the attack environment changes. To that purpose, we define the perturbation space and propose an evaluation framework on the evasion attacks for graph classification. Then we first relax perturbation space for ranking its elements based on mutual information, and then we project the ranking into generating adversarial samples with a specified budget. The experimental results show that our method performs well in attack performance, and the learned attack strategies can be directly transferred to generate adversarial samples when the budget changes. Furthermore, the visualization of adversarial samples generated by our method shows a variety of attack patterns, which helps identify the vulnerability of the victim models.
Our future works include simultaneously making perturbations in structure and node features and performing evasion attacks on directed graphs and graphs with edge attributes. In addition, two promising directions are exploring how imbalanced datasets influence the performance/robustness of GNNs and the interaction between robustness and explainability [47] by diving into adversarial samples.

APPENDIX A CHALLENGES IN EVASION ATTACK
Unlike attack methods for node classification and link prediction, we find some challenges in designing evasion attack methods for graph classification. They are: (1) Huge search space. The perturbation space is huge when the size of graph data is big. For example, it is hard for attackers to obtain the optimal adversarial samples when making edge perturbations. Different from mainly considering the link situation of the target node in the nodelevel task, the time complexity in the graph-level attack tasks is O(n 2 ), where n is the node number of the graph. When d-dimension binary attributes are associated with edges [48], this complexity changes to worse O(2 d n 2 ). It is usually difficult for the adversary to solve this discrete combinatorial optimization problem.
(2) Profits maximization. The profits here include the direct and indirect profits. The direct profit is the attack benefit since the primary goal of attackers is to obtain adversarial samples with high attack performance. The indirect profits contain learning transferable strategies and defect mining. In the aspect of transferable strategies, attackers expect to learn strategies that help attack unseen samples or generate adversarial samples under a changed perturbation budget. In the aspect of defect mining, the adversary yearns for revealing the defects or weaknesses of the victim models by analyzing the patterns in adversarial samples. The weaknesses of the victim models inspire attackers in designing more powerful attack methods. Once the flaws of the victim models are found, they could customize the attack strategies for different types of data to improve the attack performance.

APPENDIX B DIFFERENT MEASURES OF ATTACK BENEFIT
In this section, we will discuss the measure differences between sensitivity, long-term benefit, and importance concerning the attack benefit principle. Fig. 7. Illustration of GradArgmax and RL-S2V. GradArgmax uses realtime gradient information to make perturbations, RL-S2V utilizes the estimated long-term benefits to finish the attack.

B.1 Sensitivity
The sensitivity here refers to the gradient in the GradArgmax method. It is intuitional to employ the gradient to make perturbation decision, since the gradient in GradArgmax method exactly describe the structure or feature sensitivity of graph G with respect to the victim model f θ . Taking the edge perturbation on graph G as example, a coefficient a u,v is introduced for each nodes pair (u, v) ∈ V × V, and a u,v = I(v ∈ N (u)). The message function in Section 3.2 changes to To generate an adversarial sample, attackers first need to calculate the gradient on all a u,v where L is the loss function of victim models. Then GradArgmax will choose the position with the largest positive g u,v to add an edge or the smallest negative g u,v to remove an edge. GradArgmax will repeat the above process until it uses up all perturbation budget k. However, the gradient which measures the sensitivity is not suitable enough to measure the importance of each perturbation operation for some reasons [49], [50], [51]: (1) The perturbation generated by GradArgmax is suboptimal. The principle in GradArgmax is choosing the position with gradient extremum to make modifications. If there is an edge at the position with the largest positive gradient value or there is no edge at the position with the smallest negative gradient value, GradArgmax will have to re-select the perturbation position.
which is only a first-order linear approximation function about ∆G. However, to obtain powerful discrimination ability, GNN models usually contain nonlinear activation functions like ReLU. The linear approximation based on local gradient can't describe the change in the output of the victim models well when the input value changes greatly.
(3) The iterative selection of perturbation operations based on local gradients cannot accurately describe the attacker's expectations. The GradArgmax attempts to use the local gradient to approximately measure the importance of each perturbation operation in the generation of adversarial samples. When the perturbation budget k > 1, the local gradient is not a suitable approximate meassure. The reason is the local gradient g u,v at the κ th (1 < κ ≤ k) perturbation step is calculated based on current graph which is obtained by adding a perturbation graph ∆G ∈ T κ−1 (G). Actually, in the κ th perturbation step, the attackers attempt to choose the perturbation operation which brings κ th largest attack benefit for the original clean sample G, but not the operation that brings 1 st largest benefit for current graph G + ∆G (∆G ∈ T κ−1 (G)). So the gradient information is enough to predict the sensitivity but not a suitable meassure to identify the importance of each operation.

B.2 Long-term Benefit
The long-term benefit here is the estimated reward of each operation in the adversarial samples generated by reinforcement learning. A conspicuous drawback of GradArgmax is that the greedy selection mechanism focuses on the shortterm benefit (i.e., maximizing loss function) of the current operation, while neglect the benefit of current operation should be defined by its importance in final adversarial samples. In the training of RL-S2V with perturbation budget k, the estimated reward of each perturbation operation is 0 when the perturbation budget k is not used up. Once the budget is exhausted, the adversarial samples obtain positive or negative reward defined by the output of the victim model f θ on these samples. In the experience pool of RL-S2V, the long-term benefit of each perturbation operation is determined by the final benefit of adversarial samples. In this way, RL-S2V can learn a more powerful attack strategy than GradArgmax.

B.3 Importance
The reward function in RL-S2V mainly focuses on the overall benefits caused by all perturbation operations in the adversarial samples. The long-term benefit of each perturbation operation in RL-S2V can only be evaluated by the reward function after the generation of adversarial examples exhausts all perturbation budget k. The long-term benefit reflects the absolute importance of each perturbation operation according to the reward function under a specific budget k. This kind of absolute importance of the same perturbation operation is different under various perturbation budgets in attack methods based on reinforcement learning [22], [24], so RL-S2V needs retraining to obtain attack strategy when the perturbation budget changes. From the perspective of operation ranking principle, compared with the specific absolute importance of each perturbation operation, attackers are more concerned about which perturbation operation should be selected from the perturbation space (i.e., relative importance).