PaperlayerView exact revision on arXiv

Source-linked AI summary

A Survey of Adversarial Learning on Graphs

Liang Chen, Jintang Li, Jiaying Peng, Tao Xie, Zengxu Cao, Kun Xu, Xiangnan He, Zibin Zheng, Bingzhe Wu

arXiv:2003.05730v3cs.LGcs.AIstat.ML

TL;DR

Graph adversarial-learning research lacks unified problem definitions and a comprehensive review despite the vulnerability of graph models to adversarial examples. This survey synthesizes attack and defense work, definitions, taxonomies, and evaluation metrics, and identifies limitations and open questions. It concludes that the field has an arms race between attackers and defenders and that current methods have unresolved limitations.

  • Problem

    Graph adversarial-learning studies lack unified problem definitions and a comprehensive review, despite graph models' vulnerability to adversarial examples.

    Source: §1 · pp. 1–2

  • Method

    The survey reviews graph attacks and defenses, unifies their formulations and definitions, develops taxonomies, and summarizes evaluation metrics.

    Source: §1 · p. 2

  • Results

    The survey synthesizes the arms race between attackers and defenders and summarizes current methods' contributions, limitations, and open problems.

    Source: §7 · p. 14

  • Takeaways & Limitations

    The survey provides a structured overview of graph adversarial learning and identifies open problems for further study.

    Source: §7 · p. 14

    Existing attack works often neglect noticeable impacts, and many focus on relatively small graphs rather than million-scale graphs.

    Source: §3.3.2 · p. 8

Abstract

from arXiv · show

Deep learning models on graphs have achieved remarkable performance in various graph analysis tasks, e.g., node classification, link prediction, and graph clustering. However, they expose uncertainty and unreliability against the well-designed inputs, i.e., adversarial examples. Accordingly, a line of studies has emerged for both attack and defense addressed in different graph analysis tasks, leading to the arms race in graph adversarial learning. Despite the booming works, there still lacks a unified problem definition and a comprehensive review. To bridge this gap, we investigate and summarize the existing works on graph adversarial learning tasks systemically. Specifically, we survey and unify the existing works w.r.t. attack and defense in graph analysis tasks, and give appropriate definitions and taxonomies at the same time. Besides, we emphasize the importance of related evaluation metrics, investigate and summarize them comprehensively. Hopefully, our works can provide a comprehensive overview and offer insights for the relevant researchers. Latest advances in graph adversarial learning are summarized in our GitHub repository https://github.com/EdisonLeeeee/Graph-Adversarial-Learning.

1 INTRODUCTION

Graph-learning models are vulnerable to small perturbations that can misclassify targets, while studies of graph attacks and defenses lack unified formulations and comprehensive review. This survey organizes the field, standardizes its definitions and taxonomies, reviews evaluation metrics, and identifies limitations and open questions.

1 INTRODUCTION

  • Small changes to graph structure and node features can lead graph-learning models to misclassify target nodes.In the described node-classification setting, attackers may add or remove edges involving fake nodes.Source: §1 · p. 1, Figure 1 · p. 1
  • Existing graph adversarial-learning studies use inconsistent formulations, while evaluation metrics vary across tasks and lack common standards.The survey highlights the need for scenario-specific measures, including metrics for attack impact.Source: §1 · p. 2
  • The survey unifies problem formulations and definitions for graph attacks and defenses, and classifies existing work using systematic criteria.It also organizes attack and defense works into taxonomies.Source: §1 · p. 2
  • The survey reviews evaluation metrics and identifies current limitations and open questions in graph adversarial learning.It describes these as part of its effort to provide a comprehensive overview of the area.Source: §1 · p. 2

2 PRELIMINARY

The preliminary section establishes graph notation, graph-type categories, and the node-, link-, and graph-level tasks used to frame the survey. It also notes that prior work often simplifies settings to static, homogeneous, unweighted, undirected graphs.

2.1 Notations

  • The section introduces typical graph notations and identifies frequently used symbols in a notation table.A graph is represented as G = (V, E), with nodes V and edges E.Source: §2 · p. 2, §2.1 · p. 2, Table 1 · p. 3

2.2 Taxonomies of Graphs

  • The survey distinguishes directed, weighted, attributed, heterogeneous, and dynamic graphs from their respective alternatives.It notes that many existing studies simplify to static, homogeneous, undirected, unweighted graphs, which this paper calls simple graphs.Source: §2.2 · p. 2

2.3 Graph Analysis Tasks

  • Graph analysis tasks are grouped into node-, link-, and graph-level tasks, with classification and prediction objectives specified for each level.Node classification predicts labels for unlabeled nodes; link prediction predicts whether an edge exists; graph classification assigns categories to graphs.Source: §2.3 · pp. 2–3
  • Node classification maps nodes to predefined labels and can use inductive or transductive training and testing settings.In the inductive setting, test nodes are unseen during training; in the transductive setting, unlabeled test nodes are visible during training.Source: §2.3 · p. 3

3 ADVERSARIAL ATTACK

The section introduces graph adversarial attacks, then presents attack-model categories and an overview of existing work.

3 ADVERSARIAL ATTACK

  • The section is organized around defining graph adversarial attacks, categorizing attack models, and surveying existing work.The passage previews these tasks without specifying the categories or individual studies.Source: §3 · p. 3

3.1 Definition

The survey formulates graph attacks as maximizing loss on selected target instances. It also describes constraints on the target set and perturbations intended to keep changes imperceptible.

3.1 Definition

  • An attacker seeks to maximize the target-instance loss of a graph-learning model, degrading prediction performance.Targets are instances without labels in the relevant node, edge, or graph set.Source: §3.1 · p. 3
  • The formulation restricts attack targets to the test set.The passage explicitly states that attackers focus on test-set target instances.Source: §3.1 · p. 3
  • The formulation constrains perturbations through graph similarity, requiring the comparison to remain within an allowed threshold.Q denotes the similarity function and ϵ the allowed threshold of changes.Source: §3.1 · p. 4

3.2 Taxonomies of Attacks

The survey classifies graph attacks across attacker knowledge, goals, capabilities, strategies, manipulations, algorithms, and target tasks, providing definitions and instructions for these scenarios.

3.2 Taxonomies of Attacks

  • The taxonomy distinguishes attacker knowledge, attack goals, capabilities, graph manipulations, algorithms, and target tasks.It organizes these perspectives for different attack scenarios.Source: §3.2 · p. 4

3.2.1 Attacker’s Knowledge

  • White-box, gray-box, and black-box attacks differ in access to target-model information, while dataset knowledge ranges from perfect to minimal.No-box attacks use a surrogate model and are treated as gray- or black-box attacks; successful transfer from the surrogate can make them white-box in effect.Source: §3.2.1 · p. 4

3.2.2 Attacker’s Goal

  • Attack goals distinguish security violation, attack specificity, and error specificity; targetedness concerns attack range, while error specificity concerns the prediction consequence.Security violation includes availability and integrity attacks, among other goals.Source: §3.2.2 · pp. 4–5

3.2.3 Attacker’s Capability

  • Poisoning modifies training data and retrains the target model, whereas evasion adds adversarial examples at test time with model parameters fixed.The survey notes that poisoning often does not work well because retraining alleviates adversarial impacts.Source: §3.2.3 · p. 5

3.2.4 Attack Strategy

  • Attack strategies target graph topology, node or edge features, or both, and may also inject fake nodes with features and relationships.Feature attacks may modify binary or continuous features, while adding fake nodes can change graph dimensions.Source: §3.2.4 · p. 5

3.2.5 Attacker’s Manipulation

  • Manipulations include adding or removing edges or features and rewiring, which combines operations and can preserve graph properties such as degree.The survey represents these operations as O = {OAdd, ORem, ORew}.Source: §3.2.5 · pp. 5–6

3.2.6 Attack Algorithm

  • Gradient-based algorithms select graph inputs to perturb using loss gradients, while alternatives include genetic algorithms, reinforcement learning, and generative models.Because graph data are discrete, attacks typically use gradient magnitudes to choose a perturbation rather than applying gradients directly.Source: §3.2.6 · p. 6

3.2.7 Target Task

  • Attacks target node-relevant tasks, link-relevant tasks such as link prediction, and graph-relevant tasks such as graph classification or clustering.The survey reports more attack work on node classification than on graph-level tasks.Source: §3.2.7 · p. 6

3.3 Summary: Attack on Graph

The survey reviews attack methods across graph-analysis tasks and identifies limitations involving noticeability, scale, attacker knowledge, and physical settings.

3.3 Summary: Attack on Graph

  • Table 2 summarizes released attack papers and their characteristics.The survey’s review covers attacks on node-, link-, and graph-relevant tasks, including methods and applications across these categories.Source: §3.3 · p. 6, §3.3.1 · pp. 6, 8, Table 2 · p. 7

3.3.1 Major Contributions

  • Reviewed methods span node, link, and graph tasks, with node classification prominent and approaches including gradients, heuristic search, reinforcement learning, and genetic algorithms.The survey also describes attacks on link prediction and graph classification, clustering, and community detection.Source: §3.3.1 · pp. 6, 8

3.3.2 Current Limitations

  • The survey identifies limits in preserving unnoticeability, scaling attacks to million-scale graphs, studying moderate or minimal attacker knowledge, and handling physical-world distortions.It notes that low attack budgets alone are insufficient for unnoticeability, and physical distortions often prevent desired results.Source: §3.3.2 · p. 8

4 DEFENSE

The survey defines graph defense as maintaining model performance on maliciously disturbed data, then classifies defense methods and reviews their contributions and limitations.

4.1 Definition

  • Defense aims to keep model performance stable on maliciously disturbed data, using a defense loss and a model that accepts perturbed or clean graphs.Source: §4.1 · p. 8

4.2 Taxonomies of Defenses

  • Defenses are grouped as preprocessing-, structure-, adversarial-, objective-, detection-, or hybrid-based; hybrid methods combine types, while detection monitors or certifies security rather than directly improving robustness.Source: §4.2 · pp. 8–9

4.3 Summary: Defense on Graph

  • The defense review summarizes contributions, limitations, and research opportunities, with detailed method comparisons placed in Table 3.Source: §4.3 · p. 9, Table 3 · p. 10

4.3.1 Major Contributions

  • The review organizes defense contributions into adversarial learning, model improvement, and other robustness work such as certification, detection, and edge dithering.Source: §4.3.1 · pp. 9, 11

4.3.2 Current Limitations

  • Defense research is limited by node-classification concentration, little attention to training cost, and reliance largely on experiments and textual descriptions rather than theoretical proof.Source: §4.3.2 · p. 11

5 METRICS

The survey organizes graph adversarial-learning metrics into common graph-task measures and measures specific to attacks and defenses, covering effectiveness, efficiency, and imperceptibility.

5 METRICS

  • Specific attack-and-defense metrics complement common task measures and are grouped by effectiveness, efficiency, and imperceptibility.Source: §5 · p. 11, §5.2 · p. 12

5.1 Common Metrics

  • AP summarizes the precision-recall curve; MRR scores the rank of the first correct item, while Hits@K measures correct entities in the top K.Source: §5.1 · p. 12
  • Modularity and NMI assess clustering or community structure, with NMI reflecting similarity between partitions.Source: §5.1 · p. 12
  • Common measures include ARI for clustering similarity, accuracy for correct predictions, AUC for positive-negative ranking, and F1 as a precision-recall harmonic average.Source: §5.1 · pp. 11–12

5.2.1 Effectiveness-relevant Metrics

  • Effectiveness measures include ASR within a fixed attack budget, ADR for defense improvement, ACD for confidence changes, and DPR for prevented loss.Source: §5.2.1 · p. 12
  • Classification-margin measures target misclassification distance; RM compares post-attack with pre-attack accuracy, while attack deterioration captures prediction impacts.Source: §5.2.1 · p. 12

5.2.2 Efficiency-relevant Metrics

  • AML measures the average topology perturbation size needed for a successful attack, under a limited modification budget.Source: §5.2.2 · p. 13

5.2.3 Imperceptibility-relevant Metrics

  • Imperceptibility measures include link similarity, degree-distribution test statistics and attack budgets, as well as community-detection attack effect.Source: §5.2.3 · p. 13

6 OPEN PROBLEMS

The survey identifies open problems in attacks, defenses, and evaluation, emphasizing practical constraints and gaps in current methods and measures.

6.1 Attack

  • Attacks should preserve graph properties to remain unnoticeable, since most existing work does not enforce such constraints despite strong performance.Source: §6.1 · p. 13
  • Many attacks rely on storing whole-graph information and struggle to scale; subgraph-based methods are proposed as a route to lower time and space costs.Source: §6.1 · p. 13
  • Practical black-box attacks need limited model and data knowledge, but many methods assume full input knowledge; transfer from substitute models is a proposed direction.Source: §6.1 · pp. 13–14
  • Attacks also need evaluation beyond simple static graphs, which the survey describes as an unrealistic real-world assumption.Source: §6.1 · p. 14

6.2 Defense

  • Defense research is concentrated on node classification, leaving link prediction and other graph tasks comparatively underexplored.Source: §6.2 · p. 14
  • Defense methods need acceptable training costs and large-scale evaluation; existing efficiency discussions and experiments often use small graphs.Source: §6.2 · p. 14
  • Empirical robustness can vary with hyperparameters, implementation, initialization, and hardware, while certification can establish node robustness under arbitrary perturbations.Source: §6.2 · p. 14

6.3 Evaluation Metric

  • Evaluation needs better cost measures that distinguish edge additions from removals, better-defined imperceptibility measures, and guidance for selecting metrics by scenario.Source: §6.3 · p. 14

7 CONCLUSION

The survey reviews graph adversarial attacks, defenses, and evaluation metrics, offering unified formulations, taxonomies, and discussion of current limitations and open problems.

7 CONCLUSION

  • The survey covers attacks, defenses, and their evaluation metrics, and presents a taxonomy and unified problem formulation for the field.Source: §7 · p. 14
  • It discusses the major contributions and limitations of current attack and defense methods and identifies open problems for future study.Source: §7 · p. 14
  • The authors state that future work will measure proposed models using relevant metrics in extensive empirical studies.Source: §7 · p. 14

Related papers

Loading 2003.05730v3…