PaperlayerView exact revision on arXiv

Source-linked AI summary

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

arXiv:1812.10528v4cs.CRcs.AIcs.SI

TL;DR

Graph adversarial-learning research lacks a unified way to compare studies because existing works use specific assumptions and separate mathematical formulations. This survey synthesizes more than 100 papers through unified formulations, taxonomies, datasets, metrics, and a maintained repository. It summarizes current contributions, limitations, and future directions for graph attacks and defenses.

  • Problem

    Existing graph adversarial-learning studies use specific attack assumptions and distinct mathematical formulations, making relationships and comparisons among methods difficult.

  • Method

    The survey unifies graph adversarial-learning formulations, organizes attacks and defenses into taxonomies, and summarizes metrics, datasets, contributions, limitations, and future directions.

  • Results

    The review provides a comprehensive landscape of more than 100 graph adversarial attack and defense papers and analyzes their approaches, evaluation practices, and open challenges.

  • Takeaways & Limitations

    The unified framework and collected resources provide a basis for understanding existing graph adversarial-learning models and developing future benchmarks and research.

  • Takeaways & Limitations

    Graph adversarial research remains limited for attributed and heterogeneous graphs, graph-level attacks, inductive node-level attacks, and comprehensive imperceptibility metrics.

Abstract

from arXiv · show

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.

1 INTRODUCTION

Graph adversarial learning is difficult to compare and analyze because graph structure is discrete and varies across tasks, while existing studies use differing assumptions and formulations. This survey organizes the literature, unifies attack models, and compiles datasets and metrics to support systematic understanding and future benchmarking.

  • Motivation: Graph data poses distinctive adversarial-analysis challenges because its discrete structure makes subtle or imperceptible perturbations difficult to define.The survey contrasts graph data with image, language, and speech domains and highlights the need for further measurement and investigation.
  • Survey scope: The survey covers more than 100 papers and provides a taxonomy organized around GNN and Non-GNN methods.Relevant works are listed according to tasks, strategies, baselines, evaluation metrics, and datasets.
  • Research resources: An open-source repository tracks relevant papers and corresponding code, providing a maintained resource for following developments in the field.The repository is intended to make research easier to use and track, although many listed works are preprints or reports.
  • Research gap: Existing graph adversarial studies often target specific attacks under particular assumptions and use incompatible mathematical formulations, hindering comparison.The survey addresses this lack of a common basis for understanding relationships and properties across models.
  • Unified framework: It introduces a unified formulation and definition for systematically analyzing graph adversarial attack models, while categorizing defenses by their distinct strategies.The defense categories extend beyond adversarial learning because graph defenses frequently use additional strategies.
  • Evaluation resources: The review summarizes commonly used datasets and metrics because differing goals and data make results across studies difficult to compare.It identifies benchmarking as a needed direction for practical model selection and future research.

2 GRAPH

This section introduces graph-data representations, learning settings, and application levels used throughout the survey. It distinguishes graph types and tasks while emphasizing the survey’s focus on supervised learning.

  • Types of Graph Data: Attributed graphs attach features to nodes, edges, or both, including weights and application-specific information.Examples include user demographics on nodes and road conditions as edge weights.
  • Types of Graph Data: Graph data may be static or dynamic, depending on whether nodes, edges, or their attributes change over time.Molecular structures exemplify static graphs, whereas social networks exemplify dynamic graphs.
  • Types of Graph Data: Graphs can be directed or undirected, depending on whether edges encode one-way or reciprocal relationships.Facebook illustrates an undirected graph, while Twitter illustrates a directed graph.
  • Learning Settings: Inductive learning predicts labels for unseen examples, whereas transductive learning predicts labels for instances from graphs seen during training.The survey mainly focuses on supervised learning and also introduces selected unsupervised works.
  • Applications: Graph applications operate at node, link, or graph level, covering tasks such as node classification, link prediction, and molecular graph analysis.Most existing adversarial studies focus on transductive node classification, while graph-level tasks appear in chemistry and medicine.

3 ADVERSARIAL ATTACKS ON GRAPH DATA

The survey defines graph adversarial attacks as minimally modifying graphs to degrade task performance, then proposes a unified formulation spanning different tasks and attack settings. It also notes that graph similarity and perturbation costs remain difficult to compare consistently.

  • Unified Definition: Graph adversarial attacks modify a graph slightly while requiring similarity to the original and substantially worsening graph-task performance.The definition applies to datasets containing target components, graphs, and labels.
  • Unified Definition: Existing studies often address specific attack types under different assumptions and mathematical formulations, making cross-method comparison difficult.The survey motivates a unified formulation to relate these problems systematically.
  • Unified Formulation: The unified formulation accommodates learning functions for link prediction, node- and graph-level embedding, and node- and graph-level classification.It represents attacked instances using perturbed graphs drawn from a perturbation space.
  • Unified Formulation: The formulation covers node manipulation, edge manipulation, or both, subject to a graph-distance function and a per-sample cost budget.The distance function measures similarity between the benign and adversarial graphs.
  • Graph Distance: Perturbation evaluation depends on the learning task, attack strategy, and adversarial cost type, so different graph distances may identify different optimal targets.The survey highlights this dependence as a challenge for comparing attacks.

3.2 Adversarial Perturbation

Graph adversarial perturbations can target edges, nodes, structure, or attributes, while imperceptibility must be evaluated relative to graph type and application task. The survey proposes principles for setting perturbation costs but notes that GNN representations remain vulnerable to multiple perturbation modes.

  • Perturbation Evaluation: Adversarial samples modify nodes or edges while remaining similar and imperceptible under task-appropriate perturbation metrics.The suitable similarity measure differs between node-level and graph-level tasks.
  • Perturbation Types: Edge-level perturbation adds, removes, or rewires edges within a budget, commonly measured by the number of modified edges.Such changes may be difficult for defenders to detect, particularly in dynamic graphs.
  • Perturbation Types: Node-level perturbation changes nodes or their features, with magnitude measured by modified-node counts or feature-vector distance.This category includes adding or removing nodes and manipulating target-node features.
  • Perturbation Types: Structure-preserving perturbation constrains graph changes using properties such as degree distributions and node distributions.It extends ordinary edge perturbation with explicit structural preservation requirements.
  • Perturbation Types: Attribute-preserving perturbation changes node or edge features and evaluates magnitude using graph-attribute properties.GNN representations can be attacked through structure-only, feature-only, or combined perturbations.
  • Evaluation Principles: For static graphs, perturbation costs should keep modified-edge counts and feature-vector distances small, whereas dynamic-graph costs can reflect intrinsic temporal changes.Statistical analysis may provide an upper bound for permissible manipulation in dynamic graphs.

3.3 Attack Stage

Graph attacks differ by when perturbations occur and what they target. The survey distinguishes poisoning from evasion attacks, and model-objective attacks from data-objective attacks, including gradient, reinforcement-learning, generative, poisoning, and statistic-based approaches.

  • Attack Stage: Poisoning attacks insert adversarial samples into training data, after which the model is retrained.Most existing works study poisoning attacks for transductive node classification.
  • Attack Stage: Evasion attacks alter testing data while keeping trained-model parameters fixed, so retraining is unnecessary.The unified formulation represents this setting by retaining the original training graph.
  • Attack Objective: Model-objective attacks target a particular learning model, whereas data-objective attacks operate without sufficient information about the model.Data-objective attacks arise when the attacker has access to data but not the model.
  • Model Objective: Gradient-based attacks use or estimate gradients to identify important information for modification and degrade model accuracy.The surveyed literature describes this strategy as common and effective across white-box and black-box settings.
  • Model Objective: Non-gradient-based attacks can rely on reinforcement-learning rewards or generative models to construct adversarial samples.These methods attack models without gradient information.
  • Data Objective: Data-objective attacks include model poisoning through dataset signals and statistic-based attacks that exploit graph information to disrupt analyses.One example modifies a few inter-community edges to make community counting inaccurate.

3.5 Attack Knowledge

Graph attacks are characterized by the information available to the attacker and the attacker's objective. The survey also maps a unified attack formulation across node-, link-, and graph-relevant tasks.

  • Attack Knowledge: Attack knowledge ranges from white-box access to grey-box partial information and black-box queries, with black-box attacks potentially most dangerous if successful.Most existing graph attack studies focus on white-box settings, leaving other knowledge levels relatively underexplored.
  • Attack Goal: Availability attacks reduce overall system performance, whereas integrity attacks target selected instances while preserving similar total performance.Availability attacks are generally studied under evasion settings because positioning attacks make them easier to detect.
  • Task Scope: The unified formulation represents node-relevant attacks by setting c_i to the target-node representation.Node classification and node embedding are the principal node-level task examples discussed.
  • Task Scope: For link-relevant attacks, c_i represents a node-pair target and y_i ∈ [0, 1] supports the link-prediction formulation.The formulation applies to link prediction based on node embedding or topological similarity.
  • Task Scope: For graph-relevant attacks, c_i is set to the representation of the target graph rather than an individual node.Graph classification requires graph representations as input.

3.8 Summary: Attack on Graph

The survey organizes graph attack research, distinguishes high-level strategies from concrete perturbation approaches, and identifies broad methodological coverage alongside persistent limitations and future opportunities.

  • Contributions: The survey lists released papers and categorizes them into main topics, while distinguishing an attack's strategy from its concrete perturbation approach.Strategy denotes high-level design philosophy; approach denotes the concrete way graph data are perturbed.
  • Graph Neural Networks: GNN attack research spans reinforcement learning, optimization, gradient-based methods, spectral approximations, edge or node modifications, and hybrid feature perturbations.The surveyed works address node classification, link prediction, attributed graphs, and multiple model classes.
  • Others: Non-GNN graph attacks include unsupervised attacks, heuristic community-detection attacks, theoretical analyses, and applications in recommendation, fraud detection, opinion dynamics, and graph classification.The survey notes growing attention to theoretical work and diverse application settings.
  • Limitations: Most current studies lack clear real-world justification for attack budgets and distances, and often evaluate imperceptibility with only one metric.The survey argues that adversarial samples may evade one imperceptibility metric yet be detected by others.
  • Future Directions: Future work should address attributed and complex graphs, underexplored learning settings, multiple imperceptibility metrics, and better distance or similarity measures.The listed directions include graph-level attacks and inductive node-level attacks.

4 ADVERSARIAL DEFENSE ON GRAPH DATA

The survey classifies graph defenses into adversarial training, attack detection, and other modification-based methods. It also highlights robustness certification, complex-graph settings, and major gaps in task and model coverage.

  • Defense Taxonomy: Graph defenses are organized into adversarial training, attack detection, and other methods that fit neither generic category.The survey summarizes the defense literature and lists works in a time-ascending table.
  • Adversarial Training: Adversarial training alternates an attacker maximizing task loss through graph perturbations with a defender minimizing that loss through robust model parameters.The objective is to train models resistant to future adversarial attacks.
  • Adversarial Training: Training defenses perturb structure, attributes, or attack-specific examples, with reported applications to node classification, graph classification, community detection, and mixed attacks.Examples include random edge dropping, projected-gradient topology attacks, virtual adversarial training, and attack-oriented pipelines.
  • Attack Detection: Detection-based defenses identify or down-weight suspicious edges, nodes, or training data after assuming the graph has already been polluted.Methods use graph generation, link prediction, outlier detection, graph-aware criteria, attention, or embedding uncertainty.
  • Robustness Certification: Robustness certificates quantify individual-node safety under structural or attribute perturbations and can provide rigorous guarantees for more nodes when jointly trained.Certification is presented as an alternative to directly detecting attacks.
  • Other Methods: Other defenses modify graph data, models, or both through low-rank approximation, redesigned operators or losses, edge dithering, and jointly learned clean structures.These methods cover homogeneous and attributed graphs and include non-GNN alternatives such as SVM-based classification.
  • Limitations and Future Directions: Defense research remains concentrated on node-level GNN tasks, with limited coverage of link- and graph-level tasks, dynamic or content-rich networks, and non-GNN models.The survey identifies graph search, recommendation, advertisement, and other real-world tasks as additional opportunities.

5 METRICS

The survey organizes graph adversarial-learning evaluation around general task metrics, graph-property metrics, and attack- or defense-specific measures. These metrics quantify classification, ranking, structural change, attack effectiveness, perturbation cost, and defense performance.

  • General Metrics: Accuracy, Recall, Precision, and F1 measure node-classification accuracy, while FNR and FPR quantify missed positives and misclassified negatives.
  • General Metrics: AUC and AP evaluate ranked classification outputs, with AUC reflecting positive-instance probability ordering and AP balancing Precision and Recall.
  • Graph-Based Metrics: MRR and Hits@K evaluate knowledge-graph link-prediction rankings, while NMI and Modularity evaluate community-detection performance.
  • Graph-Based Metrics: Graph-property statistics such as Gini Coefficient, Characteristic Path Length, Distribution Entropy, Power Law Exponent, and Triangle Count quantify attack-induced structural changes.
  • Attack Metrics: ASR, Concealment Measures, Similarity Score, Classification Margin, and Correct/Mis Classification Rate measure attack outcomes across different objectives and instances.
  • Attack Metrics: Attacker Budget measures the minimum perturbations needed to achieve an objective, whereas AML reports the average number of modified links required.
  • Defense Metrics: RM, AD, ADR, ACD, DPR, and Certified Accuracy quantify defense performance through post-attack accuracy, deterioration, attack success, margins, prevented damage, or provable robustness.

6 DATASET AND APPLICATION

The survey reviews datasets used across graph tasks and identifies underexplored graph types and applications. It also records open-source algorithm implementations to support research use and comparison.

  • Datasets: Citation graphs support node classification, Cora and Citeseer also support adversarial link prediction, and DBLP supports community detection.
  • Datasets: PolBlogs is used in adversarial social-network settings, while biology-compound datasets represent chemical-bond graphs.
  • Future Applications: Heterogeneous information networks, opinion-propagation graphs, knowledge graphs, and dynamic graphs remain relatively limited areas for adversarial attack and defense research.
  • Future Applications: Biology, causal, and bipartite graphs have received little study of security issues, and graph applications in recommender systems, computer vision, and natural language processing remain promising directions.
  • Resources: Table 6 summarizes open-source implementations of algorithms, complementing the survey’s dataset and literature overview.

7 CONCLUSION

The survey unifies and organizes research on adversarial attack and defense for graph data. It covers formulations, taxonomies, metrics, datasets, limitations, implementations, and future directions.

  • The review gives a unified formulation and taxonomies for adversarial learning on graph data while covering the released literature known to the authors.
  • It summarizes imperceptible-perturbation metrics and datasets, discusses principles of imperceptibility measurement, and analyzes existing contributions and limitations.
  • The survey concludes by outlining promising future research directions and opportunities emerging from graph adversarial learning.

APPENDIX A OPEN-SOURCE RESOURCES

The survey summarizes commonly used datasets and metrics, links open-source implementations, and notes the Graph Robustness Benchmark’s node-classification focus.

  • The survey summarizes datasets and metrics frequently used in graph adversarial attack and defense studies.
  • Table 6 provides links to open-source implementations of popular methods.
  • The Graph Robustness Benchmark provides a standardized evaluation framework for measuring attacks and defenses on node classification.

APPENDIX B COMPARISON OF EXISTING SURVEYS AND OURS

The survey presents a unified formulation for graph adversarial learning and distinguishes its contribution from another survey’s implementation details and empirical studies.

  • The survey established a unified formulation for adversarial learning on graph data and was the first comprehensive review of graph adversarial attack and defense.
  • Jin et al. provide implementation details and specified mathematical modeling of representative algorithms, together with empirical studies on graph adversarial attacks.
  • Compared with this survey, Jin et al.’s survey lacks the unified formulation presented here.
Loading 1812.10528v4…