Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: The paper proposes a new one vertex adversarial attack to evaluate the robustness on deep spatialtemporal graph neural network. First, it formally defines the adversarial attack into optimization problem and uses a genetic algorithm to solve it. 

Pros:
1. To my best of knowledge,  none adversarial attack has been applied to spatialtemporal graph neural network. And the spatialtemporal graph neural network has its uniqueness in terms of unfixed input and graph property.
2. The attack performance seems reasonable.

Cons:
1. While it has proposed a new attack towards the spatialtemporal graph neural network, the novelty of the proposed method is not significant. It could just be treated as attack the node features on a normal graph neural network to predict the next node' label. 
2. The difficulty of unfixed or interactive input on spatialtemporal graph neural network is avoided instead of solving it. There are some papers like [1][2] that already attack the interactive input and address the problem instead of avoiding it. 
3. The universal attack claimed is not actually a universal attack. The universal attack is defined to use a common perturbation on features on every node instead of just one node. I suggest to take out the universal claims.
4. While attacking the node attributes or features, it would be more interesting to utilize the graph topology as well, which is commonly discussed on the adversarial attacks related to graph neural networks.
5. The constraint on the perturbation is actually a l2 constraint however it is a soft constraint. I am not sure whether the constraint is strictly forced. If not, how to measure the node feature's similarity after the perturbation?


[1] Cheng, Minhao, Wei Wei, and Cho-Jui Hsieh. "Evaluating and enhancing the robustness of dialogue systems: A case study on a negotiation agent." Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers). 2019.

[2] Gleave, Adam, et al. "Adversarial policies: Attacking deep reinforcement learning." arXiv preprint arXiv:1905.10615 (2019).
review_title: The attack only focuses on a very small part on the spatiotemporal neural network.

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: This paper investigates the attack of a spatiotemporal GNN and also proposing a method to find the weakest vertex for this attack. It investigates the strength of the suggested approach. The results are convincing.   It is well written with a few edits to make:
- Page 2, ln 8: Spelling of spatiotemporal 
- Page 2, Section 2, par 2: These cannot... instead of These work cannot... 
- Page 3, par 2: equation 1 should be repositioned for flow. 
- Equation 6: \min etc instead of min etc.
- Page 4, last paragraph: refer to the section by number instead of saying 'above'
- Page 5 and further: weakness and others have the speech commas facing incorrectly outwards. These could also just be removed rather. 
- Page 6, par above Table 2: Refers to the 'above results' which are actually below in Table 2 - use labels and ref. 
- There are many unpublished references included - these should possibly be reduced - many are probably now published? 
- Ref Dai 2018 has et al in it? 


review_title: Review 

final_score: rating: 4: Ok but not good enough - rejection
review_content: This paper studies the problem of attacking graph neural networks for spatio-temporal prediction problems (e.g., traffic speed prediction). The input of the problem is a spatio-temporal sequence represented as graphs at time t-N+1 to t, where a graph neural network is trained to predict the graph sequence for time t+1 to t+M. The aim is to add perturbations to the input graph sequence, such that the predicted graph sequence varies from the ground truth as much as possible. 

The novelty of the proposed attack model lies in that it does not require knowledge on the ground truth graph sequence. Instead, it uses an inverse estimation that uses the "opposite" of the graph at time t as the perturbation target. 

For efficiency and practicality considerations, the vertex that has the maximum impact on the prediction output is computed using a heuristic algorithm, and perturbation is done on this vertex only. This makes the attack more realistic as only one vertex needs to be attacked rather than the full graph. 

Pros:
1. The problem studied is interesting. Spatio-temporal prediction problems have many applications, and many recent works on such problems do use graph neural networks to make predictions. 

2. Experimental results on real datasets show that the proposed algorithms are effective and efficient. 

Cons:
1. The proposed models and algorithms are shown to be effective. One concern is on the technical depth. The modelling of the problem and the algorithms are relatively straightforward. There is a lack of performance guarantees and theoretical guidance on the choice of parameter values. For example, how much worse in terms of the attack impact when the weakest vertex is found by the heuristic algorithm instead of by a full traversal? Why is g bounded by 10 in Equation 9? Are there guidance on choosing \alpha in Equation 4 beyond "empirically"? What is the relationship between the number of vertices attacked and the impact of the attack? 

Additional comments:
How exactly are the experiments in Table 1 set up? Are all algorithms/models in Table 1 given the same input and ground truth output for the error calculation? If not (which seems to be the case based on the current wording), the comparison might be unfair. 

What are the meanings of "position" of a vertex and '-' in Equation 9? What is the intuitive idea that the genetic algorithm suits the problem to find the weakest vertex?  

What exactly does the right arrow in Equation 5 mean? Assigning \Tilde{g}_t to \Tilde{g}_{t+1}? 

The related work section claims that "these works (i.e., works on adversarial attacks against recurrent neural network) focus on regular vectors or matrices, rather than irregular graphs." It would be good to clarify the difference between "regular matrices" and "irregular graphs", since graphs are often represented by their adjacency (or vertex feature) matrices.  

Typo: Check the double quotes throughout the paper. 

**Update after author response:** I appreciate the authors' efforts to address my comments. Part of the comments on the presentation of technical details have been addressed, such as the meaning of "position" of a vertex and "-" in Equation 9. However, the main concern in terms of the technical depth has not been addressed well. There is a lack of performance guarantees and theoretical guidance on the choice of parameter values. For example, how much worse in terms of the attack impact when the weakest vertex is found by the heuristic algorithm instead of by a full traversal? The results in Section 4.2 and Table 3 are empirical and not theoretical. As such, I could not change to a more positive rating. 
review_title: A simple and effective one vertex attack method on graph neural networks for spatio-temporal prediction problems

final_score: rating: 4: Ok but not good enough - rejection
review_content: This paper proposes a single vertex based white-box attack on spatiotemporal GNNs. They solve the optimization of the least perturbations with the inverse estimation. The results demonstrate that the perturbation on one vertex can mislead the performance of the GNNs. 

Advantages: 
The idea of designing a single one vertex based attack is novel; the experiments are exhaustive, and the results validate the effectiveness of the attack method. 

Concerns: 
I think the technical contribution of this paper is weak in that: 
1. One-pixel attack [1] is not new, I don’t see some novelties in designing the one vertex attack. The only interesting point is the expansion into the new scene of attacking GNNs.
2. I'm wondering the efficiency of the one vertex attack. Is it really important to implement the one vertex attack? Besides, how's the attack success rate if the STGCN, DCRNN and Graph WaveNet are all aware of the attack method, i.e. the performance of attacks on defensed neural networks? For example, preprocessing is a routine method for defending against adversarial attacks. If the denfense side is aware of the attack, then how's the attack success rate when the attacked model is equipped with a simple filtering operation before the test sample are fed into the GNN?
3. As far as I'm concerned, the adversarial attack and defense are the arms race, I'm not surprised the one vertex attack has a strong attack success rate since it is a white-box attacked and it computes the modification by solving an optimization problem. What really matters is why it is important to attack a GNN like network and what's the novelty, since we all know that deep neural network can be easily attacked by adversarial examples. I wish to see the real discoveries rather than just adapting an attack mechanism to a new classification task. 

[1] Su J, Vargas D V, Sakurai K. One pixel attack for fooling deep neural networks[J]. IEEE Transactions on Evolutionary Computation, 2019, 23(5): 828-841.

review_title: This paper proposes a single vertex based white-box attack on spatiotemporal GNNs. 

Meta-review: This paper proposes one vertex attack for GNN, applied to spatiotemporal forecasting. The paper can be improved w.r.t novelty, incorporating graph topology and rigorous analysis. 
Decision: Reject