Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: In this paper, the authors mainly show that the adversary can force the GNN to classify any target node to a chosen label by perturbing another single arbitrary node’s feature in the graph. The paper is well written and easy to understand. However, there are several concerns about the paper:

1. The novelty of the paper is rather limited. The paper simply uses the gradient attacker method to add continuous perturbations to the node attributes. What is the novelty here compared to other gradient based attacks for the data without graph structure such as images? I don’t see any novelty or contribution from the methodology perspective.

2. The problem setting needs to be well discussed. In the introduction, the authors use the example of crafting adversarial posts to motivate the problem. However, in the problem definition, it becomes adding perturbations to the node features.  Modifying the node’s feature in realistic settings is even harder than modifying the graph structure to me .(They could revise the words or sentences in the post, but they could not add the feature vector directly as the feature vector are usually preprocessed by some other models).

3. The authors should include some robust GNNs such as [1][2] as baselines to test how effective is the proposed method. The authors should also consider add more baselines as the attack methods. 

[1] Zügner, Daniel, and Stephan Günnemann. "Certifiable robustness and robust training for graph convolutional networks." In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 246-256. 2019.
[2] Jin, Hongwei, and Xinhua Zhang. "Robust Training of Graph Convolutional Networks via Latent Perturbation." ECML-PKDD 2020


review_title: the paper lacks novelty

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper studies the problem of adversarial attacks in graph neural networks. It proposes a new attack strategy called single-node attack where only one node is perturbed.  A gradient-based attack algorithm is proposed to modify features of the attack node and achieve the single-node attack. Experiments have demonstrated the effectiveness of the proposed attack algorithm.
The studied problem (adversarial attack on graphs) is important and the single-node attack setting is interesting. However, there are several concerns that need to be addressed.
1.	For the constraint of unnoticeable perturbation discussed in Section 3.2, the authors argue that the perturbation would be unnoticeable if the frequency of some words is slightly modified. This contradicts with the claim that the attack should preserve the feature co-occurrence to make the perturbation unnoticeable in Nettack[1]. According to Section 4.1, SINGLE changes 50%, 31% of the node attributes on Cora and CiteSeer, respectively. With so many perturbed elements, the attack could be easily detected if many pairs of features that never appear together suddenly co-occur in a single node.
2.	Also, it is hard to evaluate whether comparing single-node attack with single-edge attack is fair, since single-edge attack only changes one edge while single-node attack can change a relative larger number of elements in the feature vector. (In Nettack, one element change in the feature matrix or adjacency matrix is considered as one perturbation) It would be more convincing if the number of elements in the feature vector changed by SINGLE is much less.
3.	For the first claim in Section 3.2 "Perturbing nodes instead of edges", although this claim shows perturbing features could be better than removing edges, it remains a question whether it is better than adding edges. Also, it might be interesting to include one more baseline where we set $\eta=-x_a$ as the feature perturbations to illustrate SINGLE can find better perturbations than simply removing the edges of the attacker node.
4.	For datasets with discrete features, SINGLE only uses "$\epsilon_{\infty}=1$" as the constraint but the discrete features are originally binary values and "$\epsilon_{\infty}=1$". This basically means no unnoticeable constraints are applied on the attacker for those datasets (Cora and CiteSeer). Hence, it would be more convincing to conduct experiments on how the model performs when using different norms as constraints (e.g., l1 and l2 norm) for discrete datasets.
5.	Since the authors claim a single-node attack is as effective as a multiple-node attack, multiple-node attacks, i.e setting the number of attacker nodes to a larger value, are suggested to be included as baselines.
6.	Given the superiority of only changing the features for one attacker node, injecting one attacker node would be of more interest since it is even more practical than modifying features on the existing node (e.g., creating an attacker account on Twitter). So, it would be better to add the experiment of node injecting to further improve the algorithm.
Minor Comments
1.	It would be better to report the standard deviation of the proposed methods in Table 1/2 considering the performances of other baselines are reported with standard deviation.
[1] Adversarial Attacks on Neural Networks for Graph Data. KDD'18

review_title: Official Blind Review #2

final_score: rating: 6: Marginally above acceptance threshold
review_content: This submission shows that a single-node attack for GNNs can be surprisingly effective. The discovery is mostly in the form of experimental results, rather than in the form of a new method.

Strengths:

S1: The discovery that a single-node attack can be surprisingly effective is indeed interesting. It can potentially complement our understanding of GNNs and bring novel ideas in the future.

S2: The empirical results are mostly sufficient to support the main insight that a single-node attack can be effective in many cases. Still, it would be even better if Table 2 can include results for models other than the vanilla GNNs (e.g., GAT) (note that there aren’t GAT’s results on Cora, CiteSeer, Twitter, even though GAT’s result on PubMed is shown in Figure 2). 

S3: Good literature review. Friendly to even the readers who don’t follow the field of adversarial attacks closely.

Weaknesses:

W1: The abstract is a bit exaggerating the main discovery. The empirical results only suggest that single-node attacks are effective under the following conditions: (1) the model is the vanilla GNN (while GAT is much harder to attack), (2) the attack node is close enough to the victim node (<= 3 hops), and (3) the node features are of the continuous kind (the results on datasets of discretized features are much weaker).
 
W2: The proposed method seems unrealistic for datasets of discretized (one-hot, multi-hot, integer-valued, etc.) node features. (1) It seems like the optimized perturbation vector \eta is still of continuous values (rather than being discretized after optimization) even for datasets of discretized node features. (2) The submission states that “In Cora, SINGLE perturbed 717 elements on average, which are 50%...” However, 50% of ALL features seems to be a bit too unrealistic if most of the normal nodes have far fewer than 50% features that are not zeros. 
 
W3: The submission is mostly about new insights. It, however, barely invent any novel techniques. The submission would be stronger if it had explored how to improve the effectiveness of the single-node attack on the discretized datasets or against GNNs with attention.
review_title: Interesting insights, sufficient empirical results, but risks over-claiming

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper studies how to attack a specific attacker node by perturbing only one single node's feature. The authors proposed a gradient-based attack strategy, namely SINGLE, to learn the perturbation vector with the consideration of unnoticeability. In general, I really like the idea of this work. Compared with other attacking strategies, the attacking scenario in this paper is more realistic, e.g., the access to a single node (hacking the account), etc. And the gradient-based attack is intuitive and straightforward. Overall, this paper is well-written and easy to follow. I have the following concerns that would like the authors to clarify.

- In the paper, the authors claim that it can attacking by perturbing single arbitrary node. I think 'arbitrary' is a little bit over-claimed, since the distance between attacker node $a$ and the victim node $v$ should satisfy $d(a, v) \leq L$ (# layers).
- I am a little bit confused about how to process the encoded dataset. In section 4, the authors mention that the most frequent 10000 words are used as node features, then the glove embeddings are used to multiply by the embedding. Does it mean that the update rule in each layer becomes $\sigma(A X Z W)$, where $A$ = adjacency matrix (shape $n \times n$), $X$ = many-hot/TD-IDF encoding of 10000 words (shape $n \times 10000$), $Z$ = $d$-dimensional word embedding (shape $10000 \times d$) and $W$ = weight matrix (shape $d \times \textit{nhid}$)? If I understand it correctly, the derivative of loss wrt $X$ (i.e., many-hot/TD-IDF encoding) is calculated. If so, I think it could be better to make it clear in your manuscript.
- If the parameter $\epsilon_{\inf}$ is set to a very small value (like 0.1 or 1), it is possible that a lot of words in the original text would be perturbed. In this case, is it still reasonable to say the perturbation is unnoticeable? For example, in section 4.1, there are 50% and 31% of the features (I assume it means words) being perturbed. If 50% of words are perturbed in some texts, I think we can notice such changes as a human. A related but different question: what are the ratio of perturbed words if we set $\epsilon_{\inf}$ a little bit larger?
- A general question about your experiments: how does the test accuracy computed? If we only wish to attack one node, is it more reasonable to test the success rate (like waht the authors did in appendix). Or does it mean that the overall test accuracy can drop that much if we only perturb one node in the graph? This is a little bit unclear in the manuscript (or please point it out if there is something I missed).
- About the analysis on distance between attacker and victim nodes, it seems the test accuracy of cora and pubmed does not change once the # layers reaches to 5. How many different rounds of experiments do the authors conduct in this part? If an attacker node is randomly chosen, you cannot always find a victim node v that has a large $d(a, v)$. If the authors want to study the effect of distance, maybe the attacker node needs to be carefully chosen.
- In section 4.4, does the attacker still use GCN as base model (or imitation model) to attack GAT, GIN and GraphSage? If so, does the number of layers in imitation model remain the same as the attacked true model? What would happen if the number of layers in imitation model is different from the attacked model? I think all those models have some sort of nonlinearity baked in the model. Just for my curiosity, I wonder what would happen if we use a simpler model like SGC (without any nonlinearity) as the imitation model.
- Just some minor comments, I sometimes got confused about 'attacker node' and 'victim node'. It would be better if the authors can clearly define it somewhere in the paper or mark them (which one is which) on figure 1.
review_title: Official Blind Review #4

final_score: rating: 6: Marginally above acceptance threshold
review_content: # summary #
This paper studies a problem of attacking graph neural networks. 
Especially, the paper focuses on the single node attack while most of the attack studies focusing on edges. 
The paper claims that attacks on multiple edges (and nodes) are difficult to conduct in practice. 
Considering the single node attack is important since injecting a new single node, or a manipulation on one vulnerable node is less difficult. 
The studied problem is an evasion attack on a node feature vector of a single node. 
Untargeted and targetted attacks are both formulated with a gradient-based update of a perturbation vector. The proposed attack method perturbates BoW count vectors, not the embedded continuous vectors. 
Experimental results show that the proposed single-node attack is more effective than a single-edge attack. Also, the single-node attack is not much weaker than the two-nodes attack experimentally. 

# comment #
I am not an expert on the attacks of GNN. However, this manuscript is easy to read for non-expert readers like me. 

Single-node interventions for GNNs sounds realistic than attacks on multiple edges. 
I feel a node injection (add a new malicious node to a graph) is also a possible scenario but the paper does not consider this case. Any comments? 

I find no obvious concerns about the methodology. However, I have a few questions concerning the experiments. 

Table 1: 
I'm not sure comparisons between the proposed SINGLE method and the baseline EdgeGrad method are fair comparisons, in terms of the amount of perturbations on graphs. 
The proposed SINGLE method manipulates 15%, 50%, and 31% of the feature attributes for PubMed, Cora, and CiteSeer, respectively. 
However, the counterpart EdgeGrad always manipulates a single edge. Is a single edge manipulation a (roughly) same amount of perturbations of MULTIPLE attribute manipulations of the SINGLE method? 
An average degree (number of edges a node has) will be a good measure to check this issue. Is it possible to add an average degree to Table 4? 

Table 3:
I'm curious about the differences between SINGLE-two attackers and the SINGLE. 
The two-nodes attacks perform inferior 3 out of 4 datasets than the single-node attacks. 
This conflicts with a naive guess: multi-node attacks is stronger than single-node attacks. 
So I think many readers will expect some intuitive explanations. Gradients from two nodes harm each other in optimization? What will happen if we choose three, or more attackers? 


# Evaluation points #
(+) Single-node evasion attack on GNN is first in the literature

(+) Readability

(-) I'm not fully sure about the fairness of parts of the experiment Table 1. 

(-) No explanation in why two-nodes attacks are not superior to the one-node attacks. 
review_title: ICLR 2021 Conference Paper421 AnonReviewer1

Meta-review: The paper deals with adversarial attacks on graph neural networks, a new and promising field in graph representation learning. The paper analyzes a new extreme setting of attack for a single node, and presents important insights, albeit not new algorithms.

The reviewers were not particularly enthusiastic and complained about
- limited novelty in light of Zuegner et al
- missing baselines
- doubts about the attack setting with a selected attacker node

The authors provided an elaborate rebuttal, including specific responses to the above questions, however, the final scores are not quite above the bar, especially having in mind the sheer number of submissions on graph deep learning this year. We, therefore, recommend rejection and encourage the author to publish the paper elsewhere. 

Decision: Reject