Adversarial Attack and Defense on Graph Data: A Survey
Lichao Sun Yingtong Dou Carl Yang Ji Wang Yixin Liu Philip S. Yu Lifang He Bo Li






Adversarial Attack and Defense on Graph Data: A Survey
    Lichao Sun, 
        Yingtong Dou, 
        Carl Yang, 
        Kai Zhang,
        Ji Wang, 
        Yixin Liu,
        Philip S. Yu, Fellow, IEEE,
        Lifang He, 
        and Bo Li, 
        Lichao Sun, Kai Zhang, Yixin Liu, Lifang He are with the Department of Computer Science and Engineering, Lehigh University, Bethlehem, PA, 18015 USA. E-mail: {lis221, kaz321, yila22, lih319}@lehigh.edu.
        Yingtong Dou, and Philip S. Yu are with the University of Illinois Chicago, Chicago, IL, 60607 USA. E-mail: {ydou5, psyu}@uic.edu
        Carl Yang is with the Emory University Atlanta, GA 30322 USA. E-mail: j.carlyang@emory.edu
	    Ji Wang is with the College of Systems Engineering, National University of Defense Technology, Changsha, Hunan, 410073 P. R. China. E-mail: wangji@nudt.edu.cn.
	    Bo Li is with the University of Illinois Urbana-Champaign at Champaign, IL 61820 USA. E-mail: lbo@illinois.edu
	    

    December 30, 2023
===============================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================




    Deep neural networks (DNNs) have been widely applied to various applications, including image classification, text generation, audio recognition, and graph data analysis. However, recent studies have shown that DNNs are vulnerable to adversarial attacks. Though there are several works about adversarial attack and defense strategies on domains such as images and natural language processing, it is still difficult to directly transfer the learned knowledge to graph data due to its representation structure. Given the importance of graph analysis, an increasing number of studies over the past few years have attempted to analyze the robustness of machine learning models on graph data. Nevertheless, existing research considering adversarial behaviors on graph data often focuses on specific types of attacks with certain assumptions. In addition, each work proposes its own mathematical formulation, which makes the comparison among different methods difficult. Therefore, this review is intended to provide an overall landscape of more than 100 papers on adversarial attack and defense strategies for graph data, and establish a unified formulation encompassing most graph adversarial learning models. Moreover, we also compare different graph attacks and defenses along with their contributions and limitations, as well as summarize the evaluation metrics, datasets and future trends. We hope this survey can help fill the gap in the literature and facilitate further development of this promising new field [We also have created an online resource to keep track of relevant research on the basis of this survey at <https://github.com/safe-graph/graph-adversarial-learning-literature>.].
    
    
    









adversarial attack, adversarial defense, adversarial learning, graph data, graph neural networks





§ INTRODUCTION


Recent years have witnessed significant success achieved by deep neural networks (DNNs) in a variety of domains, ranging
from image recognition <cit.>, natural language processing <cit.>, graph data applications <cit.>, to healthcare analysis <cit.>,
brain circuit modeling <cit.>, and gene mutation functionality <cit.>. 
With the superior performance, deep learning has been applied in several safety and security critical tasks such as self driving <cit.>, malware detection <cit.>, identification <cit.> and anomaly detection <cit.>.
However, the lack of interpretability and robustness of DNNs makes them vulnerable to adversarial attacks. Szegedy et al. <cit.> have pointed out the susceptibility of DNNs in image classification. The performance of a well-trained DNN can be significantly degraded by adversarial examples, which are carefully crafted inputs with a small magnitude of perturbations added.
Goodfellow et al. <cit.> analyzed this phenomenon and proposed a gradient-based method (FGSM) to generate adversarial image samples. Different adversarial attack strategies are then proposed to demonstrate the vulnerabilities of DNNs in various settings  <cit.>.
For instance, black-box adversarial attacks are later explored based on transferability <cit.> and query feedback from DNN models <cit.>. Some defense and detection methods have also been followed to mitigate such adversarial behaviors <cit.>, while various adaptive attacks continue to be proposed showing that detection/defense is hard in general <cit.>.



Although there are an increasing number of studies on adversarial attack and defense, current research mainly focuses on image, natural language, and speech domains. The investigative effort on graph data is at its infancy, despite the importance of graph data in many real-world applications. For example, in the credit prediction application, an adversary can easily disguise himself by adding a friendship connection with others, which may cause severe consequences <cit.>. Compared with non-graph data, the adversarial analysis of graph data presents several unique challenges: 1) Unlike image data with continuous pixel values, the graph structure are discrete valued. It is difficult to design an efficient algorithm that can generate adversarial examples in the discrete space. 2) Adversarial perturbations are designed to be imperceptible to humans in the image domain, so one can force a particular distance function, such as ℓ_p-norm distance to be small between adversarial and benign instances. However, in graph data, how to define “imperceptible” or “subtle perturbation” requires further analysis, measurement and investigation.

Given the importance of graph applications in the context of big data and the successful use of graph neural networks (GNNs), the robustness of GNNs has attracted significant interests from both academia and industry. In recent years, many efforts have been made to explore adversarial attacks and defenses for a set of GNN models. The purpose of this paper is to present a comprehensive taxonomy of existing adversarial learning literature on graph data, to develop a framework to unify most existing approaches, and to explore the future tendencies.




All relevant attack and defense studies are listed in Tables <ref> and <ref>, primarily on the basis of tasks, strategies, baselines, evaluation metrics and datasets. Despite more than 100 papers published in the last three years, there are several challenges remaining unsolved until now, which we contribute to summarize and introduce in this work as follows.

Comprehensive Understanding. To the best of our knowledge, this survey is the first attempt to present an in-depth and comprehensive understanding of the literature about adversarial attack and defense on graph data. 

It has stimulated (and been cited by) various following-up research in this line <cit.>. 

This paper not only provides a broad perspective and guidance for key adversarial attack and defense technologies in the context of GNNs, but also explains many observations related to non-gradient and non-model-based approaches and gives an insight into future directions.


Online Updating Resource.
We created an open-source repository that includes all relevant works and maintained the update on it in the last two years[<https://github.com/safe-graph/graph-adversarial-learning-literature>]. This repository contains links to all relevant papers and
corresponding codes, which makes it easier for researchers to use and track the latest developments, and could serve as a benchmark library in this area. 

However, many of these papers are preprints and reports which give a preview of research results, we will keep tracking them and weaving any updates into the repository accordingly. 



We hope this resource can foster further research on this important topic, and keep shedding light on all facets of future research and development.

Unified Problem Definition.
Though there have been various attack and defense strategies on graph data, there is no unified approach to characterize their relationships and properties; each model seems to be a result of a unique approach.



It is necessary to establish a good basis for easy understanding of existing models and efficient development of future technologies.

In this review, we pioneer to establish a unified formulation and definition to systematically analyze all adversarial attack models on graph data.
Unlike attacks, defenses on graph data often go beyond adversarial learning, for which we provide additional categories based on their unique strategies.

Taxonomy of Adversarial Analysis on Graph Data.
So far there are over a hundred papers that study adversarial analysis on graph data. Compared with image data and text data, the analyses of graph data are more complex due to variations in the graph structure and task. Listing all papers could help but is not intuitive for readers to quickly understand the similarities and discrepancies between different studies. To this end, we summarize existing works based on GNN and Non-GNN methods, aiming to help readers find the most relevant papers easily. We present our taxonomy with more details in Table <ref>.

Datasets and Metrics.
Due to different goals and data used in previous attack and defense works, it is difficult to compare the results of different studies.
Currently, no one could directly answer the question about “what attack or defense is the best benchmark in this domain?”. The only way to alleviate this is to build a benchmark like other areas <cit.>. Toward this end, we not only develop taxonomies for previous approaches based on different criteria, but also summarize the corresponding datasets and metrics that are frequently used. We hope this study could pave the way for the community to establish a benchmark for future research and practical selection of models in this area.

The rest of this survey is organized as follows: Section <ref> provides the necessary background information of graph data and common applications.
Section <ref> presents the unified problem formulation and discusses the existing adversarial attack works on graph data.
Section <ref> discusses the existing defense works on graph data.
Section <ref> summarizes the evaluation and attack metrics used in different studies.
Section <ref> describes the details of each dataset and summarizes existing works across datasets.
The last section concludes this review.






§ GRAPH
 


In this section, we first give the notations of graph data, and then introduce the preliminaries about graph types, learning settings, and application tasks. The most frequently used notaions in the paper are summarized in Table <ref>.



 §.§ Notations

We use 𝒢={G_i}_i=1^N to represent a set of graphs, where N is the number of graphs.
Each graph G_i is generally denoted by a set of nodes V_i={v_j^(i)} and edges E_i={e_j^(i)},
where e_j^(i) = (v_j,1^(i),v_j,2^(i)) ∈V_i×V_i is the edge between the nodes v_j,1^(i) and v_j,2^(i).
Both nodes and edges can have arbitrarily associated data such as node features, edge weights and edge directions.
According to these properties, graph data can be classified into different types as follows.





 §.§ Types of Graph Data

Dynamic and Static Graphs. From a temporal perspective, graph data can be grouped into static graphs and dynamic graphs. 
A graph is dynamic, denoted as G^(t), if any of its nodes, edges, node features, or edges features change over time.
On the contrary, a static graph, denoted as G,
consists of a fixed set of nodes and edges without changing over time.

A typical example of static graph is the molecular structure of drugs <cit.>. Once a drug is developed, its molecular structure does not change over time.
Social network <cit.> is a good example of dynamic graphs.
As people often add or remove friendship links in their social networks, the graph of relationships and interactions changes over time.
In most existing attack works, the researchers study the attacks on dynamic graphs.

Directed and Undirected Graphs.
The graphs can be divided into directed and undirected graphs according to whether the direction between the initial node and end node is unidirectional or bidirectional.
A directed graph, denoted as G^(Dr), has direction information associated with each edge,
where any directed edge e_1^(i) = (v_1^(i), v_2^(i)) ≠ (v_2^(i), v_1^(i)) = e_2^(i), while an undirected graph has edges made up of unordered pairs of nodes.


Facebook is a classic undirected graph that A is B's friend means B is A's friend too. In contrast to friendships, links of many real networks such as the World Wide Web (WWW), food webs, neural networks, protein interaction networks and many online social networks are directed or asymmetrically weighted. Twitter is a typical example of directed graph, where the directed edge represents the following information from one user to another.






Attributed Graph on Edge. An attributed graph on edge, denoted as G^(A_e), has some features associated with each edge, which is denoted by x(e_j^(i)) ∈^D_edge.


The weighted graph where each edge has a weight, x(e_j^(i)) ∈, is a special case of attributed graph on edges.
A traffic flow graph <cit.> is a typical example of weighted graph where roads are modeled as edges and road conditions are represented by weights of edges.

Attributed Graph on Node. An attributed graph on node, denoted as G^(A_n), has some features associated with each node, which is denoted by x(v_j^(i)) ∈^D_node.

The e-commerce network <cit.> with different users can be regarded as an example of attributed graph on node where each user is modeled as nodes with some features like demographics and clicking history.

Note that, directed graph and heterogeneous information networks are special cases of attributed graph, which are widely used to model different applications.



 §.§ Learning Settings on Graph Data

This section introduces the different machine learning settings used on graph data.
Before introducing the learning settings, we first provide the notations for mathematical formulation.
We associate the target component c_i within
a graph G^c_i∈ with a corresponding ground truth label y_i ∈ = {1, 2, …, Y}. Here i ∈ [1, K], K represents the total number of target components, and Y is the number of classes being predicted. 
The dataset ^(ind)= {(c_i, G^c_i, y_i)}^K_i = 1 is represented by the target graph component, graph containing c_i, and the corresponding ground truth label of c_i.
For instance, in a node classification task, c_i represents the node to be classified, and y_i denotes its label within G^c_i.
Based on the features of training and testing processes,
the learning settings can be classified as inductive and transductive learning.


Inductive Learning. It is the most realistic machine learning setting
where the model is trained by labeled examples, and then predicts the labels of examples never seen during training.
Under the supervised inductive learning setting, the classifier f^(ind)∈ F^(ind) :→ is optimized:

    ^(ind) = 1/K∑^K_i=1(f^(ind)_θ(c_i, G^c_i), y_i),

where (·, ·) is the cross entropy by default, 
and c_i can be node, link or subgraph of its associated graph G^c_i.
Note that, two or more different instances, c_1, c_2, …, and c_n can be associated with the same graph G ∈.

Transductive Learning.
Different from inductive learning, the testing graphs have been seen during training in the transductive learning.
In this case, the classifier f^(tra)∈ F^(tra) :→ is optimized:

    ^(tra) = 1/K∑^K_i=1(f^(tra)_θ(c_i, G^c_i), y_i).

Transductive learning predicts the label of seen instances,
but inductive learning predicts the label of unseen instances.


Unified Formulation of Learning on Graph Data.
We give an uniform formula to represent both supervised inductive and transductive learning as below:

    ^(·) = 1/K∑^K_i=1(f^(·)_θ(c_i, G^c_i), y_i),

where f^(·)_θ = f^(ind)_θ is inductive learning and f^(·) = f^(tra)_θ is transductive learning.

In the unsupervised learning setting, we can use the unlabelled dataset ^(ind)= {(c_i, G_j)}^K_i = 1 and replace the supervised loss  and function f(c_i, G_i) of Eq. (<ref>).

In this survey, we mainly focus on the supervised learning setting, while also introducing a few new works in the unsupervised learning setting.




 §.§ Application


In this section, we will introduce the main tasks on graph data,
including node-level, link-level and graph-level applications.
Moreover, we also introduce how to use the unified formulation of Eq. (<ref>) to define each application task below.

Node-Level Application.
The node-level application is the most popular one in both academia and industry.
A classic example is labeling the nodes in the Web and social network graphs, 
which may contain millions of nodes, such as Facebook and Twitter.

Most existing papers <cit.>
focus on node-level applications.
All of these papers study node classification in the transductive learning setting whose objective function can be formulated by modifying Eq. (<ref>)
where f^(·)_θ = f^(tra)_θ, c_i here is the representation of node target and its associated graph G^c_i is set as a single graph G.

Few existing works have discussed the node-level applications in the inductive leaning setting. However, these applications frequently appear in real life.
For example, the first party only has several large and public network information, such as Facebook and Twitter.
The second party has private unlabeled graph data in which the nodes can be predicted by using the information from the first party.
In this case, the node-level classification task is no longer transductive learning. It can be easily formulated by modifying Eq. (<ref>) with f^(·)_θ = f^(ind)_θ and c_i here is still the representation of node target.

Link-Level Application.
Link prediction on dynamic graphs is one of the most common link-level applications.
The models try to predict missing links in current networks, as well as new or dissoluted links in future networks.
The corresponding attacks and defenses have been discussed in <cit.>.

Compared with node classification tasks, link predication tasks still use node features,
but target at the missing or unlabelled links in the graph.
Therefore, we can formulate the link predication task by slightly modifying Eq. (<ref>)
with c_i being the representation of link target, and y_i ∈{0, 1}.

Graph-Level Application. 
Graph-level tasks are frequently seen in the chemistry or medical areas,
such as the modeling of drug molecule graphs and brain graphs. In <cit.>, the whole graph is used as the sample instance. Different from this setting, some other graph-level applications use the subgraphs of a larger graph for particular tasks <cit.>.

Compared with the existing works on node classification and link predication,
graph classification uses the graph-structure representation as the features to classify the unlabelled graph instances.
Therefore, we can formulate the graph classification task by slightly modifying Eq. (<ref>)
by setting c_i as the representation of graph target.















§ ADVERSARIAL ATTACKS ON GRAPH DATA
 

In this section, we give a general definition and taxonomies of adversarial attacks on graph data,
and then introduce the imperceptibility metrics, attack types, attack tasks and levels of attack knowledge.



 §.§ An Unified Definition and Formulation


(General Adversarial Attack on Graph Data)
    Given a dataset = (c_i, G_i, y_i), after slightly modifying G_i (denoted as G^c_i),
    the adversarial samples G^c_i and G_i should be similar under the imperceptibility metrics,
    but the performance of graph task becomes much worse than before.



Existing papers <cit.> considering adversarial behaviors on graph data usually focus on specific types of attacks with certain assumptions.
In addition, each work proposes its own mathematical formulation which makes the comparison among different methods difficult.
In order to help researchers understand the relations between different problems,
we propose a unified problem formulation that can cover all current existing works.

(Adversarial Attack on Graph Data: A Unified Formulation)
    f can be any learning task function on graph data,
    e.g., link prediction, node-level embedding, node-level classification,
    graph-level embedding and graph-level classification.
    Φ(G_i) denotes the space of perturbation on the original graph G_i,
    and dataset  = {(c_i, G^c_i, y_i)}_i=1^N denote the attacked instances.
    The attack can be depicted as,
    
    G^c_i∈Φ(G_i)max      ∑_i (f^(·)_θ^*(c_i, G^c_i), y_i)) 
       s.t.      θ ^* = min_θ∑_j (f^(·)_θ(c_j, G'_j), y_j)).

When G'_j equals to G^c_j, Eq. (<ref>) represents the poisoning attack, whereas when G'_j is the original G without modification, Eq. (<ref>) denotes the evasion attack.
f^(·)_θ = f^(ind)_θ represents inductive learning and f^(·)_θ = f^(tra)_θ transductive learning.

Note that, with G^c_i∈Φ(G), (c_i, G^c_i) can represent node manipulation, edge manipulation, or both.
For any G^c_i∈Φ(G_i), G^c_i is required to be similar or close to the original graph G_j, and such similarity measurement can be defined by the general distance function below:

    𝒬( G^c_i, G_i) < ϵ
       s.t.   G^c_i∈Φ(G_i)

where 𝒬(·, ·) represents the distance function, and ϵ is a parameter denoting the distance/cost budget for each sample.

Discussion: Graph Distance Function.



Graph distance functions can be defined in many ways,
a lot of which have been discussed on graph privacy-preserving related work <cit.>.

Such distance functions include the number of common neighbours of given nodes, cosine similarity, Jaccard similarity and so on. 
However, few of them are discussed in depth regarding adversarial behaviors (adversarial cost in game theory). 
In general, an attacker aims to make “minimal" perturbations on the existing graph and therefore such distance measurement is important to measure the quality of attacks. How to design and choose proper distance function to quantify the attack ability under different attack scenarios is also critical towards developing defensive approaches regarding specific threat model. 
We will discuss potential perturbation evaluation metrics in detail in Sec <ref>.

In addition to the unique properties of each graph distance function, it would also be interesting to analyze the “equivalence" among them.

For instance, an attacker aims to attack one node by adding/removing one edge in the graph can encounter similar “adversarial cost" as adding/removing edges.
It is not hard to see that by using a graph distance function or similarity measures,
only a few targets would be the optimal choices for the attacker (with different distance), so this can also help to optimize the adversarial targets.


In summary, due to the complexity and diversity of graph representations and adversarial behaviors,
perturbation evaluation or graph similarity measurement will depend on various factors such as different learning tasks, adversarial strategies, and adversarial cost types.






















 §.§ Adversarial Perturbation



To generate adversarial samples on graph data, we can modify the nodes or edges from the original graph.
However, the modified graph G need to be “similar” with the original graph G based on certain perturbation evaluation metrics and remain “imperceptible". The following metrics help understand how to define “imperceptible perturbation".

Edge-level Perturbation.
In most existing works, the attacker is capable of adding/removing/rewiring edges in the whole original graph within a given budget.
In this case, the number of modified edges is usually used to evaluate the magnitude of perturbation.
In addition to other perturbations, edge perturbation is hardly found by the defender, especially in dynamic graphs.

Node-level Perturbation.
The attacker is also capable of adding/removing nodes, or manipulating the features of target nodes.
The evaluation metric in this case can be calculated based on the number of nodes modified or the distance between the benign and adversarial feature vectors. 

Structure Preserving Perturbation.
Similar to edge-level perturbation, an attacker can modify edges in the graph within a given budget in terms of graph structure.
Compared to general edge-level perturbation, this considers more structural preservation, such as total degree, node distribution, etc.
For instance, in <cit.>, the attacker is required to preserve the key structural features of a graph such as the degree distribution.
Therefore, the perturbation here can be measured by the graph structure drift.


Attribute Preserving Perturbation.
In the attributed graphs, each node or edge has its own features. 
In addition to manipulating the graph structure,
the attacker can choose to modify the features of nodes or edges to generate adversarial samples on graph data.
Various measurements based on graph-attribute properties can be analyzed to characterize the perturbation magnitude. 
For instance, in <cit.>, 
the authors argue adding a feature is imperceptible if a probabilistic random walker on the co-occurrence graph can reach it with high probability by starting from existing features.

Note that, most GNN methods learn the feature representation of each node, which means it could be easily attacked by structure-only, feature-only perturbations or both. 

Principles of imperceptible perturbation evaluation.
Given various graph distance discussion, there is no clear discussion in existing research about how to set the adversarial cost for attacks on graph data so far. Therefore, we summarize some principles of defining the perturbation evaluation metrics as below for future research.


    
  * For static graph, both the number of modified edges and the distance between the benign and adversarial feature vectors should be small.
    
    
  * For a dynamic graph, we can set the distance or adversarial cost based on the intrinsic changing information over time.
    For example, by using statistic analysis, we can get the upper bound of the information manipulated in practice,
    and use this information to set an imperceptible bound. 
    
  * For various learning tasks on graph data, e.g., node or graph classification,
    we need to use a suitable graph distance function to calculate the similarity between the benign and its adversarial sample.
    For example, we can use the number of common neighbours to evaluate the similarity of two nodes, but this is not applicable for two individual graphs. 
    

In summary, compared to image and text data, an attacker first can modify more features on the information network, and also can explore more angles to define “imperceptible” based on the format of graph data and the application task.








 §.§ Attack Stage


The adversarial attacks can happen at two stages:
evasion attack (model testing) and poisoning attacks (model training).
It depends on the attacker’s capacity to insert adversarial perturbations:

Poisoning Attack.
Poisoning attack tries to affect the performance of the model by adding adversarial samples into the training dataset.
Most existing works are poisoning attacks,
and their node classification tasks are performed in the transductive learning setting.
In this case, once the attacker changes the data, the model is retrained.
Mathematically, by setting G'_j = G^c_j in Eq. (<ref>),
we have a general formula for adversarial attack on graph data under poisoning attacks.

Evasion Attack.
Evasion attack means that the parameters of the trained model are assumed to be fixed.
The attacker tries to generate the adversarial samples of the trained model.


Evasion attack only changes the testing data, which does not require to retrain the model.
Mathematically, by setting G'_j to original G_j in Eq. (<ref>),
we have a general formula for adversarial attack on graph data under evasion attacks.




 §.§ Attack Objective


Though all adversarial attacks are modifying the data,
an attacker needs to choose their attack targets or objectives: model or data.
In this case, we can summarize them as model objective and data objective.

Model Objective.
Model objective is attacking a particular model by using various approaches.
It could be either evasion attack or poisoning attack.
Most current adversarial attack is related to model objective attack.

The target could be either GNN or other learning models. An attacker wants to make the model become non-functional in multiple scenarios.
Model objective attack can be categorized by whether using the gradient information of the model or not.

    
  * Gradient-based Attack. 
    In most studies, we can see that the gradient-based attack is always the simplest and most effective approach.
    Most gradient-based attack, no matter white-box or black-box, tries to get or estimate the gradient information to find the most important features to the model.
    Based on the above knowledge, an attacker can choose to modify the limited information based on the feature importance to the model and make the model inaccurate when using the modified information <cit.>.
    
    
  * Non-gradient-based Attack. 
    In addition to gradient information, an attack could destroy the model without any gradient information.
    As we know, besides the gradients, many reinforcement learning based attack methods can attack the model based on long-term rewards <cit.>.
    Some works can also construct the adversarial samples with generative models <cit.>.
    
    All the above approaches can attack the model without the gradient information but attack the model in practice. 



Data Objective.
Unlike model objective attacks, data objective attacks do not attack a specific model.
Such attacks happen when the attacker only has access to the data, but does not have enough information about the model. 
In general there are two settings when data become the target.

    
  * Model Poisoning. Unsupervised feature analysis approaches can still get useful information from the data without any knowledge of the training approach.
    Even with a small perturbation on the data, it can make general training approaches cease to work. Besides, backdoor attack is another relevant hot topic where an attacker only injects the adversarial signals in the dataset, but does not destroy the model performance on regular samples <cit.>.
    
  * Statistic Information.
    In addition to using the data to train a model, in many studies, researchers use statistical results or simulation results from the graph data <cit.>. In this case, an attacker can break the model based on the capturing of the valuable statistical information on graph data. For example, by modifying a few edges between different communities based on structural information and analysis, one can make communities counting inaccurate under this attack <cit.>. 






 §.§ Attack Knowledge


The attacker would receive different information to attack the system.
Based on this, we can characterize the dangerous levels of existing attacks.

While-box Attack.
In this case, an attacker can get all information and use it to attack the system,
such as the prediction result, gradient information, etc.
The attack may not work if the attacker does not fully break the system first.

Grey-box Attack. 
An attacker gets limited information to attack the system.
Comparing to white-box attack, it is more dangerous to the system, since the attacker only need partial information.

Black-box Attack.
Under this setting, an attacker can only do black-box queries on some of the samples.
Thus, the attacker generally can not do poisoning attack on the trained model.
However, if black-box attack can work, it would be the most dangerous attack compared with the other two,
because the attacker can attack the model with the most limited acknowledge.

Most existing papers only study white-box attack on the graph,
and there are lots of opportunities to study other attacks with different levels of knowledge.



 §.§ Attack Goal


Generally, an attacker wants to destroy the performance of the whole system,
but sometimes they prefer to attack a few important target instances in the system.
Based on the goal of an attack, we have:

Availability Attack.
The adversarial goal of availability attack is to reduce the total performance of the system.
For example, by giving a modification budget,
we want the performance of the system decreasing the most as the optimal attack strategy.

Integrity Attack. 
The adversarial goal of integrity attack is to reduce the performance of target instances.
For example, in recommendation systems,
we want the model to not successfully predict the hidden relation between two target users.
However, the total performance of the system is the same or similar to the original system.

Availability attack is easier to detect than integrity attack under the positioning attack setting. Therefore, meaningful availability attack studies are in general under the evasion attack setting.



 §.§ Attack Task


Corresponding to various tasks on graph data,
we show how to attack each task and explain the general idea by modifying the unified formulation. 

Node-relevant Task.
As mentioned before, most attack papers focus on node-level tasks,
including node classification <cit.> and node embedding <cit.>.
The main difference is that node embedding uses the low dimensional representations of each node for an adversarial attack.
Mathematically, by setting c_i as representation of node target in Eq. (<ref>),
we have a general formula for adversarial attack on node-relevant tasks.


Link-relevant Task.
Several other existing works study node embedding <cit.> or topological similarity <cit.> and use them for link prediction.
Compared with node classification,
link prediction requires to use different input data,
where c_i represents link target, i.e., the information of a pair of nodes.
By setting c_i as representation of link target and y_i ∈ [0, 1] in Eq. (<ref>),
we have a general formula for adversarial attack on link-relevant tasks.

Graph-relevant Task.
Compared with node classification, graph classification needs the graph representation instead of the node representation <cit.>.
By setting c_i as representation of graph target in Eq. (<ref>),
we have a general formula for adversarial attack on graph-relevant tasks.




 §.§ Summary: Attack on Graph

In this subsection, we analyze the contributions and limitations of existing works.
Then we discuss the potential research opportunities in this area.

Contributions.
First, we list all released papers and their characteristics in Table <ref>, and then categorize them into selected main topics in Table <ref>.
Then, we summarize the unique contributions of existing adversarial attacks.
Note that, because 11 of 34 papers we discuss are pre-print version, we especially list the venue in Table <ref>.
We also firstly use Strategy and Approach to differ individual attack method. Strategy refers to the high-level design philosophy of an attack, while Approach represents the concrete approach the attacker takes to perturb the graph data.

Graph Neural Networks.
Most adversarial attacks are relevant to graph neural networks.
<cit.> used reinforcement learning approach to discover adversarial attack,
which is the only approach that supports black-box attack compared to other works.
<cit.> studied adversarial graph samples with traditional machine learning
and deep learning. Meanwhile, they are the first and only group to discuss the adversarial attack on attributed graph. <cit.> mainly attacked the link predication task with a deep graph convolutional embedding model.
<cit.> attacked multiple models by approximating the spectrum and using the gradient information.
<cit.> attacked node classification through optimization approach and systematically discussed adversarial attacks on graph data.
Previous works focused on edge or node modification, whereas <cit.> also modified the node features and proposed a hybrid attack on the graph convolutional neural networks (GCN) <cit.>.
In addition to gradient check, <cit.> attacked GCN by using the first-gradient optimization and low-rank approximation which makes an attack more efficient.
<cit.> attacked general learning approaches by devising new loss and approximating the spectrum. 
<cit.> used graph attack knowledge into the malware detection problem, which showed various graph-based applications to be vulnerable to adversarial attacks.
Without gradient check and optimization design, <cit.> used reinforcement learning to attack GCN. However, it contains an obvious issue that it needs to break the graph structure by injecting new nodes.
<cit.> tried to hide nodes in the community by attacking the graph auto-encoder model.
Instead of using a gradient check or other optimization approaches, this work leverage the surrogate community detection model to achieve the attacking goal.
More recent works investigates the vulnerability of GNNs under backdoor attacks <cit.>. Backdoor attack modifies the labels of the triggers (e.g., subgraphs with typical patterns) in the training data, and it aims to make the GNNs misclassify those triggers without affecting the overall performance of GNNs on the testing data. 






Others.
Though many attack works are relevant to GNN, many recent papers start to focus on other types of adversarial attacks on graph data.
<cit.> is one of the first works to attack the graph data, and it also first proposed the attack approach in the unsupervised learning setting.
<cit.> first attacked community detection though edge rewriting based on a heuristic approach.
<cit.> attacked link prediction based on a heuristic approach which is based on the similarity measures.
<cit.> used a greedy approach to attack link prediction based local and global similarity measure.
In addition to traditional graph applications, <cit.> first attacked knowledge graph and destroyed the basic relational graph prediction model.
<cit.> attacked community detection based on genetic algorithms. Unlike previous approaches, it chose to use rewiring instead of adding/removing edges while attacking the data.
<cit.> used a generation approach to create a new isomorphism network to attack node classification.
In addition to all previous works, <cit.> started to study attacks through theoretical analysis, and we believe more theoretical works will be seen in this domain.
They can help us understand the attacks better on graph data.
Besides the applications mentioned above, attacking graphs in recommender system <cit.>, fraud detection <cit.>, opinion dynamic <cit.>, and graph classification <cit.> tasks have been drawing attention from researchers as well.



Limitations.
The limitations of most current works are summarized below. 
Most existing works do not give very clear strategies about the setting of the budget and distance with reasonable explanations in real applications.
Different from other adversarial attacks, most graph modifications can hardly be noticed by humans in real life.
To solve this problem, we give a more detailed discussion on perturbation and evaluation metrics in Section <ref>.
Meanwhile, about graph imperceptible evaluation metrics, 
most papers <cit.> use one metric for attack,
but these adversarial samples could be detected by other existing imperceptible evaluation metrics.
In this work, we list all existing evaluation metrics,
and recommend future adversarial samples to be imperceptible with more listed evaluation metrics.

Another main issue is due to the different problem formulations.

To this end, we give the unified problem formulation for all existing works discussed in this survey.

Most Recent Work. For the recently proposed attack methods, imperciptible pertubations such as added edges and modified node features are also the principle approaches like previous work. For the defense models, instead of commonly-used adversarial training techniques before, some researchers  first tried to propose new neiborhood aggregation schemas which guarantee the theoretical robustness under adversarial attack.

Future Directions.
Adversarial attack on graph data is a new and hot area, and potential research opportunities are summarized below:
1) Most graphs are associated with attributes or more complex contents on nodes or edges in practice. However, few studies have well designed adversarial attack on attributed graphs, e.g., heterogeneous information networks and web graphs.

2) Some advanced ideas can be applied for generating the adversarial samples, e.g., homomorphism graph.

3) Various learning settings are not sufficiently studied yet, such as graph-level attacks and inductive learning on node-level attacks.
4) Most existing attacks do not consider various imperceptibility metrics in their models.
Concise and comprehensive imperceptibility metrics are necessary in different tasks.
A good and explainable evaluation metric may easily discover more existing adversarial samples created by current methods. 
5) Last but not least, the distance or similarity measures of high quality adversarial samples are not well studied in this area.




































§ ADVERSARIAL DEFENSE ON GRAPH DATA
 

With graph data, recent intensive studies on adversarial attacks have also triggered the research on adversarial defenses. Here we survey existing works in this line and classify them into the two popular categories of Adversarial Training and Attack Detection. 
After them, we use an additional Other Methods subsection to summarize the remaining methods that do not fit into the two generic categories.



 §.§ Adversarial Training


While adversarial training has been widely used by attackers to perform effective adversarial intrusion, the same sword can be used by defenders to improve the robustness of their models against adversarial attacks <cit.>. In the graph setting, we formulate the objective of adversarial defense by slightly modifying our unified formulation of adversarial attacks, i.e., Eq. (<ref>), as follows

    θminG^c_i∈Φ(G_i)max      ∑_i (f_θ(c_i, G^c_i), y_i)).

where meanings of the notations remain the same as defined in Section <ref>. 
The idea is to alternatively optimize two competing modules during training, where the attacker tries to maximize task-oriented loss by generating adversarial perturbations G on the graph, and the defender tries to minimize the same loss by learning the more robust graph model parameters θ under the generated adversarial perturbations. In this way, the learned graph model is expected to be resistant to future adversarial attacks.

 Structure Perturbations.
The earliest and most primitive way of perturbing the graph is to randomly drop edges <cit.>. The joint training of such cheap adversarial perturbations is shown to slightly improve the robustness of standard GNN models towards both graph and node classification tasks.
One step further, <cit.> proposed a topology attack generation method based on projected gradient descent to optimize edge perturbation. The topology attack is shown to improve the robustness of the adversarially trained GNN models against different gradient-based attacks and greedy attacks <cit.> without sacrificing node classification accuracy on the original graph.
In the meantime, <cit.> proposed to learn the perturbations in an unsupervised fashion by maximizing the influence of random noises in the embedding space, which improved the generalization performance of DeepWalk <cit.> on node classification.
Towards similarity-based link prediction, <cit.> formalized a Bayesian Stackelberg game to optimize the most robust links to preserve with an adversary deleting the remaining links.

 Attribute Perturbations.
Besides links, <cit.> also perturb node features to enable virtual adversarial training <cit.> that enforces the smoothness between original nodes and adversarial nodes. In particular, <cit.> designed a dynamic regularizer forcing GNN models to learn to prevent the propagation of perturbations on graphs, whereas <cit.> smoothed GCN in its most sensitive directions to improve generalization. <cit.> further conducted virtual adversarial training in batch to perceive the connectivity patterns between nodes in each sampled subsets. 
<cit.> leveraged adversarial contrastive learning <cit.> to tackle the vulnerabilities of GNN models to adversarial attacks due to training data scarcity and applied conditional GAN to utilize graph-level auxiliary information.  
Instead of approximating the discrete graph space, <cit.> proposed to directly perturb the adjacency matrix and feature matrix by ignoring the discreteness, whereas <cit.> proposed to focus on the first hidden layer of GNN models to continuously perturb the adjacency matrix and feature matrix. These frameworks are all shown to improve GNN models on the node classification task.

 Attack-oriented Perturbation
Based on existing network adversarial attack methods of FGA <cit.> and Nettack <cit.>, <cit.> designed the adversarial training pipelines with additional smooth defense strategies. The pipeline is shown to improve GNN models against different adversarial attacks on node classification and community detection tasks.
<cit.> employed reinforcement learning to train a robust detector against mixed attacks proposed in the paper.




 §.§ Attack Detection

Instead of generating adversarial attacks during training, another effective way of defense is to detect and remove (or reduce the effect of) attacks, under the assumption that data have already been polluted. Due to the complexity of graph data, the connection structures and auxiliary features can be leveraged based on various ad hoc yet intuitive principles to essentially differentiate clean data from poison ones and combat certain types of attacks.

 Graph Preprocessing.
<cit.> proposed different approaches to detect potential malicious edges based on graph generation models, link prediction and outlier detection.
Instead of edges, <cit.> proposed to filter out node sets contaminated by anomalous nodes based on graph-aware criteria computed on randomly drawn subsets of nodes; <cit.> proposed to detect nodes subject to topological perturbations (particularly by Nettack <cit.>) based on empirical analysis on the discrepancy between the proximity distributions of nodes and their neighbors.
These models only rely on network topology for attack detection.
On attributed graphs, based on the observations that attackers prefer adding edges over removing edges and the edges are often added between dissimilar nodes, <cit.> proposed to compute the Jaccard Similarity to remove suspicious edges between suspicious nodes.
<cit.> sampled sub-graphs from the poisoned training data and then employed outlier detection methods to detect and filter adversarial edges.
All of these models can be used for graph preprocessing before training normal graph models like GNNs. 



 Model Training.
Rather than direct detection of suspicious nodes or edges before training, several works designed specific attention mechanisms to dynamically uncover and down-weigh suspicious data during training. 
<cit.> assumed high prediction uncertainty for adversarial nodes and computed the attention weights based on the embedding variance in a Gaussian-based GCN. 
<cit.> suggested to train an attack-aware GCN based on ground-truth poisoned links generated by Nettack <cit.> and transfer the ability to assign small attention weights to poisoned links based on meta-learning.

 Robustness Certification.
On the contrary of detecting attacks, <cit.> designed robustness certificates to measure the safety of individual nodes under adversarial perturbation. In particular, <cit.> considered structural perturbation while <cit.> considered attribute perturbation. Training GNN models jointly with these certificates can lead to a rigorous safety guarantee of more nodes. From a different perspective, <cit.> derived the robustness certificate of community detection methods under structural perturbation.
<cit.> proved polynomial
spectral graph filters are stable under structural perturbation.

 Complex Graphs
Beyond traditional homogeneous graphs, <cit.> studied the sensitivity of knowledge graph link prediction models towards adversarial facts (links) and the identification of facts. 
<cit.> studied the detection of poisoning nodes in heterogeneous graphs to enhance the robustness of Android malware detection systems.





 §.§ Other Methods

Now we summarize the remaining graph adversarial defense algorithms that are neither based on adversarial training nor aiming at attack detection. We further group them into three subcategories based on their modifications to the graph data and graph models.

 Data Modifications.
We have presented several attack detection algorithms that can be used for modifying graph data, i.e., graph preprocessing <cit.>. There exist methods that modify graph data without directly detecting attacks. 
Based on the insight that Nettack <cit.> only affects the high-rank singular components of the graph, <cit.> proposed to reduce the effect of attacks by computing the low-rank approximation of the graphs before training GNN models.
<cit.> proposed an augmented training procedure by generating more structurally noisy graphs to train GNN models for improved robustness, and showed it to be effective for structural role identification of nodes. 
<cit.> analyzed the topological characteristics of graphs and proposed two training data selection techniques to raise the difficulty of effective adversarial perturbations towards node classification.
These methods are all based on graph topology alone, and they only modify the graph data instead of the graph models.
<cit.> leveraged variational graph autoencoders to reconstruct graph structures from perturbed graphs where the reconstructed graphs can reduce the effects of adversarial perturbations.


 Model Modifications.
On the contrary, there exist methods that only modify the graph models, such as model-structure redesign or loss-function redesign.
The simplest way is to redesign the loss function.
From several existing works, the results show some loss functions perform better performance against the adversarial examples.
For example, <cit.> designed an alternative operator based on graph powering to replace the classical Laplacian in GNN models with improved spectral robustness. They demonstrated the combination of this operator with vanilla GCN to be effective in node classification and defense against evasion attacks.
<cit.> proposed a hierarchical GCN model to aggregate neighbors from different orders and randomly dropped neighbor messages during the aggregation.
Such mechanism could improve the robustness of GCN-based collaborative filtering models.
<cit.> introduced neighbor importance estimation and the layer-wise graph memory components which can be integrated with GNNs.
Those two components could help increase the robustness of GNN models agaisnt various attacks.


Hybrid Modifications.
One step further, some methods modify both the graph data and graph models.
<cit.> designed an edge-dithering approach to restoring unperturbed node neighborhoods with multiple randomly edge-flipped graphs and proposed an adaptive GCN model that learns to combine the multiple graphs. The proposed framework is shown to improve the performance and robustness of GCN towards node classification (in particular, protein function prediction) on attributed graphs.
<cit.> proposed a heuristic method to iteratively select training data based on the degrees and connection patterns of nodes. It further proposed to combine node attributes and structural features and use SVM for node classification instead of any GNN models.
Guided by graph properties like sparsity, rank, and feature smoothness, <cit.> presented Pro-GNN which jointly learns clean graph structure and trains robust GNN models together.




 §.§ Summary: Defense on Graph


From the perspective of defenders, the defense approaches can be designed with or without knowing the specific attacks. Thus, current defense works can be classified into two categories: 1) Attack-agnostic defenses are designed to enhance the robustness of graph models against any possible attacks instead of a fixed one. 2) Attack-oriented defenses are designed according to the characteristics of specific attacks. The attack-agnostic defenses usually have a wider assumption space of attacks comparing to attack-oriented attack. 
Last, we discuss some future opportunities on adversarial defense in this area.

 Attack-agnostic Defense.
As we summarized in Section <ref>, adversarial training is a typical instance of attack-agnostic defense approach <cit.>. It usually generates simple perturbations on graphs or models to train a defense model. In the test phase, some models trained in this way could exhibit good robustness against those perturbations. Some methods <cit.> trained in this way even attain good defense performance against other specific attacks like Meta-self proposed in <cit.>. Note that the defense methods are designed and trained without knowing other new attacks.

Besides adversarial training, other works secure the graph model with heuristic assumptions on the attack strategies and outcomes. <cit.> assumes that there are unpolluted graphs to aid the detection of attacks. <cit.> propose new GNN architectures to enhance their robustness. <cit.> directly curates an optimal training set to mitigate the vulnerability of trained models.

Attack-oriented Defense.
Attack-oriented defenses are designed based on the strategy and approach of specific attacks. Namely, the defender has full knowledge of an attack method and the defense method could detect the corresponding attack or curb its performance. Among current defense works, <cit.> first argued the weakness of Nettack <cit.> and leveraged SVD to defend against Nettack. <cit.> analyzed the strategies and approaches of  Nettack <cit.> and RL-S2V <cit.> and proposed an adversarial training method. <cit.> inspected two gradient-based attacks (i.e., FGSM <cit.> and JSMA <cit.>) and applied edge-dropping technique during model training to alleviate the influence of such attacks. Similar to attack-agnostic defenses, some attack-oriented methods exhibit good generability which means it can defend against other unknown attacks. For instance, the defense method proposed in <cit.> could defend the Nettack as well. 
Along with the Corresp. Attack column of Table <ref>, we could see that Nettack and RL-S2V have become benchmark attack methods for defense design and evaluation. 
Some works employ the framework of minimax game <cit.> or optimization <cit.> to certify the robustness bounds of graph models under given attacks and defenses. Such kind of defense works are attack-oriented since they have assumed specific attacks.

Most Recent Work. In addition to common tasks such as node classification and link prediction, attacks  and defenses  on graph alignment tasks (e.g. graph matching) were also proposed.

 Limitations and Future Directions.
We have been focusing on the contributions of different existing works on graph adversarial defense. Now we summarize some common limitations we observe in this line of research and hint on future directions:
1) Most defense models focus on node-level tasks, especially node classification, while it may be intriguing to shed more light on link- and graph-level tasks like link prediction and graph classification. There is also large potential in more real-life tasks like graph-based search, recommendation, advertisement and etc.
2) While network data are often associated with complex contents nowadays (e.g., timestamps, images, texts), existing defense models have hardly considered the effect of attacks and defenses under the settings of dynamic or other content-rich complex networked systems.
3) Most defense models are relevant to GNNs or GCN in particular, but there are many other graph models and analysis methods, possibly more widely used and less studied (e.g., random walk based models, stochastic block models, and many computational graph properties). How are they sensitive and prone to graph adversarial attacks? Can the improvements in GNN models transfer and generalize to these traditional methods and measures?
4) Most existing works do not study the efficiency and scalability of defense models. As we know, real-world networks can be massive and often frequently evolve, so how to efficiently learn the models and adapt to changes is very important for defenders.
5) While there are standard evaluation protocols and optimization goals for down-stream tasks like node classification and link prediction, defense methods are optimized towards heterogeneous goals like accuracy, robustness, generalizability and so on, and they tend to define their own experimental settings and metrics, rendering fair and comprehensive evaluations challenging.




§ METRICS
 



In this section, we summarize the metrics for evaluating attack and defense performance on graph data. We first briefly introduce the general evaluation metrics along with some notes on their specific usage in adversarial performance evaluation. We then give a detailed introduction of particular evaluation metrics designed for attacks and defenses.



 §.§ General Metric




  §.§.§ Accuracy-based Metric


According to Table <ref> and Table <ref>, many existing works tackle the node classification problem which is usually a binary or multi-class classification problem. The accuracy-based metrics like Accuracy, Recall, Precision, and F1 score are all used by existing works to reflect the classification accuracy from different angles. Readers can refer to <cit.> for detailed explanations of those metrics. Note that the False Negative Rate (FNR) and False Positive Rate (FPR) used by <cit.> are two metrics derived from the confusion matrix. FNR is the percentage of false negatives among all actual positive instances, which describes the proportion of positive instances missed by the classifier. Similarly, FPR reflects the proportion of negative instances misclassified by the classifier. Adjusted Rand Index (ARI) <cit.> is an accuracy-based metric without label information. <cit.> uses it to measure the similarity between two clusters in a graph.

Besides the above metrics, Area-under-the-ROC-curve (AUC) <cit.> and Average
Precision (AP) <cit.> are widely used, such as by <cit.>. AUC is sensitive to the probability rank of positive instances, which is larger when positive instances are ranked higher than negative instances according to the predicted probability of a classifier. AP is a metric balancing the Precision and Recall where AP is higher when Precision is higher as Recall threshold increase from 0 to 1. Those two metrics could better reflect the classification performance as single scores since they provide an all-around evaluation over the predicted probabilities of all instances.




  §.§.§ Ranking-based Metric

Mean Reciprocal Rank (MRR) <cit.> and Hits@K are two ranking metrics used by <cit.> to evaluate the performance of link prediction on knowledge graphs. Given a list of items retrieved regarding a query and ranked by their probabilities, the reciprocal rank of a query response is the multiplicative inverse of the rank of the first correct item: 1 for first place, 1⁄2 for second place, 1⁄3 for third place and so on. Hits@K is the number of correct answers among the top K items in the ranking list. It can be used to evaluate the performance of recommender system as well <cit.>. nDCG@K <cit.> is another metric to evaluate the robustness of recommendation models <cit.>.




  §.§.§ Graph-based Metric

The graph-based metrics indicate the specific properties of a graph. Normalized Mutual Information (NMI) <cit.> and Modularity <cit.> are two metrics used by <cit.> to evaluate the performance of community detection (i.e., clustering) on graphs. NMI is originated from information theory that measures the mutual dependence between two variables. In a community detection scenario, NMI is used to measure the amount of shared information (i.e., similarity) between two communities. Modularity is designed to measure the strength of the division of a graph into clusters. Graphs with high Modularity have dense connections between the nodes within clusters but sparse connections between nodes in different clusters.


<cit.> employs a couple of graph property statistics as metrics to evaluate how much the attacker changed the graph (i.e., the imperceptibility of attacks). The metrics include Gini Coefficient, Characteristic Path Length, Distribution Entropy, Power Law Exponent, and Triangle Count. Please refer to <cit.> for more details about those metrics. Some more graph statistics metrics include Degree Ranking, Closeness Ranking, Betweenness Ranking used by <cit.> and Clustering Coefficient, Shortest Path-length, Diagonal Distance used by <cit.>.



 §.§ Adversarial Metric

Besides the general metrics above, a number of metrics which measure the attack and defense performance on graph data have been proposed or used by existing works. We first present the detailed formulations and descriptions of widely used metrics, and then briefly summarize some unique metrics used by particular papers. The reference after each metric name refers to the first paper that proposes or uses this metric and the references inside the parentheses refer to other attack and defense papers using this metric. 



  §.§.§ Common Metric





  * Attack Success Rate (ASR) <cit.>
(<cit.>).
ASR is the most frequently used metric to measure the performance of a giving attack approach:

    ASR = # Successful attacks/# All attacks.




  * Classification Margin (CM) <cit.>
(<cit.>).
CM measures the performance of the integrity attack:

    CM(t) = p_t, c_t - max_c≠ c_tp_t, c,

where t is the target instance, c_t is the
ground-truth class for t, p_t, c is the probability of t being c. The above equation calculates the maximum difference between the probability of ground-truth class and that of other classes. In other words, it shows the extent of an attack flipping the predicted class of a target instance. <cit.> proposed another version of CM:

    CM(t) = logp_t, c_t/max_c≠ c_tp_t, c.


When the instance is correctly classified, CM will be positive; otherwise it will be negative.



  * Correct/Mis Classification Rate <cit.>
(<cit.>).
Those two metrics evaluate the attack/defense performance based on the classification results among all instances. 

    MCR   = # Misclassified instances/# All instances: 
    CCR   = 1 - MCR.




  * Attacker Budget <cit.>
(<cit.>).
Attacker budget is a general metric to measure the minimum perturbations the attacker needs to fulfill its objective. The lower value indicates a better attack performance and a worse defense performance respectively. <cit.> takes the number of removed edges as the attacker budget. <cit.> take the smallest number of perturbations for the attacker to successfully cause the target to be misclassified as the budget.



  * Average Modified Links (AML) <cit.>
(<cit.>).
AML is a variance of Adversary budget introduced above. It describes the average number of modified links the attacker needed to meet the attack objective:

    AML = # Modified links/# All attacks.



  * Concealment Measures <cit.>
(<cit.>).
The concealment measures are used to evaluate the performance of hiding nodes or communities in a graph <cit.>. From another perspective, the structural changes introduced by an attack can be used to quantify the concealment of the attack as well <cit.>.



  * Similarity Score <cit.>
(<cit.>).
Similarity score is a general metric to measure the similarity of given instance pairs. It can be used as the goal of integrity attack where the attacker’s goal is either to increase or decrease the similarity
score of a target instance pair. For a node instance in a graph, both of its local structure and node embedding can be used to compute the similarity score. 










  §.§.§ Unique Metric





  * Averaged Worst-case Margin (AWM) <cit.>.
The worst-case margin is the minimum value of the classification margin defined above. The averaged worse-case margin means the value is averaged across a worst-case margin of each batch of data. 



  * Robustness Merit (RM) <cit.>.
RM is the difference between the post-attack accuracy of the proposed method and the post-attack accuracy of the vanilla GCN model. A greater value indicates a better defense performance. 



  * Attack Deterioration (AD) <cit.>.
AD is the ratio of decreased amount of accuracy after an attack to the accuracy without attack.  



  * Average Defense Rate (ADR) <cit.>.
ADR is a metric evaluating the defense performance according to the ASR defined above. It compares the ASR after attacks with or without applying the defense approach.



  * Average Confidence Different (ACD) <cit.>.
ACD is a metric evaluating the defense performance based on the average difference between the classification margin after and before the attack of a set of nodes. Such a set of nodes includes correctly classified nodes before the attack.



  * Damage Prevention Ratio (DPR) <cit.>.
Damage prevention measures the amount of damage that can be prevented by the defense. Let L_0 be the
defender’s accumulated loss when there is no attack. Let L_A be the defender’s loss under some attack A when the defender cannot make any reliable queries. L_D denotes the
loss when the defender make reliable queries according to
a certain defense strategy D. DPR can be defined as follows:

    DPR_A^D = L_A-L_D/L_A-L_0.



  * Certified Accuracy <cit.>.
It is proposed to evaluate the certification method for robust community detection models against adversarial attacks.
The certified accuracy CK(l) is the fraction of sets of victim nodes that proposed method can provably detect as in the same community when an attacker adds or removes at most l edges in the graph.


  * Practical Effect <cit.>.
Since the attacker may target at practical effect of attacks like boosting item revenue or reputation, 
<cit.> proposed a revenue-based metric to measure the performance of attacks and defenses from a practical angle.




§ DATASET AND APPLICATION
 


Table <ref> summarizes some common datasets used in adversarial attack and defense works on graph data.
The first four citation graphs have been widely used as node classification benchmarks in previous work <cit.>.
<cit.> also studies the adversarial link prediction problem on Cora and Citeseer.
DBLP includes multiple citation datasets with more metadata information.
Thus it can be used to study the community detection task <cit.>.
Among the social network datasets, PolBlogs is another dataset used especially in adversarial settings where blogs are nodes and their cross-references are edges.
Reddit and Facebook are two larger graph datasets compared to citation datasets.
Since there are multiple versions of Facebook datasets used across different papers, we omit its statistics.
WTC 9/11, Email, Dolphin, Karate, and Football are five benchmark datasets for community detection.
Some recent works also studied attacks and defenses of recommender system <cit.> and review system <cit.> based on the Yelp and MovieLens data.
<cit.> investigated the adversarial attacks and defenses on knowledge graphs using two knowledge graph benchmarks WN18 and FB15k.
Scale-free network is a typical type of graph synthesized by graph generation models. 
Some works also employ other graph generation models like Erdős-Rényi model to generate graphs to facilitate their experiments <cit.>. 
Besides the node-level tasks, Bitcoin, AIDS, and DHFR datasets which contain multiple graphs are used to investiagte the robustness of graph classfication models <cit.>.
Among them, Bitcoin is a Bitcoin transaction dataset, 
AIDS contains biological graphs to represent the antiviral character of different biology compounds,
and DHFR contains graphs to represent the chemical bond type. 




Future Directions. 
Besides the datasets listed in Table <ref>, it is worth noting some other datasets which get less attention but could be studied in future research. To the best of our knowledge, <cit.> is the first and only paper to examine the vulnerability of Heterogeneous Information Network (HIN) which is a graph model with heterogeneous node and edge types <cit.>. Though HIN has been applied to many security applications like malicious user detection <cit.>, spam detection <cit.>, and financial fraud detection <cit.>, its robustness against adversarial attacks remain largely unexplored. A recent study <cit.> firstly gives a formulation of adversarial attacks on opinion propagation on graphs with a spectral form that could be used to study the opinion dynamics of social network. <cit.> are the first two works studying the adversarial attacks and defenses on Knowledge Graph (KG) models. As the research of KG becomes popular in recent years, its security issue needs to be noticed as well. The security of dynamic graph models <cit.> is another avenue of research as well.

Besides the above works and datasets, there has been little discussion on the security issues of many other graph types and their related applications. To name a few, the biology graph, causal graph, and bipartite graph have attracted significant research attention but few work has studied potential attacks and their countermeasures on those graphs. From the perspective of applications, as the GNNs having been successfully applied to recommender system, computer vision and natural language processing <cit.>, adversarial attacks and defenses on graph data under those specific applications is another promising research direction with de facto impacts.








§ CONCLUSION

In this work, we cover the most released papers about adversarial attack and defense on graph data as we know them today.
We first give a unified problem formulation for adversarial learning on graph data,
and give definitions and taxonomies to categorize the literature on several levels.
Next, we summarize most existing imperceptible perturbations evaluation metrics, datasets
and discuss several principles about imperceptibility metric.
Then, we analyze the contributions and limitations of existing works.
Finally, we outline promising future research directions and opportunities that may come from this effort.



§ ACKNOWLEDGEMENT

Thanks to Yixin Liu's (yila22@lehigh.edu) contributions to this work and the future maintenance of this work. This work is also supported in part by NSF under grants III-1763325, III-1909323,  III-2106758, and SaTC-1930941. 



§ OPEN-SOURCE RESOURCES


In this work, we not only develop taxonomies for all relevant works based on different criteria, but also summarize the corresponding datasets and metrics that are frequently used.
Moreover, in Table <ref>, we also provide links to the open-source implementation of popular methods.

To date, it has been a benchmark, Graph Robustness Benchmark (GRB) , that aims to provide a standardized evaluation framework for measuring adversarial attacks and defenses on the node classification task. We hope our work can facilitate the community towards the construction of benchmarks of other graph tasks.



§ COMPARISON OF EXISTING SURVEYS AND OURS
 

We conducted the first comprehensive review on graph adversarial attack and defense, and we established a unified formulation for adversarial learning on graph data, which is also utilized in the following two surveys . In contrast to our work, Jin et al.,  provide implementation details and the specified mathematical modeling of representative algorithms instead of unified formulation, and they conduct empirical studies on graph adversarial attacks. However, the survey lacks introduction to evaluation and perturbation metrics, which are significant to measure the quality of attacks and defenses on graphs. In addition, limitations of current work and future directions are not fully discussed. Although  and ours have similar structure and content, we provide clearer taxonomies and more comprehensive analysis of attack/defense methods. We also summarize specific strategies of each paper. Besides, our survey covers more papers including most recent work compared with the other two reviews.












plain



[
    < g r a p h i c s >
] Lichao Sun is currently an Assistant Professor in the Department of Computer Science and Engineering at Lehigh University. Before that, he received my Ph.D. degree in Computer Science at University of Illinois, Chicago in 2020, under the supervision of Prof. Philip S. Yu. Further before, he obtained M.S. and B.S. from University of Nebraska Lincoln. His research interests include security and privacy in deep learning and data mining. He mainly focuses on AI security and privacy, social networks, and natural language processing applications. He has published more than 45 research articles in top conferences and journals like CCS, USENIX-Security, NeurIPS, KDD, ICLR, AAAI, IJCAI, ACL, NAACL, TII, TNNLS, TMC.




[
    < g r a p h i c s >
] Yingtong Dou received the B.E. degree in IoT engineering from Beijing University of Posts and Telecommunications, Beijing, China, in 2017. He is currently pursuing the Ph.D. degree in computer science at University of Illinois at Chicago, Chicago, IL, USA.
He has published several papers in top-tier conferences including KDD, WWW, SIGIR, and CIKM. His research interest includes graph mining, fraud detection, social media analysis, and machine learning security. 




[
    < g r a p h i c s >
]Carl Yang is an Assistant Professor in Emory University. He received his Ph.D. in Computer Science at University of Illinois, Urbana-Champaign in 2020, and B.Eng. in Computer Science and Engineering at Zhejiang University in 2014. His research interests span graph data mining, applied machine learning, knowledge graphs and federated learning, with applications in recommender systems, biomedical informatics,  neuroscience and healthcare. Carl's research results have been published in top venues like TKDE, KDD, WWW, NeurIPS, ICML, ICLR, ICDE, SIGIR and ICDM. He also received the Dissertation Completion Fellowship of UIUC in 2020, the Best Paper Award of ICDM in 2020, the Dissertation award finalist of KDD in 2021, and the Best Paper Award of KDD Health Day in 2022.




[
    < g r a p h i c s >
]Kai Zhang is a Ph.D. student at Lehigh University, US. His research interests include machine learning and data mining. He recently focuses on federated learning, security & data privacy in machine learning, and Edge AI. Before joining Lehigh, he was a Reearch Assistatn at Embry-Riddle Aeronautical University working on large-scale flight dispatching for disaster evacuation with big aviation data. The system design has been featured by the Annual National Mobility Summit and the National Transportation Library. 





[
    < g r a p h i c s >
] Ji Wang received the PhD degree in information system from National University of Defense Technology, Changsha, China, in 2019. He is currently an Assistant Professor at the College of Systems Engineering, National University of Defense Technology. His research interests include deep learning and edge intelligence. He has published more than 20 research articles in refereed journals and conference proceedings such as IEEE TC, IEEE TPDS, SIGKDD, and AAAI. He was a visiting PhD student at University of Illinois at Chicago from March 2017 to September 2018 under the supervision of Prof. Philip S. Yu.




[
    < g r a p h i c s >
] Yixin Liu received his BEng degree from the Department of Software, South China University of Technology, in 2022. He is currently pursuing a Ph.D. degree in the Department of Computer Science and Engineering at Lehigh University. His research interests mainly include machine learning security, trust-worthy machine learning and adversarial learning.




[
    < g r a p h i c s >
] Philip S. Yu received the B.S. Degree in E.E. from National Taiwan University, the M.S. and Ph.D. degrees in E.E. from Stanford University, and the M.B.A. degree from New York University. He is a Distinguished Professor in Computer Science at the University of Illinois at Chicago and also holds the Wexler Chair in Information Technology.   Before joining UIC, Dr. Yu was with IBM, where he was manager of the Software Tools and Techniques department at the Watson Research Center. His research interest is on big data, including data mining, data stream, database and privacy. He has published more than 1,200 papers in refereed journals and conferences. He holds or has applied for more than 300 US patents. Dr. Yu is a Fellow of the ACM and the IEEE. Dr. Yu is the recipient of ACM SIGKDD 2016 Innovation Award for his influential research and scientific contributions on mining, fusion and anonymization of big data. 
He also received the ICDM 2013 10-year Highest-Impact Paper Award, and the EDBT Test of Time Award (2014). He was the Editor-in-Chiefs of ACM Transactions on Knowledge Discovery from Data (2011-2017) and IEEE Transactions on Knowledge and Data Engineering (2001-2004).




[
    < g r a p h i c s >
]
Lifang He is currently an Assistant Professor in the Department of Computer Science and Engineering at Lehigh University. Before her current position, Dr. He worked as a postdoctoral researcher in the Department of Biostatistics and Epidemiology at the University of Pennsylvania. Her current research interests include machine learning, data mining, tensor analysis, with major applications in biomedical data and neuroscience. She has published more than 100 papers in refereed journals and conferences, such as NIPS, ICML, KDD, CVPR, WWW, IJCAI, AAAI, TKDE, TIP and AMIA.  





[
    < g r a p h i c s >
]Bo Li is an assistant professor in the department of Computer Science at University of Illinois at Urbana–Champaign, and is a recipient of the Symantec Research Labs Fellowship, Rising Stars, MIT TR 35, and best paper awards in several machine learning and security conferences. Previously she was a postdoctoral researcher in UC Berkeley. Her research focuses on both theoretical and practical aspects of security, machine learning, privacy, game theory, and adversarial machine learning. She has designed several robust learning algorithms, a scalable framework for achieving robustness for a range of learning methods, and a privacy preserving data publishing system. Her work have been featured by major publications and media outlets such as Nature, Wired, Fortune, and IEEE Spectrum.


