Collective Robustness Certificates: Exploiting Interdependence in Graph
  Neural Networks
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$.
Jan Schuchardt, Aleksandar Bojchevski, Johannes Gasteiger, Stephan Günnemann
# Collective Robustness Certificates:

###### 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\).

## 1 Introduction

Most classifiers are vulnerable to adversarial attacks (Akhtar & Mian, 2018; Hao-Chen et 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 to ensure that models are robust since data can be noisy, incomplete, or anomalous. We study classifiers that collectively output many predictions based on a single input. This includes node classification, link prediction, molecular property prediction, image segmentation, part-of-speech 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 (Goodfellow et al., 2015), which has been applied to part-of-speech tagging (Han et al., 2020), semantic segmentation (Xu et al., 2020) and node classification (Feng et al., 2019). Graph-related tasks in particular have spawned a rich assortment of techniques. These include Bayesian models (Feng et al., 2020), data-augmentation methods (Entezari et al., 2020) and various robust network architectures (Zhu et al., 2019; Geisler et 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 (Zugner & Gunnemann, 2019). Other methods try to detect adversarially perturbed graphs (Zhang et al., 2019; Xu et al., 2020) or directly correct perturbations using generative models (Zhang & Ma, 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 is established, it may subsequently be defeated using novel attacks (Carlini & Wagner, 2017). We are therefore interested in deriving adversarial robustness certificates which provably guarantee that a model is robust.

In this work we focus on node classification.1 Here, the goal is to assign a label to each node in a single (attributed) graph. Node classification can be the target of either _local_ or _global_ adversarial attacks. Local attacks, such as Nettack (Zugner et al., 2018; Zugner et al., 2020), attempt to alter the
prediction of a particular node in the graph. Global attacks, as proposed by Zugner and Gunnemann (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 input. 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 a choice and can attack only one subset of nodes (see Fig. 1).

Existing certificates (Zugner and Gunnemann, 2019; Bojchevski and Gunnemann, 2019; Bojchevski et 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, i.e. to certify the predictions of many nodes at once2. A naive certificate for global attacks can be constructed from existing single-node certificates as follows: One simply certifies each node's prediction independently and counts how many are guaranteed to be robust. This, however, implicitly assumes that an adversary can use different perturbed inputs to attack different predictions, ignoring the fact that we have a single shared input.

Footnote 2: Chiang et al. (2020) certify multi-object detection, but they still treat each detected object independently.

We propose a _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 to 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 to as base certificates, into a drastically (and provably) stronger collective one. Our approach is independent of how the base certificates 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-passing graph neural 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 in its surrounding.

For classifiers that satisfy locality, perturbations to one part of the graph do not affect all nodes. Adversaries are thus faced with a budget allocation problem: It might be possible to attack different 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, overestimating how many nodes can be attacked. We design a simple (mixed-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. 1).

We evaluate our approach on different datasets and with different base certificates. We show that incorporating 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 a provably stronger certificate by explicitly modeling _locality_.
* Is the first node classification certificate that can model not only global and local budgets, but also the number of adversary-controlled nodes, regardless of whether the base certificates support this.

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 practice due to mutually exclusive perturbations. Our collective certificate enforces a single perturbed graph (center). It aggregates the amount of perturbation within each receptive field and then evaluates a single-node certificate to determine whether the corresponding prediction is robust (right).
## 2 Preliminaries

**Data and models.** We define our unperturbed data as an attributed graph \(\mathcal{G}=(\mathbf{X},\mathbf{A})\in\mathbb{G}\) with \(\mathbb{G}=\{0,1\}^{N\times D}\times\{0,1\}^{N\times N}\), consisting of \(N\)\(D\)-dimensional feature vectors and a directed \(N\times N\) adjacency matrix. Each vertex is assigned one out of \(C\) classes by a multi-output classifier \(f:\mathbb{G}\mapsto\{1,\dots,C\}^{N}\). In the following, \(f_{n}(\mathcal{G})=f_{n}(\mathbf{X},\mathbf{A})=f_{n}\) refers to the prediction for node \(n\).

**Collective threat model.** Unlike previous certificates, we model an adversary that aims to change multiple predictions at once. Let \(\mathbb{B}_{\mathcal{G}}\subseteq\mathbb{G}\) be a set of admissible perturbed graphs. Given a clean graph \(\mathcal{G}\), the adversary tries to find a \(\mathcal{G}^{\prime}\in\mathbb{B}_{\mathcal{G}}\) that maximizes the number of misclassified nodes, i.e. \(\sum_{n\in\mathbb{T}}\mathbf{1}_{f_{n}(\mathcal{G})\neq f_{n}(\mathcal{G}^{ \prime})}\), for some set of target nodes \(\mathbb{T}\subseteq\{1,\dots,N\}\).

Following prior work (Zugner and Gunnemann, 2019), we constrain the set of admissible perturbed graphs \(\mathbb{B}_{\mathcal{G}}\) through global and (optionally) local constraints on the number of changed bits. Our global constraints are parameterized by scalars \(r_{\mathbf{X}_{\text{add}}},r_{\mathbf{X}_{\text{del}}},r_{\mathbf{A}_{\text{add}}},r_{ \mathbf{A}_{\text{del}}}\in\mathbb{N}_{0}\). They are an upper limit on how many bits can be added (\(0\to 1\)) or deleted (\(1\to 0\)) when perturbing \(\mathbf{X}\) and \(\mathbf{A}\). Our local constraints are parameterized by vectors \(r_{\mathbf{X}_{\text{add,loc}}},r_{\mathbf{X}_{\text{del,loc}}},r_{\mathbf{A}_{\text{add, loc}}},r_{\mathbf{A}_{\text{del,loc}}}\in\mathbb{N}_{0}^{N}\). They are an upper limit on how many bits can be added or deleted per row of \(\mathbf{X}\) and \(\mathbf{A}\), i.e. how much the attributes of a particular node can change and how many incident edges can be perturbed.

Often, it is reasonable to assume that no adversary has direct control over the entire graph. Instead, a realistic attacker should only be able to perturb a small (adaptively chosen) subset of nodes. To model this, we introduce an additional parameter \(\sigma\in\mathbb{N}\). For all \((\mathbf{X}^{\prime},\mathbf{A}^{\prime})\in\mathbb{B}_{\mathcal{G}}\), there must be a set of node indices \(\mathbb{S}\subseteq\{1,\dots,N\}\) with \(|\mathbb{S}|\leq\sigma\) such that for all \(d\in\{1,\dots,D\}\) and \(n,m\in\{1,\dots,N\}\):

\[\left(X^{\prime}_{n,d}\neq X_{n,d}\implies n\in\mathbb{S}\right)\left(A^{ \prime}_{n,m}\neq A_{n,m}\implies n\in\mathbb{S}\lor m\in\mathbb{S}\right). \tag{1}\]

The set \(\mathbb{S}\) is not fixed, but chosen by the adversary.3 The resulting set \(\mathbb{B}_{\mathcal{G}}\) is formally defined in Section B. If the global budget parameters are variable and the remaining parameters are clear from the context, we treat \(\mathbb{B}_{\mathcal{G}}\) as a function \(\mathbb{B}_{\mathcal{G}}:\mathbb{N}_{0}^{4}\mapsto\mathcal{P}(\mathbb{G})\) that, given global budget parameters, returns the set of all perturbed graphs fulfilling the constraints.

Footnote 3: Note that the adversary only needs to control one of the nodes incident to an edge in order to perturb it. We do not associate different costs for perturbing different nodes or edges, but such an extension is straightforward.

**Local predictions.** Our certificate exploits the locality of predictions, i.e. the fact that predictions are only based on a subset of the input data. We characterize the receptive field of \(f_{n}\) via an indicator vector \(\mathbf{\psi}^{(n)}\in\{0,1\}^{N}\) corresponding to rows in attribute matrix \(\mathbf{X}\) and an indicator matrix \(\mathbf{\Psi}^{(n)}\in\{0,1\}^{N\times N}\) corresponding to entries in adjacency matrix \(\mathbf{A}\). For all \((\mathbf{X}^{\prime},\mathbf{A}^{\prime}),(\mathbf{X}^{\prime\prime},\mathbf{A}^{\prime\prime}) \in\mathbb{B}_{\mathcal{G}}\):

\[\sum_{m=1}^{N}\sum_{d=1}^{D}\psi_{m}^{(n)}\mathbf{1}_{X^{\prime}_{m,d}\neq X^{ \prime\prime}_{m,d}}+\sum_{i=1}^{N}\sum_{j=1}^{N}\Psi_{i,j}^{(n)}\mathbf{1}_{ A^{\prime}_{i,j}\neq A^{\prime\prime}_{i,j}}=0\implies f_{n}(\mathbf{X}^{ \prime},\mathbf{A}^{\prime})=f_{n}(\mathbf{X}^{\prime\prime},\mathbf{A}^{\prime\prime}). \tag{2}\]

Eq. 2 enforces that as long as all nodes and edges for which \(\mathbf{\psi}^{(n)}=1\) or \(\mathbf{\Psi}^{(n)}=1\) remain unperturbed, the prediction \(f_{n}\) 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, \(\mathbf{\psi}^{(n)}\) and \(\mathbf{\Psi}^{(n)}\) correspond to all data points that influence \(f_{n}\) under some graph in \(\mathbb{B}_{\mathcal{G}}\), i.e. 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 is any procedure that can provably guarantee that the prediction \(f_{n}\) for a specific node \(n\) cannot be changed by any perturbed graph in an admissible set, such as sparsity-aware smoothing (Bojchevski et al., 2020). As you shall see in the next section, our collective certificate requires evaluating base certificates for varying adversarial budgets within \(\mathbb{L}=[r_{\mathbf{X}_{\text{add}}}]\times[r_{\mathbf{X}_{\text{del}}}]\times[r_{ \mathbf{A}_{\text{add}}}]\times[r_{\mathbf{A}_{\text{del}}}]\) (with \([k]=\{0,\dots,k\}\)), the set of vectors that do not exceed the collective global budget.

A base certificate implicitly partitions \(\mathbb{L}\) into a set of budgets \(\mathbb{K}^{(n)}\subseteq\mathbb{L}\) for which the prediction \(f_{n}\) is certifiably robust and its complement \(\overline{\mathbb{K}^{(n)}}=\mathbb{L}\setminus\mathbb{K}^{(n)}\) with

\[\mathbb{K}^{(n)}\subseteq\left\{\mathbf{\rho}\in\mathbb{N}_{0}^{4}\mid\mathbf{\rho} \in\mathbb{L}\land\forall(\mathbf{X}^{\prime},\mathbf{A}^{\prime})\in\mathbb{B}_{ \mathcal{G}}(\mathbf{\rho}):f_{n}(\mathbf{X},\mathbf{A})=f_{n}(\mathbf{X}^{\prime},\mathbf{A}^{ \prime})\right\}. \tag{3}\]
Note the subset relation. The set \(\mathbb{K}^{(n)}\) does not have to contain all budgets for which \(f_{n}\) is robust. Conversely, a certain budget vector \(\mathbf{\rho}\) not being part of \(\mathbb{K}^{(n)}\) does not necessarily mean that \(f_{n}\) can be attacked under threat model \(\mathbb{B}_{\mathcal{G}}(\mathbf{\rho})\) - its robustness is merely unknown. We now make the following natural assumption about base certificates: If a classifier is certifiably robust to perturbations with a large global budget, it should also be certifiably robust to perturbations with a smaller global budget.

\[\forall\mathbf{\rho}\in\mathbb{K}^{(n)},\mathbf{\rho}^{\prime}\in\mathbb{L}:[\forall d \in\{1,2,3,4\}:\rho_{d}^{\prime}\leq\rho_{d}]\implies\left[\mathbf{\rho}^{\prime }\in\mathbb{K}^{(n)}\right]. \tag{4}\]

From a geometric point of view, Eq. 4 means that the budgets \(\mathbb{K}\) for which the prediction \(f_{n}\) is certifiably robust form a singular enclosed volume around \((0\quad 0\quad 0\quad 0)^{T}\) within the larger volume \(\mathbb{L}\). Determining whether a classifier is robust to perturbations in \(\mathbb{B}_{\mathcal{G}}(\mathbf{\rho})\) is equivalent to determining which side of the surface enclosing the volume \(\mathbb{K}\) the budget vector \(\mathbf{\rho}\) lies on. This can be be done by evaluating linear inequalities, as shown in the following.

First, let us assume that all but one of the budgets are zero, e.g. \(\mathbb{L}=[r_{\mathbf{X}_{\mathrm{add}}}]\times[0]\times[0]\times[0]\), with \(r_{\mathbf{X}_{\mathrm{add}}}>0\). Due to Eq. 4 there must be a distinct value \(p_{n}\in\mathbb{N}_{0}\) (the smallest uncertifiable budget) with \(\forall\mathbf{\rho}\in\mathbb{L}:\mathbf{\rho}\in\overline{\mathbb{K}^{(n)}} \iff\rho_{1}\geq p_{n}\). Evaluating the base certificate can thus be performed by evaluating a single inequality. This approach can be generalized to arbitrary types of perturbations. Instead of using a single scalar \(p_{n}\), we characterize the volume of budgets \(\mathbb{K}^{(n)}\) via the pareto front of points on its enclosing surface:

\[\mathbb{P}^{(n)}=\left\{\mathbf{\rho}\in\overline{\mathbb{K}^{(n)}}\mid\neg \exists\mathbf{\rho}^{\prime}\in\overline{\mathbb{K}^{(n)}}:\mathbf{\rho}^{\prime} \neq\mathbf{\rho}\wedge\forall d\in\{1,2,3,4\}:\rho_{d}^{\prime}\leq\rho_{d} \right\}. \tag{5}\]

These points fulfill \(\forall\mathbf{\rho}\in\mathbb{L}\left(\mathbf{\rho}\in\overline{\mathbb{K}^{(n)}} \iff\exists\mathbf{p}\in\mathbb{P}^{(n)},\forall d\in\{1,2,3,4\}:\rho_{d}\geq p_{ d}\right).\) Here, evaluating the base certificate can be performed by evaluating \(4|\mathbb{P}|\) inequalities.

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 \(\mathbb{K}^{(n)}\), followed by a thinning operation (for more details, see Section D).

## 4 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 a linear program to enable fast computation and show the certificate's tightness when using a randomized smoothing base certificate. We conclude by discussing the certificate's time complexity and limitations.

**Naive collective certificate.** Assume we are given a clean input \((\mathbf{X},\mathbf{A})\), a multi-output classifier \(f\), a set \(\mathbb{T}\) of target nodes and a set of admissible perturbed graphs \(\mathbb{B}_{\mathcal{G}}\) fulfilling collective global budget constraints given by \(r_{\mathbf{X}_{\mathrm{add}}},r_{\mathbf{X}_{\mathrm{add}}},r_{\mathbf{A}_{\mathrm{add}}},r_{\mathbf{A}_{\mathrm{add}}}\). Let \(\mathbb{L}=[r_{\mathbf{X}_{\mathrm{add}}}]\times[r_{\mathbf{X}_{\mathrm{add}}}]\times[ r_{\mathbf{A}_{\mathrm{add}}}]\times[r_{\mathbf{A}_{\mathrm{add}}}]\) 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 \(f_{n}\) is certifiable robust to perturbations within a set of budgets \(\mathbb{K}^{(n)}\) (see Eq. 3). As discussed, the naive certificate simply counts the predictions whose robustness to perturbations from \(\mathbb{B}_{\mathcal{G}}\) is guaranteed by the base certificate. Using the representation of base certificates introduced in Section 3, this can be expressed as \(\sum_{n\in\mathbb{T}}\mathbf{1}\left[\mathbb{K}^{(n)}=\mathbb{L}\right]\). From the definition of \(\mathbb{K}^{(n)}\) in Eq. 3, we can directly see that this is a lower bound on the optimal value of \(\sum_{n\in\mathbb{T}}\min_{(\mathbf{X}^{\prime},\mathbf{A}^{\prime})\in\mathbb{B}_{ \mathcal{G}}}\mathbf{1}\left[f_{n}(\mathbf{X},\mathbf{A})=f_{n}(\mathbf{X}^{\prime},\mathbf{A}^{ \prime})\right]\), i.e. the number of predictions guaranteed to be stable under attack. Note that each summand involves a different minimization problem, meaning the adversary may use a different graph to attack each of the nodes.

**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_{(\mathbf{X}^{\prime},\mathbf{A}^{\prime})\in\mathbb{B}_{\mathcal{G}}}\sum_{n\in \mathbb{T}}\mathbf{1}\left[f_{n}(\mathbf{X},\mathbf{A})=f_{n}(\mathbf{X}^{\prime},\mathbf{A}^{ \prime})\right]. \tag{6}\]
Solving this problem is usually not tractable. For simplicity, let us assume that the adversary is only allowed to perform attribute additions. As before, we can lower-bound the indicator functions using the base certificates:

\[\min_{(\mathbf{X}^{\prime},\mathbf{A}^{\prime})\in\mathbb{B}_{\mathcal{O}}}\sum_{n\in \mathbb{T}}\mathbf{1}\left[\left(b\quad 0\quad 0\quad 0\right)^{T}\in\mathbb{K}^{(n)}\right] \tag{7}\]

where \(b=\sum_{(n,d):X_{n,d}=0}X^{\prime}_{n,d}\) 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:

\[\min_{b\in\mathbb{N}_{0}}\sum_{n\in\mathbb{T}}\mathbf{1}\left[\left(b\quad 0\quad 0 \quad 0\right)^{T}\in\mathbb{K}^{(n)}\right]\text{ s.t. }b\leq r_{\mathbf{X}_{\text{ valid}}}. \tag{8}\]

There are two limitations: (1) The certificate does not account for locality, but simply considers the number of perturbations in the entire graph. In this regard, it is no different from the naive 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 1**: _Assume multi-output classifier \(f\), corresponding receptive field indicators \(\mathbf{\psi}^{(n)}\in\{0,1\}^{N}\) and \(\mathbf{\Psi}^{(n)}\in\{0,1\}^{N\times N}\), and a clean graph \((\mathbf{X},\mathbf{A})\). Let \(\mathbb{K}^{(n)}\) be the set of certifiable global budgets of prediction \(f_{n}\), as defined in Eq. 3. Let \((\mathbf{X}^{\prime},\mathbf{A}^{\prime})\) be a perturbed graph. Define \(\mathbf{X}^{\prime\prime}\in\{0,1\}^{N\times D}\) and \(\mathbf{A}^{\prime\prime}\in\{0,1\}^{N\times N}\) as follows:_

\[\mathbf{X}^{\prime\prime}_{i,d} =\psi^{(n)}_{i}\mathbf{X}^{\prime}_{i,d}+(1-\psi^{(n)}_{i})\mathbf{X}_{i,d}, \tag{9}\] \[\mathbf{A}^{\prime\prime}_{i,j} =\Psi^{(n)}_{i,j}\mathbf{A}^{\prime}_{i,j}+(1-\Psi^{(n)}_{i,j})\mathbf{A} _{i,j}, \tag{10}\]

_i.e. use values from the clean graph for bits that are not in \(f_{n}\)'s receptive field. If there exists a vector of budgets \(\mathbf{\rho}\in\mathbb{N}_{0}^{4}\) such that \((\mathbf{X}^{\prime\prime},\mathbf{A}^{\prime\prime})\in\mathbb{B}_{\mathcal{O}}(\bm {\rho})\) and \(\mathbf{\rho}\in\mathbb{K}^{(n)}\), then \(f_{n}(\mathbf{X},\mathbf{A})=f_{n}(\mathbf{X}^{\prime},\mathbf{A}^{\prime})\)._

See proof in Section B. Due to Lemma 1 we can ignore all perturbations outside \(f_{n}\)'s receptive field when evaluating its base certificate. We can thus replace \(\left(b\quad 0\quad 0\quad 0\right)^{T}\) in Eq. 8 with \(\left(\mathbf{b}^{T}\mathbf{\psi}^{(n)}\quad 0\quad 0\quad 0\right)^{T},\) where the vector \(\mathbf{b}\in\mathbb{N}_{0}^{N}\) indicates the number of attribute additions at each node. Optimizing over \(\mathbf{b}\) yields a collective certificate that accounts for locality:

\[\min_{\mathbf{b}\in\mathbb{N}_{0}}\sum_{n\in\mathbb{T}}\mathbf{1}\left[\left(\mathbf{b}^{ T}\mathbf{\psi}^{(n)}\quad 0\quad 0\quad 0\right)^{T}\in\mathbb{K}^{(n)}\right]\text{ s.t. }||\mathbf{b}||_{1}\leq r_{\mathbf{X}_{\text{ valid}}}. \tag{11}\]

We now tackle issue (2) by employing the compact representation of base certificates defined in Section 3. Since we are only allowing one type of perturbation, the base certificate of each classifier \(f_{n}\) is characterized by the smallest uncertifiable radius \(p_{n}\) (see Section 3). To evaluate the indicator function in Eq. 11 we simply have to compare the number of perturbations in \(f_{n}\)'s receptive field to \(p_{n}\), which can be implemented via the following MILP:

\[\min_{\mathbf{b}\in\mathbb{N}_{0}^{N},\mathbf{t}\in\{0,1\}^{N}}|\mathbb{T }|-\sum_{n\in\mathbb{T}}t_{n} \tag{12}\] \[\text{s.t. }\mathbf{b}^{T}\mathbf{\psi}^{(n)}\geq p_{n}t_{n}\quad\forall n \in\{1,\dots,N\}\] (13) \[||\mathbf{b}||_{1}\leq r_{\mathbf{X}_{\text{ valid}}}. \tag{14}\]

Eq. 14 ensures that the number of perturbations fulfills the global budget constraint. Eq. 13 ensures that the indicator \(t_{n}\) can only be set to \(1\) if the local perturbation on the l.h.s. exceeds or matches \(p_{n}\), i.e. \(f_{n}\) is _not_ robustly certified by the base certificate. The adversary tries to minimize the number of robustly certified predictions in \(\mathbb{T}\) (see Eq. 8), which is equivalent to Eq. 12.

**Collective certificate for arbitrary perturbations**. Lemma 1 holds for arbitrary perturbations. We only have to consider the perturbations within a prediction's receptive field when evaluating its base certificate. However, when multiple perturbation types are allowed, the base certificate of a prediction \(f_{n}\) is not characterized by a scalar \(p_{n}\), but by its pareto front \(\mathbb{P}^{(n)}\) (see Eq. 5). Let \(\mathbf{P}^{(n)}\in\mathbb{N}_{0}^{[\mathbb{P}^{(n)}]\times 4}\) be a matrix encoding of the set \(\mathbb{P}^{(n)}\). To determine if \(f_{n}\) is robust we can check whether
there is some pareto-optimal point \(\mathbf{P}_{i,:}^{(n)}\) such that the amount of perturbation in \(f_{n}\)'s receptive field matches or exceeds \(\mathbf{P}_{i,:}^{(n)}\) in all four dimensions. This can again be expressed as a MILP (see Eq. 15 to Eq. 23 below).

As before, we use a vector \(\mathbf{t}\) with \(t_{n}=1\) indicating that \(f_{n}\) is not certified by the base certificate. The adversary tries to find a budget allocation (parameterized by \(\mathbf{b}_{\mathbf{X}_{\text{add}}},\mathbf{b}_{\mathbf{X}_{\text{del}}}\) and \(\mathbf{B}_{\mathbf{A}}\)) that minimizes the number of robustly certified predictions in \(\mathbb{T}\) (see Eq. 15). Eq. 20 and Eq. 21 ensure that the budget allocation is consistent with the global budget parameters characterizing \(\mathbb{B}_{\mathcal{G}}\). The value of \(t_{n}\) is determined by the following constraints: First, Eq. 17 to Eq. 19 ensure that \(Q_{\mathcal{D},d}^{(n)}\) is only set to \(1\) if the local perturbation matches or exceeds the pareto-optimal point corresponding to row \(p\) of \(\mathbf{P}^{(n)}\) in dimension \(d\). The constraints in Eq. 16 implement logic operations on \(\mathbf{Q}^{(n)}\): Indicator \(s_{p}^{(n)}\) can only be set to \(1\) if \(\forall d\in\{1,2,3,4\}:Q_{p,d}^{(n)}=1\). Indicator \(t_{n}\) can only be set to \(1\) if \(\exists p\in\{1,\ldots,|\mathbb{P}^{(n)}|\}:s_{p}^{(n)}=1\). Combined, these constraints enforce that if \(t_{n}=1\), there must be some point in \(\mathbb{P}^{(n)}\) that is exceeded or matched by the amount of perturbation in all four dimensions.

\[\min_{(\mathbf{Q}^{(n)},\mathbf{s}^{(n)})_{n=1}^{N},\mathbf{b}_{\mathbf{X}_{\text{add }}},\mathbf{b}_{\mathbf{X}_{\text{del}}},\mathbf{B}_{\mathbf{A}},\mathbf{t}}|\mathbb{T}|-\sum_{n \in T}t_{n}\] (15) s.t. \[||\mathbf{s}^{(n)}||_{1}\geq t_{n},\qquad Q_{p,d}^{(n)}\geq s_{p}^{(n )}, \tag{16}\] \[(\mathbf{b}_{\mathbf{X}_{\text{add}}})^{T}\mathbf{\psi}^{(n)}\geq Q_{i,1}^{(n )}P_{p,1}^{(n)},\qquad(\mathbf{b}_{\mathbf{X}_{\text{del}}})^{T}\mathbf{\psi}^{(n)}\geq Q_ {p,2}^{(n)}P_{p,2}^{(n)},\] (17) \[\sum_{m,m^{\prime}\leq N}(1-A_{m,m^{\prime}})(\mathbf{\Psi}^{(n)} \odot\mathbf{B}_{\mathbf{A}})_{m,m^{\prime}}\geq Q_{p,3}^{(n)}P_{p,3}^{(n)},\] (18) \[\sum_{m,m^{\prime}\leq N}A_{m,m^{\prime}}(\mathbf{\Psi}^{(n)}\odot \mathbf{B}_{\mathbf{A}})_{m,m^{\prime}}\geq Q_{p,4}^{(n)}P_{p,4}^{(n)},\] (19) \[||b_{\mathbf{X}_{\text{add}}}||_{1}\leq r_{\mathbf{X}_{\text{add}}},\qquad ||b_{\mathbf{X}_{\text{add}}}||_{1}\leq r_{\mathbf{X}_{\text{del}}},\] (20) \[\sum_{(i,j):A_{i,j}=0}B_{\mathbf{A}_{i},j}\leq r_{\mathbf{A}_{\text{add}} },\qquad\sum_{(i,j):A_{i,j}=1}B_{\mathbf{A}_{i},j}\leq r_{\mathbf{A}_{\text{del}}},\] (21) \[\mathbf{s}^{(n)}\in\{0,1\}^{|\mathbb{P}^{(n)}|},\qquad\mathbf{Q}^{(n)} \in\{0,1\}^{|\mathbb{P}^{(n)}|\times 4}\qquad\mathbf{t}\in\{0,1\}^{N}\] (22) \[\mathbf{b}_{\mathbf{X}_{\text{add}}},\mathbf{b}_{\mathbf{X}_{\text{del}}}\in \mathbb{N}_{0}^{N},\qquad\mathbf{B}_{\mathbf{A}}\in\{0,1\}^{N\times N}. \tag{23}\]

**LP-relaxation.** For large graphs, finding an optimum to the 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>t_{n}>0\)). The relaxation yields a linear program, which can be solved much faster.

**Tightness for randomized smoothing.** One recent method for robustness certification is randomized smoothing (Cohen et al., 2019). In randomized smoothing, a (potentially non-deterministic) base classifier \(h:\mathbb{X}\mapsto\mathbb{Y}\) that maps from some input space \(\mathbb{X}\) to a set of labels \(\mathbb{Y}\) is transformed into a smoothed classifier \(g(x)\) with \(g(x)=\operatorname*{argmax}_{y\in\mathbb{Y}}\Pr\left[h(\phi(x)=y\right]\), where \(\phi(x)\) is some randomization scheme parameterized by input \(x\). For the smoothed \(g(x)\) we can then derive probabilistic robustness certificates. Randomized smoothing is a black-box method that only depends on \(h\)'s expected output behavior under \(\phi(x)\) and does not require any further assumptions. Building on prior randomized smoothing work for discrete data by Lee et al. (2019), Bojchevski et al. (2020) propose a smoothing distribution and corresponding certificate for graphs. Using their method as a base certificate to our collective certificate, the resulting (non-relaxed) certificate is tight. That is, our mixed-integer 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 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\sum_{n=1}^{N}|\mathbb{P}^{(n)}|+8N+2e+5\)
constraints and \(5\sum_{n=1}^{N}|\mathbb{P}^{(n)}|+4N+e\) variables, where \(e\) are the number of edges in the unperturbed graph (we disallow edge additions). For single-type perturbations we have \(\mathcal{O}(N+e)\) terms, linear in the number of nodes and edges. The relaxed LP takes at most a 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 naive combination of base certificates that sums over perturbations in the entire graph. A non-obvious limitation is 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 \(\mathbf{\psi}^{(n)}\) and \(\mathbf{\Psi}^{(n)}\) correspond to the union of all achievable receptive fields. Take for example a two-layer message-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 a graph such that \(m\) is in \(f_{n}\) receptive field. We thus have to treat the \(f_{n}\) 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 (Zugner & Gunnemann, 2020) edge addition is inherently harder and less relevant in practice.

## 5 Experimental evaluation

**Experimental setup.** We evaluate the proposed approach by certifying node classifiers on multiple 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 different random initializations and data splits. Unless otherwise specified, we do not impose any local budget constraints or constraints on the number of attacker-controlled nodes. We compare the proposed method with the naive collective certificate, which simply counts the number of predictions 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 [https://www.daml.in.tum.de/collective-robustness/](https://www.daml.in.tum.de/collective-robustness/). 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); Bojchevski & Gunnemann (2018); \(N=2810\), \(7981\) edges, \(7\) classes), Citeseer (Sen et al. (2008); \(N=2110\), \(3668\) edges, \(6\) classes), PubMed (Namata et al. (2012); \(N=19717\), \(44324\) edges, \(3\) classes), Reuters-215784 (\(N=862\), 2586 edges, \(4\) classes) and WebKB (Craven et al. (1998); \(N=877\), \(2631\) edges, \(5\) classes). The graphs for the natural language corpora Reuters and WebKB are constructed using the procedure described in Zhou & Vorobeychik (2020), resulting in 3-regular graphs. We use five types of classifiers: Graph convolution networks (GCN) (Kipf & Welling, 2017), graph attention networks (GAT) (Velickovic et al., 2018), APPNP (Gasteiger et al., 2019), robust graph convolution networks (RGCN) (Zhu et al., 2019) and soft 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 Zugner & Gunnemann (2019) (convex relaxations of network nonlinearities, attribute perturbations). We provide a summary of all hyperparameters in Section F.

Footnote 4: Distribution 1.0, available from [http://www.daviddlewis.com/resources/testcollections/reuters21578](http://www.daviddlewis.com/resources/testcollections/reuters21578)

**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 in certified ratio (visualized as shaded areas in 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. \(\bar{r}=(\sum_{r=0}^{\infty}\omega(r)*r/\sum_{r=0}^{\infty}\omega(r))\), where \(\omega(r)\) 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 randomized smoothing as the base certificate, we evaluate the certified ratio of GCN classifiers for varying global attribute deletion budgets \(r_{\mathbf{X}_{\text{del}}}\) on the citation graphs Cora, Citeseer and PubMed (for Reuters and WebKB, see Section A). The remaining global budget parameters are set to \(0\). Fig. 2 shows that for all datasets, the proposed method yields significantly larger certified ratios than the naive certificate and can certify robustness for much larger \(r_{\mathbf{X}_{\text{del}}}\). The average certifiable radius
on Citeseer increases from \(7.18\) to \(351.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.0\,\mathrm{s}\), \(0.29\,\mathrm{s}\) and \(336.41\,\mathrm{s}\). Interestingly, the base certificate yields the highest certifiable ratios on Cora, while the collective certificate yields the highest certifiable ratios on PubMed. We attribute this to differences in graph structure, which are explicitly taken into account by the proposed certification procedure.

**Simultaneous attribute and graph perturbations.** To evaluate the multi-dimensional version of the certificate, we visualize the certified ratio of randomly smoothed GCN classifiers for different combinations of \(r_{\mathbf{X}_{\text{\tiny{del}}}}\) and \(r_{\mathbf{A}_{\text{\tiny{del}}}}\) on Cora-ML. For an additional experiment on simultaneous attribute additions and deletions, see Section A. Fig. 4 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\,\mathrm{\char 37}\) the naive certificate 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\,\mathrm{s}\).

**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. In Fig. 4 we compare the certified collective robustness of GAT, GCN, and APPNP, using the sparse smoothing certificate on Cora-ML.5 Better base certificates translate into better collective certificates. For an additional experiment on the benefits of robust classifier architectures RGCN and SMA, see Section A.

Figure 4: Comparison of certified ratios for GAT, GCN and APPNP on Cora-ML under varying \(r_{\mathbf{X}_{\text{\tiny{del}}}}\) for our (solid lines) and the naïve (dotted lines) collective certificate.
**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 Zugner & Gunnemann (2019). We certify a GCN model for varying \(r_{\mathbf{X}_{\text{\tiny{adcl}}}}\) on Cite-seer. Unlike randomized smoothing, this base certificate models local budget constraints. Using the default in the base certificate'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. 6 shows that the proposed collective certificate is again significantly stronger. The average certified radius \(\hat{r}\) increases from \(17.12\) to \(971.36\). The average wall-clock time per certificate is \(0.39\,\mathrm{s}\).

**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, \(r_{\mathbf{A}_{\text{\tiny{adcl}}}}\), and the local budgets \(\mathbf{r}_{\mathbf{A}_{\text{\tiny{adcl}},\text{\tiny{loc}}}}\). 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_{\mathbf{A}_{\text{\tiny{adcl}}}}=1000\). In Fig. 7, we fix a relatively large local budget of \(16\) edge deletions per node (only \(\sim 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 \(r_{\mathbf{A}_{\text{\tiny{adcl}}}}\) 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 attacker-controlled nodes. It is independent of the global budget.

## 6 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 a 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 a 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 Acknowledgements

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 no. 01IS18036B, and the TUM International Graduate School of Science and Engineering (IGSSE), GSC 81.