Research map / Adversarial robustness and security / Attacks on text and graphs
Value at Adversarial Risk: A Graph Defense Strategy against Cost-Aware Attacks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes RisKeeper, a graph defense that learns per-node protection costs via bi-level robust training against a cost-aware gradient-based structural attack, outperforming heuristic cost allocations and GNN defenses on node classification.
Problem
Defending GNNs against structural adversarial attacks in a cost-aware way, where defenders assign protection costs to nodes so that attacks become expensive for the attacker, rather than reacting to attacks after they occur.
Approach
Treats defense as allocating learnable node costs (produced by a GCN+MLP cost model) and solves a minimax bi-level problem against a cost-aware PGD attack whose objective subtracts the attack's cost from the loss; the attack's discrete edge flips are handled via relaxation, projection onto a cost-budget set, and Bernoulli sampling.
Key results
- RisKeeper reaches 0.795 test accuracy on Cora under Cost-Aware PGD evasion attack at 0.08|E| budget, versus 0.811 unattacked and 0.746 for GCN with average cost allocation.
- Under poisoning attack at 0.08|E| budget on Cora, RisKeeper obtains 0.791 versus 0.739 for GCN, and it wins most settings against GCN-SVD, GCN-Jaccard and GNN-Median.
- Case study with learned costs identifies 3-star, 4-circle and tailed-triangle graphlets as the most vulnerable structures.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| learn node-specific costs with RisKeeper instead of assigning equal node costs | GCN defense · Cora, evasion, Cost-Aware PGD (0.08|E|) | accuracy: 0.746 ± 0.004 -> 0.795 ±0.004 | Helped |
| learn node-specific costs with RisKeeper instead of assigning equal node costs | GCN defense · Citeseer, evasion, Cost-Aware PGD (0.08|E|) | accuracy: 0.659 ± 0.011 -> 0.707 ± 0.003 | Helped |
| learn node-specific costs with RisKeeper instead of assigning equal node costs | GCN defense · Amazon Computers, evasion, Cost-Aware PGD (0.08|E|) | accuracy: 0.788 ± 0.005 -> 0.819 ± 0.017 | Helped |
| learn node-specific costs with RisKeeper instead of assigning equal node costs | GCN defense · Amazon Photo, evasion, Cost-Aware PGD (0.08|E|) | accuracy: 0.854 ± 0.016 -> 0.874 ± 0.018 | Helped |
| learn node-specific costs with RisKeeper instead of assigning equal node costs | GCN defense · Cora, poisoning, Cost-Aware PGD (0.08|E|) | accuracy: 0.698 ± 0.084 -> 0.791 ± 0.004 | Helped |
| learn node-specific costs with RisKeeper instead of assigning equal node costs | GCN defense · Citeseer, poisoning, Cost-Aware PGD (0.08|E|) | accuracy: 0.649 ± 0.008 -> 0.708 ± 0.003 | Helped |
| learn node-specific costs with RisKeeper instead of assigning equal node costs | GCN defense · Amazon Computers, poisoning, Cost-Aware PGD (0.08|E|) | accuracy: 0.798 ± 0.032 -> 0.830 ± 0.008 | Helped |
| learn node-specific costs with RisKeeper instead of assigning equal node costs | GCN defense · Amazon Photo, poisoning, Cost-Aware PGD (0.08|E|) | accuracy: 0.865 ± 0.016 -> 0.875 ± 0.018 | Helped |
Surprising findings
- Clustering-coefficient-based cost allocation performs much worse on Citeseer (0.589 evasion), which the authors say casts doubt on heuristic cost schemes' generality.
- Gains of RisKeeper narrow as attacker budget increases, since larger budgets let attackers ignore assigned costs.
Limitations
- Only untargeted structural attacks are studied; targeted attacks are left for future work.
- Evaluated only on four node classification datasets and a single GCN backbone.
Experimental setup
Datasets: Cora Citeseer Amazon Computers Amazon Photo
Benchmarks: Cora Citeseer Amazon Computers Amazon Photo
Metrics: test accuracy
Baselines: Raw Avg. cost Rand. cost Degree-based cost Cluster-Coef. cost GCN-SVD GCN-Jaccard GNN-Median
Builds on: Projected gradient descent (Madry et al. 2017) Topology attack and defense (Xu et al. 2019) Meta-Self attack (Zügner and Günnemann 2019) Robust training (Song et al. 2023) GCN (Kipf and Welling 2017)
Closest papers by meaning
- Boosting the Adversarial Robustness of Graph Neural Networks: An OOD Perspective (ICLR 2024 · similarity 0.92)
- Adversarial Training for Graph Neural Networks: Pitfalls, Solutions, and New Directions (NeurIPS 2023 · similarity 0.92)
- Are Defenses for Graph Neural Networks Robust? (NeurIPS 2022 · similarity 0.91)
- If You Want to Be Robust, Be Wary of Initialization (NeurIPS 2024 · similarity 0.91)
- A Simple and Yet Fairly Effective Defense for Graph Neural Networks (AAAI 2024 · similarity 0.90)
- Highly Imperceptible Black-Box Graph Injection Attacks with Reinforcement Learning (AAAI 2025 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.