# Turning Strengths into Weaknesses: A Certified Robustness Inspired Attack Framework against Graph Neural Networks

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Mar 2023.

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

- [Graph Neural Network Causal Explanation via Neural Causal Models](https://mlsanity.com/paper/2407.09378/) (2024)
- [GDeR: Safeguarding Efficiency, Balancing, and Robustness via Prototypical Graph Pruning](https://mlsanity.com/paper/2410.13761/) (2024)
- [A Certified Radius-Guided Attack Framework to Image Segmentation Models](https://mlsanity.com/paper/2304.02693/) (2023)
- [Certifiable Black-Box Attacks with Randomized Adversarial Examples: Breaking Defenses with Provable Confidence](https://mlsanity.com/paper/2304.04343/) (2023)
- [Certifiably Robust Graph Contrastive Learning](https://mlsanity.com/paper/2310.03312/) (2023)
- [On the Relationship Between Interpretability and Explainability in Machine Learning](https://mlsanity.com/paper/2311.11491/) (2023)
- [Watermarking Graph Neural Networks via Explanations for Ownership Protection](https://mlsanity.com/paper/2501.05614/) (2025)
- [Backdoor Attacks on Discrete Graph Diffusion Models](https://mlsanity.com/paper/2503.06340/) (2025)
- [Deterministic Certification of Graph Neural Networks against Graph Poisoning Attacks with Arbitrary Perturbations](https://mlsanity.com/paper/2503.18503/) (2025)
- [Cost Aware Untargeted Poisoning Attack against Graph Neural Networks,](https://mlsanity.com/paper/2312.07158/) (2023)
- [Target-Aware Interaction-Guided Reinforcement Learning for Black-Box Node Injection Attacks on Graph Neural Networks](https://mlsanity.com/paper/2607.04091/) (2026)

## Abstract (arXiv)

Graph neural networks (GNNs) have achieved state-of-the-art performance in many graph learning tasks. However, recent studies show that GNNs are vulnerable to both test-time evasion and training-time poisoning attacks that perturb the graph structure. While existing attack methods have shown promising attack performance, we would like to design an attack framework to further enhance the performance. In particular, our attack framework is inspired by certified robustness, which was originally used by defenders to defend against adversarial attacks. We are the first, from the attacker perspective, to leverage its properties to better attack GNNs. Specifically, we first derive nodes' certified perturbation sizes against graph evasion and poisoning attacks based on randomized smoothing, respectively. A larger certified perturbation size of a node indicates this node is theoretically more robust to graph perturbations. Such a property motivates us to focus more on nodes with smaller certified perturbation sizes, as they are easier to be attacked after graph perturbations. Accordingly, we design a certified robustness inspired attack loss, when incorporated into (any) existing attacks, produces our certified robustness inspired attack counterpart. We apply our framework to the existing attacks and results show it can significantly enhance the existing base attacks' performance.