Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper studies the robustness of machine learning models for node prediction problems. It is well-known that GNN models are sensitive to small perturbations in the graph structure. However, it is difficult to justify which perturbations are semantically-preserved for graph-like input (which is easier for images as humans are often considered robust judgers). The authors used CSBMs to generate synthetic graphs with which the optimal Bayes classifier is derivable and then used it as the reference classifier for semantic changes. Using the Bayes classifier, the authors introduce a notion of over-robustness: the prediction of the studied classifier is not changed for a perturbed graph (which is generally known as adversarial robustness), but the prediction of the reference classifier does. They then showed that there is no inherent trade-off between semantic-aware robustness and test accuracy, similar to Suggala et al. (2019) work. Empirically, they show that most GNN models suffer from over-robustness, and using Label Propagation on top of GNNs does alleviate them.
strength_and_weaknesses: Overall, the results of this paper could bring more insight into the current understanding of adversarial robustness for GNNs. The main result that indicates no robustness-accuracy tradeoff for inductively classifying a newly added node is interesting, even though a similar result is introduced by Suggala et al. (2019). This work focuses on non-i.i.d data instead of i.i.d. data in Suggala et al. 

The study of over-robustness seems to be appealing. However, there is a concern about its practicality, as it requires the optimal (reference) classifier. Most of the analyses in this paper are on synthetic graphs. The results in Section 5.2.1 are not very significant to me. The authors should discuss how over-robustness could be avoided in real-world applications.


clarity,_quality,_novelty_and_reproducibility: Generally, this paper is well-polished and easy to read. 

- In the Introduction, Paragraph 2, the authors should elaborate more on the reasons other notions of perturbation sets (degree assortativity, other homophily metrics) are not semantically preserved.
- Section 5.2: the authors examine the over-robustness for \mathcal(B)_deg only. It would be nice to see the results with other perturbation radii.
- Page 8: The reason MLP provides an upper bound on the over-robustness for a particular K is unclear to me.
- The experiments should include other perturbation sets such as using degree distribution (Zugner et al. 2018) or degree assortativity (Li et al. 2021).


Minor comments:
- Legends of Figure 3 is not indicating dash lines.
- Citation error in paragraph 4, page 6.

summary_of_the_review: My initial impression of this paper is positive; thus, I lean towards acceptance of this paper.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors introduced a principled notion to be aware of semantic content change of an adversarial graph by  Contextual Stochastic Block Models (CSBMs). The experimental results showed for a majority of nodes the prevalent perturbation models include a large fraction of perturbed graphs violating the unchanged semantics assumption and all assessed GNNs show over-robustness - that is robustness beyond the point of semantic change. 
strength_and_weaknesses: Strength:
The authors revisted the robustness of graph neural network, and proposed a method to detect the semantic content change of an adversarial graph, which is interesting and meaningful. The presentation is good, and easy to follow. The experimental results demonstrated the effectiveness of the proposed method.

Weakness:
1) It is expected to give more details about Figure 1.

2) There are two many symbols in the paper. I suggest the authors give a table to summary these symbols for reader understanding.
clarity,_quality,_novelty_and_reproducibility: The idea of this paper is novel. It is a nice work.
summary_of_the_review: I incline to accept this paper, because of its novelty.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper discusses the semantics-preserving adversarial attack in graph. Based on CSBMs, the constructed graphs show over-robustness of GNNs. The authors also prove that GNN+LP could be one way to reduce the over-robustness.
strength_and_weaknesses: S1: Revisiting classic graph adversarial attacks from a semantic-preserving angle is novel and interesting.
S2: This paper leverages the synthetic graphs based on CSBMs and Bayes classifiers as reference classifiers to formulate the concept of over-robustness if the perturbation unnecessarily changes the semantics.
S3: The robustness-accuracy tradeoff is also discussed in inductive settings based on the constructed graphs and reference classifiers.

W1: Some works which propose the notion of unnoticeable perturbations mentioned in Introduction lack further comparison in the following part of this paper. whether these unnoticeable perturbations are semantic-preserving or not is unknown, at least from an experimental perspective.
W2: It would be better if more realistic datasets are discussed in this paper. Besides, when the CSBMs violates the real graph construction also needed more discussion.
W3: The attack algorithms used in the Results sections are targeted attacks. I wonder whether the untargeted attack like MetaAttack will also cause the same over-robustness.
W4: There are some typos in this paper, e.g., structure using is miswritten as structureusing in page 1, APPNP has no reference in page 6 section 5.

clarity,_quality,_novelty_and_reproducibility: The formulation and theoretical analysis of the semantic-preserving perturbations in graph adversarial attack is carefully defined and the proofs of the robustness-accuracy trade-off is clear. The notion of semantic-preserving for common graph adversarial attacks is novel. Moreover, the experimental setup is provided in Appendix for better reproducibility. 
summary_of_the_review: The concept of semantic-preserving perturbation and over-robustness of GNNs are interesting and attractive. The theoretical analysis based on these concepts is also sufficient. However, the authors lack more discussion with the unnoticeable perturbations mentioned in Introduction and the attack algorithm set in the experiment is relatively small.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper studies adversarial robustness of graph neural networks. The authors formally define the "semantically preserved perturbation set" based on the optimal Bayes classifier and found that many GNNs are "over-robust" with respect to this perturbation set. This new finding contradicts with previous work (which often defined "semantic preservation" in an ad-hoc way) and leads to several interesting future directions. Although all reviewers agreed that this is an interesting paper, during the zoom discussion we identified several weaknesses of the paper: 

- (Please address in the camera ready version.) The notion "over-robust" is not new to the adversarial robustness community. In fact, it has been implicitly discussed in (Jia and Liang, 2017) where they define this as "overstability". More recently, the same concept has also been discussed in (Tramer et al., 2020) in the computer vision domain, where they found many (MNIST/CIFAR) networks are over robust to semantically preserved perturbations. Please cite and discuss those previous papers in the camera ready version. 
Despite that over-robustness is not a new idea, this paper is the first formally defining and measuring it in the context of GNN. Further, the paper showed that it's possible to formally measure over-robustness in the synthetic case, where the data distribution and optimal Bayes classier is known. 

- Real world evaluation is the main weakness of this work, recognized by most of the reviewers and the AC. Since it's hard to get the optimal Bayes classifier, the conclusion on real world data is somehow questionable. However, reviewers and AC think the theoretical analysis on synthetic case is interesting enough. It will be great if the authors can discuss their limitations in real world study in the camera ready version, which may motivate future study (potentially involve human evaluation) on real world problems. 

(Jia and Liang, 2017) Adversarial Examples for Evaluating Reading Comprehension Systems. 

(Tramer et al., 2020) Fundamental Tradeoffs between Invariance and Sensitivity to Adversarial Perturbations.
justification_for_why_not_higher_score: There are weaknesses identified by the reviewers and AC, as pointed out in the meta review. 
justification_for_why_not_lower_score: This is the first paper studying over robustness in GNN, and this is the first paper connecting it with optimal Bayes classifier and formally investigate this phenomenon on synthetic data.
Decision: Accept: poster