Collective Robustness Certificates: Exploiting Interdependence in Graph Neural Networks
Authors: Jan Schuchardt
Aleksandar Bojchevski
Johannes Gasteiger
Stephan Günnemann
Venue: ICLR 2021 Poster (2021)
Keywords: Robustness certificates
Adversarial robustness
Graph neural networks

Abstract: In tasks like node classification, image segmentation, and named-entity recognition we have a classifier that simultaneously outputs multiple predictions (a vector of labels) based on a single input, i.e. a single graph, image, or document respectively. Existing adversarial robustness certificates consider each prediction independently and are thus overly pessimistic for such tasks. They implicitly assume that an adversary can use different perturbed inputs to attack different predictions, ignoring the fact that we have a single shared input. We propose the first collective robustness certificate which computes the number of predictions that are simultaneously guaranteed to remain stable under perturbation, i.e. cannot be attacked. We focus on Graph Neural Networks and leverage their locality property - perturbations only affect the predictions in a close neighborhood - to fuse multiple single-node certificates into a drastically stronger collective certificate. For example, on the Citeseer dataset our collective certificate for node classification increases the average number of certifiable feature perturbations from $7$ to $351$.


Published as a conference paper at ICLR 2021
COLLECTIVE ROBUSTNESS CERTIFICATES: EXPLOITING INTERDEPENDENCE IN GRAPH NEURAL NETWORKS
Jan Schuchardt, Aleksandar Bojchevski, Johannes Gasteiger & Stephan Günnemann Technical University of Munich, Germany {jan. schuchardt, bojchevs, j. gasteiger, guennemanneeennnn uum de
ABSTRACT
In tasks like node classification, image segmentation, and named-entity recogni- tion we have classifier that simultaneously outputs multiple predictions (a vector of labels) based on a single input, i.e. a single graph, image, or document respec- tively. Existing adversarial robustness certificates consider each prediction inde- pendently and are thus overly pessimistic for such tasks. They implicitly assume that an adversary can use different perturbed inputs to attack different predictions, ignoring the fact that we have single shared input. We propose the first col- lective robustness certificate which computes the number of predictions that are simultaneously guaranteed to remain stable under perturbation, i.e. cannot be at- tacked. We focus on Graph Neural Networks and leverage their locality property perturbations only affect the predictions in a close neighborhood to fuse mul- tiple single-node certificates into a drastically stronger collective certificate. For example, the Citeseer dataset collective certificate for node classification increases the average number of certifiable feature perturbations from 7 to 351.
INTRODUCTION
Most classifiers are vulnerable adversarial attacks (Akhtar & Mian 2018 Hao-Chen al. 2020). Slight perturbations of the data are often sufficient to manipulate their predictions. Even in scenarios where attackers are not present it is critical ensure that models are robust since data can noisy, incomplete, or anomalous. We study classifiers that collectively output many predictions based single input. This includes node classification, link prediction, molecular property prediction, image segmentation, sart-of-speecle tagging, named-entity recognition, and many other tasks.
Various techniques have been proposed to improve the adversarial robustness of such models. One example is adversarial training (Goodtellow et al. 2015). which has been applied to part-of-speech
tagging (Han et al. 2020), semantic segmentation (Xu et al.) 2020b) and node classification (Feng et al. 2019). Graph-relate tasks in particular have spawned rich assortment of techniques. These
include Bayesian models (Feng et al. 20220), data-augmentation methods (Entezari et al. (020) and
various robust network architectures (Zhu al. 2019 Geisler al., 2020). There are also robust loss functions which either explicitly model an adversary trying to cause misclassifications (Zhou & Vorobeychik, 2020) or use regularization terms derived from robustness certificates (Zügner &
Günnemann 2019). Other methods try to detect adversarially perturbed graphs (Zhang et al. 2019 Xu et al. 2020a) or directly correct perturbations using generative models (Zhang & 2020).
However, none of these techniques provide guarantees and they can only be evaluated based on their ability to defend against known adversarial attacks. Once a technique subsequently be defeated using novel attacks (Carlini & Wagner 2017). We are therefore interested deriving adversarial robustness certificates which provably guarantee that a model is robust.
established, it may
In this work we focus node classification/ Here, the goal is to assign a label to each node in single (attributed) graph. Node classification can be the target of either local or global adversarial attacks. Local attacks, such Nettack (Zügner et al. 2018 Zügner et al. 2020), attempt to alter the
While we focus on node classification, our approach can easily be applied other multi-output classifiers.

---

Published as a conference paper at ICLR 2021
attacked edges
collectively robust
mutually exclusive
Esz Ba
e
Ese
each
1
2/3
1/2
encodes
1
2/2
X
the receptive 1
receptive
0/3
field
field
1/2
a nade
1/1
X
individual
callective
allocated
min. required
Figure 1: Previous certificates consider each node independently. Most nodes cannot be certified since the adversary can choose a different perturbed graph per node (left). This is impossible in prac- tice due to mutually exclusive perturbations. Our collective certificate enforces single perturbed graph (center). aggregates the amount of perturbation within each receptive field and then evalu- ates a single-node certificate to determine whether the corresponding prediction is robust (right).
prediction of a particular node in the graph. Global attacks, as proposed by Zügner Günnemann (2019), attempt to alter the predictions of many nodes at once. With global attacks, the attacker is constrained by the fact that all predictions are based on a single shared imput. To successfully attack some nodes the attacker might need to insert certain edges in the graph, while for another set of nodes the same edges must not be inserted. With such mutually exclusive adversarial perturbations, the attacker is forced to make choice and can attack only one subset of nodes (see Fig.
Existing certificates (Zügner & Günnemann 2019 Bojchevski Günnemann 2019 Bojchevski al. 2020) are designed for local attacks, i.e. to certify the predictions of individual nodes. So far, there is no dedicated certificate for global attacks, iee. to certify the predictions of many nodes at once A naïve certificate for global attacks be constructed from existing single-node certifi- cates as follows: One simply certifies each node's prediction independently and counts how many guaranteed to be robust. This, however, implicitly assumes that adversary can different perturbed inputs to attack different predictions, ignoring the fact that we have single shared input.
We propose collective robustness certificate for global attacks that directly computes the number of simultaneously certifiable nodes for which we can guarantee that their predictions will not change. This certificate explicitly models that the attacker is limited a single shared input and thus accounts for the resulting mutual exclusivity of certain attacks. Specifically, we fuse multiple single-node certificates, which we refer as base certificates, into a drastically (and provably) stronger collective one. Our approach is independent of how the base certi firctiiates are derived, and any improvements to the base certificates directly translate to improvements to the collective certificate.
The key property which we exploit is locality. For example, in a k-layer message-passeen passing graph neu- ral network (Gilmer et al. 2017) the prediction for any given node depends only on the nodes in its k-hop neighborhood. Similarly the predicted segment for any pixel depends only on the pixels in its receptive field, and the named-entity assigned to any word only depends on words its surrounding.
For classifiers that satisfy locality perturbations to part of the graph do not affect all nodes. Adversaries are thus faced with a budget allocation problem: It might be possible to attack differ- ent subsets of nodes via perturbations to different subgraphs, but performing all perturbations at once could exceed their adversarial budget. The naive approach discussed above ignores this, over- estimating how many nodes be attacked. We design simple (mixed-inteed integer) linear program (LP) that enforces a single perturbed graph. It leverages locality by only considering the amount of perturbation within each receptive field when evaluating the single-node certificates (see Fig. l).
We evaluate our approach on different datasets and with different base certificates. We show that in- corporating locality alone is sufficient to obtain significantly better results. Our proposed certificate:
Is the first collective certificate that explicitly models simultaneous attacks on multiple outputs.
Fuses individual certificates into provably stronger certificate by explicitly modeling locality.
Is the first node classification certificate that model not only global and local budgets, but also the number of adversary-controlle nodes, regardless whether the base certificates support this.
Chiang et al. 2020) certify multi-object detection, but they still treat each detected object independently.
2

---

Published as a conference paper at ICLR 2021
2 PRELIMINARIES
Data and models. We define our unperturbed data as an attributed graph g = (X, E G with G = {0, 1)NxD> x (0, 1 1 consisting of N D-dimensional feature vectors and a directed N x N adjacency matrix. Each vertex is assigned one out of C' classes by multi-output classifier f G + (I....,) CJ.. In the following, fn (G) fn (x, A) = fn. refers to the prediction for node
Collective threat model. Unlike previous certificates, we model an adversary that aims to change multiple predictions at once. Let Bg C G be set of admissible perturbed graphs. Given clean graph g, the adversary tries to find a g E Bg that maximizes the number of misclassified nodes, L.e. Σner (0)) for some set of target nodes T C (1,....N).
Following prior work (Zügner& & Günneeaan 2019), , we constrain the set of admissible perturbed graphs Bg through global and (optionally) local constraints on the number of changed bits. Our global constraints are parameterized by scalars r'x I' aa 1' A'uda' T' Aaa E No. They are an upper limit on how many bits can be added (0- + 1) deleted + when perturbing X and A. Our
local constraints are parameterized by vectors "'aadd, P X' Y A'Aadd loc? H Aan lor. E No They are an upper limit on how many bits can be added or deleted per row of X and A, i.c. how much the attributes of a particular node can change and how many incident edges can be perturbed.
Often, it is reasonable assume that no adversary has direct control over the entire graph. Instead, realistic attacker should only be able to perturb a small (adaptively chosen) subset of nodes. To model this, we introduce an additional parameter E N. For all (X', A') E Bg, there must be a set of node such that for all d E {1, .I...., D) and n, E (1. (I.....AA N}:
indices S C
N] with [S]
(X,,d Xn.d = n E) A (A' + An.m = n E S m E
(I)
The set S is not fixed, but chosen by the adversary The resulting set Bg is formally defined in variable and the remaining parameters clear from
Section B If the global budget parameters the context, we treat Bg as function Bg N2 + P(G) that, given global budget parameters, returns the set of all perturbed graphs fulfilling the constraints.
Local predictions. Our certificate exploits the locality of predictions, i.e. the fact that predictions only based on subset of the input data. We characterize the receptive field of fn via indicator vector cb(n) {0, 1 corresponding to rows in attribute matrix X and an indicator matrix (n))) E
{o, NXN corresponding to entries in adjacency matrix A. For all (X', A") (X" AA) E Bg:
N
N
N
(n) 1x
LA A =0 = fa(X', A') = fn A") (2)
Eq. 2) enforces that as long as all nodes and edges for which (b(") = 1 or T (n) = remain unper- turbed, the prediction fn does not change. Put differently, changes to the rest of the data do not affect the prediction. Note that the adversary can alter receptive fields, e.g. add edges to enlarge them. To
capture all potential alterations, 2b()) and (") correspond to all data points that influence fn under some graph in Bg. i.c. the union of all receptive fields achievable under the threat model.
3 COMPACT REPRESENTATION OF BASE CERTIFICATES
Before deriving our collective certificate, we define a representation that allows us to efficiently evaluate base certificates. A base certificate any procedure that can provably guarantee that the prediction fn for a specific node n cannot be changed by any perturbed graph in an admissible set, such as sparsity-aware smoothing (Bojchevski
al., 2020). As you shall see the next section, our collective certificate requires evaluating base certificates for varying adversarial budgets within = [rxmall x |rxual x [r Aaal x [aa (with [k] {o...., k)),, the set of vectors that do not exceed the collective global budget.
A base certificate implicitly partitions L into set of budgets k(n) C L for which the prediction fx
is certifiably robust and its complement k() L K(n) with
(n)) C {p E No p DELAVI V(X A') E BB(() fa(x A) fx'' A')
(3)
Note that the adversary only needs to control one of the nodes incident to edge in order to perturb it. We do not associate different costs for perturbing different nodes edges, but such extension is straightforward.
3

---

Published as a conference paper at ICLR 2021
Note the subset relation. The set K(") does not have to contain all budgets for which fn is robust. Conversely, a certain budget vector p not being part of k(n) does not necessarily mean that fn can be attacked under threat model (p)(p) - its robustness merely unknown. We now make the following natural assumption about base certificates: If classifier is certifiably robust perturbations with large global budget, it should also be certifiably robust to perturbations with a smaller global budget.
vp E (((),, pp' EL: (vd E (1,2,3,4) Pa pal [p'E e R(a)
(4)
From geometric point of view, Eq. 4 means that the budgets IK for which the prediction fn is
certifiably robust form a singular enclosed volume around (0 0 0) within the larger volume L. Determining whether classifier is robust to perturbations in (p) is equivalent to determining
which side of the surface enclosing the volume K. the budget vector p lies on. This can be be done by evaluating linear inequalities, shown in the following.
First, let us assume that all but one of the budgets are zero, e.g. L [rx.el] x [0] x [0] x [0], with Eq. 4 there must be distinct value p.. Ng (the smallest uncertifiable budget)
Panda > 0. Due to
P1 2 Pn. Evaluating the base certificate can thus be performed by evaluating single inequality. This approach can be generalized to arbitrary types of perturbations. Instead of using single scalar Pn, we characterize the volume of budgets K(n) via the pareto front of points on its enclosing surface:
with Vp E L E Kin) +
p(n)_ {p E K(n) -3p's K(n), p' + PAAd E (1,,, 4) : Paa S Pa).
(5)
These points fulfill Vpp E L p Kin) uating the base certificate can be performed by evaluating P inequalities.
((p
3p E pP AA E (1, 3, 4) : pa 2 Ps) Here, eval-
In the following, we assume that we are directly given this pareto front (or the smallest uncertifiable budget). Finding the pareto front can be easily implemented via a flood-fill algorithm that identifies the surface of volume K("), followed by a thinning operation (for more details, see Section D
COLLECTIVE CERTIFICATE
To improve clarity in this section, we only discuss the global budget constraints. All remaining constraints from the threat model can be easily modelled as linear constraints. You can find the certificate for the full threat model in (Section C We first formalize the naive collective certificate described in the introduction, which implicitly allows the adversary to use different graphs to attack different predictions. We then derive the proposed collective certificate, first focusing on attribute additions before extending it to arbitrary perturbations. We relax the certificate to linear program to enable fast computation and show the certificate's 's tightness when using a randomized smoothing base certificate. We conclude by discussing the certificate's 's time complexity and limitations.
Naïve collective certificate. Assume we are given a clean input ( (X, A), a multi-output classifier f. a set T of target nodes and set of admissible perturbed graphs Bg fulfilling collective global budget constraints given by r xxaaa 7 Xaa Amaa A.a. Let L = [r xaxlaal I x [rx.a] X [r x [r Atal be the set of all vectors that that do not exceed the collective global budget. Further assume that the base certificate guarantees that each classifier fn is certifiable robust to perturbations within a set of budgets k(n) (see Eq. 3). As discussed, the na've certificate simply counts the predictions whose robustness to perturbations from Bg is guaranteed by the base certificate. Using the representation of base certificates introduced in Section 3) this can be expressed as Σner 1 [T<(i)) IL]. From the
definition of (K()) in Eq. 3. we can directly see that this is a lower bound on the optimal value of fa (A), i.c. the number of predictions guaranteed to be stable under attack. Note that each summand involves a different minimization problem, meaning the adversary may use different graph to attack each of the nodes.
ΣnEt xin E3, I (x,,
Collective certificate for attribute additions. To improve upon the naive certificate, we want to determine the number of predictions that are simultaneously robust to attacks with a single graph:
min A' NET
Σ
1 [f, A) fx(X'' AA))].
(6)
4

---

Published as a conference paper at ICLR 2021
Solving this problem is usually not tractable. For simplicity, let assume that the adversary is only allowed to perform attribute additions. As before, we can lower-bound the indicator functions using the base certificates:
11(0 Σ1
0 o 0)* T E K
min (X A EA) EBC
where b = E (n. x.. X nd is the number of attribute additions for a given perturbed graph. Since this certificate only depends on the number of perturbations, it is sufficient to optimize over the number of attribute additions while enforcing the global budget constraint:
Σ1 1 (b BENO WET
O O 0)" <K(n) s.t. 6 S "'xadd
min
There two limitations: (1) The certificate does not account for locality, but simply considers the number of perturbations in the entire graph. In this regard, is no different from the naïve collective certificate; (2) Evaluating the indicator functions, i.e. certifying the individual nodes, might involve complex optimization problems that are difficult to optimize through. We tackle (1) by evaluating the base certificates locally.
Lemma Assume multi-output classifier f. corresponding receptive field indicators ab(n) (0, 13 and (p()) E {0, 1JNNN and clean graph (X, A). Let Iiin) be the set of certifiable global budgets of prediction In. as defined in Eq. 3 Let (X', A') be perturbed graph. Define X" {0, ij and A" E (0,1]Nx0
XN follows:
X²aa = v. (m) X + (1 1/ )
(9)
A" = ! Al. + (1 - )
(10)
i.e. use values the clean graph for bits that are not in fn 's receptive field. If there exists a vector
of budgets p E Ng such that (X" A E Bg( and p IK ((("), then fa(X, A) = [x(X', A').
See proof in Section B Due to Lemma I we ignore all perturbations outside fa 's recep- tive field when evaluating its base certificate. We can thus replace (b 0 0) in Eq. 8 with
(bT (b 0 0)²² where the vector b E N& indicates the number of attribute additions at each node. Optimizing over b yields a collective certificate that accounts for locality:
E1((b (b Binn
s.t. [[b]] S T'xas" 0)² E K [(()
min BENO
0 0
(11)
NET
We now tackle issue (2) by employing the compact representation of base certificates defined in Section 3) Since we only allowing one type of perturbation, the base certificate of each classifier In is characterized by the smallest uncertifiable radius pn, (see Isee/Section 3p. To evaluate the indicator function in [q. 11 we simply have compare the number of perturbations in fu f.'s receptive field to Pa. which can be implemented via the following MILP:
min BENN 1EE
T
Σ tn
(12)
RET
s.t. 6t (n)
putn
Vn
E [1.....N}
(13)
|bا|| S T'..4"
(14)
Eq. 14Jensurs that the number of perturbations fulfills the global budget constraint. [Eq. 13 ensures that the indicator tn can only be set to if the local perturbation on the l.h.s. exceeds or matches Pns i.c. fn is not robustly certified by the base certificate. The adversary tries minimize the number of robustly certified predictions in T (see Eq. 8). which is equivalent to Eq. 12
Collective certificate for arbitrary perturbations, Lemma Tholds for arbitrary perturbations. We only have to consider the perturbations within prediction's ' receptive field when evaluating its base certificate. However, when multiple perturbation types are allowed, the base certificate of prediction fn not characterized by a scalar pr, but by its pareto front IP(x) (see 5j. Let p(x) Ni 1x1 be matrix encoding of the set Tp(n), To determine if fn is robust
check whether
5

---

Published as a conference paper at ICLR 2021
there is some pareto-optimal point p(()) such that the amount of perturbation in fu's receptive field matches or exceeds P.: in all four dimensions. This can again be expressed as a MILP (see Eq. 15 to Eq. 23 below).
As before, we use vector t with L, = 1 indicating that fn is not certified by the base certificate. The adversary tries to find a budget allocation (parameterized by bx add bx del and B that minimizes the number of robustly certified predictions in (see Eq. 15 Eq. 20 and Eq. 21 ensure that the budget allocation is consistent with the global budget parameters characterizing Bg. The value of I, is determined by the following constraints: First, Eq. 17 Eq. 19 ensure that Qu1) p.d is only set to 1 if the local perturbation matches exceeds the pareto-optumal point corresponding row p of p(n) in dimension d. The constraints in Eq. 16 implement logic operations Q (n); Indicator Sp can only be set to 1 if Vd E (1,2,3,4] 4} 0 = 1. Indicator in can only be set to
(n)
Bp E {I,..., [,,(()(())) : sp = 1. Combined, these constraints enforce that if tn = 1, there must be some point p(r) that exceeded or matched by the amount of perturbation in all four dimensions.
min (Q()), "x-1.xant bx
[T]
Σ tn
(15)
Ba.t
NET
s.t. ||s(")|11 2 tn
(()
2 (n) ndd
(16)
(bxand) T 2 Q. p.1:
p(x)
(bxIn)
T *bb(n)
2 2 (n) p(n)
p.2 p.2:
(17)
Σ (1 Am,mn ) (w)( 2 BAdm. 2 2 (n) p(n)
(18)
p.3
m,m's SN
Am,m (m)()) @ BB.mm, 2 200 p!n) S
Σ
pd
(19)
bbxmaal|| S Sxxaaa
|bx 11 S raxa
20
Σ
BAi S A'Adda
Σ
BAis S T'aa
(21)
(6,))A
(
(1) E 13 1iin
Q(1) E (0. (3.
tE 10,1)
(22)
bx bxnda bxaa
E NN
BA 10,1)NXN.
(23)
LP-relaxation. For large graphs, finding an optimum to the mixed mixed-integer problem is prohibitively expensive. In practice, we relax integer variables to reals and binary variables to [0, 1]. Semantically, the relaxation means that bits can be partially perturbed, nodes can be partially controlled by the
attacker and classifiers can be partially uncertified (i.e. 1 > In > 0). The relaxation yields linear program, which can be solved much faster.
Tightness for randomized smoothing. One recent method for robustness certification is random- ized smoothing (Cohen et al. 2019). In randomized smoothing, a (potentially non-deterministic) base classifier h : X - Y that maps from some input space X to a set of labels Y is transformed into a smoothed classifier g(x) with g(z) = argmax,ey pev Pr [h(((()) = yl. where ((x) is some randomization scheme parameterized by input x. For the smoothed g(x) we can then derive proba- bilistic robustness certificates. Randomized smoothing is black-hox method that only depends on h's expected output behavior under ((x) and does not require any further assumptions. Building on prior randomized smoothing work for discrete data by Lee et al. (2019), BBojcheski al. (2020) propose a smoothing distribution and corresponding certificate for graphs. Using their method as base certificate to our collective certificate, the resulting (non-relaxed) certificate is tight. That is, our mixed-intee inteeer collective certificate is the best certificate we can obtain for the specified threat model, if we do not use any information other than the classifier's expected predictions and their locality. Detailed explanation and proof in Section E
Time complexity, For our method we need to construct the pareto fronts corresponding to each prediction's 's base certificate. This has to be performed only once and the results can then be reused in evaluating the collective certificate with varying parameters. We discuss the details of this pre- processing in Section D The complexity of the collective certificate is based on the number of
constraints and variables of the underlying (MI)LP. In total, we have 13 ΣN [IP(X) | 8N + 2e +

---

Published as a conference paper at ICLR 2021
N constraints and 5 n= +4N+ variables, where are the number of edges in the unperturbed graph (we disallow edge additions). For single-type perturbations we have ONN + e) terms, linear in the number of nodes and edges. The relaxed LP takes most few seconds to certify robustness for single-type perturbations and a few minutes for multiple types of perturbations (see [Section 5).
Limitations. The proposed approach is designed to exploit locality. Without locality, it is equivalent to a naïve combination of base certificates that sums over perturbations in the entire graph. A non- obvious limitation that our notion of locality breaks down if the receptive fields are data-dependent and can be arbitrarily extended by the adversary. Recall how we specified locality in Eq. 2 The indicators v6(*) and [n()) correspond to the union of all achievable receptive fields. Take for example two-layer cessage-passing neural networks and an adversary that can add new edges. Each node is classified based on its 2-hop neighborhood. For any two nodes n. m, the adversary can construct graph such that vn in fn receptive field. We thus have to treat the fn as global, even if for any single graph they might only process some subgraph. Nonetheless, our method still yields significant improvements for edge deletions and arbitrary attribute perturbations. As discussed in prior work Zügner & Günnemann] 2020) edge addition is inherently harder and less relevant in practice.
EXPERIMENTAL EVALUATION
Experimental setup. We evaluate the proposed approach by certifying node classifiers on multi- ple graphs and with different base certificates. We use 20 nodes per class to construct a train and a validation set. We certify all remaining nodes. We repeat each experiment five times with dif- ferent random initializations and data splits. Unless otherwise specified, we do not impose any lo- cal budget constraints or constraints on the number of attacker staacker-contollldd nodes. We compare the proposed method with the naive collective certificate, which simply counts the number of predic- tions that are certified to be robust by the base certificate. All experiments are based on the relaxed linear programming version of the certificate. We assess the integrality gap to the mixed-integer version in Section A The code is publicly available under htt : / www. daml. in. tum. de co collecti vee- www.ouussteesseooooo / We also uploaded the implementation as supplementary material.
Datasets, models and base certificates. We train and certify models on the following datasets: Cora-ML (McCallum et al.] (2000); BBojcheskii & Günnemann| (2018); N 2810, 7981 edges, 7 classes), Citeseer (Sen et al. (2008); N 2110, 3668 edges, 6 classes), PubMed (Namata et al. 862, 2586 edges, classes) and
2011 N = 19717, 44324 edges, 3 classes), Reuters-21578 (N (N W (Craven et al. (1998); N 877, 2631 edges, 5 el classes). The graphs for the natural language corpora Reuters and WebKB are constructed using the procedure described in Zhou & Vorobeychik 2020)) resulting in 3 3-regular graphs. We use five types of classifiers: Graph convolution networks
(GCN) (Kipf & Welling 2017), graph attention networks (GAT) (Veličković et al. 2018), APPNP (Gatteiger et al.]9 robust graph convolution networks (RGCN) (Zhu et al. medoid aggregation networks (SMA) (Geisler et al., 2020). All classifiers are configured to have two layers, i.e. each node's classifier is dependent on its two-hop neighborhood. We use two types of base certificates: (Bojchevski et al. 2020) (randomized smoothing, arbitrary perturbations) and Zügner& & Günnemann (2019) (convex relaxations of network nonlincarities, attribute perturbations). We provide a summary of all hyperparameters in [Section F
2019) and soft
Evaluation metrics. We report the certified ratio on the test set, i.e. the percentage of nodes that are certifiably robust under a given threat model, averaged over all data splits. We further calculate the standard sample deviation certified ratio (visualized as shaded areas plots) and the average wall- clock time per collective certificate. For experiments in which only one global budget parameter is altered, we report the average certifiable radius, i.e. F = (Er= w(r) * r/ En=n w(r)). where w()) is the certified ratio for value r of the global budget parameter, averaged over all splits.
Attribute perturbations. We first evaluate the certificate for a single perturbation type. Using ran- domized smoothing as the base certificate, we evaluate the certified ratio of GCN classifiers for varying global attribute deletion budgets r T',,. on the citation graphs Cora, Citeseer and PubMed (for Reuters and WebKB, see [Section A). The remaining global budget parameters Fig. shswo that for all datasets, the proposed method yields significantly larger certified ratios than the naive certificate and can certify robustness for much larger Xx.a The average certifiable radius
set O.
Distribuutin 1.0, available from http://www..iiiiii.oooooeeeeeees

---

Published as a conference paper at ICLR 2021
1.0
25
Certified ratio
0.8
Edge deletions
20
Our Naive
0.8
0.6
15
0.4
Cora
10
Citeseer
50%
0.4
0.2
Pubmed
70%
0.0
0.2
100
10
10a
103
10
30
40
Attribute deletions
Attribute deletions
Figure 2: Certified ratios for smoothed GCN
Figure Two-dimensional colective certificate for smoothed GCN on Cora-ML under varying TX and ''A.:. The solid and dotted contour lines show ratios 2 0.5 and 2 0.7 for our vs. the naïve certificate respectively. Our method achieves much larger certified ratios and radii.
Cora, Citeseer and PubMed, under varying r "Xaa"" We compare the proposed certificate (solid lines) to the naïve certificate (dotted lines). Our method certifies orders of magnitude larger radii (note the logarithmic x-axis).
1.0
1.0
Our certificate
Certified ratio
0.8
Certified ratio
0.8
Naive certificate
0.4
GAT
0.4
GCN
0.2
0.2
APPNP
0.0
0.0
0
5
10
15
20
0
200
400
600
800
1000
Attribute deletions
Attribute additions
Figure 4: Comparison of certified ratios for GAT, GCN and APPNP on Cora-ML under varying Txaa for our (solid lines) and the naive (dotted lines) collective certificate.
Figure 5: Certifying GCN on Citeseer, un- der varying TX.aa using Zügner & Günnemann (2019)'s base certificate. Our certificate yields significantly larger certified ratios and radii.
on Citeseer increases from 7.18 to 33..73. The results demonstrate the benefit of using the collective certificate, which explicitly models simultaneous attacks on all predictions. The average wall-clock time per certificate on Cora, Citeseer and PubMed is 2.0s, 0.29 and 336.41 s. Interestingly, the base certificate yields the highest certifiable ratios on Cora, while the collective certificate yields the highest certifiable ratios PubMed. We attribute this differences in graph structure, which are explicitly taken into account by the proposed certification procedure.
Simultaneous attribute and graph perturbations. To evaluate the the certificate, we visualize the certified ratio of randomly smoothed GCN classifiers for different combinations of T'aa and T'ais Cora-ML. For additional experiment simultancous at- tribute additions and deletions, see Section A Fig. 3/shows that we achieve high certified ratios even when the attacker is allowed to perturb both the attributes and the structure. Comparing the contour lines at 50 % the naïve certiface can only certify much smaller radii, e.g. at most 6 attribute deletions compared to 39 for our approach. The average wall-clock time per certificate is 106.90
version of
Different classifiers. Our method is agnostic towards classifier architectures, as long as they are compatible with the base certificate and their receptive fields can be determined. Iniig we com- pare the certified collective robustness of GAT, GCN, and APPNP, using the sparse smoothing cer- tificate on Cora-MI_ Better base certificates translate into better collective certificates. For addi- tional experiment on the benefits of robust classifier architectures RGCN and SMA, SectSontion A
*Our method certify larger radii, 10 (see Fig. 2 Here show < 20 to highlight the difference.
8

---

Published as a conference paper at ICLR 2021
1.0
1.0
Local budget
Att. nodes
Certified ratio
0.8
Certified ratio
0.8
0.6
0.6
2
0.4
0.4
16
32
0.2
0.2
16
0.0
0.0
200
600
1000
400
600
800
1000
Edge deletions
Edge deletions
Figure 6: Certified ratios for smoothed GCN
Figure 7: Certified ratios for smoothed GCN on Cora-ML. We vary T' and a. The certified ra- tios remain constant and non-zero for large l'Aaal-
on Cora-ML, under varying T Te and d'ddel tos" Stricter local budgets yield larger certified ratios.
Different base certificates. Our method is also agnostic to the base certificate type. We show that it works equally well with base certificates other than randomized smoothing. Specifically, we use the method from Zügner&& & Günnemann (2019). We certify GCN model for varying r'xaac Cite- seer. Unlike randomized smoothing, this base certificate models local budget constraints. Using the default in the base certificate's 's reference implementation, we limit the number of attribute additions per node to [0.01D] 21 for both the base and the collective certificate. Fig. 5 shows that the pro- posed collective certificate is again significantly stronger. The average certified radius & increases from 17.12 to 971.36. The average wall-clock time per certificate is 0.39
Local constraints. We evaluate the effect of additional constraints in our threat model. We can enforce local budget constraints and limit the number of attacker-controlled nodes, even if they are not explicitly modeled by the base certificate. In Fig. 6] we use a smoothed GCN on Cora-ML. and vary both the global budget for edge deletions, "' and the local budgets r ''acitoo" Even though the base certificate does not support local budget constraints, reducing the number of admissible deletions per node increases the certified ratio as expected. For example, limiting the adversary to one deletion per node more than doubles the certified ratio at r r'iii 1000. In Fig. 7, we fix a relatively large local budget of 16 edge deletions per node (only ~ 5% of nodes on Cora-ML have a degree > 16) and vary the number of attacker-controlled nodes. We see that for any given number of attacker nodes, there is some point ('Aae after which the certified ratio curve becomes constant. This constant value is an an upper limit on the number of classifiers that can be attacked with a given local budget and number of altaccer-conttrlleed nodes. It independent of the global budget.
CONCLUSION
We propose the first collective robustness certificate. Assuming predictions based on a single shared input, we leverage the fact that an adversary must use single adversarial example to attack all predictions. We focus on Graph Neural Networks, whose locality guarantees that perturbations to the input graph only affect predictions in a close neighborhood. The proposed method combines many weak base certificates into provably stronger collective certificate. It is agnostic towards network architectures and base certification procedures. We evaluate it on multiple semi-supervised node classification datasets with different classifier architectures and base certificates. Our empirical results show that the proposed collective approach yields much stronger certificates than existing methods, which assume that an adversary can attack predictions independently with different graphs.
7 ACKNOWIFDDGMMENTS
This research was supported by the German Research Foundation, Emmy Noether grant GU 1409/2- 1, the German Federal Ministry of Education and Research (BMBF), grant 011$18036B, and the TUM International Graduate School of Science and Engineering (IGSSE), GSC 81.

---

Published as a conference paper at ICLR 2021
REFERENCES
Naveed Akhtar and Ajmal Mian. Threat of adversarial attacks on deep learning in computer vision: A survey. IEEE Access, 6:44400-4440, 2018
Aleksandar Bojchevski and Stephan Günnemann. Deep gaussian embedding of graphs: Unsuper- vised inductive learning via ranking. In International Conference on Learning Representations, 2018.
Aleksandar Bojchevski and Stephan Günnemann. Certifiable robustness to graph perturbations. In Advances in Neural Information Processing Systems, volume 32, pp. 8319-8330, 2019.
Aleksandar Bojchevski, Johannes Gasteiger, and Stephan Günnemann. Efficient robustness certifi- cates for discrete data: Sparsity-awand randomized smoothing for graphs, images and more. In Proceedings of the 37th International Conference Machine Learning, volume 119 of Proceed- ings of Machine Learning Research, pp. 1003-1013,200 2020.
Nicholas Carlini and David Wagner. Adversarial examples are not easily detected: Bypassing ten detection methods. Workshop on Artificial Intelligence and Security, AlSec, 2017.
Ping-yeh Chiang, Michael J. Curry, Ahmed Abdelkader, Aounon Kumar, John Dickerson, and Tom Goldstein. Detection as regression: Certified object detection by median smoothing, In Advances in Neural Information Processing Systems, volume 33, pp. 1275-1286, 2020.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 1310-1320, 2019.
Mark Craven, Dan DiPasquo, Dayne Freitag, Andrew McCallum, Tom Mitchell, Kamal Nigam, and Seán Slattery. Learning to extract symbolic knowledge from the world wide web. In Proceedings of the Fifleenth National/Tenth Conference on Artificial Inteliggnce/lmnovatiee Applications of Artificial Intelligence, AAAI '98/IAAI '98, pp. 509-516. American Association for Artificial Intelligence, 1998.
Negin Entezari, Saba A. Al-Sayouri, Amirali Darvishzadeh, and Evangelos E. Papalexakis. All you need is low (rank): Defending against adversarial attacks on graphs. In Proceedings of the 13th International Conference on Web Search and Data Mining, pp. 169-177, 2020.
Boyuan Feng, Yuke Wang, Zheng Wang, and Yufei Ding. Uncertainty- attention graph neural network for defending adversarial attacks. arXiv preprint arXiv:2009. 10235, 2020.
Fuli Feng, Xiangnan He, Jie Tang, and Tat-Seng Chua. Graph adversarial training: Dynamically regularizing based on graph structure. IEEE Transactions Knowledge and Data Engineering, 2019.
Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In International Conference Learning Representations, 2019.
Simon Geisler, Daniel Zügner, and Stephan Günnemann. Reliable graph neural networks via robust aggregation. In Advances in Neural Information Processing Systems, volume 33, pp. 13272- 13284, 2020.
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 1263-1272 2017.
Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In International Conference Learning Representations, 2015.
Wenjuan Han, Liwen Zhang, Yong Jiang, and Kewei Tu. Adversarial attack and defense of structured prediction models. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 2327-2338, 2020.
10

---

Published as a conference paper at ICLR 2021
Han Xu Yao Ma Hao-Chen, Liu Debayan Deb, Hui Liu Ji-Liang Tang Anil, and K. Jain. Adversarial attacks and defenses in images, graphs and text: A review. International Journal of Automation and Computing, 1 17(2):151-178, 2020.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In International Conference on Learning Representations, 2017.
Gu Lee, Yang Yuan, Shiyu Chang, and Tommi Jaakkola. Tight certificates of adversarial robustness for randomly smoothed classifiers. In Advances in Neural Information Processing Systems 32, pp. 4910-4921. Curran Associates, Inc., 2019.
Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 3(2):127-163, 2000.
Galileo Mark Namata, Ben London, Lise Getoor, and Bert Huang. Query-driven active surveying for collective classification. In Workshop on Mining and Learning with Graphs, 2012.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification network data. Al Magazine, 29(3):33, 2008
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. In International Conference Learning Representations, 2018.
X Xu, Y Yu, L Song, Ciu, B Kailkhura, C Gunter, and B Li. Edog: Adversarial edge detection for graph neural networks. Technical report, Lawrence Livermore National (LLN,,, Livermore, CA (United States), 2020a.
Xiaogang Xu, Hengshuang Zhao, and Jiaya Jia. Dynamic divide-and-conquer adversarial training for robust semantic segmentation. arXiv preprint arXiv:2003.0655 066555, 2020b.
Ao Zhang and Jinwen Ma. Defensevgae: Defending against adversarial attacks on graph data via a variational graph autoencoder. arXiv preprint arXiv:2006.08900 2020.
Yingxue Zhang, Sakif Hossain Khan, and Mark Coates. Comparing and detecting adversarial tacks for graph deep learning. In Representation Learning on Graphs and Manifolds Workshop, International Conference on Learning Representations, 2019.
Kai Zhou and Yevgeniy Vorobeychik. Robust collective classification against structural attacks. In Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI), volume 124 of Proceedings of Machine Learning Research, pp. 250-259, 2020.
Dingyuan Zhu, Ziwei Zhang, Peng Cui, and Wenwu Zhu. Robust graph convolutional networks against adversarial attacks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1399-1407,2011
Daniel Zügner and Stephan Günnemann. Certifiable robustness and robust training for graph con- volutional networks. 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 of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1656-1665, 2020.
Daniel Zügner, Amir Akbarnejad, and Stephan Günnemann. Adversarial attacks neural networks for graph data. In Proceedings the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 2847-2856. 2018
Daniel Zügner, Oliver Borchert, Amir Akbarnejad, and Stephan Günnemann. Adversarial attacks on graph neural networks: Perturbations and their patterns. ACM Transactions on Knowledge Discovery from Data, 14(5), 2020.
11

---

Published as a conference paper at ICLR 2021
A ADDITIONAL EXPERIMENTS
Robust architectures. Our comparison of different standard classifier architectures demonstrated that the proposed collective certificate is Serhiteecture-gnostte and that better base certificates trans- late into better collective certificates. In Fig. 8 we assess the benefit of using SMA and RGCN, both of which are robust architectures meant to improve adversarial robustness. We use GCN as baseline for comparison and evaluate the respective certified ratios for varying attribute deletion budgets on Cora-MI. While RGCN supposed to be more robust to adversarial attacks, it has lower certified ratio than GCN. Soft medoid aggregation Its base certificate is almost as strong as the collective certificate of RGCN. Its collective certified ratio XX
the other hand has significantly higher certified ratio.
21 is 88.3%, compared to the 76.9% and 74% of GCN and RGCN.
1.0
1.0
Certified ratio
0.8
Certified ratio
0.8
0.6
0.6
0.4
SMA
0.4
GCN
WebKB
0.2
RGCN
Reuters
0.0
0.0
10
15
20
100
10a
10a
10a
Attribute deletions
Attribute deletions
Figure 8: Certified ratios for smoothed GCN, RGCN and soft medoid aggregation on Cora-ML. under varying r ax for our (solid lines) and the naïve (dotted lines) collective certificate.
Figure Certified ratios for smoothed GCN on WebKB and Reuters-21578, under varying Xxas for our (solid lines) and the naïve (dotted lines) collective certificate.
Attribute perturbations on additional datasets. In addition to citation graphs, we also use graphs constructed from the Reuters-2155 -25578 and WebKB natural language corpora evaluate the proposed certificate. As in the main experiments section, we use randomized smoothing base certificate for GCN classifiers and assess the certified ratio for varying global attribute deletion budgets. Fig. shows that the certified ratio increases and that much larger ''xaa (up to approximately 10²) can be certified when using the collective approach. The average certifiable radius for Reuters and WebKB increases from 6.54 and 8.08 to 265.62 and 309.32, respectively. With less than 900 nodes each, both datasets are smaller than our three citation graphs. This leads to even shorter average wall- clock times per certificate: 0.105 and 0.116s.
Simultaneous attribute deletions and additions. the main experiments section, we applied our collective certificate simultaneous certification of attribute and adjacency deletions. Here, we sess how it performs for simultaneous deletions and additions of attributes. We again use a randomly smoothed GCN classifier on Cora-ML, and perform collective certification for different combina- tions of T'aaa and TXa. on Cor As shown in Fig. 3) the collective certificate is again much stronger than the naive collective certificate. For example, we obtain certified ratios between 30% and 60% at radii for which the naïve collective certificate cannot certify any robustness at all. The average wall-clock time per certificate 40.51s.
Integrality gap. For all previous experiments, we used the relaxed linear programming version of the certificate to reduce the compute time. assess the integrality gap (i.e. the difference between the mixed-integer linear programming and the linear programming based certificates), we apply both versions of the certificate to a single smoothed GCN on Cora. We certify both robustness to attribute deletions (Fig. la and edge deletions (Fig. 1lb). The wall-clock time per certificate for the MILP increased from 0.24s to 64 with increasing edge deletion budget (0.35 to 9 for attribute deletions). Due to the exploding runtime for the MILP, we cannot compute the integrality gap for radii larger than 8 and 12, respectively The integrality gap is small (at most 4% for attribute deletions, 4.3% for edge deletions), relative the certified ratio, and appears be slightly increasing with increasing global budget.
As discussed the main paper the relaxed I.P fast and efficient solve, even for radii larger than 1000.
12

---

Published as a conference paper at ICLR 2021
Attribute additions
6
1.0
Attribute additions
1.00
5
4 5
0.75
0.8
5
3
0.50
2
1 2
1
0.6
0.25
0
0.00
4
10 12 16
4
10 16 20
Attribute deletions
Attribute deletions
(a) Proposed collective certificate
(b) Naive collective certificate
Figure 10: Comparison of the proposed collective certificate Fig. 10ap to the naïve collective cer- tificate (Fig. 10b) for certification of smoothed GCN on Cora-ML, under varying Xaa and T'aa"" Our method achieves much larger certified ratios for all combinations of attack radii.
1.0
1.0
Certified ratio
0.8
Certified ratio
0.6
0.6
0.4
0.4
MILP
MILP
0.2
0.2
LP
LP
0.0
6
8
Attribute deletions
Edge deletions
(a)
(b)
Certified ratios for smoothed GCN on Cora, under varying rX Fig. 11ab and Aam (iig. 11b), using the mixed mixed-integer collective certificate (blue line) and the relaxed linear programming certificate (orange line). The integrality gap small, relative to the certified ratio.
Figure 11:
B FORMAL DEFINITION OF THREAT MODEL PARAMETERS AND PROOFS
Here we define formally the of admissible perturbed graphs Bg described in(Section Recall that we have an unperturbed graph (X, A) E G, global budget parameters xaaa I'Xaa ''Aaa A'aa E No. local budget parameters TX loe P'X loo P 3 Aaeettto E N and at most a adversary- controlled nodes. Given these parameters, the set of admissible perturbed graphs Bgg is defined as follows:
(X', Bg
H(n,d) Xn,d 0 Xh,a} < rx A (n, :Xn,d * X/,d} $ T'
(((,m) An.m + Al.mm S TAras
m)) An, 1 + A/,m) S &'Aail
^ (Vn (I,...,
[d: Xn,d = + X x S S F too A ((d: XX,d = + X x²
(24)
A {m Anm = =0 X } S SAAddd,oo A f/m: An, 1 X" n.m }
$ ('Agelloom
A( IS C [1, SoAVdE {1,... D) n,m E (I....,
(Xh,d Xn,d n E) A (Anmm Anm nESVmES)
Next, show the proof of Lemma delegated from the main paper.
13

---

Published as a conference paper at ICLR 2021
Proof: By the definition of receptive fields (Eq. changes outside the receptive field do not influence the prediction, i.e. Jn X A') = [n A"). Since (X", AA) E BB(p)) and p E (((), we know that Jn X A)
= fa x" A.). By transitivity (x, A) = Jn A m.
C FULL COLLECTIVE CERTIFICATE
Here we discuss how to incorporate local budget constraints and constraints on the number of attacker-controlled nodes into the collective certificate for global budget constraints (see Eq. 15 We also discuss how to adapt it to undirected adjacency matrices (see Sectionio C.T As before, we lower-bound the true objective
min A')BB NET
[)) = fx ,
(25)
(X'
by replacing the indicator functions with evaluations of the corresponding base certificates and opti- mizing over the number of perturbations per node / the perturbed edges. The only difference that more constraints are imposed on 18g.
The derivation proceeds as before: Lemma 1 still holds, meaning we only have to consider pertur- bations within fn's 's receptive field in evaluating whether its robustness is guaranteed by the base certificate. The base certificates can be efficiently evaluated by comparing the perturbation within fa 's receptive field to all points in the pareto front [(x)) characterizing the volume of budgets K(*)
After encoding p(r) matrix p(x) (x((())x
we can solve the following optimization problem
to obtain a lower bound on Eq. 25
min (Q()), W bxnds Axan Batt
|T]
Σ tn
(26)
nET
s.t. ||8(00|1 2 las
(n)
p.d 2 (
(27)
(bxnaa) T Tabin) 2 (, p(x)
(bxua) ) (b((n)
2 0 (())
p.l
p.2
(28)
Σ (1 Am. (TD(") )
@ Ba)m, 2 p.3 p.3
(n) p(n)
(29)
m.m'SN
Σ
Am, (m) + BA)m, 2 2ur p(n) p.
(30)
M
||bxmna
ll1 TXaaa:
1ibxmall1 S 8Xan
(31)
BAi S A'dda
Σ
BAi S A
(32)
(b.j):A..,
(1,))A1,;=1
bxisan S annT AnddXaddloon
bxaan S ann "aalloon
(33)
Σ
BAn.m + BAm,n S "'aed,
Σ
BAn,m + BAm,n S A'adlooo
(34)
miAa. 0
m:An.
Baysa+on Vi,j E NJ.
(35)
||a/| 5a,
(36)
(11) E 10
Q(n) E {0, 1) (),1)/mm)/x4
(0,1) B E 10,1
(37)
a (0,1
bx bxas E NW
(38)
Vn E (1,...,NI,P E (1..... PPO d (1,
The constraints from Eq. 27 to Eq. 30 are identical to constraints Eq. 16 to Eq. 19 of our collective certificate for global budget constraints. They simply implement boolean logic to determine whether there is some pareto-optimal p E IP(n) such that the perturbation in fn receptive field matches or exceeds p in all four dimensions. If this is the case, the base certificate cannot certify the robustness of fn and t, can be set to 1. 1. and and Eq.
enforce the global budget constraints. The difference to the global budget certificate lies in Eq. 33 to Eq. 36) We introduce an additional variable vector a e {0. 1 that indicates which nodes attacker controlled, [g.. 33 enforces that the attributes of node
14

---

Published as a conference paper at ICLR 2021
remain unperturbed, unless dn = 1. If a, the adversary add or delete at most to or loep, attribute bits. With edge perturbations, it is sufficient for either incident node to be attacker-controlled. This is expressed via Eq. 35 The number of added or deleted edges incident to node n is constrained via Eq. 34 Finally, Eq. ensures that at most a nodes are attacker-controlled.
C.I UNDIRECTED ADJACENCY MATRIX
To adapt our certificate to undirected graphs, we simply change the interpretation of the indicator matrix A- Now, setting either B Bag or Baja to 1 corresponds to perturbing the undirected edge (i , An edge should not be perturbed twice, which we express through an additional constraint:
B BAi BAJA S Vi,j (L.
(39)
We further combine Eq. 34 which enforced that at least one of the incident nodes of a perturbed edge has to be attacker controlled, and Eq. 35] which enforced the local budgets for edge perturbations, into following constraints:
Σ
BAn. I an lacd,
(40)
m:An m =0
BAn,m S az loc
(41)
These changes do not affect the optimal value of the mixed-integer linear program. But they are more effective than [q. 34 anddFqg (5qq.355 35 when solving the relaxed linear program and the nodes' local budgets are small relative their degree.
D DETERMINING THE PARETO FRONT OF BASE CERTIFICATES
For our collective certificate, assume that base certificates directly yield the pareto front p(n) of points enclosing the volume of budgets K(") for which the prediction fn is certifiably robust:
p()) {p K(n)
-3E's E K(a) p' #AAVd (1,2,3.4) Psa S pu)
(42)
with
((a) E NO PELAY(X' E Sa(X, A) In fx(X', A')
(43)
[nn) L()()) and LL [rx x [ra x [rAuaal x [rr (with [k: {0...... , k} (see Section 3 In practice, finding this representation requires some additional processing which we shall discuss in this section.
Existing certificates for graph-structured data are methods that determine for a specific budget E L whether classifier fn is robust perturbations in (p)) other words: They can only test the membership relation p (n),, One possible way of finding the pareto front is through the following three-step process:
1. Use flood-fill algorithm starting at (0 0 0
0)" to determine (()),
2. Identify all points in (()) = IL (n) that enclose the volume K(x)
3. Remove all enclosing points that not pareto-optimal.
A pseudo-code implementation is provided in algorithm 1 It has running time in O ((((a))). where è is the worst-case case of performing membership test p (k).
15

---

Published as a conference paper at ICLR 2021
Algorithm 1: Determining the pareto front of base certificates
Result: Set (a(n) of pareto-optimal points enclosing the volume of budgets IK within
L = [ra x [xxaal x |TAaall x [r [rAaal (see Section 3).
pr(n) 0 //://Pttntial pareto points
closed_set - //Visittedd vectors
F Function flood
closed <- closed set {p}:
if i (p
| K(n)) then
p((n) -pr(n) {p}
else
for p' E {p- dld E [0.1}* A ||d]] = 1} do
if (p' E closed set) then
flood p')l( Consiider neighboring vectors
end
end
end
flod-fill(() p(n) + //a/rPereto front for p p(")' do pareto optimal <- true; for p' (pp-di d'ld' [0,1]* A ||d']] 2 do
0)²);
p' E p(n)' then
pareto.optimal false / //Parettooptiimallt does not allow
decreasing values while staying in K(n)
break;
end end
pareto optimal then P(n) p()) (p)
end
end
TIGHTNESS FOR RANDOMIZED SMOOTHING
In this section prove that if use the randomized smoothing based certificate from Bojchevski et al. (2020) as our base certificate, then our collective certificate is tight: If we do not make any fur- ther assumptions, outside each smoothed classifier's receptive field and its expected output behavior under the smoothing distribution, we cannot obtain better collective certificate. We define the base certificate and then provide a constructive proof of the resulting collective certificate's 's tightness.
E. RANDOMIZED SMOOTHING FOR SPARSE DATA
Bojchevski et al. 2020 provide robustness certificate for classification of arbitrary sparse binary data. Applied to node classification, it can be summarized as follows:
Assume given multi-output classifier h G (1...., CY.. Define smoothed classifier f: (1, (1,..., C) with
= argmax Pr [hn (datr (X), Pady Vn E (L,
(44)
where Qaur and dadj are independent randomization schemes that assign probability to the set of attribute matrices {0, 1] N and adjacency matrices (0, NxNN respectively. The ran-
16

---

Published as a conference paper at ICLR 2021
domization schemes are defined as follows:
(X) Pr ( (X) m.d 1 X m. 0 Xad 100 g11-xmmm Vm E (I,...,NI.ds (I....,D)
(45)
Pr Padil (A):. = As.j A 00 (01AA15)
Andd
Vi,j (N.
(46)
Each bit's probability of being flipped is dependent on its current value, but independent of the other bits.
An adversarially perturbed graph (X', AA) successful in changing prediction yn. = A), if
yn argmax Pr [ (Xattr(X'), Padj(A")) = =..
(47)
Evaluating this inequality usually not tractable. We can however relax the problem: Let pn Pr [A,, (Pater (X)ttr(X), Ouaj (A)) V/ and let HI be the set of all possible classifiers for graphs in g (including non-dcterministic ones). If
min Pr (onuue (X'), Oudj Dudi(AA)) ynn R,EH
0.5
(48)
s.t.
Pr [ (X). Oudj ( (A)) Yn
Pn.
(49)
A). It is easy set defined by Eq. 49 so the result of the optimization problem is a lower bound on Pr (Phutrr (X') Paatj (A')) = yn.. If this lower bound is larger than 0.5, then yn is guaranteed to be the argmax class.
then (X' A')
why: The unsmoothed hn is in the
Optimizing over the set of all possible classifiers might appear hard. We can however the ap- proach of Lee et al. (2019) to find an optimum. Let X', X', A' be a graph that results from bxmae attribute additions, bxaa attribute deletions, bAnas edge additions, and b b edge additions applied to (X, A). We can partition the set of all graphs G into (bx,as + bx + 1) (bAnn + bAan + regions that have a constant likelihood ratio under our smoothing distribution:
Jaxxna 9x,94 QA A S (Dxmss + (bO)
+1) A Ag S
(DAnd +
(1(m)
(x)
Ada + +1)}
(50)
with
Pr [oatt (X) X" S (A) A"
(X",A") E Jax
Toatr (') = X" A Oadj (A') = A" n
(51)
where the 7,,-- R4 are constants. The regions have particular semantic meaning, which will be important for our later proof: Any (x", A") E Jax has qx attribute bits and QA adjacency bits that have the same value in (X, A), and different value in A'):
((X", AA" E Jnx.9A) =
(52)
H m, d) x m.d = Xm, # X Xmm gx A Ki,jJ = A # Al = QA
As proven by [ee et al. 2 we can find an optimal solution Eq. 48 by optimizing over the expected output of within each region of constant likelihood ratio. This can be implemented via the following linear program:
An (bxiaa bxan bAnda b Aad Pr:)) :=
(bx + bxaa) (Danaa +baga)
(53)
Hin) aa Pr Pr(easse(X') Daals (n))( E Tax-9a)
min H
0 (banad tbraa)
(bxnad + +bxaa)
s.t.
H(a)
E Nax Max- Par
(54)
=x=0
9A=0
H E [0, 1] (rx (xxaaattxaal ( traaa)).
(55)
Any optimal solution H (n) corresponds to a single-output classifier hn that, given an input graph x A"), simply counts the number of attribute bits qx and adjacency bits QA that have the same
17

---

Published as a conference paper at ICLR 2021
value in (X, A) and different value in (X', A') and then assigns a probability of H .A to class fn and - .4 A to the remaining classes.
The optimal value of Eg. 53 being larger than 0.5 for a fixed perturbed graph (X', A') only proofs that this particular graph is not a successful attack on fn- For a robustness certificate, we want to know the result for worst-case graph. However, the result is only dependent on the number of per- turbations bx.as: : 6xaa:: Aadd and b and not on which specific bits are perturbed. Therefore, we can solve the problem for an arbitrary fixed perturbed graph with the given number of perturbations, and obtain valid robustness certificate.
For use our collective certificate, we define the set of budgets (()) for which prediction fn is certifiably robust as
(nn) = (bx.ad bxam
bAndd
bAnd) _ E IL |An (bxsad bxam: basdd b Aa Pr.) > 0.5 (56)
where An defined as in Eq. 53d IL = [rix.aal x [r'xaal x x|r (raaall x (rAag] (with [k]
(o....,,k)
is the set of vectors that do not exceed the available collective budget (see Section 3).
E.2 TIGHTNESS PROOF
With the definition of our base certificate in place, we can now formalize and prove that the re- sulting collective certificate is tight. Recall that randomized smoothing is black-box method. The classifier that is being smoothed is treated as unknown. A robustness certificate based on random- ized smoothing has account for the worst-case (i.c. least robust under the given threat model) classifier. Our collective certificate lower- be simultaneously robust. We show that with the randomized smoothing base certificate from the previous section, it actually yields the exact number of robust predictions, assuming the worst-case unsmoothed classifier.
the number of predictions that are guaranteed to
Theorem Lel (X, A) be an unperturbed graph. Let h : G + (I....,C}* be a (potentially neneeettriii multi- nutti- classifier. Let f G + {1....,C? C} be the corresponding smoothed classifier with
fa(X". AA") argmax DE (I.......) Pr [hn(@uter (x"e)tttrrx(),,))))))))) Gudj Puaj(AA)) =c],
(57)
On = fr((, A),
(58)
Pa Pr (Pen (dhatr (a)aarrr()))))) Dndj (A)) = yn),
(59)
and randomization schemes Ounr (X), Dadi defined as in Eq. 45 and Eq. 46 Let
ub E {0.1) (0,1),,U) T E {0, 10,13NxN be receptive field indicators corresponding to In (see Eq. 2/. Let Bg be T T T' "' A'daa Auas: T Xaaatooc> T Xaesstoo: T A'nca,oo loo T Ades toe: 0, as defined in Seccion 2) Let T be the indices of nodes targeted by an adversary. Under the given parameters, let os be the optimal value of the optimization problem defined in Section C
set of admissible perturbed graphs, constrained by parameters
Then there are a perturbed graph (X', A'), a non-deterministic multi-output classifier and a corresponding smoothed multi-output classifier ff with
Fa (,,X, A) = argmax sejp.... Pr [hn(Oattr()) Oudj (A)) = c] Vn E (1....,N)
(60)
such that
f | A') = yn 0z,
(61)
Pr [nn (X), Daas (A)) = Un = pni
(62)
and each Fn is only dependent on nodes and edges for which (b(m)) and (p(n) have value
The optimization problem from Section C has three parameters bxsar bx BA which specify the budget allocation of the adversary. Let b" Xsas by by... B be their value in the optimum. We can construct a perturbed graph (X', A') from the clean graph (X, A) as follows: For every node n, set the first x anan
Proof:
zero-valued bits to one and the first b bxae non-zero bits to zero Then,
18

---

Published as a conference paper at ICLR 2021
flip any entry (n, m) of An.m for which BAn. 1. The parameters 6%..... 6x... BAx are part of feasible solution to the optimization problem. In particular, they must fulfill constraints Eq. 31 3o
Eq. 36, which guarantee that the constructed graph is in Bg.
Given the perturbed graph field of each prediction fn:
calculate the amount of perturbation in the receptive
Xaad = (bXads) (e)(()
[m]
(63)
(n)
= (bixa)) )' (Tbb(n)
(64)
Xaal
(n) u. Annd
Σ
Vi. BAij
(65)
(1,))Ar,5=0
(n) "Anda
Σ
Vis BAis
(66)
(k.))Ar.==1
We can now specify the unsmoothed multi-output classifier h. Recall that in the collective cer- tificate's is optimization problem, each fn is associated with binary variable e, In the optimum,
(1% 0)
(1 u "Xanl
(n)
"Asad
(n)
u "Ain)
T
E K(n) i.e. Jn 's robustness is guaranteed by
the base certificate, and o* = -nnrr [T] - -
Case 1: & T. Choose h. = hn. Trivially, constraint Eg. 62 is fulfilled since Jn, is only dependent on nodes and edges for which vb(()) and (n(n) have value 1. Whether f is adversarially attacked or not does not influence Eq. 61 as n & T.
Case 2: n E T and t = Choose hn = fug Again, constraint Eq. 62 is fulfilled since Fr is only dependent on nodes and edges for which (b(m) and ((() have value 1. Since t O, we know that
(m)
(m)
(n)
(("), i.e. fn A') yn-
u uXaad
"Xasl Aadd U'aa
Case 3: (u(n))
E T and t = 1. Since it = 1, we know that fn is not certified by the base certificate:
(Xuaad
u "Xaal
(n)
u Aadd
(n)
AAaa
(n)
& K(²), Let (*) [0,
(w) Xadd +
(n)
Anad" +u
Aaa
be
the optimum of the linear program underlying the hase certificate (see Eq. 53 to Eq. 55 have the following non-deterministic output behavior:
Define h
Pr [T' A") = Vin| = (n)
v(X" A²) EG
(67)
2x (X") (0)
(A
(A")
Pr [Tn(X" A²) = si] = - H. (n)
V(X" A²) EG
(68)
4x (X"), (A")
(n)
(A")
for some 1/2 # yn and with
x (X") = (m, d)|X" = Xn,d + X Xm
(69)
(n) 4 (A") (n,, m)) m)) A".. An,m Ammm
(70)
As discussed at the end Section E. this classifier simply counts the number of bits in (X", that are within f,'s 's receptive hield and have the same value in the clean graph (X, A) and
A")
different value in the perturbed graph program underlying the base certificate, we know that Eq. 62 is fulfilled, as it is equivalent to
Since H (n) is valid solution to the linear
Eq. 54 from the base certificate. Since (n)
(n)
Anaa u (n) uAua)
(n)
TT'
$ K("), we know
u Xaal
that Pr [hattar Andj ( (A')) vi] ((XXXA))
2 0.5 (see
Eq. 56)
i.e. fn is successfully attacked,
Fa(X', A') = s/n # (x A).
By construction, we have exactly of nodes for which (x', A') = Yn and the remaining constraints fulfilled well. 0
19

---

Published as a conference paper at ICLR 2021
F HYPERPARAMETERS
Training schedule for smoothed classifiers. Training is performed in a semi-supervised fashion with 20 nodes per class as a train set. Another 20 nodes per class serve as a validation set. Models are trained with Adam (learning rate = 0.001 [0.01 for SMAJ, 31 = 0.9, 82 = 0.999, e 10 weight decay 0.001) for 3000 epochs, using the average cross-entropy loss across all training set nodes, with a batch size of 1. We employ early stopping. if the validation loss does not decrease for 50 epochs (300 epochs for SMA). In each epoch, a different graph is sampled from the smoothing distribution. We do not use the -L-devereeece based regularization loss proposed for RGCN, we found to decrease the certifiable robustness of the model.
Training schedule for non-smoothed GCN. Training is performed in a semi- supervisee fashion with 20 nodes per class as a train set. Another 20 nodes per class serve as validation set. For the first 100 of 1000 epochs, models are trained with Adam (learning rate 0.01, Br 0.9, B2 loss across all training set nodes, with batch size of 8. After 100 episodes, we add the robust loss proposed in (Zügner & Günnemann 2019) (local budget q == 21, global budget Q = 12, training node classification margin 10) unlabeled node classification margin log (60/40), The gradient for the robust loss term is accumulated over 5 epochs before each weight update in order to simulate larger batch sizes.
0.999, c = 10 weight decay = 1005), 5), using the average cross-
Network parameters. In all models, hidden linear and convolutional layers are followed by ReLU nonlinearity. During training, each ReLU nonlinearity is followed by 50% dropout. For GCN and GAT, we use two convolution layers with 64 hidden activations. The number of attention heads for GAT is set to 8 for the first layer and for the second layer. RGCN uses independent gaussians as its internal representation (i.e. each feature dimension has a mean and a variance). For RGCN, we use one linear layer, followed by two convolutional layers. We set the number of hidden activations to 32 for the means and 32 for the variances. Dropout is applied to both the means and variances. For APPNP, we use two linear layers with 64 hidden activations, followed by a propagation layer based on approximate personalized pagerank (teleport probablity = 0.15, iterations 10). To ensure locality, set all but the top 64 of each row in the approximate pagerank matrix to 0. For SMA, we first transform each node's 's features using a linear layer with 64 hidden activations. We then apply soft medoid aggregation (k 64, T = 10) based on the approximate personalized pagerank matrix (teleport probablity = 0.15, iterations = 2). Note that we use the alternative parameterization from appendix B.5 of (Geisler et al., (020) that is designed improve robustness to attribute perturbations. After the aggregation, we apply a ReLU nonlinearity. Finally, we apply second linear layer to each node independently.
Randomized smoothing. Randomized smoothing introduces four additional hyperparameters 8xmas: 0x Asda Aams which control the probability of flipping bits in the attribute and ad- jacency matrix under the smoothing distribution. we only certify attribute perturbations, we set 0.002 and 0x 0.6. If we only certify adjacency perturbations, and 0 A 0.4. If we jointly certify attribute and ad-
OAwn 0 A 0, 0 0x
0, 0 Anaa jacency perturbations, we set 0x.da = 0.002, 0 0x = 0.6, 0 A
we set xxx 0 0xam
0 and 0 0 = 0.4. Exactly evaluating smoothed classifiers is not possible, they have to be approximated via sampling. We use 1000 samples determine classifier's majority class (y,,), followed by 10 samples to estimate the probability of the majority class (px)) via a Clopper-Pearson confidence interval. Applying Bon- ferroni correction, the confidence level for each confidence interval is set to 1 0.01/N to obtain an overall confidence level of 99% for all certificates.
20


Reviews:
[{"review_id": "lqtzTmNj6Ms", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper addresses the limitation of the existing adversarial robustness certificates that ignores that a single shared input is present, and thus assumes an adversary can use different perturbed inputs to attack different predictions. A novel collective certificate fusing single certificates into a stronger one, is proposed by explicitly modeling local structure of input data using graph convolution node classifiers. In terms of certified ratio, the collective certificate significantly improve the results compared with existing individual certificates. \n\n-quality: the technical quality is sound.\n\n-clarity: the input data, problem formulation and method are clearly described.\n\n-originality & significance: it is the first attempt in considering collective robust certificates (CRCs) by fusing individual adversarial certificate. As shown in the experiments, the certified ratio of the CRC is significantly improved over existing adversarial one. I think the collective robust certificate has some impacts for robust graph node classifications.\n\nPros: The paper is well motivated. The problem and the method are both clearly presented. The improvements of the collective robust certificate over the existing ones is sufficiently high in terms of certified ratios.\n\nCons: I do not find any notable weaknesses.", "extra_scores": {}, "extra_text": {}}, {"review_id": "c5YLnE9omq", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "** Summary:\nIn the context of structured prediction, where multiple predictions are simultaneously made based on a single input, this works argue that existing robustness certificates independently operating on each node prediction end up with overly pessimistic results. Rather than that, this work advocates to collectively certify the overall accuracy using a single perturbed graph at a time. Starting from the building-blocks of base certificates, the authors formulate a global optimization problem, which is made tractable via a number of relaxation steps resulting in a final mixed-integer linear programming (MILP). Experimental results demonstrate clear advantage of the proposed certificates over base ones, with reasonable computational overheads coming from solving the MILP.\n\nThe paper is well-motivated, well-written and easy to follow. I think this is a valid method to assess robustness of classifier satisfying locality like GCN.\n\n** Strength:\n - This work is well-motivated. The arguments are valid on the limitations of independent based certificates for collective tasks. Experimental results convincingly show how such certificates are pessimistic in the addressed context.\n - The writing is clear and well-structured, easy to understand and follow. \n - Nice discussion on the limitations\n \n** Limitations:\n - Typos:\n \t+ Eqn. (2): $f_n(\\boldsymbol {X}^{'}, \\boldsymbol{A}^{'}) = f_n(\\boldsymbol{X}^{''}, \\boldsymbol{A}^{ \\textcolor{red}{''}})$\n\n \t+ Eqn. (7): $\\boldsymbol {X}^{''}_{i,d} = \\psi_i^{(n)}\\boldsymbol {\\textcolor{red}{X}}^{'}_{i,d} + (1-\\psi_i^{(n)})\\boldsymbol {\\textcolor{red}{X}}_{i,d}$\n \n \n\n** Justification of rating: overall this is an interesting paper. The motivation, arguments and results are convincing.", "extra_scores": {}, "extra_text": {}}, {"review_id": "Z8FbJxzBmOj", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies classifiers that collectively output many predictions based on a single input. Existing adversarial robustness certificates assume that an adversary can use different perturbed inputs to attack different predictions, and ignore the fact of a single shared input, thereby being overly pessimistic. This paper proposes a collective certificate that computes the number of simultaneously certifiable nodes for which the predictions can be guaranteed to be stable (not change). It is conducted basically by fusing individual certificates into a provably stronger certificate through explicitly modeling locality. \nPros: This is the first effort that considers collective robustness certificate. \nCons: \n1.\tAs discussed in the paper, the proposed approach is designed to exploit locality. Without locality, it is equivalent to a naïve combination of base certificates that sums over perturbations in the entire graph. \n2.\tThe writing of the paper can be improved. The abstract seems to be unfinished. It appears to be hard to include sufficient preliminaries to clearly describe the research problem in a conference paper. It’s probably better to have a longer version as a journal paper.  \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "OQdINjSLlrE", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary\n-------------\nCurrent methods on adversarial robustness certificates consider data points independently which are highly pessimistic for structured data. This work proposes the first collective robustness certificate that considers the structure of the graph by modeling locality in order to derive stronger guarantees  that the predictions remain stable under perturbations.\n\nThis work focuses on Graph Neural Networks comparing between a Naive collective certificate (baseline) and a proposed collective certificate that combines single-node certificates effectively. \n\nThe experiments compares these two methods against certified ratio vs. attribute and edge perturbations on the datasets Cora-ML, Citeseer, and PubMed.\n\nPros\n------\n- The paper is well-written and easy to follow.\n- The paper tries to address a very common problem of adversarial attacks where data points are structured. Although it is a common problem, it was not explored with respect to collective robustness certificates before this work.\n- The paper shows a novel, effective way of combining individual certificates by incorporating locality.\n- The paper presents an LP-relaxation method that allows us to solve the certificate fast for large graphs where mixed-integer problems are prohibitively costly.\n- The paper shows strong theory and experiments to illustrate the efficacy of the proposed collective certificate.\n- The experiments show run-time and uncertainty measures with multiple runs for statistical significance.\n\nQuestions\n--------------\n- Is there a reason why [1] was not discussed in the paper? it is highly relevant as it also studies adversarial robustness for structural attacks. \n- How does the proposed method apply to robust Associative Markov Networks (AMN) in [1]?\n- Did you try running the proposed method on WebKB and Reuters which are present in this work [1]?\n- How does the linear relaxation in this work differ from the one provided in [1]?\n- How would the proposed method compare against robust AMN [1]?\n- Can the findings be used to come up with robust methods outside classification, like segmentation and scene understanding?\n\nIn summary, I like the novelty of this method and the through experiments that were conducted that illustrate the efficacy of the proposed collective certificate, thus I recommend an accept.\n\n[1] Kai Zhou, Yevgeniy Vorobeychik. Robust Collective Classification against Structural Attacks. UAI 2020. \n\n------- Post rebuttal\nI am satisfied with most of the rebuttal the authors have provided, and I have raised my score to an 8. \n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper considers a new setting of robustness, where multiple predictions are simultaneously made based on a single input. Different from existing robustness certificates which independently consider perturbation of each prediction, the authors propose collective robustness certificate that computes the number of predictions which are simultaneously guaranteed to remain stable under perturbation. This yields more optimistic results. Most reviewers think this is a very interesting work and the authors present an effective method to combine individual certificate. The experimental results are convincing. I recommend accept.
Decision: Accept (Poster)