Topological Effects on Attacks Against Vertex Classification
  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.
