Topological Attacks and Defenses on Graph Neural Networks: An Optimization Perspective
Topology Attack and Defense for Graph Neural Networks: An Optimization Perspective
The authors propose convex-relaxation-based GNN topology attacks (PGD and min-max) and adversarial training; on Cora/Citeseer under 5% edge perturbation, the misclassification rate is better than DICE, Greedy, and Meta-Self.
The attacker misleads GNN node classification by adding or deleting edges (edge perturbation, which the paper calls topology attack), with a perturbation budget of 5% of the number of existing edges in the original graph (up to 20% in some experiments). Two scenarios: a) attacking a pre-defined GNN with known weight W; b) attacking an interactive GNN whose W can be retrained. The paper focuses on untargeted attack, and the victim system is GCN.
- GNNs perform well on semi-supervised node classification, but research on adversarial robustness against discrete graph structures is scarce; first-order continuous optimization methods are difficult to apply directly to topology attacks that add or delete edges.
- Convexly relax the Boolean edge perturbation variable to [0,1], use PGD and min-max alternating optimization to generate topology attacks, then restore to a binary perturbation via random sampling; and based on this construct min-max adversarial training to improve GCN robustness.
- On Cora/Citeseer, under 5% edge perturbation, CE-PGD/CW-PGD have higher misclassification rates against natural GCN than DICE, Greedy, and Meta-Self; adversarial training with ε=5% reduces the CE-PGD attack misclassification rate on Cora from 28.0% to 22.0%, with the original graph accuracy essentially unchanged.
- The paper does not specifically discuss limitations. The experiments cover only GCN and the two datasets Cora and Citeseer, the evaluation metric is the test-node misclassification rate, and each setting is repeated 5 times; attack runtime and comparison with the query cost of adversarial training in the image domain are not reported.
- Evaluated models
- GCN
- Benchmarks
- CoraCiteseer
- Metrics
- misclassification rate (1 − prediction accuracy)attack loss (CE-type / CW-type)
The researchers propose a gradient-optimization-based topological attack method on graph neural networks; compared with existing GNN adversarial attacks, it requires only a small number of edge additions or deletions to significantly degrade semi-supervised node classification performance. The authors state that this is the first optimization-based GNN adversarial training method, with higher robustness against both gradient-based and greedy attacks, without sacrificing classification accuracy on the original graph.
Paper analysis
What problem does this paper attempt to solve?
Addresses the problem that discrete graph structure makes first-order adversarial attacks difficult to apply directly to GNNs, and provides attack and adversarial training methods.
Core problem: how to generate first-order optimization-based topology attacks (adding/deleting edges) against graph neural networks (GNNs), and on this basis improve the adversarial robustness of GNNs.
- Scenario and importance: GNNs perform prominently on semi-supervised node classification and are used in security-related fields such as blockchain and communication networks, but the authors state that research on the adversarial robustness of GNNs is scarce.
- Shortcomings of existing methods: The authors state that recent work points out that traditional first-order continuous optimization methods cannot be directly used for edge manipulation (topology attack) due to the discreteness of graphs; existing attacks are mostly greedy search or methods based on surrogate models or meta-gradients.
- Core observation: After relaxing the Boolean edge perturbation variable to its convex hull [0,1], first-order methods such as PGD can be used to solve the continuous attack problem, which is then restored to a binary perturbation via random sampling.
- What the paper proposes: two topology attacks (PGD topology attack, min-max topology attack) and what the authors call the first optimization-based adversarial training method for GNNs.
- Threat model:
- Goal: mislead GNN node classification by adding or deleting edges; the paper focuses on untargeted attack (an extension to targeted is also given).
- Knowledge: scenario a attacks a pre-defined GNN with known weight W; scenario b attacks an interactive GNN whose W can be retrained.
- Capability: can only modify edges (add/delete), with a perturbation budget of 5% of the number of existing edges (up to 20% in some experiments).
- Victim system: GCN, performing semi-supervised node classification on Cora and Citeseer.
What related research exists?
Related work includes graph adversarial attacks (Dai, Zügner et al.) and first-order attacks and adversarial training in the image domain (CW, Madry); the authors position the difference in terms of convex-relaxation first-order methods.
Adversarial attacks on graph data
- Dai et al. (2018): study test-time non-targeted attacks, allowing only edge addition and deletion, covering white-box, practical black-box, and restricted black-box scenarios, targeting graph classification and node classification.
- Zügner et al. (2018): study test-time (evasion) and training-time (data poisoning) attacks, which can also modify node attributes in addition to adding and deleting edges; design attacks based on a static surrogate model, targeting a single node as a targeted attack.
- Bojcheski and Günnemann (2018): data poisoning attacks against unsupervised node embeddings (DeepWalk), maximizing the loss based on perturbation theory.
- Zügner and Günnemann (2019): training-time attacks, treating the graph topology as a hyperparameter and solving a min-max problem with meta-gradients; their Meta-Self attack is the state-of-the-art compared against in this paper in the retrained model scenario.
First-order attacks and robust training in the image/audio domain
- Carlini and Wagner (2017): the CW attack; this paper draws on its CW-type attack loss and the constraint form of targeted attack.
- Madry et al. (2017): min-max adversarial training for image classifiers; this paper's robust training follows this form and draws on its practice of increasing model capacity (hidden units 16→32).
Baselines and benchmarks: the attacks are compared with DICE (Waniek et al., 2018), Greedy attack (a variant of Meta-Self with weight retraining removed), and Meta-Self; the benchmarks are Cora and Citeseer node classification.
Positioning: the authors state that existing work points out that first-order continuous optimization is not applicable to discrete edge attacks; this paper fills this gap through convex relaxation, making gradient attacks feasible for GNNs, and states that its adversarial training is the first optimization-based GNN adversarial training.
How does the paper address this problem?
After convexly relaxing the Boolean edge perturbation, solve the attack with PGD/min-max first-order optimization, then restore it by random sampling, and based on this perform min-max adversarial training.
Overall idea: formulate the discrete edge add/delete problem as a continuous optimization problem, solve it with first-order methods and then discretize, and embed the same attacker into adversarial training. The methods include PGD topology attack, min-max topology attack, and robust training (Algorithm 4).
Problem formulation
- Use a Boolean symmetric matrix S to encode whether edges are modified; the perturbed adjacency matrix is A′ = A + C ◦ S, where C = Ā − A, positive entries denote edges that can be added and negative entries denote edges that can be deleted.
- The attack loss can be CE-type (negative cross-entropy) or CW-type: fi = max{Zi,yi − maxc≠ yi Zi,c, −κ}, where κ is the confidence.
- The two threat models correspond to two optimization problems: when W is fixed, minimize the sum of attack losses of each node under the budget 1ᵀs ≤ ε; when W can be retrained, it is a min-max form, where the inner layer maximizes the attack loss over W to simulate retraining.
PGD topology attack (Algorithm 2)
- Relax s ∈ {0,1}ⁿ to the convex hull [0,1]ⁿ, and perform projected gradient descent on the constraint set S = {s | 1ᵀs ≤ ε, s ∈ [0,1]ⁿ}: s(t) = ΠS[s(t−1) − ηt ∇ f(s(t−1))].
- Proposition 1 gives the closed-form solution of the projection; the dual variable µ involved is solved by bisection, and the authors state that it converges at a log rate.
- The continuous solution is restored via random sampling in Algorithm 1: using s as a probability vector, sample K = 20 binary vectors, and take the one that satisfies the budget and has the smallest attack loss (changed to the highest misclassification rate in the experiments).
Min-max topology attack (Algorithm 3)
- For the retrainable scenario, use first-order alternating optimization: the inner layer performs gradient ascent on W (set to 20 steps in the experiments), and the outer layer performs PGD on s.
- The authors state that multiple inner maximizations can be performed within each outer iteration to balance computational efficiency and convergence accuracy.
Adversarial training (Algorithm 4)
- Solve the min-max robust optimization problem, with the loss restricted to CE-type; the inner layer runs PGD on s (20 steps), and the outer layer updates W in a gradient-ascent manner (i.e., minimizing −f).
- Proposition 2 gives the equivalence relation of this problem with the max-min form and the bound (22) ≤ (20); the authors state that because f is non-convex in s and non-concave in W, this formulation is not equivalent to the attack problem (7).
- Settings: T = 1000, βt = 0.01, ηt = 200/√t; following Madry et al., the GCN hidden units are increased from 16 to 32.
What experiments did the paper conduct?
On Cora/Citeseer, compare four attacks and three baselines with 5% edge perturbation, and evaluate the effect of adversarial training at ε=5%–20%.
Experimental setup
- Model under test: GCN (Kipf and Welling, 2016), with 16 hidden units by default, increased to 32 in adversarial training.
- Datasets: Cora and Citeseer, undirected unweighted edges, sparse bag-of-words features; training labeled nodes: 140 for Cora and 120 for Citeseer, test labeled nodes: 1000 for both.
- Baselines: DICE, Greedy attack (Meta-Self with weight retraining removed), Meta-Self.
- Metric: test node misclassification rate (1 − prediction accuracy), mean ± std; the evaluation follows the criterion of Meta-Self, using an independent pre-trained model to predict test node labels during the attack.
- Number of repetitions: each group of experiments is repeated 5 times with different training/test splits.
- Perturbation budget: by default ε = 5% of the number of existing edges; in adversarial training experiments ε is taken from 5%–20%.
Main results
Table 1: misclassification rate under 5% edge perturbation (%, mean ± std).
Swipe horizontally to read the table
Setting Method Cora Citeseer — clean (no attack) 18.2 ± 0.1 28.9 ± 0.3 fixed natural model DICE 18.9 ± 0.2 29.8 ± 0.4 fixed natural model Greedy 25.2 ± 0.2 34.6 ± 0.3 fixed natural model Meta-Self 22.7 ± 0.3 31.2 ± 0.5 fixed natural model CE-PGD 28.0 ± 0.1 36.0 ± 0.2 fixed natural model CW-PGD 27.8 ± 0.4 37.1 ± 0.5 fixed natural model CE-min-max 26.4 ± 0.1 34.1 ± 0.3 fixed natural model CW-min-max 26.0 ± 0.3 34.7 ± 0.6 retrained model (20) Meta-Self 29.6 ± 0.4 39.7 ± 0.3 retrained model (20) CE-min-max 30.8 ± 0.2 37.5 ± 0.3 retrained model (20) CW-min-max 30.5 ± 0.5 39.6 ± 0.4 - The authors state that when attacking the natural model, the misclassification rates of CE-PGD and CW-PGD are higher than all baselines; PGD attacks outperform min-max attacks because attacking a pre-defined GCN is easier.
- For the retrained model, the authors state that min-max attacks are competitive compared with Meta-Self: CE-min-max is higher on Cora, and Meta-Self is higher on Citeseer; the authors also point out that evaluation on the (20) retrained model is not entirely fair, because the retrained weights may be suboptimal.
- Figure 1 shows that the attack loss of CE-PGD/CW-PGD decreases with iterations (T = 200, ηt = 200/√t), and the authors state that PGD converges smoothly.
Effect of adversarial training (Table 2, Figure 2)
- What was tested: Algorithm 4 trains a robust GCN at ε = 5%, comparing the misclassification rates of natural/robust models on the original graph A and the adversarial graph A′ (generated by CE-PGD).
- Results: on Cora, A′/natural 28.0 ± 0.1 drops to A′/robust 22.0 ± 0.2; on Citeseer, 36.0 ± 0.2 drops to 32.2 ± 0.4; on the original graph, Cora 18.2 → 18.1, Citeseer 28.9 → 28.7 (Table 2).
- Authors' interpretation: the authors state that robust training at ε = 5% does not harm test accuracy on the original graph while reducing the attack success rate; Figure 2 shows that the robust training loss decreases within 1000 iterations, and the authors state that ordinary training requires only 200 iterations, while robust training requires more.
Effect of the training budget ε (Table 3, Figure 3)
- What was tested: on Cora, the CE-PGD misclassification rate when training ε ∈ {0,5,10,15,20}% and the attack ε varies over the same range.
- Results: when the attack ε = 5%, the model with training ε = 5% has the lowest misclassification rate (22.0), rising to 26.5 when training ε = 20%; when the attack ε = 20%, the model with training ε = 20% is 33.5, lower than the natural model's 40.2 (Table 3).
- Authors' interpretation: the authors state that the model gains robustness under the ε constraint used in training, and recommend training at ε = 0.1 to balance original-graph performance; Figure 3 shows that as ε increases, the gap between test accuracy and CE-PGD attack accuracy increases, based on which the authors state that robust models with large ε are harder to obtain, and state that the robust model is effective against all three attacks: CE-PGD, CW-PGD, and Greedy.
Other ablations and analyses
- Attack loss type: on Cora, CE-PGD is slightly higher than CW-PGD (28.0 vs 27.8); on Citeseer, CW-PGD is higher (37.1 vs 36.0) (Table 1).
- Number of inner maximization steps for min-max: fixed at 20 steps (Section 6.2).
- Number of inner minimization steps for robust training: 20 steps (Section 6.3).
- Model capacity: adversarial training increases hidden units from 16 → 32 (Section 6.3).
What are some points that can be further explored?
The paper does not specifically discuss limitations; the experiments cover only GCN, two citation network datasets, and a 5%–20% edge perturbation budget.
Limitations and future directions noted by the authors
- The paper does not specifically discuss limitations.
- In the Conclusion, the authors state that this paper may provide a potential avenue for theoretical research on and improvement of the robustness of deep learning models on graph data (this is the authors' outlook, not a specific limitation or plan).
Scope of experimental coverage
- The model tested is one kind, GCN (Section 6.1), with 16 hidden units (32 in adversarial training).
- The datasets are two citation networks, Cora and Citeseer (Section 6.1), with 140/120 labeled nodes for training and 1000 for testing.
- Attack evaluation covers three baselines, DICE, Greedy, and Meta-Self, and four variants of this paper, with a budget of 5% (Table 1); adversarial training evaluation covers three attacks, CE-PGD, CW-PGD, and Greedy, with training and attack ε at 5%–20% (Table 3, Figure 3).
- Each group of experiments is repeated 5 times, reporting mean ± std (Section 6.1).
- The paper does not report the running time of attacks, the specific query cost of PGD iterations in the min-max attack, nor the experimental results of targeted attack (Section 4.1 states that this paper focuses on untargeted).
Summarize the main content of the paper
First-order topology attacks and adversarial training for GNNs based on convex relaxation; on Cora/Citeseer the attacks are stronger than baselines, and the defense reduces the attack success rate.
An attack+defense paper on GNN adversarial robustness, studying the generation and defense of edge addition/deletion (topology attack) in semi-supervised node classification.
- Problem: The discreteness of graphs makes first-order continuous optimization attacks difficult to apply directly to edge manipulation; the authors state that prior GNN robustness research is scarce.
- Method: Relax the Boolean edge perturbation matrix to [0,1], solve the attack with PGD (fixed-weight setting) and min-max alternating optimization (retrainable setting), and restore the binary perturbation by random sampling; then embed this attacker into min-max adversarial training (Algorithm 4), with a CE-type loss.
- Attack results: Under 5% edge perturbation, CE-PGD achieves a misclassification rate of 28.0% on Cora and 36.0% on Citeseer, and CW-PGD achieves 37.1% on Citeseer, all higher than DICE, Greedy, and Meta-Self (Table 1); for the retrained model, CE-min-max achieves 30.8% on Cora, higher than Meta-Self's 29.6%, while on Citeseer it is lower than Meta-Self.
- Defense results: Adversarial training with ε = 5% reduces the misclassification rate of the CE-PGD attack on Cora from 28.0% to 22.0%, and the misclassification rate on the original graph remains essentially unchanged, from 18.2% → 18.1% (Table 2); the authors state that the robust model is effective against CE-PGD, CW-PGD, and Greedy, and recommend a training ε of 0.1.
- Authors' conclusion: The authors state that changing only a small number of edges can degrade GNN performance, that their adversarial training improves robustness to gradient and greedy attacks without sacrificing accuracy on the original graph, and that this paper offers a potential avenue for theoretical research on the robustness of graph data models.
Related papers
Show 2 more papers
- RGDM: Robust Graph Diffusion ModelDefensesarXiv