Provable Adversarial Robustness for Group Equivariant Tasks: Graphs, Point Clouds, Molecules, and More
Authors: Jan Schuchardt
Yan Scholten
Stephan Günnemann
Venue: NeurIPS 2023 poster (2023)
Keywords: Adversarial robustness
Geometric machine learning
Equivariances
Robustness Certification
Graph neural networks
TL;DR: We propose a sound notion of robustness and robustness certificates for group equivariant tasks.

Abstract: 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.

Provable Adversarial Robustness for Group Equivariant Tasks: Graphs, Point Clouds, Molecules, and More
Jan Schuchardt, Yan Scholten, Stephan Günnemann
{j schuchardt, y. scholten,, 8. g..gunnnemann
Department of Computer Science & Munich Data Science Institute Technical University of Munich
Abstract
A machine learning model is traditionally considered robust prediction remains (almost) constant under input perturbations with small norm. However, real-world tasks like molecular property prediction 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 's semantic content. Furthermore, there are perturbations for which model's prediction explicitly needs to change. For the first time, we propose 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 gquivariance-preservinn randomized smoothing, which enables architecture-ee aggnosticc certification. We additionally derive the first urchitecture-specifie graph edit distance certificates, i.c. sound robustness guarantees for isomorphism equivariant tasks like node classification. Overall, a sound notion of robustness is important prerequisite for future work at the intersection of robust and geometric machine learning.
Introduction
Group equivariance and adversarial robustness are two important model properties when applying machine learning to real-world tasks involving images, graphs, point clouds and other data types:
Group equivariance is an ubiquitous form of task symmetry M. For instance, we do not know how to optimally classify point clouds, but know that the label calculate molecular forces in closed form, but know that the force vectors rotate as the molecule rotates. Directly enforcing such equivariances in models an effective inductive bias, as demonstrated by the success of convolutional layers [2], transformers
affected by permutation. We cannot
B and graph neural networks 4
Adversarial robustness (5-7) is generalized notion of model I. Lipschitzness: A small change model's imput x should only cause a small change to its prediction (x) If model is adversarially robust, then its accuracy will not be negatively affected by sensor noise, measurement errors or other small perturbations that are unavoidable when working with real-world data.
For the first time, we address the following question: What is adversarial robustness in tasks that are group equivariant? This is necessary because the notions of input and output similarity used in prior work adversarial robustness (e.g. lp distances) not suitable for group equivariant tasks.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Insertion
Roe(90*)
Deletion
Noise
The right graph is constructed by in- serting and deleting four edges. While their to distance is large, the graphs are isomorphic and should thus have the same set of node labels.
Figure 1:
Figure The predicted trajectory (blue) should rotate as the image rotates (green), even in the presence of camera noise and other perturbations. It should not remain constant (red).
Fig. Iillustrates why group equivariant tasks require rethinking input similarity. The right graph is constructed by modifying a large fraction of edges, meaning the perturbation of the adjacency matrix has large &o norm. Prior work [8]17] may deem it too large for node classifiers' prediction be robust. However, we know the graphs are isomorphic, meaning they are the same geometric object and should have the same set of labels. Fig. jillustrates why group equivariant tasks also require rethinking output similarity. Prior work considers prediction robust if it remains (almost) constant. But when predicting trajectories from drone footage, we know that they should rotate as the drone rotates even in the presence of camera noise. The predictions should explicitly not remain constant.
To address these two issues propose sound notion of adversarial robustness for group equivariant tasks that a) measures input similarity by lifting distance functions to group invariant distance functions and b) jointly considers transformations of the input and output space. This notion of adversarial robustness applies to arbitrary tasks, groups and distance functions.
A natural goal after introducing novel notion of robustness is developing (provably) robust models. show that robustness can be guaranteed by being robust under the traditional notion adversarial robustness if the model's equivariances match the equivariances of the task is used for. Importantly, this implies that existing robustness guarantees may actually hold for significantly larger sets of perturbed imputs. For instance, proving the robustness of graph neural network w.r.t. lu distance is in fact proving robustness w.r.t graph edit distance with uniform cost for insertion and deletion.
Although equivariant models make provable robustness more attainable, there are no certification procedures for many architectures. For instance, there is no prior work on proving robustness for rotation equivariant models. To close this gap, we develop the framework of wwwrarainnce-peeevviii randomized smoothing. It specifies sufficient conditions under which models retains their equiv- ariances when undergoing randomized smoothing increasing and proving the robustness of arbitrary models (1) In addition to that, we generalize the aforementioned graph edit guarantees to arbitrary, user specified costs. Varying these costs allows for a fine- mne-grained analysis of a model's 's robustness to graph perturbations.
saate-ofthe-an approach for simultaneously
To summarize, our core contributions are that we
propose sound notion of adversarial robustness for group equivariant tasks,
show that using equivariant models facilitates achieving (provable) robustness,
develop the framework of sndivarranceepreeevvinn randomized smoothing,
and generalize each existing graph and node classification robustness certificate for to perturbations to graph edit distance perturbations with user-specified costs.
Overall, reconsidering what adversarial robustness means in equivariant tasks is an important prereq- uisite for future work at the intersection of robust and geometric machine learning.
Related work
There is little prior work that studies equivariance and adversarial robustness jointly. The work that exists [I only considers group invariant classification (a special case of equivariance) and does not consider how task's equivariances should inffuence what we consider robust.
Model invariance and robustness. Prior work mostly focuses on a trade-off between invariance and robustness in image classification, i.c., whether increasing robustness to rotation translation

---

decreases robustness to l perturbations and vice-versa [21 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-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 dessedeenddntt A rotation invariant distance for images may be desirable when segmenting cell nuclei, but not when classifying
digits, since it would fail to distinguish 6 and 9.
String edit distance. In concurrent work, Huang al. [22 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 E U {1} into another, up to insertion of alignment tokens 1. 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/7 331. transformers 37], point cloud models [30] 31 [6) and graph neural networks [8 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
under our proposed notion of adversarial robustness (see Section 5)
Transformatioon-peefffe robustness. A subfield of robust machine learning focuses robustness to unnoticeable parametric transformations (e.g. small rotations) [42] 46 (6-65). These works implicitly assume that large transformations lead to easily identifiable out-o--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, robustness can be framed as a special case of our proposed notion (see Appendix D))
Semantics-aware robustness. Our work is closely related to different proposals to include ground truth labels in the definition of adversarial robustness [22 52 [7) 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 (2 67 [1]. 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 decision problem. Group equivariant tasks admit a
similar approach, since we know how the ground truth changes for specific input transformations.
3 Background
Group theory and equivariance. Discussing group equivariance requires a few algebraic con- cepts. A group is a set G with identity element and associative operator G x G - G such that Vg E G: e. g g e 9 and each E G has an inverse element g with g g = 9 We are interested in transformations with a group structure, such rotations. Given set X, (left) group action is a function ax G x
e.
X- + X that transforms elements of X and preserves the structure
of G, i... g xx h og x = (g- h) x For instance, rotation by ø and then by & is the same as rota- tion by (1 + 6 A group may act differently on different sets. For example, rotation group SO(3) may act on point clouds via matrix multipliciation while acting on class labels via the identity function.
When clear from context, we drop the subscripts. A function f: X- - is equivariant if each action on its input is equivalent to an action on its output, i.c. Vx E X.g g E G f(g o% x) = g gyy f(x).
Adversarial robustness means that any small change to clean input x only causes a small change to prediction f(x), i.e. max dout (f(x), f(x') < 8 with B, = {x' (z, x') S <e). and da, and dout quantifying input and output distance. We refer to the set of admissible perturbed inputs B, as the perturbation model. A common special case is dout (y. v') = 1 [l + y'1 and 8 = 0 5.7.. Other forms of robustness involve training data [73 [44 but we focus on test-time perturbations.
Randomized smoothing [8]20] is a paradigm for increasing and proving the robustness of models in an architecture-agnosicc manner. works by randomizing the inputs of base model i to construct more robust smoothed model f. While originally proposed for provably robust image classification,
3

---

it has evolved into a much more general framework that can be applied to various domains and tasks [4] 20 55 8T. Consider a measurable imput space (X, D) and measurable base model h: X + V that maps to measurable intermediate space (V, IR) (e.g. logits). Given the base model h and a family of probability measures (fzx)zx on (X, ID) indexed by X (e.g. Gaussians with mean a), we can define the input-dependent pushforward measure Ma o h for any input E X We can further define a smoothing scheme { : A F) + Y that maps from probability measures A I)) on the intermediate space to an output space Y (e.g. logit distributions to labels) B This lets us construct the smoothed model f(x) = E(uz o h 1-1), which makes prediction for input x E X based on some quantity of the input-dependent pushforward measure Ma h h (e.g. the expected value). Intuitively, two inputs x and x' are sufficiently similar, then the smoothing measures μe and μlz will have large overlap, thus leading to similar smoothed predictions. The combination of measures (pz) Jrex and smoothing scheme & determines for which din and dout robustness is guaranteed. We discuss these combinations in more detail in Appendix D
4 Redefining robustness for group equivariant tasks
For the first time, we seek to define adversarial robustness for group equivariant tasks. By task mean unknown function y: X + Y that is equivariant with respect to the action of a group G. We assume that it is approximated by a (learned) model f X + Y whose robustness we want to determine. The model does not have to be equivariant. Like traditional adversarial robustness, we assume there are functions dm : X x X + R2 and daut Y x W -> IR,, which define what constitutes small change in domain X and co-domain Y, if symmetries. For instance, & distance is a natural notion of similarity between Fuclidean coordinates.
not concerned with group
For case of exposition, we further assume that all considered optimization domains are compact (so that minima and maxima exist) and that group G acts isometrically on X, i.e. Vr, E X, Vg E G dia (g x, g x') = d (1r x²). This covers most practically relevant use cases. For completeness, we discuss non con-compact sets and non-isometric actions in Appendices H and
4.1 Perturbation model for group equivariant tasks
Our first goal is to resolve the shortcomings of using typical input distance functions di to define what constitutes small input perturbations in group equivariant tasks. We seek some improved function du that accounts for the equivariance of y and simultaneously captures the similarity of objects in domain X, as defined by original distance function din- To this end, we define three desiderata.
Desideratum 1. We know that any perturbed x' E X and g x' with g E C are up to symmetry the same geometric object with the same semantic content, i.e. yig x²) = g y(x') ). But as illustrated in Fig. group actions may cause drastic change w.r.t. distance dun Thus, even if f fx) is "robust"
within g = {x'] d=n(222') I }} for some e, there may still be a x' E BB and o x' & B. that lead to two completely different predictions. If prediction can be altered without changing the semantic content of an input, it can hardly be considered robust. This problem cannot be resolved by requiring robustness for very large 6 so that By covers all symmetric objects. Doing so would also include objects with substantially different semantic content from clean input æ, which should actually lead to different predictions. Instead, we need dip that is constant for all symmetric forms of x', so that robustness to one implies robustness to all: Vx, x' E X, g E G din(z, g x') din (x, x').
While the first desideratum accounts for equivariance, model should also be robust to sensor noise, measurement errors and other small perturbations that are not necessarily group actions. Therefore, elements that are close with respect to the original distance function d.n should remain close under our new distance function dmn i... Vx, d (I, x²) ) S din xx)
Desideratum 2.
Desideratum 3. The first two desiderata could be fulfilled by dx, x²) = or a function that arbitrarily changes the ordering of inputs w.r.t distance. To appropriately capture similarity, dm should not only underapproximate din, but preserve it best as possible. Let ID be the set of functions from X x X to RR., that fulfill the first two desiderata. We require that d (I. x') = max,eD a").
Note that h 1 is not the inverse hut the pre-image. The hase model need not be invertible. b and Y can also be the same set, the case with majority voting for classifiers.

---

Proposition 1. A function din : X x X R4 that fulfills all three desiderata for any original dis- tance din X x X R, exists and is uniquely defined: (x, x') mingeg dm (z, g x').
We prove this result in Appendix C We refer to din as the action-induced distance. It is the distance after optimally aligning the perturbed input x' with the clean input x via a group action.
Example: Point cloud registration distance. Let X = NR Consider G = SN x (E(D), the set of permutation matrices, rotation matrices and translation vectors. Let G act via (P. (P,R,t) x
P (X Rº + 1xt²) and let din be the Frobenius distance. Then din is the registration distance (2) i.e. the distance after finding optimal correspondence and applying an optimal rigid transformation.
Example: Graph edit distance. Let be the set of all adjacency matrices {0. 1 1 with din (A, = | A'llo: Consider G = Sx. the set of permutation matrices. Let G act via P A PAP". Then diu (A, A') is the graph edit distance with uniform cost (83)85). That is, the number edges that have to be inserted or deleted to transform A into a graph isomorphic to A'.
As demonstrated by these examples, equivariant domains. Our contribution is justifying, a principled manner, why this notion of distance should be used to define adversarial robustness for group equivariant tasks.
do not claim to have invented this notion of distance for
Perturbation model. Now that we have an appropriate input distance for group equivariant tasks, we can use it to define the set of admissible perturbed inputs B3 as {a' mingec d (I, 9 x²) < with some small E R,, Because every g E G has an inverse element g this set is identical to {g x' 9 G, (z, xx) S e]. We use this equivalent representation because it lets disentangle group actions from other perturbations. That is, f() should be robust to inputs that can be generated via small perturbation w.r.t. the original distance du followed by group action.
4.2 Output distance for group equivariant tasks
Fig. illustrates that we also need to reconsider what a small change model's prediction is. Letting group element act on a prediction may cause a large change w.r.t. dout- In particular, we 0, even though and g have distance of zero w.r.t. the action-induced distance. Thus, we would consider even the ground truth y itself to be non-robust. Using action-induced distances, i.e. mingec dout (y, g y'). is not appropriate either. Action-induced distances cannot distinguish between model that transforms its predictions in compliance with the ground truth and one that applies arbitrary group actions.
may have dont(y(a:) v(g x)) dout (v(x). g yar))
To appropriately measure output distance, we need to account for differences between clean prediction fx) and perturbed prediction f(g z²) that are caused by the specific group element g E G acting on the model's input. To do so, we need to first revert the effect of the group action before comparing the predictions. That is, we need measure output distance using dowt (J (f(x), " [[g x²)).
(f
4.3 Proposed definition of robustness for group equivariant tasks
Combining the perturbation model from Section 4.1 with the output distance from Section 4.2 leads to the following definition of adversarial robustness for group equivariant tasks:
Definition 1. Assume that ground truth function y X _> Y is equivariant with respect to the action of group G. Then, a prediction f(x) for clean input x E X is (G, din dout: e, 6) -equivvivaaatttooooo robust if (max max dow (f
f(g xx) s.t. (In(x, x²) S e) 8.
(1)
e'ex gEG
Simply speaking, prediction f(z) should be considered robust if it is robust unnoticeable perturba- tions and is approximately equivariant around x. For perturbations of size w.r.t. the original din the prediction should not change by more than d and group action should cause this error to increase beyond 5. Note that Definition I depends on the equivariances of the task y. not those of the model f. Further note that the constraint involves original distance din, not action-induced distance d.n-
Special cases. If the task is not equivariant, i.e. G {e), we recover the traditional notion of adversarial robustness because e acts via identity. For e = 0. constant 8 a bound on the equivariance error, a common evaluation metric in geometric machine learning (see, e.g. (0).
Other invariant distances. As discussed in Section 2 alternative invariant distances have been proposed for certain group invariant classification tasks. This includes Hausdorff and Chamfer
5

---

distance 30 311, as well as optimal transport for graphs (27 29
Any group invariant function dm is mingeG dip (z. x²) dip (i, 2²).
preserved by the induudd distance: mingeG dm (z.
Thus, all previous results for invariant classification are compatible with our notion of robustness.
Local budgets and local robustness. For data that is composed of N distinct elements, such as point clouds, one may want local budgets El...., EN. For tasks that involve M distinct predictions, such as segmentation, one may only be interested in the robustness of some subset of predictions. Definition I can be extended to accommodate local budgets and robustness, see Appendix G
5 Achieving provable robustness for group equivariant tasks
Now we have a sound notion of robustness that overcomes the limitations discussed in Section [ But it is not clear how to achieve provable robustness. Given a task y X Y that is equivariant with respect to the action of group G. we want model f X - Y and corresponding algorithm that can verify the (G, dmn dout, e, 5) eequivvriaat
of a prediction f(x)).
A challenge is that the action-induced distance din- which defines our perturbation model and thus underlies the optimization domain in Eq. ① is generally not tractable. For example, deciding whether the graph edit distance smaller than some E R is NP-hard 91] A solution would be to relax the optimization domain in order to pessimistically bound the model's 's actual robustness. This is, in essence, the approach taken by works on robustness to graph optimal transport perturbation models (e.g. [27 (8)). Instead of optimizing over discrete correspondences between objects, they optimize over couplings that define soft correspondences. There is however more arraihhtforwart solution that lets us take advantage of years of research in geometric and robust machine learning: Applying the principles of geometric machine learning and using a model with matching equivariances.
Proposition 2. Consider model f : X - Y that equivariant with respect to the action of a group G. Any prediction f(x) is (G, din, dout, c, 8) -euuivariantttrobee if and only if it is (fe), din. dout: C, (.J)=equvvariant-robsst i.e. fulfills traditional adversarial robustness.
Proof. Because f is equivariant, we have Vg gg gg1 f(g o [g)=))= = g f f(x') f(e x²) and thus dout (f(x). f(g x') dout (f(z), f(e=x')).
O
By using model f with the same equivariances ground truth y, we reduce the problem of proving robustness to that of proving traditional adversarial robustness i.c. G = {e}. Again, note that robustness does not mean that prediction remains constant, but that it transforms in compliance with semantics-presene
transformations of the input, even under small perturbations (see Eq. (.)
Discussion. Proposition 2 provides another strong argument for the use of geometric machine learning models. These models facilitate the problem of achieving provable robustness for group equivariant tasks - without relaxing the action-induced distance and thus weakening our guarantees. We can instead build upon existing robustness certification procedures for equivariant models, such as transformers, PointNet and graph convolutional networks, under traditional perturbation models, like lg or to perturbations 88-77 44). We just need to use our knowledge about the equivariances of tasks and models to reinterpret what is actually certified by these procedures.
Relation to babet-based certificates. A related result was discussed for group invariant point cloud classifiers in [26:: If X = NxD and classifier f is constant within Frobenius norm ball B and invariant w.r.t. the action of group G, then it is also constant within {g- X' X' E B. E G).
However, this work did not discuss whether being constant within this set is desirable, how it relates to task invariance and what this result tells us about the adversarial robustness of the classifier.
Adversarial attacks. While we focus on provable robustness, PropositionOllle applies to adversarial attacks, i.c. proving non-robustness via counterexample. Even when the equivariances of y and do not match, traditional attacks are feasible solutions to Eq. (I) since they amount to constraining g to set {e). For completeness, we perform experiment, with adversarial attacks in Appendix A.4 A.4
5.1 Equirarranne-preserving randomized smoothing
Equivariant models reduce the problem of proving robustness for group equivariant tasks to that of proving traditional robustness. However, specialized procedures to make these proofs are only available for limited range of architectures. For example, specialized certification procedures for

---

point cloud models are limited to the PointNet architecture 42 12], and there are no procedures to prove the robustness of models with continuous equivariances, such as rotation equivariance.
For such models, one could try to apply randomized smoothing (recall Section 3 By choosing a suitable smoothing scheme Ç and measures (/z))xxx for distances din and dout- one can transform any How-
base model into smoothed model f and prove its (fe), din, dout: e, l--quivariant-robutteee ever, base model h having the same equivariances as task y does not guarantee that smoothed model has the same equivariances. Thus, one can generally not use Proposition 2 to prove (G, din, dout. e, 6)- suuivariiantrobustten
We propose the following sufficient condition for verifying that a specific smoothing scheme and family of measures are
(proof in Appendix (E.I)
Proposition 3. Assume two measurable spaces (X, D), (V,F), an output space Y and a measurable base model h X + V that is equivariant with respect the action of group G. Further assume that G acts on X and V via measurable functions. Let & (V,F) + Y be a smoothing scheme that maps from the set of probability measures A IF) on intermediate space (V,F) to the output space. Define Tx.g() (-) to be the group action on set X. for a fixed g, i.e. (x,g(z) = 9 xx x. Then, the smoothed model f fxx) = E(pz o 11 is equivariant with respect to the action of group G if both
the family of measures (pe)xex is equivariant, i.e. Vr E XX.g E G Pgen 22 %x.9
and smoothing scheme 5 is equivariant, i.e. Vv E FV, E G E(v TV
E(v).
Note that o is composition of functions, whereas is a group action. The intuition behind Propo- sition is that, if family of measures (pz)uex, and base model h, and smoothing scheme are cquivariant, then we have a chain of equivariant functions which is overall equivariant. We provide a visual example of such an equivariant chain of functions in Fig. 31
In the following, we show that various schemes and measures preserve practically relevant equivari- ances and can thus be used in conjunction with Proposition 2 to prove (G, din, dout, c, (.)euiieeeeeeeuuaaiiiiaittt -equuivaria robustness. For the sake of readability, we provide a high-level discussion, leaving the formal propositions in Appendix cuss how to derive robustness guarantees for arbitrary combinations of these schemes and measures.
E.2 We summarize our results in Tables and 2
In Appendix D we dis-
Componentwise smoothing schemes. The most common type of smoothing scheme can be applied whenever the intermediate and output space have M distinct components, i.c. V = A M and Y = BM for some A, B. It smooths each of the M base model outputs independently. This includes majority voting [20]. expected value smoothing [75] 76) and median smoothing (77). which can be used for tasks like classification, segmentation, node classification, regression, uncertainty estimation and object detection [4 20 [1 81. Such schemes preserve equivariance to groups acting on V and Y via permutation. Note that G need not be the symmetric group Sy to act via permutation. For instance, the identity function a permutation, meaning componentwise smoothing schemes can be used to prove robustness for arbitrary group invariant tasks. See Proposition 4
Expected value smoothing scheme. When the intermediate and output space are real-valued, i.e.
V y Y = RMM,, one can make predictions via the expected value [75] 76).. Due to linearity of expectation, this scheme does not only preserve permutation equivariance but also equivariance to affine transformations. However, certifying the smoothed predictions requires that the support of the
output distribution bounded by a hyperrectangle, i.e. Sp e o h-1) C {y E M I'm am S
ym I bm } for some a, b E R M
75 76).
See Proposition
Median smoothing scheme. When the support of the model's output distribution is real-valued and potentially unbounded, one can make smoothed predictions via the elementwise median (77]. This scheme does not only preserve permutation equivariance but also equivariance elementwise linear transformations, such as scaling. See Proposition 6
Center smoothing scheme. Center smoothing 93 is flexible scheme that can be used whenever dout fulfills a relaxed triangle inequality. It predicts the center of the smallest dout ball with measure of at least J. Center smoothing has been applied to challenging tasks like image reconstruction, dimen- sionality reduction, object detection and image segmentation [1) We prove that center smoothing is equivariant any group acting isometrically w.r.t. dout For example, when V = Y R MxD and dout. is the Frobenius norm, center smoothing guarantees (G, din, dout: e, 8) eeuuivariannttoouusee for any group acting on R-N xD via permutation, rotation, translation reflection. See Proposition 7
Product measures. Many randomized smoothing methods use product measures. That is, they use independent noise to randomize elements of an --dimensional input space X AN. The most
7

---

popular example are exponential family distributions, such Gaussian, uniform and Laplacian noise, which can be used to prove robustness for various e, distances [9 20 94 95], Mahalanobis distance [60 [66] and Wasserstein distance [97]. Product measures preserve equivariance to groups acting via permutation. Again, group G need not be symmetric group S, to act via permutation. For is permutation of its pixels. See Proposition X
instance, rotating a square image by 90" (see Fig. 2
Isotropic Gaussian measures. Isotropic Gaussian measures are particularly useful for X >R They guarantee robustness when din is the Frobenius distance 43 46 and preserve equivariance to isometries, i.e. permutation, rotation, translation and reflection. Combined with Proposition 2 this guarantees robustness w.r.t. the aforementioned point cloud registration distance. See Proposition 9
Transformation-specii measures. A standard tool for proving transformation (see Section 2 is transformatioo-sseccffe smoothing [46 60 transformations from parametric family (the) Jaee with vhy X X to the inputs of a model. If all
robustness
63 65 i.e. applying randomly sampled
tho with E θ are equivariant to the actions of group G. then transformation-speciin preserves this equivariance. For example, random scaling [65] preserves rotation equivariance and additive noise (e.g. Gaussian) preserves translation equivariance for X = NXDD, See Proposition 10
smoothing
Sparsity- aware measures. Sparsity- noise [4] can be applied to discrete graph-structured data to guarantee robustness to edge and attribute insertions and deletions. We prove that sparsity- aware measures preserve equivariance to groups acting via graph isomorphisms. As we discuss in the next section, this guarantees robustness w.r.t. the graph edit distance. See Proposition
5.2 Deterministic edit distance certificates for graph and node classification
Besides sparsity-aware smoothing, there are also deterministic procedures for proving robustmess for specific graph neural networks, namely graph convolutional networks [98] and APPNP [99]. They are however limited to uniform costs. To be more specific, let X be the set of all graphs
{0. 13 NND x {0, N with N nodes and D binary attributes and let (A). + = max AA 0) and
(A) --mmin., (A,0) 0) with elementwise maximum and minimum. Define d ((x, A), (X', A')) as
x 1[(XX'X)-l1 -XX''-X + cx |1(X' - -lo + c |I(A' - -))+ll + + I[(A' llo. (2)
with costs cx. Ct. CA for insertion and deletion of attributes and edges. Prior work can only prove robustness for costs in (oo. J.J i.c. disallow certain types of perturbations and use uniform cost for the remaining ones. In Appendix(F]]) we generalize each existing deterministic graph and node clas- sification guarantee to non-uniform costs. This includes procedures based on convex outer adversarial polytopes [0], policy iteration 11 interval bound propagation [12, bilinear programming [3], and simultaneous linearization and dualization [13]. Our proofs mostly require solving different knapsack problems with local constraints and only two distinct costs - which can be done efficiently via dynamic programming or linear relaxations with analytic solutions (see Appendix [.I). As per Proposition 2 of isomorphism equivariant models this way proves (SN, dins dout, e, 6. "o--equivvrriant-oousttses Thus, these procedures guarantee robustness w.r.t graph edit distance din ((X, A), (X', A')) minpesy dia((,, A), (PX', PA'P"))
proving (Le), din, dout, e, 8) eequivarianttrobusttnn
5.3 Limitations
Group equivariance covers various common task symmetries. However, there are symmetries that do not fit into this framework, such as local gauge equivariance [00 [02] or wave function symmetries [10) A limitation of relying on group equivariant models for provable robustness that there are tasks where non equivarrian models have better empirical performance, for example vision transformers D... Models that are in principle equivariant may also lose their equivariance due to domain-specific artifacts like image interpolation. Finally, it should be noted that providing guarantees of the form (G, din dout. e, d) requires a-priori knowledge that the task is equivariant to group G. These limitations are however not relevant for many important domains in which equivariant models are the de-facto standard (c.g. graphs, point clouds and molecules).
Experimental evaluation
In the following, we demonstrate how sound robustness guarantees for tasks with discrete and contin- uous domains and cquivariances can be obtained via equivariaace--rreerving randomized smoothing.
8

---

100%
Avg. á [kcal/mol/A/
PointNet DGCNN
0.100
80%
Cort. Acc.
0.075
60%
40%
0.050
Aspini
Napthalone
Uracil
Toloene
20%
0.025
Fihanol
Salicylia acid
Benzene
Molonaldehyde
0%
0.000
0.0
0.2
0.4
0.6
0.0
0.5
1.5 2.0
Correspondence distance
Registration distance e [fm]
Figure 3: Provable robustness of smoothed (o = Figure 4: Provable robustness of smoothed (a 0.2) PointNet and DGCNN point cloud classifiers fm) DimeNet++ force predictions on MD17. on ModelNet40.. Correspondence distance e is The average provable bounds å on prediction the Frobenius distance between point clouds after changes are to 13 times smaller than the av- finding an optimal matching via permutation.
erage test emrors (0.19 to 0.74 kcal/mol/A)
We additionally evaluate our graph edit distance certificates and how the cost of edit operations affects provable robustness. All experimental details are specified in Appendix B Certificates are evaluated on a separate test set. Randomized smoothing methods are evaluated using sampling and hold with high probability. Each experiment is repeated 5 times. We visualize the standard deviation using shaded areas. When the shaded area is too small, we report its maximum value. An implementaton will be made available at https://css.t https://cs.cit.tum. wwt.:sttttttcceeeeeeeeeee
Point cloud classification. The first task we consider is point cloud classification, i.e. X = RVV N33 and Y = fl..... K}. Natural distances dm and dout are the Frobenius distance and 0-1-loss. The task is permutation invariant, i.c. symmetric group G Sy acts on X via permutation and on Y via identity. Thus, we need to prove robustness w.r.t. to the correspondence distance din- i.e. the Frobenius distance after finding optimal matching between rows via permutation. To preserve invariance and use Proposition 2 while randomly smoothing, we use Gaussian measures and majority voting, i.e. we predict the most likely label under Gaussian input perturbations. As invariant base models h we choose PointNet [114] and DGCNN (15), which are used in prior work on robust point cloud classification 30.B1] We evaluate the robustness guarantees for smoothing standard deviation o = 0.2 on ModelNet40 [16]. This dataset consists point cloud representations of
CAD models from 40 different classes. Fig. 3 shows the certified accuracy, i.e. the percentage of predictions that are correct and provably robust. Both smoothed models have a high accuracy above 80%, but DGCNN has significantly higher provable robustness. In Appendix A. we repeat the experiment for different values of and compare our guarantees to those of 3DVerifier
(22
Molecular force prediction. Next, we consider task with continuous equivariances: Predicting the forces acting on each atom in a molecule, which can for instance be used to simulate molecular dynamics. We have X IR Nx3 (atomic numbers are treated as constant) and Y B x33 Suitable distances din and dout are the Frobenius distance and the average f2 error Σn Yr, Y, N.
The task is permutation, rotation and translation equivariant, i.c. G = SN x SE(3). Thus, d is the point cloud registration distance. To preserve equivariance, we use Gaussian measures and center smoothing. We choose DimeNet++ [117 as equivariant base model h. We evaluate the provable robustness for smoothing standard deviation = 1 fm MD17 118), a collection of 8 datasets, each consisting of large number of configurations a specific molecule. With just 1000 training samples, the models achieve low average test errors between 0.19 and 0.74 kcal/ /e////o//A// Å. We use 1000 samples per test set to evaluate the robustness guarantees. Fig. 4 shows the average upper bounds on the change of the predicted force vectors for small perturbations between 0 and 2 fm. These average ö are smaller than the average test errors by factors between 2 and 13. The standard deviation across seeds is below 3 10-4 kcal/mol/ Á for all In Appendix A.2 show that the maximum c and 5 grow approximately linearly with a and repeat our experiments with SchNet [19 and SphereNet [120) base models. Note that are not (primarily) proving robustness to malicious perturbations, but robustness to measurement errors or errors in previous simulation steps.
Node classification. Finally, we consider a task with discrete domain and co-domain: Node clas- sification, i.e. X = {0, 1) X x {0, N and V = (1...., K)N Distance din naturally defined via weighted sum of inserted and deleted bits (see Eq. 2 Output distance dout is the

---

ex
Cx
100%
100%
100%
100%
Cort. Acc.
75%
Cert. Acc.
75%
Cerl. Acc.
75%
0x
Cert. Acc.
75%
50%
50%
50%
50%
25%
25%
25%
25%
0%
0%
0%
0%
5
10
0
5
10
0
25
50
25
50
Edit distance
Edit distance
Edit distance
Edit distance
Figure 5: Randomized smoothing guarantees for Figure 6: Convex adversarial polytope guaran- GCNs on Cora-ML. Increasing the cost of ad- tees for GCNs on Cora-ML. Increasing the cost versarial edge insertions increases the provable of attribute insertions increases the provable ro- robustness for the same perturbation budgets e. bustness for the same perturbation budgets
to distance, i.e. the number of changed predictions. The task is equivariant to symmetric group S, acting on and Y via isomorphisms and permutations, respectively. To preserve equivariance, we use sparsity-aaaa aware measures and majority voting. The flip probabilites (see Appendix (F.7) are set to px = 0x = 0, P, = 0.001, P = 0.8. We use a 2-layer graph convolutional network (98] as our isomorphism equivariant base model h. Fig. shows the resulting guarantees Cora ML [21 for graph edit perturbations of the adjacency, i.e. cx cx = oo, for varying costs ct and CA. We observe that increasing the cost for edge insertions significantly increases the provable robustness for the same budgets e, whereas the cost for edge deletions has virtually no effect. This suggests that insertions much more effective changing model's 's predictions, which was empirically observed in prior work [13]. We repeat the experiment with other flip probabilities in Appendix A.3 The standard deviation of certified accuracies across all seeds was below 2.1 p.p. everywhere. Note that here, certified accuracy does not refer to the percentage of predictions that are correct and constant, but those that are correct and permute in compliance with isomorphisms of the input graph.
Deterministic edit distance certificates. In Fig. 6 we repeat the node classification experiment with our generalization of the convex polytope method from [10]. We consider feature perturbations, i.e. x c = oc, for varying cX and Cx- Again, the cost insertions has a larger effect, suggesting that the model is less robust to them. In Appendix [A.3 we repeat the experiments with the four other graph edit distance certificates and also evaluate them on Citeseer [124] and the TUDataset [25]. Overall, our generalizations of existing graph robustness guarantees let us prove robustness to more complex threat models, even though evaluating the edit distance is computationally hard.
7 Conclusion
The main goal of this paper is to define adversarial robustness for group equivariant tasks. To this end. we introduce ection-induced distances as the appropriate notion of input distance and consider how predictions should transform for semantics- prrpeerriigpeeeiingggg... transformations of inputs. If the equivariances of task and model match, the proposed notion of robustness can be guaranteed by proving traditional adversarial robustness. This has two consequences: Firstly, specialized certification procedures for equivariant architectures can be reused. One just has to reinterpret what is actually guaranteed by these procedures, e.g. robustness to perturbations bounded by graph edit distance. Secondly, randomized guarantees - but only if the smoothing
smoothing can be used to provide architecture-agnen scheme and measures preserve the model's equivariances. We experimentally demonstrated the randomized smoothing approach by certifying robustness
generality of this setiiaariance-prseevvie for graph, point cloud and molecule models. Overall, our work provides a sound foundation for future work at the intersection of robust and geometric machine learning.
Future work. Based on Proposition 2 direction for future work is to continue making equivariant models more robust to classic threat models, without caring about equivariance. A more interesting direction is to make attacks, defenses and certificates equivariance-awee -ware.. For instance, knowledge about model equivariances could be used to reduce the search space for attacks, disrupt gradient- based attacks (similar to [266] ) or derive stronger randomized smoothing guarantees (as proposed for invariant models in (26) ). Finally, developing procedures to certify non-equivariant models (e.g.
vision transformers) or models that are only "almost equivariant" (e.g. due to interpolation artifacts)
under the proposed notion of robustness would be desirable for equivariant computer vision tasks.
10

---

8 Acknowledgments and disclosure of funding
The authors would like to thank Hongwei Jin for assistance with the implementation of their topology attack certificates, Tom Wollschläger for providing access to code for training molecular force models, and Aman Saxena for valuable discussions concerning non-compact sets and non-isometric actions. This work has been funded by the Munich Center for Machine Learning, by the DAAD program Konrad Zuse Schools of Excellence in Artificial Intelligence (sponsored by the Federal Ministry of Education and Research), and by the German Research Foundation, grant GU 1409/4-1. The authors of this work take full responsibility for its content.
References
[1] Michael M Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometric deep learning: Grids, groups, graphs, geodesies, and gauges. arXiv preprint arXiv:2104. 13478, 2021.
[2] Kunihiko Fukushima. Neural network model for a mechanism of pattern recognition unaffected by shift in position - neocognitron. IEICE Technical Report, A, 62(10):658-66) 1979.
[3] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances neural information processing systems, 2017.
[4] Marco Gori, Gabriele Monfardini, and Franco Scarselli. new model for learning in graph domains. In Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005., volume 2. pages 729-734, IEEE, 2005.
[5] Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties neural networks. In International Conference on Learning Representations, 2014.
[6] Anh Nguyen, Jason Yosinski, and Jeff Clune. Deep neural networks are easily fooled: High confidence predictions for unrecognizable images. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 427-436, 2015.
[7] Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversar- ial examples. International Conference on Learning Representations, 2015.
[8] Daniel Zügner, Amir Akbarnejad, and Stephan Günnemann. Adversarial attacks neural networks for graph data. In Proceedings of the 24th ACM SIGKDD international conference knowledge discovery & data mining, pages 2847-2856, 2018.
[9] Daniel Zügner and Stephan Günnemann. Adversarial attacks on graph neural networks via meta learning. In International Conference on Learning Representations, 2019.
[10] Daniel Zügner and Stephan Günneemann. Certifiable robustness and robust training for graph convolutional networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2019.
[11] Aleksandar Bojchevski and Stephan Günnemann. Certifiable robustness graph perturbations. In Advances in Neural Information Processing Systems, 2019.
[12] Yang Liu, Jiaying Peng, Liang Chen, and Zibin Zheng. Abstract interpretation based robustness certification for graph convolutional networks. In ECAI 2020, pages 1309-13155 2020.
[13] Daniel Zügner and Stephan Günnemann. Certifiable robustness of graph convolutional net- works under structure perturbations. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2020.
[14] Aleksandar Bojchevski, Johannes Klicpera, and Stephan Günnemann. Efficient robustness certificates for discrete data: Sparsity-awan randomized smoothing for graphs, images and more. In International Conference on Machine Learning, 2020.
11

---

[15] Hongwei Jin, Zhan Shi, Venkata Jaya Shankar Ashish Peruri, and Xinhua Zhang. Certified robustness of graph convolution networks for graph classification under topological attacks. Advances in neural information processing systems, 2020.
[16] Jan Schuchardt, Aleksandar Bojchevski, Johannes Kliepera, and Stephan Günnemann. Col- lective robustness certificates: Exploiting interdependence in graph neural networks. In International Conference on Learning Representations, 2021.
[17] Lichao Sun, Yingtong Dou, Carl Yang, Kai Zhang, Ji Wang. S Yu Philip, Lifang He. and Bo Li. Adversarial attack and defense on graph data: A survey, IEEE Transactions on Knowledge and Data Engineering, 2022.
[18] Bai Li, Changyou Chen, Wenlin Wang. and Lawrence Carin. Certified adversarial robustness with additive noise. Advances in neural information processing systems, 2019.
[19] Mathias Lécuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Cer- tified robustness to adversarial examples with differential privacy. In IEEE Symposium on Security and Privacy, pages 656-672, 2019.
[20] Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via random- ized smoothing. In International Conference on Machine Learning, 2019.
[21] Sandesh Kamath, Amit Deshpande, Subrahmanyam Kambhampati Venkata, and Vineeth N Balasubramanian. Can we have it all? on the trade-off between spatial and adversarial robustness of neural networks. Advances in Neural Information Processing Systems, 2021.
[22] Florian Tramèr, Jens Behrmann, Nicholas Carlini, Nicolas Papernot, and Jörn-Henrik Jacobsen. Fundamental tradeoff' between invariance and sensitivity to adversarial perturbations. In International Conference on Machine Leurning, 2020.
[23] Ke Sun, Mingjie Li, and Zhouchen Lin. Pareto adversarial robustness: Balancing spatial robustness and sensitivity-bar based robustness. CoRR, abs/211 1 1.01996, 2021.
[24] Vasu Singla, Songwei Ge, Basri Ronen, and David Jacobs. Shift invariance can reduce adversarial robustness. In Advances in Neural Information Processing Systems, 2021.
[25] Beranger Dumont, Simona Maggio, and Pablo Montalvo. Robustness of rotation-equivarian networks to adversarial perturbations. CoRR, abs/1802.06627,. 2018.
[26] Jan Schuchardt and Stephan Günnemann. Invariance-aware randomized smoothing certificates. In Advances in Neural Information Processing Systems, 2022.
[27] Hongwei Jin, Zishun Yu, and Xinhua Zhang. Certifying robust graph classification under orthogonal Crromov-Wassersterr threats. In Advances in Neural Information Processing Systems, 2022.
[28] Ching Yao Chuang and Stefanie Jegelka. Tree mover's distance: Bridging graph metrics and stability of graph neural networks. In Advances in Neural Information Processing Systems, 2022.
[29] Samantha Chen, Sunhyuk Lim, Facundo Mémoli, Zhengchao Wan, and Yusu Wang. The Weisfeiler-Lehman distance: Reinterpretation and connection with gnns. arXiv preprint urXiv:2302.007113 2023.
[30] Chong Xiang, Charles R Qi, and Bo Li. Generating 3d adversarial point clouds. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 1136-9144 2019.
[31] Jiancheng Yang, Qiang Zhang, Rongyao Fang, Bingbing Ni, Jinxian Liu, and Qi Tian. Adver- sarial attack and defense on point sets. arXiv preprint (1t.::/902.10999 2019.
[32] Zhuoqun Huang, Neil Marchant, Keane Lucas, Lujo Bauer, Olya Ohrimenko, and Benjamin
I. P. Rubinstein. RS-Del: Edit distance robustness certificates for sequence classifiers via randomized deletion. In Advances in Neural Information Processing Systems, NeurlPS, 2023.
12

---

[33] Naveed Akhtar and Ajmal Mian. Threat of adversarial attacks on deep learning in computer vision: A survey. IEEE Access, 1114400-4430, 2018.
[34] Yu-Lum Hsieh, Minhao Cheng, Da-Cheng Juan, Wei Wei, Wen-Lian Hsu, and Cho-Jui Hsieh. On the robustness of self-attentive models. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 1520-1529, 2019.
[35] Zhouxing Shi, Huan Zhang. Kai-Wei Chang, Minlie Huang, and Cho-Jui Hsieh. Robustness verification for transformers. In International Conference on Learning Representations, 2020.
[36] Gregory Bonaert, Dimitar Dimitrov, Maximilian Baader, and Martin Vechev. Fast and precise certification of transformers. In Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation, pages 466-481, 2021.
[37] Kaleel Mahmood, Rigel Mahmood, and Marten Van Dijk. On the robustness of vision trans- formers to adversarial examples. In Proceedings of the IEEE/CVF International Conference Computer Vision, pages
2021.
[38] Hang Zhou, Dongdong Chen, Jing Liao, Kejiang Chen, Xiaoyi Dong, Kunlin Liu, Weiming Zhang, Gang Hua, and Nenghai Yu. LG-GAN: Label guided adversarial network for flex- ible targeted attack of point cloud based deep networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pages 10356-10365, 2020.
[39] Yuxin Wen, Jichong Lin, Ke Chen, CL Philip Chen, and Kui Jia. Geometry-aware generation of adversarial point clouds. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020.
[40] Qidong Huang, Xiaoyi Dong, Dongdong Chen, Hang Zhou, Weiming Zhang, and Nenghai Yu. Shape-invariant 3d adversarial point clouds. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition (CVPR). pages 15335-15344. 15344, June 2022.
[41] Daniel Liu, Ronald Yu, and Hao Su. Adversarial shape perturbations on 3d point clouds. In European Conference on Computer Vision, pages 88-104. Springer, 2020.
[42] Tobias Lorenz, Anian Ruoss, Mislav Balunović, Gagandeep Singh, and Martin Vechev. Ro- bustness certification for point cloud models. Proceedings of the IEEE/CVE International Conference on Computer Vision, pages 7608-7618, 2021.
[43] Hongbin Liu, Jinyuan Jia, and Neil Zhenqiang Gong. PointGuard: Provably robust 3d point cloud classification. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 6186 6695,,996 2021.
[44] Dishanika Dewani Denipitiyage, Thalaiyasingam Ajanthan, Parameswaran Kamalaruban, and Adrian Weller. Provable defense against clustering attacks on 3d point clouds. In The AAA1-22 Workshop on Adversarial Machine Learning and Beyond, 2021.
[45] Jaeyeon Kim, Binh-Son Hua, Thanh Nguyen, and Sii-Kit Yeung. Minimal adversarial examples for deep learning on 3d point clouds. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 7797-7806, 2021.
[46] Wenda Chu, Linyi Li, and Bo Li. TPC: Transformatioon-peciffe smoothing for point cloud models. In International Conference on Machine Learning, 2022.
[47] Simon Geisler, Daniel Zügner, and Stephan Günnemann. Reliable graph neural networks via robust aggregation. In Advances in Neural Information Processing Systems, 2020.
[48] Simon Geisler, Tobias Schmidt, Hakan Sirin, Daniel Zügner, Aleksandar Bojchevski, and Stephan Günneeann. Robustness of graph neural networks scale. In Advances in Neural Information Processing Systems, 2021.
[49] Yan Scholten, Jan Schuchardt, Simon Geisler, Aleksandar Bojchevski, and Stephan Günne- mann. Randomized ieasage-inteeception smoothing: Gray-box certificates for graph neural networks. In Advances in Neural Information Processing Systems, 2022.
13

---

[50] Felix Mujkanovic, Simon Geisler, Aleksandar Bojchevski, and Stephan Günnemann. Are defenses for graph neural networks robust? Advances Neural Information Processing Systems, 2022.
[51] Jan Schuchardt, Tom Wollschläger, Aleksandar Bojchevski, and Stephan Günnemann. Local- ized randomized smoothing for collective robustness certification. In International Conference on Learning Representations, 2023.
[52] Lukas Gosch, Daniel Sturm, Simon Geisler, and Stephan Günnemann. Revisiting robustness in graph machine learning. In International Conference on Learning Representations, 2023.
[53] Francesco Campi, Lukas Gosch, Tom Wollschläger, Yan Scholten, and Stephan Günnemann. Expressivity of graph neural networks through the lens of adversarial robustness. In The Second Workshop on New Frontiers in Adversarial Machine Learning, 2023.
[54] Lukas Gosch, Simon Geisler, Daniel Sturm, Bertrand Charpentier, Daniel Zügner, and Stephan Günnemann. Adversarial training for graph neural networks. In Advances in Neural Informa- tion Processing Systems, 2023.
[55] Yan Scholten, Jan Schuchardt, and Stephan Günnemann. Hierarchical randomized smoothing. In Advances in Neural Information Processing Systems, 2023.
[56] Can Kanbak, Seyed-Mohsen Moosavi-Dezfood and Pascal Frossard. Geometric robustness of deep networks: analysis and improvement. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 4441 14491,44,,4444 2018.
[57] Logan Engstrom, Brandon Tran, Dimitris Tsipras, Ludwig Schmidt, and Aleksander Madry. Exploring the landscape of spatial robustness. In International conference on machine learning. 2019.
[58] Mislav Balunovic, Maximilian Baader, Gagandeep Singh, Timon Gehr, and Martin Vechev. Certifying geometric robustness of neural networks. Advances Neural Information Process- ing Systems, 2019.
[59] Yue Zhao, Yuwei Wu, Caihua Chen, and Andrew Lim. On isometry robustness of deep 3d point cloud models under adversarial attacks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 1201-1210, 2020.
[60] Mare Fischer, Maximilian Baader, and Martin Vechev. Certified defense to image transfor- mations via randomized smoothing. Advances in Neural information processing systems, 2020.
[61] Anian Ruoss, Maximilian Baader, Mislav Balunović, and Martin Vechev. Efficient centification of spatial robustness. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 2504-2513, 2021.
[62] Jeet Mohapatra, Tsui- Wei Weng, Pin-Yo Chen, Sijia Liu, and Luca Daniel. Towards verifying robustness of neural networks against family of semantic perturbations. In Proceedings of the IEEE/CVF Conference Computer Vision and Patlern Recognition (CVPR), June 2020.
[63] Linyi Li, Maurice Weber, Xiaojun Xu, Luka Rimanic, Bhavya Kailkhura, Tao Xie, Ce Zhang, and Bo Li. TSS: Transformation-specii smoothing for robustness certification. In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, pages 535-557, 2021.
[64] Motasem Alfarra, Adel Bibi, Naeemullah Khan, Philip HS Torr, and Bernard Ghanem. De- formRS: Certifying input deformations with randomized smoothing. In Proceedings of the AAAI Conference on Artificial Intelligence, number 6, pages 6001-6009, 2022.
[65] Nikita Murarev and Aleksandr Petiushko. Certified robustness via randomized smoothing over multiplicative parameters of input transformations. In International Joint Conference on Artificial Intelligence, 2022.
14

---

[66] Jacobsen, Jens Behrmann, Richard Zemel, and Matthias Bethge. Excessive invariance causes adversarial vulnerability. In International Conference on Learning Repre- sentations, 2019.
[67] Jörn-Henrik Jacobsen, Jens Behrmann, Nicholas Carlini, Florian Tramèr, and Nicolas Papernot. Exploiting excessive invariance caused by norm-boundes adversarial robustness. CoRR, 0bs/1903.10484 2019.
[68] Justin Gilmer, Ryan P Adams, Ian Goodfellow, David Andersen, and George E Dahl. Motivat- ing the rules of the game for adversarial example research. arXiv preprint arXiv:1807.00 1807.66732, 2018.
[69] Arun Sai Suggala, Adarsh Prasad, Vaishnavh Nagarajan, and Pradeep Ravikumar, Revisiting adversarial risk. In International Conference on Artificial Intelligence and Statistics, 2019.
[70] Sadia Chowdhury and Ruth Urner. Robustness should not be at odds with accuracy. In 3rd Symposium on Foundations of Responsible Computing (FORC 2022), 2022.
[71] Marcel Kollovich, Lukas Gosch, Yan Scholten, Marten Lienen, and Stephan Günne- mann. Assessing robustness via score-based adversarial image generation. arXiv preprini arXiv:2310.04285, 2023.
[72] Simon Geisler. Johanna Sommer, Jan Schuchardt, Aleksandar Bojchevski, and Stephan Günne- mann. Generalization of neural combinatorial solvers through the lens of adversarial robustness. In International Conference on Learning Representations, 2022.
[73] Chen Wang, Jian Chen, Yang Yang, Xiaoqiang Ma, and Jiangchuan Liu. Poisoning attacks and countermeasures in intelligent networks: Status quo and prospects. Digital Communications and Networks, 8(2):225-2)) 2022.
[74] Zhiyi Tian, Lei Cui, Jie Liang, and Shui Yu. A comprehensive survey on poisoning attacks and countermeasures in machine learning. ACM Computing Surveys, 55(8):1-35, 2022.
[75] Aounon Kumar, Alexander Levine, Soheil Feizi, and Tom Goldstein. Certifying confidence via randomized smoothing. Advances in Neural Information Processing Systems, 2020.
[76] Mikhail Pautov, Olesya Kuznetsova, Nurislam Tursynbek, Aleksandr Petiushko, and Ivan Os- eledets. Smoothed embeddings for certified few-shot learning. Advances in Neural Information Processing Systems, 2022.
[77] Ping-ych Chiang, Michael Curry, Ahmed Abdelkader, Aounon Kumar, John Dickerson, and Tom Goldstein. Detection regression: Certified object detection with median smoothing. Advances in Neural Information Processing Systems, 2020.
[78] Yihan Wu, Aleksandar Bojchevski, Aleksei Kuvshinov, and Stephan Günneeannn Completing the picture: Randomized smoothing suffers from curse of dimensionality for a large family of distributions. In International Conference on Artificial Intelligence and Statistics, 2021.
[79] Mare Fischer, Maximilian Baader, and Martin Vechev. Scalable certified segmentation via randomized smoothing. In International Conference on Machine Learning. 2021.
[80] Peter Súkeník, Aleksei Kuvshinov, and Stephan Günnemann. Intriguing properties of input- dependent randomized smoothing. In International conference machine learning, 2022.
[81] Aman Saxena, Tom Wollschläger, Nicola Franco, Jeanette Miriam Lorenz, and Stephan Gün- nemann. Randomized smoothing-inspired quantum encoding schemes with formal robustness guarantees. In Quantum Techniques Machine Learning, 2023.
[82] Xiaoshui Huang. Guofeng Mei, Jian Zhang, and Rana Abbas. A comprehensive survey on point cloud registration. arXiv preprint arXiv:2103.0200 2021.
[83] HA Almohamad and Salih O Duffuaa. A linear programming approach for the weighted graph matching problem. IEEE Transactions on pattern analysis and machine intelligence, 15(5): 522-525, 1993.
15

---

[84] Derek Justice and Alfred Hero. A binary linear programming formulation of the graph edit distance. IEEE Transactions on Pattern Analysis and Machine Intelligence, 28(8):1200-121) 2006.
[85] Julien Lerouge, Zeina Abu-Aisheh, Romain Raveaux, Pierre Héroux, and Sébastien Adam. New binary linear programming formulation to compute the graph edit distance. Pultern Recognition, 72:254 265, 2017.
[86] Richard Zhang. Making convolutional networks shift-invariant again. In International confer- ence on machine learning. 2019.
[87] Fabian Fuchs, Daniel Worrall, Volker Fischer, and Max Welling. Se (3)-transformers: 3d roto-translation equivariant attention networks. Advances in Neural Information Processing Systems, 2020.
[88] Ivan Sosnovik, Michat Szmaja, and Arnold Smeulders. Scale-cquivariant steerable networks. In International Conference Learning Representations, 2020.
[89] Diane Bouchacourt, Mark Ibrahim, and Ari Morcos. Grounding inductive biases in natural images: invariance stems from variations in data. Advances in Neural Information Processing Systems, 2021.
[90] Nate Gruver, Marc Anton Finzi, Micah Goldblum, and Andrew Gordon Wilson. The lic derivative for measuring learned equivariance. In The Eleventh International Conference on Learning Representations, 2023.
[91] Zhiping Zeng, Anthony KH Tung, Jianyong Wang, Jianhua Feng, and Lizhu Zhou. Comparing stars: On approximating graph edit distance. Proceedings of the VLDB Endowment, 2(1): 25 25-36, 2009.
[92] Ronghui Mu, Wenjie Ruan, Leandro S Marcolino, and Qiang Ni. 3dverifier: efficient robustness verification for 3d point cloud models. Machine Learning, pages 1-28, 2022.
[93] Aounon Kumar and Tom Goldstein. Center smoothing: Certified robustness for networks with structured outputs. Advances in Neural Information Processing Systems, 2021.
[94] Guang-He Lee, Yang Yuan, Shiyu Chang, and Tommi Jaakkola. Tight certificates of adversarial robustness for randomly smoothed classifiers. Advances in Neural Information Processing Systems, 2019.
[95] Greg Yang, Tony Duan, Edward Hu, Hadi Salman, Ilya Razenshteyn, and Jerry Li. Random- ized smoothing of all shapes and sizes. In International Conference on Machine Learning, pages 10693-10705. PMLR, 2020.
[96] Francisco Eiras, Motasem Alfarra, Philip Torr, M. Pawan Kumar, Puncet K. Dokania, Bernard Ghanem, and Adel Bibi. ANCER: Anisotropic certification via sample-wise volume maxi- mization. Transactions on Machine Learning Research, 2022.
[97] Alexander Levine and Soheil Feizi. Wasserstein smoothing: Certified robustness against wasserstein adversarial attacks. In International Conference on Artificial Intelligence and Statistics, 2020.
[98] Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representationss 2017.
[99] Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In International Conference on Learning Representations, 2019.
[100] Taco Cohen, Maurice Weiler, Berkay Kicanaoglu, and Max Welling. Gauge equivariant convolutional networks and the icosahedral enn. International conference on Machine learning, pages 1321-1330. PMLR, 2019.
16

---

[101] Pim De Haan, Maurice Weiler, Taco Cohen, and Max Welling. Gauge equivariant mesh {cnn]s: Anisotropic convolutions on geometric graphs. In International Conference on Learning Representations, 2021.
[102] Lingshen He, Yiming Dong, Yisen Wang, Dacheng Tao, and Zhouchen Lin. Gauge equivariant transformer. Advances in Neural Information Processing Systems, 2021.
[103] Jiequn Han, Linfeng Zhang, and E Weinan. Solving many-electton schrödinger equation using deep neural networks. Journal of Computational Physics, 399:108929, 2019.
[104] Di Luo and Bryan K Clark. Backflow transformations via neural networks for quantum many-body wave functions. Physical review letters, 122(22))226401, 2019.
[105] David Pfau, James S Spencer, Alexander GDG Matthews, and W Matthew C Foulkes. Ab initio solution of the many-electron schrödinger equation with deep neural networks. Physical Review Research, 2(3))033429, 2020.
[106] Jan Hermann, Zeno Schätzle, and Frank Noé. Deep-neurallnetwoork solution of the electronic schrödinger equation. Nature Chemistry, 12(10):891 -99 2020.
[107] Max Wilson, Nicholas Gao, Filip Wudarski, Eleanor Rieffel, and Norm M Tubman. Simula- tions state-of-the-art fermionic neural network wave functions with diffusion monte carlo. arXiv preprint arXiv:2103. 2021.
[108] Nicholas Gao and Stephan Günnemann. Ab-initio potential energy surfaces by pairing GNNs with neural wave functions. In International Conference on Learning Representations, 2022.
[109] Nicholas Gao and Stephan Günnemann. Sampling-free inference for ab-initio potential energy surface networks. In International Conference on Learning Representations, 2023.
[110] Max Wilson, Saverio Moroni, Markus Holzmann, Nicholas Gao, Filip Wudarski, Tejs Vegge, and Arghya Bhowmik. Neural network ansatz for periodic wave functions and the homoge- neous electron gas. Physical Review B, 107(23):235139, 2023.
[111] Nicholas Gao and Stephan Günnemann. Generalizing neural wave functions. International Conference on Machine Learning, 2023.
[112] Michael Scherbela, Leon Gerard, and Philipp Grohs, Towards foundation model for neural network wavefunctions. arXiv preprint arXiv:2303.0990 2023.
[113] Salman Khan, Muzammal Naseer, Munawar Hayat, Syed Waqas Zamir, Fahad Shahbaz Khan, and Mubarak Shah. Transformers in vision: A survey. ACM computing surveys (CSUR), 54 (10s):1-41, 2022.
[114] Charles R Qi, Hao Su, Kaichun Mo, and Leonidas Guíbas. Pointnet: Deep learning on point sets for 3d classification and segmentation. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 652-660, 2017.
[115] Yue Wang, Yongbin Sun, Ziwei Liu, Sanjay E Sarma, Michael M Bronstein, and Justin M Solomon. Dynamic graph CNN for learning on point clouds. Acm Transactions On Graphics (log), 38(5):1-12 2019.
[116) Zhirong Wu, Shuran Song, Aditya Khosla, Fisher Yu, Linguang Zhang, Xiaoou Tang, and Jianxiong Xiao. 3D ShapeNets: A deep representation for volumetric shapes. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1912-1920, 2015.
[117] Johannes Gasteiger, Shankari Giri, Johannes T. Margraf, and Stephan Günnemann. Fast and uncertainty-awant directional message passing for non-equilibrium molecules. In Machine Learning for Molecules Workshop, NeurIPS, 2020.
[118] Stefan Chmiela, Alexandre Tkatchenko, Huziel E Sauceda, Igor Poltavsky, Kristof T Schütt, and Klaus-Rober Müllerr. Machine learning of accurate energy-conserving molecular force fields. Science advances, 3(5)=1603015 2017.
17

---

[119] Kristof T Schütt, Huziel E Sauceda, P-J Kindermans, Alexandre Tkatchenko, and K-R Müller. Schnet-a deep learning architecture for molecules and materials. The Journal of Chemical Physics, 148(24), 2018.
[120] Yi Liu, Limei Wang, Meng Liu, Yuchao Lin, Xuan Zhang, Bora Oztekin, and Shuiwang Ji. Spherical message passing for 3d molecular graphs. In International Conference on Learning Representations, 2022.
[121] Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 3(2):127-163, 2000.
[122] Aleksandar Bojchevski and Stephan Günnemann. Deep gaussian embedding of graphs: Unsupervised inductive learning via ranking. In International Conference on Learning Repre- sentations, 2018
[123] Daniel Zügner, Oliver Borchert, Amir Akbarnejad, and Stephan Günnemann, Adversarial attacks graph neural networks: Perturbations and their patterns. ACM Transactions Knowledge Discovery from Data (TKDD), 14(5):1-31, 2020.
[124] Prithviraj Sen, Galilco Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. Al Magazine, 29(3):93, 2008
[125] Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. In ICML 2020 Workshop on Graph Representation Learning and Beyond (GRL+ 2020), 2020.
[126] Jinlai Zhang. Yinpeng Dong. Binbin Liu, Bo Ouyang, Jihong Zhu, Minchi Kuang, Houqing Wang, and Yanmei Meng. The art of defense: letting networks fool the attacker. IEEE Transactions on Information Forensics and Security, 2023.
[127] Oleksandr Shehur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. In Relational Representation Learning Workshop, NeurIPS, 2018.
[128] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference Learning Represen- tations, 2018.
[129] Tom Wollschläger, Nicholas Gao, Bertrand Charpentier, Mohamed Amine Ketata, and Stephan Günnemann. Uncertainty estimation for molecules: desiderata and methods. In International Conference on Machine Learning, 2023.
[130] Jerzy Neyman and Egon Sharpe Pearson. On the problem of the most efficient tests of statistical hypotheses. Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of Mathematical Physical Character, 231 2316694-706):28-3337 1933.
[131] Elexander Levine and Soheil Feizi. Robustness certificates for sparse adversarial attacks by randomized ablation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 4585-4593, 2020.
[132] Alexander Levine and Soheil Feizi. (de) randomized smoothing for certifiable defense against patch attacks. Advances in Neural Information Processing Systems, 2020.
[133] Huan Zhang, Tsui- Wei Weng, Pin-Ye Yu Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient neural network robustness certification with general activation functions. Advances in neural information processing systems, 2018
18

---

A Additional experiments
A.1 Point cloud classification
Different smoothing standard deviations. In Fig. 7 we repeat our experiments on permutation invari- point cloud classification for different smoothing standard deviations {0.05, 0.15, 0.25). The maximum certifiable correspondence distance increases linearly with a. For o 0.05, the average natural accuracy (i.e. certified accuracy at e = 0) of the smoothed PointNet and DGCNN models is 88% and 90.4%, respectively. Their certified accuracies are almost identical for most For the larger o 0.25, their accuracy decreases 75.5% and 79.9%, respectively, i.c. the difference in accuracy grows by p.p.. DGCNN also offers stronger robustness guarantees with certified accuracies that are up to 6.3 p.p.larger. The most important takeaway should however be that equivariance preserving prrserrrnn randomized smoothing provides sound robustness guarantees for equivariant tasks where discrete groups act on continuous data.
100%
100%
80%
80%
Cert. Acc.
Cert. Acc.
60%
60%
40%
40%
PointNet DGCNN
PointNet DGCNN
20%
20%
0%
0%
0.00
0.05
0.10
0.15
0.20
0.0
0.1
0.2
0.3
0.4
Correspondence distance 6
Correspondence distance
(a) a 0.05
(b) o = 0.1
100%
100%
PointNet DGCNN
PointNet
80%
80%
Cert. Acc.
Cert. Acc.
DGCNN
60%
60%
40%
40%
20%
20%
0%
0%
0.0
0.1
0.2
0.3
0.4
0.5
0.0
0.2
0.4
0.6
0.8
Correspondence distance
Correspondence distance
(c) o = 0.15
(d) o = 0.25
Figure 7: Provable robustness of smoothed PointNet and DGCNN point cloud classifiers on Mod- elNet40 for different smoothing standard deivations a. Correspondence distance is the Frobenius distance between point clouds after finding an optimal matching via permutation. For larger o, DGCNN offers better accuracy and provable robustness than PointNet.
Comparison to 3DVerifier. As shown in Fig. 7 Gaussian randomized smoothing with [0.05, 0.25] lets us retain relatively high accuracy while certifying robustness to correspondence distance perturbations of sizes up to e 0.8. However, as discussed in Section (5) Proposition 2 does not make any assumptions about how we prove traditional adversarial robustness. For example, 3DVerifier [92]. which is a specialized certification procedure for PointNet, can on average prove robustness robustness to & norm perturbations of size 0.959 (see Table 2 in 192). Because both the point cloud classification task and the PointNet architecture are permutation invariant, this directly translates to correspondence distance perturbations with an average size of 0.959. This experiment demonstrates that developing specialized certification procedures for a wider range of equivariant models is promising direction for future work. Nevertheless, smoothing remains valuable as a general-purpose certification procedure. For instance, 3DVerifier cannot prove robustness for DGCNN other point cloud classification architectures.
wwwawarinnne-peseevvie
randomized
16

---

A.2 Molecular force prediction
Different smoothing standard deviations. In Fig. we repeat our experiments on permutation and isometry equivariant force prediction on MD17 with different smoothing standard deviations f1, fm, 100 fm). The maximum certifiable registration distance grows linearly with o. This is inherent to Gaussian smoothing (see (20). The average certified output distance also grows approximately linearly. This can potentially be explained as follows: In sufficiently small region around clean input X. the model may have approximately linear behavior. If a is small, the output distribution will be similar to normal distribution whose covariances grow linearly with o². The certified of center smoothing are always between the median and maximum sampled distance from the smoothed prediction (see (93). which will in this case also increase approximately linearly.
Different base models. In Appendix A.2 we repeat our experiment with o = 1 fm and different base models, namely SchNet [19 and SphereNet [120]. SphereNet achieves lower average test errors between 0.45 and 1.4 /ooa//moo/A A than SchNet, which has errors between between 0.51 and 1.89 kcal/mol// A. However, the provable robustness guarantees obtained for SphereNet are worse than those for SchNet by more than an order of magnitude. For adversarial budgets of up to 2 fin, the average certified output distance 8 for SphereNet varies between 0.35 /cal/mol/a (Benzene) and 1.61 kcal/ /moo// A (Malonaldehyde), For comparison, the average certified output for SchNet vary between 0.04 kcal/mol/ À (Ethanol) and 0.12 kcal/mol/ Á (Uracil) and are quite similar (but not identical to) those for DimeNet++. We also observe much higher variance across random seeds.
Conclusion. While these observations may be interest to some readers that are specifically interested in machine learning for molecules, the most important takeaway should be that equivariance- preserving randomized smoothing can be used to obtain sound robustness guarantees for equivariant tasks in which continuous groups act continuous data.
Avg. 0 [kcal/mol/AA
Avg. [kcal/mol/A]
10.0
0.75
7.5
0.50
Aspirin
Napchalene
Aspirin Uracil
Napthalene
Utacil
Tohone
Tohene
0.25
Fitinne
Salkelie acid Malemá&ehyyde
2.5
Fifinndd
Salkelic acid
Henzene
Benzene
Malonakehyyde
0.00
150 Registration distance [fmm]
50
Registration distance é [fm]
(a) a 10
(b) a = 100
Figure 8: Provable robustness of smoothed DimeNet++ force predictions MD17 with smoothing standard deviations a E {10 fm, 100 fm The average certified output distance and the maximum certifiable registration distance grow (approximately) linearly with
Avg. 8 [[kca//mo//A]
Avg. [kcal/mol/A/
1.5
Aspirin
Napthalene
0.100
Uracil
Tolozne
Ethanol
Salicylic and
0.075
1.0
Benzene
Malomaldchyde
0.050
Aspirin
Napthalene
Uracil
Toloene
0.5
0.025
Fihuned
Salicyli acid
Benzene
Malenzkdehyde
0.000
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
Registration distance [fmm]
Registration distance [fm]
(a) SchNet
(b) SphereNet
Figure 9: Provable robustness of smoothed SchNet and SphereNet force predictions on MD17 with smoothing standard deviation a fm.. While SphereNet more accurate, provable robustness guarantees are weaker and have higher variance across different random weight initializations.
17

---

A.3 Node and graph classification
Next, we evaluate the different robustness guarantees for graph and node classification that we generalized to graph edit distance perturbations with user-specified costs (see Appendix
Convex outer adversarial polytopes for attribute perturbations. In Fig. we repeat our ex- periment on proving the robustness of 2-layer graph convolutional networks to graph edit distance perturbations. We use our generalization of the convex relaxation approach (see Appendix F.3). which was originally proposed in [10], on the Citeseer 124 node classification dataset. As before, we set A = CA oC and vary the cost of attribute insertion c and deletion cx. The result is qualitatively similar to our results on Cora-ML. Increasing the cost of attribute insertions leads to significantly higher certified accuracy. With cx = 1, the average certified accuracy for cx = 4 at edit distance <= 25 is 23.4%, which is much larger than the 6.6% for cx = 1. Increasing the cost of deletions does however not have noticeable effect, which matches the empirical observation that insertions are more effective when attacking graph neural networks [23]. The main difference to Cora-ML is that we have larger standard deviation across seeds. This is not necessarily surprising, since many
graph benchmarks are known to be sensitive to the choice of data split and model initialization 127
Note that the split and initialization for each seed the same in all experiments.
Cx
XX =
Cx
100%
100%
100%
100%
Cert. Acc.
75%
cx
Cert. Acc.
75%
Cx
Cert. Acc.
75%
ex
Cert. Acc.
75%
Cx
50%
2
50%
50%
2
50%
4
25%
25%
25%
25%
0%
0%
0%
0%
50
0
25
50
25
50
25
50
Edit distance
Edit distance e
Edit distance
Edit distance e
Figure 10: Convex outer adversarial polytope ro- bustness guarantees for GCNs under attribute per- turbations on Cora-ML.
Figure 11: Convex outer adversarial polytope ro- bustness guarantees for GCNs under attribute per- turbations on Citeseer.
Interval bound propagation for attribute perturbations. In Figs. 12 and 13 repeat the same experiment using our generalization of the interval bound propagation approach (see Appendix F22) originally proposed in [12]. Unlike before, increasing single cost parameter while keeping the other one at 1 has no noticeable effect on the certified accuracy. A potential explanation is that interval bound propagation only offers very loose guarantees. For example, the maximum certifiable edit distance on Cora (see Fig. 12) is 10, compared to over 50 with the previously discussed convex relaxation approach. The relaxation might simply be too loose accurately capture the effect of different perturbation types on the models.
Cx
XX
1
Cx
xx
1
100%
100%
100%
100%
Cort. Acc.
75%
cx
Cert. Acc.
75%
CX
Cert. Acc.
75%
ex
Cert. Acc.
75%
Cx
50%
2
50%
50%
50%
25%
25%
25%
25%
0%
0%
0%
0%
25
50
0
25
50
0
25
50
0
25
50
Edit distance
Edit distance
Edit distance
Edit distance
Figure 12: Interval bound propagation robustness guarantees for GCNs under attribute perturbations on Cora-ML.
Figure 13: Interval bound propagation robustness guarantees for GCNs under attribute perturbations on Citeseer.
Policy iteration for adjacency perturbations. Next, we consider perturbations of the adjacency matrix. We begin with our generalization of the policy iteration approach (sce Appendix F.6)
18

---

originally proposed in ... This robustness guarantee is specifically designed for T-PPNN, which is APPNP [99] where the degree normalized adjacency matrix D D-1/2AD)
is replaced with D- A. Different from the other guarantees, we do not have a single global budget e. Instead, we only have nodewise budgets Pl....: PN with Pn= = (Dn. c s) with an arbitrarily chosen constant e and attack strength s. Like in M. we set the resulting certified accuracies on Cora-ML and Citeseer for Cx cx = oo and varying CA CA- Again, increasing the cost of adversarial perturbations to ç = 4 has larger effect, in some cases almost tripling the certified aceuracy. But there is also a small increase of up to 2.9 p.p. certified accuracy when increasing the deletion cost CA from 1 to 4 on Citeseer.
11 and vary attack strength s. Figs. 14 and 13 shows
CA =1
1
C = 1
CA = 1
CA
100%
100%
100%
100%
Cert. Acc.
75%
CAA
Cert. Acc.
75%
CA
Cert. Acc.
75%
Cert. Acc.
75%
CA
50%
2
50%
50%
2
50%
25%
25%
25%
25%
0%
0%
0%
0%
9
0
4
9
0
9
0
4
attack strength
attack strength
attack strength
attack strength
Robustness guarantees for 7-PPNP under adjacency perturbations on Cora-ML. Note that we do not have global budget and instead vary per-node budgets.
Figure 14:
Robustness guarantees for T-PPNP under adjacency perturbations on Citeseer. Note that we do not have a global budget and instead vary per-node budgets.
Figure 15:
CA
1
CA
1
100%
100%
100%
100%
Cert. Acc.
75%
Cert. Acc.
75%
Cert. Acc.
75%
Cent. Acc.
75%
CA
50%
50%
50%
50%
25%
25%
25%
25%
0%
0%
0%
0%
20
0
20
0
20
0
20
Edit distance E
Edit distance e
Edit distance E
Edit distance
Figure 16: Linearization and dualization robust- ness guarantees for GCN graph classifiers under adjacency perturbations on PROTEINS.
Figure 17: Linearization and dualization robust- ness guarantees for GCN graph classifiers under adjacency perturbations on MUTAG.
Bilinear programming for adjacency perturbations. Generalizing the bilinear programming method for proving robustness of GCNs to adjacency perturbations proposed in [13] from cx Cx = cx 1 to cx E Ry, does not require any modifications, since scaling the cost is equivalent to scaling the adversarial budgets (see Appendix F.4p. We thus refer to 3 for experimental results.
c
Linearization and dualization for adjacency perturbations. Next, we consider GCN-based node classifiers and adjacency perturbations. We prove robustness via our generalization of the procedure proposed in 15). This guarantee is specifically designed for single layer GCNs followed by linear layer and max-pooling, Since Cora-ML and Citeseer are node classification datasets, we instead use the PROTEINS and MUTAG datasets from the TUDataset [25 collection, which were also used in [5]. Figs. 16 and 17 show the resulting certified accuracies for fixed cx Cx = oc and varying adjacency perturbation costs C and c Unlike in all previous experiments, increasing the cost of deletions also leads to a significant increase for the same edit distance budget c. On PROTEINS, choosing A = 1 and A = 4 even yields stronger robustness guarantees than CA 4 and eΛ = 1. For example, the average certified accuracies for budget are 61.2% and 55.6%, respectively (see Fig. 16]. This may be caused by one of multiple factory. Firstly, we have a different task graph instead of node classificaton. Secondly, we have a different architecture that aggregates
19

---

information from the entire graph via max- poolliniiig instead of just using local information. Thirdly, the considered graphs have a significantly different distribution than Cora-ML and Citeseer. For instance, Cora-MI. and Citeser consist of 2708 and 3327 nodes, respectively, whereas the average number of nodes in PROTEINS and MUTAG is 17.9 and 39.1. Cora-MI. and Citeseer also have much sparser adjacency matrices, with just 0. 14% and 0.08% non-zero entries.
Sparsity aware randomized smoothing for attribute and adjacency perturbations. Finally, we perform additional experiments with sparsity-aware randomized smoothing 14]. As we discussed in Section 5.1 this randomized smoothing method preserves isomorphism equivariance and can thus be used to prove adversarial robustness for arbitrary isomorphism equivariant models and tasks w.r.t. graph edit distance and both attribute and adjacency perturbations. Figs. 18 show the certified accuracy of graph convolutional networks, graph attention networks [28 (GAT), and APPNP on Cora-MI. and Citeseer for varying costs of attribute and adjacency perturbations with smoothing parameters x 0.001, . = 0.8. = O,PA = O and p = 0. = P = 0.001, 0.8 While the different models and datasets differ slightly with respect to (certified) accuracy, we observe the same effect in our previous node classification experiments: Only increasing the cost of insertions has a large effect on provable robustness for any graph edit distance e, which suggests that these perturbations are significantly more effective at changing the prediction of the models.
Conclusion. Overall, there are three main takeaways from evaluating the different graph edit distance robustness guarantees. Firstly, even though evaluating the graph edit distance is not tractable, it is possible to prove robust under to provide sound robustness guarantees for isomorphism equivariant tasks. Secondly, unless they use very loose relaxations (like interval bound propagation), generalizing existing guarantees to non-uniform costs provides more fine-grained insights into the adversarial robustness of different graph and node classification architectures. Thirdly, equivariance pareeerrrigg randomized smoothing is an effective way of obtaining sound robustness guarantees for equivariant tasks where discrete groups act on discrete data.
ex
cx
1
CA
1
1
100%
100%
100%
100%
Cert. Acc.
75%
ex
Cert. Acc.
75%
4'
Cert. Acc.
75%
CA
Cert. Acc.
75%
CA
50%
50%
2
50%
50%
25%
25%
25%
25%
0%
0%
0%
0%
5
10
0
5
10
0
5
10
0
10
Edit distance é
Edit distance e
Edit distance e
Edit distance
Figure 18: Randomized smoothing robustness guarantees for GCNs under attribute perturbations on Cora-ML. The Smoothing parameters are set to p = 0.001, Px = 0.8, PA O.PA = O.
Figure 19: Randomized smoothing robustness guarantees for GCNs under adjacency perturba- tions on Cora-ML. The moothing parameters are set to Px = Px = 0, = 0.001, PA = 0.8.
Cx =1
xx = 1
Cj
2 = 1
100%
100%
100%
100%
Cert. Acc.
75%
cx
Cert. Acc.
75%
Cx
Cert. Acc.
75%
CA
Cert. Acc.
75%
CA4
50%
50%
2
50%
2
50%
2
25%
25%
25%
25%
0%
0%
0%
0%
5
10
0
10
0
5
10
0
10
Edit distance e
Edit distance e
Edit distance e
Edit distance e
Figure 20: Randomized smoothing robustness
Figure 21: Randomized smoothing robustness guarantees for GCNs under adjacency perturba- tions on Citeseer. The moothing parameters are
guarantees for GCNs under attribute perturbations on Citeseer. The Smoothing parameters are set to
PX = 0.001 Px = 0. = 0. PA O.
set to Px = 0.P 0, PA = 0.001, PA = 0.8.
20

---

ex
cx
1
CΛ
c 1
100%
100%
100%
100%
Cort. Acc.
75%
CX
Cert. Acc.
75%
Cx
Cert. Acc.
75%
Cert. Acc.
75%
CA
50%
2
50%
50%
50%
25%
25%
25%
25%
0%
0%
0%
0%
5
10
0
5
10
0
5
10
0
10
Edit distance
Edit distance
Edit distance E
Edit distance
Figure 22: Randomized smoothing robustness guarantees for GAT's under attribute perturbations on Cora-ML. The Smoothing parameters are set to x = 0.001, Px = 0.8, PA O.PA = O.
Figure 23: Randomized smoothing robustness guarantees for GAT's under adjacency perturba- tions on Cora-ML. The moothing parameters are
set to Px = 0, Px = 0, P, = 0.001, PA = 0.8.
Cx = 1
cx =
1
CA = 1
ex = 1
100%
100%
100%
100%
Cort. Acc.
75%
cx
Cert. Acc.
75%
Cx
Cert. Acc.
75%
CA
Cert. Acc.
75%
CA
50%
50%
2
50%
2
50%
25%
25%
25%
25%
0%
0%
0%
0%
5
10
0
5
10
0
5
10
0
10
Edit distance
Edit distance
e
Edit distance e
Edit distance
Figure 24: Randomized smoothing robustness guarantces for GATs under attribute perturbations on Citeseer. The Smoothing parameters are set to
Figure 25: Randomized smoothing robustness guarantees for GATs under adjacency perturba- tions Citeseer. The moothing parameters are
pX 0.001, Px = PA = PAP = O.
set to Px
0,Px = 0, = 0.001, = 0.S.
Cx
Cx
CA
e 1
100%
100%
100%
100%
Cert. Acc.
75%
Cert. Acc.
75%
ex
Cert. Acc.
75%
CA
Cert. Acc.
75%
CA
50%
2
50%
2
50%
2
50%
4
25%
25%
25%
25%
0%
0%
0%
0%
5
0
10
0
5
0
10
Edit distance c
Edit distance c
Edit distance c
Edit distance
Figure 26: Randomized smoothing robustness
Figure 27: Randomized smoothing robustness guarantees for APPNP under adjacency perturba- tions on Cora-ML. The moothing parameters are
guarantees for APPNP under attribute perturba- tions on Cora-ML. The Smoothing parameters are O,PA- = O.
set to Px 0.001, 0.8,
Px P 0, = 0.001, = 0.8.
xx
xx =1
C
100%
100%
100%
100%
Cort. Acc.
75%
cx
Cert. Acc.
75%
Cx
Cert. Acc.
75%
Cert. Acc.
75%
CA
50%
50%
50%
50%
25%
25%
25%
25%
0%
0%
0%
0%
5
10
0
5
10
5
10
10
Edit distance
Edit distance
Edit distance e
Edit distance
Figure 28: Randomized smoothing robustness guarantees for APPNP under attribute perturba- tions on Citeseer. The Smoothing parameters are set to Px = 0.001, Px = 0.8, PA = 0.P = O.
Figure 29: Randomized smoothing robustness guarantees for APPNP under adjacency perturba- tions on Citeseer. The moothing parameters are
set to Px = 0, Px 0, P = 0.001, PA = 0.8.
21

---

A.4 Adversarial attacks
As discussed in Section any traditional adversarial attack is valid adversarial attack under our proposed notion of adversarial robustness for equivariant tasks. This holds no matter if the equivariances of task y and model f match or not. As an example we conduct adversarial attacks on PointNet classifier and a graph convolutional network. We use the same datasets, models and hyperparameters for the experiments shown in Fig. B (without randomized smoothing) and Fig. TO To attack the PointNet classifier, we use single gradient step w.r.t. cross-entropy loss, which we scale to have l norm of c. To attack the graph convolutional network, we use the method from Section 4.4 of [10] which is directly derived from their certification procedure. As can be seen, future work is needed to further improve the robustness of equivariant models to our proposed perturbation model.
100%
100%
80%
80%
Accuracy
Accuracy
60%
60%
40%
40%
20%
20%
0%
0.0
0.4
0.6
20
Correspondence distance
Edit distance
(a) PointNet
(b) GCN
Figure 30: Adversarial attacks on (a) PointNet using a single gradient step with &, norm c and (b)
GCN (with perturbation costs ox cx 1) using the method from Section 4.4 of [10].
22

---

B Full experimental setup
B.1 Point cloud classification
For our experiments on point cloud classification, we replicate the experimental setup from [26]. where randomized smoothing was also applied to point cloud classification. We just use different base models, which are not rotation and translation invariant. Each experiment (including training) is repeated 5 times using different random seeds. We report the mean and standard deviation in certificate strength across seeds.
B.1.1 Data
All experiments are performed on ModeINe which consists of 9843 training samples and 2468 test samples from 40 classes. We apply the same preprocessing steps as in [14 transform the CAD models into point clouds consisting of 1024 points, i.e. random sampling on the surface of the objects and normalization into the unit sphere. We use 20% of the training data for validation. All certificates are evaluated on the test data.
B.1.2 Models
We two different models, PointNet 114 and DGCNN 1T5
For PointNet, we use three linear layers (64, 128, 1024 neurons) before pooling and three layers (512, 256, 40 neurons) after pooling. Before feeding imput point clouds into the model, multiply them with a matrix predicted by a T-Net, i.c. another PointNet with three linear layers (64, 128, 1024 neurons) before pooling and three linear layers (512, 256, 3 3 neurons) after pooling. We hatch normalization (e = 1e - 5, momentum = 0.1) for all layers, except the output layer. We use dropout (p 0.4) for the second-to-last layer.
For DGCNN, we use four dynamic graph convolution layers (64, 64, 64, 128 neurons) with k-nearest neighbor graph construction (k 20). The outputs of all four layers are concatenated, passed through a linear layer (1024 neurons), then max-pooled across the node dimension and finally passed through three more linear layers (512, 256, 40 neurons). We use batch normalization for all layers (e (e= 1e 5, momentum = 0.1). We use dropout (p = 0.4) for the second-to-lass and third-to-lase layer. Before feeding input point clouds into the model, we multiply them with 3 x 3 matrix predicted by the same T-Net architecture we described for PointNet.
B.1.3 Training
We use the same training parameters in 126] We train for 200 (PointNet) or 400 (DGCNN) epochs using Adam (3₃ = 0.9, 32 = 0.99, = Ie 8, weight weight_decay = 1e 4e=4) with a learning rate 0.001 and exponential weight decay with factor 0.7 every 20 (PointNet) 40 (DGCNN) epochs. We use a batch size of 128 for PointNet and 32 for DGCNN. We add the T-Net loss proposed by [114] to the cross entropy loss with weight of 0.0001. The data is randomly augmented via scaling by factor uniformly sampled from 00.8, 1.25]. We additionally add isotropic Gaussian noise with the same standard deviation use for randomized smoothing (0.05, 0.1, 0.15, 0.2 or 0.25).
B.1.4 Certification parameters
perform randomized smoothing with isotropic Gaussian noise (a E {0.05, 0.1, 0.15, 0.2 or 0.25)) and majority voting (20). We use 1,000 Monte Carlo samples for prediction and 10,000 Monte Carlo samples for certification. We compute the Clopper-Pearseee confidence intervals for class probabilities with 0.001, i.c. all guarantees hold with high probability 99.9%.
B.1.5 Computational resources
All experiments involving PointNet were performed on Xeon E5-2630 v4 CPU @ 2.20 GHz with a NVIDA GTX 1080TT GPU. The average time for training model was 21.1 min. The average time for certifying the robustness of single model on the entire test set for different budgets e was
81.7 min.
23

---

All experiments involving DGCNN were performed on an AMD EPYC 7543 CPU @ 2.80GHz with NVIDA A100 (40 GB) GPU. The average time for training a model was 161.9 min. The average time for certifying the robustness of a single model on the entire test set for 50 different budgets was 601.7 min.
B.2 Molecular force prediction
Like with point cloud classification, we train and certify 5 different models using different random seeds on common benchmark dataset. We report the mean and standard deviation in certificate strength across all seeds.
B.2.1 Data
We use the original (not the revised) MD17 [18 collection of datasets. It consists different datasets, each consisting of a large number (between 133 770 and 993 237) of spatial configurations of specific molecule. For each dataset, 1000 for validation and 1000 for evaluating the robustness guarantees. We use the same data split for all experiments.
1000 randomly chosen configurations for training,
B.2.2 Models
We use DimeNet++ [17]. SchNet [19 and SphereNet [120] as our base model. All models predict atomic energies. Force are calculated via automatic differentiation w.r.t. the input coordinates.
For DimeNet++, we use the default model parameters for MD17 force predictions specified [TT> There 4 layers with 128 hidden channels. The triplet embedding size is 64. The basis embedding size is 8. The output embedding size is 256. The number of basis functions 8 (bilinear), 7 (spherical), (radial). The cutoff radius for graph construction is 5 A. The number of residual layers before the skip connection is 1. The number of residual layers after the skip connection is 2.
For SchNet, we use 128 hidden channels and 128 filters. We the number of interaction blocks to and use 50 Gaussians. The cutoff distance is 10 A, with a maximum number of 32 neighbors. We use addition as our global readout function.
For SphereNet, we use layers with 128 hidden channels. The triplet embedding size is 64. The basis embedding size 8 for distance, angle and torsion. The output embedding size is 256. The number of basis functions is 8 (bilinear), 7 (spherical), 6 (radial). The cutoff radius for graph construction is 5 Å. We use swish activation functions. The number of residual layers before the skip connection is The number of residual layers after the skip connection is 2.
B.2.3 Training parameters
To train DimeNet++ and Schnet, we use ADAM with learning rate of 0.001. We use linear warmup with exponential decay our learning rate scheduler (1000 warmup steps, 400,000 decay steps, decay rate of 0.01) and train until convergence with a patience of 50 epochs and a convergence threshold of 10-4.
To train SphereNet, we use ADAM with a learning rate 0.001. We use "reduce on plateau' as our learning rate scheduler (decay factor of 0.8, patience of 80 epochs, convergence threshold of 10" 4, cooldown of 10 epochs) and train until convergence with a patience of 50 epochs and a convergence threshold of 10
We do not add randomized smoothing noise during the training process.
B.2.4 Certification parameters
We perform randomized smoothing with isotropic Gaussian noise (a {1 fm, 10 fm, 100 100ff)) and center smoothing (93] with default parameters aj = 0.005, a2 0.005, = 0.05, i.e. guarantees hold with high probability 99%. We use 10,000 samples for prediction, 10,000 samples to test for abstention and 10,000 samples for certification. In our experiments the smoothed model never abstained.
24

---

B.2.5 Computational resources
All experiments for molecular force prediction performed Xeon E5-2630 v4 CPU @ 2.20 GHz with a NVIDA GTX 1080TI GPU. We trained 4 models simultaneously. The average time for training a + model was 28.9 h. The average time for certifying the robustness of single DimeNet++ model on 1000 molecule configurations for 1000 different budgets was 10.49 h.
B.3 Node and graph classification
In Section 5.2 we generalized six approaches for proving the robustness of graph neural networks with respect to graph edit distances. While the approaches differ, we mostly use the same datasets and models. As before, we perform each experiment (including training) with 5 different random seeds and report the mean and standard deviation in certificate strength across all seeds.
B.3.1 Data
We use two standard node classification datasets, Cora-ML [21
(2,708 nodes, 10,556 edges, 1,433 features. classes) and Citeseer [24 (3,327 nodes, 9,104 edges, 3, 3,703 features. 6 classes), and two graph classification sets, PROTEINS (1, 113 graphs, 3 features, 2 classes) and MUTAG (188 graphs, features, 2 classes), which are part of the TUDataset [T25]. These datasets were also used in the papers that proposed the original certification procedures. With Cora-MI. and Citeseer, we follow the procedure from [44 and use 20 nodes per class for training, 20 nodes per class for validation and the remainder for evaluating the certificates. With PROTEINS and MUTAG, we use 30% of graphs for training, 20% for validation and the remainder for evaluating the certificates.
B.3.2 Models
The main model we use for node classification is standard 2-layer graph convolutional network with ReLU nonlinearities and 32 hidden features. We insert self-loops and perform degree normalization via D-2 AD
For node classification, we use the architecture described in [5], i.c. a single layer GCN with 64 neurons, followed by linear layer and max- max-pooling. We also insert self-loops, but perform degree normalization via A.
With sparsity-awarr randomized smoothing, we additionally use graph attention networks 128 and APPNP [22]. We implement all GNNs with two-layers and 32 hidden dimensions, except GAT for which we implement 8 hidden dimensions and 8 attention heads. For APPNP we further set k_hops=10 and teleport probability a = 0.15.
For the experiments with certificates for the m-PPNP architecture we set teleport probability 0.15 and use hidden dimension of 64.
B.3.3 Training parameters
We train models for a maximum of 1,000 (T-PPNP), 3,000 (other node classifiers) or 200 (graph
classifiers) epochs with Adam (Ir = 1e 3, B1 0.9, 82 0.99, 1e 8) and cross entropy loss. For node classification we additionally use weight decay 5e 4 and early stopping after 50 epochs. For node-classiffcation we perform full-batch gradient descent. For graph classification we use minibatches of size 20. For the sparsity-ware randomized smoothing experiments we use a dropout of 0.5 on the hidden node representations after the first graph convolution for GCN and GAT, and additionally on the attention coefficients for GAT. For randomized smoothing we additionally add apwre noise the training data. We use the same flip probabilities for certification.
B.3.4 Certification parameters
For interval bound propagation and the convex outer adversarial polytope method, we set the nodewise local budgets .ı,... : PN
1% of input features, just like in [10].
For our generalization of the graph classification certificate from, we set the local budget p., of node with degree d, to min(0. d,, maxx dm +3), like in [15). We additionally enforce symmetry
25

---

of the adjacency matrix via Lagrange dualization (see Appendix A.3 and perform 200 alternating optimization steps using the default parameters from [5]
We perform randomized smoothing with sparse noise (PX 0.001, PX = 0.8, P
= 0, or pX 0, Px 0. P 0.001. P = 0.8) and majority voting [14]. For node classification we use 1,000 Monte-Carlo samples for prediction and 1,000,000 Monte-Carlo samples for certification. For graph classification we use 1,000 Monte-Carlo samples for prediction and 10,000 Monte-Carle samples for certification. We compute the Clopper-Peane Pearson confidence intervals for class probabilities with a = 0.01, i.c. all guarantees hold with high probability 99%.
B.3.5 Computational resources
All experiments were performed on Xeon E5-2630 v4 CPU @ 2.20 GHz with NVIDA GTX 1080TI GPU. With interval bound propagation, the average time of training and certifying model for 100 budgets was 1.2 min on Cora-MI. and 3.0 min on Citeseer. With the convex outer adversarial polytope method, the average time of training and certifying model for 100 budgets was 9.7 min on Cora-ML and 14.4 min on Citeseer. With the linearization and dualization method for graph classifiers, the average time of the average time of training and certifying model for 100 budgets e on the entire test set was 1.2 on MUTAG and 48.1 h on PROTEINS, With the policy iteration method for T-PPNP, the average time for training and certifying model for 10 attack strengths was 126.1 min. With sparsity-aware randomized smoothing. the average time for training and certifying a model for 1000 budgets
267.7 min.
B.4 Third-parts assets
Since we extend various existing methods for proving the robustness of graph neural net- works, we naturally built upon their reference implementations. For interval bound propaga- tion and convex outer adversarial polytopes, we extend the reference implementation from [10] For the linearization and dualization method, we extend the reference implementation from [5] For the policy iteration method, we extend the reference implementation from [ hhtpp::/github.com///bii ctt./boojchwsssk/ggrpppppppp cert). For sparsity-aware randomized smoothing on graphs, use the reference implementation from [14] (https:///itthub. http://hhwwu.oooooocccccs/s///// /ttp//ppprsssssottiinggg.
For equivariance- prwpencvieeeeeiiingggg randomized smoothing on point clouds, we use the training and sampling procedure from [26] (https//github.com/jaa) wttp:///w....ooccccccccccttiiiii schuchardt/ivvariance wwaarrddiinariannc--mottnng
All of the above are available under MIT license.
To train models for molecular force prediction, we use a pre-release version code from 129 for (orrrrraatttyfoooommeeeeeess which we will include in our reference
implementation.
26

---

C Proof of Proposition
In the following, we show that the action-induced distance is the only function din x IR + R+ that fulfills all three desiderata defined in Section 4.1 These were
Vx, 9 G d1n x²) dm)(,,
Vx, dm (z, x²) & (x,
(x)) max,ED (I,
where ID is the set of functions from X x X to R4 that fulfill the first two desiderata
Proposition 1. A function dmp : x X + R4 that fulfills all three desiderata for any original dis- tance function din X x X + R2 exists and is uniquely defined: dm (x,x') = mingec (In g x').
Proof. Consider specific pair x' X' The first desideratum states that must have dm (I,x') du (z.g 9 x') for g G. The second desideratum states that we must have d (x. g x') dia (z, xx) for all G. Thus, by the transitive property. fulfilling both desiderata simultaneously for our specific and x' is equivalent to Vgg E G (x, x²) S diu (2, g x'). This is equivalent to din (2r, x') S mingeg din (2.g x²). The left side of the equality is naturally maximized fulfill the third desideratum when we have strict equality, i.c. (x, = mingeG (n, gox".
27

---

D Combining smoothing measures and smoothing schemes
Most randomized smoothing literature can be divided into works that focus on investigating properties of different smoothing measures (e.g.
94 955 and works that propose new smoothing schemes (e.g. 120 75 77 93 Measure-focused works usually only consider classification
14
60)
65
tasks, while schuse-focused works usually only consider Gaussian measures. But, as we shall detail the following, any of the smoothing schemes discussed in Section be used with arbitrary smoothing measures to enable certification for various input distances dn and output distances dout-
D.1 Smoothing measures
Measure-focused works usually consider a base classifier h : X + with Y
(l....,A. K).
They define family of smoothing measures (Mz)aex to construct the smoothed classifier f(x) maxsey PIzmzu [h(2) = 1t). To certify the predictions of such a smoothed classifier, they derive lower and upper bounds the probability of classifying perturbed input x' E X as specific class E {1...., .......,.J...... i.e. ph.x',k I PIz=ay [h()) = k] S Ph,,', These bounds are usually obtained by
finding the least most robust model that has the same clean prediction probability as base classifier h, i.e.
Ph,z', min Pr 1xx-V amppe
[h(()) = k)
s.t.
Pr gopl
h1(2) = k Pr
[h(=) k],
gnitz
Ph,z' max Pr 1x zmple
h(z)) = k)
s.t.
Pr znept
h(z)) = k.
Pr
[h(z)=
k]
As long as μl and Pe have a density, these problem can always be solved exactly via the Neyman- Pearson lemma [30].
For appropriately chosen smoothing measures (fu)zex, one then identify that the perturbed probability bounds ph.a',k and Ph,a', only depend on a certain distance function din X x - R+. For example:
For X = -V,, and Us NN(x I), the bounds Ph.x',k and Ph,za, & only depend on
din( x²) = ||x æ'I12 and are monotonically decreasing / increasing (00).
For = RN,, and U = Laplace(x, o I), the bounds Ph.=',k and Ph, only depend on
di (2. .x)
æ²1|1 and are monotonically decreasing / increasing 995
For = (0, and μ being the measure associated with i.i.d. flipping of input bits, the bounds Ph. & and Ph,x' A only depend on d dz, x²) || æ'llo and are monotonically
decreasing increasing 94
For an overview of various additive smoothing schemes and their associated input distances, see 995] Note that works on pon-additive smoothing measures, like ablation smoothing [31] or derandomized smoothing [32]. also provide bounds Ph. &e and Ph.=*, &e as a function of some input distance dma. such the number of perturbed pixels the size of an adversarial image patch.
D.2 Smoothing schemes
Scheme-focused works include majority voting 20]. expected value smoothing (75,, median smooth- ing 777 and center smoothing [93] These works only consider Gaussian smoothing, i.e. X R and (A = N(x a I). Each one proposes a different prediction procedure and certification procedure. The prediction procedures provide sampling- based approximations of the smoothed prediction {(u o 1-1 and does not depend on the choice of smoothing measure. The certification procedures can be adapted arbitrary smoothing measures as follows.
Majority voting, Majority voting assumes a base classifier h X + Y with Y = (1...,,K) constructs smoothed classifier fxx) maNtey Presps [h(2) kj. The prediction f(z)= = 1s of this smoothed classifier is robust if Ph,x', > max Ph, or if ph, > 0.5. This certification procedure can be adapted to any other smoothing measure by inserting the corresponding lower and
or continuous relaxations thereof, if any constant likelihood region has non-zero measure
28

---

upper bounds. It can be generalized to multi-outpin classification tasks with Y = (1...., K} (e.g. segmentation) by applying the certification procedure independently each output dimension.
Expected value and median smoothing. Median smoothing and expected value smoothing assume base regression model h : X + R. They construct smoothed model f(æ)) via the expected value or median of pushforward measure fa h-1 To certify robustness, they require lower and upper bounds on the cumulative distribution function Pra-né [h(=) & az] for a finite range of thresholds de - ... dg co. Since each of the indicator functions [h(2) I ar) can be thought of as binary classifier 9t X - {0, 11. these lower and upper bounds are given by Pg..a'.1 and Pg..ar,1- These certification procedures can thus be adapted to any other smoothing measure by inserting the corresponding lower and upper bounds. They can be generalized multi-outpul regression tasks with = by applying the certification procedure independently to each output dimension. Instead of proving that the smoothed prediction f(x:) remains constant, these smoothing schemes guarantee that the output remains in a certified hyperrectangle HH = {y E R Im S Zm I um J. One can then prove that dout (f(z), (x²)) I 6 by verifying that {y E RM dout (f()), y) I 8} HI, i.e. the hyperrectangle contains dout-ball of radius ó.
Center smoothing. Center smoothing is compatible with any model X V. as long the output space W fulfills a relaxed triangle inequality. It constructs a smoothed model f(x: via the center of the smallest ball that has at least 50% probability under pushforward measure Hez o h- To certify bustness, it requires bounds on the cumulative distribution function Pre-nçs 1 [dout (f(æ), h[() S az). Thus, like with expected value and median smoothing, this certification procedure can be adapted to any other smoothing measure by inserting the corresponding bounds Pg. and PT. This smoothing scheme directly provides upper bound on dout (fx)), f(x').
Informally speaking, any of these schemes can be adapted to non- non-Gaussian measures by replacing which are the formulae for P and ,h.=', & of Gaussian measures (20. with the bounds of another smoothing measure. For example, one can combine the bounds from derandomized smoothing with the center smoothing certification procedure to prove robustness of generative image reconstruction models to patch-based attacks.
any occurence of & (...) ....) and & (......)+.......
29

---

E Equivariance-preseriing randomized smoothing
In the following, we provide more formal justifications for our randomized smoothing framework, that we introduced in section Section 5.1 and that is visualized in Fig. 31 We first verify the correctness randomized smoothing. We then consider
of our sufficient condition for wwtpaaaiinnneppeeeeviee the different equivariances preserved by different smoothing schemes and measures. We provide tabular overview of different schemes, measures and their properties in Tables 2
Concerning notation for pushforward measures. Consider measurable spaces (X, D) and (V, R), and a mcasurable function X + V. We write h -1 to refer to the preimage of function h, not its inverse. That is, for any A V we have h h- (A) we have h h-1 (A) E ID whenever A E F. Thus, the expression o (A) refers to the measure of all elements of X that get mapped into & E F, i.e. it is the pushforward measure of μs
fx E X h(z) E A}. Because f is measurable,
fx
Mx h
fxx
X
V
h
g
9
X
X
V
Y
h
Tzg (x)
Mx Tx.9
Mx h- TV
T2.9 (f))
Figure 31: Example of wwwparaiinne-peseevinne randomized smoothing for X V Y TR.2 and diagonal translation group G = (RR +), which acts via Ta. x 2 1. We construct our smoothed model using Gaussian measures Mx= = (ax a 1). base model h X + and expected value smoothing scheme & A(V, FF) + Y, which maps from measures intermediate space (V, IF) to output space Y. Measures are visualized via isocontours of their densities. Because the family of measures (P=)=ex is equivariant (left cycle), the base model h is equivariant (central cycle). and the smoothing scheme & is equivariant (right cycle), the smoothed model f(x) = E 1) is also equivariant to diagonal translation.
E.1 Proof of Proposition
Proposition 3. Assume two measurable spaces (X, FV, an output space Y and a measurable base model h: X + V that is equivariant with respect to the action of group G. Further assume that G acts on X and V via measurable functions. Let & ((V + Y be a smoothing scheme that maps from the set of probability measures A on intermediate space (V, to the output space. Define Tx.g(-) (-) to be the group action on set for a fixed g, i.e. Tx.g(x) = 9 *% x. Then, the smoothed model fxx) [(pz h- is equivariant with respect to the action of group G if both
the family of measures (Hu)zex is equivariant, i.e. Vr E Xx g G Mgoz fx T=1 and smoothing scheme is equivariant, i.e. Vv AVV G Elv T E(v).
Proof. By definition of f, verifying that Var E X Vy E G verifying that E(gger o h -11 = g E(u, o -1). We can do so by first using the equivariance of the family of measures (fæ)zEX, then the equivariance of base model h and then the equivariance of
f(g .) g f(x) is equivalent to
30

---

smoothing scheme ç:
E(Ugen o - -
xig o h1))
= No o (T о h
= Ne o (h Txgg)
= & (No o (Iv. o h1)
= (Mz (h-1 TTg.9)
= ((1z o h) Tx.9 = E(U, o h-
In the second and sixth equality we used the associativity of function composition. In the third and fifih equality we used that the preimage of a composition of functions is equivalent to the composition of the individual preimages in reverse order.
E,2 Equivariance--reeservin schemes and measures
In the following, A AXX D) refers to the set of all probability measures on measurable space (X, ID).
E.2.1
Componentwise smoothing schemes.
For this type smoothing scheme. we assume that the intermediate space and output space consist of M distinct components, i.e. V = A and Y = BB' for some sets A. B. We write proj.. AM - A for the function that maps any vector E A. to its mth component Om- Thus, for any measure E A(A M JPa) ) the function v projm is the mth marginal measure, which is a measure on the single-dimensional space (A, F). Componentwise smoothing means generating the mth prediction based on some quantity of the mith marginal measure.
Proposition 4, Assume an M M-diimensonal measurable product space (AM, FM) and an output space BM. Further assume that there is a function κ. : A(A, F) - B such that Vv AA ,M)) ((V)m k<v projm'). If group G acts &N and B via the same permutation. then the smoothing scheme & is equivariant.
Proof. Consider arbitrary
G with corresponding actions Tv.g AM AM with Tv. (v)
Ux (m) and Tv. A + AM with Ty (1) (y) m U/-)((m) where {1...., M) (1.....M, M)
a permutation. For any m, we can use the definition ç, the associativity of function composition and the fact that the preimage of composition is equivalent to the composition of preimages in reverse order to show that
E {VV TV. = R (v TTgy) projm!)
vo (TV
y projmm))
on (projm Tv.9) )
v pro)
(m)))( (g o (v))
For the fourth equality we used that selecting the mith element from a sequence permuted by π is equivalent selecting the element (m)) of the unpermuted sequence. The second to last equality just the definition of our smoothing scheme ç.
In practice, componentwise smoothing schemes are not evaluated exactly but approximated using S Monte Carlo samples (11), ...., (S) E V. The mith component of smoothed prediction yn is generated based on some quantity of um same argument as above to show that the Monte Carlo approximations are permutation equivariant: Permuting the components of the samples before applying componentwise functions is equivalent to first applying componentwise functions and then performing permutation.
(5) E V, such as their mean 75 We can thus use the
31

---

E.2.2 Expected value smoothing scheme.
For this smoothing scheme, we assume that the intermediate and output space coincide are real-valued, i.e. V Y R We then make smoothed predictions via the expected value the model's output distribution over Y.
Proposition 5. Let (IR be the corresponding Borel o-algebra of gM, Define expected value smoothing scheme ARR ,B(*")) + IR with
{(V) - | JR
y dvly)
If group G acts on R&M via affine transformations, then smoothing scheme & is equivariant.
Proof. Consider an arbitrary g E with corresponding action Tr.g By change of variables and linearity of integration, we have
& {( Iv
S y (od (z)
Tx. duly)
Tv.a (fr duly)
9 E(V).
In practice, expected value smoothing is not evaluated exactly but approximated using the average of S Monte Carlo samples (1)) (5) M [75]. We can thus use the same argument as above to show that the Monte Carlo approximation equivariant to affine transformations: Affinely transforming the samples before computing the average is equivalent to computing the average and
then applying the affine transformation.
E.2.3 Median smoothing scheme
For this smoothing scheme, we assume that the intermediate and output space coincide and are real-valued, i.c. = Y AM We then make smoothed predictions via the elementwise median of the model's output distribution over V. As before, we write projm R.M + R for the function that maps any vector E M to its mith component Pm. Thus, o projm is the mth marginal measure of v.
Proposition 6. tion function for marginal measure v projm - i.e.
Let B(RM) be the Borel o-algebra T. Let Fm (v, be the cumulative distribu-
Fm x) (v o projm') ((-o0,a)).
Let Fm (v. p) and F# (v, p) be the corresponding lower and upper quantile functions, i.e. Fm = inf(x Fm 2 p}
F = sup(# Fm (v. S p}
Define median smoothing scheme E ARRM, B(RR + MM with
E(V)m 2 F (v. 1/2) + (v, 1/2)
If group G acts on Y via elementwise linear transformations, then smoothing scheme & is equivariant.
Proof. Consider an arbitrary E G. Let Tv.g be the corresponding group action with (Y) m Wm ym Cm for some Wm, Cm R. Assume w.L.og.. that Vm Wm 0.
For the cumulative distribution functions, we have
F. (v TT x) Fm (v, (x cm) / Wm))
32

---

For the corresponding lower and upper quantile functions, we thus have
Fm (v/ Iy ( Wmm Fm p) + Cm F (v 1z p) = Wm F (v. p) + Cm
For the smoothing scheme, we thus have
E(v T Wm E(v)m Cm (g E(v))m.
In practice, median smoothing is not evaluated exactly but approximated using the elementwise me- dian of S Monte Carlo samples ((t), ((9) [75]. We can thus use the same argument as above to show that the Monte Carlo approximation is equivariant elementwise linear transformations: Linearly transforming the samples elementwise before computing the sample median is equivalent to computing the sample median and then applying the elementwise linear transformations.
E.2.4 Center smoothing scheme
For this type of smoothing scheme, we assume that the intermediate and output space are identical, i.e. V= Y. Let By, = (v/ E EY| dout (y,y') S J be the dout ball of radius r around E Y. Center smoothing makes its predictions using the center of the dout ball with the smallest radius among all dome balls with measure of at least 2.
Proposition Consider a measurable space (Y, a function dout Y Y Rt, and assume that Vy E Yrr 2 0 B(y,r) E F. Define center smoothing scheme & A(Y,F) F) - Y with {(v) arg min, y r s.l. v (B(y,r)) 2 2. If G acts isometrically on Y, i.e Vy. E Y.g G
dout 9 g.g = dout (v: vf), then smoothing scheme & is equivariant.
Proof. Consider an arbitrary g E G with corresponding action Ty.g. By definition of the center smoothing scheme, E(v o T is
1 = arg min s.t. v arg min s.t. ( (B(y. r)) 2 y
( コラ )
E.g
y
By definition of the preimage and action Ty. we have Ty (B(y r)) Ev' y' E B(y = {v' dout (g-
{v/ dout (v.g go)ggoy')) <r) equality holds because acts isometrically. This shows that
y,v') < r}
B (g v.r) where the second to last
{(v o T arg min r s.t. (Bigg
y, yrr)) z
The optimum of this problem is g (V)), because g (g (v)) {1v) and ((v) is the optimum of the original problem without group action.
In practice, center smoothing is approximated using Monte Carlo samples y (1),
(8) Y
by selecting the sample with the smallest median distance dout to all other samples [93] We can use similar argument to the one above to show that the Monte Carlo approximation is isometry equivariant: Isometries, by definition, do not change the pairwise distances and therefore do not change which sample has the smallest median distance to all other samples.
E.2.5 Product measures
For our discussion of product measures, note that the o-algebra DN of a measurable product space (AN, D is not the n-fold Cartesian product of the o-algebra D. Instead, it is defined as
{X
S1 DD...,,NN E TD) i.e. the set containing all Cartesian products of measurable
m=1
sets.
Proposition 8. Assume that (pe )pen is a family of product measures on the N-dimensional measurable product space N D D.),, i.e. there is family of measures (Ka)aes on (A, D) such that
Va AN, N.YY (X"=)s,) permutation, then the family of measures (Mæ) is equivariant.
Sn) TDN pe (Xm= Sm) = -I Kiz,, (Sn). If group G acts on A via
33

---

Proof. Consider an arbitrary E G with action Txg AA + A with TV (x,)(x), = 2 where [I....,NN {I, , } N is permutation. For any (X Sn) B.,, we have
N
N Nen (Sx(a)) pa
N X
Mgew
X
Sn
II (gem)), (Sn)
II n=1
(Sn)
II
For the second to last equality, we have just changed the iteration order of the product from (L,..., N) to (I(1), (NN).. Finally, it follows from the definition of our group action and preimages that
X (7())
= fsr E AN
81 E EI(())...., SN E ST(N))
= {s E AN
81- ESI,.... SI,..., STN)(NN E ST(N)}
s A
(x.g($)
E
X Sy
Tx
X Sn
n=1
and thus Vo E AM g E G Pgen
Pa o %.g"
E.2.6 Isotropic Gaussian measures
Proposition 9. Consider the measurable space NRNxD, B(RNxD)), where BDD is the Borel a- algebra NxD Let (JIx X be the family of isotropic Gaussian measures with standard
deviation (R. N B(R If group G acts isometrically D with respect to
Frobenius norm || l|,. then the family of measures is equivariant.
Proof. By definition of the Gaussian measure, have for any A B(RNxD)
o = /
IIII
D
1
20 (nnd - x22,2) dz
exp
2
n=1
d=1
1
20 1 - -x1 dz.
N.D
exp
V2T02
By change of variables, have
(NX.0 o Tx.) (A) = Jmmgee)) (V2TT²2)
1
2 - 1-x1 dz
N.D exp
20
-/ det (Jzz
| ( - -x1 dz
N.D exp
(V2TT))
20
J (V2TT))
1
1
Tx (x)11 dz
N.D exp
-20=
20
Xg (A)).
The third equality follows from Tx., being an isometry with respect to the Frobenius norm || 112-
E.2.7 Thansformatioo--specffe measures
In transformation-specfiic smoothing [46] 60 63-65), the clean input x X is transformed via
randomly sampled functions from parametric family )ooe with tha : X - X and measurable parameter space (O, G). Let 7 G R_, be the corresponding parameter distribution. Then, transformation-specffic smoothing induces a smoothing measure
(A( (10 θ fe(x) A))
(3)
34

---

on input space (x, D). In the following, we show that this induced measure inherits its equivariances from the family of transformations (Vo))cs le
Proposition 10. Consider measurable space (X, D) and parametric family of transformations (vo))ese with thg % - % and measurable parameter space (e,G). Ty: G R- be a measure on parameter space (Ø, G) and consider the family of induced smoothing measures (12))eX as
defined in Eq. 33. If all transformations th are equivariant to the actions of group G, then the family of measures equivariant.
Proof. Consider an arbitrary group element 9 E G with corresponding group action Tx.g By definition of μa and the equivariance of all tee we have for all E X that
Mga (A) 7 (10 E θ folg A))
= 7 g
E A})
= 7 ((0E0) So(x) E (2)(4))) (un Txz! (A).
The second-to-last equality holds because, by definition of the pre-image, (x) (x X x E } and thus g fa(x) E b Sa(x) E (A).
E.2.8 Sparsity-aware measures
Proposition 11. Consider the measurable space (X, )D,, where = (0. (0.1) x (0, 1JNNN is the set of all binary attributed graphs with N nodes and features and DD PXX) is its powerset. Let (px,A)(x, AAexx be the family of sparsity-aware aware measures on (X, DD), as defined by the sparsity-
aware probability mass function with fixed flip probubilities vxx v vf. Pr E [0, (see Eq. (18). If group G acts on % via graph isomorphisms, then the family of measures is equivariant.
Proof. Group G acting on X via graph isomorphisms means that for every (X, A) E X and g E C there is some permutation matrix P E {0, 11. x such that g (X, A) = (PX, PAP"). That is, the entries of the attribute and adjacency matrix are permuted. The aparsity-awand measures product measures, i.c. sparsity-award aware smoothing perturbs each element the attribute and adjacency matrix independently. Families of product measures equivariant with respect the action of groups acting via permutation, see Proposition g
Table 1: Suitable measures for different input domains X, input distances dm, and group actions.
din
Group action
Smoothing measure
NND
l 8oo
Permutation, Translation
Uniform(-o,0)
RND
f1,6x
Permutation,
Laplace(O,
Translation
RNDD
82
Euclidean isometries
INDD
to
Permutation
Discrete smoothing (sce Lee et al. [80])
(0, 1 x {0, NJNN (Attributed graphs)
Edit cost (see Eq. (2)
Sparsity-aware smoothing (see Appendix E.7)
Graph isomorphism
'Assuming V& D: (0) fo(x) E A) G.e.e. all preimages are in the parameter o-fied G.
35

---

Table 2: Suitable smoothing schemes for different output domains Y, output distances dout, and group actions (see discussion in Section 5.1). (*)For expected value and median smoothing, robustmess can be certified as long as the dout ball (v/ dont (f()).// S e) contained within hyperrectangle (see Appendix D.2
dout
Group action
Smoothing scheme
(1...., KJN N
Eo
Permutation
Elementwise majority voting
Permutation, Affine
RN
Any"
Expected value
Permutation,
RN
Any"
Elementwise median
Elementwise linear
Isometry w.r.t. dous
Any
Any
Center
(e.g. Fuclidean isometries for E2)
36

---

Graph edit distance certificates
In the following, show how the different existing approaches for proving the robustness of graph w.r.t to distance dia
neural networks operating on {0, 1jNxD {0, 1] 1.x8 x N
-1(1'-X - -X) + 11(X' - x) + II - A)+Ilo + ca II(A' (on'-A)llooy A)- (4)
with costs cx, CA E foo, 1) can be generalized to non-uniform costs, i.e. Cx CA.
{oo} R. Combined with Proposition 2 this yields robustness guarantees w.r.t. to the graph edit distance, where the edit operations
insertion and deletion of edges and/or node attributes. Note that we also consider local budgets ,,,.... PN. which we introduce Appendix G
Before making the different generalizations, discuss how to solve Knapsack problems with local constraints, which will be used in many the subsequent derivations.
Please note that providing an in-depth explanation and motivation for each of the certification procedures would be out of scope. Instead, we strongly recommend first reading the original papers. Our discussions are to be understood as specifying changes that have to be made relative to the original certification procedures.
F.1 Knapsack problems with local constraints
A recurring problem in proving the robustness of graph neural networks is selecting set of edges attributes that have the largest effect on a classifier's prediction while complying with global and node-wise constraints on the cost of perturbations. This is form of Knapsack problem.
Definition 2. knapsack problem with local constraints a binary integer program of the form
N
M
max QE (0.1)
Σ
Vn,m Qn.
NXM
==1
N
M
M > Cn.m Qn.m S Pr:
s.t.
On,m Qn.m Sc Vn m=
with value matrix V NxM cost matrix C R.N global budget E R,, and local budgets Pi.-.., ,PN E IR
Matrix Q indicates which entry of an attribute or adjacency matrix should be adversarially perturbed.
When there are only two distinct costs, i.c. we are only concerned with attribute or adjacency perturbations, the above problem be solved exactly via dynamic programming. Alternatively, an upper bound can be found via linear relaxation, i.e. optimization over [0, N
F.1.1 Dynamic programming
In the following, assume that there is an index set II C I such that V(n, m) T Cn,m c+ and V(n, m) E T: C,,m costs. In this case, the problem from Eq. (5) can be solved in two-step procedure, which generalizes the certification procedure for uniform costs discussed Section of [15].
(1,.., M) with complement i.e. only have distinet
The first step is to find optimal solutions per row т, while ignoring the global budget e. We pre- compute N dictionaries a1...... ON N N -> R4 and N dictionaries 31, ................................ By N x N + P((1...., M)), where is the powerset. Entry a1, is the optimal value of Eq. (5) if only row Q, non-zero, and exactly indices in and j indices in are non-zero, i.c.
N
M
(,,1) =
max Nxx
Σ
Σ
Vn,m
Qn.m
n= m=
Σ Qn.m = Q-r n.mel
s.t.
mnmm i,
or sparse matrices
37

---

Entry (i) is the corresponding set of non-zero indices of the optimal Qr. Because all entries of value matrix V and cost matrix C' are non non-negative, the optimal solution is to just select the indices with the largest value Vn,m- This pre-processing step is summarized in Algorithm | Its complexity is in ON ((max, Pr)) / ((max, Pn) c )), i.e. scales linearly with the number of rows and the maximum number of non-zero values in row of Q.
The second step combine these local optimal solutions while complying with the global budget and local budgets Pl...... PNN. This can be achieved via dynamic programming. We create dictionaries
$1..... SN. with s, (7) being the optimal value of Eq. (5) when only allocating budget to the first rows and incurring an overall cost of y.
N
(T(7)
max QE(0.1)XXM
Vn, Qn.
n=l mi=1
s.t.
Σ PLRRE
c
cc- Qn.m= =7
Q = 0.
n.mei
The first dictionary, 81, can be generated from the precomputed optimal values 01- After that, each dictionary 8, can be generated from 1y-1, while ensuring that we remain within local budget Pa and global budget e. The optimal value is given by max, 87(7). In addition, we generate dictionaries (1,..., LN. which aggregate the row-wise optima stored in 91....; .N such that (x(>*) with 7 argmax, (N gives us the non-zero entries of the optimal Q. This procedure is summarized in Algorithm 2 Its complexity is in O(N (c/ct) (c///t/())))))))))) ((max, Pn)) / ct) ((max, Pn) / cT)),, iee it scales linearly with the number of rows, the maximum number of non-zero values in Q, and the maximum number of non-zero values in a row of Q. Note that graph neural networks are generally brittle to small adversarial perturbations, so the algorithm only needs to be executed for small 6.
Algorithm 1 Precomputation of local solutions
for
,,...,N do On, 3n <- dict()
best_ <- argsort_cod argsorr_dcsco(( Vn)
best add idx best idx II
best_del_idx &- best jexsl_ixx \I max_ _d___ <- / c+]
for i= i max max_adds addss do
max_dels <- Lpn ct 1) c-
for j j .,.., max mal_dels do
an - sum({Vn.t k best add idxx:ix((
an(i, + an(i,) + mumi(Vz,, k k E [eee___e__xx(:]]]] (d)))
(i. t sct(best_ades add idxxixx({)) set(best dcl del idx]:))
return O1,...,, ONN. ,,,...,8N
38

---

Algorithm 2 Construction of the global solution from local solutions
lo - () dict()
(0
(0()) -- []
for n .,.... do
Sn, d) dict() for prev_cos keys( do
b b- miminn max_adds -- b// ct
preeppeeoo cost)
for i 0..... max adds do max_dels + [(b-c (1b-ca c ii) ] for J = 0, ...... max_ dels do
? 4 prev_cost + c i c .j
sp-1(prev_comm costt) + Ot (i,j) y $ keys($n) or > (n) then
5n (7) +
tn - concatenate(t (prevv_oss)))) 3(i,j))
7 ( return (N(1"),(N("")
F,1.2 Linear relaxation
The above dynamic programming approach can generalized to arbitrary cost matrices E R N However, it may not scale because it requires iterating over all possible combinations of costs admitted by global budget and local budgets Pl,- p1....: PN. more efficient alternative is upper-bounding the xM to
optimal value of the knapsack problem in Eq. 5 by relaxing the binary matrix Q E {0, N real values Q E [0, N
max QERNXA XM
Vn.m Qn.m
n= m
(6)
Σ
Σ
Cn.m Qn,m Se,
Vn Eonm Cum Qn,m S Pno
Vn, m 0 Qu.m. Vn, Qn.m
Intuitively, it is best to set those Qn.m to that have the largest value-to-coss ratio, i.c. the largest Vn,m / Cn,m- To comply with the local and global budgets, one should first greedily select the (n, (n. with the largest ratio in each row until the local budgets Pa are exhausted. One should then aggregate all these row-wise optimal indices and select those with the largest ratio, until the global budget is exhausted. This procedure is summarized in Algorithm
39

---

Algorithm 3 Optimal value of the linearly relaxed knapsack problem with local constraints (Eq. > Initialize global allocations with N x M zeros. Initialize row-wise allocations with N x M zeros. > Elementwise division. Division by 0 is defined as co.
Q' + 0
L 0
R t V
for I,..., do best_cols cols t argsort desc (oesc(R,,) R
b Pn for m E bost colt_colsoor do
In, t b Ca,
Im. t min(1, (n, mm)
Clip, to avoid allocating values larger than 1.
b b Cn,m Lmn.
best_idx - gegsort_desee
c
for (n,m) m) E best_ idx do Qi.m + b/ Cn.m
Qn.m f- min( Tmmmm Q7,m) f Cn.m mn.m
Clip, avoid violating local budget constraints.
return Enm Vn.m Qu.
Proposition 12. Algorithm 3 yields the optimal value of the linearly relaxed knapsack problem with local constraints, as defined in Eq. (6).
Proof. To simplify the proof, we make certain assumptions about budgets and ,l...., PN- If <= 0, then the value of Q computed by Algorithm is obviously correct, because the only feasible solution that does not violate the global budget is Q* 0. If pn 0 for some then the value of Qn computed by Algorithm 3 is obviously correct, because the only feasible solution that does not violate the local budget is Qi O. We thus assume w.l.o.g. that > 0 and Vn Pn O. Furthermore, we assume that the budgets do not exceed the maximum overall and row-wise cost, ie.. e < Σ
nn= Em=r Cn.m and Vn M Cn,m S Pn. since any excess budget will not have any effect on the optimal value of Eq. (6)
In the following, we prove the correctness of Algorithm by verifying that the constructed solution fulfills the Karush-Kuhn Beass--Kun-TTuukkke conditions. We define the Lagrangian
N
M
N
M
L(Q, X, K. T,U)
Vna
Ou. + A
Σ
Σ
Cr.m - Qum -
n=
m=1
m=1
M
M
N
Fin
Σ m=
Cn. Qu.
Pn
Σ
T Ta,m Qu.m+
Σ n= m==1
Unm (Qu, 11) -1
n=1
n=1m= m==1
We introduce a negative sign in the objective, because Eq. (6) is maximization problem. Variable E E, corresponds to the global budget constraint, variable E R. correspond to the local budget
constraints and variables T, U RRN correspond the constraint that Q should be in [0, 1] NN X
We claim that Q, X, k. T and U have the following optimal values:
The optimal value Q is the Q" computed by Algorithm
The optimal value is X* mill,.m m. Vn.m / Cn.m S.t. Qi.,. O, with Q' computed as in Algorithm 3 That is, X is the smallest value-to-cost ratio for which some global budget is allocated.
Define o,, = minm Va. / Cn.m S.t. Ln,m > 0 with L computed as in Algorithm That is, on is the smallest value-to-cost ratio in row n for which some local budget allocated. The optimal value of Kn, is x max(0, on )*).
The optimal value of Unm is U maxx(Vn. Cn. (A* Rr)),
40

---

The optimal value of Tu.m is T n. -V + Cr.m (A* +n,) Un which is equivalent to max VV. + Cn. (X* xx))).
Stationarity. By the definition of T we trivially have Qu.. L(Q" X² K<" ,,",""," -0)=,-0)----
+ Cn.m (X* + kmp) T.m Un, 0.
Primal feasibility. The clipping in Algorithm 3 ensures that vn, m budget and local budgets Pl..... PN are never exceeded.
Qu. S and that global
Dual feasibility. Because all values V and all costs C' are non-negative, the optimal values X", K² are non-negative. The optimal values T and U are non-negative by definition.
Complementary slackness. We first verify complementary slackness for variable A. Because we assume that the global budget does not exceed the maximum overall cost Σ Σm Cr,m and all values V are non-negative, Algorithm will always allocate the entire global budget, i.c.
Σ
Σ
Cu,m
2r.m -c
0=
m=
Next, verify complementary slackness for variable We make case distinction, based the value of Ky max(0, On - -x)). If On I X2, we have
M
Kip
Σ
Ca. Qn.m
Pn =0
Σ Wi=1
Ca. Qn.m
Pn
O.
If On, >> X", then - by definition - the smallest value-to-cost ratio for which budget is allocated in row is larger than the smallest value-to-cost ratio for which budget is allocated overall. Combined with our assumption that the local budget Pn. does not exceed the overall cost Em=1 Cr,m row n, this means that the entire local budget Pn. is used up, i.c.
M
Σ m==
Cr,m
Qu,m
Pn = Ki 0.
Next, we verify complementary slackness for variable T. If Qr.m = O, we obviously have T n.m (- (-Qr.m) = 0. For Q² > O, recall that Tim = max(0, - Vn,m Cr.m (X* + kt)). Because we defined ne, = max(0, on - X*), ). we have X + KT = max(A* , On,m X and V Vn . Cn,m on show that max(0, V m. + Cu.m (X* xT)) 0.
o.)). We can thus verify Vn, 2
We defined X to be the smallest value-to-cost ratio for which Q > Vn,m 2 Cn.m X" whenever Q > O.
We thus know that
We defined on be the largest value-to-cost ratio for which Lnn 0. Due to the clipping
in Algorithm 3 we know that Ln,m 2 Q We thus know that, if Q > 0, then Ln, > 0 and
thus Vn,m Cn.m On--
Combining these two results confirms that Ti 0 if Qi... > and thus T (-Qinm) = O.
Finally, we verify complementary slackness for variable U using similar argument. If Q 1, we trivially have U* n,m (Q",, - 1) = 0. For QT,, < 1, recall that U (A+K,, 0). We can again use that X- + K", = max(A*, on). There are two only two potential causes for Qi... 1. The first one that all the local budget Pr. was used up in column of row n or columns with higher value-to-cost ratio. In this case, we have Vn,m & Cn.m -On- The other one is that all of the global budget e was used up entry (n, m) or entries with higher value-to-cost ratio. In this
max(Vn... Cn.m
case, we have Vn,m & Cn.m X" Overall, this implies that U n.m. (Qr,. 1) 0 (Q"
0.
F.2 Interval bound propagation for attribute perturbations
Liu et al. 12 propose to prove the robustness of T.-layer graph convolutional networks 98 to 1, CA oo) via interval bound
attribute perturbations with uniform cost (cx Cx
41

---

propagation. In the following, we generalize their guarantees to arbitrary attribute perturbation costs ex-O E p.
Graph convolutional networks applied to attributes X E {0, 1x and adjacency A E {0, 1 are defined as
H X
2 (1) ÁH W + 1(6 for / = .,..., for l I,..., L,
H の0 (Z
where W
are bias vectors, g(1), ,....., g(L) are activation functions (here assumed to ReLU in the first layers and softmax in the last layer), and Á is the adjacency matrix after additional preprocessing steps, such degree normalization.
((L-1) ((-.)) are weight matrices, (( ......., b(L
Given a perturbation set IB, interval bound propagation proves the robustness of a prediction yn arg max; H arg max, Z(L-!) by computing elementwise lower and upper bounds R()) and
(()) on the pre-activation values ( and elementwise lower and upper bounds R()) and S on
the acttvactiitionn values H via interval arithmetic. If vk + Yn ((L-11) s(L-1) then the prediction Yo for node n is provably robust.
n.k
In our case, the perturbation set is
B = (X',, A X E (0,1) AE (0,1NNxN,
A' A,
(8)
1 + +ox ||(X -X- s, vn: |1(X, x,) + + 11(X, X,) S pa):
with global budget e and local budgets Pa-
We propose compute the lower and upper bounds R and ( for the first pre-activation values
by solving knapsack problem with local constraints (see Definition 2 via the methods discussed in Appendix F.1 We define the cost matrix C E R to be
6 Xn.d =
Cn,d
Cx
Xn,d 1.
To obtain an upper bound 1 we define the value matrix V E NxD to be
( Ar. A max((= d, d.. 0) if Xnnd = A,n maa-max(-W"
Vn
. 0)
if X = 1.
That is, setting an attribute X,,d from to makes positive contribution to upper bound S the corresponding entry of the weight matrix is positive and there is an edge between nodes n and i. makes positive contribution, if the corresponding entry of the
Setting an attribute Xn,d from weight matrix is negative and there is edge between nodes and i. We then solve the knapsack problem and add its optimal value the original, unperturbed pre-activation value z!!)
To obtain lower bound R R.O we analogously define the value matrix V RRNx
Nx to be
A (Ain- (maxx(-:100 a.. 0)
if X
Vn.d
A max(w/1)) d, 0) if Xn,d = 1,
multiply the optimal value of the knapsack problem with -1 and then add it to the original, unper- turbed pre-activation value 2,00
42

---

After we have obtained the lower and upper bounds for the first layer's pre-activation values, we can use the same procedure as Liu al. [2 bound the subsequent post- and pre- pre-activation values:
R ReLU((((-))
for 1 = 1,... . L 1,
5(0) ReLU(S((-1)s
for I...., L
R (A W (1) (AS W ( + 1(b())
for 1,..., 1 1,
S() (Ā _ (1) + (AS W + 1(b()T
for 1,....
with W+ = max 0, W) and W- = mO, W FF * yn Rn.. > Sn,k
5((-1) then the
prediction yn for node n is provably robust. In our experiments, we use linear programming and not the exact dynamic programming solver for the knapsack problems (see Appendix E.I.
F.3 Convex outer adversarial polytopes for attribute perturbations
Zügner and Günnemann [10] also propose robustness guarantees for L-layer graph convolutional networks (see Eq. (7) under attribute perturbations with uniform cost (c = Cx = 1, = CA = oo). However, their method solves a convex optimization problem and yields robustness guarantees that are always at least as strong as interval bound propagation. Again, we want to generalize their guarantees to arbitrary attribute perturbation costs c C E IR...
Let (x A) be the pre-activation values in the last layer, given attribute matrix X (0. NxD and adjacency matrix E {0, 1)NxN.
prediction yn arg max, ( A) 1n, k robust to all perturbed X', A' from perturbation set B vk # ya. v(X', AA) E B: Z(L-11 (X', n' (LL-1) n. This is equivalent to showing that, for all ks + yn:
Z ((1-1) (x', A') (X
min
(XX, A'),A') A'),, 0.
Solving these i optimization problems is generally intractable due to the ReLU nonlinearities and the discrete set of perturbed graphs B. Zügner and Günnemann [10) thus propose to make two relaxations. The first relaxation is relax the integrality constraints on the perturbation set IB, In our case, this leads to the relaxed set
B = {XX', A E [0, 1| A E [0,1]
A' = A,
(10)
*x (X' - X)+111 + cx 11(XXX -)) S,, Vn : xx ||(X,, xx) + 11(X, x,) S pn)
Note that we now use & instead of tu norms. The second relaxation is to relax the strict functional dependency between pre- and post-activation values ( (eLU(Z()) to its convex hull:
(
! hull (aa, ReLU(a) RR R S s12 )). n.d)
where R and ((!) are elementwise lower and upper bounds on the pre-activation values ()), We propose to use the modified interval bound propagation method introduced in Appendix F.2 obtain these bounds.
These two relaxations leave us with an optimization problem that almost identical to the one discussed in [10]. We just weight insertions and deletions with constants cx and c instead of uniform weight 1 and have different values for the elementwise pre-activation bounds. We can thus go through the same derivations as in the proof of Theorem 4.3 in [10] while tracking the constants <x and ex to derive the dual of our relaxed optimization problem, which lower-bounds Eq. (9). We highlight the difference to the result for uniform costs in red. The dual problem for local budgets
43

---

and global budget e is
max
(x,c(X,52,1
20 ,.. (....) M,,
Ω E [0, Nxx0 N R. R+,
for l L 1,..,
(LI)
where ((9) is the number of neurons in layer and
S R nJ
L-1
Ip.c 9pc(X,S0,K,))) Ks = Σ
(1)
Σ 1=0
1 (1+)))))))))
R
1= (mj)EZ())
Tr
x $
(0)
Σ
Pri Kn
X,
where I is the set of unstable neurons in layer 1, i.c. I
{(n,)) R S 0 < 5 and
j= y
=
0
otherwise
$1)
ÄT Φ (I+1) (WO)T
for
1 = L I,...,0
if 5(1) 0
1
(11) n.j
8 njjj
if Raj >
for l,...
(1) n1,]
+ 20
(111
if (n, E z())
R.!
n.
max (An,d - Cx
(Nin + 2),
if X 0
L n.d
max
[An, - Cx (Nin + 2),
if Xn,d
An.d
(0)
(1 Xn,a)
[5000]
Xn.d-
The indexing changes are necessary because we consider L and not (L ( layer networks. The sign changes are necessary because we define the clipping negative values differently, i.e. X_ min( X, 0) and not X
(Xn,X, 0). Aside from that, the only difference are the costs cx and
cx in the definition of Nr.
Because this is dual problem, any choice of Ωt and yields lower bound on Eq. optimal parameters yields a tighter bound.
9
But using
Proposition 13. Define value matrix V and cost matrix C = x [1 X Then,
C
The optimal value of is X minn, Vn.n / Cn.m s.t. Qi, > with Q' computed as in Algorithmm 3 That is, X is the smallest value-to-cost ratio for which some global budget
is allocated.
Define on min Vn,m / Co.m 8.1. In,m > with computed as Algorithm That is, on is the smallest value-to-cost ratio in row for which some local budget is allocated. The optimal value of Kn is K", = max(0, On - X²).
Proof. For any fixed (1) (L-1)) we can go through the same derivations as in the proofs of Theorems 4.3 and 4.4 in [10 while keeping track of constants cx Cx to show that the above
optimization problem is up to an additive constant equivalent to
E +
Σ pn Kin + e n=1
min | NERY UER NXD n.d
s.t. Und 2 Vna
Ond Kn Cndd
44

---

with V - and C c - + [X]]
By standard construction, the dual of the above linear program is
M Vum Qn.m
Σ
max QERNXM
n=1
m=1
NVC
M
s.t.
Cr.m Qu.m Sc, Vn:
Σ
Cn. Qn,
I Pr:
1= m=1
m==
Vn, m S Qn.m,
Vn, m. Qn.m 1.
This is exactly the linearly relaxed knapsack problem with local constraints from Eq. (6) During our proof of Proposition] 12 via Karush- Kuhn- Kuhn-Tucket Tucket conditions, we have already shown that X* and k are the optimal values of the dual (here: primal) variables.
Since have optimal values for variables and of the optimization problem in Eq. 11 only need choose values for Ω ;..... (((11), They be either be optimized via gradient ascent set to some constant value. In our experiments, we choose
50h
2
n
S
$0
as suggested [TO. As discussed in [TO,, the efficiency certification procedure can further improved by slicing the attribute and adjacency matrix to only contain nodes that influence the hidden representation of node n in each layer l.
E4 Bilinear programming for adjacency perturbations
Zügger and Günnemann 13 derive guarantees for the robustness of graph convolutional networks to edge deletions (cx cx = CA = xc, CA = 1). Generalizing these guarantees to arbitrary costs
A E R4 does not require any additional derivations. Multiplying the cost by factor k is equivalent dividing global budget and local budgets pı,..., Pr. by factor k.
F.5
Linearization and dualization for adjacency perturbations
Jin et al. [15] derive robustness guarantees for graph elassifiers consisting of 1-layer graph convo- lutional network followed by a linear layer and mean pooling under adjacency perturbations with uniform cost (c)
20, C CA 1). In the following, we want generalize their guarantees arbitrary c'A and CA.
Cx
In fact, the authors propose two different approaches. The first one involves lincarization of the neural network and the formulation of Lagrange dual problem enforce symmetry of the perturbed adjacency matrix. The second one combines Fenchel biconjugation with convex outer adversarial polytopes to derive lower bound that is then optimized via conjugate gradients. While the second objective is sound, its optimization via conjugate gradient may be numerically unstable, which is why an entirely different solver is used in practice In order not mispresent the contents of (15). we focus on the first approach, which offers similarly strong guarantees (see Fig.4 in (55).
The considered graph classification architecture is
N
F(X, A) = Σ ReLU (D-AAW) U/N,
where À A is the adjacency matrix after introducing self-loops, i.e. setting all diagonal entries to DE E I N with D,,; 1 A, is the diagonal degree matrix of Á, W Dx are the graph
convolution weights and U R "I are the linear layer weights for K classes.
SSee out.g///hhhooooooooooooo/aaaaaae
45

---

As before, robustness for specific prediction arg max, F(X, A))x under perturbation set IB can be proven by showing that the classification margin is positive, i.e.
Vk +
min (X'AA))3
F(X', A F(X', A') > 0.
For this specific architecture, this is equivalent showing that, for all k + y.
min Σ Sn,a(''' A') (X,A)EB
with A = 1'''',
ReLU (A'')) (U - -,,)) /N.
Note that we could move the degree of node n of the nonlinearity because it only scalar factor. Our perturbation set is
B
{XX', A x E (0, 13,1 A (0,1)
X' = X,
(12)
A || -X) + CA ||(X' - -X-110 S, +c Vn ot -1(X,, xx) + CA 1I(X; - x10 S Pm).
Lincarization. Unless one wants to find the worst-case perturbation for each fn,* via brute-forcing (which is viable approach for very small budgets and discussed in [I5). the first step of the certification procedure to find N linear models that lower-bound the nodewise functions fn, for
all possible perturbed inputs. That is, we want find vectors (1))...,, R.N and scalars
5(2) ,..., ((N) R.K such that
V(xi (X A') 2 fnx(X' A')
(13)
with (X' A) = (IT ((A).) (m) b(m))
(14)
Like in 15 we use the linear bounds from CROWN 1B3
Computing these bounds requires
elementwise lower and upper bounds y(11) (N) and g(1) ((N) on the pre-activation values
(x)) ((Á',) x)) X'W) with (n) E RR
For our perturbation set, propose compute these elementwise lower and upper bounds by solving knapsack problems with local constraints via the algorithms discussed Appendix F.T To bound the the pre-activation values (11) of the wihh node, we define the cost matrix C' E | as
CC
m = n if fm+#n Fn A An. =0 if + A An,
Ci,m
The infinite cost for diagonal elements ensures that they are not adversarially perturbed. Afterall, there no benefit to attacking elements that are anyway overwritten by self-loops. The cost matrix has shape x N, because in every row n, there are only N edges that can be perturbed.
To obtain upper bound s
(n)
define the value matrix V E IRI to be
V1.m mmxx (X W. A. 0) max (-XT 0)
if An 0 if An.m = L.
We then solve the knapsack problem, which tells us how much the pre-activation value can change under I, and then add this optimal value to the original, unperturbed pre-activation value 2/
(n)
(N) To obtain a lower bound rh we analogously define the value matrix V E x to be
max
X W. t, 0) if An X m
V1.m max
W
w. 0)
An.m = L.
These linear bounds referred to doubleL in [1
46

---

multiply the optimal value of the knapsack problem with -1 and then add it to the original, unper- turbed pre-activation value 2/ (N)
Nodewise guarantees. The next step to use the constructed linear lower bounds fi.k..... JN.A to lower-bound the value of functions -...,. for each possible number of perturbations admitted need to take the degree normalization into account.
by local budgets p1.-..: PN- Note that
For our new perturbation set, we propose to use Algorithm to perform these precomputations. We set the cost parameters to c+ ca and c-' CA. To prevent perturbations of the diagonal entries that are overwritten with self-loops, set the index set parameters II and to I {(1,)) |A..m 0} (1, and I {[1, An.m [1,, We set the global and local budget parameter of the algorithm to and respectively. Because Algorithm I is defined to solve a maximization and a minimization problem, we define the value matrix V R1xN be
- qm
(n)
if An,m = 0 if An.m
V1
(n)
qm
=
That is, setting An, from O to 1 has a large value if qm is a negative number. Setting An, from to 0 has large value if ((") if large positive number. Algorithm 1 yields dictionary where an (i,j) indicates how much the value of (x, A) changes when optimally inserting and deleting j edges. It further yields a dictionary 3n. where 3n (i,,) contains the optimal set of edges to perturb in row n of the adjacency matrix. The last thing we need do add them the unperturbed values fr, (X, , A) while accounting for the fact that perturbing edges also influences the degree and thus the degree normalization. We propose to do so via Algorithm 4
Algorithm 4 Computation of min i e'eB fa.s from the precomputed worst-case changes without degree normalization stored in dictionary ay.
max_adds adds + Len cc|
for i O.... max adds do max max_ddes- + [pn c+ i) c
for = ..... max dels do
old ald_eegree+ 1 An
new new_ new_degree + old_ degree + i new degrre < max(1, (ne (amn_ddwggre,,,, N)) an (i, + (i, - old degree fr.k X A) an((,)) (i.j)) new wew_eegree
Between and N, due self-loop.
return Okn
Note that we compute the negative value of the lower bound, because all discussed algorithms are designed for maximization problems.
Combining the nodewise guarantees. Now we have, for each node n and every possible number of insertions and deletions the negative of lower bound fn,k, which is stored in a (i. j). The last step is to combine these nodewise guarantees while complying with global budget e. To this end, we can just reuse Algorithm 2 with c+ C and em CA It yields a sequence t of length N, whose rath element the set of the worst indices to perturb in row n the adjacency matrix. further yields a lower bound the negative classification margin -1 (F(X', A'), F(X', A')s) for a specific If after performing the above procedure for all + all classification margins are positive, then the prediction is provably robust.
Enforcing symmetry via dualization. An important aspect of the discussion in [5 is that one may want introduce the additional constraint A' A" when proving robustness for symmetric graphs.
47

---

The authors show that
min JE
Σ fux (X',
I ,') s.t. A' A
N Σ ( A) +TT(AA A)A') 1m
max AERNEN
min (E
with dual variable E R NxN Note that Tr((A" A)A) = A MM (A A) A
The inner optimization problem can be solved exactly via the "nodewise guarantees" and "combining the nodewise guarantees" steps above, after replacing each parameter vector ((()) the linearized models fr.k defined in Eq. (14 with q(T) + 1''AA A'm) (A-A"), A7)
Because the inner optimization problem is solved exactly, dual variable A can be optimized via gradient ascent on Tr((A"- A') (Danskin's theorem).
F.6 Policy iteration for adjacency perturbations
Bojchevski and Günnemann 11 derive robustness certificates for models where the predictions are a linear function of the (personalized) PageRank. Specifically, they consider the following architecture called --PPNP:
= (oftmax(IIH)
- fo(
= (1- - -aD-1A)-
where X the feature matrix of the graph, ff is neural network with parameter 8, H..; the prediction for node and II the personalized PageRank matrix with teleport probability a (i.e. II,, is the personalized PageRank of node v). Further note that IN the identity matrix and is the degree matrix D; = Σ, = Aij of a graph G (V,E) with nodes V and edges E
Their certificates against adjacency perturbations with uniform costs (c) - generalize their certificate to arbitrary costs for edge insertion and deletion. Let the following set denote all admissible perturbed graphs under costs cx for edge insertion and ca for edge deletion:
and we will
2x = (VV, : U.F F E P(F),
1 EE 1 EE 1 + E LE'S Po,
(15)
where E set of fixed edges that cannot be modified, F C V the of fragile edges that can be modified. Here, F+ C F denotes the set of edges that are included in the perturbed graph (analogously F_ S the set of edges that are not included anymore in the perturbed graph). Here, denotes the global budget and Pe the local budget for node v.
We assume fixed graph G, set of fragile edges F, global budget B and local budgets b.. Note that since π- PPNP separates prediction from propagation we can further assume fixed model logits H. Following Bojchevski and Günnemann [1]] we further define the worst-case margin between classes
Yt and under any perturbed graph G E Qr (Problem 1 of Bojchevski and Günnemann III:
m
min (t).e(t) min (T(e))"(HH -H.c) GEOF
(16)
GERF
where e is the unit vector and Te(e;) the personalized PageRank vector of target node under perturbed graph G. We want to show that a specific target node is certifiably robust w.r.t. the logits H and the set Qr. This the case if m (1) = mineyy, mt) > 0. In the following we will derive guarantees for this under local and global adversarial budgets, respectively.
Local constraints only. Bojehevski and Günnemann 11 phrase the problem of Equation 16 as a more general average cost infinite horizon Markov decision process and present a policy iteration algorithm that solves in polynomial time. Following their derivations we also define r - -H.... H.o), where r, denotes the rewards a random walker gets for visiting node v M.
The following adapted policy iteration computes the worst-case graph G E Q, under arbitrary costs:
48

---

Algorithm 5 Policy Iteration with local budgets under arbitrary costs
Require: Graph G = EV,E), reward set of fixed edges ε fragile edges F, local budgets b, and costs C². for edge insertion and CA for edge deletion
1: Initialization: arbitrary Wo S F. A corresponding G
2: while Wi + W
3: Solve (IN aD-1 A) = r for where Aij = 11
A if (1,5) E We
4: kj (1- 2A (x) - for all (i,j) E F
5: for v E V do
6:
m < m [(WJ)F-UP-- myles s.t. E(ojier- Ca + Evuner camy 1
Pu. m,. E {0.1]
7:
Lu t (vv5) E F m, =1
8:
We U.6o
9:
*+k+1
return Wk
Line of the policy iteration requires us to find those fragile edges with the largest score under the local budget Pv. This is an instance of the Knapsack problem, which we discussed earlier. In practice we solve this using dynamic programming, specifically we call Algorithm 2 for row-vector V1, + lej. & oo and P1 + Pu- Finally, note that Bojchevski and Günnemann | show the correctness of the policy iteration for arbitrary sets of admissible perturbed graphs Qu,, thus the correctness of Algorithm folloows from their proof. In particular, the additional costs for insertion and deletion does not change the fact that we can model the problem as a Markov decision process.
Local and global constraints. Lastly, for local and global constraints we can use the same auxiliary graph introduced by Bojchevski and Günnemann [11]. In particular, the additional constraints are only additional enrichments of the Linear Program resulting from the auxiliary graph, yielding quadratically constrained linear program. To account for additional costs, we have replace constraint (4f) of their QCLP with the following constraints that also considers additional costs:
Σ A ((.j) E + c [(i,5) 81318 S (KEE
F.7 Sparsity-aware randomized smoothing for attribute and adjacency perturbations
Bojchevski et al. [14] present robustness certificates for sparse data based on randomized smoothing. Their main idea is to introduce sparsity- aware smoothing distribution that preserves the sparsity of the underlying data distribution. Such sparsity-aware certificates for discrete data are currently state-of-the-ar for certifying robustness of GNNs against structure and attribute perturbations.
Bojchevski et al. [4 derive robustness guarantees only under uniform costs (ct = - = cx
'x 1). Here we make use of our findings (Appendix) F and generalize their certificate to graph edit distances under arbitrary costs for insertion and deletion. Specifically for sparse graphs we model adversarics that perturb nodes by adding ones (flip 0 - 1) to or deleting ones (flip + 0) of the adjacency or feature matrix. Since adversaries can perturb both the features X and edges A of graph G (A, X) we consider the threat model (G) {Ō' 8(G, G) e) with
6(G. G) = Σ Σ
I(A; Aij + 1) C ΣΣ I(A,; = 11)
(17)
* Σ > TI T(X;) Xij +1) x ΣΣ(X, 11)
where is an indicator function and ct C, xx: cx the corresponding costs for addition and deletion.
Sparsity-aware smoothing distribution. Bojchevski et al. [14] propose a family of smoothing distributions that preserves sparsity of the underlying data. Applied to graphs, the distribution of randomly perturbed graphs (X, A) given clean graph (X, A) is defined by the probability mass
49

---

function Q: (0.1) NXD x {0,1)MxM
+ [0, 1] with
Q(X. A) II 9x (.)) II (A())) f
(18)
1.
and elementwise functions 9x:94 94 {0,1} - [0. with
(px) 1-x (px) Xz
if X # XiJ otherwise
(x
(vx) ) (px) X1,
(A(A..) (PA)² -As
(PA) Ag
if A + Aij
(w 111A (Pa) A
otherwise
where parameters PX Px PA.PA [0, 1] specify the probability of randomly inserting or deleting attributes and edges, respectively. Note that by using different probabilities to flip 0 - with probability y= and 1 -> with probability pT the smoothing distribution allows to preserve sparsity of the data especially for pt p.p
Graph edit distance certificates. The certificate of Bojchevski et al. 14 guarantees robustness against the threat model B, a' (G), which bounds the perturbations individually by having separate radii for addition r+ and deletion r- To certify robustness under graph edit distance with arbitrary costs and given budget 6, we have to certify robustness with respect to all balls B " (G) with
+ CA rA
+ Cx TX S.
Finally note that in practice do not have consider all balls since if we certify one radius the classifier also robust for smaller radii [1].. Therefore the number of combinations one has to consider reduces significantly in practice.
50

---

G Local budgets and local robustness
As discussed in Section the domain X may be composed of N distinct elements, i.c. X A for some set A. Similarly, the task may require making M distinct predictions, i.e. the co-domain Y BM for some set B. In certain tasks, like node classification, it is common to enforce local distance constraints on each of the N elements of perturbed input x' and investigate the robustness of some subset prediction elements C [I...., M). ). In the following, we discuss how to generalize our definition of robustness (see Definition 1 enforce such local budget constraints and quantify such local robustness.
For this discussion, recall that model is (G, dia dout; equivariiant-robus if
max max dou (f f(g x')) s.t. d (I, x') Se) S..
r'ex gEG
Local budgets. Local budget constraints can be easily accounted for by replacing the original optimization domain og 1 x E din,n, S e) in the above definition with
{o 1 G E AN din (I, x') I e, Vn choo(Inn x'm) S pn }
with global distance din : :AN - R+, global budget c, local distance dioe A - R4, and local budgets Pl,....PN R.+.
Local robustness. Quantifying the robustness of some subset of prediction indices C (l,..., M} requires function dout BBTTI Fl + TR+, We need be careful about where we introduce the indexing pass the original M-dimeesioonal predictions into dout It is not correct to measure output distance using dout (fz) g [(g r²)r). i.e. is not correct to index before reverting the effect of group action E G. Afterall, group may act differently on BM and BB""), For example, rotating point cloud around its center of mass and then subsampling it is not the same as rotating around the center of mass of the subsampled point cloud, Therefore, dowt( (f(x) g f ee''' ))))) may very large, even if ff is perfectly equivariant and not affected by the small perturbation (x² x). Instead, we need to measure output distance using
dout (f (x)), (g f(g )r)
Combining local budgets and local robustness leads to the following definition:
Definition 3. Consider a ground truth function % - with X = &N and Y BN for some sets A. B. Further consider input distance function dm A, A + R.,, local distance function dioc x A. - 4 set of output indices T C (1,..., M) and an output distance function dout. BI21 x BBT + 14.. Assume that is equivariant with respect to the action of group G. Then, a prediction [())for clean input % (G, din, dout, e, p, 6, 6 -eeuuvaariant--rbuu
max max dout (f(xr), (g- f(g x! (T) 2'EX SEC
Vn (N s'a) Pn: s.t. dia (x. x0) Sc
is less than or equal to
Similar to what we discussed in Section 5 using an equivariant model f means that dout. (f(I),, (g f(g . 2²))=) dout (f(x)), (x))T) and we recover the traditional notion of adversarial robustness with local constraints for the subset predictions T.
51

---

H Definition of robustness for non-compact sets
For our discussion in Section 4 assumed compactness of all optimization domains, that minima and maxima always exist. In particular, we assumed that the set {a' E X dm (x, S E} is compact for all E R2+ and thus contains all its limit points. If this is not the case, the minimum minges din ( x²) may not exist for certain groups G and perturbed inputs x' E X. In this case, the action-induced distance needs to be defined as din (x, (x,x') x²) = inf geG din r').
Furthermore, our discussion on perturbation models in Section 4.1 may no longer hold. We may have {a' dd x²) S c) 2 {g x' g E G, dm, x²) S c}. since the l.h.s. set also contains perturbed inputs x' E X that can be mapped arbitrarily close to dia-ball of radius e, whereas the r.h.s. set only contains perturbed inputs that can mapped into the interior of the ball (via the inverse group element g )) To ensure equality, we also need to include these limit points. This leads us to the following definition:
Definition 4. Assume that ground truth function y X - Y is equivariant with respect to the action
of group G. Further define the set of limit points
== {gg a'
inf (z,(z, h xa) = A g E arg inf pe x'}}.
heG
Then, a prediction f(x) for clean input x E X is (G, dm dout, e, (aouu,,,))equveeeee equuivvvarriintt-oooa
if
(max max down (J()) 2' EX gEG
f(g o x²)) s.l. din (z, x') ) V x' EL) S 8.
One could also constrain x' be in the closure of fa' E X din (x, S c). This would however correspond to a potentially stronger notion of robustness, since the closure may also contain limit points that are not in L. The model may thus need to be robust to larger set of perturbed inputs.
Note that all our discussions in Section
5 also apply to this notion of robustness.
Definition of robustness for non-isometric group actions
For our discussion in Section Vr, X, Vgg E G dg Z; x²) dm x'). If this not the case, one could also try to define an action-ined -etion-induced distance as follows:
we assumed that group @ acts isometrically on input space X, i.e.
(x, min dia (h x. x²),
ghee
ic. try to minimize the distance between clean input x and perturbed input x' by transforming both via group actions. However, evidently have men dia (h z, x²) I mingec dia (I, g x²). We can thus distinguish two cases
Case 1.
Both oction-induces distances are identical for all x, x' E X (which is always the case when acts isometrically). this case, introducing the second group element is redundant.
Case 2. There is pair x, x E X such that ming, din (h x, g x²) < mingeg din din 9 x²). ). In this case, Desideratum 3 from Section 4 would be violated, i.e. the action-induced distance di would not optimally preserve the original distance din-
Nevertheless, one could conceivably define robustness for equivariant tasks with non-isometri group actions as follows:
(max max dout (h-1 f(h x). flg (())z')) s.t. (2, S <) 5
x'eX g.ee
All our discussions in Section 5) also apply to this notion of robustness.
However, this notion would be qualitatively different from Definition Rather than requiring robustness robustness for a specific clean prediction f(r), one would require robustness for the entire set of predictions (f r) f E G}. As such, it is arguably not good of generalization of the classic notion of adversarial robustness. If one opts to use this notion robustness for certification, one should least state it explicitly. Afterall, being explicit about the underlying semantics of tasks and certificates is a main focus of this work.
Note that typically considered group actions (translation, rotation, reflection, permutation, etc.) act isometrically on the typically considered input spaces (e.g. Fuclidean spaces), meaning these considerations should usually not be relevant in practice.
52

---

Relation to transformatiion-seeciie robustness
As discussed in Section works on transformattion-peeciie robustness are concerned with robustness to unnoticeable parametric transformations, such as small rotations or translations. More formally, consider a parametric function d9 X + X with parameter E O. A model is considered robust to cansformation-speete
attacks if maxage dout (fr), (()) I 6 for some small Ó E R+- Usually, dout is defined as the 0-1-loss [ A y/) [56-65]. The underlying assumption that the transformations the do not change the ground truth label of an input.
The key differences our proposed notion of robustness ness does not consider that there are transformations for which predictions explicitly need to change and (2) works on transformation-specifff usually do not consider unstructured perturbations like camera noise which are only constrained by distance function din-
that (1) transformation-speeffee robust-
In the following, demonstrate that transformation-speede as a special case of our proposed notion of robustness or relaxations thereof. We can distinguish three cases, depending the structure of {e 1 E O).
robustness can nevertheless be framed
Case the first case, the family of transformations (th | E } forms a group G with composition as the group operator (1h0 the 1ho wher) and application of the transformation as the group action (thg x = the (x)) In this case, the above definition of cannsfrmattonnspeeiiii robustness be reformulated as maxgec dout (f(x), flg x)) 6. Assuming that our distance function fulfills dia (z, = = x = x', this is equivalent to
s.t. (z (2,x') x') S max max dout (f(z). f() x') < e'ex ge
(19)
We observe that this is a special of our notion of robustness (see Definition D. where the adversary has a budget o 0 (i.e. can only apply group actions) and the task is group invariant.
Case 2. In the second case, the set of transformations is restricted to a subset liIl of G that is not proper group. For example, one may restrict adversary small translations instead of arbitrary translations (see, e.g., (57). In this case, transformation
robustness can be framed as max max dout (f(x), flg z')) S 8 s.t. diu (z, x') S O, z'EX gEll
which is relaxation of Eq. (9) since H C G.
Case 3. In the third case. the family {wis 0 E }} does not have a group structure or the ( is not a proper group action (e.g. due to interpolation artifacts after rotation of an image). In this case, can choose an arbitrary e IR and define an arbitrary dia (2, x') such that {a' dz, x') I E} = (vo(z) 0 E θ). That is, the distance between and x' is smaller than e if z' can be obtained via transformation of æ. With this choice din, transformation-speciine
robustness is equivalent to s.t. di (a, x') S e. max dout f(). S z' x'eX
This is an instance of classic adversarial robustness, which is a special case of our proposed notion of robustness (no equivariance).
Suuh family of transformations is referred to as "resolvable" in ttaasfoomation-speiiiii robustness literature.
53


Reviews:
[{"review_id": "HiNsX6MOuw", "reviewer": "Reviewer_kw3s", "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.", "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. ", "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).\nIs there any :\n- empirical proof for it?\n- theoretical consideration reasons for it?\n\nProbably the answer was somehow blurred inside the text, would love to hear the clear explanation for it.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "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?\nAlthough the task seems very vague, the authors answered it in a very elegant manner by:\n- introducing the new distance $\\hat{d}_{in}$ which should be invariant w.r.t. to the group transformations\n- introducing two properties of this new distance (upper bound as usual distance $d_{in}$ + being the max of such distances)\n- 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.\nBased 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.\nMoreover, 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:\n- multiplicative group of the \"gamma correction\" image transformations\n- Rayleigh distribution to serve as a smoothing distribution\nWould be interesting to know how it fits into the proposed framework.\n\nAdditionally, 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.\n\n\n[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.\n[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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thorough review of our submission and pointing out the interesting connection to smoothing over multiplicative transformation parameters.\n\n## How randomized smoothing over multiplicative parameters fits into the proposed framework\nWe provide an in-depth discussion of transformation-specific robustness through the lens of our novel notion of robustness in the global rebuttal comment above. \n\n**In short:**  \n1.) If transformations have a group structure, and the task is known to be invariant w.r.t. this group, then transformation-specific robustness is equivalent to ($G$, $d_\\mathrm{in}$, $d_\\mathrm{out}, \\epsilon, \\delta)$ robustness with adversarial budget $\\epsilon=0$ -- or a relaxation thereof.  \n2.) Otherwise, it can be thought of as guaranteeing classic adversarial robustness, i.e. $G = \\\\{e\\\\}$,  w.r.t. a distance function $d_\\mathrm{in}(x,x')$ that determines if $x'$ is a transformed version of $x$.\n\n**Concerning randomized smoothing of transformation parameters**:  \nAn interesting connection here is that transformation-specific smoothing can actually be an instance of equivariance-preserving smoothing. The smoothed model may simply inherit equivariances from the transformation: If $\\forall g \\in G, \\forall \\theta, \\forall x : \\psi_\\theta(g \\bullet x) = g \\bullet \\psi_\\theta(x)$, then the smoothed model $\\xi(\\psi_\\beta(x))$ with random parameters $\\beta$ will be equivariant w.r.t. group $G$ -- assuming an appropriate smoothing scheme $\\xi$ (e.g. center smoothing).\n\nConcerning **multiplicative transformations:**  \nThe Gamma transformation is a multiplicative group. In fact, any multiplicatively composable transformation inherits its group structure from the multiplicative group $(R_+,\\cdot)$ if we define the group operator as $\\psi_\\alpha \\bullet \\psi_\\beta = \\psi_{\\alpha \\cdot \\beta}$.\nThus, if our task is invariant w.r.t. to group $(\\psi_\\theta)$, we are in case 1.) above.\n\nIf our task is not specifically invariant w.r.t. $(\\psi_\\theta)$, we are in case 2.). As discussed above, we can use the method from [1] as a form of equivariance-preserving smoothing.\nMultiplicative transformations actually have many practically interesting equivariances. For example, scaling of point clouds is multiplicatively composable and also rotation and permutation equivariant. So we can use the results in [1] together with our work to prove the robustness of models for rotation-invariant point cloud classification to adversarial scaling.\n\nConcerning **Rayleigh smoothing:**  \nThus far, we have not been able to discern whether specifically using Rayleigh parameter noise offers us any additional equivariances that are not achievable with other parameter distributions. But we will try to look further into it.\n\nBased on your feedback, we will expand our discussion of transformation-specific smoothing and specifically [1] in the camera-ready version.\n\n## How interpolation errors fit into the framework\nInterpolation errors are primarily an issue with digital images, because they are the result of rasterizing the continuous image signal and quantizing the color values.\nUsing the terminology from [1], this means that certain transformations are non-composable. Using the terminology from our paper, this means that the transformations are not a group. Since we are focusing on group equivariance, such transformations are not covered by our framework.\n\nPlease note that this is an inherent problem of the image domain and not specifically a limitation of our work. This is also why equivariant models for images are typically derived for continuous image signals (see, e.g., [2, 3]).\nDomains where equivariant models are actually used in practice (graphs, point clouds, molecules ...) do not suffer from this problem. For example, PointNet is perfectly permutation invariant, DimeNet++ is perfectly rotation equivariant and GCNs are perfectly ismorphism equivariant.\n\nBased on your comment, we will include this discussion in Section 6 of the camera ready.\n\n## Why we provide experimental results\nYou are right. Our rigorous derivations show that existing certification methods for equivariant models can be reused for the proposed notion of robustness.\nThe reason we conducted new experiments is that they offer novel insights:  \n1.) Firstly, there is no prior work on proving the robustness of models with continuous equivariances. Our equivariance-preserving randomized smoothing approach can thus be seen as a baseline for future work.  \n2.) Secondly, we derive new graph guarantees with non-uniform cost for insertion and deletion (see Section 5.2). Their experimental evaluation provides more detailed insights into the robustness of graph neural network, which were impossible to obtain with existing certification methods.\n\n## How prior work underestimates the strength of the adversary\nWe discuss this point in the global rebuttal comment. In short: What we meant to say is that prior work uses their method to claim  robustness within a set $B = \\\\{x' \\mid d_\\mathrm{in}(x,x')\\leq \\epsilon\\\\}$. Our work shows that, under a  sound notion of robustness, the same models are actually robust (but not constant) in $\\hat{B} =  \\\\{x' \\mid \\hat{d}\\_\\mathrm{in}(x,x')\\leq \\epsilon\\\\} \\supseteq B$ with action-induced distance $\\hat{d}_\\mathrm{in}$. This certified region may be significantly larger, depending on the distance function and group (see Fig. 3 in the pdf attached to the global comment).\n\nBased on your comment, we will make this more explicit in the camera-ready version of our paper.\n\n---\n\nPlease let us know if you have any additional questions.\n\n---\n\n[1] Nikita Murarev and Aleksandr Petiushko. “Certified robustness via randomized smoothing over multiplicative parameters of input transformations.” IJCAI 2022.  \n[2] Maurice Weiler and Gabriele Cesa. \"General E(2) - Equivariant Steerable CNNs\". NeurIPS 2019.   \n[3] Gabriele Cesa, Leon Lang, and Maurice Weiler \"A Program to Build E(N)-Equivariant Steerable CNNs\". ICLR 2022."}, {"review_id": "o6vh4EjfCe", "reviewer": "Reviewer_y2Vs", "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.", "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?", "limitations": "The authors adequately addressed the limitations.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "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.\n- The paper provides theoretical proofs for the soundness of their proposed notion.\n- The proposed method is applicable to a wide range of tasks, including graphs, point clouds, molecules, and more.\n- 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:\n- 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?\n\n[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.   \n[2] Daniel Zügner and Stephan Günnemann. Adversarial attacks on graph neural networks via meta learning. arXiv preprint arXiv:1902.08412, 2019.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. We are glad to hear that you find our paper sound and innovative.\n\nWe are not quite sure if we interpreted your first question correctly, so please let us know if you would like any additional clarification during the second part of the rebuttal period.\n\n## Flaws of classic robustness exemplified in Figures 1 and 2.\nThe goal of provably robust machine learning is to provide a robustness certificate, i.e. a guarantee that a model's prediction cannot be adversarially attacked (similar to how a high test accuracy can be thought of as certifying good generalization to unseen data -- but provably).\n\nThe shown flaws would cause this certificate to either oversell (Figure 1) or undersell (Figure 2) the actual robustness of the model.\n\nIn Fig. 1, a method operating under the classic notion of robustness might prove that a prediction does not change with up to $\\epsilon=7$ edge perturbations and thus claim it to be very robust. However, this claim could even be made about a model whose prediction is changed by something as simple as representing exactly the same graph via an equivalent adjacency matrix. It thus has little practical value.\n\nIn Fig. 2, a method operating under the classic notion of robustness would deem a model non-robust if it rotates its prediction as the input image rotates. However, this equivariance (learned or enforced) is exactly what is needed to solve the task with high accuracy. Thus, existing certificates would force model developers to either prioritize accuracy or provable robustness -- even though they are not actually add odds with each other.\n\nOur proposed notion of robustness resolves these flaws by accounting for equivariance, so that meaningful robustness certificates can be provided without causing wrong incentives for model developers.\n\n## How the novel notion affects the considerations of attacks (particularly on graphs)\nWe can distinguish two cases.\n\nWhen **the model equivariances and the task equivariances match**, then the model is equivariant-robust if and only if it is classically robust. We can thus reuse any existing method to disprove robustness, i.e. perform an adversarial attack. In particular, this applies to graph neural networks, where one can continue using Nettack or meta learning.\n\nFurthermore, existing attacks are even valid adversarial attacks when **the model and task equivariance do not match**. Recall the optimization problem from Eq. 1:\n$\\max_{x' \\in X} \\max_{g \\in G} d_\\mathrm{out}(f(x), g^{-1} \\circ f(g \\circ x'))$ s.t. $d_\\mathrm{in}(x, x') \\leq \\epsilon$.\nA classic adversarial attack is equivalent to constraining group element $g$ to be the identity element $e$. Thus, any classic adversarial attacks is a valid (but not necessarily optimal) adversarial attack chosen from some more constrained search space.\n\nBased on the feedback of Reviewer 5, we have also conducted some adversarial attacks of our own (see global rebuttal pdf).\n\n## Implications / Potential directions for attacks and defenses\nA direct implication of the discussion above is that one can continue using existing methods -- at least as baseline. There are however interesting directions for developing improved methods that are specifically tailored towards equivariant settings.\n\n**Concerning attacks:**  \nOne interesting direction is developing adversarial attacks for scenarios where the model and task equivariances do not match (e.g. vision transformers). As discussed above, existing attacks are in such cases only a pessimistic bound on the model's actualy vulnerability. The challenge here is finding good ways of  optimizing both the adversarial noise and the group action -- a first attempt could be made via alternating optimization.\n\nAnother interesting direction is using our knowledge about equivariances to reduce the search space for adversarial noise. Finding an attack essentially requires optimization over $\\hat{B} = \\\\{g \\bullet x \\mid g \\in G, x \\in B\\\\}$, where $B$ is a classic perturbation set $B = \\\\{x' \\mid d_\\mathrm{in}(x,x') \\leq \\epsilon\\\\}$, such as a  $\\ell_p$ ball. There may be a smaller set $S \\subset B$ which gets mapped to the same $\\hat{B}$ by group $G$. Consider for example Fig. 3d in the pdf attached to the global comment above. Instead of by a ball, the same set could also be generated by a line that is diagonally translated. Thus, we could find $x'$ via optimization over a one-dimensional space.\n\n**Concerning defenses:**  \nA natural direction is using newly developed attacks for adversarial training. Stronger and more efficient attacks allow the trained model to be more robust without overly impacting the computational cost of the training procedure.\n\nAnother interesting direction direction is actively using a model's equivariances as a defense mechanism. A first example of this is actually discussed in [1]. There, the inputs of a permutation invariant model are randomly shuffled to disrupt gradient-based attacks without changing the model's prediction.\n\n---\n\nBased on your comment and those of other reviewers, we will add a section on attacks and defenses to the camera ready version of our paper (after Section 5). We also conducted some initial experiments (see Reviewer 5).\n\nWe hope that we could address all your questions to your satisfaction.\nPlease let us know if you have any additional comments or questions during the second part of the rebuttal period.\n\n---\n\n[1] Zhang et al. \"The Art of Defense: Letting Networks Fool the Attacker\". IEEE Transactions on Information Forensics and Security."}, {"review_id": "0c6ns6ME4a", "reviewer": "Reviewer_t1fA", "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). ", "questions": "See weaknesses.", "limitations": "Authors acknowledge that their approach is applicable only to equivariant models.", "rating": 4, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "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).\n\nI might be wrong, so I would appreciate input from other reviewers.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review.\n\nIn the following, we would like to highlight the ways in which our results are both surprising and practically useful. We would further like to illustrate this by constrasting them with those of Karras et al. Then, we would like to call attention to the fact that the results of Section 4 are not primarily \"a shared language\", but contributions in themselves. Finally, we would like to emphasize two key technical and useful contributions.\n\n## Surprising practically useful results\nWe would strongly argue that \"It is possible to prove the robustness of neural networks to perturbations bounded by semantically meaningful, extensively studied and computationally hard (even NP-hard) distance functions\" is in itself a very surprising result.\n\nTo go into more detail: Section 4 leaves us with a novel notion of robustness that requires optimization over a set bounded by potentially NP-hard functions. As such, developing a general algorithm that lets us compute such distances efficiently is not really realistic and would have implications beyond machine learning.\n\nThere are two paths one could take:\n* The first one would be the classic certification approach of relaxing the problem. This is essentially the approach taken by recent work on robustness w.r.t. graph optimal transport. For instance, [27] essentially replaces the discrete permutation matrices corresponding to symmetric group $S_N$ with a continuous matrix defining a soft correspondence between nodes in two graphs. The resulting guarantees would be pessimistic bounds on the actual robustness.\n* The second one is the path we take: We identify that, nowadays, equivariant tasks are solved with equivariant models. This allows us to completely eliminate the hard, group-theoretic aspects without any  pessimistic relaxation.\n\nIgnoring the surprise factor: It cannot be denied that this is a practically useful result that resolves an inherent limitation of recent work, which invested  significant  effort into a suboptimal solution to the practically relevant problem of in-/equivariance aware robustness certification.\n\n## Concerning Karras et al.\nThank you for pointing out the interesting connection to the work of Karras et al., which we will also include in the related work section of the paper. This offers a great opportunity to highlight the practical usefulness of our novel \"equivariance-preserving randomized smoothing\" framework.\n\nThe results from Appendix C of Karrass et al. show for different transformations $T$ and all  distributions:  \n$\\mu = \\mu' \\iff T \\mu = T \\mu'$.  \nA discriminator can thus learn (properties of) the original data distribution. This allows the generator to learn the original distribution while benefitting from a less overfitting discriminator enabled by data augmentation.\n\nThe results from Appendix D of our work show for different transformations $T_g$ (corresponding to the push-forward of group actions) and  families of smoothing distributions $(\\mu_x)\\_{x \\in X}$:  \n$\\mu_{g \\bullet x} = \\mu_{g \\bullet x'} \\implies T_g \\mu_x = T_g \\mu_{x'}$.  \nAn in-/equivariant base model thus recovers the original smoothing distributions. This allows the smoothed model to appropriately model the equivariant ground truth while benefitting from  provable robustness enabled by randomized smoothing and Proposition 2.\n\nBecause robustness is a practically useful property, both works make a strikingly similar \"amount\" of practically useful contribution.\n\n## \"Shared language\"\nOur goal in Section 4 is not (primarily) to define shared language so that members of the trustworthy and geometric ML communities can collaborate.\n\nWe first identify deficiencies of directly transplanting common notions of robustness from the image domain onto equivariant domains (Section 1). We then develop a sound notion of adversarial robustness from the perspective of semantics-aware robustness, i.e. defining robustness with knowledge about the ground-truth (Section 4).\n\nWe do not deny that similar equivariance errors appear in other fields (see \"special cases\" in Section 4.3). But the contribution is justifying, in a principled manner, why this notion of robustness should be be worked on by trustworthy machine learning researchers.\n\n## Observations we already take for granted\nWe understand that certain intermediate steps may be less exciting for some readers with a background in geometric machine learning (which are not our primary audience, see above).\n\nHowever, we believe that our findings are crucial for the trustworthy ML community, which thus far fails to appropriately address key aspects of extending their methods to geometric machine learning tasks and models.\n\n## Additional technical contributions\nFinally, we  want to highlight two key technical and practical contributions.\n\nEven though Proposition 2 eliminates some of the hard group-theoretic aspects, we still need to prove that our equivariant model is robust under the classic notion of robustness. Prior to this work, there simply existed no specialized method to do so for many practically relevant models (e.g. those with continuous equivariances).\nWe identify that randomized smoothing is a promising candidate, but may invalidate Proposition 2.\nWe thus develop the novel framework of equivariance-preserving smoothing to enable model-agnostic certification under our notion of robustness.\n\nWe further derive multiple non-probabilistic certification procedures for GNNs under perturbations with non-uniform cost. This was not possible before and offers new insights into the robustness properties of this important class of equivariant models (see Section 5.2 and Appendix E).\n\nWe will update the beginning of Section 5.1 to better emphasize these contributions.\n\n--- \n\nWe hope that we could convince you that our submission is a meaningful contribution to the field of trustworthy machine learning.\n\nPlease let us know if you have any additional questions during the discussion period.\n"}, {"review_id": "CNFxXLavsz", "reviewer": "Reviewer_jBnt", "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. ", "questions": "What is the model settings of the DimeNet++ in Figure 4? What is the performance compared to reported results?", "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.", "rating": 5, "confidence": 1, "soundness": 2, "presentation": 2, "contribution": 2, "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.\n2. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your helpful review, based on which we will add additional information to the camera ready version, as detailed in our discussion below.\n\n## Experiments with different architectures\nFollowing your comment, we performed experiments with additional geometric models for molecule data. Thus far, we added SchNet (one of the best known baselines in the field) and PaiNN (another geometric GNN), as implemented in PyTorch geometric and SchNetPack, respectively.\n\nYou can find these results in the rebuttal pdf attached to the global comment above.\nWe observe that PaiNN and SchNet offer very similar (but not identical) provable robustness w.r.t.  registration distance attacks.\n\nFor the camera ready version we will also include experiments with SphereNet and GemNet.\n\n## DimeNet++ model settings\nAs mentioned in Appendix B.2.2 we use the default parameters specified in the original DimeNet and DimeNet++ papers. The parameters are also included in the file `seml/configs/force_fields/train_dimenet_pp_md17.yaml` provided with the supplementary material.\n\nWe use 4 layers with 128 hidden channels. The triplet embedding size is 64. The basis embedding size is 8. The output embedding size is 256. The number of basis functions is 8 (bilinear), 7 (spherical), 6 (radial). The cutoff radius for graph construction is $5 \\mathring{A}$. The number of residual layers before the skip connection is $1$. The number of residual layers after the skip connection is $2$.\n\nBased on your comment, we will explicitly include these parameters (and the parameters for any additional models we investigate) in Appendix 2 of our submission.\n\n## SchNet and PaiNN model settings\nFor SchNet, we use 128 hidden channels and 128 filters. We set the number of interaction blocks to 6 and use 50 Gaussians. The cutoff distance is $10 \\mathring{A}$, with a maximum number of $32$ neighbors. We use addition as our global readout function.\n\nFor PaiNN, we use 128 embedding dimensions in 3 interaction blocks (without shared interaction or filter weights). We use $20$ Gaussian radial basis functions and a cutoff distance of $5 \\mathring{A}$.\n\nAgain, these parameters (and details on the training procedure) will be added to Appendix 2 of our submission.\n\n## Model performance with and without smoothing\nAs suggested by you, we also performed experiments without randomized smoothing.\nRecall that we had eight sub-datasets \"aspirin\", \"uracil\", \"ethanol\", \"benzene\", \"napthalene\", \"toluene\", \"salicylic acid\", \"malonaldehyde\".\n\nThe average force MAE of DimeNet++ was:\n* 0.344, 0.182, 0.176, 0.158, 0.095, 0.111, 0.227, 0.304 (without smoothing)\n* 0.369, 0.201, 0.181, 0.192, 0.104, 0.122, 0.238, 0.299 (with smoothing)\n\nThe average force MAE of SchNet was:\n* 0.870, 0.322, 0.263, 0.244, 0.250, 0.289, 0.449, 0.445 (without smoothing)\n* 0.931, 0.371, 0.285, 0.260, 0.285, 0.321, 0.496, 0.449  (with smoothing)\n\nThe average force MAE of PaiNN was:\n* 0.450, 0.247, 0.295, 0.168, 0.167, 0.188, 0.312, 0.423 (without smoothing)\n* 0.516, 0.285, 0.372, 0.197, 0.192, 0.229, 0.367, 0.493 (with smoothing)\n\nWe observe that the accuracy of the model decreases as we apply smoothing noise.\nThis is expected and inherent to all randomized smoothing methods. We essentially trade off accuracy for provable robustness. We found $\\sigma=1 \\mathrm{fm}$ to be a sweet spot where the errors are still very similar to the baseline but we can effectively prove that the adversarial change of the model's predictions is small compared to the test error.\n\nCombined with the evaluation of our randomized smoothing certificates above, we can conclude that DimeNet++ and PaiNN offer a better accuracy-robustness tradeoff than SchNet.\n\n## Comparison to the reported results in  DimeNet++/SchNet/PaiNN papers\nDimeNet++ is actually not evaluated on MD17 in the original paper. However, the reported MAEs for DimeNet  (which DimeNet++ is a slightly tweaked, more efficient version of), are\n* 0.499, 0.301, 0.230, 0.187, 0.215, 0.216, 0.374, 0.383\n\nWe observe that the DimeNet++ MAEs are slightly lower, which is consistent with the claims in the DimeNet++ paper.\n\nThe numbers reported for SchNet and PaiNN in the original PaiNN paper are\n* 1.35, 0.56, 0.39, -, 0.58, 0.57, 0.85, 0.66 \n* 0.371, 0.140, 0.230, -, 0.083, 0.102, 0.209, 0.319\n\nWe observe that our numbers for SchNet are slightly better and our numbers for PaiNN are slightly worse than in the PaiNN paper (which may be expected). However, all numbers are in the expected range of $[0.05, 1.0]$.\n\n## More detailed description on how to apply randomized smoothing\nWe agree that, due to the 9 page limit for the initial submission, the description is currently somewhat terse and directed at an audience already familiar with randomized smoothing.\n\nIn essence, all randomized smoothing methods are the same. We just need to choose a smoothing distribution based on the input domain and distance, sample from it and feed the results into our model.\nThen we need to choose a smoothing scheme based on the output domain and distance to compute some simple statistic of the random predictions (e.g. mean or median).\nThis may have been somewhat obscured by our measure-theoretic formalization of the procedure.\n\nBased on your comment, we will make the following changes to the ten-page camera ready version:\n* Provide a less dense explanation of randomized smoothing in Background Section 3\n* Provide pseudocode for the overall randomized smoothing procedure\n* Provide a table specifying when to use which smoothing distribution\n* Provide a table specifying when to use which smoothing scheme\n* Provide pseudocode for the certification procedure of the different smoothing schemes (currently, we only reference the original papers for this)\n\nWe already included the tables in the rebuttal pdf above.\n\n---\nWe hope that we answered all questions to your satisfaction.\nPlease let us know if there is anything else you would like to discuss during the second part of the rebuttal period.\n"}, {"review_id": "nD81a6E27N", "reviewer": "Reviewer_4EgB", "summary": "The paper investigates adversarial robustness for group equivariant tasks. To this end, the authors propose a novel notion of adversarial robustness:\nAn 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.\n\nFurther, 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.\nSeveral instantiations of this approach are showcased on a variety of tasks, including graphs, point clouds, and molecules.\n", "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?\n- 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?\n", "limitations": "Limitations are adequately discussed in the paper.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "- Well written and easy to read\n- The proposed definition for adversarial robustness is a) novel, b) a natural extension of the classical definition, and c) well motivated\n- The section on the different variants of randomized smoothing and their relation to the problem is extensive\n- 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\n- Some further disambiguation from related work might be helpful to the reader (see below)\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review!\n\nPlease note that we cannot update the manuscript during the rebuttal period. We will however make several changes for the camera ready version, some of which are already integrated into the one-page pdf attached to the global comment above.\n\n## Adversarial attacks\nAs you mention, for \"a model equivariant to the underlying group, this [the novel notion of robustness] reduces to classical adversarial robustness\", which is one of our key theoretical results. Please note that this result applies to both provable robustness and adversarial attacks. Attacks on equivariant models for graphs and point clouds under the classic notion of robustness has already been extensively studied [1, 2].\n\nIn fact, **even when the model's equivariances do not match those of the task, any classic adversarial attack is a valid adversarial attack under our notion of robustness**.\n\nRecall the optimization problem from Eq. 1:\n$\\max_{x' \\in X} \\max_{g \\in G} d_\\mathrm{out}(f(x), g^{-1} \\circ f(g \\circ x'))$ s.t. $d_\\mathrm{in}(x, x') \\leq \\epsilon$.\nA classic adversarial attack is equivalent to constraining group element $g$ to be the identity element $e$. Thus, any classic adversarial attacks is a valid adversarial attack chosen from some more constrained search space.\n\nNevertheless, conducting some adversarial attacks of our own is a great opportunity to showcase that our novel notion of robustness is not just some theoretical construct, but a practical property that can be empirically studied. You can find our results for adversarial attacks against PointNet (using a single-step gradient attack) and GCN (using the method from Section 4.4 of [3]) in the pdf attached to the global comment above.\n\nBased on your comment we will\n* explicitly discuss the relation between classic adversarial attacks and our notion of robustness\n* and include the aforementioned experiments (including a full experimental setup) in the camera-ready version of our submission.\n\n## Unknown equivariances\nWe would first like to point out that assuming certain equivariances to be known is not a specific limitation of our work. In fact, the entire field of geometric machine learning is centered around building models implementing specific known equivariances.\n\nHow unknown equivariances fit into our framework is however a very interesting question.\n\nFirstly: The notion of **robustness does not require knowledge of the underlying equivariances** (as long as they have a group structure). It is just a property of the model and task that is either fulfilled or not fulfilled. If one had a guarantee that the model's and the task's equivariances match, one could even derive robustness guarantees using classic methods. However: Without specifying the \"$G$\" part of  $(G, d_\\mathrm{in}, d_\\mathrm{out}, \\epsilon, \\delta)$-equivariance-robustness, it would not really be possible to interpret what these robustness guarantees specifically mean.  Making robustness guarantees for equivariant tasks meaningful and interpretable is, in a sense, the exact goal of our paper.\n\nSecondly: One could even generalize our notion of robustness to **unknown equivariances without a group structure**. We could simply define $\\max_{x' \\in X} \\max_{\\theta \\in \\Theta} d_\\mathrm{out}(f(x), \\psi_{Y,\\theta}^{-1} (f( \\psi_{X,\\theta}(x') )))$, where $\\psi_{X,\\cdot}$ and $\\psi_{Y,\\cdot}$ are (unknown) parametric functions in the input and output space.\nThe same argument as above would apply. But again: Without knowledge of the equivariances, the robustness properties would not really be interpretable.\n\nBased on your comment, we will mention that\n* our definition does not assume the equivariances to be known,\n* but knowing the equivariances is necessary to provide interpretable robustness gurantees  .\n\nin Section 6 of the camera-ready version.\n\n\n## Transformation-specific robustness viewed through our notion of robustness\nThese methods can indeed be seen as a first step towards provable robustness for non-equivariant models applied to equivariant tasks (for the special case of group invariance). Thank you for pointing out this connection.\n\nWe discuss this relation in detail in the global rebuttal comment above. In short:  \n1.) If the transformations have a group structure, and the task is known to be invariant w.r.t. this group, then transformation-specific robustness is equivalent to ($G$, $d_\\mathrm{in}$, $d_\\mathrm{out}, \\epsilon, \\delta)$ robustness with adversarial budget $\\epsilon=0$ -- or a relaxation thereof.  \n2.) Otherwise, it can be thought of as guaranteeing classic adversarial robustness, i.e. $G = \\\\{e\\\\}$,  w.r.t. a distance function $d_\\mathrm{in}(x,x')$ that determines if $x'$ is a transformed version of $x$.\n\nThere are two key **differences to our notion of robustness**.\nFirstly, we do not constrain the adversary to only applying a specific type of (group-structured) transformation. Instead, they can perform arbitrary perturbations within some distance $\\epsilon$ of the original input. Secondly, we do account for how the model's predictions should change under transformations of its inputs (equivariance), whereas transformation-specific robustness always requires the predictions to remain constant (invariance).\n\nBased on your comment, we will include this discussion in the camera ready version of our paper.\n\n---\n\nWe hope that we could answer all your questions to your satisfaction. Please let us know if you have any further questions during the discussion period.\n\n---\n\n\n[1] Naderi et al. \"Adversarial Attacks and Defenses on 3D Point Cloud Classification: A Survey\". arxiv 2023  \n[2] Jin et al. \"Adversarial Attacks and Defenses on Graphs: A Review and Empirical Study\". SIGKDD Explorations 2020  \n[3] Zügner et al. \"Certifiable robustness of graph convolutional networks under structure perturbations\". KDD 2019\n"}, {"review_id": "MZltM1UKxh", "reviewer": "Reviewer_nMMh", "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.", "questions": "Summary of rating:\n\nI 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", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The motivation of studying robustness with equivariance is clear and the problem is well formulated.\n\n- 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.\n\n- 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.\n\n- Each experiment needs more justifications for choosing different smoothing schemes and measure types. \n\n- 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.\n\n\n---\n\n[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.\n\n[2] Chu, Wenda, Linyi Li, and Bo Li. \"Tpc: Transformation-specific smoothing for point cloud models.\" *International Conference on Machine Learning*. PMLR, 2022.\n\n[3] Hu, Hanjiang, et al. \"Robustness Certification of Visual Perception Models via Camera Motion Smoothing.\" *Conference on Robot Learning*. PMLR, 2022.\n\n[4] Hao, Zhongkai, et al. \"Gsmooth: Certified robustness against semantic transformations via generalized randomized smoothing.\" *International Conference on Machine Learning*. PMLR, 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review!\n\n## Baselines and the deficiencies of prior work\nWe discuss this aspect in detail in the global rebuttal comment above.\n\nIn short: We did not mean to say that existing certification procedures had some weakness that needed to be resolved in order to obtain stronger guarantees.\nWhat we meant to express is that **prior work does not adequately interpret the robustness guarantees  computed by their proposed certification procedures**.\n\nPrior work uses methods like convex relaxation to prove that an equivariant model's prediction is (almost) constant within a certified region $B = \\\\{x' \\mid d_\\mathrm{in}(x,x') \\leq \\epsilon\\\\}$. One of our main arguments in Section 5 is that, under our sound notion of robustness,  this implies that the model is robust (but not constant) within  region $\\hat{B} = \\\\{x' \\mid \\hat{d}_\\mathrm{in}(x,x') \\leq \\epsilon\\\\} \\supseteq B$. Here, $\\hat{d}\\_\\mathrm{in}$ is the action-induced distance from Section 4. Depending on $d\\_\\mathrm{in}$ and the equivariance group, the region $\\hat{B}$ may be significantly larger than the region $B$ reported in prior work (see visual example in global comment above). Importantly, this does not depend on a specific certification procedure or baseline.\n\n**Baselines:**  \nOur paper is not primarily about which certification method we use, but about what their computed  guarantees actually mean.\nHowever:\n* For GNNs, we evaluate every existing certificate for insertion/removal of edges/attributes. This corresponds to the $(c^+=1 = c^-)$ lines in Fig. 5, Fig. 6 and Appendix A.3. We further develop novel methods for non-uniform cost.\n* There is no prior work for models with continuous equivariances like DimeNet++. This is why we had to develop equivariance-preserving randomized smoothing in Section 5.1.\n* Similarly, there is no method outside randomized smoothing that can prove robustness for DGCNN under $\\ell_2$ norm threats.\n\nDuring the rebuttal period, we became aware of \"3DVerifier\" [1], which is specifically designed for the PointNet architecture and $\\ell_2$ perturbations. They claim a higher average certified $\\ell_2$ radius of $0.959$ (see Table 2 in [1]). This is actually great for us. Combined with our novel theoretical insights (Proposition 2), we can use this method to provide even stronger guarantees against correspondence distance attacks.\n\nAgain, please note that our focus is not on advocating for a specific certification method, but on providing semantically meaningful guarantees. We propose equivariance-preserving smoothing as a general-purpose method for cases where no specialized ones are available.\n\nWe will update Sections 5.0 and 5.1 of the camera-ready to further clarify this for future readers and use 3DVerifier to showcase stronger guarantees for PointNet.\n\n## Transformation-specific robustness for (non-)resolvable transformations and group equivariance.\nWe discuss this in detail in the global comment.\nIn short:  \n1.) If the transformations have a group structure, and the task is invariant w.r.t. this group, then transformation-specific robustness is equivalent to ($G$, $d_\\mathrm{in}$, $d_\\mathrm{out}, \\epsilon, \\delta)$ robustness with adversarial budget $\\epsilon=0$ -- or a relaxation thereof.  \n2.) Otherwise, it can be thought of as guaranteeing classic adversarial robustness w.r.t. a distance function $d_\\mathrm{in}(x,x')$ that determines whether $x'$ is a transformed version of $x$.\n\n**Concerning (non)-resolvable transformations**\nResolvability is similar to the closedness of groups. A family of functions is resolvable if composing two functions yields another function from the family. A group is closed if combining two group elements yields a new element from the group. The group operator is basically the same as the functions' composition operator. However, groups impose additional constraints on what transformations are to be considered (invertibility, existence of an identity element).\n\nOverall, our paper does indeed deal with resolvable transformations with a group structure (e.g. rotation). Unlike work on transformation-specific robustness, we consider adversaries that are not limited to such transformations, but can perform arbitrary perturbations within some distance $\\epsilon$. In addition, we consider the entire group, whereas transformation-specific robustness usually considers some small range of parameters (e.g. rotation angles). We further account for how the model's predictions should change under specific perturbations (equivariance), whereas transformation-specific robustness assumes them to remain constant (invariance).\n\nWe will include this and all papers you mentioned in Section 2 of the camera-ready.\n\n## Justification for smoothing schemes and measures\nHaving to choose smoothing schemes and measures is inherent to randomized smoothing. In prior work, the scheme is dictated by the co-domain and the output distance. The measure is dictated by the domain and input distance (see Fig. 1 of [2]).\nIn equivariance-preserving smoothing we additionally need to consider their equivariances, which we specify in Section 5.1.\n\nWe created two tables that show which scheme and measure is to be used when (see global rebuttal pdf above). These should facilitate the practical application of equivariance-preserving randomized smoothing and will be included in the camera ready.\n\n## Notation in Section 3\nWe agree that our explanation of a randomized smoothing was a little too terse. We will use the higher page limit in the camera ready to provide an explanation of the involved symbols before explaining randomized smoothing.\n\n---\n\nWe hope that we addressed all your comments to your satisfaction. \nPlease let us know if you have any further questions during the discussion period.\n\n---\n\n[1] Mu et al. \"3DVerifier: Efficient Robustness Verification for 3D Point Cloud Models\". Machine Learning 2022 (Springer)  \n[2] Yang et al. \"Randomized smoothing of all shapes and sizes\". ICML 2020\n"}]

Author rebuttal:
While we have already personally responded to each of the reviewers insightful comments and questions, there are two points that appeared multiple times. 

We would like to use this comment to discuss them in detail. We also attached a pdf with additional figures and tables. We further list prospective changes for the camera ready version at the end of this comment.

The comments asked for further clarification concerning:
* How transformation-specific robustness fits into our proposed notion of robustness.
* In what way prior work underestimates the strength of the adversary.
---
## Transformation-specific robustness
Consider a parametric function $\psi_\theta : X \rightarrow X$ with parameter $\theta \in \Theta$.
A model is robust to transformation-specific attacks if $\max_\mathrm{\theta \in \Theta} d_\mathrm{out}(f(x), f(\psi_\theta(x))) \leq \delta$ for some small $\delta$. We can distinguish two cases:

**Transformations with a group structure:**  
The first case is that the set of functions $\\{\psi_\theta \mid \theta \in \Theta\\}$ forms a group $G$, with function composition $\circ$ being the group operator and group action $\bullet$ being the application of the function (e.g. rotation).

In this case, the above problem can be reformulated as 
$\max_\mathrm{g \in G} d_\mathrm{out}(f(x), f(g \bullet x))$.
This optimization problem is equivalent to $\max_{x' \in X} \max_\mathrm{g \in G} d_\mathrm{out}(f(x), f(g \bullet x'))$ under the constraint $x' = x$.
We can  reformulate this constraint using any formal distance function $d_\mathrm{in}(x,x')$ as $d_\mathrm{in}(x,x') \leq 0$.
We can thus express transformation-specific robustness as
$(\max_{x' \in X} \max_\mathrm{g \in G} d_\mathrm{out}(f(x), f(g \bullet x'))$ s.t. $d_\mathrm{in}(x,x') \leq \epsilon) \leq \delta$ with adversarial budget $\epsilon = 0$.

We observe that this is a special of our notion of robustness, where the adversary has a budget of 0 (i.e. can only apply group actions) and the task is group invariant.
However, in practice, methods for proving transformation-specific robustness are only applied to some subset of $G$ (e.g. a small range of rotation angles). Their guarantees can thus be thought of as a relaxation of this special case.

**Transformations without a group structure:**  
If the parametric function $\psi_\theta$ does not have a group structure, we can define any distance function $d_\mathrm{in}(x,x')$ such that $\\{x' \mid d_\mathrm{in}(x,x') \leq \epsilon\\} =
\\{\psi_\theta(x) \mid \theta \in \Theta\\}$. That is, perturbed inputs are closer than $\epsilon$ iff they are the result of applying the function to $x$ with some choice of parameter. 

With this choice of distance function, transformation-specific robustness is equivalent to
$(\max_{x' \in X}  d_\mathrm{out}(f(x), f(g \bullet x')$ s.t. $d_\mathrm{in}(x,x') \leq \epsilon) \leq \delta$. 
This is an instance of classic adversarial robustness, which is a special case of our notion of robustness (no equivariance).

## How existing works underestimate the strength of the adversary
One of our key results (Proposition 2) is that classic robustness certificates for equivariant models are in fact valid for our novel notion of robustness.
What we meant to say is that, by definition, being robust under our notion of robustness means being robust within a potentially much larger region.

**Importantly, there are no technical deficiencies with the  existing robustness certification methods that exist for specific equivariant model architectures. The problem is with how their provided robustness guarantees have been interpreted thus far.**

Prior work guarantees that a model’s prediction is (almost) constant within certified region $B = \\{x' \mid d_\mathrm{in}(x,x') \leq \epsilon \\}$.
As discussed in Section 4, this means that the model is actually robust (but not necessarily constant) within certified region $\hat{B} = \\{x' \mid \hat{d}_\mathrm{in}(x,x') \leq \epsilon\\}$, where $\hat{d}\_\mathrm{in}$ is the action-induced distance (e.g. the graph edit distance).

All we meant to say is that region $\hat{B}$ may be significantly larger than original region $B$, depending on original input distance $d_\mathrm{in}$, budget $\epsilon$ and equivariance group $G$.

**Visual example (see Fig. 3 in attached pdf):**  
Assume clean input $x = (\sqrt{2} \ \sqrt{2})^T \in R^2$. Futher assume that $d_\mathrm{in}$ is the $l_2$ distance and $\epsilon=1$, i.e. we have a certified circle of radius $1$ around $x$.

If we assume the model and task to be equivariant w.r.t. to rotation group $\mathit{SO}(2)$, then the model is equivariant-robust within an annulus ("donut") around the origin.
It's area is $\pi \cdot (3^2 - 1^2)$, which is significantly larger than the original $\pi \cdot 1^2$

If we additionally assume translation equivariance, then the certified region even has an infinite area,  unlike the original small circle. Furthermore, it contains an $l_2$ ball centered at $x$ with a radius of $3$ (compared to the original $1$).

---

## Changelog
Based on the reviewer's valuable feedback, we have decided to make the following changes to the camera ready version of our paper (note that this year's review process does not allow changes during the rebuttal):
* Expand discussion of transformation-specific smoothing in Section 2 and Appendix (see above)
* Discuss image interpolation errors in Section 6
* Further clarify the  "existing methods underestimate the strength of the adversary" comment (see above)
* Add discussion of attacks/defenses (Reviewer 2/5)
* Discuss GAN training with data augmentation in Section 2 (Reviewer 3)
* Add experiments on SchNet / PaiNN / GemNet / SphereNet (see Reviewer 4 and rebuttal pdf)
* Provide more detailed instructions on applying randomized smoothing, including tables (see Review 6 and rebuttal pdf)
* Add experiments on adversarial attacks (Reviewer 5 and rebuttal pdf)
* Mention that we assume equivariance to be known (Reviewer 5)


Meta-review: The authors study adversarial robustness for group equivariant tasks by proposing a novel notion of adversarial robustness. This problem is important and well motivated. The reviewers highly appreciated the novelty and the elegance of the method proposed. All the reviewers found the work relevant, interesting, with meaningful theoretical and empirical results. Therefore I do recommend acceptance of this paper.
Decision: Accept (poster)