Turning Strengths into Weaknesses: A Certified Robustness Inspired Attack Framework against Graph Neural Networks. (arXiv:2303.06199v1 [cs.CR])

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.