# Adversarial Immunization for Certifiable Robustness on Graphs

arXiv: https://arxiv.org/abs/2007.09647 · HTML: https://mlsanity.com/paper/2007.09647/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Jul 2020.

## Built on by (most cited first, 14 of 14)

- [Trustworthy Graph Neural Networks: Aspects, Methods and Trends](https://mlsanity.com/paper/2205.07424/) (2022)
- [Single Node Injection Attack against Graph Neural Networks](https://mlsanity.com/paper/2108.13049/) (2021)
- [Are Defenses for Graph Neural Networks Robust?](https://mlsanity.com/paper/2301.13694/) (2023)
- [Data-centric Graph Learning: A Survey](https://mlsanity.com/paper/2310.04987/) (2023)
- [Adversarial Camouflage for Node Injection Attack on Graphs](https://mlsanity.com/paper/2208.01819/) (2022)
- [IDEA: Invariant Defense for Graph Adversarial Robustness](https://mlsanity.com/paper/2305.15792/) (2023)
- [Graph Adversarial Immunization for Certifiable Robustness](https://mlsanity.com/paper/2302.08051/) (2023)
- [Everything Perturbed All at Once: Enabling Differentiable Graph Attacks](https://mlsanity.com/paper/2308.15614/) (2023)
- [Deterministic Certification of Graph Neural Networks against Graph Poisoning Attacks with Arbitrary Perturbations](https://mlsanity.com/paper/2503.18503/) (2025)
- [Universal and Transferable Attacks on Pathology Foundation Models](https://mlsanity.com/paper/2510.16660/) (2025)
- [RIDA: A Robust Attack Framework on Incomplete Graphs](https://mlsanity.com/paper/2407.18170/) (2024)
- [Adversarial Graph Neural Network Benchmarks: Towards Practical and Fair Evaluation](https://mlsanity.com/paper/2605.05534/) (2026)
- [NNV3: Expanding Neural Network Verification to New Architectures and Domains](https://mlsanity.com/paper/2609.30050/) (2026)
- [Reachability-Based Formal Verification of Graph Neural Networks with Node and Edge Features](https://mlsanity.com/paper/2609.30079/) (2026)

## Abstract (arXiv)

Despite achieving strong performance in semi-supervised node classification task, graph neural networks (GNNs) are vulnerable to adversarial attacks, similar to other deep learning models. Existing researches focus on developing either robust GNN models or attack detection methods against adversarial attacks on graphs. However, little research attention is paid to the potential and practice of immunization to adversarial attacks on graphs. In this paper, we propose and formulate the graph adversarial immunization problem, i.e., vaccinating an affordable fraction of node pairs, connected or unconnected, to improve the certifiable robustness of graph against any admissible adversarial attack. We further propose an effective algorithm, called AdvImmune, which optimizes with meta-gradient in a discrete way to circumvent the computationally expensive combinatorial optimization when solving the adversarial immunization problem. Experiments are conducted on two citation networks and one social network. Experimental results demonstrate that the proposed AdvImmune method remarkably improves the ratio of robust nodes by 12%, 42%, 65%, with an affordable immune budget of only 5% edges.