Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper investigates relational adversaries, which craft adversarial examples via an arbitrary number of transformations. Based on the theoretical analysis of the robustness-accuracy trade-off, the authors propose normalize-and-predict, a learning framework that leverages input normalization to achieve provable robustness. Experiments on source code authorship attribution and malware detection verify the proposed method.
strengths_and_weaknesses: ### Strengths 
- The considered adversarial robustness against relational adversaries is well defined. This problem would be important to the community.
- The three levels of the robustness-accuracy trade-off are interesting and insightful. The second and third cases indeed happen in practice.

### Weaknesses
- Although it is well-known that there might exist a robustness-accuracy trade-off in defending against $\ell_p$ attacks, it is still necessary to cite relevant papers in the main text for reference. Moreover, while it is true that robustness against $\ell_p$ attacks may be at odds with accuracy, it does not mean that the trade-off is inevitable. For example, human visual systems are known to be simultaneously robust and accurate under small $\ell_p$ perturbations. 
- This paper claims that the robustness-accuracy trade-off exists for learning against relational attacks and depicts three levels. However, the claimed trade-off relies on relational adversaries being able to change labels with feasible transformations. This is very different from the $\ell_p$ attacks in the image domain, where small perturbations hardly change the ground-truth labels. If the ground-truth labels are allowed to be different, then is not surprising that the trade-off occurs.
- The effectiveness of the proposed framework depends heavily on the specified transformations. It would be unrealistic to assume that all the transformations the attacker can apply can be known in advance.

== Post rebuttal ==  
Based on the rebuttal, I have decided to increase my score to weak accept.
questions: Is the reason why there is a trade-off between robustness and accuracy in defending relational opponents different from $\ell_p$ attacks?
limitations: A major limitation is that the effectiveness of the proposed framework depends heavily on specified transformations, some of which may be unknown to the defender.
review_title: null

final_score: rating: 9: Very Strong Accept: Technically flawless paper with groundbreaking impact on at least one area of AI/ML and excellent impact on multiple areas of AI/ML, with flawless evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors first provide the definition of relational adversaries and then propose normalize-and-predict framework for a robust classifier against those adversaries. They show how to obtain the optimal normalizer for normalizing the model's input. Then, they apply the adversarial training to deal with the robustness-accuracy tradeoff. As a result, their approach can outperform state-of-the-art defenses (e.g., adversarial training).
strengths_and_weaknesses: Strength
The approach is promising with the theoretical proof for the normalizer. Also, it can empirically outperform the state-of-the-art defenses in terms of robustness and the tradeoff.   

Weakness
There is only two datasets in the experiment. It would be better to see more datasets.
questions: I have no question regarding this paper.
limitations: The authors provide how they deal with the negative societal impact very well.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper studies robustness against relational adversaries, a broad class of attackers who create adversarial examples in a reflexive-transitive closure of a logical relation and is motivated by attacks in program analysis and security tasks. Specifically, the paper first analyzes the conditions for robustness against relational adversaries and investigates different levels of robustness-accuracy trade-off.  Inspired by the insights, the authors propose normalize-and-predict (N & P), a learning framework that leverages input normalization to achieve provable robustness by design. The framework can be also combined with adversarial training ti further enhance the robustness. The proposed framework is tested on source code authorship attribution and malware detection and significantly improves the robustness of models against relational adversaries.  
strengths_and_weaknesses: Strengths

+ Paper is well-written and well-organized 

+ The studied problem is novel 

+ The proposed N & P is novel and theoretically grounded



Weaknesses

- I do not see any serious weaknesses 
questions: How can you generate the “equivalence group” in general real-world problems? Is there any possible automatic way?   

How accurate is the proposed efficient normalization, compared to the exact normalization? 

Can you comment on: whether and how the robust learning results of the N & P + AdvTrain can be used to provide model explanations?  
limitations: The authors adequately addressed the limitations and potential negative societal impact.
review_title: null

Meta-review: metareview: This paper studies relational adversary, a general threat model in which adversary can manipulate test data via transformations specified by a logical relation. Inspired by the conditions for robustness against relational adversaries and the sources of robustness-accuracy trade-off, the authors propose a learning framework called normalize-and-predict, which leverages input normalization to achieve provable robustness. Experiments on two tasks verify the effectiveness of the proposed method. 

Overall, the paper is well organized and presented. It proposes a novel and technically sound defense mechanism and takes the first step towards robust learning against relational adversaries. The author responses have address reviewers' concerns, and all reviewers finally agree on the acceptance.
confidence: Certain
Decision: Accept