Topology Attack and Defense for Graph Neural Networks: An Optimization Perspective

TLDR

Graph neural networks have achieved strong performance in semi‑supervised node classification, yet their adversarial robustness remains largely unexplored. This work aims to develop a gradient‑based attack and an optimization‑based defense for GNNs. The authors design a gradient‑based attack that perturbs a small number of edges in discrete graph data, and use this attack to train GNNs via an optimization‑based adversarial training scheme. The attack significantly degrades classification accuracy with few edge changes, while the proposed defense improves robustness against both gradient‑based and greedy attacks without harming accuracy on clean graphs.

Abstract

Graph neural networks (GNNs) which apply the deep neural networks to graph data have achieved significant performance for the task of semi-supervised node classification. However, only few work has addressed the adversarial robustness of GNNs. In this paper, we first present a novel gradient-based attack method that facilitates the difficulty of tackling discrete graph data. When comparing to current adversarial attacks on GNNs, the results show that by only perturbing a small number of edge perturbations, including addition and deletion, our optimization-based attack can lead to a noticeable decrease in classification performance. Moreover, leveraging our gradient-based attack, we propose the first optimization-based adversarial training for GNNs. Our method yields higher robustness against both different gradient based and greedy attack methods without sacrifice classification accuracy on original graph.