  Recent studies have shown that graph convolution networks (GCNs) are
vulnerable to carefully designed attacks, which aim to cause misclassification
of a specific node on the graph with unnoticeable perturbations. However, a
vast majority of existing works cannot handle large-scale graphs because of
their high time complexity. Additionally, existing works mainly focus on
manipulating existing nodes on the graph, while in practice, attackers usually
do not have the privilege to modify information of existing nodes. In this
paper, we develop a more scalable framework named Approximate Fast Gradient
Sign Method (AFGSM) which considers a more practical attack scenario where
adversaries can only inject new vicious nodes to the graph while having no
control over the original graph. Methodologically, we provide an approximation
strategy to linearize the model we attack and then derive an approximate
closed-from solution with a lower time cost. To have a fair comparison with
existing attack methods that manipulate the original graph, we adapt them to
the new attack scenario by injecting vicious nodes. Empirical experimental
results show that our proposed attack method can significantly reduce the
classification accuracy of GCNs and is much faster than existing methods
without jeopardizing the attack performance.
