Hierarchical Randomized Smoothing
Authors: Yan Scholten
Jan Schuchardt
Aleksandar Bojchevski
Stephan Günnemann
Venue: NeurIPS 2023 poster (2023)
Keywords: Adversarial Robustness
Robustness Certification
Randomized Smoothing
Graph Neural Networks
TL;DR: Robustness certificates against adversaries that perturb a subset of all entities of an object (e.g. pixels in an image or nodes in a graph).

Abstract: Real-world data is complex and often consists of objects that can be decomposed into multiple entities (e.g. images into pixels, graphs into interconnected nodes). Randomized smoothing is a powerful framework for making models provably robust against small changes to their inputs - by guaranteeing robustness of the majority vote when randomly adding noise before classification. Yet, certifying robustness on such complex data via randomized smoothing is challenging when adversaries do not arbitrarily perturb entire objects (e.g. images) but only a subset of their entities (e.g. pixels). As a solution, we introduce hierarchical randomized smoothing: We partially smooth objects by adding random noise only on a randomly selected subset of their entities. By adding noise in a more targeted manner than existing methods we obtain stronger robustness guarantees while maintaining high accuracy. We initialize hierarchical smoothing using different noising distributions, yielding novel robustness certificates for discrete and continuous domains. We experimentally demonstrate the importance of hierarchical smoothing in image and node classification, where it yields superior robustness-accuracy trade-offs. Overall, hierarchical smoothing is an important contribution towards models that are both - certifiably robust to perturbations and accurate.

Hierarchical Randomized Smoothing
Yan Scholten's .an Schuchardt', Aleksandar Bojchevski & Stephan Günnemann' {y. acchhltnn,, j scchuchardt, 8. guwnneuann de, a. bo coocssk @un -koeln. de Dept. of Computer Science & Munich Data Science Institute, Technical University of Munich University of Cologne, Germany
Abstract
Real-world data is complex and often consists of objects that can be decomposed into multiple entities (e.g. images into pixels, graphs into interconnected nodes). Randomized smoothing is powerful framework for making models provably robust against small changes to their inputs - by guaranteeing robustness of the majority vote when randomly adding noise before classification. Yet, certifying robustness on such complex data via randomized smoothing is challenging when adversaries do not arbitrarily perturb entire objects (e.g. images) but only a subset of their entities (e.g. pixels). As solution, we introduce hierarchical randomized smoothing: We partially smooth objects by adding random noise only on ran- domly selected subset of their entities. By adding noise in more targeted manner than existing methods we obtain stronger robustness guarantees while maintaining high accuracy. We initialize hierarchical smoothing using different noising distri- butions, yielding novel robustness certificates for discrete and continuous domains. We experimentally demonstrate the importance of hierarchical smoothing in image and node classification, where it yields superior robustness accuraacy trade-offs. Overall, hierarchical smoothing is important contribution towards models that are both - certifiably robust to perturbations and accurate."
Introduction
Machine learning models are vulnerable to small input changes. Consequently, their performance typically better during development than the real world where noise, incomplete data and adversaries are present. To address this problem, robustness certificates constitute useful tools that provide provable guarantees for the stability of predictions under worst-case perturbations, enabling us to analyze and guarantee robustness of our classifiers in practice.
Randomized smoothing (Lecuyer et al., 2019; Cohen al., 2019) a powerful and highly flexible framework for making arbitrary classifiers certifiably robust by averaging out small discontinuities in the underlying model. This achieved by guaranteeing robustness of the majority vote when randomly adding noise to model's input before classification. This typically yields robustness- accuracy trade-off more noise increases certifiable robustness but also reduces clean accuracy.
Recent adversarial attacks against image classifiers (Su et al., 2019; Croce and Hein, 2019; Modas al., 2019) and graph neural networks (Ma et al., 2020) further motivate the need for more flexible robustness certificates against threat models where adversaries are bounded by both: the number of perturbed entities and perturbation strength. For example in social networks, adversaries typically can- not control entire graphs, but the perturbation of the controlled nodes may be (imperceptibly) strong,
When adversaries perturb only subset of all entities, existing smoothing- based approaches sacrifice robustness over accuracy (or vice versa): They either add noise to entire objects (e.g. images/graphs) ablate entire entities (e.g. pixels/nodes) even if only small subset is perturbed and requires noising.
Project page: https://wwer cit. tum. wtt..ttddta///iitrreeeeeeeeeeeee htt//t//l/iirrrcccccaalll-- smootchin
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Entity with two binary features
Selected entity with added noise
Perturbed entity
Clean object
Majority vote over randomly smoothed and then classified inputs
Perturbed object
Figure 1:
Hierarchical randomized smoothing: We first select subset of all entities and then add noise to the selected entities only. We achieve stronger robustness guarantees while still maintaining high accuracy especially when adversaries can only perturb subset of all entities. For example in social networks, adversaries typically control only subset of all nodes in the entire graph.
The absence of appropriate tools for decomposable data prevents us from effectively analyzing the robustness of models such as image classifiers or graph neural networks -raooksnrriiingg the research question: How can we provably guarantee robustness under adversaries that perturb only a subset of all entities? We propose hierarchical randomized smoothing: By only adding noise on a randomly selected subset of all entities we achieve stronger robustness guarantees while maintaining high accuracy (Figure 1).
Our hierarchical smoothing framework is highly flexible and can integrate the whole suite of smooth- ing distributions for adding random noise to the input, provided that the corresponding certificates exist. Notably, our certificates apply to wide range of models, domains and tasks and are at least as efficient as the certificates for the underlying smoothing distribution.
We instantiate hierarchical smoothing with well-established smoothing distributions (Cohen et al., 2019; Bojchevski al., 2020; Levine and Feizi, 2020b; Scholten et al., 2022). yielding novel robustness certificates for discrete and continuous domains. Experimentally, hierarchical smoothing significantly expands the Pareto-front when optimizing for accuracy and robustness, revealing novel insights into the reliability of image classifiers and graph neural networks (GNNs).
In short, main contributions
We propose novel framework for strong robustness certificates for complex data where ob- jects (e.g. images or graphs) can be decomposed into multiple entities (e.g. pixels or nodes). We instantiate our framework with well-established smoothing distributions, yielding novel robustness certificates for discrete and continuous domains.
We demonstrate the importance of hierarchical smoothing in image and node classification, where significantly expands the Pareto-front with respect to robustness and accuracy.
Related work
Despite numerous research efforts, the vulnerability of machine learning models against adversarial examples remains an open research problem (Hendrycks et al., 2021). Various tools emerged to address adversarial robustness: Adversarial attacks and defenses allow to evaluate and improve robustness empirically (Szegedy al., 2014; Goodfellow al., 2015; Carlini et al., 2019; Croce and Hein, 2019). While attacks provide an upper bound on the adversarial robustness of model, robustness certificates provide a provable lower bound. The development of strong certificates challenging and constitutes a research field with many open questions (Li et al., 2020).
Robustness certification via randomized smoothing. Randomized smoothing (Lecuyer al., 2019; Cohen et al., 2019) represents a framework for making arbitrary classifiers certifiably robust while scaling to deeper architectures. There are two main approaches discussed in the literature: Additive noise certificates add random noise to continuous (Cohen et al., 2019) or discrete (Lee et al., 2019) input data. Ablation certificates "mask" out parts of the input to hide the potentially perturbed information (Levine and Feizi, 2020b). Since the input is masked, ablation certificates can be applied to both continuous and discrete data. We are the first to combine and generalize additive noise and ablation certificates into novel hierarchical framework: We first select entities to ablate, but instead of ablating we add noise to them. By only partially adding noise to the input our framework is more flexible and allows us to better control the robustness- accurayy trade-off under our threat model.

---

Further research directions and orthogonal to ours include derandomized (deterministic) smoothing (Levine and Feizi, 2020a, 2021; Horváth et al., 2022b; Scholten et al., 2022), input-dependent smoothing (Súkeník et al., 2022), and gray-box certificates (Mohapatra et al., 2020; Levine et al., 2020; Schuchardt and Günnemann, 2022; Scholten et al., 2022: Schuchardt et al., 2023a).
Kobustness-accuree trade-off. The robustness-accuracy trade-off has been extensively discussed in the literature (Tsipras et al., 2019; Raghunathan et al., 2019; Zhang al., 2019; Yang et al., 2020b; Xie et al., 2020), including works for graph data (Gosch et al., 2023b). In randomized smoothing the parameters of the smoothing distribution allow to trade robustness against accuracy (Cohen et al., 2019; Mohapatra et al., 2020; Wu et al., 2021) 1) where more noise means higher robustness but lower accuracy. Our framework combines two smoothing distributions while introducing parameters for both, which allows us to better control the robustness-accuran we can control both- the number of entities to smooth and the magnitude of the noise. Further advances in the trade-off in randomized smoothing include the work of Levine and Feizi (2020a) against patch-attacks, Schuchardt et (2021, 2023b) for collective robustness certification, and Scholten et al. (2022) for graph neural networks. Other techniques include consistency regularization (Jeong and Shin, 2020), denoised smoothing (Salman et al., 2020) and ensemble techniques (Müller et al., 2021; Horváth et al., 2022a,c). Notably, our method ís orthogonal to such enhancements since we derive certificates for a novel. flexible smoothing distribution to better control such trade-offs.
trade-off under our threat model since
Robustness certificates for GNNs. Research on GNN certification is still at an early stage (Gün- nemann, 2022), most works focus on heuristic defenses rather than provable robustness guarantees. But heuristics cannot guarantee robustness and may be broken by stronger attacks in the future (Mujkanovic et al., 2022). Most certificates are limited to specific architectures (Züggnr and Gün- nemann, 2020; Jin et al., 2020; Bojchevski and Günnemann, 2019; Züggerr and Günnemann, 2019). Randomized smoothing is a more flexible framework for certifying arbitrary models while only accessing their forward pass. We compare method to additive noise certificates for sparse data by Bojchevski et al. (2020), and to ablation certificates by Scholten et al. (2022) that ablate all node features to derive certificates against strong adversaries that control entire nodes. While we implement certificates against node-attribute perturbations, our framework can in principle integrate smoothing based certificates against graph-structure perturbations well.
3 Preliminaries and background
Our research is focused on data where objects can be decomposed into entities. W.l.o.g. we represent such objects as matrices where rows represent entities. We assume a classification task on a discrete or continuous (N x -ddmeenniol space N (e.g. X f0. 1] or X' = R). We propose certificates for classifiers f N + 3 that assign matrix X E X a label E y = {l,.... C}.² We model evasion settings, i.e. adversaries perturb the input at inference. We seek to verify the robustness f(X) f(x) for perturbed X from threat model of admissible perturbations:
D.e (X) A E X NND
Σ 1=1
[xx
+
x1 S r, ||vec(X 81)1 S
where 1 denotes an indicator function, |I Ilp a ly vectoor norm and vec(.) the matrix vectorization. For example, vec(-))l is the Frobenius norm. Intuitively, we model adversaries that control up to rows in the matrix, and whose perturbations are bounded by e under fixed Ey-norm.
3.1 Randomized smoothing framework
Our certificates build on the randomized smoothing framework (Lecuyer et al., 2019; Li et al., 2019: Cohen et al., 2019). Instead of certifying a base classifier f. one constructs smoothed classifier that corresponds to the majority vote prediction of ʃ under a randomized smoothing of the input. We define the smoothed classifier g X N + y for smoothing distribution μx
(XX)
argmax PX. yEY
Px,y
Pr. W~jx
[f(W) = y]
where px.y is the probability of predicting class for input X under the smoothing distribution μa- Let y² _ (X) further denote the majority vote of g, i.e. the most likely prediction for the clean X.
Multi-output classifiers can be treated multiple independent single-output classifiers.
3

---

To derive robustness certificates for the smoothed classifier we have to show that ("= for clean matrix X and any perturbed matrix X E 1y (X). This is the case if the probability to classify any perturbed matrix X as y² still larger than for all other classes, that is if "x,,," > 0.5. However, randomized smoothing is designed to be flexible and does not assume anything about the underlying base classifier, i.e. all we know about f is the probability Px,v for the clean matrix X. We therefore derive a lower bound a S Px,y under a worst-case assumption: We consider the least robust classifier among all classifiers with the same probability px.y of classifying X as y:
min Pr (M( = v) s.t. Pr [h( y] Px,y BER W
Px.2
W~px
where H A (h: X 7 } is the set of possible classifiers with f E H. To ensure that the smoothed classifier robust to the entire treat model we have to guarantee min XEB(X) > 0.5. One also derive tighter multi-class certificates, for which we refer Appendix D for conciseness.
Probabilistic certificates. Since computing Px.y exactly is challenging in practice, one estimates using Monte-Carie samples from μxx and bounds px,y with confidence intervals (Cohen et al., 2019). The final certificates are probabilistic and hold with an (arbitrarily high) confidence level of a.
3.2 Neyman-Pearson Lemma: The foundation of randomized smoothing certificates
So far we introduced the idea of robustness certification using randomized smoothing, but to compute certificates one still has to solve Equation 1. To this end, Cohen et al. (2019) show that the minimum of Equation can be derived using the Neyman-Pearge Peatasn ("NP") Lemma (Neyman and Pearson, 1933). Intuitively, the least robust model classifies those W y for which the probability of sampling W around the clean X is high, but low around the perturbed X:
Lemma 1 (Neyman- Pearssn lower bound). Given X, X XNDD distributions μ.x, Mxx, class label y E Y, probability px.y and the set S, å (W& E XNXD =x (W) S k -xpx (W)). we have Pr [W E Sx) with K E R_ s.t.
Px,
Pr I E Sp] = PX
W-ux
Proof. See (Neyman and Pearson, 1933) and (Cohen et al., 2019).
3.3 Existing smoothing distributions for discrete and continuous data
Our hierarchical smoothing framework builds upon certificates for smoothing distributions that apply noise independently per dimension (Lecuyer et al., 2019; Cohen et al., 2019; Lee et al., 2019). Despite being proposed for vector data æ E X² these certificates have been generalized to matrix data by applying noise independently on all matrix entries (Cohen et al., 2019; Bojchevski et al., 2020; Chu et al., 2022; Schuchardt and Günnemann, 2022). Thus, given matrix data we define the density μx (W)+ A I I[ (Wi)) given the density of an existing smoothing distribution μ..
Gaussian randomized smoothing. For continuous data X' IR Cohen et al. (2019) derive the first tight certificate for the f2-threat model. Given an isotropic Gaussian smoothing distribution Ml (w)) N NN(urla æ. I). Cohen et al. (2019) show that the optimal value of Equation given by
Pa.y + Φ- (px (Px,y)
[18112 where & denotes the CDF of the normal distribution and 5 - a.
Randomized smoothing for discrete data. Lee et al. (2019) derive tight certificates for the to threat model. Certificates for discrete domains in general combinatorial problems and computationally challenging. To overcome this, Lee et al. (2019) use the NP-Lemma for discrete random variables (Tocher, 1950) and show that the minimum in Equation 1 can be computed with linear program (LP): Lemma (Discrete Neyman- Paaaa-n lower bound). Partition the input space X into disjoint re- gions Ri...., Ri of constant likelihood ratio a (w) u/)/ua (m))
E ( for all w E RR Define F. Prwwpa (w E R.) and r. PIww-pa (w E R.). Then Equation I is equivalent the linear program pa.y minne(o,11 h2 s.l. h"r Pa.y where h represents the worst-cuse classifier.
Proof in (Tocher, 1950). The LP can solved efficiently using a greedy algorithm that consumes regions with larger likelihood ratio first (Lee et al., 2019). If the number of regions is small and r;, P; can be computed efficiently, robustness certificates for discrete data become computationally feasible.
We write 2ZZ) when referring to the density of the distribution μ.

---

1. 7. Ber(p)
2. 2 W pX
T. ~ Ber(p)
2. Z-
X|0
(0,01)
X
2 E 2 NXLD
(0,11))
ZE2(C+1x0X
(a) For graphs we extend the feature matrix by an additional column that indicates which nodes in the graph to add noise to.
(b) For images add an additional channel indicating the pixels to smooth.
Figure 2: We derive flexible and efficient robustness certificates for hierarchical randomized smooth- ing by certifying classifiers on a higher-dimensional space where the indicator t is added to the data.
4 Hierarchical smoothing distribution
We aim to guarantee robustness against adversaries that perturb a subset of rows of given matrix X. To achieve this we introduce hierarchical randomized smoothing: We partially smooth matrices by adding random noise on randomly selected subset of their rows only. By adding noise in a more targeted manner than existing methods we will obtain stronger robustness while maintaining high accuracy. We describe sampling from the hierarchical (mixture) distribution V x as follows:
First, we sample an indicator vector T E {0, 1}.\ from an upper-level smoothing distribution <(T) that indicates which rows to smooth. Specifically, we draw each element of independently from the same Bernoulli distribution Second, we sample matrix W by using lower-level smoothing distribution μ (depending on domain and threat model) to add noise on the elements of the selected rows only. We define the overall density of this hierarchical smoothing distribution as x/x (W, px (W (T)(T) with:
~ Ber(p). where denotes the probability for smoothing rows.
N
M2: (W;) 8iww; - -x;)
if T
x () & II Fx. (walTz)
for Mz. (ee(w//)) A
if = 0
where N is the number of rows and 8 the Dirac delta. In the case of a discrete lower-level smoothing distribution, V x is probability mass function and 5 denotes the Kronecker delta d
5 Provable robustness certificates for hierarchical randomized smoothing
We develop certificates by deriving condition that guarantees (XX g x(X) for clean X and any perturbed X B (X). Certifying robustness under hierarchical smoothing is challenging, especially if we want to make use of certificates for the lower-level smoothing distribution μ without deriving the entire certificate from scratch. Moreover, Lemma domains where certification involves combinatorial problems. We are interested in certificates that are (1) flexible enough make use of existing smoothing based certificates, and (2) efficient to compute.
be intractable in discrete
Our main idea to achieve both - flexible and efficient certification under hierarchical smoothing - is to embed the data into a higher-dimensional space W 2 NN((+1) by appending the indicator т as an additional column: A W ("I' denotes concatenation, see Figure 2). We construct new base classifier that operates on this higher-dimensional space, e.g. by ignoring and applying the original base classifier to W. In our experiments we also train the classifiers directly on the extended data.
Certifying the smoothed classifier on this higher-dimensione appending the data the supports of both distributions V and v x differ, and they intersect only for those Z for which all perturbed rows are selected by 7 (see Figure 3). This allows the upper-level certificate to separate clean from perturbed rows and delegate robustness guarantees for perturbed rows to an existing certificate for the lower-level We further elaborate on why this concatenation is necessary in Appendix H. In the following we show robustness certification under this hierarchical smoothing mainly involves (1) transforming the observed label probability px.y- (2) computing an existing certificate for the transformed px.y- and (3) transforming the resulting lower bound Px..' We provide pseudo-code for the entire certification in Appendix C.
space simplifies the certification: By
5

---

NN(+D11
Ra
S A
(2)
(W2))
[
0x
0
Prz 12 Rs] A
R1
R2
R3
Piz x 12 R2] A
Piz x 12 R2] =
Figure 3: Overview of the disjoint regions and probabilities to sample Z of each region. The absence of arrows into specific regions indicates a probability of zero. Only Z in region R₂ can be sampled from both distributions V x and V x. The likelihood ratios visualize the proof of Theorem 1.
5.1 Point-wise robustness certificates for hierarchical randomized smoothing
Before providing certificates against the entire threat model we first derive point-wise certificates,
Lee we consider an arbitrary but fixed X e,,, (X) and show robustness g( ))= = g=(X)) by deriving
.v" The smoothed classifier y is certifiably robust w.r.t. X if Px,'' > 0.5. We derive a lower bound by using the discrete NP-Lemma on the upper-level ø. which allows us to delegate robustness guarantees to the lower-level μ the perturbed rows only.
a lower bound Px.y PP
Let C {i:
# } denote the rows in which X and X differ. To apply the discrete NP-Lemma we have to partition the space Z NNx(D+1) into disjoint regions (Lemma 2). The upper-level distribution allows us define the following four regions (Figure 3): In region R2 all perturbed rows are selected (ViEC:T,=]] = 1). In regions R₁ and R3 at least one perturbed row is not selected when sampling from Vx and V x. respectively. Region Rg contains Z that cannot be sampled from either distribution.
Example for matrices. Consider the following example for matrix data to see the existence of four different regions. Define X (z) [22| (2g])))) and X (x |
)2g)) (second row in X is perturbed). Now consider smoothed row with w j 222 and w o 22 that we can sample from both lower-level distributions Mang
(w) > 0 and Mag (w) > 0. Then we can define four examples, one for each region:
Zo Ro
Z X JOER,
Z
Z;= x-00 R
T
Σ
( w
0
I1
0
111
w
22
E3
0
0
0
F3
xx(Z)) (Zo)= (Zo)=0 4x (Z ( (Z1)=0 Vx(Z2)>0, (Zz)30 #x (Z()))=0,1 (Zs)30
Note that can sample the row w by adding noise to the rows 22 or ã. only if the upper-level smoothing distribution & first selects the perturbed row (T2 = 1). In general, we can only sample the same matrix Z from both distributions V x and V x if the upper-level smoothing distribution first selects all perturbed rows E C. We group all those Z in the region R2.
Partitioning into regions. By appending the indicator to the data we obtain four disjoint regions.
To formally characterize these regions, we define the reachable set as A é A U A₂ S 2 (D+++
with A1 ZZ Vi: (T; 0) + (z, = 20)0)), ) and A, _ [ Vi : (T, = 0) + (z: = z; [0)}. where x; 00 denotes concatenation. Intuitively, A only contains matrices that can be sampled from V.
Now we can define the regions and derive the required probabilities to sample Z of each region:
Proposition 1. The regions Ro; R1, R2 and R2 are disjoint and partition the space 2 xD+1),
R, A z (x(++1)) \
R1
Z E A 3i E C T; 0, 2, (0
R2 A [Z E A ViEC
Rg
IZ
3i E C T. = 0, = (0)
Proposition 2. Given x and x. the regions of Proposition I and A & 1 c we have
Pr IZ E R1 A
Pr Z
E R2
= 1
Pr ZZ
R3] =
Z~ x
z~ x
Z ス~ル V
Pr Z R1 =0 z z~
Pr Z R2 -
Pr Z Ra A
2~4
x
2~
Proofs in Appendix C. Intuitively, 1 A = ulll is the probability that all perturbed rows i E C are selected (T; = 1), and A that least one row E C is not selected by d. Lastly, the probability to sample Z E Ro is just O. We visualize Proposition and Proposition 2 in Figure 3.

---

Hierarchical smoothing certificates. Having derived a partitioning of Z 2Nx(D+) as above, we can apply the NP-Lemma for discrete random variables (Lemma 2) on the upper-level distribution Φ. Notably, we show that the problem of certification under hierarchical smoothing can be reduced to proving robustness for the lower-level distribution js on the adversarially perturbed rows oonly:
Theorem 1 (Neyman-Pearson Pearson lower bound for hierarchical smoothing). Given fixed X, X E XN let μx denote a smoothing distribution that operates independently on matrix elements, and V x the induced hierarchical distribution over 2N NNx(D+1), Given label y E y and the probability px. to
classify X as under V. Define Sx. A { (W& E Xle1ID 18x (W) S K Mxxe (xxeex))))))) We have:
Px.y - A
Pr [W E - (1- with IR+ S.t.
Pr W W-pxe
[W S.]
Wouxee
1
where Xe and Xc denote those rows x, of X and is of X with i i C, that is x; + T..
Proof sketch (Full proof in Appendix C). In the worst-case all matrices in R₁ are correctly classified.
Note that this is the worst case since we camnot obtain any matrix of region R1 by sampling from the distribution V x Therefore the worst-case classifier first uses the budget px on region R₁ and we can subtract the probability Prz x I E R1] A from the label probability Px,y'
Since we never sample matrices of region R3 from the distribution x the remaining correctly classified matrices must be in region R2, which one reaches with probability 1 - A from both distributions V x and V. x. In region R2, however, we can simplify the problem to computing the certificate for μ on the perturbed rows to distribute the remaining probability. Since one never samples matrices of region Ro we do not have to consider it. The remaining statement follows from the (Neyman and Pearson, 1933; Tocher, 1950).
Jeyman-Pearson-LLene
Note that we also derive the counterpart for discrete lower-level μ in Appendix F.
Implications. Notably, Theorem implies that we can delegate robustness guarantees to the lower- level smoothing distribution μs, compute the optimal value of Equation under given the transformed probability (Px.y / - A) and multiply the result with (1 - A). This way we obtain the optimal value of Equation 1 under the hierarchical smoothing distribution Yi on the extended matrix space and thus robustness guarantees for hierarchical smoothing. This means our certificates are highly flexible and can integrate the whole suite of existing smoothing distributions with independent noise per dimension (Lecuyer et al., 2019; Cohen et al., 2019; Lee et al., 2019; Yang et al., 2020a). This is contrast to all existing approaches where one has to come up with novel smoothing distributions and derive certificates from scratch once new threat models are introduced.
Special cases. We discuss two special cases of the probability p for smoothing rows: probability to select rows for smoothing is p = 1 (intuitively, we always smooth the entire matrix), then we have A= - ple1 = 0 for any number of perturbed rows |C] and with Theorem I we get Px,,( (v) = Px., (n). That is in this special case we obtain the original certificate for the lower-level smoothing distribution μ. Note that in this case the certificate ignores r. Second, if the probability to select rows is p = 0 (intuitivelyy we never sample smoothed matrices), we have 1 - plc: 1 for any [C] 2 1, and with Theorem 1 we get Px.. 0, that is we do not obtain any certificates.
First, if the
5.2 Regional robustness certificates for hierarchical randomized smoothing
So far we can only guarantee that the prediction is robust for a specific perturbed input X E B% (X). To ensure that the smoothed classifier is robust to the entire treat model By (X) we have to guarantee min XEB,, (x) Px," .r- 0.5. In the following we show that it is sufficient to compute Theorem 1 for A = 1-1p p" with the largest radius r. In fact, the final certificate is independent of which rows are perturbed, as long the two matrices differ exactly rows the certificate is the same.
Proposition 3. Given clean X E N Consider the set O (X) of inputs at a fixed distance r (i.e. [C] = for all X (x)). Then we have minxeB, (X) Px., min (x),,. PX..'
Proof. The probability 1- A =- is monotonously decreasing in the number of perturbed rows |C]. Thus the lower bound px,, is also monotonously decreasing in |C| (see Theorem 1). It follows for
fixed e that P Px,g is minimal at [C] = r. i.c. the largest possible radius under our threat model (x).
7

---

Initializing hierarchical randomized smoothing
In the previous section derive robustness certificates for hierarchical randomized smoothing for any lower-level smoothing distribution f by deriving a general lower bound on the probability Px,, in Theorem 1. In this section we instantiate our hierarchical smoothing framework with specific lower-level smoothing distributions for discrete and continuous data.
6.1 Hierarchical randomized smoothing using Gaussian isotropic smoothing
Concerning continuous data X' IR, consider the threat model B (X) for p 2. We initialize the lower-level smoothing distribution of hierarchical smoothing with the Gaussian distribution (Cohen et al., 2019) (as introduced in Section 3), since specifically designed and tight for the well- studied f2-norm threat model. For our purposes we apply the Gaussian noise independently on the matrix entries. the following we present the binary-class certificates for hierarchical randomized smoothing induced by isotropic Gaussian smoothing:
Given continuous X' R. consider the threat model B (X) for fixed X E N Initialize the hierarchical smoothing distribution using the isotropic Gaussian distribution u (W) & II""", [ww, x o² that applies noise independently on each matrix element. Let y" y denote the majority class and px,y the probability to classify X as y" under V. Then the smoothed classifier g certifiably robust g( x g( ) any X (X) if
Corollary 1.
e<o (0-1
)
1
PX 1-A
---1
2(1 - A) where - denotes the inverse CDF of the normal distribution and A A p².
Proof in Appendix E. We also derive the corresponding multi-class certificates in Appendix E.
6.2 Hierarchical randomized smoothing using sparse smoothing
To demonstrate our certificates in discrete domains we consider binary data X = {0, 1} and model adversaries that delete тa ones (flip 1 + 0) and add ra ones (flip 0 + 1), that we consider the ball B3 B (X) (see Appendix B for formal introduction). We initialize the lower-level smoothing distribution of hierarchical smoothing with the sparse smoothing distribution proposed by Bojchevski al. (2020): p(u(=);; A 2x)) p 1-=", introducing two different noise probabilities flip 0 1 with probability p+ and 1 + 0 with probability p-. The main idea is that the different flipping probabilities allow to preserve sparsity of the underlying data, making this approach particularly useful for graph-structured data. Note that we can consider the discrete certificate of Lee et al. (2019) as a special case (Bojchevski et al., 2020). We derive the corresponding certificates in Appendix F.
6.3 Hierarchical randomized smoothing using ablation smoothing
Lastly, randomized ablation (Levine and Feizi, 2020b) is a smoothing distribution where the input is not randomly smoothed but masked, e.g. by replacing the input with special ablation token t & X that does not exist in the original space. There are different variations of ablation and we carefully discuss such differences in Appendix G. By choosing smoothing distribution Jr that ablates all selected rows we can prove the following connection between hierarchical and ablation smoothing:
Corollary 2. Initialize the hierarchical smoothing distribution Y with the ablation smoothing distribution μz (t) = for ablation token t & X² and pæ (w) = for w E x otherwise (i.e. we always ablate selected rows). Define A & -ppp. Then the smoothed classifier is certifiably robust g(X) = (())),))))))))))) for any x E B3, (X) if - A 0.5.
Proof in Appendix G. Interestingly, Corollary and Corollary 2 show that hierarchical smoothing is generalization of additive noise and ablation certificates. The additional column indicates which rows will be ablated, but instead of ablating we only add noise to them. In contrast to ablation smoothing (which just checks if px.y - > 0.5) we further "utilize" the budget px the lower-level certificate. Notably, we are the first to generalize beyond ablation and additive noise certificates, and our certificates are in fact orthogonal to all existing robustness certificates that are based on randomized smoothing.
by plugging into
8

---

Clean Accuracy (%)
90
81
Clean Accuracy
85
80
Hierarchical smoothing
80
Hierarchical smoothing
Spurse smoothing (Bojehevski et al., 2020)
Gaussian smoothing (Cohen et al., 2019)
Interception smoothing (Scholten et al.,, 2022)
Ablation smoothing (Levine and 2020b)
79
75
0
10
20
30
40
50
60
70
58
60
62
64 66
68
70
72
Certified Accuracy
(%)
Certified Accuracy (%)
Figure 4: Hierarchical smoothing significantly expands the Pareto-front w.r.t. robustness and accuracy in node and image classification. Left: Discrete hierarchical smoothing for node classification, smoothed GAT on Cora-MI. (r (r=1h r. = 40, 0). Right: Continuous hierarchical smoothing for image classification, smoothed ResNet50 on CIFARIO (r = 3, e 0.35). Non-smoothed GAT achieves 80%=2% clean accuracy Cora-ML, ResNet50 94% CIFARIO. Large circles and stars are dominating points for each certificate. Dashed lines connect dominating points across methods.
7 Experimental evaluation
In this section we highlight the importance of hierarchical smoothing in image and node classification, instantiating our framework with two well-established smoothing distributions for continuous (Cohen al., 2019) and discrete data (Bojchevski et al., 2020). In the following we present experiments sup- porting our main findings. We refer to Appendix A for more experimental results and to Appendix B for the full experimental setup and instructions reproduce our results.
Threat models. For images we model adversaries that perturb at most r pixels of an image, where the perturbation over all channels is bounded by under the f--norm. For graphs model adversaries that perturb binary features of at most nodes by inserting at most Ta and deleting at most ra ones.
Datasets and models. For image classification train ResNet50 (He et al., 2016) on CIFAR10 (Krizhevsky et al., 2009) consisting of images with three channels of size 32x32 categorized into 10 classes. We certify the models
random but fixed subset of 1,000 test images. For node classification we train graph attention networks (GAT's) (Velickovic et al., 2018) with two layers on Cora-ML (McCallum et al., 2000; Bojehevski and Günnemann, 2018) consisting of 2,810 nodes with 2,879 binary features, 7,981 edges and 7 classes. We train and certify GNNs in an inductive learning setting (Scholten et al., 2022). We defer results for more models and datasets Appendix A.
Experimental setup. During training, we sample one smoothed matrix each epoch to train our models on smoothed data. Note that for hierarchical smoothing also train our models on the higher- dimensional matrices. At test time, we use significance level a = 0.01, no = 1,000 samples for estimating the majority class and n 10,000 samples for certification. We report the classification accuracy of the smoothed classifier on the test set (clean accuracy), and the certified accuracy, that is the number of test samples that correctly classified and certifiably robust for a given radius. For node classification we report results averaged over five random graph splits and model initializations.
Baseline certificates. We compare hierarchical smoothing to additive noise and ablation certificates since our method generalizes both into a novel framework. To this end, we implement the two additive noise certificates of Cohen et al. (2019) and Bojchevski et al. (2020) for continuous and discrete data, respectively. Concerning ablation certificates, we implement the certificate of Levine and Feizi (2020b) for image classification, which ablates entire pixels. For node classification we implement the generalization to GNNs of Scholten et al. (2022) that ablates all node features of entire nodes. We conduct exhaustive experiments to explore the space of smoothing parameters for each method (see details in Appendix B). To compare the three different approaches we fix the threat model and investigate the robustness accuracy trade-off by comparing certified accuracy against clean accuracy.
Hierarchical smoothing significantly expands the Pareto-front. Notably, hierarchical smoothing is clearly expanding the Pareto-fros front when optimization for both certified accuracy and clean accuracy (see Figure 4). Especially when the number of adversarial nodes or pixels small but the feature perturbation is large, hierarchical smoothing is significantly dominating both basclines.

---

Interestingly, both baselines either sacrifice robustness over accuracy (or vice versa): While additive noise certificates obtain higher clean accuracy at worse certified accuracy, ablation certificates obtain strong certified accuracy at lower clean accuracy. In contrast, hierarchical smoothing allows to explore the entire space and significantly expands the Pareto-front of the robustness-aceuracy trade-off under our threat model. This demonstrates that hierarchical smoothing is a more flexible framework and represents a useful and novel tool for analyzing the robustness of machine learning models in general.
Entity-selection probability. With hierarchical smoothing we introduce the entity-selection probabil- ity p that allows to better control the robustness- -cceuurcy trade-off under our threat model. Specifically, for larger p we add more noise and increase robustness but also decrease accuracy. As usual in randomized smoothing, the optimal p needs to be fine-tuned against a task, dataset and radius r. In our settings we found dominating points e.g. for p = 0.81 (Cora-ML) and p = 0.85 (CIFAR10).
8 Discussion
Our hierarchical smoothing approach overcomes limitations of randomized smoothing certificates: Instead of having to derive Lemma from scratch for each smoothing distribution, we can easily integrate the whole suite of existing and future randomized smoothing certificates. Our framework is highly flexible and allows to certify robustness against a wide range of adversarial perturbations.
Hierarchical smoothing also comes with limitations: First, we inherit the limitations of ablation certificates in which the certifiable radius r bounded by the smoothing parameters independently of the classifier (Scholten et al., 2022). The underlying reason is that we do not evaluate the smoothed classifier on the entire space since we cannot reach certain matrices as exploited in Section Second, the classifier defined on the original matrix space is invariant with respect to the new dimension introduced by our smoothing distribution and not incorporating such invariances into the Neyman-Pearson--Le
yields strictly looser guarantees (Schuchardt and Günnemann, 2022).
Beyond that, our certificates are highly efficient: The only additional cost for computing hierarchical smoothing certificates is to evaluate the algebraic term A = 11-p,, p", which takes constant time (see also Appendix H). Since we train our classifiers on the extended matrices, we also allow classifiers to distinguish whether entities have been smoothed by the lower-level distribution (see Appendix A).
Future work. Future work can build upon work towards even stronger certificates in theory and practice, for example by deriving certificates that are tight under the proposed threat model and efficient to compute the same time. Future work can further (1) implement certificates for other -n-norms (Levine and Feizi, 2021: Vorácek and Hein, 2023) and domains, (2) improve and assess adversarial robustness, and (3) introduce novel architectures and training techniques.
Broader impact. Our hierarchical smoothing certificates are highly flexible and provide provable guarantees for arbitrary (Ep (or-norm) threat models, provided that certificates for the corresponding lower- level smoothing distribution exist. Therefore our contributions impact the certifiable robustness of a large variety of models in discrete and continuous domains and therefore the field of reliable machine learning in general: Our robustness certificates provide novel ways of assessing, understanding and improving the adversarial robustness of machine learning models.
Conclusion
With hierarchical smoothing we propose the first hierarchical (mixture) smoothing distribution for complex data where adversaries can perturb only a subset of all entities (e.g. pixels in an image, or nodes in graph). Our main idea is to add noise in more targeted manner: We first select subset of all entities and then we add noise to them. By certifying robustness under this hicrarchical smoothing distribution we achieve stronger robustness guarantees while still maintaining high accuracy. Overall, our certificates for hicrarchical smoothing represent novel, flexible tools for certifying the adversarial robustness of machine learning models towards more reliable machine learning.
Acknowledgments and Disclosure of Funding
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.
10

---

References
Aleksandar Bojehevski and Stephan Günnemann. Certifiable robustness to graph perturbations. In Neural Information Processing Systems, NeurIPS, 2019.
Aleksandar Bojchevski and Stephan Günnemann. Deep gaussian embedding of graphs: Unsupervised inductive learning via ranking. In International Conference on Learning Representations, 2018.
Aleksandar Bojchevski, Johannes Gasteiger. and Stephan Günnemann. Efficient robustness certifi- cates for discrete data: Sparsity-aware randomized smoothing for graphs, images and more. In Proceedings of the 37th International Conference Machine Learning, pages 1003-1013, 2020.
Shaked Brody, Uri Alon, and Eran Yahav. How attentive are graph attention networks? In Interna- lional Conference on Learning Representations, 2022.
Nicholas Carlini, Anish Athalye, Nicolas Papernot, Wieland Brendel, Jonas Rauber, Dimitris Tsipras, Ian Goodfellow, Aleksander Madry, and Alexey Kurakin. On evaluating adversarial robustness. CoRR, abs/ 10s//9992.0675, 2019.
Wenda Chu, Linyi Li, and Bo Li. TPC: transformattinnsppeciiec smoothing for point cloud models. In ICML, volume 162 of Proceedings of Machine Learning Research, pages 4035-4056. PMLR, 2022.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In International Conference on Machine Learning, pages 1310-1320. PMLR, 2019.
Francesco Croce and Matthias Hein. Sparse and imperceivable adversarial attacks. In ICCV, pages 4723-4731. IEEE, 2019.
Matthias Fey and Jan Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
Zhidong Gao, Rui Hu, and Yanmin Gong. Certified robustness of graph classification against topology attack with randomized smoothing. GLOBECOM, pages 1-6. IEEE, 2020.
Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In ICLR (Poster), 2015.
Lukas Gosch, Simon Geisler, Daniel Sturm, Bertrand Charpentier, Daniel Zügner, and Stephan Günnemann. Adversarial training for graph neural networks: Pitfalls, solutions, and new directions. In Advances Neural Information Processing Systems, NeurIPS, 2023a.
Lukas Gosch, Daniel Sturm. Simon Geisler, and Stephan Günnemann. Revisiting robustness in graph machine learning. In International Conference on Learning Representations (ICLR), 2023b.
Stephan Günnnemann. Graph neural networks: Adversarial robustness. In Lingfei Wu, Peng Cui, Jian Pei, and Liang Zhao, editors, Graph Neural Networks: Foundations, Frontiers, and Applications, chapter 8, pages 149-176. Springer, 2022.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. CVPR, pages 770-778. IEEE Computer Society, 2016.
Dan Hendrycks, Nicholas Carlini, John Schulman, and Jacob Steinhardt. Unsolved problems in ML safety. CORR, abs/2109. 13916, 2021.
Miklós Z. Horváth, Mark Niklas Müller, Mare Fischer, and Martin T. Vechev. Boosting randomized smoothing with variance reduced classifiers. In ICLR. OpenReview.net, 2022a. 2022a.
Miklós 7. Horváth, Mark Niklas Müller, Marc Fischer, and Martin T. Vechev. (De-) Randomiedd Smoothing for Decision Stump Ensembles. In Advances in Neural Information Processing Systems, NewrIPS, 2022b.
Miklós Z. Horváth, Mark Niklas Müller, Mare Fischer, and Martin T. Vechev. Robust and accurate compositional architectures for randomized smoothing. CoRR, abs/2204.00487,, 2022c.
11

---

Zhuoqun Huang, Neil Marchant, Keane Lucas, Lujo Bauer, Olya Ohrimenko, and Benjamin I. P. Rubinstein. RS-Del: Edit distance robustness certificates for sequence classifiers randomized deletion. In Advances in Neural Information Processing Systems, NeurIPS, 2023.
Jongheon Jeong and Jinwoo Shin. Consisteney regularization for certified robustness of smoothed classifiers. Advances in Neural Information Processing Systems, NeurIPS, 2020.
Jinyuan Jia, Xiaoyu Cao, and Neil Zhenqiang Gong. Intrinsic certified robustness of bagging against data poisoning attacks. In AAAI, pages 7961-7969. AAAI Press, 2021.
Hongwei Jin, Zhan Shi, Venkata Jaya Shankar Ashish Peruri, and Xinhua Zhang. Certified robustness of graph convolution networks for graph classification under topological attacks. In Advances in Neural Information Processing Systems, NewrIPS, 2020.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017.
Johannes Klicpera, Alcksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In ICLR (Poster). OpenReview.net, 2019.
Mareel Kollovieh, Lukas Gosch, Yan Scholten, Marten Lienen, and Stephan Günnemann. Assessing robustness via score-based adversarial image generation. arXiv preprint arXiv:2310.04288. 2023.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. 2009.
Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. In 2019 JEEE Symposium on Security and Privacy (SP), pages 656 672. IEEE, 2019.
Guang-He Lee, Yang Yuan, Shiyu Chang, and Tommi Jaakkola. Tight certificates of adversarial robustness for randomly smoothed classifiers. In Advances in Neural Information Processing Systems, NeurlPS, 2019.
Alexander Levine and Soheil Feizi. (De)Randomized Smoothing for Certifiable Defense against Patch Attacks. In Advances in Neural Information Processing Systems, NeurIPS, 2020a.
Alexander Levine and Soheil Feizi. Robustness certificates for sparse adversarial attacks by random- ized ablation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 4585 4593, 2020b.
Alexander Levine and Soheil Feizi. Improved, deterministic smoothing for l certified robustness. In International Conference on Machine Learning, 2021.
Alexander Levine, Aounon Kumar, Thomas Goldstein, and Soheil Feizi. Tight second-orden certifi- cates for randomized smoothing. arXiv preprint arXiv:2010. 2020.
Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin. Certified adversarial robustness with additive noise. In Advances in Neural Information Processing Systems, NeurlPS, pages 9459-9469, 2019.
Linyi Li, Xiangyu Qi, Tao Xie, and Bo Li. Sok: Certified robustness for deep neural networks. CoRR, abs/2009.0410 04131, 2020.
Hongbin Liu, Jinyuan Jia, and Neil Zhenqiang Gong. Pointguard: Provably robust 3d point cloud classification. In CVPR, pages 6186-6195, Computer Vision Foundation IEEE, 2021.
Ilya Loshchilov and Frank Hutter. SGDR: stochastic gradient descent with warm restarts. In ICLR (Poster). OpenReview.net, 2017.
Jiaqi Ma, Shuangrui Ding, and Qiaozhu Mei. Towards more practical adversarial attacks on graph neural networks. In Advances in Neural Information Processing Systems, NeurIPS, 2020.
Andrew McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore, Automating the construction of internet portals with machine learning. Inf. Retr., 3(2): 2000.
12

---

Apostolos Modas, Seyed-Mohsen Moosavi-Dezfooli, and Pascal Frossard. Sparsefool: A few pixels make a big difference. In CVPR. pages 9087-9096. Computer Vision Foundation IEEE, 2019.
Jeet Mohapatra, Ching-Yun Yun Ko, Tsui-Wei Weng, Pin-Yu Chen, Sijia Liu, and Luca Daniel. Higher- order certification for randomized smoothing. In Advances in Neural Information Processing Systems, NeurlPS, volume 33, pages 1501-4511, 2020.
Felix Mujkanovic, Simon Geisler, Stephan Günnemann, and Aleksandar Bojchevski. Are defenses for graph neural networks robust? In Neural Information Processing Systems, NeurIPS, 2022.
Mark Niklas Müller, Mislav Balunovic, and Martin T. Vechev. Certify or prediet: Boosting certified robustness with compositional architectures. In ICLR. OpenReview.net, 2021.
Jerzy Neyman and Egon Sharpe Pearson. 1x.
the problem of the most efficient tests of statistical hypotheses. Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of Mathematical or Physical Character, 231
1933.
Aditi Raghunathan, Sang Michael Xie. Fanny Yang, John C. Duchi, and Percy Liang. Adversarial training can hurt generalization. CoRR, abs/1906.06032, 2019.
Hadi Salman, Mingjie Sun, Greg Yang, Ashish Kapoor, and J. Zico Kolter. Denoised smoothing: A provable defense for pretrained classifiers. In Advances in Neural Information Processing Systems, NeurlPS, 2020.
Yan Scholten, Jan Schuchardt, Simon Geisler, Aleksandar Bojchevski, and Stephan Günnemann. Randomized cressage-intereepee smoothing: Gray-box certificates for graph neural networks. In Advances in Neural Information Processing Systems, NeurIPS, 2022.
Jan Schuchardt and Stephan Günnemann. Invariance-aware randomized smoothing certificates. In Advances in Neural Information Processing Systems, NeurIPS, 2022.
Jan Schuchardt, Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Collective robustness certificates: Exploiting interdependence in graph neural networks. In International Conference on Learning Representations, 2021.
Jan Schuchardt, Yan Scholten, and Stephan Günnemann. Provable adversarial robustness for group equivariant tasks: Graphs, point clouds, molecules, and more. In Advances in Neural Information Processing Systems, NeurlPS, 2023a.
Jan Schuchardt, Tom Wollschläger, Alcksandar Bojchevski, and Stephan Günnemann. Localized randomized smoothing for collective robustness certification. In ICLR. OpenReview.net, 2023b.
Oleksandr Shchur. Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint arXiv:1811.05868, 2018.
Jiawei Su, Danilo Vasconcellos Vargas, and Kouichi Sakurai. One pixel attack for fooling deep neural networks. IEEE Trans. Evol. Comput., 23(5):228-88) 2019.
Peter Súkeník, Aleksei Kuvshinov, and Stephan Günnemann. Intriguing properties of input-dependent randomized smoothing. In ICML, volume 162 of Proceedings of Machine Learning Research, pages 20697-20743. PMLR, 2022.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In ICLR (Poster), 2014.
Keith D Tocher. Extension the soyman--parsee theory of tests to discontinuous variates. Biometrika, 37(1/2)110-144, 1950.
Dimitris Tsipras Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry. Robustness may be at odds with accuracy. In ICLR (Poster). OpenReview.net, 2019.
Petar Velickovie, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
13

---

Václav Vorácek and Matthias Hein. Improving 11-certified robustness via randomized smoothing by leveraging box constraints. In ICML, volume 202 of Proceedings of Machine Learning Research, pages 35198-35222. PMLR, 2023.
Binghui Wang, Jinyuan Jia, Xiaoyu Cao, and Neil Zhenqiang Gong. Certified robustness of graph neural networks against adversarial structural perturbation. KDD, pages 1645-1653. ACM, 2021.
Yihan Wu, Aleksandar Bojchevski, Aleksei Kuvshinov, and Stephan Günnemann. Completing the picture: Randomized smoothing suffers from the curse of dimensionality for a large family of distributions. In AISTATS, volume 130 of Proceedings of Machine Learning Research, pages 3763-3771. PMLR, 2021.
Cihang Xie, Mingxing Tan, Boqing Gong, Jiang Wang, Alan L. Yuille, and Quoe V. Le. Adversarial examples improve image recognition. CVPR, pages 316-825. Computer Vision Foundation / IEEE, 2020.
Greg Yang. Tony Duan, J. Edward Hu, Hadi Salman, Ilya P. Razenshteyn, and Jerry Li. Randomized smoothing of all shapes and sizes. ICML, volume 119 of Proceedings of Machine Learning Research, pages 10693-10705. PMLR, 2020a.
Yao-Yuan Yang. Cyrus Rashtchian, Hongyang Zhang, Ruslan Salakhutdinov, and Kamalika Chaud- huri. closer look at accuracy vs. robustness. In Advances in Neural Information Processing Systems, NeurIPS, 2020b.
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing. Laurent El Ghaoui, and Michael I. Jordan. Theoretically principled trade-off between robustness and accuracy. In ICML, volume 97 of Proceedings of Machine Learning Research, pages 7472-7482. PMLR, 2019.
Daniel Zügger and Stephan Günnemann. Certifiable robustness and robust training for graph convolutional networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2019.
Daniel Zügner and Stephan Günnemann. Certifiable robustness of graph convolutional networks under structure perturbations. In Proceedings the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1656-1665, 2020.
14

---

A Additional experiments and results
In the following we provide additional results for our experiments with hierarchical randomized smoothing for the tasks of node and image classification.
83
Clean Accuracy
82
Clean Accuracy
81
81
80
Hicrarchical smoothing
Hierarchical smoothing
Sparse smoothing (Bojchevski et al., 2020)
Spurse smoothhng (Bujchevski 2020)
Interoeption smoothing (Scholten al., 2022)
Interception smoothing (Scholten al., 2022)
79
30
60
70
20 30
50
60
Certified Accuracy (%)
Certified Accuracy (%)
Figure 5: Discrete hierarchical smoothing significantly extends the Pareto-front w.r.t. robustness-
accuracy (smoothed GAT on Cora-ML). Left: r= = 0, = 20. Right: 1, = 0, ra = 40.
83
83
Clean Accuracy (%)
Clean Accuracy (%
82
82
Iberarchical smoothhing
Hieerrchical smoothing
Sparse smoothing (Bojchevaki et al.,, 2020)
Sparse smoothing (Bojchevski et 2020)
Interception smoothing (Scholten 2022)
Interception smoothing (Scholten 2022)
79
79
20
30
40
50
60
10
20
30
40
50
60
70
Certified Accuracy (%)
Certified Accuracy (%)
Figure 6: Discrete hierarchical smoothing significantly extends the Pareto-front w.r.t. robustness- 5, rd
accuracy (smoothed GAT on Cora-ML). Left: r 1,
0. Right: = 11 10, ra = 0.
83
82
Clean Accuracy
82
Clean Accuracy
81
Hiersrchical smoothing
Hierurchical smoothing
Sparse smoothing (Bojchevski et al., 2020)
Sparse smoothing (Bojchevski et al., 2020)
Interception smeothing (Scholten 2022)
Interception smonthing (Scholten 2022)
79
78
10
20
30
40
50
60
70
20
30
50
60
Certified Accuracy (%)
Certified Accuracy (%)
Figure 7: Discrete hierarchical smoothing significantly extends the Pareto-front w.r.t. robustness-
accuracy (smoothed GAT on Cora-ML). Left: r=1,ra = 5, d
15. Right:
ra = 0, = 40.
Clean Accuracy (%
Clean Accuracy (%
90
85
85
80
Hierarchical smoothing
Hierarchical smoothing
Gaussian smoothing (Coben et al., 2019)
Gaussian smoothing (Cohen et al., 2019)
Ablation smoothing (Levine and Feizi, 2020b)
Ablation smoothing (Levine and 2U20b)
75
75
58 60 62 64 66 68 70 72 74 76 78 80
58
60
62
64
66
68
70
72
Certified Accuracy (%)
Certified Accuracy (%)
Figure 8: Continuous hierarchical smoothing significantly extends the Pareto-front w.r.t. robustness-
accuracy (smoothed ResNet50 on CIFAR10). Left: r 2, = 0.4. Right: r = 3, e = 0.3.
15

---

Clean Accuracy (%)
90
Clean Accuracy (%)
85
85
80
Hicrarchical smoothhng
80
Hierarchical smoothing
Gaussian smoothing (Coben al.,
Gaussian smoothing al.,
Ahlation smoothing (Levine and Feizi, 20206)
Ahlation smoothing (Levine and Feizi, 2020b)
75
58
60
62
64
66
68
70
72
58
60
62
64
66
68
70
72
Certified Accuracy (%)
Certified Accuracy (%)
Figure 9: Continuous hierarchical smoothing significantly extends the Pareto-front w.r.t robustness-
accuracy (smoothed ResNet50 on CIFARIO). Left:
c 0.35. Right: = 4, 0.4.
Clean Accuracy (%)
80
Clean Accuracy (%)
80
75
75
65
Hierarchical smoothhng (with skip)
65
Hierarchical smoothing (with skip)
Hierarchical smoothing (without skip)
Hierarchical smoothing (without skip)
60
Spurse smoothing (with skip)
60
Sparse smoothing (with skip)
Sparse smoothing (without skip)
Sparse smoothing (withour skip)
55
55
10
20
30
40
50
60
0
10
20
30
40
50
60
Certified Accuracy (%)
Certified Accuracy (%)
Figure 10: Skip-connections for hierarchical and sparse smoothing significantly extend the Pareto-
front (smoothed GAT on Cora-ML). Left: r = r,
0, rd
70. Right: 3, ra = 0,
70.
Clean Accuracy (%)
82
Clean Accuracy (%)
82
81
81
79
79
78
78
Hierarchical smoothing (with cnlumn)
Hiemrchical smoothing (with column)
76
76
Hierarchical smoothing (wle column)
Hierarchical smoothing (wlo column)
30
60
30
60
Certified Accuracy (%)
Certified Accuracy (%)
Figure 11: Hierarchical smoothing with and without appended column (smoothed GAT on Cora-ML).
Left: L, 0,r 40. Right: r
rd
70.
Cert. ACC (%)
Cert. ACC (%)
0.8
GATV22
0.8
GATIV
0.8
GATV22
0.6
OCN
0.6
GCN
Cort. ACC
0.6
GCN
0.4
0.4
0.4
0.2
0.2
0.2
10
15
20
25
30
5
10
15
20
25
30
5
10
15
20
25
30
Fo (dotted) ra (solid)
Ta (dotted) ra (solid)
Ta (dotted) ra (solid)
Cort. ACC (%)
0.8
Cert. ACC ())
0.8
Cert. ACC (%)
0.8
0.6
0.6
0.6
0.4
0.4
0.4
0.2
0.2
0.2
0.0 0.2 0.4 0.6 0.8 1.0 1.2
0.0
0.2 0.4
0.6 0.8 1.0 1.2 0.0 0.2 0.4 0.6 0.8 1.0 1.2
Radius
Radius
Radius
Figure 12: Upper row: Smoothed GNNs on Cora-MI. (p 0.8, Pa 0.006, Pa 0.88) for
r 1,2.3 3 from left to right. Lower row: Smoothed ResNet50 on CIFAR10 for different radii r (Left:
150, a = 0.25, Middle: 150, o = 0.35. Right: = 160, a 0.4.)
16

---

Cert. ACC (%)
Cert. ACC (%
Cert. ACC (%)
0.8
10,000
0.8
0.01
0.8
0.01
0.6
1,000
0.6
0.001
0.6
0.001
211
0.4
0.4
0.4
0.2
0.2
0.2
10
15
20
25
30
0
5
10
15
20
25
30
0
5
10
15
20
25
30
Radius Fd
Radius rd
Radius Td
Figure 13: Smoothed GAT models on CoraML (r = 1, = 0). Different number of Monte-Carlo
samples and the effect on the certifiable robustness. Left: a = 0.01. Middle: nı = 100. Right: n1 = 10,000. Different clean accuracies at 0 are due to abstained predictions.
For node classification we experimentally observe that smoothed GAT models are more robust on average (Figure 12 upper row). We therefore decide show results for smoothed GAT models in the following. Recall that r is the number of adversarial nodes, Fa is the number of adversarial deletions (1 -> 0), and ra the number of adversarial insertions (0 - 1). In Figure we show results for varying with fixed r = and ra = 0. In Figure 6 we further vary Ta with fixed r = 1 and ra > 0 and r.
ra 0. Figure 7 show results for For image classification, recall that r is the number of pixels controlled by the adversary and e the perturbation strength in fi-dittance across channels. In Figure 8 and Figure 9 provide additional results for different radii and c.
and separately results for
Clearly, hierarchical randomized smoothing is significantly expanding the Pareto-froe front w.r.t. the robustness- accurrcy trade-off in all these settings. Since our certificates generalize ablation and additive noise certificates into with the existing methods under our threat model. Note that in special threat models where e.g. adversaries have access all nodes (r N), our certificates correspond to standard randomized smoothing and consequently perform on-par with existing methods.
common framework, our method performs either better on-par
In Figure 12 (upper row) we compare different GNN architectures for the task of node classification and generally observe that smoothed GAT models are more robust on average. Figure 12 (lower row) we provide further results for different smoothing paramcters when certifying the robustness of smoothed ResNet50 models on CIFAR 10. Note the different effects on the certifiable robustness at different radii when increasing and le (increasing & corresponds to decreasing p).
In Figure we study the setting where adversaries do have access to target nodes in the graph only to nodes in the first- and second-hoy neighborhoods (this setting has been previously studied by Scholten et al. (2022)). Such threat models allow us to introduce skip-connections: We can forward the (unsmoothed) features of target nodes separately through the GNN (without graph structure) and add the final representations on the representations obtained with smoothing. In Figure 10 we experimentally observe that such skip-connections can significantly expand the Pareto-front w.r.t. robustness and accuracy of sparse and hierarchical smoothing.
In Figure 11 we perform experiments with and without the additional additional column for smoothed GAT models on CoraML. Notably, training the models on the extended matrices and using the additional column at inference can result in better classifiers: As we experimentally observe for graph- structured data, using the additional column significantly extends the Pareto-front w.r.t. robustness and accuracy under specific threat models.
In Figure 13 we study the effect of different numbers of Monte-Carlo samples on the certificate strength. We observe that for our setting using a = 0.01 and 10,000 sufficient to compare our method to the baselines. Note that in practice one would have to fix a and no. ni prior to computing certificates to ensure their statistical validity.
every experiment 5 times with different dataset splits and model initializations and report averaged results. The average standard deviation is (3%, 3%, 4%, 4%) in clean accuracy and (3%, 3%, 2%, 3%) in certified accuracy (across all node classification experiments, hierarchical smoothing only, sparse smoothing only, and ablation smoothing only, respectively).
Error bars. For the node classification task
17

---

B Full experimental setup (Section 7)
We provide detailed information on the experimental setup as described in Section 7 to ensure reproducibility of our results. Note that we also upload our implementation."
B.1 Experimental setup for the task of node classification
Datasets and models. We implement smoothed classifiers for four architectures with two message- passing layers: Graph convolutional networks (GCN) (Kipf and Welling, 2017), graph attention networks (GAT and GATv2) (Velickovic et al., 2018; Brody et al., 2022), and APPNP (Kliepera et al., 2019). We train models the citation dataset Cora-ML (Bojchevski and Günnemann, 2018; McCallum et al., 2000) consisting of 2,810 nodes with 2,879 binary features, 7,981 edges and 7 classes. We follow the standard procedure in graph machine learning (Shchur al., 2018) and preprocess graphs into undirected graphs containing only their largest connected component.
Model details. We implement all GNN models for two peessage-passingg layers. We use 64 hidden channels for GCN (Kipf and Welling, 2017) and APPNP (Kliepera al., 2019), and 8 attention heads for 8 hidden channels for GAT and GATv2 (Velickovic et al., 2018; Brody et al., 2022). For APPNP we further set the hyperparameter s_hops to 10 and the teleport probability to 0.15.
Node classification task. For GNNs we follow the setup in (Scholten et al., 2022). We evaluate our certificates for the task of node classification in semi-supervised inductive learning settings: We label 20 randomly drawn nodes per class for training and validation, and 10% of the nodes for testing. We use the labelled training nodes and all remaining unlabeled nodes as training graph, and insert the validation and test nodes into the graph at validation and test time, respectively. We train our models on training nodes, tune them on validation nodes and compute certificates for all test nodes. Note that transductive settings come with shortcomings when evaluating robustness certificates (Scholten et al., 2022), or in adversarial robustness on graph-structured data in general (Gosch et al., 2023a).
Training details. We train models full-batch using Adam (learning rate = 0.001, =09,, 32 0.999, --00, weight decay 54) for maximum of 1,000 epochs with cross-entropy loss. Note that we implement early stopping after 50 epochs. We also use a dropout of 0.5 on the hidden node representations after the first graph convolution for GCN and GAT, and additionally dropout of 0.5 on the attention coefficients for GAT and GATv2.
Training-time smoothing parameters. During training sample one smoothed feature matrix (i.e. a matrix with (partially) added noise) in each epoch and then we normally proceed training with the noised feature matrix. Unless stated differently we also train models on the higher-dimensional matrices, i.e. we append the additional column to the matrices. Note that we use the same smoothing parameters during training as for certification.
Experimental evaluation. We compare hierarchical smoothing to the additive noise baseline by Bojchevski et al. (2020) and the ablation baseline Scholten et al. (2022) as follows: We run 1,000 experiments for each method by (1) randomly drawing specific smoothing parameters (p and p-, depending the method), (2) training 5 smoothed classifiers with different seeds for the datasplit and model initialization, (3) computing robustness certificates under the corresponding smoothing distribution, and (4) averaging resulting clean and certified accuracies.
Exploring the Pareto-front. In our exhaustive experiments we randomly explore the entire space of possible parameter combinations. The reason for this is to demonstrate Pareto-optimality. i.e. to find all ranges of smoothing parameters for which we can offer both better robustness and accuracy. Note that in practical settings one would have to conduct significantly less experiments to find suitable parameters, and the task efficiently finding the optimal parameters is a research direction orthogonal to deriving robustness certificates.
Smoothing parameters for node classification. We randomly sample from the following space of possible smoothing parameters (we draw from a uniform distribution over these intervals):
Discrete hierarchical smoothing: p E [0.51, 0.993), p+ E [0, 0.05), p_ E [0.5, 1),
Sparse smoothing (additive noise baseline): p+ E [o, 0.05]. p_ E [0.5, 1]
Interception smoothing (ablation smoothing baseline): p E [0.51, 0.993]
PProject page: tttps://wwit cs. cit. www. ttw.dd//dmmm/iheerrraaaaaammooo
18

---

Note that the search space of hierarchical smoothing is the cross product of the search spaces of the two baselines (sparse smoothing (Bojchevski et al., 2020) and interception smoothing (Scholten et al., 2022)). Notably, we still find that hierarchical smoothing is superior despite running 1,000 experiments equally for three methods (see Section 7). Note that we run 1,000 experiments equally for all methods to establish an equal chance for random outliers in accuracy. Also note that for clarity of the plots we only include points with certified accuracies of larger than 0%.
B.2 Experimental setup for the task of image classification
Dataset and model architecture. For the task of image classification we follow the experimental setup in (Levine and Feizi, 2020b) and train smoothed ResNet50 (He al., 2016) on CIFARIO (Krizhevsky et al., 2009). CIFAR10 10 consists of 50,000 training images and 10,000 test images with 10 classes (6,000 images per class). The colour images are of size 32x32 and have channels. Note that for runtime reasons we only certify a subset of the entire test set: For all experiments we report clean and certified accuracy for the same subset consisting of 1,000 randomly sampled test images.
Training details. We train the ResNet50 model with stochastic gradient descent (learning rate 0.01, momentum 0.9, weight decay 5e-4) for 400 epochs using batch-size of 128. We also deploy cosine learning rate scheduler (Loshchilov and Hutter, 2017). At inference we use a batch size of 300. We append the additional indicator channel (see Figure 3) during training and certification. We train the smoothed classifiers with the same noise level as during certification.
Image preprocessing and smoothing. We augment the training with random horizontal flips and random crops (with a padding of 4). We normalize all images using the channel-wise dataset mean [0.4914, 0.4822, 0.4465] and standard deviation [0.2023, 0.1994, 0.2010). For the ablation smoothing baseline we follow the implementation of Levine and Feizi (2020b) and first normalize the images before appending three more channels to the images. Specifically, for each channel x we append the channel x (resulting in 6 channels in total). Finally, we set all channels of ablated pixels to O. We train and certify the extended images. See Levine and Feizi (2020b) for a detailed setup of their method. For hierarchical smoothing and the Gaussian smoothing baseline (Cohen et al., 2019) we first add the Gaussian noise and then normalize the images. Note that for hierarchical smoothing we extend the images with the additional indicator channel (Figure 3), resulting in 4 channels in total.
Smoothing parameters for image classification. Note that the ablation baseline (Levine and Feizi, 2020b) draws pixels to ablate from a uniform distribution 2/(A: N) over all possible subsets with pixels of an image with N total pixels. This is in contrast to our approach, which selects pixels to add noise to with a probability of p. For the comparison we choose the pixel selection probability
= 1 for every k, where N is the number of pixels in an image (i.e. we select & pixels in expectation). This way, increasing i corresponds to decreasing p and vice versa. We run experiments for every 10th & from 0 to 500. Note that for & larger that 512 we cannot obtain certificates with either method since then A > 0.5. For Gaussian smoothing we run experiments for every 100th in the interval [o. 1]. and for hierarchical smoothing for every 20th a in [0, 1]. Overall, we run 50 experiments for the ablation baseline (Levine and Feizi, 2020b), 100 experiments for the Gaussian noise baseline (Cohen et al., 2019), and 1,000 experiments for hierarchical smoothing.
19

---

B.3 Further experimental details
Certification parameters. All presented plots for graphs show results for the tighter multi-class certificates, for images we compute the binary-class certificates. Our certificates are probabilistic (Cohen et al., 2019), and we use Monte-Carte samples estimate the smoothed classifiers with Clopper-Pearson confidence intervals for 0.01 (thus our certificates hold with high probability of 99%). We also apply Bonferroni correction to ensure that the bounds hold simultaneously with confidence level 1 a. We follow the procedure of Cohen et al. (2019) and, if not stated differently, use no = 1,000 Monte-Carlo samples for estimating the majority class at test time and n 10,000 samples for the certification at test time.
Reproducibility. To ensure reproducibility we further random seeds for all random processes including for model training, for drawing smoothing parameters and for drawing Monte Carlo samples. We publish the source code including reproducibility instructions and all random seeds.
Computational resources. All experiments were performed on a Xeon E5-2630 v4 CPU with a NVIDIA GTX 1080TI GPU. In the following we report experiment runtimes (note that for node classification we compute certificates for different smoothed models each experiment): Regard- ing node classification experiments, the average runtime of hierarchical smoothing for the 1,000 experiments is 1.6 hours. For the additive noise baseline 1.5 hours, and for the ablation baseline 0.92 only train single classifier. The overall training and certification
hours. For image classification process takes (on average) 9.9 hours for hierarchical smoothing, 8.6 hours for Gaussian smoothing. and 13.3 hours for ablation smoothing.
Third Whird-party party assets. For the sparse smoothing baseline we use the implementation Bojchevski the implementation of Scholten et al. (2022). 6 We implement all GNNs using Py'Torch Geometric (Fey and Lenssen, 2019).' The graph datasets publicly available and can be downloaded also e.g. using PyTorch Geometric. The CIFARI 10 dataset also publicly available, for example via the torchvision library.
al. (2020). 5 For the ablation smoothing bascline for GNNs
http:://oooootttooggr//sssssttte html
20

---

C Robustness certificates for hierarchical smoothing (Proofs of Section 5)
In the following we show the statements of Section 5 about hierarchical smoothing certificates and correctness of the following certification procedure:
Algorithm 1: Binary-class Robustness Certificates for Hierarchical Randomized Smoothing
Input: f. X, Lower-level smoothing distribution Radius (r, c), Ro. R1,
counta0 + SampleUhderHHosseu/ X. p. μ4 mo)
counts1 SampleUnnderNoise/// X, p4, n1)
y4 f top index in counts0; :
PA ConfideenceBound
[ya], n,, 1 - -a);
A - y²:
PA LowerieeraKoorssaaaeooverroooo
E, T-A
PA- (1 -1-)) Α) > 3 then
Return: yA certified
end
Return: ABSTAIN
Here, oower e,,,, PA) computes the existing certificate, specifi-
cally the smallest Px,ya over the entire threat model, e.g. (pA) - +) for Gaussian smoothing.
The remaining certification procedure is analogous to the certification in (Cohen et al., 2019).
C.1 Proofs of Section 5
First, define the space Z Nx(+++ & XND 10, 11 and recall the definition of the reachable set A a A1 A2 with
A A Z E E Nx(+11
Vi: (T: 0) - (z: =x;00);
and
A - I Nx(+1) Vi (T:
(z. ã. (0)]
Intuitively, A contains only those Z that be sampled from either V x x (given the lower-level smoothing distribution has infinite support). Note that these two sets are not necessarily disjoint, so we cannot apply the Neyman CeymannPearson Lemma for discrete random variables (Tocher, 1950) on the upper-level smoothing distribution o yet. The following Proposition therefore provides a partitioning of the space (D++1)
Proposition The regions Ro, R1, R2 and Rg are disjoint and partition the space Nx++1)),
R. _ I Nxx+11) \ A
R1 [Z E A T, 0, 2, xz x,
. R2 _ [Z E A WEC:T=])
Rs Z E A E
0, (
Proof. We want to show that the four sets above (1) are pairwise disjoint, and (2) partition (D+1)) that is Ro W R1 H RR2 t R3- N (D++1)
Clearly have Nx++1) Ro A due the definition the region Ro. Thus we only have to show R, I R2 I R3 = A:
(I) We show Ry, are pairwise disjoint:
We have R₂ R1 = 0 and R2 n R3 since in region R2 have t, for all E C, which does not hold for R2 or R3.
Moreover, R2 R3 0 because Z R2 then R3 (and vice versa) due the to definition of A and R2 C Ar, R3 C Ag.
(2) We show R1 R2 U R3 = A:
"C": Clearly R, C A.R C A, and Ra C A by definition of the regions.
"!": Consider any Z E A = Ai U.. Either (1) all perturbed rows are selected and Z E R2-
or (2) at least one perturbed row is not selected (3i T. = 0), in which case we either have
Z E R1 Z R3. depending on whether Z E A,, Z Ag. respectively.
21

---

We further have to derive the probability to sample Z of each region from both Dx and Li x for applying the Neyman-Penne Pearson Lemma (Tocher, 1950) for discrete random variables on the upper-level smoothing distribution & that selects rows before adding noise.
Proposition 2. Given x and M X. the regions of Proposition 1 and A _ 1 - 1-plcl we have
Pr IZ E R1 A
Pr 2 22)
11
Pr
1 E Ra] = 0
-~ x
Z~
ロ~ x
Pr IZ E R1] 0 Z~4 x
Pr E R2 -1
Pr Z E Ra = A
2 ロ~の
x
2 -~ x
Proof. The probability to select all |C] perturbed rows is p" since we sample each T; independently
from a Bernoulli: T: sid 1 - p" = A. The remaining follows from the fact that matrices from region R₁ cannot be sampled from V x and matrices from R3 cannot be sampled from V xx.
~ Ber(p). Consequently the probability to not select at least one perturbed row
Note that we need region Ro just for a complete partitioning of 2Nx(D+1), This region contains essentially all matrices we cannot sample neither from x nor V x. For example, matrices with a row that differs from the same row in X and X without a previous selection of that row cannot be sampled from the two distributions simply because first select rows and then we only add noise to the rows that we selected. Thus we have Prz x LZ E Ro] = 0 and Prz x IZ E Rol = O.
Before we derive the lower bound on PX,y we first restate the Neyman Pearson Lemma as presented in Section 3:
Lemma 1 Jeyyann-Parsoee lower bound). Given X, E XNDD distributions px: x class label E Y, probability px,y and the set S₂ _ {W E EXNxD 1x (W) S K 1xxxx( (W)) }. we have
Px
Pr [W E Sx] with K E R. s.t.
Pr I E Sx] = PX.9
W--x
Proof. See (Neyman and Pearson, 1933) and (Cohen et al., 2019).
There are different views on Lemma 1. In the context of statistical hypothesis testing, Lemma I states that the likelihood ratio test is the uniformly most powerful test when testing the simple hypothesis x (W) against | (W). For such views refer to Cohen et al. (2019).
Now we prove our main theorem:
Theorem 1 SrcymannPeeasoon lower bound for hierarchical smoothing). Given fixed X, X E NND let μx denote a smoothing distribution that operates independently on matrix elements, and V x the induced hierarchical distribution over z x(D+1), Given label y y and the probability px,y y to
classify X as under V. Define Sy & {We E XICxDD Mxe (W) S K. (W)]. We have:
Px 2
Pr IW E 3.). 61]-(1-00 (1-A) A) with K E R4 S.t.
Pr W-RXE
W E S.]
Px,v
W-u8e
1 1- A
where Xe and Xe denote those rows a, of X and i; of X with i E C, that is x; F i.
Proof. We are solving the following optimization problem:
Px,u
min Pr [MZ = =y s.l.
Pr
[M( = v) PX."
REa 2~
We can use the partitioning of Proposition 1 and apply the law of total probability:
P
min kell
Pr [b(Z) H~ x
Z R.]
Pr IZ
Rd]
z~のx x
1=0
s.t.
Σ
Pr Z~E x
|h (Z) y Z R.)
Pr 1Z Ru] px,y 2~ルx x
We apply Proposition 2 and cancel out all zero probabilities:
P Px,
min
Pr [k(Z) y Z E R2] (1 A) +
Pr [k(Z) Z E Ra] A
KEB
n~E x
こーの x
s.t.
Pr [h(Z) = y Z E R₂ (1 - A) + -~
Pr [h(Z) 2 E R1] A = Px
Z -~"x
22

---

This is minimization problem and to minimize we choose Prz [M = Z E Ra] = 0 and Prz [k( y Z R1 = 1. In other words, in the worst-case all matrices in R1 that we never observe around X are correctly classified and the worst-case classifier first uses the budget px,y on region R,
We obtain:
PR
min KcH
Pr [k( = y Z E R2] (1 -1-46 () 2~ x
s.t.
Pr Z~ x
[b( = y Z E R2] (1 A) = Px.y
Here we can see that for p 0 (i.e. A = 1) we have just Px.y = 0. We can assume p > 0 in the following.
We can further rearrange the terms:
P Px,
(1 A)
min hell
Pr [k(Z) y Z E R2]
Px.y
s.t.
Pr
[h(Z) = y Z E R2
Z~0x
1-
Now can apply Lemma 1:
Px
Pr I Sx Z~V
Z E R2] (1 (1- A)
with E R, s.t.
(2)
Px,y A (1-A)
Pr IZ Sx 2 R2] -~7x x
for S. 2 z ZNX(D-1), x (Z) S k v x { Note the difference between Sy and S,
We need to realize that due to independence we have:
{Z RR x (Z) I K (x(
IZ E R2 V x W, 7) S k < (x(
ZZ R2 : Mx W T ) kx. k. px (W
N
N
Z R
II
Na. (w, [T,) S k. II
Max (w0,1T))
(3)
i=1
Z R2: II
Na (w)) SK K II Mex (wi)
sEC
iEC
Z E R2 Mxx (We) S k pxx [We)
where (*) is due to 2; 3; for all i & C and T; = 1 for i E C.
In other words this means that if Z S, R₂ then all Z' R2 that differ only in rows i C from Z are also in S, n R2 and integrate out (the "likelihood ratio" is only determined by rows i E C).
It follows that for fixed K E 14 we have
Pr IZ Z~ x
Sx
Z
R2]
[ E S.] W~uipo
Pr
and
Pr IZ E S.
Z R2]
W E Šz] W~xxe
Pr W
z~Ex
for S5 1 { E XICIDD
Mx, (W) S R. Mxe (W)} All together we obtain:
Px,y A 1-A
Px,v
Pr I Sz] (1 1 A) with k E R4 s.t.
Pr W~ixe
[ E S.)
W W~M&E
23

---

D Multi-class certificates for hierarchical randomized smoothing
In the main section of our paper we only derive so-called binary-class certificates: If PX 0.5, then the smoothed classifier g is certifiably robust. We can derive tighter certificate by guaranteeing To this end, we derive an upper bound Px,v .y S Px.v in the following:
P Px.y'
max Px.v'
Px
Pr (h(W) vl s.t.
Pr W~ux
(W y) Px.9
REA Wopx
Cohen et al. (2019) show that the maximum of Equation 4 can be obtained by using following lemma:
x, X E XNDD, distributions px, & class label y Y. probability px,y and the set S, & { E X px (W) K px ( (W) } we have
Lemma 3 Secyman-Pearson upper bound). Given X,
Px
Pr IW E Sz] with K E R. s.t.
Pr Wopx
I E Sz] = Px.v
Proof. See (Neyman and Pearson, 1933; Cohen et al., 2019).
We can now use Lemma 3 to derive upper bound under hierarchical smoothing:
Theorem 2 (Neyman- Pearson upper bound for hierarchical smoothing). Given fixed X, X E N (Neyman-Pearson
let μxx denote a smoothing distribution that operates independently on matrix elements, and V x the induced hierarchical distribution over Nx(=+11) Given label y Y and the probability px,y y to classify as y under V. Define S, A { ( E X Pxx, (W) 2 K (Xx)W))
We have:
Pr E E WWE.).CC ( A)+ + with E R. s.l. WOHRe
Pr IW E 5n] = Px.9
PX.
Wouxe
A
where Xe and Xe denote those rows x, of X and i; of X with i C, that is x; # Zt.
Proof. We are solving the following maximization problem:
Px
max Pr [b(Z)= = 8.L.
Pr
(1( = y) = px.9
hEM Z x
2~
We can use the partitioning of Proposition and apply the law of total probability:
PX,0
max KEE
Pr Z
[h(Z) = y Z E R,
Pr Z~ x
ZZ
E R.
i=0
Pr hh y Z E R1) Z x
Pr こ~ x
[Z E R.] Px.v
We apply Proposition 2 and cancel out all zero probabilities:
PX
Pr [1(Z) y Z R2] (1 A) N~V x
+ Pr [M(Z) y Z E Ra] A
KEB
Z~Z2
x
s.t.
[h(Z) = y Z E R2] (1 A) + ユーリx
Pr
Pr Z~"X
[M(Z) = Z E R2 A = Px.v
This is maximization problem and to maximize choose Prz [b(
Z E Rg =1
and Prz [h( y Z R1 0. In other words, all matrices in R3 that never observe around X are correctly classified and the worst-case classifier does not use any budget px.y on this region R3.
We obtain:
max NEEL
Pr [M( Z Ro] (1 A) + + 2~ x
s.t.
Pr オーのx
[z( = Z E RR (1 A) = PX.
The remaining statement follows analogous to the proof in Appendix C.
24

---

In this section we derived multi-class robustness certificates for randomized smoothing and showed the correctness of the following certification procedure:
Algorithm Multi-class Robustness Certificates for Hierarchical Randomized Smoothing
Input: ʃ. X, p. Lower-level smoothing distribution Radius (r, e), no, Th, a counta0 SampleUnderNNisse X, P. μs, mo)
counts1 - Sampl Semppleeenderooise(( f. XX, P. 14, 111);
yA. yB -- top two indices in countsO;
PB < ConfidenceBounds (counts1 [yA] counts [yb], R1, 1 a):
+ p":
PB LoverrLavellorrsccceepppprrooddd (14, 6,
PB
I-
A Lovertevallorrrtcsstoveeeooodd
6, 1-A
AA- (1 - A) > Pn (1 A) + A then
Return: Ул certified
end
Return: ABSTAIN
pn) computes the existing certificate, specifi- cally the largest Px.g over the entire threat model, e.g. + (TB + =) for Gaussian smoothing.
Here, Lovertlwwakoorssccseppeerrboool
The remaining certification procedure is analogous to the certification in (Cohen et al., 2019).
25

---

E
Hierarchical randomized smoothing using Gaussian isotropic smoothing (Proofs of Section 6)
Having derived our general certification framework for hierarchical randomized smoothing, we can instantiate with specific smoothing distributions certify specific threat models. In the following we show the robustness guarantees for initializing hierarchical randomized smoothing with Gaussian isotropic smoothing, as already discussed in Section We will also derive the corresponding multi-class robustness certificates.
Corollary 3. Given continuous X' R. consider the threat model B (X) for fixed X E NDD, Initialize hierarchical smoothing with the isotropic Gaussian smoothing distribution defined as μx (W)= - II= ((wss, o2 Let y y denote a label and px the probability to classify X as y under Define 1 p". Then we have:
-1p"..
PX.y - - -
min Px XEB (X)
Φ-1
1- A
Proof. As outlined in Subsection 3.3, Cohen et al. (2019) show that the optimal value of Equation 1 under Gaussian smoothing is & (Pxw.) ||ólla where & denotes the CDF of the normal
distribution and 6 Σ. Plugging this optimal value into Theorem 1 yields for any X (X))
Px,y - A 1 1
||01|2 -1 (1 (1-A)
PX.9 = -1
where A 1 11
X). The remaining statements about the minimum over the entire threat model follows from the fact that Px., is monotonously decreasing in ||0||2 and
plcl and 6 vec( X
monotonously decreasing in (see also Proposition in Section 5). Note that for fixed X we write A 1 - plci but for the entire threat model we have to use the largest A 1 1pp".
Corollary 1. Given continuous X TR consider the threat model B (X) for fixed X N Initialize the hierarchical smoothing distribution using the isotropic Gaussian distribution p (W) & I ((w;) [ I that applies noise independently on each matrix element. Let Y" E y denote the majority class and px. x the probability to classify X as y" under V. Then the smoothed classifier is certifiably robust g(X) = ((X) ) for any X E (x) if
Px - )
<<O
x-11
1-
4-1
2(1
AT
where -11 denotes the inverse CDF of the normal distribution and A ppp".
Proof. For the binary-class certificate, the smoothed classifier g is certifiably robust for fixed input X min (x)Px. > 0.5. By using Corollary 3 we have
min EB
> Px,y*
(X)
2
Px.y* g
C
$ +
(1 - A) >
A
2
PX "
A
$
1
A
2(1 -A)
PX
+ BE<O
A
2(1 41
26

---

In the following we additionally derive the corresponding multi- class- robustness certificates: Corollary 4. Given continuous X R. consider the threat model (X) for fixed X NND Initialize hierarchical smoothing with the isotropic Gaussian smoothing distribution defined as (x(W)) - as y under V. Define A - 1- - p". Then we have:
Niw:) I2.). Let E y denote a label and px v the probability to classify X
PX, 1 A
max X E (X)
Px, ①
④
(1 - -1
Proof. Cohen al. (2019) show that the optimal value of Equation 4 under Gaussian smoothing ( (P .). where Φ denotes the CDF of the normal distribution. The statement follows analogously to Corollary 3 by directly plugging this optimal value into Theorem 2.
Corollary 5 (Multi-class certificates). Given continuous X' - R. consider the threat model ( for fixed X E XNDD Initialize the hierarchical smoothing distribution V using the isotropic each
Gaussian distribution μx (W) - II N(w, (x,, o²I) that applies noise independently matrix element. Given majority class y E y and the probability px,y" to classify X as y under W.
Then the smoothed classifier is certifiably robust g(X) (XX) ffor any X E B2 (X) if
PX.." 1-
A
:)
max & "79"
Φ-
Px
A
0
1- A
where + denotes the inverse CDF of the normal distribution and A 1-p".
Proof. For the tighter multi-class certificate we have to guarantee Px, > maxy Px. The statement follows directly from Corollary and Corollary 4.
27

---

F Hierarchical smoothing for discrete lower-level smoothing distributions
Threat model details for discrete hierarchical smoothing experiments. In our discrete experiments in Section 7 we model adversaries that perturb multiple nodes in the graph by deleting ra ones (flip 1 > 0) and adding ra ones (flip
1) in the feature matrix X, that is we consider the ball B (X). Here we define this threat model more formally:
B Broir (X)
(x)=
- 1X
EXE NND
Σ +
1 1(x; Xij + +1)
(5)
ΣΣ 1X,, x; 11) S.rss ra)
where is an indicator function, the number of controlled nodes, ra the number of adversarial insertions (0 -> 1), and ra the number of adversarial deletions (1 - 0).
We expand the result of Theorem I to certificates for discrete lower-level smoothing distributions μc: Theorem 3 (Hierarchical lower bound for discrete lower-level smoothing distributions). Given discrete X and a smoothing distribution Ue for discrete data, assume that the corresponding discrete certificate partitions the imput space XrD into disjoint regions ......, Hi of constant likelihood ra- tio: He (w(w)/ (w)/ (w) Ci for all u E Hi. Then we can compute lower bound P&.y S PX.. by solving the following Linear Program (LPP):
hau (1 (1-A) S.t. h"v Px,
PX
min h
0 0
A
where i. & PIW ~ [vec( W) E Hyg and Vg & Prw |vec (W)
E Hol all q E {l,....
Proof. This follows from applying the Peyman-Pearson-Lemmaa for discrete random variables
twice (see Lemma 2). While R1, R2, R3 represent "super regions" for the upper-level smoothing distribution Ø, Hı,... H. further subdivide R2 into smaller regions of constant likelihood ratio. which is required for the lower-level discrete smoothing distribution μ.
Notably, Theorem 3 implies that we can compute the LP of the original discrete certificate for the adjusted probability of (px.,> - A1 A), and then multiply the resulting optimal value by the constant 1 - A. In particular, the feasibility of the Linear Program and of computing v, 0 can be delegated to the certificate for the underlying μ.
Analogously for the upper bound for discrete lower-level we need:
Lemma 4 (Discrete Neyman Pearson upper bound). Partition the input space X into disjoint re- gions RI,..., , R₂ of constant likelihood ratio ua (w pa (w) = c, {ll for all w E R,, Define f. Prw~pa (w E R2) and T 2 Pewpp (w E R.). Then Equation 4 is equivalent to the linear program Pa.. = maxne(u,1] h² s.f. h² Pa.w where h represents the worst-case classifier.
Then we can show:
Theorem 4 (Hierarchical upper bound for discrete lower-level smoothing distributions). Given discrete X and a smoothing distribution Ui for discrete data, assume that the corresponding discrete certificate partitions the input space XrD into disjoint regions Hi,..., Hi of constant likelihood ra- tio: pan (n)))a(w)) = 0; for all w E Hi. Then we can compute an upper bound P solving the following Linear Program (LP):
2 P Px by
Px max
h' (1 - A)+ S.F. hTv-
PX
0 0 h4h $
I-
where i, & Prw (V) E H.yl and V & PIw (ve E Hor all q E I3.
Proof. This follows analogously to Theorem 3, specifically by applying the Neyman- Neyman-Pearson- Pearson-Lemma upper bound for discrete random variables (Lemma 4) twice (first using the "super regions" and then the level" regions).
28

---

G Hierarchical randomized smoothing using ablation smoothing
There are different types randomized ablation certificates: In image classification, Levine and Feizi (2020b) randomly ablate pixels by masking them. In point cloud classification, Liu et al. (2021) ablate points by deleting them certify robustness against adversarial point insertion, deletion and modification. In sequence classification, Huang et al. (2023) randomly delete sequence elements to certify robustness against edit distance threat models. In node/graph classification. Bojchevski et al. (2020) experiment with ablation smoothing for individual attributes but show that their additive method is superior. Scholten et (2022) directly mask out entire nodes, yielding strong certificates against adversaries that arbitrarily perturb node attributes.
Ablation smoothing differences. The ablation baseline (Levine and Feizi, 2020b) draws k pixels to ablate from a uniform distribution (k, N) over all possible subsets with k out of N pixels. Levine
and Feizi (2020b) derive A =1 (Nx
This is in contrast to approach, which selects pixels to
(x)
add noise to with a probability of p. for which we have A = p". In other words, we choose the pixel selection probability of
N (i.e. we select & pixels in expectation). This way, increasing k corresponds decreasing p and vice versa. Interestingly, this type of ablation smoothing is tighter for small N since A < A for > (see Scholten et al. (2022) (Appendix B, Proposition 5) for a detailed discussion; later also verified by Huang al. (2023)).
A
blation and additive noise hybrid. Notably, our method generalizes ablation and additive noise smoothing into a common framework: The additional indicator indicates which entity will be ablated, but instead of ablating entities we only add noise to them. If we ablate the selected rows instead of adding noise,
restore certificates for ablation smoothing as special case of our framework:
Corollary 2. Initialize the hierarchical smoothing distribution Yp with the ablation smoothing distribution (t((t) for ablation token t X² and pze (w) for w X. otherwise (i.e. we always ablate selected rows). Define A A - 1-p". Then the smoothed classifier g is certifiably robust g(X) = g(X) ) for any X E B2, (X) pxx A 0.5.
Proof.
We can first apply Theorem 3 and obtain:
PX,y A
Px
ming hTD. A) s.t. hT nT
0 h, S
1
for and 1 (since we always ablate selected rows there is only a single lower-level region H). Solving this I.P yields
Px,y A (1- Px.y A
PX.
1 A
Note one can analogously compute the upper bound Px.y by applying the corresponding Theorem 4:
Px,v A) + px + A
PX
Altogether in this special case we obtain for the multi-class certificate PX,"- > maX.4y" PX.v*
px.y* A > px.j + A
where y" is the most likely class and y the follow-up class. That is in this special case with ablation smoothing again obtain the multi-class guarantees derived by Levine and Feizi (2020b).
Related work. In the context of randomized ablation (a special case of our framework), Jia al. (2021) also define three regions and build an ablation certificate using the Neyman-Pearsee Lemma. Their regions are, however, different ours, and their certificates are designed for poisoning threat models (whereas we consider evasion settings). Moreover, Liu et al. (2021) define three regions similar to ours, but their certificate is only for point cloud classifiers and suffers from the same limitations of ablation certificates that we overcome: Our key idea is to further process the region R₂ and to utilize the budget px.y yy - by plugging it into the certificate for the lower-level smoothing distribution, which yields stronger robustness-accurage trade-offss under our threat model.
29

---

Discussion, In general, the difference between ablation certificates and additive noise certificates is that ablation smoothing does not evaluate the base classifier on the entire input space. Specifically, the supported sample spaces around X and X are overlapping but not the identical. In this context, additive noise certificates are technically tighter for threat models where adversarial perturbations are bounded. Since our certificates generalize ablation smoothing and additive noise smoothing we inherit advantages and disadvantages of both methods: While the certificate for the lower-level smoothing distribution may tight, the upper-level smoothing distribution prevents us from evaluating the base classifier on the entire matrix space. We leave the development of tight and efficient certificates for hierarchical randomized smoothing to future work.
Gray-box certificates. Scholten et al. (2022) derive gray-box certificates by exploiting the underlying mnssage-passing principles of graph neural networks. In detail, they derive tighter gray-box A that accounts for the fact that nodes may be disconnected from a target node when randomly deleting edges in graph (and disconnected nodes do not affect the prediction for the target). Interestingly, we can directly plug their gray-box A into our framework to obtain gray-box robustness certificates for hierarchical randomized smoothing.
H Extended discussion
Motivation for the indicator variable as additional column. We certify robustness of classifiers operating on the nngher-dimensiona matrix space, which allows our certificates to be efficient and highly flexible, In the following we motivate this by considering the scenario of certifying robustness on the original data space X D_ The main problem is that is technically challenging obtain an efficient certificate that depends only on the radius (and not on fixed X and X):
Consider discrete lower-level smoothing distribution, fixed X, X, smoothed matrix W and row i E C such that x; * Φ; but æ; = w; To certify robustness on the original space we have to consider the likelihood ratio for the marginal distribution x (W) _ Σ, V x (WW,T))
V x xW) E, v TT x (W)
Σ. x (T)
Let C. describe all perturbed and C all clean rows. Similar due to independence we have:
x (W)
(1)
Vx (w:) Ilr Vx, (w:) Heee xx (w,) (2) Hiec Vxx (w:)
V x
(w,) Hlee Mx, (w:) Ilie 2x, (w;)
Ilie Vx, (w,)
where (1) is due independence and (2) due to æ; = o; for clean rows i E C. Now we can consider the perturbed row i E C that chose above and consider the likelihood ratio:
(3) Mx. (w.)p + (1 p) VR. W:) Ex. UR, (w: T.)((T)
xx (w)) Er. Mxx (WTTT))((TT)
PHR. (w:)
where (3) is due to w; 2; but wi + Z.-
Due to the mixture, there are two ways sampling w; from Vz First, we may not "select" row (and then we do not smooth the row). Second, we may "select" row i but not add any noise on the selected row. Due to the mixture, we cannot simply cancel out dimensions in which the rows n; and ã; agree as in (Bojchevski et al., 2020), leading to the problem that the likelihood ratio and subsequently the point-wise certificate depends on X. Consequently, certifying robustness against an entire ball of perturbations is technically challenging since the likelihood ratio will change for every X.
We can resolve this problem by realizing that for reasonable smoothing parameters, the probability Ma, (w,) = Ha. (xx) is close to zero (probability for flipping exactly and only the dimensions where o; disagrees with 2; is close zero for small radii and high dimensional data). Specifically, the likelihood ratio for such elements is approaching co (e.g. for sparse smoothing with fixed radius ra, ra we have Msx (W:) + for + oo). Note that if we choose W and row such that x; * ã, but .; w;, we can derive the same but the other way around and find the likelihood ratio approaching O. In other words, we cannot avoid regions of 0, and do likelihood ratio for such smoothing distributions where we can flip "entire rows" from C; to ä. Certifying robustness on the higheradimensional matrix space instead is efficient, highly flexible and tight for higher dimensional rows as for example in graphs where rows represent node features.
30

---

Efficiency of hierarchical randomized smoothing. We discuss (1) the efficiency of the smoothing process, and (2) the efficiency of the certification. First, regarding the efficiency of the smoothing process, note that hierarchical smoothing only adds noise on subset of all entities. Technically this can be more efficient, although drawing from a bernoulli before adding noise may require more time in practice than directly drawing (e.g. gaussian) noise for all matrix elements simultaneously. Second, regarding certification efficiency, our method only requires the additional computation of the term A which takes constant time. Yet, closed-form solutions for the largest certifiable radius may not be available, depending on the lower-level smoothing distribution. For example we may not be able to derive flosed-form radius for the multi-class certificate under hierarchical Gaussian smoothing (see Appendix E). Still, the certification process can be implemented efficiently even without closed-form solutions, e.g. via bisection just by incrementally increasing to find the largest certifiable radius.
Non-uniform entity-selection probability p. In general we can also use non-uniform p: Let Ps denote a node-specific (non-uniform) selection probability for node i that the adversary does not control. To get robustness certificates we have to make the worst-case assumption, i.e. nodes with lowest selection probability will be attacked first by the adversary. For the certificate this means we have to find the largest possible A (see also Theorem 1). Specifically, we have to choose A A 1 - Ileez P3 where I contains the indices of the r smallest probabilities p;- Then we can proceed as in our paper to compute certificates for the smoothing distribution with non-uniform p. If we additionally know that certain nodes will be attacked before other nodes, we do not have to consider the first nodes with smallest p; but rather the first nodes with smallest p; under an attack order. This can be useful for example if one cluster of nodes is attacked before another, then we can increase the selection probability for nodes in the first cluster and obtain stronger certificates.
Node-specific smoothing distributions. If some nodes are exposed to different levels of attacks than others, we can obtain stronger certificates by making the lower-level smoothing distribution node-specific. This would allow us to add less noise for nodes that are less exposed to attacks, potentially leading to even better robustness-acuuracy trade-offs. Note, however, that this increases threat model complexity since we will have to treat all nodes separately.
Input-dependent randomized smoothing. We derive certificates for a smoothing distribution that adds random noise independently on the matrix elements. This the most studied class of smoothing distributions and allows us to integrate a whole suite of existing distributions. Although there are first approaches adding non-independent noise, the corresponding certificates are still in their infancy (Sákeník et al., 2022). Data-dependent smoothing is a research direction orthogonal to ours, and we consider the integration of such smoothing distributions as future work.
Finding optimal smoothing parameters. The randomized smoothing framework introduces param- eters of the smoothing distribution as hyperparameters (see e.g. (Cohen et al., 2019)). In general, increasing the probabilities to add random noise increases the robustness guarantees but also decreases the accuracy. We introduce an additional parameter allowing to better control the gbbustness-accuraa trade-off. Specifically, larger p adds more noise and increases the robustness but also decreases accuracy. In our exhaustive experiments we randomly explore the entire space of possible parameter combinations. The reason for this is to demonstrate Pareto -ottimllttilllty...... i.e. to find all ranges for which we can offer both better robustness and accuracy. In practice one would have to conduct significantly less experiments to find suitable parameters. Note that the task of efficiently finding the optimal parameters a research direction orthogonal to deriving robustness certificates.
Limitation of fixed threat models. Recent adversarial attacks (see e.g. (Kollovieh et al., 2023)) go beyond the notion of -n-orrm balls and assess adversarial robustness using generative methods. Our approach is limited as we can only certify robustness against bounded adversaries that perturb at most r objects with a perturbation strength that is bounded by under some Ey-norm. Since current robustness certificates can only provide provable guarantees under fixed threat models, certifying robustness against adversaries that are not bounded by l.- f.-norms is out of the scope of this paper.
Graph-structure perturbations. While we implement certificates against node-attribute perturba- tions, our framework can in principle integrate certificates against graph structrre perturbations (for example by bounding the number of nodes whose outgoing edges can be perturbed). This can be implemented by first selecting rows of the adjacency matrix A and then applying sparse smoothing (Bojchevski et al., 2020) to the selected rows only. Note that the works of Gao et al. (2020) and Wang al. (2021) also study randomized smoothing against perturbations of the graph structure, but they consider a special case of sparse smoothing Bojchevski et al. (2020) with equal flipping probabilities.
31


Reviews:
[{"review_id": "npLXVROvbn", "reviewer": "Reviewer_FfTs", "summary": "This paper proposes hierarchical randomized smoothing, a variant of randomized smoothing that not only randomly perturbs input data at test time but also randomly selects which rows of the input to perturb. This is motivated by a threat model in which an adversary only selects a subset of rows of matrix-valued data to attack. The authors show that their hierarchical smoothing scheme inherits certified robustness by the lower-level smoothing scheme used (i.e., the randomization method on the rows to be perturbed), and also show that the hierarchical scheme generalizes randomized ablation (random masking of elements rather than random additive noise). Experiments are conducted on benchmark node classification datasets that show the increased certification power over prior smoothing methods that do not account for the row-selection limitations of the adversary.", "questions": "1. In my opinion, the overarching structure of the paper could be improved. I'd recommend moving the Discussion section to the end of the paper with the Conclusion, and also moving at least the more \"general\" parts of the Related Work section to the end of the Introduction.\n\n2. Line 276: \"discrete, binary features: $\\mathcal{X} = [0,1]$.\" Do you mean $\\mathcal{X} = \\\\{0,1\\\\}$?\n\n3. Line 302: Should \"(2) evaluating certificates\" be \"(3)\"?\n\n4. The experimental comparisons seem a bit misleading. In particular, you are not making an entirely fair comparison to conventional RS, since those certificates are tailored to threat models where the adversary has access to perturb every entry in your input data. It is therefore no surprise that your certified radii are larger, since you are considering a weaker adversary altogether. How do your certificates perform in the extreme case where the adversary does have access to all entries in the matrix? Do your certificates still outperform conventional RS?", "limitations": "N/A.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is easy to follow, well-written, and appears to have some nice novel ideas for exploiting the structure of adversarial attacks on graph neural networks and related \"hierarchical\" models in order to get tighter robustness certificates than structure-blind methods.\n\n2. It is interesting that the proposed approach generalizes both conventional additive noise certificates as well as ablation (masking) certificates.\n\n3. The proposed hierarchical approach seems to be quite modular, allowing for new lower-level certification methods to be incorporated as they are developed in the future.", "weaknesses": "See below \"Questions.\"", "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 paper during the rebuttal period according to the rebuttal policy, and we therefore carefully describe all changes directly here in the rebuttal.\n\n### Concerning the paper structure (Question 1)\nWe followed your suggestion and moved the (improved) related work after the introduction, and the discussion to the end. We found that this way we also better highlight the novelty of our contributions and the contrast to related work. Thank you for helping us to further improve the paper.\n\n### Concerning the typos in line 276 and 302 (Question 2 and 3)\nYes you are right, we fixed the corresponding lines. \n\n### Concerning the experimental comparison (Question 4)\nSince our certificates generalize ablation and additive noise certificates into a new common framework, our method performs either better or on-par with the existing methods. To see this, for $r=N$ (all rows are under attack) we recover the threat model already studied in the literature (see e.g. [1,2]). In the special case of choosing $p=1$, our certificate boils down to the standard certification methods and therefore performs on-par with the baselines (see discussion in lines 195-201). \n\nPlease consider that the threat model where adversaries can only attack a subset of all rows ($r \\ll N$) is a more realistic assumption for graphs such as social networks and already actively exploited in several recent adversarial attacks against graph neural networks (see e.g. [3]). Since we propose the first smoothing distribution specifically tailored against the described threat model, we believe our experimental comparison to existing certificates is fair and scientifically sound.\n\nWe hope that we could address all your questions to your satisfaction. Please let us know if you have any additional comments or questions.\n\n### References\n[1] Jeremy M. Cohen, Elan Rosenfeld, J. Zico Kolter. Certified Adversarial Robustness via Randomized Smoothing. ICML 2019.\n\n[2] Aleksandar Bojchevski, Johannes Klicpera, Stephan Günnemann: Efficient Robustness Certificates for Discrete Data. Sparsity-Aware Randomized Smoothing for Graphs, Images and More. ICML 2020.\n\n[3] Jiaqi Ma, Shuangrui Ding, Qiaozhu Mei. Towards More Practical Adversarial Attacks on Graph Neural Networks. NeurIPS 2020.\n"}, {"review_id": "mDJth2zDVz", "reviewer": "Reviewer_7yDS", "summary": "The paper introduces a new variant of the randomized smoothing algorithm for certified robustness. The paper considers the setting where the input data is split into multiple parts or sites (e.g., a graph) and an adversary can perturb at most $r$ sites at the same time.\nTo obtain robustness certificates for this setting, the authors introduce hierarchical randomized smoothing.\n\nIn standard randomized smoothing (Gaussian) noise is added to the input, a classification model is evoked on the noisy input, and the lost likely output class is taken as the final prediction.\nIn practice this is done via Monte Carlo estimate: Noise is sampled multiple times and the majority vote is returned.\n\nHierarchical randomized smoothing mimics this process but splits the sampling of the noise into two steps: i) first a random indicator variable determining the affected sites is sampled, ii) noise is added to those sites as before.\n\nTo obtain a guarantee in this setting, the theoretical derivation combines the standard form for randomized smoothing for continuous (Gaussian) with a variant for discrete noise. Ultimately, this approach recovers the same certificate as the standard randomized smoothing algorithm, up to a scaling factor depending on the number of sites that can be perturbed at the same time, thus allowing for improvements.\n", "questions": "- Does row selection $p$ need to be uniform? What is the impact on the certificate if it is used to encode a prior on the likelihood of change/attack for different part.s\n- Can you further comment on the threat model? Not mathematically, but rather on the settings in which the proposed combination of LP-constraints over $r$ site changes is applicable.", "limitations": "Limitations and broader impact are adequately discussed in the paper.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- Strong and original contribution\n- Well written\n- Rigorous mathematical derivation\n- Good empirical results\n", "weaknesses": "I have no major concerns, other than maybe the applicability of the threat model considered in the paper (see questions).\nHowever, I have some minor comments mostly on the presentation of the paper:\n\n- In the example around line 153, I found the set $\\mathcal{R}_0$ confusing as the explanation only comes on the next page.\n- Similarly the construction of Propositions 1 and 2 might be easier to follow if it was visualized.", "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 paper during the rebuttal period according to the rebuttal policy, and we therefore carefully describe all changes directly here in the rebuttal.\n\n### Concerning a visualization of Propositions 1 and 2 (Comment 1 and 2)\nThank you for your suggestion to further improve the clarity of our claims. In response to your comment, we rewrote Section 4 to make our derivations more accessible. In this context we also included a new Figure to visualize the regions and the propositions (see rebuttal PDF in the global response). We also followed your suggestion and explain the regions and $\\mathcal{R}_0$ earlier. \n\n### Concerning row-selection probability $p$ (Question 1)\nIn our paper we currently select rows independently from each other with a row-selection probability $p$. Although there are first non-hierarchical smoothing distributions adding data-dependent noise, the corresponding certificates are still in their infancy (see e.g. [1]). The challenge of making our hierarchical smoothing data-dependent is that using higher $p$ for some parts of the input means adversaries could simply attack the other parts. Please consider that deriving robustness certificates for data-dependent smoothing distributions represents a research direction orthogonal to ours. Thank you for pointing us to this interesting idea for future work.\n\n### Concerning further applications for our threat model (Question 2)\n\nAs you correctly pointed out, we consider the threat model where adversaries can perturb at most $r$ entities of an object. This is a realistic assumption for graphs such as social networks and already actively exploited in several recent adversarial attacks against graph neural networks (see e.g. [2]). For example, consider you want to attack advertisements in Facebook: Probably you will not be able to control the entire Facebook graph, but you may be able to buy a few hundred accounts.\n\nSince we propose certificates for data where objects can be decomposed into multiple entities there are numerous applications beyond graphs: For example in Natural Language Processing, adversaries may be restricted to perturb at most $r$ documents in a collection, or at most $r$ paragraphs in a document. Further real-world examples include applications where reliability and security are crucial, this includes especially the medical and financial domains. Since graphs are ubiquitous datastructures the applicability of our certificates is versatile with a far-reaching impact. \n\nBeyond their real-life applicability, robustness certificates are also generally useful tools that allow us to assess the robustness of models beyond adversarial perturbations (for example against noisy signals or incomplete data). Robustness certificates can also provide insights to design more robust models in the future.\n\nWe hope that we could address all your questions to your satisfaction. Please let us know if you have any additional comments or questions.\n\n### References\n[1] Peter Súkeník, Aleksei Kuvshinov, Stephan Günnemann. Intriguing Properties of Input-Dependent Randomized Smoothing. ICML 2022.\n\n[2] Jiaqi Ma, Shuangrui Ding, Qiaozhu Mei. Towards More Practical Adversarial Attacks on Graph Neural Networks. NeurIPS 2020."}, {"review_id": "s1VeYykgyg", "reviewer": "Reviewer_u4ou", "summary": "A randomized smoothing based robust certification approach is presented for machine learning under test-time/inference attacks, when only a subset of data is under attack e.g. a subset of nodes in graphical data. Robustness certificates are derived for discrete and continuous domains, and empirically certified and clean accuracies are computed and compared with prior work for certified robustness for graph neural networks (GNNs).", "questions": "- What is $\\alpha$ in line 82? How is its value related to the certificates?\n- Why is the noise applied independently to all matrix entries (e.g. line 97)?\n- How do the theoretical results compare to Scholten et al. 2022?\n- If $r=N$, i.e. all rows are under attack, how do current certificates compare to previously known certificates?", "limitations": "The authors could investigate further the limitations of the proposed approach and add a discussion.", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The studied GNN model where only a subset of nodes of the graph may be attacked by the adversary is interesting and of practical significance.\n- The proposed robust certification approach could achieve better trade-off of clean and certified accuracy than existing approaches.", "weaknesses": "- The overall approach seems like a simple extension to (Cohen et al. 2019), with a suitable adjustment factor $1-\\Delta$ in the analysis corresponding to selecting a subset of rows. The theoretical analysis also follows similar arguments and it is not clear if any novel insights are obtained.\n- A key tuning parameter for the approach is $p$, it is not clear how to set $p$ in a principled way.\n- Missing several closely related prior research works e.g. [1] and [2].\n- Results seem specific to bounded $\\ell_2$ norm attacks.\n\n\n[1] Wang, Binghui, Jinyuan Jia, Xiaoyu Cao, and Neil Zhenqiang Gong. \"Certified robustness of graph neural networks against adversarial structural perturbation.\" In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 1645-1653. 2021.\n[2] Gao, Zhidong, Rui Hu, and Yanmin Gong. \"Certified robustness of graph classification against topology attack with randomized smoothing.\" In GLOBECOM 2020-2020 IEEE Global Communications Conference, pp. 1-6. IEEE, 2020.", "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 paper during the rebuttal period according to the rebuttal policy, and we therefore carefully describe all changes directly here in the rebuttal.\n### Concerning the overall approach (Comment 1)\nSo far there are no randomized smoothing certificates designed against our threat model and we demonstrate that simply using previous works is not enough when considering the robustness-accuracy trade-off. Deriving new certificates is technically challenging: One would have to propose a new smoothing distribution and prove robustness certificates for each $\\ell_p$-norm. The modularity of our approach and the adjustment by $1-\\Delta$ is the result of our particular smoothing distribution followed by a rigorous proof and represents a novel contribution: Our framework is of great flexibility since we can integrate existing certificates into our framework. We believe that our derivations represent an important contribution to the scientific community since our certificates provide better ways of assessing the robustness of GNNs and machine learning models in general.\n### Concerning hyperparameter p (Comment 2)\nAs you correctly pointed out, $p$ is a key parameter of our method and represents the probability of adding noise to the rows of a matrix. In response to your comment, we now provide additional intuition about $p$ in the paper: Specifically, larger $p$ adds more noise and increases the robustness but also decreases accuracy. By introducing this additional parameter we can better control the robustness-accuracy trade-off. Please consider that using hyperparameters of the smoothing distribution to control this trade-off is standard in randomized smoothing, and finding the optimal parameters efficiently is a research direction orthogonal to deriving robustness certificates.\n### Concerning additional related work (Comment 3)\nIn response to your comment, we revised the related work section and included the work [1] and [2] that you mentioned: The works of [1] and [2] derive robustness certificates against structural perturbations of the graph. While their certificates can be technically integrated into our framework, we experiment with the sparsity-preserving certificates proposed in [3] since it represents the current state-of-the-art in GNN certification. \n### Concerning the threat model (Comment 4)\nPlease note that our certificates hold under arbitrary $\\ell_p$-norms (we just instantiate our framework with three different norms later in the experiments). In response to your comment, we rephrased the corresponding parts in the theoretical analysis (Section 4) for clarification. \n### Concerning the parameter $\\alpha$ (Question 1)\nRandomized smoothing certificates are probabilistic and $1-\\alpha$ represents the confidence level used when estimating the smoothed classifier with Monte-Carlo samples. Please note that this is an inherent property of probabilistic certification and not a limitation of our work specifically. In response to your comment, we added further clarifications in the background section when introducing the randomized smoothing framework.\n### Concerning independent noise (Question 2)\nAs you correctly pointed out, we derive certificates for a smoothing distribution that adds random noise independently on the matrix elements. This is the most studied class of smoothing distributions and allows us to integrate a whole suite of existing distributions. Although there are first approaches adding non-independent noise, the corresponding certificates are still in their infancy [4]. Please note that non-independent noise is a research direction orthogonal to ours. Integrating such smoothing distributions is an interesting idea for future work.\n### Concerning the theoretical comparison (Question 3)\nThe certificate proposed in [5] is based on ablation smoothing and can be considered as a special case of our framework. In contrast, our paper represents a novel contribution that goes beyond simple ablation: We first select rows but instead of ablating them we add random noise to them. As we show experimentally, our method yields stronger results under our threat model when compared to [5].\n### Concerning the special case $r=N$ (Question 4)\nFor $r=N$ (all rows are under attack) we recover the threat model already studied in the literature (see e.g. [3]). In this special case our certificates are exactly as strong as existing methods (see lines 195-201). Please consider that we are proposing novel certificates specifically designed against the threat model of $r \\ll N$ (multiple but not all rows are under attack), which is a more realistic assumption for graphs and already actively exploited in several adversarial attacks against GNNs [6].\n### Concerning the discussion (Comment 5)\nPlease consider that we already discuss the limitations of our approach in Section 5. In response to your review, we further extended the discussion: Specifically, we included the hyperparameter discussion and the non-independent noise discussion (see our response to Comment 2 and Question 2). Thank you for helping us to further improve the paper.\n\nWe hope that we could address all your questions to your satisfaction. Please let us know if you have any additional comments or questions.\n### References\n[3] Aleksandar Bojchevski, Johannes Klicpera, Stephan Günnemann: Efficient Robustness Certificates for Discrete Data. Sparsity-Aware Randomized Smoothing for Graphs, Images and More. ICML 2020.\n\n[4] Peter Súkeník, Aleksei Kuvshinov, Stephan Günnemann. Intriguing Properties of Input-Dependent Randomized Smoothing. ICML 2022.\n\n[5] Yan Scholten, Jan Schuchardt, Simon Geisler, Aleksandar Bojchevski, Stephan Günnemann. Randomized Message-Interception Smoothing: Gray-box Certificates for Graph Neural Networks. NeurIPS 2022.\n\n[6] Jiaqi Ma, Shuangrui Ding, Qiaozhu Mei. Towards More Practical Adversarial Attacks on Graph Neural Networks. NeurIPS 2020."}, {"review_id": "ABYTvn8W6T", "reviewer": "Reviewer_BgsW", "summary": "The paper proposes a new threat model for the adversarial robustness - intersection of $\\ell_0$ and $\\ell_2$ ones where the $\\ell_0$ is measured as the number of modified rows of a matrix. To certify robustness to this threat models, the authors propose a variant of randomized smoothing - hierarchical smoothing scheme. First, some rows are selected at random and then they are smoothed with Gaussian smoothing. Robustness certificate is provided for this kind of smoothing distribution and the superiority over baselines is demonstrated on some graph-network tasks.", "questions": "-", "limitations": "-", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "* The paper proposes a new threat model that makes sense for modeling adversaries on graphs.\n* The proposed certification method on this threat model (actually intersection of threat models) outperforms the baselines (methods designed for the individual threat models).\n\nIn general, this would be enough for me to vote for acceptance, however there are some problems as I list below.", "weaknesses": "* The technical novelty of the paper is limited; the paper focuses on a new threat model - an intersection of two standard threat models $\\ell_0$ and $\\ell_2$ - and the provided certification method is randomized smoothing where the smoothing distribution is essentially a product of the distribution used for $\\ell_0$ (random mask) and $\\ell_2$ (Gaussian noise). The certification is then analogical to (Cohen et al.).\n* Please check all the claims if they actually say what you want to say. There are two main problems here - you consider a fixed $\\hat{X}$ and provide certificate with respect to this particular point (e.g., in Coro 1 and also in the text.) whereas you obviously want to certify robustness to all points within this distance. And second, you assume that the perturbed point is at $\\ell_0$ distance $r$ while it should be at a distance at most $r$ (e.g., lines 142-144 and from this point on).  These things should be very easy to fix to make it correct, but now it is just lax and wrong at places and it is the reason for the rejection at this point. **If this is fixed, then the paper becomes borderline acceptable for me**.\n* The exposition is maybe unnecessarily complicated. The actual mathematical machinery performed in the paper boils down to decomposing the smoothing distribution as a mixture of two distributions (over $R_1, R_2$ or $R_2,R_3$ respectively in Propo 2) and then the NP lemma to two Gaussians is used for the distributions over $R_2$ (This is the standard NP-certification of (Cohen et al.)). It takes quite some effort to even understand \"what is done\" in the paper before I can focus on \"why does it work\". I suggest the authors to provide a pseudocode (e.g., as in (Cohen et al.)).\n\n### minor\n* The method has some parameters, but there is no suggestion on how to select them. They are selected randomly here and one can see a huge variance in the performance.\n* The datasets are not explained. E.g., their dimensionality and rande of values. The discrete dataset contain some new parameters here but they are unexplained ($r_d, r_a, p_d, p_a..$)", "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 paper during the rebuttal period according to the rebuttal policy, and we therefore carefully describe all changes directly here in the rebuttal.\n\n### Concerning the technical contribution (Comment 1)\nPlease consider that our certificates hold under adversarial perturbations that are bounded by arbitrary $\\ell_p$-norms, unlike the result of Cohen et al., 2019 [1] that is limited to the $\\ell_2$-norm. So far there are no randomized smoothing certificates specifically designed against our threat model and we experimentally demonstrate that simply using previous works is not enough when considering the robustness-accuracy trade-off. Deriving new certificates against this threat model is technically challenging: One would have to propose a new smoothing distribution and prove robustness certificates for each possible $\\ell_p$-norm.\n\nAs the result of a rigorous theoretical proof, we can provide robustness certificates that are more modular and in fact orthogonal to all existing ones. With hierarchical smoothing we also obtain stronger guarantees compared to the baselines. We believe that this is a sufficient contribution to the scientific community since it not only impacts the community of machine learning on graphs but also the (certifiable) robustness community in general.\n\n### Concerning theoretical claims (Comment 2)\nThank you for pointing out potential for using a more precise formulation in Section 4. In response to your comment, we carefully went over all theoretical statements to ensure their quality and further improve their clarity.\n\nSpecifically, we clarified the statement regarding fixed $\\tilde{\\mathbf{X}}$ and a fix distance $r$ and rewrote Section 4 as follows: We first derive the NP-lower bound for a fixed point in the entire ball, yielding a point-wise certificate. Then we introduce guarantees against the entire threat model by including an additional proposition stating that the minimum of Theorem 1 (line 174) is assumed when exactly $r$ rows are perturbed (and not less). To see this note that $\\Delta=1-p^{|\\mathcal{C}|}$ is strictly monotonically increasing in the number of perturbed rows $|\\mathcal{C}|$ for $p\\in(0,1)$. We agree that this argument was missing, and we therefore fixed the corresponding parts. Thank you for helping us to further improve the clarity of our theoretical claims.\n\nPlease further note that Corollary 1 is already correct and assumes any perturbed $\\tilde{X}$ in the ball (line 207). \n\n\n### Concerning the exposition (Comment 3)\nThank you for helping us to further improve the exposition of our paper. In response to your comment, we simplified the explanations of the regions in Section 4 and additionally provide a Figure for clarification (see Figure 1 in the rebuttal PDF and also our response to reviewer 7yDS). Following your suggestion, we will also include pseudocode in the camera-ready version to further improve the clarity of our methodology.\n\n### Concerning parameters of the smoothing distribution (Comment 4)\nThe randomized smoothing framework already introduces parameters of the smoothing distribution as hyperparameters (see e.g. [1]). In general, increasing the probabilities to add noise increases the robustness guarantees but also decreases the accuracy. We introduce an additional parameter allowing to better control the robustness-accuracy trade-off. \n\nAs you correctly pointed out, in our exhaustive experiments we randomly explore the entire space of possible parameter combinations. The reason for this is to demonstrate Pareto-optimality, i.e. to find all ranges for which we can offer both better robustness and accuracy. In practice one would have to conduct significantly less experiments to find suitable parameters. Please also consider that the task of efficiently finding the optimal parameters is a research direction orthogonal to deriving robustness certificates.\n\n### Concerning further explanations (Comment 5)\nPlease note that we thoroughly describe the graph datasets including number of nodes, edges and the feature dimensionality in lines 256-261 (Section 6). For experiments on discrete data we carefully introduce $r_d, r_a, p_d, p_a$ in lines 275-284 (Section 6) and we also elaborate on this in Appendix B.\n\nWe hope that we could address all your questions to your satisfaction. Please let us know if you have any additional comments or questions.\n\n### References\n[1] Jeremy M. Cohen, Elan Rosenfeld, J. Zico Kolter. Certified Adversarial Robustness via Randomized Smoothing. ICML 2019."}]

Author rebuttal:
We would like to thank all reviewers for their valuable feedback.

Please note that we cannot update the paper during the rebuttal period according to the rebuttal policy, and we therefore carefully describe all revisions directly in the rebuttals. In the rebuttal PDF we further include a Figure as clarification of the regions and propositions as suggested by the reviewers (see PDF attached).

Meta-review: I have thoroughly read the reviews, rebuttals, and subsequent discussions. The paper has received generally positive initial scores, and it's encouraging to note that several reviewers have further improved their evaluations after considering the rebuttal.

The paper introduces a novel approach that addresses a new type of attacks on structured data, such as graphs. The theoretical results, while potentially having limitations in their applicability, generalize existing randomized smoothing (RS) certificates for when a subset of size "r" of the nodes is perturbed (each node with a probability of perturbation = p). The certificates are now more general and function of both p and r. It would be intriguing to explore an extension of this work for scenarios where the adversary can perturb at most "r" nodes, as opposed to exactly "r" nodes. This aligns more closely with realistic attack scenarios, where one knows a maximum adversarial budget rather than the exact adversarial budget.

Nonetheless, the contributions and experiments presented in the paper are robust and well-founded. Based on my evaluation, I recommend accepting the paper, in alignment with the sentiments of all reviewers.
Decision: Accept (poster)