Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: ** I have checked the author feedback **

This paper studies adversarial attacks to graphs and proposes ‚black-box‘ Bayesian optimization (BO) to find harmful perturbations. Moreover, the authors analyze the properties of adversarial examples to increase understanding of the topology of attacked graphs.
main_review: Originality:
1) The usage of BO to attack graph classification models is new. Though, BO has been used on black-box attacks before in the image domain. 

2) A new challenge with the application of BO on graphs is discreteness which is handled through the encoding through WL feature extraction. However, it would have been beneficial to investigate in more detail the effect of this feature extraction (e.g. how does the approach perform with other features?)

Quality:
1) The paper only evaluates the approach empirically. However, the evaluation could be more comprehensive. The authors could include more baselines to compare to (e.g. Nettack). The baseline GA is also used as a component of the proposed technique, and the „white-box“-method is difficult to compare to. Also, the Sequential Random in Fig. 12 in the App. F should be evaluated in more detail. In particular, there it is performing on par with the proposed approach. Furthermore, it would be interesting to see how the approach performs 2-hop and 2-hop + rewire experiments compared to the baselines.

2) All empiric results are evaluated over the number of queries. An additional runtime comparison would be interesting as another metric. In general, I feel that it would be beneficial to discuss more carefully the comparison (e.g. the white-box attack is not using any query budget at all; however, requires access to the parameters; is such a comparison fair?). Potentially it would be helpful to include more baselines which require/use the same set-up (this is partially done in App. F; but as discussed above not really in detail).

3) The attack analysis is highly beneficial. However, it could be improved through the evaluation of statistics. Currently, it is unclear how many samples were evaluated. Also, it would be great if the analysis would include different approaches as a comparison to see if there is a difference between what the proposed approach attacks compared to a baseline and what makes it more successful. Moreover, analysis of the patterns of attacks have been performed in other work which should be discussed be the authors (e.g. "Wu H, Wang C, Tyshetskiy Y, Docherty A, Lu K, Zhu L (2019) Adversarial examples for graph data: Deep insights into attack and defense" and "Zugner D, Borchert O, Akbarnejad A, Gunnemann S (2020) Adversarial attacks on graph neural networks: Perturbations and their patterns")




Clarity:
1) The paper has a good structure, is well written, and good to follow.

2) It seems to be counterintuitive why Nettack is not chosen as a baseline when it is discussed the most in related work.

3) Fig. 5 should be clarified: how many edges are on the graph, what dataset it is etc. 

Significance:
1) With a more extensive study on the attack analysis including a discussion of existing works as well as a couple of stronger attack baselines (see point above) this work could add significant insights into the domain of graph classification attacks. 
2) The application of BO on graph classification in combination with the analysis adds the opportunity of using more informed strategies (as briefly highlighted in Appendix G, constraining the search space)


limitations_and_societal_impact: 1) Limitations are not really discussed. Especially the strong baseline sequential random should be discussed in the main paper. With respect to the runtime, an argument could be made that sequential random could be better in some cases. However, the opportunity to use more informed decisions within the framework of the proposed approach would still make it interesting. This would make the limitation discussion sounder. 

2) Clearly, the attack has a potential negative impact, especially on the Twitter environment. But this point is discussed, and new defenses are said to be future work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors propose an adversarial attack method for graph classification models. Specifically, the method is based on Bayesian optimization and uses a genetic algorithm (GA) as the acquisition function and a Bayesian linear regression surrogate model which provides the fitness scoring for the GA. The approach is greedy in the sense that it selects the best perturbation in a stage and then proceeds to the next one. The authors evaluate their method on a set of standard graph classification datasets ("TU Datasets") as well as on a graph version of MNIST and on a Twitter dataset. 
main_review: The paper is well-structured and the presentation is clear. The method seems novel, though Bayesian Optimization and graph classification attacks are not my core field of expertise. Overall I am not opposed to publication as the results appear to be stronger than the baselines.

Nevertheless I do have some concerns / questions:
* What is the empirical runtime of the attack? Since the method performs a GA for **each** graph in a dataset, it seems to be quite expensive.
* Another main concern is that the authors do not evaluate any defenses. While there may not be many defenses for graph classification attacks, I would expect that defenses for node classification (e.g., [Zhang and Zitnik 2020], [Geisler et al. 2020]) could improve robustness.
* In many of the result figures, it seems that the proposed approach performs worse than random for a small number of queries. What is the reason for this and how can it be addressed? It would also be interesting to list the "break-even" number of perturbations per dataset evaluated.
* How is the second requirement of the surrogate model (probabilistic interpretation of uncertainty) used in the present work? 
* On a related note, what is the performance of the model when using a standard $L_1$- or $L_2$-regularized linear regression surrogate model?
* Why does Table 1 show validation and not test accuracy?
* Are the initialization points counted towards the global budget $B$? In Algorithm 1 it seems like they are not counted towards $B$, which would be counterintuitive.
* Why are there no results for Cheby-GIN in Table 1?
* Why does the gradient-based baseline perform much worse than random on PROTEINS?
* How to adjust the surrogate model for injected nodes? From the description I understand that injecting a node can lead to a longer vector representation of the graph (i.e., more entries). Therefore, the number of parameters $\alpha$ and $\lambda$ of the surrogate model do not fit the graph representation any more. How is this resolved?
* For the case of continuous node features, it seems like the resulting feature vectors can be very high-dimensional ($H\cdot D \cdot N$), where $D$ is the feature dimension. Does this pose a problem of the method for large graphs?
* Remark about the "Beware the low-degree nodes!" point. Since on Twitter the victim model is a GCN, this comes as no surprise: the weight in the neighborhood aggregation of node $j$ is proportional to $\frac{1}{\sqrt{d_j}}$, i.e., lower-degree neighbors have larger influence in the neighborhood aggregation in GCN. This was also discussed by Zügner et al. (TKDD 2020).
limitations_and_societal_impact: The authors do have a short section on limitations. In the case that the empirical runtime is very large, I recommend to list this also as a limitation of the approach.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes GRABNEL, which formulates the adversarial attack on graph classification as a black-box optimisation problem and uses Bayesian optimisation to solve it. Experiments on multiple datasets demonstrate the effectiveness of the proposed method.
main_review: Originality: The technical contribution is incremental, which heavily limits the significance of the proposed method. To be specific, Weisfeiler-Lehman (WL) feature extraction methods and Bayesian optimization (BO) are well-known techniques, and the combination of them in this work is straightforward.

Quality: The proposed method is well motivated and is technically sound. Although the attack analysis part provides some insights into the robustness of graph classification models, the last two claims are not well supported by empirical verification.

Clarity: The paper is well organized and articulated in general. 

Significance: The comparison experiments are not convincing. The authors are encouraged to compare the proposed method with more recent SOTA methods, rather than one method that was published in 2018, on more benchmarks, e.g., AIDS, DHFR or Bitcoin. Besides, for the image classification and Fake news detection tasks, it will be more convincing to report the results of other competitive methods.

limitations_and_societal_impact: One limitation of this work is that the proposed method is only applicable for graph classification models. The authors claim that some progress will be made in future work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes a query-efficient and parsimonious attack method for graph classification models based on Bayesian optimization. Attacks are performed under the black-box evasion setting by flipping or rewiring edges and injecting nodes. Besides, the authors provide insights between topological properties of perturbed graphs and graph classification models. 
main_review: Strengths:
- Both the problem of adversarial attacks on graph classification and attack modes of rewiring edges as well as node injection is rarely researched, which shows the novelty of this work.
- The experimental results are strong. Various domains of datasets are used and different attacking strategies are exploited in the experiment. 
- The attack analysis of the relationship between robustness and topological patterns of adversarial samples is interesting and could provide insights for further graph robustness research.

Weakness:
-	The black-box setting used in this work falls into the approach with a specific surrogate model. There are several works considering the black-box setting without a surrogate model, such as [1-3]. Though their focuses are on the node classification side, the relationship with this line of research is suggested to be discussed either. 
-	The computation analysis of the total attack process should be demonstrated. The authors only provide the complexity of the surrogate model and neglect that of sequential perturbation selection and acquisition function optimization. The complexity analysis is crucial when using large-scale graphs as one strong motivation from authors to choose a proper surrogate model. Further, it would be better if the running time analysis is provided.
-	For the experimental results, why there is no comparison between RL-S2V and GRABNEL on real-world datasets? Meanwhile, the advantage of GRABNEL over RL-S2V is not strong enough on the ER graphs.
-	If possible, I would suggest exploiting additional hierarchical graph classification models in experiments. GCN and GIN are strong classic graph classification models but two victims are kind of weak, especially considering GCN is not very powerful for graph classification tasks. Therefore, other SOTA hierarchical models like DIFFPOOL[4] and G-U-Nets[5] which are also essential parts for graph classification tasks are suggested to be selected as targets.

[1] Towards More Practical Adversarial Attacks on Graph Neural Networks, NeurIPS 2020

[2] Adversarial Attacks on Node Embeddings via Graph Poisoning, ICML 2019

[3] A Restricted Black-box Adversarial Framework Towards Attacking Graph Embedding Models, AAAI 2020

[4] Hierarchical graph representation learning with differentiable pooling, NeurIPS 2018

[5] Graph u-nets, ICML 2019

limitations_and_societal_impact: The limitations and potential negative societal impact are discussed in the Conclusion, though not adequately which could be due to the space limitation.

The authors are suggested to further describe both of the limitations and social impact from multiple perspectives more in details, such as the user privacy issue when evaluating on the real-world Twitter dataset.
review_title: null

Meta-review: This paper provides a new Bayesian Optimization approach to developing adversarial attacks on graphs. While some prior work has used a similar approach for other domains (e.g., images), it seems that the authors are the first to develop a successful attack methods for graphs in this way. The reviewers felt that the experiments were mostly thorough and at least were convinced about the contributions of this paper. Moreover, there was a lot of discussion, but the reviewers seem to have reached consensus with the authors on the major issues. Therefore, I recommend acceptance of this paper. 

Given the lengthy discussion, I would strongly encourage the authors to be thoughtful and thorough in the revision for the next version of the paper. It seems that many of the reviewer concerns can be directly addressed in the paper by improving the writing and exposition. 
Decision: Accept (Poster)