Topological Effects on Attacks Against Vertex Classification
arXiv:2003.05822
Abstract
Vertex classification is vulnerable to perturbations of both graph topology and vertex attributes, as shown in recent research. As in other machine learning domains, concerns about robustness to adversarial manipulation can prevent potential users from adopting proposed methods when the consequence of action is very high. This paper considers two topological characteristics of graphs and explores the way these features affect the amount the adversary must perturb the graph in order to be successful. We show that, if certain vertices are included in the training set, it is possible to substantially an adversary's required perturbation budget. On four citation datasets, we demonstrate that if the training set includes high degree vertices or vertices that ensure all unlabeled nodes have neighbors in the training set, we show that the adversary's budget often increases by a substantial factor---often a factor of 2 or more---over random training for the Nettack poisoning attack. Even for especially easy targets (those that are misclassified after just one or two perturbations), the degradation of performance is much slower, assigning much lower probabilities to the incorrect classes. In addition, we demonstrate that this robustness either persists when recently proposed defenses are applied, or is competitive with the resulting performance improvement for the defender.
arXiv comment17 pages, 11 figures
References in corpus (10)
- Inductive Representation Learning on Large Graphs
- Adversarial Attacks on Neural Networks for Graph Data
- Provable defenses against adversarial examples via the convex outer adversarial polytope
- On Evaluating Adversarial Robustness
- Adversarial Attacks on Graph Neural Networks via Meta Learning
- Adversarial Attacks on Node Embeddings via Graph Poisoning
- On the Robustness of the CVPR 2018 White-Box Adversarial Example Defenses
- Adversarial Examples on Graph Data: Deep Insights into Attack and Defense
- Provable Robustness of ReLU networks via Maximization of Linear Regions
- Certifiable Robustness to Graph Perturbations