# Randomized Message-Interception Smoothing: Gray-box Certificates for Graph
Neural Networks

Yan Scholten$1$, Jan Schuchardt$1$, Simon Geisler$1$,
Aleksandar Bojchevski$2$ & Stephan Günnemann$1$
{y.scholten, j.schuchardt<EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>
$1$Dept. of Computer Science & Munich Data Science Institute, Technical
University of Munich
$2$CISPA Helmholtz Center for Information Security

###### Abstract

Randomized smoothing is one of the most promising frameworks for certifying
the adversarial robustness of machine learning models, including Graph Neural
Networks (GNNs). Yet, existing randomized smoothing certificates for GNNs are
overly pessimistic since they treat the model as a black box, ignoring the
underlying architecture. To remedy this, we propose novel gray-box
certificates that exploit the message-passing principle of GNNs: We randomly
intercept messages and carefully analyze the probability that messages from
adversarially controlled nodes reach their target nodes. Compared to existing
certificates, we certify robustness to much stronger adversaries that control
entire nodes in the graph and can arbitrarily manipulate node features. Our
certificates provide stronger guarantees for attacks at larger distances, as
messages from farther-away nodes are more likely to get intercepted. We
demonstrate the effectiveness of our method on various models and datasets.
Since our gray-box certificates consider the underlying graph structure, we
can significantly improve certifiable robustness by applying graph
sparsification.111Project page: https://www.cs.cit.tum.de/daml/interception-
smoothing

##  1 Introduction

The core principle behind the majority of Graph Neural Networks (GNNs) is
message passing – the representation of a node is (recursively) computed based
on the representations of its neighbors (gilmer2017neural). This allows for
information to propagate across the graph, e.g. in a k-layer GNN the
prediction for a node depends on the messages received from its k-hop
neighborhood. With such models, if an adversary controls a few nodes in the
graph, they can manipulate node features to craft adversarial messages that in
turn change the prediction for a target node.

Such feature-based adversarial attacks are becoming significantly stronger in
recent years and pose a realistic threat (ma2020towards; zou2021tdgia):
Adversaries may arbitrarily manipulate features of entire nodes in their
control, for example in social networks, public knowledge graphs and graphs in
the financial and medical domains. Detecting such adversarial perturbations is
a difficult unsolved task even beyond graphs (carlini2017adversarial), meaning
such attacks may go unnoticed.

How can we limit the influence of such adversarial attacks? We introduce a
simple but powerful idea: _intercept_ adversarial messages. Specifically, we
propose message-interception smoothing where we randomly delete edges and/or
randomly ablate (mask) nodes, and analyze the probability that messages from
adversarially controlled nodes reach the target nodes. By transforming any
message-passing GNN into a smoothed GNN, where the prediction is the majority
vote under this randomized message interception, we can provide robustness
certificates (see Figure 1).

Experimentally we obtain significantly better robustness guarantees compared
to previous (smoothing) certificates for GNNs (compare Section
LABEL:sec:experiments). This improvement stems from the fact that our
certificates take the underlying architecture of the classifier into account.
Unlike previous randomized smoothing certificates which treat the GNN as a
black-box, our certificates are _gray-box_. By making the certificate message-
passing aware we partially open the black-box and obtain stronger guarantees.

Our approach is also in contrast to white-box certificates that apply only to
very specific models. For example, zuegner2019certifiable only certify the GCN
model (kipf2017semi). While newly introduced GNNs require such certificates to
be derived from scratch, our approach is model-agnostic and flexible enough to
accommodate the large family of message-passing GNNs.

We evaluate our certificates on node classification datasets and analyze the
robustness of existing GNN architectures. By applying simple graph
sparsification we further increase the certifiable robustness while retaining
high accuracy, as sparsification reduces the number of messages to intercept.
In stark contrast to previous probabilistic smoothing-based certificates for
GNNs, our certificates require only a few Monte-Carlo samples and are more
efficient: For example, we can compute certificates on Cora-ML in just 17
seconds and certify robustness against much stronger adversaries than previous
smoothing-based certificates (bojchevski2020efficient) that take up to 25
minutes.

In short, our main contributions are:

  * •

The first gray-box smoothing-based certificates for GNNs that exploit the
underlying _message-passing_ principle for stronger guarantees.

  * •

Novel randomized smoothing certificates for strong threat models where
adversaries can arbitrarily manipulate features of multiple nodes in their
control.

Adversarial nodeAblated nodeAdversarial messageIntercepted messageDeleted
edge$v$Receptive field (2 layers)$v$$v$$v$…Adversarial messages intercepted in
2 out of 3 random samples Figure 1:  Randomized message-interception
smoothing: We model adversaries that can arbitrarily manipulate features of
multiple nodes in their control (red) to alter the predictions for a target
node $v$. We intercept messages (gray) by randomly deleting edges and/or
ablating (mask) all features of entire nodes. Our certificates are based on
the majority vote under this randomized message interception.

##  2 Preliminaries and Background

Threat model. We develop certificates for feature perturbations given evasion
threat models. Specifically, we model adversaries that attack GNNs by entirely
perturbing attributes of a few $\rho$ nodes in the graph at inference. Given
an attributed graph $G=(\bm{A},\bm{X})\in\mathbb{G}$ encoded via adjacency
matrix $\bm{A}\in\\{0,1\\}^{n\times n}$ and feature matrix
$\bm{X}\in\mathbb{R}^{n\times d}$ with $n$ nodes and $d$ features, we formally
define the threat model of feature perturbations as a ball centered at a given
graph $G=(\bm{A},\bm{X})$:

$B_{\rho}(G)\triangleq\\{G^{\prime}=(\bm{A}^{\prime},\bm{X}^{\prime})\mid\bm{A}=\bm{A^{\prime}},\delta(G,G^{\prime})\leq\rho\\}$

where
$\delta(G,G^{\prime})\triangleq\sum_{v=1}^{n}\bm{1}_{\bm{x}_{v}\neq\bm{x}^{\prime}_{v}}$
denotes the number of nodes whose features differ in at least one dimension
when comparing the clean graph $G$ and the perturbed graph $G^{\prime}$.
Intuitively, this means adversaries control up to $\rho$ nodes in the graph
and can arbitrarily manipulate node features.

Graph neural networks. We design robustness certificates for GNNs that
instantiate the so-called message-passing framework (gilmer2017neural). The
message-passing framework describes a large family of GNN architectures that
are based on the local aggregation of information from neighboring nodes in
the graph. To compute a new representation $\bm{h}_{v}^{(\ell)}$ of node $v$,
each message-passing layer $\Psi^{(\ell)}$ transforms and aggregates the
representations $\bm{h}_{v}^{(\ell-1)}$ and $\bm{h}_{u}^{(\ell-1)}$ of all
nodes $u$ in the local neighborhood
$\mathcal{N}(v)\triangleq\\{u\mid\bm{A}_{uv}=1\\}$ of node $v$.

We can formally describe a message-passing layer as follows:
$\bm{h}_{v}^{(\ell)}\triangleq\Psi_{u\in\mathcal{N}(v)\cup\\{v\\}}^{(\ell)}\left(\bm{h}_{v}^{(\ell-1)},\bm{h}_{u}^{(\ell-1)}\right)$.
For node classification, message-passing GNNs with $k$ GNN-layers can be
described as parametrized functions
$f:\mathbb{G}\rightarrow\\{1,\ldots,C\\}^{n}$ that assign each node $v$ in
graph $G$ class
$f_{v}(G)\triangleq\operatorname*{\arg\\!\max}_{c}\bm{h}_{v,c}^{(k)}$, where
$\bm{h}_{v}^{(0)}\triangleq\bm{x}_{v}\in\mathbb{R}^{d}$ denotes the input and
$\bm{h}_{v}^{(k)}\in\mathbb{R}^{C}$ the final representation of node $v$.

Randomized smoothing. Our robustness certificates for GNNs build upon the
randomized smoothing framework (cohen2019certified; lecuyer2019certified):
Given any base classifier $f$, for example a message-passing GNN, we can build
a “smoothed” classifier $g$ that classifies randomly perturbed input samples,
and then takes the “majority vote” among all predictions. The goal is to
construct a smoothed classifier that behaves similar to $f$ (for example in
terms of accuracy) and for which we can prove (probabilistic) robustness
certificates.

Randomized ablation (levine2020robustness) is a smoothing-based certificate
that “ablates” the input: Unlike in randomized smoothing where the input is
randomly perturbed (e.g. by adding Gaussian noise to images), in randomized
ablation the input is randomly masked, for example by replacing parts of the
input with a special ablation token that “hides” the original information. If
the perturbed input is masked for the majority of predictions, we can issue
certificates for the smoothed classifier $g$.

##  3 Randomized Message-Interception Smoothing for Graph Neural Networks

The main idea of our gray-box smoothing certificates is to intercept messages
from perturbed nodes by (1) deleting edges to disconnect nodes, and/or (2)
ablating nodes to mask their features (cf. Figure 1).

To implement this we introduce two independent smoothing distributions
$\phi_{1}(\bm{A})$ and $\phi_{2}(\bm{X})$ that randomly apply these changes to
the input graph: The first smoothing distribution $\phi_{1}(\bm{A})$ randomly
deletes edges in the adjacency matrix ($1\rightarrow 0$) with probability
$p_{d}$. The second smoothing distribution $\phi_{2}(\bm{X})$ randomly ablates
all features of nodes with probability $p_{a}$ by replacing their feature
representations with a fixed representation token $\bm{t}\in\mathbb{R}^{d}$
for ablated nodes. The ablation representation $\bm{t}$ is a trainable
parameter of our smoothed classifier and can be optimized during training.
Introducing two independent smoothing distributions is important since our
base classifiers $f$ are GNNs, which behave differently under structural
changes in the graph than to feature ablation of nodes in practice.

We use this message-interception smoothing distribution
$\phi(G)\triangleq(\phi_{1}(\bm{A}),\phi_{2}(\bm{X}))$ to randomly sample and
then classify different graphs with a message-passing GNN $f$. Finally, our
smoothed classifier $g$ takes the majority vote among the predictions of $f$
for the sampled graphs $\phi(G)$. We formally describe our smoothed classifier
$g$ as follows:

$g_{v}(G)\triangleq\operatorname*{\arg\\!\max}_{y\in\\{1,\ldots,C\\}}p_{v,y}(G)\quad\quad
p_{v,y}(G)\triangleq p(f_{v}(\phi(G))=y)$

where $p_{v,y}(G)$ denotes the probability that the base GNN $f$ classifies
node $v$ in graph $G$ as class $y$ under the smoothing distribution
$\phi(G)=(\phi_{1}(\bm{A}),\phi_{2}(\bm{X}))$.

##  4 Provable Gray-box Robustness Certificates for Graph Neural Networks

We derive provable certificates for the smoothed classifier $g$. To this end,
we develop a condition that guarantees $g_{v}(G)=g_{v}(G^{\prime})$ for any
graph $G^{\prime}\in B_{\rho}(G)$: We make the worst-case assumption that
adversaries alter the prediction for a target node whenever it receives at
least one message from perturbed nodes. Let $E$ denote the event that at least
one message from perturbed nodes reaches a target node $v$. Then the
probability $\Delta\triangleq p(E)$ quantifies how much probability mass of
the distribution $p_{v,y}(G)$ over classes $y$ is controlled by the worst-case
adversary:

######  Proposition 1.

Given target node $v$ in graph $G$, and adversarial budget $\rho$. Let $E$
denote the event that the prediction $f_{v}(\phi(G))$ receives at least one
message from perturbed nodes. Then the change in label probability
$|p_{v,y}(G)-p_{v,y}(G^{\prime})|$ is bounded by the probability $\Delta=p(E)$
for all classes $y\in\\{1,\ldots,C\\}$ and graphs $G^{\prime}$ with
$G^{\prime}\in B_{\rho}(G)$: $|p_{v,y}(G)-p_{v,y}(G^{\prime})|\leq\Delta$.
Proof sketch (Proof in LABEL:appendix:certificateProofs). Whenever we
intercept all adversarial messages, adversaries cannot alter the prediction.
Thus $|p_{v,y}(G)-p_{v,y}(G^{\prime})|$ is bounded by $\Delta$. $\square$

Note that we derive an upper bound on $\Delta$ in LABEL:sec:practical.

We first consider the special case of node ablation smoothing, discuss its
relation to randomized ablation for image classifiers (levine2020robustness),
and then we derive our provably stronger guarantees for the general case of
message-interception smoothing.

Special case of node ablation smoothing. For the special case of node feature
ablation smoothing only ($p_{d}=0$), we can directly determine the probability
$\Delta$ (Proof in LABEL:appendix:nodeAblation):