GNNCert: Deterministic Certification of Graph Neural Networks against Adversarial Perturbations
Authors: zaishuo xia
Han Yang
Binghui Wang
Jinyuan Jia
Venue: ICLR 2024 oral (2024)
Keywords: Adversarial attacks to graph classification; provable robustness
Primary area: societal considerations including fairness, safety, privacy

Abstract: Graph classification, which aims to predict a label for a graph, has many real-world applications such as malware detection, fraud detection, and healthcare. However, many studies show an attacker could carefully perturb the structure and/or node features in a graph such that a graph classifier misclassifies the perturbed graph. Such vulnerability impedes the deployment of graph classification in security/safety-critical applications. Existing empirical defenses lack formal robustness guarantees and could be broken by adaptive or unknown attacks. Existing provable defenses have the following limitations: 1)  they achieve sub-optimal robustness guarantees for graph structure perturbation, 2) they cannot provide robustness guarantees for arbitrarily node feature perturbations, 3) their robustness guarantees are probabilistic, meaning they could be incorrect with a non-zero probability, and 4) they incur large computation costs. We aim to address those limitations in this work. We propose GNNCert, a certified defense against both graph structure and node feature perturbations for graph classification. Our GNNCert provably predicts the same label for a graph when the number of perturbed edges and the number of nodes with perturbed features are bounded. Our results on 8 benchmark datasets show that GNNCert outperforms three state-of-the-art methods.

Published as a conference paper at ICLR 2024
GNNCERT: DETERMINISTIC CERTIFICATION OF GRAPH NEURAL NETWORKS AGAINST ADVERSARIAL PERTURBATIONS
Zaishuo Xiat**, Han Yang"**, Binghui Wang*1 Jinnuan Jia 1 Renmin University of China, Sichuan University,
3 Illinoois Institute of Technology, "The Pennsylvania State University
ABSTRACT
Graph classification, which aims to predict label for a graph, has many real-world applications such as malware detection, fraud detection, and healthcare. However, many studies show an attacker could carefully perturb the structure and/or node fea- tures in a graph such that a graph classifier misclassifies the perturbed graph. Such vulnerability impedes the deployment of graph classification in security/safety- critical applications. Existing empirical defenses lack formal robustness guarantees and could be broken by adaptive or unknown attacks. Existing provable defenses have the following limitations: 1) they achieve sub-optimal robustmess guarantees for graph structure perturbation, they cannot provide robustness guarantees for arbitrarily node feature perturbations, 3) their robustness guarantees are probabilis- tie, meaning they could be incorrect with a non-zero probability, and 4) they incur large computation costs. We aim to address those limitations in this work. We propose GNNCert, a certified defense against both graph structure and node feature perturbations for graph classification. Our GNNCert provably predicts the same label for a graph when the number of perturbed edges and the number of nodes with perturbed features are bounded. Our results 8 benchmark datasets show GNNCert outperforms three state-of-the-art methods
INTRODUCTION
In graph classification, a graph classifier takes a graph as input and predicts label for Graph classification is fundamental task for graph analytics, which has been widely used in many real- world applications such as fraud detection [Weber et al.) 2019), malware detection (Kong & Yan
2013, Hassen & Chan 2017: Yan et al., 2019), and healthcare (Li et al. [2077] Chen | 2018). Graph neural networks Kipf & Welling 2016 are widely used as graph classifiers as they achieve state-of-the-art classification accuracy for graph classification. Despite their superior performance,
many studies (Dai et al. 2018 Tang et al. 2020 Chen et al. 2021 Mu et al. 2021b Zhang et al.)
202 Wan al. 202 bb) Zhang et al. 2022 Mu et al. 2021a Wang al. 2022 2023) show graph classification is vulnerable to adversarial perturbations, where an attacker could arbitrarily perturb
the graph structure and/or node features of testing graph such that graph classifier predicts an incorrect label for the testing graph. Such attacks significantly impede the deployment of the graph classification for security- and safety-critical applications such as fraud detection.
Many defenses were proposed to defend against adversarial perturbations to graph classification. In particular, those defenses can be classified into empirical defenses (Chen et al., 2020 Zhang & Lu 2020 Zhao et al. 2021) and certified defenses (Bojchevski et al. 2020; Wang et al. 2021 Zhang et al. 2021b). Empirical defenses cannot provide formal robustness guarantees, i.e., they cannot guarantee the graph classification performance under arbitrary attacks, and thus lead to and- mouse game between the attacker and defender. As a result, they could be broken by advanced attacks, as shown in Mujkanovic et al.) (2022). By contrast, certified defenses could guarantee the graph classification performance under arbitrary attacks, once the number of perturbed edges and number
"Equal contribution, 'Corresponding authors. Zaishuo and Han performed this rescarch when they were interns. The code is available at httts::/ggithhbb com/ aFi re/GNNCERT

---

Published as a conference paper at ICLR 2024
of nodes with perturbed features are bounded. However, existing certified defenses (Bojchevski iet al. 2020; Wang et al. 2021] Zhang et al.) 2021b) suffer from the following limitations. First, they cannot provide robustness guarantees when an attacker can arbitrarily perturb the features of nodes, Second, they achieve sub-optimal robustness guarantees for graph structure perturbation as shown in our experimental results. Third, their robustness guarantees are prohabílistic, i.e., their robustness guarantees could be incorrect with a certain probability. Fourth, their computation costs are large. We aim to address all these limitations in this work.
Our contribution: In this work, we propose GNNCert, the first certified defense against both graph structure and node feature perturbations for graph classification with deterministic robustness guarantees. Given testing graph and graph classifier (called base graph classifier), we first use hash function to divide the testing graph into multiple sub-graphs, then use the graph classifier to predict a label for each -raap, and finally use the majority vote to predict label for the testing graph. We show the majority vote result is provably unaffected, i.c., GNNCert provably predicts the same label for testing graph under arbitrary adversarial structure and feature perturbations, once the number of perturbed edges and number of nodes with perturbed features are bounded. Following Cohen al. (2019), to improve the provable robustness guarantees of GNNCert, also utilize sub-graphs created from training graphs to train the base graph classifier. Our experimental results show such training method significantly improves the provable robustness guarantees.
We conduct comprehensive evaluations on 8 benchmark datasets (e.g., MUTAG (Debnath et al. 1991]. NCII (Wale al. 2008). PROTEINS (Borgwardt et al., 2005]. COLLAB Yanardag & Vishwanathan 2013) for graph classification. We use certified accuracy as the evaluation metric, which is a lower bound of the classification accuracy of a defense under arbitrary adversarial attacks with a bounded number of perturbed edges and/or nodes with perturbed features. We compare our GNNCert with state-of-ther the--tt-rtt certification methods (Bojchevski et al., [020 Wang et al. 2021 Zhang et al.) [02 and results show GNNCert significantly outperforms them. Our major contributions are follows:
We propose GNNCert, certified defense against both graph structure and node feature perturbations to graph classification.
We derive the deterministic robustness guarantee of GNNCert.
We extensively evaluate GNNCert on 8 benchmark datasets.
2 BACKGROUND AND RELATED WORK
Many existing studies (Dai 2018 Tang et al. 2020; Chen et al. 2021 Mu et al. 20216 Zhang et al. 2021a Wan et al. 2022 Zhang et al. 2022 Mu et al.] 2021a Wang et al.) 2022 2023) show graph classification vulnerable to adversarial attacks. Given a testing graph, an attacker could perturb the graph structure and/or node features such that a graph classifier makes incorrect predictions for the perturbed testing graph. For instance, WWang] et al. 2022) proposed to leverage bandits to design black-box attacks on graph classifications with guaranteed attack performance.
Adversarial attacks to graph classification:
Existing empirically robust defenses: To defend against adversarial attacks, many empirical defenses (Chen et al. 2020 Zhang & Lu 20200 Zhao et al.) (2021) were proposed. The key limitation of those empirical defenses that they cannot guarantee their performance under arbitrary adversarial perturbations, leading to a cat-and-mouse game between the attacker and defender. In other words,
those empirical defenses could be broken by adaptive attacks (Mujkanovic al. 2022).
Existing certified defenses (Bojchevski et al. 2020 Jin et al. 2020: Wang et al. 2021 Zhang et al. 202Tb) could show they provably predict the same label for testing graph when the number of perturbed edges to the graph is bounded. For instance, Bojchevski
Existing provably robust defenses:
ct al. (020)) and Wang et al. I) generalized randomized smoothing (Lecuyer et al. 2019 Cohen
al. 2019) (a state-of-the-art art method to certify robustness against adversarial examples) from the
image domain to the graph domain. Zhang et al. (2021b) extended randomized ablation (Levine & Feizi] 2020c) to build provably robust graph classification against graph structure perturbations. Existing certified defenses for graph classification suffer from the following limitations. First, they
can only provide robustness guarantees for graph structure perturbations. However, in practice, an
2

---

manipulate both the graph structure and Published as a conference paper at ICLR 2024
structurdivision
(b) festure division
(c) structre-feshmre division
Figure 1: Overview of GNNCert. The black node features mean special values, e.g., zero.
attacker may perturb node features to perform attacks. Second, they achieve sub-optimal certified robustness guarantees for graph structure perturbations as shown in our experimental results. Third, they incur large computation costs. Fourth, their robustness guarantees are probabilistic, which means their guarantees could be incorrect with a certain probability. We aim to address those limitations. We note that the defense proposed by Din et al. (2220) only be applied specific architectures.
OUR GNNCERT
3.1
GRAPH CLASSIFICATION SETUP
Given graph G (V, F, where V (2,, ,Un is of nodes, E is set of edges connecting nodes V. and X, denote the feature vector the node v E V. Given a training dataset Dr that contains a of training graphs and their ground truth labels, we can use it to train graph classifier f. Given testing graph G, we could use the graph classifier f to predict label for it. For simplicity, we use f(G) denote the predicted label for the graph
3.2 THREAT MODEL
Attacker's goal, background knowledge, and capability: Given a testing graph G and graph classifier f. an attacker's goal is to perturb the graph structure and/or node features of G such that the graph classifier makes an incorrect prediction for the perturbed testing graph. As we focus on provable defenses, (e.g., the edges, nodes, and node features) about G, and all information (e.g., the model parameters, architecture) about f. We further consider the attacker node feature. For graph structure perturbations, the attacker could arbitrarily add or delete a certain number of edges in the testing graph G. For node feature perturbations, the attacker could arbitrarily perturb the features of certain number of nodes in G.
consider the strongest attack. That is, the attacker knows all information
Defender's goal: The defender aims to build provably robust graph classifier such that provably predicts the same label for the testing graph G when the number of perturbed edges and/or number of nodes with perturbed features are no larger than threshold (called certified perturbation size).
3.3 OUR GNNCERT
GNNCert consists of three main steps: 1) divide a graph into different sub-graphs; 2) build an ensemble classifier on the sub-graphs; and 3) derive the formal robustness guarantees of the ensemble classifier against graph structure perturbations, node feature perturbations, as well as both graph structure and node feature perturbations. Figure shows overview of GNNCert.
3.3. DIVIDING A GRAPH INTO SUB-GRA SUB-GRAPHS
Our idea is divide into different sub-graphs. A hash function (c.g.. MD5) takes a string as input and produces an integer. We leverage the node IDs divide the testing graph G into multiple sub-graphs. Let
hash function 7. (H does not depend on the edge structure/node features) to
3

---

Published as a conference paper at ICLR 2024
ID be the node ID of a node v. We can transform ID, into string, denoted as S... For instance, S. could be "3" when the node ID of is 3. Given S, 's for every node v E V, we propose three ways, namely structure division. feature division, and structure-feature division, to divide the testing graph G into different sub-graphs. In particular, the structure division, feature division, and structure- feature division, enable our GNNCert defend against graph structure perturbations, node feature perturbations, as well as both graph structure and node feature perturbations, respectively. Next, we will discuss the three division methods in detail.
Suppose attacker aims perturb the graph structure by adding/deleting edges in G. To defend against this attack, we can divide edges in E into T, groups using the hash function H. where T. a hyper- paraae-.r First, we can compute group index for every edge (vi, 0/) E E based on the concatenation of Su, and Se.. For simplicity, we denote H(S,, @ Su, )%T. + 1 as the group index for the edge (V,, v2), where % is the modulo operation and ① represents the concatenation of two strings. Then, we use E to denote the set of edges whose group index is t, where 1. TT,, i.c., E {(v,, R,) E ES, + S.,),I. + 1 = t3. Given each E", we can construct the each sub-graph G. as Gi = (V, We call this method structure division as we keep all the nodes and their features in each sub-graph while dividing edges into different sub- graphs.
Structure division:
Suppose an attacker aims to perturb features of nodes in V. For this type of attack, we can divide features of nodes into Tj groups using the hash function H. where T'y is byper-parameter Likewise, we could first compute a group index H(S.)) - for every node using the hash function H. Then we use X to denote the features of nodes whose group index is t, where / = 2, ..... TT. Then, we construct the sub-graph& G. as G. (V, E, X*). Note that there exist many nodes whose feature vectors are not X and we set their feature vectors to be a special value, c.g., zero. We call this method feature division as we keep the entire graph structure in each sub- bob-graph but divide node features into different uub-graphs.
Feature division:
structure- feature division, we combine the above strategies to construct sub- graphs... In particular, we first use structure division to divide edges E into T, groups E ..... F.T and use feature division to divide features X into T groups X X2, X,,X2 ,.... Xx;, Then we can construct T.- - T sub-graphs. In particular, we have G. = (V, E" x"), where t = 2. T. Tr, u = [t/Tr]. I. and v = t- (u - 1) Ty, We call this method structure-feature division as we divide both graph structure and node features into different sub- graphs.
Structure-feature division:
3.3.2 BUILDING AN ENSEMBLE GRAPH CLASSIFIER
Given a testing graph G. we can use structure (or feature or structure-featur division to divide into N sub-graphs, where N- T, (or N Ty or N T. Ty). Given the N sub-graphs [G.] and base graph classifier f. we can use / to predict a label for each sub-graph. Note that we remove the node in the sub-graph if it simultaneously satisfies the following conditions: 1) it does not have any edge with all other nodes in the sub- wub-graph, and 2) its feature vector is set to be special value. The reason is that this kind of node does not provide any information for graph classification since is not connected with any other nodes and its node feature is special value. Suppose the set of all the possible classes is 21,2,-- ... C). We use N₂ to denote the number of sub-graphs that are predicted as the class e by the base graph classifier f. i.e., N₂ = Σnn T(](G)) c). where = 1,2,..., C and is the indicator function. Then, we define our ensemble graph classifier y as follows:
g(G) = arg max No, dE cE,,,......C
where a label with a smaller index is taken by our ensemble classifier when there are ties. We denote I = g(G) the predicted label. Then, g can provably predict the same label for G' when the number of perturbed edges and/or number of nodes with perturbed features are bounded, as shown below.
3.3.3 DERIVING THE PROVABLE ROBUSTNESS GUARANTRES
Suppose we have an adversarially perturbed graph GP. Similarly, we use Gp, -.....,.. Py to denote the N sub- uub-graphs created from GP. Moreover, we denote by N = >N I(f(G)) = c). Ve e 21.2.... C), i..., No measures the number of sub- mub-graphs created from GD that are predicted as the class e by the base graph classifier f. Due to the perturbed node features or graph edges, some sub-graphs would be corrupted. For simplicity, we use M to denote the total number of aub-graphs
4

---

Published as a conference paper at ICLR 2024
in 9. P........ that are corrupted by the perturbed node features or graph edges. Then, we can derive the following lower or upper bounds:
Ne - -M- S N? S No + M, Ve E (1,2.-.... ,...
(2)
Our ensemble graph classifier g still predicts the label for the perturbed graph GP if N? (1.2.- (1.......... (y,(U) TT(2 < c)), where the term [[ < c) stems from our tie breaking mechanism (i.e., we take a label with a smaller index where there are ties). Then we have the following theorem: Theorem Given an arbitrary base graph classifier f. our ensemble graph classifier g is as defined in Equation] 7 Given lesting graph G, we can use our structure (or feature or structure-feature) division to divide it into N sub-graphs. Suppose Ne is the number of suub-graphe predicted as the label с by the given base graph classifier f. where c 1,2,.... ,C. Moreover, we assume M is the total number of corrupted sub- graphs created from a perturbed graph GP. Then, we have g(G) = g(GP)= when the following condition is satisfied:
>
Ni- - m (1.2, -o,- - I(1 < {()
M S M
2
Proof. See Appendix A
We have the following remarks from theorem:
With structure division, each added or deleted edge results in one corrupted sub- sub-graph. Thus, our GNNCert with structure division could tolerate up to M added or deleted edges. With feature division, single sub-graph corrupted when an attacker arbitrarily perturb the features of node. Thus, our GNNCert with feature division could tolerate up to M nodes with adversarially perturbed features.
With frratture-feature division, T/ (or Tx) sub-graphs are corrupted when attacker adds/deletes an arbitrary edge (or arbitrarily perturb the features of a node). Thus, our GNNCert with feature division could tolerate up to [MP _M//Tyy perturbed edges (or [M' /Ty. of nodes with adversarially perturbed features).
Our provable robustness guarantees hold for arbitrary adversarial attacks that perturb bounded number of edges and/or node features. Moreover, our robustness guarantee is deterministic, i.e., the robustness guarantee is true with probability of 1.
Technical contributions: To the best of our knowledge, we the first to utilize hash function to divide a graph into sub-graphs to build a certifiably robust graph classifier. Our GNNCert effectively addresses the aforementioned four limitations of sfate-of-the-ar provable defenses for graph classifi- cation (Bojchevski et al. 2020; Wang et al., 2021 Zhang et al. 2021b). Particularly, it could resist structure perturbations, feature perturbations, as well as both structure and feature perturbations. Our GNNCert is effective and easy to implement, and thus could be widely applied in graph classification tasks that require provable robustness guarantees against adversarial attacks.
Our GNNCert is based on general randomized smoothing framework (i.e., splitting & prediction & majority vote) (Lecuyer et al. 2019 Cohen et al., (019). The key insight of the defense is based on 1) only bounded fraction of predictions are corrupted when the perturbation is bounded, and 2) majority vote is intrinsically robust against corrupted voters (each prediction can be viewed as one voter). This framework was also utilized in previous certified defenses for adversarial patch attacks (Levine & Feizi| 20206; Xiang et al., (021). data poisoning attacks (Jia et al., [021 Levine & Feizi 2020a Jia et al.] 2022). fo-norm adversarial examples for image and tabular data (Hammoudeh
& Lowd 2023), and many others (Zhang et al. 2023; Zeng et al.) 2023: Pei et al.) 2023). Our robustness guarantee derivation is also based on the intrinsic robustness of the majority vote, which follows previous certified defenses (Levine & Feizi| 22200b a Jia et al. 2022 Hammoudeh & Lowd 2023). The key difference between different methods is that they create different voters (i.c., the voters have different meanings) for the majority vote. Our key contribution is to design three graph division methods (e.g., structure, feature, structure-fean feature division) tailored to the graph domain.
Our following theorem shows the tightness of our derived bound: Theorem 2. Without leveraging any information on the base graph classifier, our derived bound is right, i.e., it is impossible to derive a tighter bound than ours.
Proof. See Appendix B
5

---

Published as a conference paper at ICLR 2024
4 EVALUATION
4.1 EXPERIMENTAL SETUP
Datasets: We use 8 benchmark datasets for graph classification in our evaluations: DBLP (Pan et al. 2013). DD (Dobson & Doig 2003), ENZYMES (Hu et al. 2020). MUTAG (Debnath et al. 1.9 p. NCII (Wale et al. 2008). PROTEINS (Borgwardt al. 2005), REDDIT-B (Yanardag & Vishwanathan 2015), COLLAB Yanardag & Vishwanathan 2013). Table 2 in the Appendix shows the statistics of those datasets. For each dataset, we randomly sample two- woo-thirds of the graphs as the training dataset to train a base graph classifier and use the remaining graphs as the testing dataset.
Base graph classifier: We use state-of-the-art graph neural networks as the base graph classifier. Unless otherwise mentioned, consider GIN (Xu al., 2019) and utilize its publicly available implementation" in our experiments. To train a graph classifier, we use the Adam optimizer with a learning rate of 0.001 and a batch size of 32 for 1,000 epochs.
Compared methods: We compare our GNNCert with three state-of the-art certification methods for graph classification: Zhang al. 2021b) Wang et al. (202T), and Bojchevski et al. (2020). In particular, Zhang et al. (2021b) extends randomized ablation (Levine & Feizi] (022cc from the image domain the graph domain. Given a testing graph, Zhang et al. (2021b) create S, subsampled graphs, where each subsampled graph is obtained by sampling r fraction of edges from a testing graph uniformly at random without replacement. Then, Zhang et al. (202Tb) uses a base graph classifier to predict label for each subsampled graph and take majority vote over those predicted labels. Following Zhang et al. 2 we set 7 = 10% and set S₂ = 1, 000, and use subsampled training graphs to train the base graph classifier in our comparison.
Given a testing graph and a base graph classifier, Wang et al. (2021) and Bojchevski et al. (2020) first randomly perturb the graph structure of testing graph to create S.. and S, noisy graphs, then use the base classifier to predict a label for each noisy graph, and finally take a majority vote over the predicted labels. The key difference between Wang et al. (202T) Bojchhees al. (2020) is that they use different ways to perturb the graph structure vector to obtain a noisy graph. In particular, Wang et al.| (2021) proposed flip the connection status of two nodes with a probability 3, e.g.. there is an edge between two nodes, the edge is deleted with probability B. We set / = 0.3 by following Wang et al, (202T). By contrast, BBoccheskki et al.; (2020) utilizes two probabilities (denoted as p+ and p-) p-) to create a noisy graph from given testing graph. In particular, if there is an edge (or no edge) between two nodes, the edge is deleted (or added) with a probability of p_ (or p+) We set p_ = 0.3 (or p+ = 0.3) in our experiments to be consistent with Wang et al. (202]) (i.e., on average, the number of perturbed edges is the same for those two methods). Following Wang et al. (202I) and Bojchevski et al. (2020), we set S. 1, 000 and S,, 1, 000, i.c., randomly create 1, 000 noisy graphs for each testing graph for those two methods.
All the three compared methods utilize Monte-Carlo sampling to compute the certified perturbation size. As a result, the certified perturbation size correct with a probability - a, where 0 < a < 1. In our comparison, we set 0.001 following those three methods. Note that we adopt the same graph neural network as the base graph classifier with our GNNCert in our comparison.
Evaluation metric: Following previous studies Zhang et al. 20216 Wang al. 2021 Bojehevski et al. 2020), we use the certified accuracy as the evaluation metric. Given perturbation size S and testing dataset Dreat: certified accuracy is defined as the fraction of testing inputs that 1) are correctly predicted, and 2) have certified perturbation size that no smaller than M.
Parameter setting: Our GNNCert has the following hyperparameters: the hash function H. the number of groups T₂ for structure division, and the number of groups T, for feature division. Unless otherwise mentioned, we use MD5 as the hash function and we set T, = -30 and T, 30. We also conduct extensive ablation studies show the impact of these paramtearameters.

---

Published as a conference paper at ICLR 2024
ONF NOCKA
Dar
(a) DBLP
(b) DD
(c) ENZYMES
(d) MUTAG
Mongie Chirs
Contraa AcceNay
Dee
Mieg at
Mang at Doe
Daes
Datutabke
(c) NCT1
(f) PROTEINS
REDDIT-B
(h) COLLAB
Figure 2: Comparing the certified accuracy of our GNNCert with existing certified defenses.
traane wbgree
Curtion ANCEO0T
(a) DBLP
(b) DD
(c) ENZYMES
(d) MUTAG
abore
(c) NCII
(i) PROTEINS
REDDIT-B
(h) COLLAB
Figure Comparing the certified accuracy of our GNNCert when the base graph classifier trained with/without sub-graphs.
Table Comparing the computation costs of GNNCert and existing defenses on MUTAG.
Compared method
Training cost (s)
Testing cost (s)
Bojchevski et al.
2020
1,455
38
Wang et al. 2022
1,344
48
Zhang et al. 2021b
1,136
25
GNNCert
773
4.2 EXPERIMENTAL RESULTS
Our GNNCert achieves better provable robustness guarantees than existing defense for graph structure perturbation: Existing state-of-the-art certification methods (Zhang et al., 2022bb Wang et al. 2021 Bojchevski et al.) 2020) for graph classification only provide robustness guarantees for graph structure perturbations. Thus, we only show the comparison results of our GNNCert with these methods for attacks that perturb the graph structure. Figure 2 shows the comparison of the certified accuracy of our GNNCert with existing defenses. We find that our GNNCert outperforms existing defenses in most cases. Our GNNCert is better than existing defenses because perturbed edge could influence at most one sub-graph for our GNNCert but could influence multiple noisy graphs for existing defenses.
7

---

Published as a conference paper at ICLR 2024
(a) DBLP
(b) DD
(c) ENZYMES
(d) MUTAG
Contaa AUNMAY
Contba AUCEAAY
Contaa AUUEAAY
Contral AUCEAAY
Twtutake
Tosta
(c) NCTI
(f) PROTEINS
REDDIT-B
(h) COLLAB
Figure 4: Impact of the number of groups T, on GNNCert for structure division.
(a) DBLP
(b) DD
(c) ENZYMES
(d) MUTAG
Contana ALCEMAA
Cuntaa ALCEMAA
Cuntaa ALCHNAN
Cunta
(c) NCTI
(f) PROTEINS
REDDIT-B
(h) COLLAB
Figure 5: Impact of the number of groups Ty GNNCert for feature division.
Our GNNCert is more efficient than existing defenses: We also compare the efficiency of GNNCert with existing defenses. Table [ and (in Appendix) compare the training and testing costs. We have observations from the experimental results. First, GNNCert is more efficient than existing methods in training the base graph classifier (note that we train the same number of epochs for the base classifier our comparison). Our GNNCert is more efficient because, on average. sub-graphs used to train a base graph classifier for our GNNCert have less number of edges than the noisy graphs used by existing defenses. Second, we find that our GNNCert is more efficient in making predictions for testing graphs. The reason is that those three existing methods need to generate 1,000 noisy testing graphs for each testing graph while our method only needs to make predictions for 30 sub- rub-graphs. In Figure 6 in Appendix D also set the number of noisy graphs to be the same as our method (i.c., use 30 noisy graphs). We find that their certified perturbation sizes for testing graphs significantly decrease.
Training with sub-graphs improves the certified accuracy of GNNCert: We train base graph classifier using sub-graphs created from training graphs. Figure 3 compares the certified accuracy of our GNNCert when the base classifier is trained with and without sub-gra aob-graphs. The result shows training with sub- aub-graphs improves the certified robustness guarantees our GNNCert. The reason that the base graph classifier trained sub-graphs is more likely make correct predictions for sub- graphs created from a testing graph.
Impact of T./Ty on our GNNCert for structure/feature division: Figure and Figure 5 show the impact of T, and Ty the certified accuracy of our GNNCert with the structure division and feature
8

---

Published as a conference paper at ICLR 2024
division, respectively. In general, find that GNNCert is more robust when T2 (or Tÿ) increases. The reason is that our GNNCert could tolerate more perturbed sub-graphs as Tg (or Ty) increases.
Figure shows the impact of the hash function on our GNNCert. The experimental results show our GNNCert achieve similar certified accuracy for different hash functions, meaning GNNCert is insensitive the hash function.
Impact of hash function H. on our GNNCert:
Impact the architecture of graph neural network: VigureBiin Appendix shows the impact of the architecture of the base graph classifier on our GNNCert. The results show GNNCert is effective for different architectures, meaning our GNNCert is generally effective for base graph classifiers with different architectures.
Our GNNCert can defend against structure and feature perturbations simultancously: Existing certified defenses for graph classification only focus on structure perturbation. By contrast, our GNNCert with structure- feature division could simultancously resist both structure and feature perturbations. Figure 9 10
and 12 (in Appendix) show experimental results under the default setting. Our experimental results demonstrate the effectiveness of our GNNCert for both graph structure and node feature perturbation.
We also conduct other experiments for ablation studies. Please refer to Appendix B for details.
5 DISCUSSION AND LIMITATION
Other graph tasks: We mainly focus on graph classification. We note that there are many other graph-relevant tasks such node classification, link prediction, and community detection graphs.
Many existing studies (Chen et al. 2017 Zügner et al., 2018 Dai et al. 2018 Wang & Gong 2019
Bojehevski & Günnemann 2019a Li et al. 2020 Sun al. 2020 Ma al. 2020) show those tasks
are vulnerable to adversarial attacks as well. In response, many certified defenses (Bojchevski &
Günnemann 2019b Jia al. 2020 Schuchardt et al. 2020 Wang et al. 202T Scholten al.) 2022)
were proposed for these tasks. We leave the comprchensive study for those tasks as a future work.
Node classification: Our method could be extended to node classification. Given node, view its ego network as graph. We can use our GNNCert to build an ensemble graph classifier to predict the label of node via its ego network. We use the white-box attack in Wan al. (202 la) to craft small perturbation such that a graph classifier makes incorrect predictions. For standard graph classifier (GIN), the accuracy drops from 76% 2% when adding/deleting most edges to each testing graph. Under the same perturbation, the accuracy of GNNCert is 68% for perturbed testing graphs. The results demonstrate that GNNCert is robust against perturbations for node classification.
Node insertion/deletion:: Our GNNCert could be further extended to certify node insertion/deletion. In particular, we could divide nodes into different sub- uub-graphs (using hash function calculate group ID for each node), where each node only belongs to one group. Thus, inserting/deleting one node would influence most one sub-graph, enabling us derive the robustness guarantees. We added an experiment to validate this. On MUTAG dataset, our GNNCert could achieve a 59% certified accuracy when an attacker could arbitrarily add/delete one node (note that the attacker could arbitrarily add/delete edges for that node).
Local structure: For strueture-feature division, our method could utilize local structure with moderate number of sub-graphs. Each sub-graph may lose local structure information when the number sub-graphs large, i..., there is a tradcoff between accuracy and robustness.
CONCLUSION
We propose GNNCert, a certified defense against graph structure and/or node feature perturbations on graph neural networks for graph classification. GNNCert provably predicts the same label for testing graph once the graph structure and/or node feature perturbation is bounded. Our extensive experimental results on 8 benchmark datasets show GNNCert achieves better robustness guarantees and is more efficient than state-of-the-ar defenses. It is an interesting future work to generalize GNNCert to certify the robustness for other tasks such community detection.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
We thank the anonymous reviewers for their insightful reviews. This work was partially supported by the Cisco Research Award and National Science Foundation under grant Nos. ECCS-22 269226, CCF. 2331302, CNS-2241713 and CNS-2339686 Results presented in this paper were obtained using the Chameleon testbed supported by NSF. Any opinions, findings and conclusions recommendations expressed this material are those of the author(s) and do not necessarily reflect the views of the funding agencies.
REFERENCES
Aleksandar Bojchevski and Stephan Günnemann. Adversarial attacks node embeddings via graph poisoning. In International Conference on Machine Learning, pp. 695-704, PMLR, 2019a.
Aleksandar Bojchevski and Stephan Günnemann. Certifiable robustness to graph perturbations. Advances in Neural Information Processing Systems, 32, 2019b.
Aleksandar Bojchevski, Johannes Gasteiger, and Stephan Günnemann. Efficient robustness certifi- cates for discrete data: Sparsity-aware randomized smoothing for graphs, images and more. In International Conference Machine Learning, pp. 1003-1013, PMLR, 2020.
K.M. Borgwardt, C.S. Ong. S. Schönauer, SVN Vishwamathan, A.J. Smola, and H. Kriegel. Protein function prediction via graph kernels. Bioinformatics, 21:i47-i56, 2005.
Hongming Chen, Ola Engkvist, Yinhai Wang, Marcus Olivecrona, and Thomas Blaschke. The rise of deep learning in drug discovery. Drug discovery today, 2341:122, 2018.
Jinyin Chen, Huiling Xu, Jinhuan Wang, Qi Xuan, and Xuhong Zhang. Adversarial detection on graph structured data. In Proceedings of the 2020 Workshop on Privacy-Preserving Machine Learning in Practice, pp. 37-41, 2020.
Jinyin Chen, Dunjie Zhang, Zhaoyan Ming, Kejie Huang, Wenrong Jiang, and Chen Cui. Graphat- tacker: A general multi-task graph attack framework. IEEE Transactions on Network Science and Engineering, 9(2)5777-555, 2021.
Yizheng Chen, Yacin Nadji, Athanasios Kountouras, Fabian Monrose, Roberto Perdisci, Manos Antonakakis, and Nikolaos Vasiloglou. Practical attacks against graph- clustering. In Proceedings of the 2017 ACM SIGSAC conference on computer and communications security, pp. 1125-1144 1142, 2017.
Jeremy M Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. arXiv preprint arXiv: arXiv:1902.022 1902.0298. 2019.
Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, and Le Song. Adversarial attack on graph structured data. In International conference machine learning, pp. 1115-1124. PMLR, 2018.
A.K. Debnath, R.L. Lopez de Compadre, G. Debnath, A.J. Shusterman, and C. Hansch. Structure- activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity. Journal of medicinal chemistry, 34(2)7886-777, 1991.
P.D. Dobson and A.J. Doig. Distinguishing enzyme structures from non-enzymes without alignments. of Mol. Bio., 330(4):771-783,, 2003.
Zayd Hammoudeh and Daniel Lowd. Feature partition aggregation: A fast certified defense against a union of L_0 attacks. In The Second Workshop New Frontiers in Adversarial Machine Learning, 2023.
Mchadi Hassen and Philip K Chan. Scalable function call graph-based malware classification. In Proceedings of the Seventh ACM on Conference on Data and Application Security and Privacy, pp. 239-248, 2017.
10

---

Published as a conference paper at ICLR 2024
W. Hu, M. Fey, M. Zitnik, Y. Dong, H. Ren, B. Liu, M. Catasta, and J. Leskovec. Open Graph Benchmark: Datasets for Machine Learning on Graphs. Adv. in NeurIPS 33, 2020.
Jinyuan Jia, Binghui Wang, Xiaoyu Cao, and Neil Zhenqiang Gong. Certified robustness of commu- nity detection against adversarial structural perturbation via randomized smoothing. In Proceedings of The Web Conference 2020, 2020.
Jinyuan Jia, Xiaoyu Cao, and Neil Zhenqiang Gong, Intrinsic certified robustness of bagging against data poisoning attacks. Proceedings of the AAAI Conference on Artificial Intelligence, 2021.
Jinyuan Jia, Yupei Liu, Xiaoyu Cao, and Neil Zhenqiang Gong. Certified robustness of nearest neighbors against data poisoning and backdoor attacks. In Proceedings of the AAAI Conference Artificial Intelligence, 2022.
Hongwei Jin, Zhan Shi, Venkata Jaya Shankar Ashish Peruri, and Xinhua Zhang. Certified robustness of graph convolution networks for graph classification under topological attacks. Advances in neural information processing systems, 33:8463-8474, 2020.
Thomas N Kipf and Max Welling. Sumi-super classification with graph convolutional networks.
arXiv preprint 1609 02900, 2016.
Deguang Kong and Guanhua Yan. Discriminant malware distance learning on structural information for automated malware classification. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 1357-1365, 2013.
Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. In 2019 JEEE Symposium Security and Privacy (SP), pp. 656-672. IEEE, 2019.
Alexander Levine and Soheil Feizi. Deep partition aggregation: Provable defenses against general poisoning attacks. In International Conference on Learning Representations, 2020a.
Alexander Levine and Soheil Feizi. (de) randomized smoothing for certifiable defense against patch attacks. 2020b.
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, pp. 4585 1185-4593,115 2020c.
Jia Li, Honglei Zhang, Zhichao Han, Yu Rong, Hong Cheng, and Junzhou Huang. Adversarial attack on community detection by hiding individuals. In Proceedings of The Web Conference 2020, pp. 917-927, 2020.
Junying Li, Deng Cai, and Xiaofei He. Learning graph-level representtionnnnn for drug discovery. arXiv preprint vwXiiv:709.03744 2017.
Jiaqi Ma. Shuangrui Ding, and Qiaozhu Mei. Towards more practical adversarial attacks graph neural networks. Advances in neural information processing systems, 33:4756-4766, 2020.
Jiaming Mu, Binghui Wang, Qi Li, Kun Sun, Mingwei Xu, and Zhuotao Liu. A hard label black-box adversarial attack against graph neural networks. In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security (CCS), 2021a.
Jiaming Mu, Binghui Wang, Qi Li, Kun Sun, Mingwei Xu, and Zhuotao Liu. A hard label black-box adversarial attack against graph neural networks. In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, pp. 108-125, 2021b.
Felix Mujkanovic, Simon Geisler, Stephan Günnemann, and Aleksandar Bojchevski. Are defenses for graph neural networks robust? Advances Neural Information Processing Systems, 35: 8954-8968, 2022.
Shirui Pan, Xingquan Zhu, Chenggi Zhang, and S Yu Philip. Graph stream classification using labeled and unlabeled graphs. In 2013 IEEE 29th International Conference on Data Engineering (ICDE), pp. 398-409. IEFE, 2013.
11

---

Published as a conference paper at ICLR 2024
Hengzhi Pei, Jinyuan Jia, Wenbo Guo, Bo Li, and Dawn Song. Textguard: Provable defense against backdoor attacks on text classification. In NDSS, 2023.
Yan Scholten, Jan Schuchardt, Simon Geisler, Aleksandar Bojchevski, and Stephan Günnemann. Randomized message- interception smoothing: Gray-box certificates for graph neural networks. Advances in Neurul Information Processing Systems, 15:33146-3311 2022.
Jan Schuchardt, Aleksandar Bojchevski, Johannes Gasteiger, and Stephan Günnemann. Collective robustness certificates: Exploiting interdependence in graph neural networks. In International Conference on Learning Representations, 2020.
Yiwei Sun, Suhang Wang, Xianfeng Tang, Tsung- Yu Hsich, and Vasant Honavar. Adversarial attacks on graph neural networks via node injections: A hierarchical reinforcement learning approach. In Proceedings of the Web Conference 2020, pp. 673-683 2020.
Haoteng Tang, Guixiang Ma, Yurong Chen, Lei Guo, Wei Wang, Bo Zeng, and Liang Zhan. Ad- versarial attack on hierarchical graph pooling neural networks. arXiv preprint arXiv:2005. 11560, 2020.
N. Wale, LA. Watson, and G. Karypis. Comparison of descriptor spaces for chemical compound retrieval and classification. Knowledge and Information Systems, 14(3):347-375, 2008.
X Wan, H Kenlay, B Ru, A Blaas, MA Osborne, and X Dong. Adversarial attacks on graph classification via bayesian optimisation. ArXiv Preprint ArXiv, 2021a.
Xingchen Wan, Henry Kenlay, Robin Ru, Arno Blaas, Michael A Oshorne, and Xiaowen Dong. Adversarial attacks on graph classifiers via bayesian optimisation. Advances in Neural Information Processing Systems, 34:6983-6996, 2021b.
Binghui Wang and Neil Zhenqiang Gong. Attacking graph-based classification via manipulating the graph structure. In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, pp. 2023-2040, 2019.
Binghui Wang, Jinyuan Jia, Xiaoyu Cao, and Neil Zhenqiang Gong. Certified robustness of graph neural networks against adversarial structural perturbation. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 1645-1653, 2021.
Binghui Wang, Youqi Li, and Pan Zhou. Bandits for structure perturbation- black-box attacks to graph neural networks with theoretical guarantees. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 13379-13387, 2022.
Binghui Wang, Meng Pang. and Yun Dong. Turning strengths into weaknesses: A certified robustness inspired attack framework against graph neural networks. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 16394-16403, 2023.
Mark Weber, Giacomo Domeniconi, Jie Chen, Daniel Karl I Weidele, Claudio Bellei, Tom Robin- son, and Charles E Leiserson. Anti-money laundering in bitcoin: Experimenting with graph convolutional networks for financial forensics. arXiv preprint arXiv:/908.0220 0259/, 2019.
Chong Xiang, Arjun Nitin Bhagoji, Vikash Sehwag, and Prateek Mittal. (PatchGuard]: A provably robust defense against adversarial patches via small receptive fields and masking. In 30th USENIX Security Symposium (USENIX Security 21). pp. 2237-2254, 2021.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019. URL https
/oopereview..oo .nt/ forum 2id ry5a611555
Jaqqi Yan, Guanhua Yan, and Dong Jin. Classifying malware represented as control flow graphs using deep graph convolutional neural network. In 2019 49th annual IEEE/FFIP international conference on dependable systems and networks (DSN), pp. 52-63. IEEE, 2019.
Yanardag and V.N. Vishwanathan. Deep graph kernels. In Proc. 21th SIGKDD, pp. 1365-1374, 2015.
12

---

Published as a conference paper at ICLR 2024
Jiehang Zeng, Jianhan Xu, Xiaoqing Zheng, and Xuanjing Huang. Certified robustness to text adversarial attacks by randomized [mask]. Computational Linguistics, 49(2):395 -2013999---72.. 2023.
He Zhang, Bang Wu, Xiangwen Yang, Chuan Zhou, Shuo Wang. Xingliang Yuan, and Shirui Pan. Projective ranking: A transferable evasion attack method on graph neural networks. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pp. 3617-3621, 2021a.
He Zhang, Xingliang Yuan, Chuan Zhou, and Shirui Pan. Projective ranking-based -based gnn evasion attacks. IEEE Transactions on Knowledge and Data Engineering, 2022.
Jinghuai Zhang, Jinyuan Jia, Hongbin Liu, and Neil Zhenqiang Gong. Pointcert: Point cloud
classification with deterministic certified robustness guarantees. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, 2023.
Li Zhang and Haiping Lu. Ceaturreimmporaaccc-vaarr and robust aggregator for gen. In Proceedings of the 29th ACM International Conference on Information & Knowledge Management, pp. 1813- 1822, 2020.
Zaixi Zhang, Jinyuan Jía, Binghui Wang, and Neil Zhenqiang Gong. Backdoor attacks to graph neural networks. In Proceedings of the 26th ACM Symposium on Access Control Models and Technologies, pp. 15-26, 2021b.
Xin Zhao, Zeru Zhang, Zijie Zhang, Lingfei Wu, Jiayin Jin, Yang Zhou, Ruoming Jin, Dejing Dou, and Da Yan. Expressive 1-lipschitz neural networks for robust multiple graph learning against adversarial attacks. In International Conference on Machine Learning, pp. 12719-12735. PMLR, 2021.
Daniel Zügner, Amir Akbarnejad, and Stephan Günnemann. Adversarial attacks on neural networks for graph data. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 2847-2856, 2018.
13

---

Published as a conference paper at ICLR 2024
Table 2: Statisties of datasets.
Datasets
#Training graphs
#Testing graphs
#Classes
DBLP (Pan et al.
2013
12,971
6,485
2
DD (Dobson & Doig
2003
785
393
2
ENZYMES (Hu et al.
2020
400
200
6
MUTAG (Debnath al.
1991
125
63
2
NCI1
Wale al.
2008
2,740
1,370
2
PROTEINS (Borgwardt et al.
2005
742
371
2
REDDIT-B
Yanardag & Vishwanathan
2015)
1,333
667
2
COLLAB
Yanardag & Vishwanathan
2015
3,333
1,667
3
A
PROOF OF THEOREM
Given clean testing graph G, our GNNCert uses structure (or feature structure-feature) division to divide it into sub-gray sub-graphs (denoted by 91, 92. ... .vv). ,. Given a base graph classifier and those T sub-graphs, use No to denote the number of sub-graphs that are predicted as the label c by the given base graph classifier. Formally, We use GP to denote an adversarially perturbed graph. Moreover, we use 9 92 ",,'.. S to denote the T sub-graphs created by our GNNCert for GP using structure (or feature structure-feature division. Recall that M is the total number of sub-graphs in G
have N₂ Σ T(J(GR) c), where II is the indicator function.
O that are corrupted. are different from those in G1, G2. GNv.
Thus, at most M sub-graphs among GJ, ...... ....
Formally, we have Σi= I[Gxx # G)) < M. We use No to denote the number of sub-graphs among 02, St that predicted as the label i.e., No Σi I(S(G)) - c). Then, have c) < E == I(f(G²) = c) + M S N + M. Similarly, we have No 2 N. M. Suppose / is the predicted label of our GNNCert for the clean graph G. Then, our GNNCert predicts the label / when we have the following: N; - M > maxce ,CM (N (Ne-1( M)).
No ΣT_ Ii=IT((GG)
N. maN.e my ( (N.cc()
In other words, we have M
B PROOF OF THEOREM 2
We reuse the notations used in the proof of Theorem Our key idea of the proof is to construct such base graph classifier f' such that the predicted label changes when M/ + sub-graphs are corrupted. In particular, we select M/ + sub-graphs among G, ... GN that are predicted the label and corrupt them. Moreover, we let the base graph classifier f to predict the label & = arg max.341 N II(1 S c)) for those corrupted sub-graphs. Then, we have N/" N; M2 - and N N.+ MP +1. Since M is the largest integer such that Ni MP max ..,.,,,........... .CyM) (N. I(I < MP) holds. Thus, have N, (MP S max cy (N. T[( < c) M 1). In other words, the / is not guaranteed to be predicted with our constructed base graph classifier f'
C DETAILS OF DATASETS
Table showws the statistics the 8 datasets used our evaluation.
D COMPARING OUR GNNCERT WITH THREE BASELINES WHEN SETTING THEIR NUMBER OF NOISY GRAPHS TO BE 30
We compare the computation cost and the certified accuracy of our GNNCert with the three compared methods when we generate 30 noisy graphs for the three compared methods. Table compares the computation costs for each testing graph. We find that those defenses have similar computation costs.
14

---

Published as a conference paper at ICLR 2024
Dojeherski Wang al. Zhoang ours
Curtified
Porturlation
Figure 6: Comparing the certified accuracy of our GNNCert when we generate 30 noisy graphs for the three compared methods. The dataset is MUTAG.
However, the certified accuracy of those three methods drop very quickly shown in Figure 6 The reason is that those defenses utilize Monte Carlo sampling to estimate the certified perturbation size. Thus, they need to generate many noisy graphs for each testing graph accurately estimate the certified perturbation size.
E
OTHER EXPERIMENT RESULTS
Impact of the order of Node ID: We note that each node has node ID. We always put the node with smaller ID first in our experiments. We also add an experiment to put the node with larger ID first on MUTAG dataset. The certified accuracy is 92% (smaller ID first) and 92% (larger ID first) when an attacker arbitrarily adds/deletes one edge, respectively. The results demonstrate that our method is insensitive to the orders of nodes.
Varying N depending on the graph size: We use fixed number of sub-graphs on 8 datasets to be consistent. Our robustness guarantee against graph structure and node feature perturbation still holds when varying N based on the number of nodes in graph. For instance, we could set T, = 0.3 #nodes in graph On MUTAG dataset, the certified accuracies are 90% and 54% when an attacker could arbitrarily add/delete and edges.
Comparing the accuracy of our ensemble graph classifier with standard graph classifier: We conduct experiments to compare the accuracy of the normally trained GIN and GNNCert with GIN trained sub-graphs. We have the following observations from the experimental results. On MUTAG, DD, COLLAB, DBLP, ENZYMES, PROTEINS datasets, the accuracy of GNNCert is at most 3% lower than that of normally trained GIN. On REDDIT and NCII datasets, the accuracy of GNNCert at most 15% lower than that of normally trained GIN. The reason is that there is tradeoff between accuracy without attacks and robustness. We note that such tradeoff widely exists for certified defenses (Cohen et al.) 2019 Lecuyer et al. 2019 Levine & Feizi] (0206)) Our GNNCent (with GIN the base classifier) reduces to GIN when set smaller T, in practice.
To reduce the accuracy drop, we could
Comparing the accuracy of base classifiers for different certification methods: We also com- pare the accuracy of base classifiers for different certified methods. We find that, the accuracy of GNNCert's 's base classifier is higher than those of other defenses, which explains why our GNNCert outperforms them. For instance, on MUTAG dataset, the accuracy of GNNCert's 's base classifier is 91.85% By contrast, the accuracy of base classifiers for Bojchevski al.. Wang et al., Zhang et al. are 67.66 88% 88.89% and 82.59%, respectively.
15

---

Published as a conference paper at ICLR 2024
Table Comparing the computation cost (s) when we generate 30 noisy graphs for three compared methods. The dataset is MUTAG.
Compared method
Total (s)
Bojchevski al.
8.42
Wang et al.
12.62
Zhang al.
12.80
Ours
7.94
Table 4: Comparing the computation costs of GNNCert and existing defenses on multiple datasets.
PROTEINS
ENZYMES
NCI1
Method
Train (s)
Test (s)
Train (s)
Test (s)
Train (s)
Test (s)
Bojchevski et al. (2000)
2,351
421
1,930
157
1,811
920
Wang et al. 2021
2,132
788
1,760
2,629
1,703
4,488
Zhang et al.
(021b
1,575
196
1,427
95
1,357
525
GNNCert
829
13
760
11
815
22
OIIEEA ALCI
KITE SHAZ2
SITE
SITS SHAZE
SHAZE
SHAZ20
(a) DBLP
(b) DD
(c) ENZYMES
(d) MUTAG
MHAT
MELL
SEAL SHADK
MHAT
(e) NCII
( PROTEINS
REDDIT-B
(h) COLLAB
Figure 7: Impact of the hash function H on GNNCert.
16

---

Published as a conference paper at ICLR 2024
6AC
GAC
GAC
GAT
Petecbition FiM
Dotelaates 5
(a) DBLP
(b)
(c) ENZYMES
(d) MUTAG
600
Cantial AIQEAA
600
(c) NCTI
(f) PROTEINS
REDDIT-B
(h) COLLAB
Figure Impact of the architecture of the base graph classifier on GNNCert.
0.5
6 condion
61
12 14
E Feature Perturbation
10
17
15 Feature Perturbatton
14
(a) DBLP
(b) DD
Figure 9: Our GNNCert could resist structure and feature perturbation simultaneously.
E114
0.1
62
Festura Pertonbationn Som
Fratore Portorbation 3000
15 0
(a) ENZYMES
(b) MUTAG
Figure 10: Our GNNCert could resist structure and feature perturbation sinultaneously.
17

---

Published as a conference paper at ICLR 2024
0.7
0.5
04
0.3
0.1
8
9 Brento
2
10
12
Festure Perturbation
12
Feature Purturlation
14
N
(a) NCTI
(b) PROTHINS
Figure 11: Our GNNCert could resist structure and feature perturbation simultaneously.
0.
65
0.4
0.
02
8
80 Blenen 8
6L
12
Teature Perturbatoo
E
10
17
Peature Porturbation
15 C
14
(a) REDDIT-B
(b) COLLAB
Figure 12: Our GNNCert could resist structure and feature perturbation simultaneously.
18


Reviews:
[{"review_id": "1i1oSsw8yl", "reviewer": "Reviewer_LqWt", "summary": "This paper claims to provide a robustness of graph classifications under adversarial attacks. It proposes a hashing method for partitioning the graph into several (overlapping) subgraphs and then ensembling them into a final classifier. The paper derives theoretical and empirical bounds on the robustness of the classifier, demonstrating that it behaves better than the state-of-the-art. No additional computational overhead is added on the classifier compared to state of the art.", "questions": "My single question that will affect my decision is the following?\nWas the perturbation uniform noise?\nCan the authors pick at least one or two datasets and experiment with types of noise that would make case in a realistic malicious agent scenario?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The theory of the paper is solid, and the experiments prove the point that the authors want to make.\nThe presentation is pretty clear and easy for the reader to follow.", "weaknesses": "As an expert in the security domain with a strong background in signal processing, the paper looks more like building a classifier robust to noise rather than a defense method against adversarial attacks. When it comes to internet security applications, in order to add value, someone has to work on real case scenarios where the deception in building the graph can be realistic. Here, the benchmarks are very weak in terms of real-case scenarios. In cases like malware or DNS graphs, etc, the deception models have to be very sophisticated and realistic. I understand that this is more like an ML theory paper, but it really has no value in real life. \nAnother problem that I have with this paper is the use of the term \"adversarial attack.\" A malicious agent tries to minimize the perturbation so that the perturbed graph is as close as possible to the initial one. Either through a black or white box attack, the agent tries to reverse engineer the classifier so that a small perturbation can lead to a big change in the output; they might choose to change, let's say, one feature or connection that will have a big impact. I don't see that study here. Instead, the authors claim that we will make it robust to a certain type of noise.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ylh6VbxRU7", "reviewer": "Reviewer_nFKx", "summary": "The paper introduces \"GraphGuard,\" a certified defense mechanism for graph classification, designed to protect against adversarial perturbations in both graph structure and node features. Unlike existing defenses that lack robustness or have high computation costs, GraphGuard offers deterministic robustness guarantees. Through evaluations on 8 benchmark datasets, GraphGuard is shown to outperform current state-of-the-art methods.", "questions": "See above.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "**Originality**: The paper stands out for its innovative use of hashing to create subgraphs that distinguish between different types of perturbations, namely structure, feature, and both. The deterministic robustness guarantee presented is a fresh and valuable approach in the domain of certified defenses. Furthermore, the incorporation of both structure and node features sets the work apart, as few studies consider node features in this context.\n\n**Quality**: The paper is grounded in solid theory and its effectiveness is corroborated by empirical evaluations.\n\n**Clarity**: The paper is articulate and straightforward. The authors proactively address and clarify potential ambiguities in each section, ensuring a smooth reading experience.\n\n**Significance**: Given the growing prominence of graph neural networks across various applications, addressing security in downstream graph tasks is paramount. This study zeroes in on the security of the graph classification task, potentially paving the way for enhanced security measures in other tasks like node classification and link prediction, emphasizing a deterministic robustness guarantee.", "weaknesses": "* On Page 4, at the end of line 4: Shouldn't the notation be $H(.)$%$T_s + 1$?\n\n* Based on my understnading $(S_{v_t} \\bigoplus S_{v_j}) \\neq (S_{v_j} \\bigoplus S_{v_t})$. If that is correct, then it seems in structure division explained in 3.3.1 the same edge can have two different hash values depending on which end node is visited first. Can the authors clarify this?\n\n* The hashing process, while detailed, lacks clarity on one aspect: How are node features transformed into string representations for the hash function? Given the diverse nature of node features in graphs, understanding this process, especially for features requiring unique treatments, is essential.\n\n* Could the authors provide an intuitive explanation for the preference of hash-based subsampling over methods like $\\tau$ fraction-based sampling (referenced in the benchmarks) or other similar techniques? What advantages does this approach offer and what are its potential limitations?\n\n* How do the authors determine the values for $T_s$ and $T_f$? It would be beneficial if this determination were associated with specific graph properties (e.g., the number of edges, nodes, diameter, path length, clustering coefficient, etc.), as this would guide potential users of this defense strategy in tailoring it to their datasets.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zuS0H0Ks26", "reviewer": "Reviewer_xWrk", "summary": "This paper develops a graph classifier called GraphGuard, that is certifiably robust to structure perturbations and node feature perturbations. The classifier first partitions the graph edges and/or features using a hash function to yield $N$ sub-graphs. The sub-graphs are then classified by a base model (e.g., a graph neural net) to produce $N$ predictions, which are aggregated by majority vote to yield a classification for the entire graph. GraphGuard is shown to be robust to a specified number of edge perturbations and/or arbitrary node feature perturbations that depends on the number of sub-graphs and the margin between votes. Experiments on eight datasets demonstrate that GraphGuard achieves better certified accuracy that three baseline certified methods.", "questions": "1. The number of sub-graphs $N$ seems to be fixed for all inputs. Would it make sense to vary $N$ depending on the graph size (e.g., number of nodes)?\n1. There doesn’t appear to be any restrictions placed on the hash function. I wonder whether it must be independent of the input’s edge structure and node features? Otherwise the certificate may not hold?\n1. Is it possible to certify robustness against node insertion/deletion using this approach?\n1. Does GraphGuard prevent the classifier from exploiting local structure, since each sub-graph tends to be sparse (both in terms of edges and node features)?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "1. GraphGuard makes improvements in several dimensions compared to prior work on certified graph classification. Specifically, it yields deterministic guarantees, it is less computationally expensive, it can cover edge and node feature perturbations simultaneously, and it is shown to achieve superior certified accuracy. Given the breadth of these improvements, I think it will be of interest to the robustness/verification community.\n\n1. The experiments are generally well-executed, apart from some issues mentioned below. It’s great to see results presented for several datasets and baselines. I appreciated the inclusion of experiments examining architectural choices, such as the architecture of the base neural network, and the choice of hashing function.\n\n1. I liked the presentation of the paper overall. The writing was clear, leaving me with few doubts about the details. I found Figure 1 especially helpful in understanding the method.", "weaknesses": "1. The paper fails to cite prior work on derandomized smoothing which is strikingly similar to GraphGuard. For example, Levine & Feizi (2020) designed a certifiably robust classifier that also splits the input into sub-parts, classifies the sub-parts using a base model, and makes the final classification using majority vote. While their method is applied to image classification to certify against patch attacks, the fundamental design pattern (and analysis) is similar to GraphGuard. More recently, Hammoudeh & Lowd (2023) showed that the same design pattern can be used to achieve certified robustness against L0 perturbations (including patch attacks) at training-time and test-time. Given this context, GraphGuard could be viewed as an extension of derandomized smoothing to a new domain (graphs), which could impact the assessment of technical novelty. **Update 21/11: The authors have promised to address this issue. I have therefore raised my _Presentation_ score from 1 to 3.**\n\n1. Although the experiments are comprehensive, I believe there is a crucial baseline missing: the base graph classifier (GIN) _without_ GraphGuard. Specifically, I would like to see a comparison of standard accuracy for GIN trained normally on full graphs, and GraphGuard with GIN trained on sub-graphs. This would allow for an assessment of GraphGuard’s impact on accuracy. This is important, as the standard accuracy of GraphGuard is fairly low for most datasets (around 70% based on Fig. 2)—it’s not clear whether this is due to GraphGuard or the inherent difficulty of the datasets. Incidentally, it may be interesting to report the accuracy of the base classifiers for all certified methods. Levine & Feizi (2020) found much higher base classifier accuracies for derandomized smoothing (which is similar to GraphGuard) than randomized ablation (which is similar to Zhang et al., 2021b). The same explanation may apply here. \n\n1. While GraphGuard outperforms prior methods in terms of certified accuracy, the standard accuracy is rather low (at around 70% for 6 of the 8 datasets). This has a bearing on the significance of the paper in my view, as the sacrifice in terms of accuracy seems to high to be practical. It’s also worth noting that the variant of GraphGuard that protects against structure and feature perturbations simultaneously suffers a severe accuracy drop for some of the datasets (DBLP and ENZYMES). For these datasets, the classifiers are no better than random based on the standard accuracy in Figs. 9 and 10.\n\nMinor:\n1. The idea of training the base classifier on sub-graphs is claimed to be a contribution. However this is standard practice in randomized smoothing. It would be unusual not to train in this way.\n1. Section 4.2: should alpha be 0.001? \n\n**References:**\n\n- Levine & Feizi, “(De)Randomized Smoothing for Certifiable Defense against Patch Attacks,” NeurIPS 2020. https://proceedings.neurips.cc/paper_files/paper/2020/file/47ce0875420b2dbacfc5535f94e68433-Paper.pdf\n\n- Hammoudeh & Lowd, “Feature Partition Aggregation: A Fast Certified Defense Against a Union of $\\ell_0$ Attacks,” AdvML-Frontiers 2023. https://openreview.net/forum?id=NX5Nxrz6PV", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (oral)