Graph convolutional networks (GCNs) have been widely used for classifying graph nodes in the semi-supervised setting. Previous work have shown that GCNs are vulnerable to the perturbation on adjacency and feature matrices of existing nodes. However, it is unrealistic to change existing nodes in many applications, such as existing users in social networks. In this paper, we design algorithms to attack 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 nodes. In additional, we introduce a discriminator to classify fake nodes from real nodes, and propose a Greedy-GAN attack 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 99% on the whole datasets, and 94% on average for attacking a single target node.
The authors propose a new adversarial technique to add “fake” nodes to fool a GCN-based classifier. The basic approach relies on a greedy heuristic to add edge/node features, and the authors also present a GAN-based approach, which allows the model to add “fake” nodes that are not easily distinguishable from regular nodes. The primary motivation behind the idea of adding “fake” is that it is unrealistic to change the features/edges of existing nodes. Experimental results show that adding a large number (20% in most cases) of fake nodes can significantly degrade accuracy of a GCN, and results show that the GAN-based approach is somewhat effective at making the “fake” nodes less distinguishable.  In terms of strengths, the GAN-based approach is well-motivated and it appears that the authors were thorough in their experiments on Cora/Citseer (e.g., with a number of ablation/sensitivity studies).
However, while interesting, this paper has a number of areas where it could be substantially improved:
1) With regards to the motivation: It is not clear what substantive technical novelty there is in the idea of “adding fake nodes”, compared to existing approaches that simply modify existing nodes in an adversarial way. Intuitively, the approach of Zugner et al can already handle this case of "adding new nodes". One just adds a set of nodes with random/null edges/features to the graph, treats this as their “attacker node” set and then runs Zugner et al's greedy algorithm. Some clarification on why this simple application of Zugner et al's approach does not work would be useful and/or empirical results using their method as a baseline would be useful. (Also, Zugner et al was published in KDD 2018, so the citation should be corrected). 
2) In Zugner et al, they derive approximations and algorithms that allow them to compute the score of adding/removing an edge in constant time. The greedy approach in this work appears quite expensive as every greedy update requires an expensive gradient computation. Some discussion of computational complexity would improve the paper. 
3) Results are only provided on two small datasets (presumably due to the large computational cost for the approach). These two very small datasets are not indicative of many real-world scenarios, and additional results on larger (and more diverse) datasets would greatly strengthen the paper. 
4) Adding 20% fake nodes seems like a prohibitively large number. Even 5% fake nodes is extremely large. It is unclear what real-world applications could admit such drastic numbers of fake nodes, and some comments on this would greatly strengthen the paper. 
5) The GAN method is interesting and well-motivated, but it is not clear if this method offers any utility beyond the “distribution matching” approach of Zugner et al (Section 4.1 of their paper). A comparison between these methods is necessary to justify the utility of the proposed GAN-greedy approach.