Provable Adversarial Robustness for Group Equivariant Tasks: Graphs, Point Clouds, Molecules, and More

Summary

This paper studies the robustness certification for equivariant tasks. Specifically, the adversarial robustness with group equivariance is defined in terms of the input and output distance. Then equivariance-preserving randomized smoothing is introduced as well as various smoothing schemes. Experiments show that robustness guarantees can be obtained via equivariance preserving randomized smoothing.

Strengths

- The motivation of studying robustness with equivariance is clear and the problem is well formulated. - The theory part looks sound and detailed and the paper is well organized.

Weaknesses

- There are not enough baselines to show that the equivariance can improve the provable robustness as claimed on line 8 in the abstract. It is expected to compare with some previous works to back up the claim that prior work underestimates the robustness as line 399 states. - If I understand correctly, the permutation invariant task is a special case of equivariant task as the experiment of point cloud classification shows. Therefore, transformation specific robustness work [1, 2, 3, 4] can be involved like image/point cloud classification against 2D/3D rotation or translation. It will be of great interest to discuss the connection between these resolvable/non-resolvable transformations and group equivariance. - Each experiment needs more justifications for choosing different smoothing schemes and measure types. - The notations in section 3 regarding measure-theoretic randomized smoothing are a bit confusing and not easy to follow. It is better to explain each domain notation ahead and explicitly. --- [1] Li, Linyi, et al. "Tss: Transformation-specific smoothing for robustness certification." *Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security*. 2021. [2] Chu, Wenda, Linyi Li, and Bo Li. "Tpc: Transformation-specific smoothing for point cloud models." *International Conference on Machine Learning*. PMLR, 2022. [3] Hu, Hanjiang, et al. "Robustness Certification of Visual Perception Models via Camera Motion Smoothing." *Conference on Robot Learning*. PMLR, 2022. [4] Hao, Zhongkai, et al. "Gsmooth: Certified robustness against semantic transformations via generalized randomized smoothing." *International Conference on Machine Learning*. PMLR, 2022.

Questions

Summary of rating: I am most concerned with the first bullet point in Weaknesses where more experiments are expected to support the claims. I would be happy to raise my rating if it is well addressed

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

Yes

Summary

The paper investigates adversarial robustness for group equivariant tasks. To this end, the authors propose a novel notion of adversarial robustness: An attacker aims to find a perturbation $x'$ "close" (up to some distance constraint in the input space) to a natural input $x$. For this perturbation, they aim to find the worst-case perturbation within the input constraint and over the group of symmetries over the input. By a model equivariant to the underlying group, this reduces to classical adversarial robustness. Further, the paper shows that randomized smoothing, a popular framework for making models provably adversarially robust, (and many of its variants) can fulfill this notion of robustness when the underlying model, distribution, measure, and smoothing scheme are equivariant. Several instantiations of this approach are showcased on a variety of tasks, including graphs, point clouds, and molecules.

Strengths

- Well written and easy to read - The proposed definition for adversarial robustness is a) novel, b) a natural extension of the classical definition, and c) well motivated - The section on the different variants of randomized smoothing and their relation to the problem is extensive - I appreciate the combination of semantic preserving change (here the group action) and perceptual noise in the set of admissible perturbations and think this is a promising direction for the field.

Weaknesses

- No investigation of the robustness notion directly, i.e., no attacks against undefended models where performed to showcase the issue - Some further disambiguation from related work might be helpful to the reader (see below)

Questions

- It seems that the described notion of adversarial robustness requires knowing the inherent equivalences in the data. However, for sufficiently complex data many of the underlying symmetries are not known. Could the notion of robustness be applied in such cases? - In the conclusion the authors state equivariant robustness guarantees for non-equivariant models as a future direction. It seems that this is the approach already taken in [53,50,77 (Appendix B.5)]. Thus, while these target a fundamentally different setting, could you comment on the difference and relation to these works, particularly when viewed through the novel notion of robustness?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

3 good

Contribution

4 excellent

Limitations

Limitations are adequately discussed in the paper.

Summary

In this paper, it propose equivariance-perserving randomized smoothing to provide the robustness of the GNN model. The proof demonstrates the provably robustness of the proposed smoothing method.

Strengths

1. The theoretic guarantee of this paper is strong. And the proposed random smoothing methods can be applied on multiple tasks including the point cloud classification and the force field prediction.

Weaknesses

1. The experiment of Figure 4 can contain more geometric GNN such as Spherenet (https://arxiv.org/abs/2102.05013), and GemNet,(https://arxiv.org/abs/2106.08903) to demonstrate. 2. The math part of this paper is a little hard to follow. Maybe some some figures or concrete descriptions on how to apply the proposed smooth techniques can help people understand better.

Questions

What is the model settings of the DimeNet++ in Figure 4? What is the performance compared to reported results?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

1: Your assessment is an educated guess. The submission is not in your area or the submission was difficult to understand. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

2 fair

Contribution

2 fair

Limitations

Is there any experiments showing the performance of model when no smoothing techniques are used? I think it can provide the reason why such smoothing technique is needed.

Summary

Authors note that the definition of adversarial robustness needs to be adjusted in cases when the problem is equivalent - for example, graph perturbations that are large in terms of the number of removed/added edges might actually be small if we take into account graph isomorphism (eg if a large graph perturbation ends up not change the graph topology much). Effectively, authors propose (Proposition 1) to change to notion of the distance between inputs x and x’ in the definition of adversarial robustness to equal the minimal distance between x and all elements of the equivalence class of x’ (eg all permutations of x’ if the input domain is graphs, or all translations and rotations of x’ if the problem is translation and rotation equivariant = use set registration distance between x and x’ to define adversarial robustness of the translation+rotation equivariant task). Then authors argue that symmetries in the output domain should also be accounted for (Def 1) which is often hard, but can be skipped entirely (Proposition 2) if the model itself is equivariant by construction. Then authors argue that the notion of smoothing distribution can (and should) take into account the updated notion of distance between points and that this definition allows that to theoretically justify several existing equivariant smoothing schemes and define more generalized notions of robustness (e.g. Eq 2). Authors note that in many cases computing such distances is computationally hard (e.g. NP-hard when working with permutation equivariance groups). Authors measure their updated equivariance-aware adversarial robustness of PointNet and DGCNN on permutation-invariant problem of ModelNet40 classification, of DimeNet++ on rigid-transformation-equivariant regression on MD17, and on graph convolutional DNN on permutation-equivariant node classification with several notions of graph edit distance (weight of deletion/insertion).

Strengths

The paper is relatively easy to follow and sound. The motivation makes sense. Authors provide a formal generalization of the intuitive notions of how to measure distances between inputs in problems that have natural symmetries and having a shared language might be useful as a reference for future research.

Weaknesses

My main concern with this paper is that it proposes a shared general formalization for the intuitive procedure that people have been already using extensively across many tasks with symmetries (eg rigid-aligned error in pose estimation), but this formalization that does not appear to bring much value beyond defining “shared language” and identifying “generalized knobs” that one can tweak to get slightly varied definitions of adversarial robustness. While reading the paper, I was hoping that authors would provide some kind of surprising practically useful result that makes use of their generalized definitions (eg a general algorithm that lets us compute such distances efficiently), but that did not happen - all presented results appear to be mathematizations of observations we already take for granted (eg if the model is equivariant by construction, there’s no need to invert its outputs because they are already “canonical”). One good example of a paper that worked with symmetries, introduced some simple new general definitions, and proved something surprising and practically useful from that point is “Training Generative Adversarial Networks with Limited Data” by Karras et al (see Appendix C). I might be wrong, so I would appreciate input from other reviewers.

Questions

See weaknesses.

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

3 good

Contribution

2 fair

Limitations

Authors acknowledge that their approach is applicable only to equivariant models.

Summary

This paper presents several contributions to the field of adversarial robustness for group equivariant tasks. The authors propose a sound concept of adversarial robustness for these tasks and demonstrate that using equivariant models can facilitate achieving provable robustness. They also prove that various randomized smoothing approaches preserve equivariance and extend existing robustness certificates for graph and node classification from $l_0$ perturbations to graph edit distance perturbations with user-specified costs. The paper underscores the importance of reevaluating adversarial robustness in equivariant tasks for future research in robust and geometric machine learning. Extensive experiments were conducted in various settings to validate the claims of the proposed method.

Strengths

- The paper presents a novel definition of adversarial robustness for group equivariant tasks, which is a significant contribution to the field. The $\epsilon-\delta$ definition is interesting. - The paper provides theoretical proofs for the soundness of their proposed notion. - The proposed method is applicable to a wide range of tasks, including graphs, point clouds, molecules, and more. - The paper includes experimental results that validate the theoretical claims, providing empirical evidence for the effectiveness of the proposed method.

Weaknesses

I think this paper is innovative and sound in general, and just want to list a few things to address below: - While the proposed definition of robustness in this paper specifically tailors toward group equivariance tasks, I am wondering how it can address the limitations and problems with the previously used definition. In figure 1 and figure 2, the authors give two examples related to graph isomorphism and rotation – how would the flaws in the old notion of robustness cause issues in applications related to those scenarios? For instance, one potential setting of graph node classification attacks is making imperceptible insertions/deletions to the recommendation graphs (example attacks in [1] and [2]). How will this new notion of robustness affect the consideration of attacks when grounded to those specific tasks/applications? [1] Daniel Zügner, Amir Akbarnejad, and Stephan Günnemann. Adversarial attacks on neural networks for graph data. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 2847–2856, 2018. [2] Daniel Zügner and Stephan Günnemann. Adversarial attacks on graph neural networks via meta learning. arXiv preprint arXiv:1902.08412, 2019.

Questions

Although the paper mainly focuses on certified robustness, will this new notion of adversarial robustness for group equivariant tasks have any implications for the design of new adversarial attacks & defenses? If so, can you discuss some potential directions for proposing new attacks & defenses with respect to this definition?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

The authors adequately addressed the limitations.

Summary

This paper provides a new insight into adversarial robustness for equivariant tasks (like graph classification) where we need to separate the perturbations that occur according the allowable transformations (that actually form a group) - and where we'd like to have the same output disregarding the norm of perturbation - and harmful perturbations, where we need to care about its norm.

Strengths

The novel work stating the very important question: what is the objective for the adversarial robustness for inputs which are equivariant according to some group of transformations? Although the task seems very vague, the authors answered it in a very elegant manner by: - introducing the new distance $\hat{d}_{in}$ which should be invariant w.r.t. to the group transformations - introducing two properties of this new distance (upper bound as usual distance $d_{in}$ + being the max of such distances) - and finally proving the Proposition 1 that shows that $\hat{d}_{in}$ is actually min among usual distances w.r.t. group transformations for one of its input. Based on it, the authors came to a definition of adversarial robustness for group equivariant tasks, which can be shrunk to the usual definition of adversarial robustness when we don't have the group properties, or compatible with other group-invariant distances like Hausdorff and Chamfer ones. Moreover, they proved the following (Proposition 2): if a model is equivariant w.r.t. to the group transformations, then the new definition it is equivalent to being robust in the usual sense. As a result, we just need to prove the usual robustness (for which we have a number of techniques like Certified Smoothing) for an equivariant model.

Weaknesses

During the discussion in "Related Work / Transformation-specific robustness" (line 88), and even more seriously during "Product measures" (lines 287-288), it makes sense to mention the work [1] where the interesting usecase was studied: - multiplicative group of the "gamma correction" image transformations - Rayleigh distribution to serve as a smoothing distribution Would be interesting to know how it fits into the proposed framework. Additionally, how the proposed framework is dealing with interpolation error (e.g., [1], [2]) which is very non-trivial and is out of group properties, is not mentioned in the paper. [1] Muravev, Nikita, and Aleksandr Petiushko. "Certified robustness via randomized smoothing over multiplicative parameters of input transformations." Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, 3366-3372, 2022. [2] Marc Fischer, Maximilian Baader, and Martin Vechev. Certified defense to image transformations via randomized smoothing. Advances in Neural information processing systems, 33: 8404–8417, 2020.

Questions

The main question is why do the authors provide multiple experimentation results if according to their theoretic results we can just re-use any existing methods provided for usual adversarial robustness? We just don't need to implement anything.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

According to the text, there is a statement: "prior work drastically underestimates the strength of the adversary and actually proves robustness for significantly larger sets of perturbed inputs" (e.g., lines 398-400). Is there any : - empirical proof for it? - theoretical consideration reasons for it? Probably the answer was somehow blurred inside the text, would love to hear the clear explanation for it.

Reply

I thank the authors for their reply. I'm delighted by the suggested discussions to be include. Currently I do not have any further questions.

Thanks!

I thank the authors for their reply. I'm grateful for the suggested discussions to be included. Currently I do not have any further questions. My main concern still is that the group structure is nice in theory but in practice it is usually broken by multiple real considerations (like interpolation), so would be nice somehow to make "almost" group structure research in the future :)

Response to Authors

Dear Authors, Thank you for the comprehensive rebuttal and the clarifications provided. At present, I have no further questions and am willing to raise my rating to weak accept. Best regards, Reviewer y2Vs