Graph convolutional networks (GCNs) have been widely used for classifying graph nodes in the semi-supervised setting.
 Previous works have shown that GCNs are vulnerable to the perturbation on adjacency and feature matrices of existing nodes. However, it is unrealistic to change the connections of  existing nodes in many applications, such as existing users in social networks. In this paper, we investigate methods attacking GCNs by adding fake nodes. A greedy algorithm is proposed to generate adjacency and feature matrices of fake nodes, aiming to minimize the classification accuracy on the existing ones. In additional, we introduce a discriminator to classify fake nodes from real nodes, and propose a Greedy-GAN algorithm to simultaneously update the discriminator and the attacker, to make fake nodes indistinguishable to the real ones.   Our non-targeted attack decreases the accuracy of GCN down to 0.10, and our targeted attack reaches a success rate of 0.99 for attacking the whole datasets, and 0.94 on average for attacking a single node. Graphs play a very important role in many real world applications, such as social networks (Facebook and Twitter), biological networks (protein-protein interaction networks and gene interaction networks), as well as attribute graphs (PubMed and Arxiv) BID12 BID32 BID26 . Node classification is one of the most important tasks on graphs-given a graph with labels associated with a subset of nodes, predict the labels for rest of the nodes. For this node classification task, deep learning models on graphs, such as Graph Convoltional Networks (GCNs), have achieved state of the art performance BID16 . Moreover, GCNs have wide applications in cyber security, where they can learn a close-to-correct node labeling semiautonomously. This reduces the load on security experts and helps to manage networks that add or remove nodes dynamically, such as, WiFi networks in universities and web services in companies.The wide applicability of GCNs motivates recent studies about their robustness. BID34 BID6 developed algorithms to attack GCNs, showing that by altering a small amount of edges and features, the classification accuracy of GCNs can be reduced to chance-level. However, changing edges or features associated with existing nodes is impractical in many cases. For example, in social network applications, an attacker has to login to the users' accounts to change existing connections and features, and gaining login accesses is almost impossible. In comparison, adding fake nodes that correspond to fake accounts or users, can be much easier in practice. But the key question is can we interfere the classification results of existing nodes by adding fake nodes to the network? We answer this question affirmative by introducing novel algorithms to design fake nodes that successfully reduce GCN's performance on existing nodes.To design the adjacency and feature matrices associated with fake nodes, we have to address two challenges. First, the edges and features are usually discrete 0/1 variables. Although there have been many algorithms proposed for attacking image classifiers, such as FGSM, C&W and PGD attacks BID11 BID1 BID21 , they all assume continuous input space and cannot be directly applied to problems with discrete input space. Second, it's not easy to make the fake nodes "looked" like the real ones? For example, if we add a fake node that connects to all existing nodes, the system can easily detect and disable such fake node. In this paper, we propose two algorithms, Greedy attack and Greedy-GAN attack, to address these two challenges. Our contributions can be summarized below:• To the best of our knowledge, this is the first paper studying how to add fake nodes to attack GCNs. We do not need to manipulate existing nodes' adjacency and feature matrices.• We propose a Greedy attack algorithm to address the discrete input space problem in designing fake nodes' adjacency and feature matrices.• We introduce a discriminator to classify fake nodes from real nodes, and propose a Greedy-GAN algorithm to simultaneous optimize the discriminator and the attacker. Despite a lower successful rate, this approach can make fake nodes harder to detect.• We conduct experiments on several real datasets. For non-targeted attack, we get accuracy down to 0.10 for the Cora dataset, and 0.14 for the Citeseer dataset. For targeted attack on whole datasets, Greedy attack have up to 99% success rate on Cora and 90% on Citeseer.For targeted attack on a single node, it could reach 94% success rate on Cora and 0.80% success rate on Citeseer. We present two algorithms, Greedy and Greedy-GAN, on adversarial attacks of GCNs by adding fake nodes, without changing any existing edges or features, for both non-targeted and targeted attacks. We successfully attacked existing GCN implementations, and explored parameter sensitives, such as number of fake nodes and different label rates of fake nodes. To make the attack unnoticeable, we added a discriminator using the Greedy-GAN algorithm to generate features of fake nodes. We noticed that data cleaning before training is crucial, and adding a discriminator makes the impact of attacks weaker. There is a trade-off between the efficiency of attack and realness of fake nodes' features.
non-targeted and targeted attack on GCN by adding fake nodes The authors propose a new adversarial technique to add "fake" nodes to fool a GCN-based classifier