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

A machine learning model is traditionally considered robust if its prediction remains (almost) constant under input perturbations with small norm. However, real-world tasks like molecular property prediction or point cloud segmentation have inherent equivariances, such as rotation or permutation equivariance. In such tasks, even perturbations with large norm do not necessarily change an input's semantic content. Furthermore, there are perturbations for which a model's prediction explicitly needs to change. For the first time, we propose a sound notion of adversarial robustness that accounts for task equivariance. We then demonstrate that provable robustness can be achieved by (1) choosing a model that matches the task's equivariances (2) certifying traditional adversarial robustness. Certification methods are, however, unavailable for many models, such as those with continuous equivariances. We close this gap by developing the framework of equivariance-preserving randomized smoothing, which enables architecture-agnostic certification. We additionally derive the first architecture-specific graph edit distance certificates, i.e. sound robustness guarantees for isomorphism equivariant tasks like node classification. Overall, a sound notion of robustness is an important prerequisite for future work at the intersection of robust and geometric machine learning. decreases robustness to ℓ p perturbations and vice-versa [21] [22] [23] [24] [25] . Schuchardt and Günnemann [26] used knowledge about the invariances of point cloud classifiers to prove that they are constant within larger regions than could be shown using previous approaches. Group invariant distances. Recently, stability results for graph classifiers under isomorphism invariant optimal transport distances have been derived [27] [28] [29] . For point cloud classifiers, using the permutation invariant Chamfer or Hausdorff distance to craft attacks has been proposed [30, 31] . These works only focus on invariance and specific domains and do not consider that distances should be task-dependent: A rotation invariant distance for images may be desirable when segmenting cell nuclei, but not when classifying hand-written digits, since it would fail to distinguish 6 and 9. String edit distance. In concurrent work, Huang et al. [32] use randomized smoothing to prove robustness of classifiers w.r.t. string edit distance, i.e., the number of substitutions that are needed to convert one string from alphabet Σ ∪ ⊥ into another, up to insertion of alignment tokens ⊥. Their work further emphasizes the need for invariant distance functions in domains with symmetries, and the usefulness of randomized smoothing for proving robustness w.r.t. such distances. Robustness of models with equivariances. Aside from work that studies invariance and adversarial robustness jointly, there is a rich literature investigating the robustness of models that happen to have equivariances. This includes convolutions [5] [6] [7] 33] , transformers [34] [35] [36] [37] , point cloud models [30, 31, [38] [39] [40] [41] [42] [43] [44] [45] [46] and graph neural networks [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [47] [48] [49] [50] [51] [52] [53] [54] [55] . The models are however treated as a series of matrix multiplications and nonlinearities, without accounting for their equivariances or the equivariances of the tasks they are used for. Nevertheless, many methods can actually be reused for proving (non-)robustness under our proposed notion of adversarial robustness (see Section 5). Transformation-specific robustness. A subfield of robust machine learning focuses on robustness to unnoticeable parametric transformations (e.g. small rotations) [42, 46, [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] . These works implicitly assume that large transformations lead to easily identifiable out-of-distribution samples. This is not the case with equivariant tasks: For instance, a molecule rotated by 180 • is still the same geometric object. Furthermore, they do not consider unstructured perturbations. Nevertheless, transformation-specific robustness can be framed as a special case of our proposed notion (see Appendix J). Semantics-aware robustness. Our work is closely related to different proposals to include ground truth labels in the definition of adversarial robustness [22, 52, [66] [67] [68] [69] [70] [71] . A problem is that the ground truth is usually unknown, which limits experimental evaluation to simple data generating distributions [52, 70] or using human study participants [22, 67, 71] . Geisler et al. [72] overcome this problem in the context of neural combinatorial optimization by using adversarial perturbations that are known to change the ground truth of a decision problem. Group equivariant tasks admit a similar approach, since we know how the ground truth changes for specific input transformations.