Randomized Message-Interception Smoothing: Gray-box Certificates for Graph Neural Networks
Authors: Yan Scholten
Jan Schuchardt
Simon Geisler
Aleksandar Bojchevski
Stephan Günnemann
Venue: NeurIPS 2022 Accept (2022)
Keywords: Robustness Certificates
Adversarial Robustness
Randomized Smoothing
Graph Neural Networks

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.

Randomized MessageInnterepttonn Smoothing: Gray-box Certificates for Graph Neural Networks
Yan Scholten's ' Jan Schuchardt', Simon Geisler', Aleksandar Bojchevski & Stephan Günnemann' ly scholten, J.shhuhhrrdt, s e.geisler)@tum de boj cojchesskiciisp de, s g.guunnmmanntumm de
1 Dept. of Computer Science & Munich Data Science Institute. Technical University of Munich CISPA Helmholtz Center for Information Security
Abstract
Randomized smoothing is 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, igmoring 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, certify robustness 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 various models and datascts. Since our gray-box certificates consider the underlying graph structure, we can significantly improve certifiable robustness by applying graph sparsification.'
Introduction
The core principle behind the majority of Graph Neural Networks (GNNs) is message passing the representation of node is (recursively) computed based on the representations of its neighbors (Gilmer et al., 2017). This allows for information propagate across the graph, e.g. k-layer GNN the prediction for node depends on the messages received from its k-hop neighborhood. With such models, if an adversary controls few nodes in the graph, they can manipulate node features to craft adversarial messages that in turn change the prediction for target node.
Such feature- based adversarial attacks are becoming significantly stronger in recent years and pose realistic threat (Ma et al., 2020; Zou et al., 2021): 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 beyond graphs (Carlini and Wagner, 2017), 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, propose message-intesd intercepttronninnn 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).
Project page: https://wart cit.
cit.tum. wtt.tttw...ddmmeee
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Adversarial node O
Ablated node +- Adversarial message +- Intercepted message -- Deleted edge
Receptive field (2 layers)
Adversarial messages intercepted in out of 3 random samples
Figure 1: Randomized message- intesaggeiiteretttion smoothing: We model adversaries that arbitrarily manipulate features 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.
Experimentally we obtain significantly better robustness guarantees compared to previous (smoothing) certificates for GNNs (compare Section 7). 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 black-box, our certificates are gray-box. By making the certificate message-passe 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, Zigner and Günnemann (2019) only certify the GCN model (Kipf and Welling, 2017). While newly introduced GNNs require such certificates to be derived from scratch, approach is model-agnostic and flexible enough to accommodate the large family of message-passing GNNs.
We evaluate our certificates 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, sparsification reduces the number of messages to intercept. In stark contrast to previous probabilistic amoothing-basee certificates for GNNs, our certificates require only few Monte-Care CCrlo samples and more efficient: For example, Cora-ML in just 17 seconds and certify robustness against much stronger adversaries than previous smoothing based certificates (Bojchevski al., 2020) that take up 25 minutes.
compute certificates
In short, our main contributions are:
The first gray-box smoothing-bar certificates for GNNs that exploit the underlying message-paxsing principle for stronger guarantees.
Novel randomized smoothing certificates for strong threat models where adversaries can arbitrarily manipulate features of multiple nodes in their control.
2 Preliminaries and Background
Threat model. We develop certificates for feature perturbations given evasion threat models. Specifi- cally, we model adversaries that attack GNNs by entirely perturbing attributes of few p nodes in the graph at inference. Given an attributed graph G = (A, X) E G encoded via adjacency matrix A E (0, j and feature matrix X E Rnxdd xd with n nodes and features, we formally define the threat model of feature perturbations
ball centered
given graph G (A, X):
(G) & (G' = (A', X') A = A', 8(G G*) S p}
1 1z denotes the number of nodes whose features differ at least one dimension when comparing the clean graph G and the perturbed graph G'. Intuitively, this means adversaries control up to P nodes in the graph and can arbitrarily manipulate node features.
where (G, G') A E
Graph neural networks. We design robustness certificates for GNNs that instantiate the so-called message-passing framework (Gilmer et al., 2017). The passsing framework describes 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 h of node v, each message-passinn layer (E) transforms and aggregates the representations h (8-1) and h (É-1) of all nodes in the local neighborhood (v)) {u Aur 1} of node v.

---

We can formally describe message-passing layer as follows: h.? & u For node classification, message-passsnng GNNs with & GNN-layers can be described as parametrized functions/ f - fi...., C}"² that assign each node e in graph G class fo(G) å argmax, h where h _ De E IR denotes the input and h E IRC the final representation of node v.
(h!-") h k)
Randomized smoothing. Our robustness certificates for GNNs build upon the randomized smoothing framework (Cohen et al., 2019; Lecuyer et al., 2019): Given any base classifier f. for example a message-passing GNN, we can build "smoothed" classifier y 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 / (for example in terms of accuracy) and for which we can prove (probabilistic) robustness certificates.
Randomized ablation (Levine and Feizi, 2020b) is smoothing based certificate that "ablates" the in- put: Unlike in randomized smoothing where the input is randomly perturbed (e.g. by adding Gaussian noise 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-Intereeple
Smoothing for Graph Neural Networks
The main idea of our gray-box smoothing certificates is to intercept messages from perturbed nodes by (I) deleting edges to disconnect nodes, and/or (2) ablating nodes mask their features (cf. Figure 1).
To implement this we introduce two independent smoothing distributions Φ1 (A) and (xxX) that randomly apply these changes to the input graph: The first smoothing distribution @1 (A) randomly deletes edges in the adjacency matrix (1 -> 0) with probability pa. The second smoothing distribution 2 (X) randomly ablates all features of nodes with probability Pa by replacing their feature represen- tations with fixed representation token t E Rd for ablated nodes. The ablation representation 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 sessage-interception smoothing distribution (G) & (Ø1 dz), (X)) to randomly sample and then classify different graphs with a message-passinng passing GNN f. Finally, our smoothed classifier g takes the majority vote among the predictions of f for the sampled graphs ((G). We formally describe our smoothed classifier g as follows:
ge(GG) A argmax (G) (E......c)
(G) _ p(fo(((G)) = =y)
where (G) denotes the probability that the base GNN f classifies node in graph G as class y under the smoothing distribution o(G) = (01 (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 condition that guarantees (G) g.'(G)) for any graph G' E (G): We make the worst-case assumption that adversaries alter the prediction for target node whenever 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 A P(E) quantifies how much probability mass of the distribution Pr.,((r over classes y is controlled by the worst-case adversary:
Proposition 1. Given target node in graph G, and adversarial budget p. Let E denote the event that the prediction (o)) receives at least one message from perturbed nodes. Then the change in label probability 'pu,y(C Po.y (G') is bounded by the probability A = p(E) for all classes y E (1,..., C) and graphs G' with G' E Bp) (G) - Po.y((")) S
Proof sketch (Proof in Appendix A). Whenever intercept all adversarial messages, adversaries cannot alter the prediction. Thus (Pr.g (G) (G') is bounded by A.
Note that we derive an upper bound on A in Section 5.
3

---

We first consider the special case of node ablation smoothing, discuss its relation to randomized ablation for image classifiers (Levine and Feizi, 2020b), and then we derive our provably stronger guarantees for the general case of message-inteereetionn smoothing.
Special case of node ablation smoothing. For the special of node feature ablation smoothing only (pa = 0), we can directly determine the probability A (Proof in Appendix B): Proposition 2. For node fealure ablation smoothing only (pa 0), we have A = pe-
In this special case, our certificates for GNNs are theoretically related to the randomized ablation certificates for image classifiers (Levine and Feizi, 2020b). We could apply their smoothing distribu- tion GNNs by randomly ablating features of entire nodes, instead of pixels in an image. However, their approach is specifically designed for image classifiers and comes with serious shortcomings when applied to GNNs. Notably, our robustness cetificates are provably tighter and experimentally stronger even in this special
without edge deletion smoothing (pa 0): Given that A L denotes the bounding constant as defined by Levine and Feizi (2020b), we show < A 4 in Appendix B. We carefully discuss such differences with more technical details in Appendix B. Most importantly, their certificate applied to GNNs ignores the underlying graph structure.
General case of rresage-interceptioon smoothing. In contrast, our message-interceptii certifi- cates are specifically designed for graph-structured data, message-passing aware, and consider the interception of messages via edge deletion as follows:
Consider fixed target node in the graph. The formal condition for intercepting messages from fixed target node to itself is 62 (xx)) = t, since we only intercept messages from the target node to the target node itself we ablate its features. To model the interception of messages from perturbed nodes IB other than the target node, we take the graph structure A into account: We consider all simple paths P (ci....., ..) i S k} from perturbed nodes w E IB to target node u of length at most (where & is the number of GNN layers). Intuitively, if any edge on path p E Pk is deleted, the features of to are ablated, messages via path get intercepted. If all messages from perturbed nodes get intercepted, adversaries cannot alter the prediction for the target node (Proof Appendix A):
Lemma 1. Given a fixed larget node and perturbed nodes B in the graph with & IB. Then fo()(G)) Jo(o(G") )) for any graph G' BB) if
Vw E B: (Vp E ph. (i.j) E (p:)) = 0) V (d2(xw) =
Since k-layer message-passineg GNNs aggregate information over local neighborhoods, only features of nodes in the receptive field affect the prediction for target node (only via paths with length of at most to v). For any perturbed node w E B outside the receptive field we have pk and the message-interception condition of Lemma is always fulfilled.
In practice, however, we do not know which nodes in the graph are controlled by the adversary. To account for this, we assume adversaries control nodes indicated by Pa E {0, 1}" that maximize the probability of the event (p.)) that target node e receives perturbed messages:
Theorem 1. The worst-case change in label probability (Pex(G) (G') is bounded by
== max P (EE(p))
1leelloSp
for all classes y E (I,...,C) and any graph G' E (G)
Proof in Appendix A. Finally, we provide conservative robustness certificates for the smoothed classifier g by exploiting that perturbed nodes are disconnected and/or ablated and cannot send messages for the majority of predictions:
Corollary (Multi-class certificate). Given A as defined in Proposition 1. Then we can certify the robustness gu (G) = (G"))))ff for any graph G' E (G) if
Poar (G) A max P (G) V$4"
where y² & (G) denotes the majority class, and ÿ the follow-up (second best) class.
Proof in Appendix A. We also provide certificate for binary node classification in Appendix A.
We consider simple paths (all nodes appear only once). since we only receive perturbed messages via more complex paths iff' we receive perturbed messages via the simple part of the complex path.

---

(a)
(b)
.2
8
8
.2
P2
4
.6
1
.6
.4
.8
.2
2
8
0
0
0
6
2 4
8
0
2
66
8
Pa
Figure 2: Single source bounding constant A for different edge deletion probabilities pa and node
feature ablation probabilities Pa- White isolines indicate A; = 0.5 and separate the theoretically certifiable region (A, < 0.5) from the uncertifiable region (A, 2 0.5). (a) For the target node, Pa does not affect A, (b) Direct neighbor of target node, single edge. (c) Second-hop neighhor, single
path (two edges). (a-c) More distant nodes have larger theoretically certifiable regions.
5 Practical Interception Smoothing Certificates
Message-interception certificates constitute challenges in practice: (I) computing the bounding constant A for arbitrary graphs and (2) computing the label probabilities Pe.y (G) and Pv.g (G). We address the first problem by providing upper bounds on A (i.e. lower bounds on the certifiable robustness). For the second problem we follow existing literature and estimate the smoothed classifier.
Lower bound certifiable robustness. Computing A of Theorem poses problems: First, finding the worst-case nodes in arbitrary graphs involves a challenging optimization over the powerset of nodes in the receptive field. Second, computing the probability p( (()(p)) receive perturbed messages is challenging even for fixed Pv. since in general, it involves evaluating the inclusion- exclusion principle (Appendix C). We can compute A exactly only for special cases such as small or tree-structured receptive fields (Appendix D). Notwithstanding the challenges, we provide practical upper bounds on A. Instead of assuming fixed P.. we solve both problems regarding A at once and directly bound the maximum over all possible Pe by assuming independence between paths. Due to Corollary 1, any upper bound on result in lower bounds on the certifiable robustness.
We first derive an upper bound on for single perturbed node, and then generalize to multiple nodes. Let Exr denote the event that the target node v receives messages from node w, and A - p( (E.)) Note in the special case of the target node the target node U are used for the prediction independent any edges. For any w * in the receptive field
we just have A
Pa. since the features æ. of
derive the following upper bound for single sources (Proof in Appendix E):
Theorem (Single Source Multiplicative Bound), Given target node u and source node w + v in the receptive field of a k-layer message spauggnn GNN with respect to Let pk denote all simple puths from w to of length at most k in graph G. Then Aw S Aw for:
A 2
1
II
(1-(1-pa))) (1 Pa)
qEPt
where igl denotes the number of edges on the simple path 9 Pk from w to v.
We visualize Aw for different Pa and Pa in Figure 2. The upper bound for single sources is tight for one- and two-layer GNNs (A = A.). since then all paths from single source to the target node are independent (Appendix E). The single source multiplicative bound on A can only be used certify radius of 1. For multiple nodes (p > 1), generalize Theorem 2 as follows:
Theorem (Generalized multiplicative bound). Assume an adversarial budget of p nodes and let
A A.....,4 Ap denote the largest D for nodes in the receptive field. Then we have A < AM for
AM - 1
Proof Appendix F. Notably, the multiplicative bound tighter than a union bound. We specifically address the approximation emror in detail in Appendix F.
5

---

Estimating the smoothed classifier in practice. Computing the probabilities Pv.y (G) and Po.g (G) exactly is challenging in practice. We instead estimate them similar to previous work by drawing Monte-Carlo samples from @ (Cohen et al., 2019; Levine and Feizi, 2020b; Bojehevski et al., 2020). We first identify the majority class y/ and follow-up class ÿ using a few samples. We then draw more samples to estimate a lower bound Po.y (G) on Pe.y" (G) and an upper bound pe.ū (G) on (o.) We use the Supper-Pearsone Bernoulli confidence interval and apply Bonferroni correction to ensure that the bounds hold simultaneously with significance level (with probability of at least 1-a) a.) Moreover, smoothed classifier abstains from predicting if Po.y (G) Pv. (G), meaning if the estimated probabilities are too similar. We experimentally analyze abstained predictions in Appendix H.
Practical robustness certificates. Finally, our robustness certificates also hold when bounding A and the label probabilities as the following Corollary shows (Proof in Appendix A):
Corollary 2. We guarantee gu (G) (o"))) with probability of at least 1 for any G' E B,( if Pu.y (G) A Po.y (G) + A, where y" denotes the majority class, and ÿ the follow-up class.
6 Discussion
Our certificates require knowledge about the graph structure A and can only account for structure perturbations if the perturbed adjacency matrix A' is known. While adversarial edge deletion potentially increases robustness (due to less messages to intercept), adversaries could arbitrarily increase the number of messages via edge insertion. Moreover, the number of simple paths in the graph can be huge. We argue, however, that (1) graphs are usually sparse, (2) the number of paths can be reduced via sparsification, and (3) we have compute paths only once for each graph.
Limitations of ablation certificates. Since the probability to receive messages from perturbed nodes increases the more nodes are adversarial, A is monotonously increasing in p. Thus, the certifiable radius is bounded independent of the label probabilities (uncertifiable region for A 2 0.5 due to Corollary 1). This bound depends on the graph structure and changes for each target node, but in the case of node feature ablation smoothing we can directly determine the bound (Proof in Appendix I):
Proposition 3. Given fixed Pa O and Pa 0, it is impossible to certify a radius p if Pa S </0.5.
This bound is only determined by the parameters of the smoothing distribution (pa, Pa) and does not depend on the base GNN f. The existence of an upper bound is in stark contrast to certificates whose largest certifiable radius depends on the inverse Gaussian CDF of the label probabilities (Cohen et al., 2019). Such certificates are theoretically tighter than ablation certificates: For example, the base classifier I classifies all samples from & the same (py- 1), they would certify a radius of oc, whereas the radius of ablation-basee certificates is bounded. We leave the development of even stronger gray-box certificates for GNNs to future work.
Limitations of probabilistic certificates. Our certificates are probabilistic and hold with significance level a. Notably, our method still yields strong guarantees for significantly smaller confidence levels (we show additional experiments for varying a in Appendix H). We found that a has just a minor effect on the certificate strength, since increasing it cannot increase the largest certifiable radius, which is theoretically bounded. Recent works also "derandomize" probabilistic certificates, that is they compute the label probabilities exactly (Levine and Feizi, 2020a, 2021). In Appendix J we propose the first derandomization technique that leverages message- paaasng structures. We believe future work can build upon it towards even more efficient derandomization schemes.
Threat model extensions. Notably, edge-deletion smoothing (pa > 0) also yields guarantees for adversarial node insertion and deletion, as disconnected nodes cannot alter the prediction." As discussed above, we can only evaluate such certificates with structural information, that is how inserted/deleted nodes are connected to target nodes: Given clean graphs (as in our evaluation), we know which nodes adversaries could delete. Given perturbed graphs, we know which nodes could have been inserted. Note that although we can technically extend our method to certify adversarial edge deletion, we focus on the novel problem of arbitrary feature manipulations of entire nodes since there are already certificates against edge-modifee modification attacks (Bojchevski et al., 2020).
'w cannot certify node insertion/deletion with feature ablation smoothing, since e.g. new nodes affect the smoothed classifier independent of whether features are ablated or not (unless we delete nodes entirely).

---

7 Experimental Evaluation
We evaluate our certificates for different GNN architectures trained on node classification datasets. Our certificates work in standard transductive learning settings used throughout the literature and we report such results in Appendix H. However, combining transductive learning with an evasion threat model comes with serious shortcomings for the evaluation of certificates, since no separate test data is available. For example, we can usually achieve high accuracy by overfitting a Multi-Layer Perceptron (MLP) to labels predicted by GNNs during training. MLPs do not propagate information through the graph at test time and are robust to adversarial messages. Instead, we evaluate our certificates in semi-supervised inductive learning settings with hold-out test nodes:
Experimental setup. As labelled nodes, we draw 20 nodes per class for training and validation, and 10% of the nodes for testing. We use the labelled training nodes and all remaining unlabeled nodes as training graph, and successively insert (hold-out) validation and test nodes. We train on the training graph, optimize hyperparameters against validation nodes, assume adversaries control nodes at test time, and compute certificates for all test nodes. We also delete edges and ablate node features during training (Appendix G). We use no 1,000 samples for estimating the majority class, Ri = 3,000 samples for certification, and set a = 0.01. We conduct five experiments for random splits and model initializations, and report averaged results including standard deviation (shaded areas in the plots). When comparing settings (e.g. architectures), we run 1,000 experiments for each setting and draw deletion and ablation probabilities from [0, 1] for each experiment (sampling separately for training and inference). Then, we compute dominating points on the Pareto front for each setting. For brevity, we only show points with clean accuracy of at most 5% below the maximally achieved performance.
Datasets and models. We train our models on citation datasets: Cora-ML (Bojchevski and Günne- mann, 2018; 8; McCallum et al., 2000) with 2,810 nodes, 7,981 edges and 7 classes; Citeseer (Sen et al., 2008) with 2,110 nodes, 3,668 edges and 6 classes; and PubMed (Namata et al., 2012) with 19,717 nodes, 44,324 edges and 3 classes. We implement smoothed classifiers for four architectures with two peessage-passing layers: Graph convolutional networks (GCN) (Kipf and Welling, 2017), graph attention networks (GAT and GATv2) (Velickovic et al., 2018; Brody et al., 2022), and soft medoid aggregation networks (SMA) (Geisler et al., 2020). More details in Appendix G. We also compute certificates for the larger graph ogbn-arxiv (Hu et al., 2020) in Appendix H.
Evaluation metrics. We report the classification accuracy of the smoothed classifier on the test set (clean accuracy), and the certified ratio, that is the number of test nodes whose predictions are certifiable robust for given radius. Since all nodes have different receptive field sizes, we also divide the certifiable radius by the receptive field size. The resulting normalized robustness better reflects how much percentage of the "attack surface" (that is the number of nodes the adversary could attack) can be certified. Moreover, we report the area under this (normalized) certified ratio curve (AUCRC). For completeness, we also report the certified accuracy in Appendix H. that the number of test nodes that are correctly classified (without abstaining) and certifiable robust for given radius.
(c)
Cert. ratio (%)
distance
2
Cert. ratio (%)
distance 2
ours (Rojelevski al., 20200
75
distance
75
distance
40
AUCRC
30
50
50
20
25
25
10
2 Perturbed nodes
0%
20%
40%
60%
1 500
1,500
2,500
Perturbed nodes
d
Figure 3: Smoothed GAT on Cora-ML: (a) Robustness at different distances target nodes (pa=0.31,
P.=0.70 794, with skip, ACC=0. 79). (b) Robustness normalized by receptive field size ("attack surface"). (c) Naïve baseline comparison (base certificate (Bojchevski et al., 2020), 10 samples, o=0.01).
Messagg--iterreptioon smoothing. In Figure 3 (a.b) we demonstrate our certificates for specific edge deletion probabilities pa and node feature ablation probabilities pa- By making our certificates cussage-passing aware, we can (1) certify robustness against arbitrary feature perturbations of entire nodes, (2) analyze robustness locally in the receptive fields by incorporating the "attack surface", and (3) provide stronger guarantees for attacks against nodes at larger distances to target nodes.
7

---

First certificate for stronger adversaries. Experimentally we obtain significantly better robustness guarantees compared to previous (smoothing- based) certificates for Graph Neural Networks. Specifi- cally, existing certificates for GNNs only certify perturbations to few attributes j in the entire graph. Our certificates are novel as they provide guarantees for much stronger adversaries that can arbitrarily manipulate features of a multiple nodes in the graph. To compare these two approaches, consider naïve baseline that certifies p = p/d nodes, where d is the number of attributes per node.* If each node in the graph had just single feature, the number of certifiable nodes is high, As the number of features d per node increases, however, the baseline dramatically deteriorates. In contrast, our certificates are entirely independent of the dimension d and hold regardless of how digh-dimmnsional the underlying node data might be. We demonstrate this comparison in Figure 3 (c) for the first smoothing- based certificate for GNNs (Bojchevski et al., 2020), assuming attribute deletions against second-hop nodes (p, (p,=0,1 =0.6). However, the superiority of our certificate regarding robustness against all features of entire nodes holds for any other GNN certificate proposed so far.
(c)
Cert. ratio (%)
sparsification
Cert. ratio (%)
spund llcatiin w/o sparsific..
Cert. ratio (%)
75
wio spursific.
75
50
50
50
1100100
25
25
11-200
751-300
m0=
=1,00,000
0
1
2 3
4
5
0%
20%
40%
60%
2
Perturbed nodes
Perturbed nodes
Perturbed nodes
Figure 4: (a.b) Sparsification significantly improves certifiable robustness of our gray-box certificates to second-hop hop attacks since sparsification reduces (a) messages to intercept, and (b) receptive field sizes and thus the "attack surface" (Smoothed GAT, Cora-MI., Pa = 0.31, Pa = 0.71, with skip- connection, ACC 0.8). (c) Our certificate with largest certifiable radius of with varying samples for certification (Smoothed GAT, Cora-ML, Pd = O, Pa = 0.85). Our certificates are more sample efficient than existing smoothing-base certificates for GNNs.
Stronger certificates for sparser graphs. Notably, our gray-box certificates incorporate graph structure and become stronger for sparser graphs. This is in contrast to black-box certificates that ignore the underlying message-passing principles of GNNs. We demonstrate this by applying graph sparsification, which significantly improves robustness while retaining high clean accuracy: First, sparsification reduces the number of paths in the graph and thus reduces the number of messages to intercept. Second, sparsification reduces the number of nodes in the receptive fields and thus the "attack surface", that is the number of nodes that send messages. In Figure 4 (a,b) we apply GDC preprocessing (Gasteiger al., 2019) to the Cora-ML. graph at test time. GDC preprocessing yields directed graphs and reduces the number of edges in the graph from 15,962 to 14,606 (we set the sparsification threshold of GDC to 0.022 and ignore resulting edge attributes). Interestingly, evaluating the model on the sparsified graph yields significantly higher certifiable robustness, although both approaches show high clean accuracy of 80%. Note that for the validity of our certificates we assume adversaries perturb nodes after sparsification and cannot attack the sparsification itself.
Efficient message-interception smoothing. Drawing Monte- Cante samples from o to estimate the smoothed classifier is usually the most costly part when computing smoothing- based certificates (Cohen et al., 2019). In Figure 4 (c) we show that our certificates we do not benefit from more than a few thousand samples from o. This is in stark contrast to existing smoothing based certificates for GNNs (Bojchevski al., 2020). For fair comparison,
much more sample efficient as
adopt their transductive setting and compute certificates for ps = 0.3 and Pa = 0.85. Bojchevski et al. Cora-ML, which takes up to 25
(2020) use 10 Monte-Carle samples for certifying test nodes minutes, In contrast, our certificates saturate already for 2,000 Monte-Carlo samples in this setting, which takes only 17 seconds (preprocessing Cora-ML takes 8 additional seconds). Our gray-box certificates are significantly more sample-efficient while also providing guarantees against much stronger adversaries. We hypotheise that our certificates saturate much faster as the certifiable radius does not depend on the inverse Gaussian CDF of the label probabilities as discussed in Section 6.
"We are the first to certify such strong adversaries. Thus no baselines exist so far and we compare our method against existing certificates for GNNs using the naive baseline we propose above.
8

---

(b)
Clean ACC (%)
82
GAT GAIYZ
Clean ACC (%
82
with skip connection skip-ooenntttonn
Clean ACC (%)
82
Pe 0.1
GCN
80
P.1
80
SMA
80
78
78
10%
20%
0%
10%
20%
30%
40%
0%
10% AUCRC
20%
AUCRC
AUCRC
Figure 5: Second-hop attacks on Cora-ML: (a) Robustness-accurae tradeoffs for different GNN architectures. (b) Skip-connections yield improved robustness-accuracy tradeoffs for node feature ab- lation smoothing. (c) Ablating less during training yields better robustness-accuracy tradeoffs (GAT).
Different classifiers. In Figure 5 (a) compare robustness-accuaan tradeoffs for different GNNs against second-hop attacks. Attention-baser message-passing passing GNNs (Velickovic et al., 2018) are dominating. We hypothesize that the geggre-normalizattinn of GCN (Kipf and Welling, 2017) may be problematic for the performance under randomized edge deletion. Our approach may promote novel message-passing architectures, specifically designed for smoothed classifiers.
Skip-connections. With higher node feature ablation probability, more messages from the target node itself will be intercepted. which may be detrimental for the accuracy. Assuming adversaries do not attack target nodes, we can modify the architecture for improved robustnes--cccrae tradeoffs (Figure 5b). To this end, we forward the non-ablated input graph through the GNN without edges, and add the resulting final representation of each node to the final representation when forwarding the complex
(ablated) graph with graph structure. We use the same weights of the base GNN, but ckip-connections are straightforward. Such skip-connections yield better robustness accuuessys-curyyyyyyy trade- offs against second-hop attacks, but we also loose guarantees for the target node itself. To account for that, future work could deploy existing smoothing methods for features of target nodes separately: e-g., if nodes represent images, could deploy Gaussian smoothing (Cohen et al., 2019) node features send through the skip-connection and still obtain robustness guarantees for target nodes.
Training- time smoothing parameters. In Figure 5 (c) show that ablating less during training can improve the robustness-accuracy tradeoffs. Note that only inference-time smoothing parameters determine the strength of our certificates, and the probabilities pa, Pa during training are just hyperpa- rameters that we can optimize to improve the robustness-accuracy tradeoffs. In detail, we experiment with three different settings: Using the same ablation probabilities during training and inference (p, = Pa), ablating 10% more during training (p: = P. + +0.1), and ablating 10% less during training (p-=p--00 0.1). Note that max maimmin(pe 1), 0) project the training-time parameters into [0, 1].
a8)
(b)
Clean ACC (%)
Clean ACC (%)
82
78
Pa
P4 >0
Clean ACC
80
76
78
72
74
0%
10%
20%
30%
0%
10%
20%
30%
40%
0%
10%
20%
30%
40%
AUCRC
AUCRC
AUCRC
Figure 6: Robustness-accuraay tradeoff's for second-hop attacks against smoothed GAT models (without skip). Edge deletion and node ablation dominates Cora-ML (a) and Citeseer (b). On PubMed (c), edge deletion stronger. Lines connect dominating points on the Pareto front.
Robustness-accuracyy We compare robustness-accuraccy accuracy tradeoff' of three different settings: (1) edge deletion and feature ablation (pa > 0, Pa > 0), (2) edge deletion only (pa > 0.Po 0), and (3) feature ablation only (pa = 0, Pa > 0). Our experiments show that edge deletion and feature ablation smoothing achieves significantly better robustness-accuran tradeoffs against attribute attacks to the second-hop neighborhood and dominates on Cora-MI. and Citeseer (Figure 6b,c). On PubMed, edge deletion smoothing dominates. More results (c.g. with skip-connections) in Appendix H.

---

8
Related Work
GNN robustness. The vast majority of GNN robustness works focus on heuristic defenses, including adversarial graph detection (Zhang and Ma, 2020; Zhang et al., 2019a); architecture modifications (Brody et al., 2022: Zhang et al., 2019b); robust aggregations (Geisler et al., 2020); robust training procedures (Xu et al., 2019; Zügner and Günnemann, 2019), transfer learning (Tang et al., 2020); and graph preprocessing techniques such as edge pruning (Zhang and Zitnik, 2020; Wu et al., 2019), low-rank approximations (Entezari et al., 2020), and graph anomaly detection (Ma et al., 2021).
The effectiveness of such seemingly robust defenses on the adversarial robustness of GNNs can only be assessed against existing adversarial attacks. Heuristic defenses do not guarantee robustness, and may even be broken by stronger attacks later on (Mujkanovic al., 2022). Instead, we are interested in robustness certificates that provably guarantee the stability of predictions. However, robustness certificates for GNNs are still in their infancy (Günnemann, 2022):
Certificates for GNNs. Most certificates for GNNs are designed for specific architectures (Zügner and Günnemann, 2020; Jin et al., 2020; Bojchevski and Günnemann, 2019; Zügner and Günnemann, 2019). Despite providing provable robustness guarantees, their applicability is limited to specific architectures. Bojchevski al. (2020) present the first tight and efficient smoothing-based, model- agnostic certificate for graph-structure data. However, their method comes with crucial limitations: First, their method cannot certify robustness against arbitrary feature modifications of entire nodes. Second, their black-box certificate deletes edges but completely ignores the underlying message- passing principle. Third, their certificate requires an expensive evaluation of the smoothed classifier, which questions the practicability of their certificate beyond theoretical robustness assessments.
Randomized ablation certificates for image classifiers (Levine and Feizi, 2020b) are another approach for discrete data. Such certificates have already been applied to point cloud classifiers (Liu et al., 2021) and even for individual attribute perturbations in GNNs (Bojchevski et al., 2020). However, Bojchevski et al. (2020) show that their method outperforms such ablation certificates for individual attributes. In contrast, we propose certify entire nodes, instead of only few of their attributes. As already discussed, applying their ablation certificates for image classifiers directly to GNNs comes with serious shortcomings that we overcome (Section 4 and details in Appendix B).
Gray-box certificates. Exploiting model knowledge to derive tighter randomized smoothing certifi- cates constitutes widely unexplored research problem. The first works derive tighter guarantees using information about the model's gradients (Mohapatra et al., 2020; Levine et al., 2020). Recently proposed collective certificates (Schuchardt al., 2021) incorporate knowledge about the receptive fields of GNNs. Their certificates are orthogonal to ours, and our certificates could lead to significant improvements in such collective settings, as adversaries cannot attack first-hop neighbors of all nodes simultaneously. Schuchardt and Günnemann (2022) propose tight gray-box certificates for models that are invariant to spatial transformations.
9 Conclusion
We propose novel gray-box, message-passing aware robustness certificates for GNNs against strong threat models where adversaries can arbitrarily manipulate all features of multiple nodes in the graph. The main idea of our certificates is to intercept adversarial messages by randomly deleting edges and/or masking features of entire nodes. Our certificates are significantly stronger and more cumple-efficiee than existing methods. Future enhancements could smooth specific edges and nodes with different probabilities, for example to intercept messages from central nodes with higher probability. Our gray-box certificates could lead to novel architectures, training techniques and graph preprocessing techniques to further strengthen the robustness of GNNs against adversarial examples.
Acknowledgments and Disclosure of Funding
This work has been funded by the German Federal Ministry of Education and Research, the Bavarian State Ministry for Science and the Arts, and the German Research Foundation, grant GU 1409/4-1. The authors of this work take full responsibility for its content.
10

---

References
Alcksandar Bojchevski and Stephan Günnemann. Certifiable robustness to graph perturbations. In Neural Information Processing Systems, NeurIPS, 2019.
Aleksandar Bojchevski and Stephan Günnemann. Deep gaussian embedding of graphs: Unsupervised inductive learning via ranking. In International Conference on Learning Representations, 2018.
Aleksandar Bojchevski, Johannes Gasteiger, and Stephan Günnemann. Efficient robustness certifi- cates for discrete data: -parsity-aware randomized smoothing for graphs, images and more. In Proceedings of the 37th International Conference on Machine Learning, pages 1003-1013, 2020.
Shaked Brody, Uri Alon, and Eran Yahav. How attentive are graph attention networks? In Interna- fional Conference on Learning Representations, 2022.
Nicholas Carlini and David Wagner. Adversarial examples are not easily detected: Bypassing ten detection methods. In Proceedings of the 10th ACM workshop on artificial intelligence and security, pages 14, 2017.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In International Conference on Machine Learning, pages 1310-1320. PMIR, 2019.
Negin Entezari, Saba A Al-Sayouri, Amirali Darvishzadeh, and Evangelos E Papalexakis. All you need is low (rank) defending against adversarial attacks graphs. In Proceedings of the 13th International Conference on Web Search and Data Mining, pages 169-177, 2020.
James D Esary, Frank Proschan, and David W Walkup. Association of random variables, with applications. The Annals of Mathematical Statistics, 3865) 1967.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
Johannes Gasteiger, Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph learning. In Conference on Neural Information Processing Systems (NeurfPS), 2019.
Simon Geisler, Daniel Zügnerr, and Stephan Günnemann. Reliable graph neural networks via robust aggregation. In Neural Information Processing Systems, NeurIPS, 2020.
Simon Geisler, Tobias Schmidt, Hakan Şirin, Daniel Zügner, Aleksandar Bojchevski, and Stephan Günnemann. Robustness of graph neural networks at scale. In Neural Information Processing Systems, NeurlPS, 2021.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pages 1263-1272. PMLR, 2017.
Larry Goldstein and Nathakhun Wiroonsri. Stein's 's method for positively associated random variables with applications the ising and voter models, bond percolation, and contact process. In Annales de I' I'Institut Henri Poincaré, Probabilités et Statistiques, volume 54, pages 385-421. Institut Henri Poincaré, 2018
Stephan Günnemann. Graph neural networks: Adversarial robustness. In Lingfei Wu, Peng Cui, Jian Pei, and Liang Zhao, editors, Graph Neural Networks: Foundations, Frontiers, and Applications, chapter 8, pages 149-176. Springer, 2022.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In Advances in Neural Information Processing Systems, 2020.
Hongwei Jin, Zhan Shi, Venkata Jaya Shankar Ashish Peruri, and Xinhua Zhang. Certified robustness of graph convolution networks for graph classification under topological attacks. In Advances in Neural Information Processing Systems, 2020.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017.
11

---

Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. In 2019 JEEE Symposium on Security and Privacy (SP), pages 656-672. IEFE, 2019.
Guang-He Lee, Yang Yuan, Shiyu Chang, and Tommi Jaakkola. Tight certificates of adversarial robustness for randomly smoothed classifiers. In Advances in Neural Information Processing Systems, 2019.
Alexander Levine and Soheil Feizi. randoozzdd smoothing for certifiable defense against patch attacks. In Advances in Neural Information Processing Systems, 2020a.
Alexander Levine and Soheil Feizi. Robustness certificates for sparse adversarial attacks by random- ized ablation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 4585 4593, 2020b.
Alexander Levine and Soheil Feizi. Improved, deterministic smoothing for & certified robustness. In International Conference Machine Learning, 2021.
Alexander Levine, Aounon Kumar, Thomas Goldstein, and Soheil Feizi. Tight second-order certifi- cates for randomized smoothing. arXiv preprint arXiv:2010. 2020.
Hongbin Liu, Jinyuan Jia, and Neil Zhengiang Gong. Pointguard: Provably robust 3d point cloud classification. In CVPR, pages 6186-6195, Computer Vision Foundation IEEE, 2021.
Jiaqi Ma. Shuangrui Ding, and Qiaozhu Mei. Towards more practical adversarial attacks on graph neural networks. In Advances in Neural Information Processing Systems, 2020.
Xiaoxiao Ma, Jia Wu, Shan Xue, Jian Yang, Chuan Zhou, Quan Z. Sheng, Hui Xiong, and Le- man Akoglu. A comprehensive survey on graph anomaly detection with deep learning. IEEE Transactions on Knowledge and Data Engineering. 2021.
Andrew McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Inf. Retr, 3(2):127-163, 2000.
Jeet Mohapatra, Ching- Yun Ko, Tsui-Wei Weng, Pin-Yu Chen, Sijia Liu, and Luca Daniel. Higher- order certification for randomized smoothing. In Advances in Neural Information Processing Systems, volume 33, pages 4501-4511, 2020.
Felix Mujkanovic, Simon Geisler, Stephan Günnemann, and Aleksandar Bojchevski. Are defenses for graph neural networks robust? In Neural Information Processing Systems, NeurlPS, 2022.
Galileo Namata, Ben London, Lise Getoor, Bert Huang, and UMD EDU. Query-driven active surveying for collective classification. In 10th International Workshop on Mining and Learning with Graphs, volume 8, page 1, 2012.
Jerzy Neyman and Egon Sharpe Pearson. Ix. on the problem of the most efficient tests of statistical hypotheses. Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Character, 23166947706 1933.
Jan Schuchardt and Stephan Günnemann. Invariance-aware randomized smoothing certificates. In Neural Information Processing Systems, NeurlPS, 2022.
Jan Schuchardt, Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Collective robustness certificates: Exploiting interdependence in graph neural networks. In International Conference on Learning Representations, 2021.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad Collective classification network data. Al magazine, 29(3):93-99 -93, 2008
Xianfeng Tang, Yandong Li, Yiwei Sun, Huaxiu Yao, Prasenjit Mitra, and Suhang Wang. Transferring robustness for graph neural network against poisoning attacks. In WSDM, pages 600-608. ACM, 2020.
12

---

Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations. 2018.
Huijun Wu, Chen Wang, Yuriy Tyshetskiy, Andrew Docherty, Kai Lu, and Liming Zhu. Adversarial examples for graph data: Deep insights into attack and defense. In IJCAI, pages International Joint Conferences Artificial Intelligence Organization, 2019.
Kaidi Xu, Hongge Chen, Sijia Liu, Pin- Yu Chen, Tsui-Wei Weng, Mingyi Hong, and Xue Lin. Topology attack and defense for graph neural networks: An optimization perspective. In IJCAI, pages 3961-3967. ijeai.org. 2019.
Ao Zhang and Jinwen Ma. Defensevgae: Defending against adversarial attacks on graph data via variational graph autoencoder. CoRR, 0aos/2006.08900, 2020.
Xiang Zhang and Marinka Zitnik. Gnnguard: Defending graph neural networks against adversarial attacks. In Advances Neural Information Processing Systems, 2020.
Yingxue Zhang, S Khan, and Mark Coates. Comparing and detecting adversarial attacks for graph deep learning. In Proc. Representation Learning Graphs and Manifolds Workshop, Int. Conf. Learning Representations, New Orleans, LA, USA, 2019a.
Yingxue Zhang, Soumyasundar Pal, Mark Coates, and Deniz Üstebay. Bayesian graph convolutional neural networks for semi-supervised classification. In AAAI, pages 5829-5836. AAAT Press, 2019b.
Xu Zou, Qinkai Zheng, Yuxiao Dong, Xinyu Guan, Evgeny Kharlamov, Jialiang Lu, and Jie Tang. Tdgia: Effective injection attacks on graph neural networks. Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, 2021.
Daniel Züggerr and Stephan Günnemann. Certifiable robustness and robust training for graph convolutional 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, pages 1656-1665, 2020.
13


Reviews:
[{"review_id": "lFropGBgXpC", "reviewer": "Reviewer_dqSE", "summary": "This paper presents a new gray-box certification method for graph neural networks (GNNs) using smoothing. Unlike previous approaches, it uses utilizes the underlying message passing based principle (e.g., deleting edges, ablating nodes, etc) to obtain a stronger guarantee. To achieve certification, the authors first derived the worst case change in label probability and then proposed practical way to give a sound lower bound.\n", "questions": "Can you show results with different confidence levels and see how strong the method is with a smaller alpha? How many samples are required and what is the certification accuracy for different levels of alpha?\n", "limitations": "Yes, the author discussed limitations of this work explicitly and I see no obvious negative societal impacts.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\n1. This method can give stronger certification compared to previous approach.\n2. The theoretical results presented in this paper are novel and practical.\n3. Experimental evaluation shows both speed and certification benefits compared to pure black box methods.\n\nWeaknesses:\n\n1. I am a bit concerned about the confidence level alpha=0.05 used for certification, because it means that the guaranteed robustness only holds with a probability of 95%. Some existing works such as (Zugner and Gunnemann 2019)  using deterministic certification methods do not have this limitation.\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ik8kYZ_P3dP", "reviewer": "Reviewer_KAVi", "summary": "This paper proposes a novel method based on randomized smoothing to achieve robustness for graph neural networks. The task here is to certify the classification accuracy of GCN under any possible attacker who can perturb a bounded number of node features. Compared to the existing method, the proposed one considers random edge ablation and random node-level ablation. As a result, the approach achieves higher certified accuracy than existing baselines by a large margin.", "questions": "In terms of suggestions for the authors, see weaknesses.\nQuestions on writing:\n- Line 234 and Appendix I: in the training process, how is the node mask t optimized?\n- Line 284: what does $\\epsilon=0.022$ stand for?\nSuggestions on writing:\n- Line 252-262: from the equation formulation, it is straightforward to see that the proposed certification is independent of perturbed feature dimensions $d$. Maybe we can omit Figure 4(a) and Line 252-262 to the appendix since it consumes much space.", "limitations": "See weaknesses.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Solid technical contributions: To the best of my knowledge, this is the first paper that applies random **edge** ablation. Existing approaches for certifying the smoothed GCNs only consider random **node** ablation. When edge ablation comes into play, the certification can take the graph topology into consideration to achieve a better robustness certification. This paper studies this problem in depth, by providing an upper bound of $\\Delta$ for certification and characterizing the computing methods for exact certification for general graphs or tree-structured graphs.\n\n- Great writing quality: the paper is easy to follow with just few typos/ambiguities. Especially, the paper studies the proposed smoothing scheme in-depth, beyond just showing a good empirical performance. This in-depth investigation includes theoretically characterizing the limitations and advantages of different graph smoothing protocols, proposing more expensive though tighter computing methods, and presenting quite a few ablation studies, especially those revealing the benefits of sparsity.\n\nWeaknesses:\n- The proposed method is a bit specific to graph neural networks with node perturbations. In other words, the method could be further benefited from extensions to a wider range of threat models, i.e., node addition/removel, edge feature perturbations, etc.\n\n- More training techniques can be applied to further strengthen the certified robustness guarantee. For example, SmoothMix training (Jeong et al), SmoothAdv training (Salman et al), and DRT training (Yang et al).\n\nOverall, I think these weaknesses are overall not critical. Disclaimer: I'm not actively working with GNNs. So I didn't evaluate the impact of this paper to GNN community nor whether the evaluation follows standardized protocols. I will refer to other reviewers' comments on these aspects to adjust my score if necessary.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "IhFLWBkPgr0", "reviewer": "Reviewer_EH8E", "summary": "This paper proposes a robustness certification against adversarial attacks on graph data. The model will randomly ablate some nodes and delete some edges so that the adversarial impact on certain nodes will not propagate to the target node with high probability. They show that the pipeline achieves good robustness, especially at larger distances.", "questions": "In the experimental setup, how is the subgraphs generated exactly? Since the nodes are randomly sampled, does the edge only exist if both nodes are sampled? How do you guarantee that the graph is still connected and not too sparse?\n\nI am curious why the authors keep mentioning gray-box certification in contrast to black-box. Since the certification is performed by the model itself, the model will for sure know the exact data as well as other information. So I can only imagine the white-box (which also satisfies gray-box and black-box) setting of the certification.", "limitations": "As mentioned in the weaknesses, I think the authors can improve by considering the edge-based attacks.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\n* The robustness certification can be verified against arbitrary perturbation on the adversarial nodes. In the pipeline, the certification is achieved by blocking the messages from the adversarial nodes. Therefore, it can provide certification without restricting the perturbation magnitude on each node. This seems a realistic setting to me - in practical graph data settings, considering the number of adversarial nodes (users) is more important than considering the magnitude of adversarial perturbation on each node. \n\n* The experimental evaluation is comprehensive. The authors evaluate their approach in different settings, e.g. with skip-connections and under different sparsifications. These approaches show the flexibility of their approach to different cases.\n\n\n## Weaknesses:\n\n* Only feature-based attack robustness is considered. Actually, a wide range of attacks on GNNs will focus on edge-modification attacks (e.g. [a,b]). The paper does not discuss the applicability of their approach against this type of attack. Actually, it feels to me that the proposed approach can still be adapted as long as both nodes of the edge are considered as adv nodes, although such a bound seems like a loose bound.\n\n[a] Zügner D, Günnemann S. Adversarial Attacks on Graph Neural Networks via Meta Learning[C]//International Conference on Learning Representations. 2018.\n\n[b] Xu K, Chen H, Liu S, et al. Topology attack and defense for graph neural networks: an optimization perspective[C]//Proceedings of the 28th International Joint Conference on Artificial Intelligence. 2019: 3961-3967.\n\n* The certification result is node-specific and not applicable in practice. If I understand correctly, the exact certification provided by the algorithm is \"given a target node, the adversarial perturbation on a specific node set can/cannot be certified to be robust\", but not \"given a target node, we can allow arbitrary N nodes to be attacked\". The latter is a more useful certificate that can be achieved by previous approaches, while the current one is limited to a specified node set.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "IVszeRwJNT", "reviewer": "Reviewer_51To", "summary": "This paper presents a technique to certify the robustness of Graph Neural Networks. Inspired by randomized smoothing, the proposed method takes advantage of the graph structure to get obtain various certificates (e.g., on accuracy). For the studied threat model, these certificates are tighter than proposed in the literature so far. The threat model consist of allowing an adversary to arbitrarily manipulate the features (i.e., emitted messages) of a subset of nodes.", "questions": "The paper is well-written. I would appreciate if the authors address the weaknesses stated above.", "limitations": "Yes, the limitations are reasonably addressed.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* The authors are the first to truly take advantage of network structure to certify GNN (at least from a smoothing perspective).\n* The results clearly demonstrate that they can certify a larger proportion of cases than prior methods (when the number of features increases).\n* The threat model is fairly broad and could have practical applications\n\nWeaknesses:\n* It would help the reader to explain a bit why the studied threat model is interesting and when it arises in the real-world. The certification method which relies on smoothing can only be used for offline analysis or, if used online (let's say on the network of machine), will be prohibitly expensive to run (i.e., sampling of various network configurations).\n* My knowledge of graph robustness is fairly limited, but I assume there has been a number of works (not specifically designed for machine learning applications) that also provide robustness to the threat model considered (e.g., r-robustness). Maybe expanding the literature survey slightly and expanding the experiments to demonstrate that r-robust networks are 100% certifiable (using the proposed approach) would help make a stronger and broader point.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept