Adversarial Attacks and Defenses on Graphs: A Review, A Tool and Empirical Studies

1. INTRODUCTION

• GNNs aggregate information from neighboring nodes, but adversaries can change predictions by manipulating graph structure or node features.The vulnerability raises concerns for safety-critical applications such as financial systems and risk management.Source: §1 · p. 1
• The survey categorizes graph attack methods and reviews representative algorithms.Source: §1 · p. 2
• It classifies countermeasures by defense strategy and reviews representative algorithms in each category.Source: §1 · p. 2
• The authors use a repository of algorithms to conduct empirical studies and discuss promising future research directions.Source: §1 · p. 2

2.1 Learning on Graph Data

• Graph data is represented by an adjacency matrix A and node attribute matrix X, while fθ denotes the learning model.Source: §2.1 · p. 2
• Node-level classification predicts labels for unlabeled nodes, whereas graph-level classification predicts labels for unlabeled graphs.Source: §2.1 · p. 2

2.2 A General Form of Graph Adversarial Attack

• A node-level attack seeks a perturbed graph that minimizes an attack loss within a constrained perturbation domain and budget.The objective uses a set of victim nodes and may use predicted or ground-truth labels.Source: §2.2 · p. 2
• Graph attacks require dedicated study because graph structure is discrete, nodes are interdependent, and perturbation imperceptibility is difficult to measure.Source: §2.2 · p. 2

3. TAXONOMY OF GRAPH ADVERSARIAL ATTACKS

• The taxonomy groups attacks by attacker goals, resources, knowledge, and capacity.Source: §3 · p. 2

3.1 Attacker’s Capacity

• Evasion attacks modify inputs after training, whereas poisoning attacks insert perturbations before training.Source: §3.1 · pp. 2–3

3.2 Perturbation Type

• Attackers may modify node features, add or delete edges, or inject fake nodes, while seeking to keep perturbations unnoticeable.Source: §3.2 · p. 3

3.3 Attacker’s Goal

• Targeted attacks seek misclassification of selected test nodes, directly or through influencer nodes, while untargeted attacks seek poor overall test performance.For graph-level classification, targeted attacks seek a specific label for a graph and untargeted attacks seek incorrect predictions.Source: §3.3 · p. 3

3.4 Attacker’s Knowledge

• White-box attackers know model parameters, training inputs, and labels; gray-box attackers have limited knowledge and may train a surrogate; black-box attackers use graph data and model outputs without parameters or labels.Source: §3.4 · p. 3

3.5 Victim Models

• Reportedly vulnerable models include GCN, CLN, GAT, and JKNet, as well as network embeddings, graph-based semi-supervised learning, and knowledge graph embeddings.Source: §3.5 · p. 3

4. GRAPH ADVERSARIAL ATTACKS

• The review organizes representative attacks by white-, gray-, and black-box knowledge, then by targeted or untargeted goals, and generally focuses on node-level classification.Source: §4 · p. 4, Table 2 · p. 4

4.1.1 Targeted Attack

• White-box targeted methods use model gradients or other optimization strategies to misclassify selected targets, including attacks on links, knowledge graphs, recommenders, and node classification.For node classification, integrated gradients help search discrete edge and feature perturbations; influencer nodes can also alter target predictions.Source: §4.1.1 · p. 4

4.1.2 Untargeted Attack

• White-box untargeted topology attack searches for edge flips under a perturbation budget, using PGD for fixed or retrainable GNNs; another method attacks multi-network mining by changing high-influence elements.Source: §4.1.2 · pp. 4–5

4.2 Gray-box Attacks

• Gray-box attacks train surrogate models using labeled data, then use them to generate perturbations against the victim model.Source: §4.2 · p. 5

4.2.1 Targeted Attack

• Targeted gray-box methods include Nettack, which constrains perturbations to preserve graph properties, and follow-on methods that improve scalability or target backdoors.Nettack's influencer attacks reduce performance less than direct attacks at the same budget, and Nettack does not scale to large graphs because of high time complexity.Source: §4.2.1 · p. 5

4.2.2 Untargeted Attack

• Untargeted gray-box Metattack uses meta-gradients through training to select perturbations, while NIPA sequentially injects nodes and labels to degrade overall performance.Source: §4.2.2 · pp. 5–6

4.3.1 Targeted Attack

• Black-box targeted methods include RL-S2V, which models edge modification as an MDP solved with Q-learning, and embedding attacks that can transfer across models.GF-Attack incorporates feature information, unlike the described structure-only embedding attack.Source: §4.3.1 · p. 6

4.3.2 Untargeted Attack

• Black-box untargeted ReWatt uses constrained rewiring to preserve node and edge counts, while a restricted-access method selects and perturbs only a small subset of nodes.ReWatt's rewiring affects algebraic connectivity and effective graph resistance less than adding or deleting edges.Source: §4.3.2 · p. 6

5. COUNTERMEASURES AGAINST GRAPH ADVERSARIAL ATTACKS

• Five defense families are identified: adversarial training, perturbation detection, certifiable robustness, graph purification, and attention mechanisms.Source: §5 · p. 6

5.1 Adversarial Training

• Adversarial training alternates perturbation generation to maximize prediction loss with model updates to minimize it; input-level variants face separate-input and discrete-structure challenges.Methods include edge dropout, projected gradient descent on structure, feature perturbations, and perturbations in the first hidden layer, whose continuous representations combine structure and attributes.Source: §5.1 · p. 7

5.2 Adversarial Perturbation Detection

• Test-phase adversary detection distinguishes adversarial from clean edges or nodes using link prediction, graph generation, outlier detection, or graph-aware filtering.The surveyed methods report some success detecting perturbations and can identify different anomaly-generation models and attacks.Source: §5.2 · p. 7

5.3 Certifiable Robustness

• Certification bounds worst-case margin loss to identify nodes whose predictions cannot be changed by allowed perturbations; surveyed settings include attribute and structural attacks.For node v, U(v) ≤ 0 means no allowed perturbation can make a wrong class score exceed the true-class score; approaches also use personalized PageRank, bilinear programming, randomized smoothing, sparsity, and immunization.Source: §5.3 · p. 7

5.4 Graph Purification

• Graph purification primarily targets poisoning attacks by purifying the training graph before or during robust model learning.Source: §5.4 · p. 7

5.4.1 Pre-processing

• Pre-processing removes edges with low endpoint Jaccard similarity or uses truncated SVD; the former requires node features, while pre-processing can mistakenly remove normal edges.Keeping the top 10 singular values is reported to defend against Nettack and improve GNN performance.Source: §5.4.1 · p. 8, §5.4.2 · p. 8

5.4.2 Graph Learning

• Graph-learning purification jointly learns a clean structure and robust GNN parameters by preserving low-rank, sparsity, and feature-smoothness properties.A variational graph autoencoder is also used to reconstruct graph structure and reduce perturbation effects.Source: §5.4.2 · p. 8

5.5 Attention Mechanism

• Attention-based defenses reduce adversarial influence during aggregation by assigning lower weight to suspicious nodes or edges.RGCN penalizes high-variance nodes; GNNGuard favors edges between similar nodes; another approach uses adversarial edges on similar clean graphs as supervision and meta-optimizes for a poisoned target graph.Source: §5.5 · p. 8

• DeepRobust covers seven graph datasets, five targeted attacks, three untargeted attacks, GCN as a victim model, and five defense algorithms.Source: §6 · p. 8
• Its APIs support generating attacks, training defenses on perturbed graphs, and evaluating model performance under the corresponding attacks.Source: §6 · p. 9

7.1 Experimental Setup

• The setup tests DICE, Metattack, and Topology attack against GCN and four defense methods on Cora, Citeseer, and Polblogs.Each dataset uses 10% of nodes for training, 10% for validation, and 80% for testing; experiments are repeated five times.Source: §7.1 · p. 9

7.2 Analysis on Attacked Graph

• Under Metattack, attackers favor adding edges; attacks tend to increase adjacency-matrix rank and reduce connectivity and clustering as perturbation rates rise.Table 3 covers graph properties across perturbation rates from 0% to 25%.Source: §7.2 · p. 9, Table 3 · p. 9
• Metattack tends to add edges between nodes with dissimilar features and different labels, and remove edges between nodes with similar features and the same label.The local analysis uses feature similarity and label equality for added, deleted, and unchanged edges; feature similarity is unavailable for Polblogs.Source: §7.2 · p. 9

7.3 Attack and Defense Performance

• As perturbations increase, GCN accuracy decreases, and defense methods also lose performance under heavy poisoning.The study evaluates Metattack; Table 4 reports accuracy under that attack.Source: §7.3 · p. 10, Table 4 · p. 10

8. CONCLUSION&FUTUREDIRECTIONS

• The survey’s empirical studies examine defense behavior under different attacks and changes in important graph properties.The conclusion also frames the survey as an overview of graph attacks and defenses.Source: §8 · p. 10
• ℓ0 constraints alone do not adequately measure imperceptibility, and few studies address concise perturbation evaluation measures.The authors identify finding such a measure as an urgent research direction.Source: §8 · p. 10
• Existing work mainly studies static graphs with node attributes; graphs with edge attributes and dynamic graphs remain under-studied.Source: §8 · p. 10
• Only a few works discuss whether graph adversarial examples exist and whether they transfer.The authors connect studying these questions with understanding graph-learning algorithms and building robust models.Source: §8 · p. 10
• High attack-method complexity hinders practical use, while efficient time and memory complexity remain challenges.The authors note that few works develop time-efficient attacks and that most attack algorithms are gradient-based.Source: §8 · p. 10

A.1 Global Measures for Topology Attack and DICE

• Table 5 presents properties of attacked graphs under Topology attack; the appendix also identifies Table 6 as the global-measures table for DICE.Source: §A.1 · p. 14, Table 5 · p. 14

A.2 Local Measures for Topology Attack and DICE

• Figures 4–7 cover node feature similarity and label equality for Topology and DICE attacks.Figure 4 is specifically identified as node feature similarity for Topology attack.Source: §A.2 · p. 14, Figure 4 · p. 14
• The local measures compare feature similarity and label equality across newly added, deleted, and unchanged edges.Source: §A.2 · p. 14
• Table 6 presents properties of attacked graphs under DICE attack.Source: Table 6 · p. 14

B. OPEN SOURCE CODE

• Figures 5 and 7 show node feature similarity and label equality, respectively, for DICE attack; Figure 6 shows label equality for Topology attack.Source: Figure 5 · p. 14, Figure 7 · p. 15, Figure 6 · p. 15

A.3 AttackandDefensePerformance forTopology Attack and DICE

• Table 7 reports accuracy under Topology attack, while Table 8 reports accuracy under DICE attack.Source: Table 7 · p. 15, Table 8 · p. 15

B. OPEN SOURCE CODE

• Table 9 summarizes open-source implementations, including GCN-Jaccard and GCN-SVD defense models.Source: B. OPEN SOURCE CODE · p. 15, Table 9 · p. 16