Provably Robust Explainable Graph Neural Networks against Graph Perturbation Attacks
Authors: Jiate Li
Meng Pang
Yun Dong
Jinyuan Jia
Binghui Wang
Venue: ICLR 2025 Poster (2025)
Keywords: Certiffed Defenses
Explainable Graph Neural Network
Explainable Artificial Intelligence
Primary area: alignment, fairness, safety, privacy, and societal considerations

Abstract: Explaining Graph Neural Network (XGNN) has gained growing attention to facilitate the trust of using GNNs, which is the mainstream method to learn graph data. Despite their growing attention, Existing XGNNs focus on improving the explanation performance, and its robustness under attacks is largely unexplored. We noticed that an adversary can slightly perturb the graph structure such that the explanation result of XGNNs is largely changed. Such vulnerability of XGNNs could cause serious issues particularly in safety/security-critical applications. In this paper, we take the first step to study the robustness of XGNN against graph perturbation attacks, and propose XGNNCert, the first provably robust XGNN. Particularly, our XGNNCert can provably ensure the explanation result for a graph under the worst-case graph perturbation attack is close to that without the attack, while not affecting the GNN prediction, when the number of perturbed edges is bounded. Evaluation results on multiple graph datasets and GNN explainers show the effectiveness of XGNNCert.

Published as a conference paper at ICLR 2025
PROVABLY ROBUST EXPLAINABLE GRAPH NEURAL NETWORKS AGAINST GRAPH PERTURBATION ATTACKS
Jiate Li", Meng Pang?. Yun Dong", Jinyuan Jia Binghui Wang'
Illinois Institute of Technology, USA, NNanchang University, China
Milwaukee School of Engineering, USA 'The Pennsylvania State University, USA
ABSTRACT
Explainable Graph Neural Networks (XGNNs) have garnered increasing attention for enhancing the transparency of Graph Neural Networks (GNNs), which are the leading methods for learning from graph-structured data. While existing XGNNs primarily focus on improving explanation quality, their robustness under adversarial attacks remains largely unexplored. Recent studies have shown that even minor perturbations to graph structure can significantly alter the explanation outcomes of XGNNs, posing serious risks in safety-critice applications such as drug discovery. In this paper, we take the first step toward addressing this challenge by introducing XGNNCert, the first provably robust XGNN. XGNNCert offers formal guarantees that the explanation results will remain consistent, even under worst-case graph perturbation attacks, as long as the number of altered edges is within a bounded limit. Importantly, this robustness is achieved without compromising the original GNN's predictive performance. Evaluation results on multiple graph datasets and GNN explainers show the effectiveness of XGNNCert. Source code is available at http::///gEEaaa.ccccm///etaaaaaa
INTRODUCTION
Explainable Graph Neural Network (XGNN) has emerged recently to foster the trust of using GNNs provides a human- uundesaaall way to interpret the prediction by GNNs. Particularly, given graph and a predicted node/graph label by GNN, XGNN aims to uncover the explanatory edges
(and the connected nodes) from the raw graph that is crucial for predicting the label (see Figure
[[a) an example). Various XGNN methods (Ying et al.] 2019 Luo et al., 2020) Yuan et al.) 2021
Zhang et al. 2022 Wang & Shen 2023 Behham & Wang 20244) have been proposed from different perspectives (more details see Section 5) and they have also been widely adopted in applications
including disease diagnosis (Pfeifer et al. 2022). drug analysis (Yang et al., 2022 Wang et al. 2023b).
fake news spreader detection (Rath et al. 2021), and molecular property prediction Wu et al. (2023
While existing works focus on enhancing the explanation performance, the robustness of XGNNs is largely unexplored. Li et al. (2024) observed that well-known XGNN methods (e.g., GNNEx- plainer (Ying et al., 2019). PGExplainer (Luo et al., (0200) are vulnerable to graph perturbation attacks GGivnn a graph, GNN model, and a GNN explainer, an adversary can slightly perturb few edges such that the GNN predictions are accurate, but the explanatory edges outputted by the GNN explainer on the perturbed graph is drastically changed. This attack could cause serious issues in the safety/security-crinn criitial applications such as drug analysis. For instance, Wang et al. (2023b) designs an XGNN tool Drug- -apllrerrrrrr for drug repurposing (reuse existing drugs for new diseases), where users input drug graph and the tool outputs the visualized explanation result (i.e., important chemical structure) useful for curing the diseases. If such tool is misled on adversarial purposes (i.e., adversary inputs carefully designed perturbed graph), may recommend invalid drugs with harmful side-effects. Therefore, it is crucial to design defenses for GNN explainers against these attacks.
Generally, defense strategies can be classified empirical defense and certified defense. Empirical defenses often can be broken by stronger/adaptive attacks, as verified in many existing works on defending against adversarial examples (Carlini et al.) (219)) and adversarial graphs (Zhang et al. 2021a Yang et al. 2024). We notice two empirical defense methods (Bajaj et al., [221;] Wang et al. 2023c) have been proposed robustify XGNNs against graph perturbations. Likewise, found they

---

Published as a conference paper at ICLR 2025
are ineffective against stronger attacks proposed in Li et al. (0244) (see Table In this paper, hence focus on designing certified defense for XGNNs against graph perturbation attacks. An XGNN is said certifiably robust against bounded graph perturbation if, for any graph perturbation attack with a perturbation budget that does not exceed this bound, the XGNN consistently produces the same correct explanation (formal definition is in Definition [ There are several technical challenges. First, GNN explanation and GNN classification are coupled in XGNNS. Robust GNN classifiers do not imply robust GNN explainers, and claiming robust explanations without correct GNN classification is meaningless] It is thus necessary to ensure both robust GNN classification and robust GNN explanation. Second, there is fundamental difference to guarantee the robustness of GNN classifiers and GNN explainers. This is because GNN classifiers map a graph to label, while GNN explainers map a graph to an edge set. All existing certified defenses (Jia et al., 2020) Jin et al., 2020) Wang
et al., 202 la Xia et al.
[024] Li & Wang 2025) against graph perturbations focus on the robustness
of GNN classifiers and cannot be applied to robustify GNN explainers.
In this work, we propose XGNNCert, the first certifiably robust XGNN against graph perturbation attacks. Given a testing graph, a GNN classifier, and a GNN explainer, XGNNCert consists of three
main steps. First, are inspired by existing defenses for classification (Levine & Feizi 2020b Jia
et al, 2021; 2022; Xia et al., 2024; Yang et al., 2024: Li & Wang 2025) that divide an input (e.g.. image) into multiple con--vvrrapping parts (e.g.. patches). However, directly applying the idea to divide the test graph into multiple non-overlapping subgraphs does not work well for robustifying GNN explainers. One reason is that it is hard for the GNN explainer to determine the groundtruth explanatory edges from each subgraph due to its sparsity. To address it, we propose to leverage both the test graph and its complete graph for "hybrid" subgraph generation. An innovation design here is only a bounded number of hybrid subgraphs could be affected when the test graph is adversarially perturbed with a bounded perturbation, which the requirement for deriving the robustness guarantee. Second, we build a majority- classifier on GNN predictions for the generated hybrid subgraphs, and a majority-vote explainer on GNN explanations for interpreting the prediction of the hybrid subgraphs. Last, we derive the certified robustness guarantee. Particularly, XGNNCert guarantees the majority-vote classifier yields the same prediction, and majority-vote explainer outputs close explanatory edges for the perturbed testing graph under arbitrary graph perturbations, when the number of perturbed edges is bounded (which we call certified perturbation size).
We evaluate XCNNCert on multiple XGNN methods on both synthetic and real-world graph dataset with groundtruth explanations. Our results show XCNNCert does not affect the normal explanation accuracy without attack. Moreover, XGNNCert shows it can guarantees at least edges are from the 5 groundtruth explanatory edges, when averaged 6.2 edges are arbitrarily perturbed in testing graphs from the SG+House dataset. Our major contributions are as follows:
We propose XGNNCert, to our best knowledge, the first certified defense for explainable GNN against graph perturbation attacks.
We derive the deterministic robustness guarantee of XGNNCert.
We evaluate XGNNCert on multiple graph datasets and GNN explainers and show its effectiveness.
2 BACKGROUND AND PROBLEM FORMULATION
GNN and XGNN: We denote graph as G = E), that consists of set of nodes e E V and edges E E E. A GNN, denoted as f. takes a graph G as input and outputs a predicted label y = f(G) E C, with including all possible labels. For instance, y can be defined on the graph G in graph classification, or specifie node e E V in node classification. An XGNN, denoted as g, uncovers the key component in G that contributes to the GNN prediction y. In this paper, we focus on the widely- edges in G. Particularly, this type of XGNN learns importance scores m for all edges & and selects the edges & C & with the top t scores in as the explanatory edges, where l is hyperparameter of the XGNN. Formally, m = g(, & = Ettops (m) E.topı (g(G,)) y)).
edge explanations where g takes (G, y) input and determines the important
Ad Adversarial Attack on XGNN: Given graph G and prediction y (by a GNN f), an XGNN g and its explanatory edges& & We notice that an attacker can perturb the graph structure to mislead the
in Appendix C also validate that if the GNN classifier is deceived, the explanation result would he drastically different compared with the groundtruth explanation.
Our additional experiments in Figure 12
2

---

Published as a conference paper at ICLR 2025
[ xx couiens
[(C)-A Prodiction
Prediction Changedt!)
CNN
GMN
GNN
f[0]=
G Original Graph
Clossdier Prodkt
Explarer
b. Explai
((G.)) Origanl Expleraioon
Prediction Unchainged
GNN Exprxeer
gtG. Peruubeed Exploration
Portureed Groph
Enaage Diffurerion (2)
(a) GNN Explanation
(b) Adversarial Attack on GNN Explanation
Figure I: (a) GNN for graph classification and GNN explanation. A GNN classifier f first predicts a label y for the graph G, and then GNN explainer g interprets the predicted label y to produce the explanatory edges & (b) Two possible graph perturbation attacks on the GNN explainer g: 1) the GNN prediction ú on the perturbed graph is different from y; 2) the GNN prediction on is kept, but the explanatory edges EN outputted by g after the attack is largely different from E
XGNN g- To be specific, the attacker could delete edges from G (to ensure stealthiness, the attacker does not delete edges in the explanatory edges &s, as otherwise it can be easily identified) or add new edge into G. We denote the adversarially perturbed graph as G = (V, E), with an attack budget M (i.e., the total number of deleted and added edges is no more than M). On the perturbed graph G, f gives new prediction أ f(C), and g produces new explanatory edges &. E.tops i)).
We assume the attacker has two ways to attack an XGNN, as illustrated in Fig (b).
1. The attacker simply misleads the GNN prediction. Note that if the prediction is changed (i.e., * y), even Eg Ek. the explanation is not useful as it explains the wrong prediction. This attack can be achieved via existing evasion attacks on GNNs, e.g., Dai et al. (2018); Zügner et al. (2018); Xu al. (:019): Mu et al. (2021); Wang et al. (2022a).
2. A more stealthy attack keeps the correct prediction. but largely deviates the explanation result. That is, the attacker aims to largely enlarge the difference between & and Ég with the prediction unchanged (Li et al. 2024).
The above results show existing XGNNs are vulnerable to effective and stealthy graph perturbation attacks. Also, as various works (Carlini et al. 2019 Mujkanovic et al.. 2022) have demonstrated, empirical defenses often can be broken by advanced/stronger attacks. Such observations and past experiences motivate us to design certifiably robust XGNNs, i.e., that can defend against the worst-case graph perturbation attacks with a bounded attack budget.
Problem Formulation:
Definition ((M,, A) A)-Certifiably robust XGNN). We say an XGNN is (Mx, A) -eretttiy robust, if, for any graph perturbation attack with no more than MA perturbed edges on a graph G, the GNN prediction the induced perturbed graph G always equals to the prediction y on G. and there least À (< k)) same edges in the explanatory edges EL after the attack and the explanatory edges & without the attack. We also call MA the certified perturbation size. Further, we denote by M the maximal MA associated with X, for which a specific XGNN remains certifiably robust.
Remark: smaller À implies a larger Mj. When À k. robust XGNN should guarantee Eg Ex- In this paper, we focus on deriving the certifiably robust XGNN for the graph-level classification task. The adaptation of the proposed defense techniques (in Section 3 to other graph-related tasks, such as node-level classification and edge-level classification, is discussed in Appendix D
3 XGNNCERT: OUR CERTIFIABLY ROBUST XGNN
In this section, we propose XGNNCert, our certifiably robust XGNN against graph perturbation attacks. Given testing graph, a GNN classifier, and a GNN explainer, XGNNCert consists of three major steps. 1) Hybrid subgraphs generation: it aims to generate set of subgraphs that leverage the edges from both the testing graph and its complete graph. 2) Majority-voting based classification and explanation: it builds majority-vote based classifier (called voting classifier) on GNN predictions for the hybrid subgraphs, as well as majority-vote based explainer (called voting explainer) on GNN explanations for interpreting the predicted label of the hybrid subgraphs. 3) Deriving the certified robustness guarantee: based on the generated subgraphs, our voting classifier and voting explainer, derives the maximum perturbed edges, such that our voting classifier guarantees the same prediction on the perturbed graph and testing graph, and our voting explainer guarantees the explanation results on the perturbed graph and the clean graph are close. Figure shows overview of our XGNNCert.
3

---

Published as a conference paper at ICLR 2025
Oug ea O Crapaee Ouart Co Selgnots, (o)) Sederattonn (03) Hyded Suggraps (F))
Eaplasinee Partibeed
Go
G
11 (6G)
(G
Slyp Payast Supgraatm Generztonn
Step Ingortty roling bamed Class Foatiee
Dap 2. Hajorty waling bamed Expliratio
Cantilee Gentoraas
Figure 2: Overview of the proposed three-step certifiably robust XGNN.
3.1 HYBRID SUBGRAPHS GENERATION
A straightforward idea is to adapt the existing defense strategy for classification (Levine & Feizi
20206 Xiang et al., 202T Jia et al. 2021 2022 Xia et al. (024) that divides an input into multiple non-overlapping parts. Particularly, one can divide a graph into multiple non-overlapping subgraphs, such that only a bounded number of subgraphs are affected when the graph is adversarially perturbed under a bounded perturbation. However, this strategy does not work well to robustify GNN explana- tion (Our results in Section alsoo validate this) due to two reasons: (1) Every edge in a graph appears only once in all subgraphs. This makes it hard for the GNN explainer to ensure the groundtruth explanatory edges to have higher scores than non-explanatory edges. (2) All subgraphs only contain existent edges in the graph, while nonexistent edges can be inserted into the graph during the attack and their importance for explanation needs to be also considered. To address the challenge, we develop a hybrid subgraph generation method, that consists of two steps shown below.
Generating Subgraph Indexes via Hash Mapping: We use the hash function (e.g., MD5) to generate the subgraph indexes as done in Xia et al. (2024); Yang et al. 2024 A hash function takes input as a bit string and outputs an integer (e.g.. within range [0, 2 - ID. Here, we propose to use the string of edge index as the input to the hash function. For instance, for an edge
(u. v), we denote its string as str(u) + str(v), where the str(-) function transfers the index number into a string in fixed length (filled with prefix "O"s), and"+" means the string concatenation Then we can map each edge using the hash function to a unique index. Specifically, we denote the hash function as h and assume T' groups in total. Then for every edge (u, v). we compute its subgraph index ie as
ie h(str(u) + str(v)) mod ++
Generating Hybrid Subgraphs: Based on the hash function, we can construct a set of subgraphs for any graph. However, instead of only using existent edges in the given graph to construct subgraphs, we propose to also use nonexistent edges to promote the robustness performance for GNN explainers. A key requirement is: how to guarantee only a bounded number of subgraphs are affected when the original graph is adversarially perturbed. To address it, we innovatively propose to use the complete graph, and our theoretical results in Theorem 2 show the requirement can be satisfied.
Dividing the input graph into subgraphs: For an input graph G = =VV.8) E). we use Ei to denote the set of edges whose subgraph index is i, i.e., E¹ -Ve E E ie = i). Then, we can construct T subgraphs for G as (G' = =(V : 1,2....,777 ,T).
Dividing the complete graph into subgraphs: We denote the complete graph of G Ge (u, v), Vu, v E V < v... Similarly, we can divide Ge into T subgraphs using the same hash function. First, the edges having a subgraph index is denoted as E = ['ve e Eg is i).
Then, create the T subgraphs for Ge as: (Gi (V, E+) : 1,2, T).
"Our theoretical results require the graph division function has two important properties: 1) It deterministic. such that each edge and node a graph is deterministically mapped into only one subgraph. This property is the core to derive our theoretical results. 2) It is independent of the graph structure, as otherwise an attacker may reverse-engincer the function to find the relation hetween the output and input, and possibly break the defense. The used hash function can achieve both properties.
Foor instance, with 4-hit length, an edge 12-21 is represented as the string "0012" and "0021", respectively. Then the concatenated string hetween the edge 12-21 is "00120021
We put the node with smaller index (say u) first and let h(str(r) + str(w)) = h[str(u) + str(r))-
4

---

Published as a conference paper at ICLR 2025
Hybrid subgraphs: Now combine subgraphs {G*} with {G²,} to construct the hybrid subgraphs. For each subgraph G", we propose to combine it with a fraction (say p) of the subgraphs in {G% to generate hybrid subgraph, denoted as G There are many ways for the combination, and the only constraint is that the subgraph Gog with the same subgraph index i as G' is not chosen in G' in order to maintain the information from the original subgraph Gi (otherwise it is overlaid by Gt)). Let T_ TV \ i be the index set not including i. For instance, we can choose [eT') indexes, denoted as Th from T_ uniformly at random. Then a constructed hybrid subgraph is G = (V,E)), where
E (UJetz, U
Note that a too small or too large p would degrade the explanation performance. This is because a too large would make excessive nonexistent edges be added in each G and too small p would make explanatory edges be difficult to have higher important scores than non-explanatory edges. Our results show the best performance is often achieved with modest p. e.g.- p [0.2, 0.4].
With the built hybrid subgraphs, we prove in Theorem 2 that for any two graphs with M different edges (but same nodes), there at most M different ones between their respective hybrid subgraphs. We emphasize this is the key property to derive our certified robustness guarantee in Section 3.3
Theorem (Bounded number of different subgraphs). For any two graphs = E), = = satisfying | \ El = M. The corresponding hybrid subgraphs generated using the above strategy are denoted as {G' } and {G respectively. Then {Giy} } and {G'H} have at most M different graphs.
Proof. See Appendix A.I
3.2 MAJORITY VOTING-BASED CLASSIFICATION AND EXPLANATION
Inspired by existing works (Levine & Feizi| 2020b Dia al. 2022; Xia et al. 2024 Yang et al.
2024), we propose to use the majority vote to aggregate the results on the hybrid subgraphs. We then design voting classifier and voting explainer that can respectively
the robust GNN classifier and robust GNN explainer, as expected. Assume we have testing graph G with label y. set of T hybrid subgraphs {G*,} J built from G, a GNN classifier f. and GNN explainer g.
Voting Classifier: We denote by ne the votes of hybrid subgraphs classified as the label c by f. i.e.
T
I(((C))) c), E.
(3)
1=1
where I(-) is an indicator function. Then, we define voting classifier f ass:
J(G) = arg max T4g-
cEC
Voting Explainer: Recall that when a GNN explainer interprets the predicted label for a graph, it first learns the importance scores for all edges in this graph and then selects the edges with the highest scores as the explanatory edges. Motivated by this, we apply g on the hybrid subgraphs having the same predicted label as the majority-voted label to obtain the explanatory edges, and then vote the explanatory edges from these hybrid subgraphs. Edges with top-k scores are the final explanatory edges. Specifically, for each GH apply g obtain its edges' importance scores m' =[G f(G)). We define the votes nž of each edge Ec as the times that its importance score m. is no less than y fraction of the largest scores in every hybrid subgraph G₁₃, with the prediction f(G = f(G):
n Σ Imm 2 min)) -(((G)))))))) F(G)), Ve E Ec,
(5)
where X(v) means the y size(x) largest element in x and is a tuning hyperparameter (we will study its impact in our experiments). We denote n" as the set of votes for all edges in Ec. Then we define our voting explainer g² outputting the edges from G' with the top-k scores in n 16 = E.topx(n")
g"
$f returns smaller label index when ties exist. When two edges have the same n², the edge with smaller index is selected by g".
5

---

Published as a conference paper at ICLR 2025
Remark: Traditional GNN classifiers are designed to be node permutation invariant (Kipf & Welling 2017 Veličković et al. 2018 Xu et al. 2019), meaning that the model's predictions remain consistent regardless of how the nodes in the graph are permuted. In contrast, our voting classifier is node permutation variant due to the properties of the hash function. This implies that both the classification and explanation performances of XGNNCert may vary depending on the node ordering. However, we empirically observed that XGNNCert's 's performance remains relatively stable across different node permutations (see Table 2 in Appendix DD. Moreover, recent studies (Loukas] 2020; Papp et al.) 2021 Huang et al., 2022) suggest that node-order sensitivity can actually enhance the expressivity and generalization capabilities of GNNs. Additional discussions are provided in Appendix D
3.3 CERTIFIED ROBUSTNESS GUARANTEE
In this section, we derive the certified robustness guarantee against graph perturbation attacks using our graph division strategy and introduced robust voting classifier and voting explainer.
We first define some notations. We let f(G) by assuming the voting classifier f has accurate label prediction, and & = g" y) by assuming the voting explainer 9 has an accurate explanation. We denote G (V,E) the complement of G, and EM the edges in & with top-M scores in n². We introduce the non-existent edges E with top scores by considering that, in the worst-case attack with M edge perturbations, Eas would be chosen compete with the true explanatory edges.
Theorem 3 (Certified Perturbation Size MA for a given X). Assume y E C and e C {y} be the class with the highest votes ny and second highest votes by Eqn (3), respectively. Assume further the edge I E EK is with the X-th highest votes nij, and edge hM Em ( Ex) with the (k + 1)-th highest votes foss in n" by Eqn (5) (hM hence depends on M). Then MA satisfies:
MA S M = min (1 (1y - nb + T(y < b) - M,), where
(7)
2
MA = max M, s.t. n7 h + T( < hM) > 2M.
(8)
Proof. See Appendix A.2
Remark: We have the following remarks from Theorem
Our voting classifier and voting explainer can tolerate M M perturbed edges.
Our voting classifier can be applied for any GNN classifier and our voting explainer for any GNN explainer that outputs edge importance score.
Our certified robustness guarantee is deterministic, i.e., it true with probability of 1.
EVALUATION
4.1
EXPERIMENTAL SETUP
Datasets: As suggested by (Agarwal al. 2023), we choose datasets with groundtruth explanations for evaluation. We adopt the synthetic dataset "SG-Motif", where each graph has a label and "Motif" the groundtruth explanation that can be "House". "Diamond", and "Wheel". We also adopt two real-world graph datasets (i.c., Benzene and FC) with groundtruth explanations from (Agarwal et al. (2023). Their dataset statistics are described in Table in Appendix C For each dataset, we randomly sample 70% graphs for training, 10% for validation, and use the remaining 20% graphs for testing.
GNN Explainer and Classifier: Recent works (Funke et al., 2022, Agarwal et al. 2023) show many GNN explainers (including the well-known GNNExplainer Ying et al. (2019)) are unstable, i..., they yield significantly different explanation results under different runs. We also validate this and show results in Table in Appendix. This makes it hard to evaluate the explanation results in consistent or predictable way. To avoid the issue. we carefully select XGNN baselines with stable explanations: PGExplainer (Luo et al. 2020), Refine (Wang et al. 2021b). and GSAT (Miao et al. 2022). We also select three well-known GNNS as the GNN classifier: GCN (Kipf & Welling 2017). GSAGE (Hamilton et al.) (017), and GIN (Xu et al., (219)). We implement these explainers and classifiers using their publicly available source code. Appendix dettais our training strategy to learn the voting explainer and voting classifier in XGNNCert.
In general, M < M3 in Def. We will leave it future work prove whether the derived M* is tight.

---

Published as a conference paper at ICLR 2025
PGExplainer
ReFine
GSAT
Datasets
T
Orig.
Orig-
Orig.
30
70
50
90
70
SG+House
0.340
0.658
0.725
0.725
0.673
0.707
0.588
0.690
0.593
0.564
0.744
0.759
0.716
0.673
0.658
SG+Diamond
0.745
0.704
0.730
0.729
0.620
0.569
0.440
0.499
0.521
0.398
0.564
0.426
0.493
0.558
0.420
WG+Wheel
0.629
0.587
0.612
0,571
0.542
0.604
0.614
0.626
0.606
0.462
0.568
0.491
0.544
0.612
0.562
Benzene
0.552
0.21
0.497
0.468
0.429
0.589
0.74
0.512
0.440
0.552
0.314
0.430
0.445
0.398
PC
0.531
0.385
0.452
0.373
0.328
0.503
0.369
0.447
0.425
0.314
0.487
0.350
0.392
0.412
0.373
Table Explanation accuracy on the original GNN explainers and our XGNNCert.
Dutusets
GCN
GIN
GSAGE
Orig.
30
50
70
90
Orig.
30
30
70
90
Org.
30
50
70
90
NG+House
0.895
0.055
0.005
0.801
0.91
0315
0300
03905
0.500
0.990
0.855
0.755
SC+Diamono
0335
0.30
0915
0.905
03885
13905
0.895
03910
0.890
Benzene
0.78
0.746
0,700
0.723
0.707
0.792
0.736
0.754
0.754
0.754
0.773
0.725
0.760
0.718
0.718
PC
0711
0.674
0.092
0092
0351
0.800
0.002
0714
0.74
0.703
0.725
0.692
00092
0.622
0.020
Table 2: Prediction accuracy on the original GNN classifiers and our XCNNCert.
Datasets
?
0.0
0.2
0.3
0.4
0.2
0.3
SHAL
SHA256
SG+House
0.053
0.695
0.725
0,710
0.715
0.725
0.720
0.725
0.718
0.710
SG++Diamond
0.045
0.620
0.729
0.720
0.712
0.729
0.718
0.729
0.729
0.721
SG+Wheel
0,012
0.511
0.571
0.508
0.550
0.571
0.564
0.571
0.363
0.562
Benzene
0.102
0.433
0,468
0.403
0.440
0.468
0.452
0.468
0.472
0.468
FC
0.096
0.353
0.373
0.288
0.345
0.373
0.385
0.373
0.382
0,390
Table 3: Explanation accuracy of our XGNNCert under different p, y, and the hash function h
Evaluation Metrics:
We adopt three metries for evaluation. 1) Classification Accuracy: fraction of testing graphs that are correctly classified, e.g., by our voting classifier; 2) Explanation Accuracy: fraction of explanatory edges outputted, e-g., by our voting explainer, are in the groundtruth across all testing graphs; 3) Certified Perturbation Size M at Certified Explanation Accuracy (or A): Given a testing graph with groundtruth (k) explanatory edges, and a predefined À (or certified explanation accuracy X/ k), our theoretical result outputs (at least) À explanatory edges on the perturbed testing graph are from the groundtruth, where the testing graph allows arbitrary M* perturbations. M vs then reports the average M* of all testing graphs for the given X.
There are several hyperparameters mentioned, we use GCN as the default GNN classifier and PGExplainer as the default GNN explainer. we use MD5 as the hash function i and we set 3, p = 0.3, T 70. 7 = 0.3 and & as Table 5 We will also study the impact of these hyperparameters on defense performance.
Parameter Setting:
our XGNNCert. Unless otherwise
4.2 EVALUATION RESULTS
We first show the explanation accuracy and classification accuracy of XGNNCert under no attack, to validate it can behave similarly to the conventional GNN classifier and GNN explainer. We then show the guaranteed robustness performance of our XGNNCert against the graph perturbation attack.
4.2.1 EXPLANATION ACCURACY AND CLASSIFICATION ACCURACY
XGNNCert maintains the explanation accuracy and classification accuracy on the original GNN explainers and GNN classifiers: Table shows the explanation accuracy of our XGNNCert and the original GNN explainers for reference. We can observe that XGNNCert can achieve close explanation accuracies (with suitable number of subgraph T) as the original GNN explainers (which have different explanation accuracies, due to their different explanation mechanisms). This shows the potential of XGNNCert as an ensemble based XGNN, We also show the classification performance of our voting classifier in XCNNCert t in Table and the original GNNs classifier for reference. Similarly, we can see our voting classifier learnt based on our training strategy can reach close classification accuracy as the original GNN classifiers.
Impact of hy perparameters in XGNNCert: Next, we will explore the impact of important hyperpa- rameters that could affect the performance of XGNNCert.
7

---

Published as a conference paper at ICLR 2025
6.0
1=20
1-20
Tx20
1-20
T:30
1:20
T-90
Tw50
T+50
13
(a) HGuee
(b)
(c) Beneze
Figure 3: Certified perturbation size over all testing graphs vs. on PGExplainer. The maximum in x-axis equals to k, the number of edges in the groundtruth explanation.
59
2.5
p-0.4
0.0
(a) SGuse
(b) SG+ Diamond
(c) Beneze
Figure 4: Certified perturbation size over all testing graphs p on PGExplainer.
5.0
7-
0.4
0.4
2.5
0.4
05
00
(a) SG+se
(b) DGaDion
(c) Beneze
Figure 5: Certified perturbation size over all testing graphs vs. 7 PGExplainer.
Impact T:: Table I shows the explanation accuracy of XGNNCert with different T. We can see the performance depends 7 and the best 7' in different datasets is different (often not the largest or smallest T). Note that the generated hybrid subgraphs use nonexistent edges from the complete small, hybrid subgraph contains more nonexistent edges, which could exceed the tolerance of the voting explainer. In contrast, too large T yields very sparse subgraphs, making the useful information in the subgraph that can used by the explainer be insufficient. This thus makes it hard to ensure explanatory edges have higher important scores than non-explanatory edges.
graph. T
Impact of p: Table shows the explanation accuracy with different p. the fraction of the subgraphs generated by the complete graph that are combined with the clean graphs' subgraphs. We have similar observation that a too small or too large p would degrade the explanation performance, with p 0.3 obtaining the best performance overall. Note that when p = 0, only the information of the original graphs, and the explanation performance is extremely bad. That means it is almost impossible obtain the groundtruth explanatory edges. This thus inspires to reasonably leverage extra information not in the original graph to guide finding the groundtruth explanatory edges.
Impact y: Table 3 also shows the explanation accuracy with different y, the fraction of the edges with the largest scores used for the voting explainer. We can observe the results are relatively stable in the range 7 [0.2, 0.4]. This is possibly due that important edges in the original graph mostly within these edges with the largest scores.
Impact of h: The explanation accuracy with different hash functions are shown in Table We see the results are insensitive to h, suggesting we can simply choose the most efficient one in practice.
4.2.2 CERTIFIED EXPLANATION ACCURACY vs. CERTIFIED PERTURBATION SIZF.
The certified robustness results are shown in Figures 3
Due to limited space, we only show results on three datasets and put results the other datasets and impact of hyperparameters in Appendix C
II
8

---

Published as a conference paper at ICLR 2025
Datasets
SG+House
SG+Diamond 0.419
SG+Wheel
Benzene
FC
V-InfoR
0.693
0,439
0.345
0.217
Exp. Acc.
XGNNCert
0.740
0.729
0.571
0.468
0,403
Difference
V-InfoR
48, 39%
73.07%
65.35%
83.82%
63.22%
Fraction
XGNNCert
7.44%
0.0%
4.20%
1.44%
1.41%
Table 4: Explanation accuracy and the fraction of different edges under attack in Li et al. (024)).
Impact of T: Figure 3 and Figures 6 in Appendix C show the (average) maximum certified perturbation size vs À with different 7. First, XGNNCert obtains reasonable certified explanation accuracy (A/k) against the worst-case graph perturbation, when the #perturbed edges is bounded by M E.g. with average 6.2 edges are arbitrarily perturbed in SG+House, XGNNCert guarantees at least À = 2 edges are from the k = 5 groundtruth explanatory edges. Second, there exists tradcoff between the clean explanation accuracy and robust explanation accuracy. Specifically, as T grows, the derived certified perturbation size increases in general. This means that larger number of generated subgraphs can enlarge the gap between the largest and second-largest votes in n On the other hand, the explanation accuracy (under no attack) can be decreased as shown in Section 4.2.
Impact of p: The results are in Figure 4 and Figure in Appendix C First, we observe the certified perturbation size 0 when p- = This means, without using information in the complete graph, is impossible to provably defend against the graph perturbation attack. Second, the certified explanation accuracies are close when p is within the range [0.2, 0.4] (which is different from the conclusions on explanation accuracy without attack). This implies, for each clean graph, we can use 20%-40% of the subgraphs generated by the complete graph for achieving stable certified explanation accuracy.
Impact of y: The results are shown in Figure 5 and Figure 10 in Appendix C Similarly, the certified results are relatively stable the range 7 = [0.2, The key reason could be that important edges in the original graph are mostly within the edges in these range.
Impact of h: The results are shown in Figure IT. Like results on explanation accuracy, we can see the hash function h almost does not affect the certified explanation accuracy, Again, this suggests we can choose the most efficient one in practice.
4.2.3 DEFENSE EFFECTIVENES, AGAINST ADVERSARIAL. ATTACK ON XGNN
We further test XGNNCert in the default setting against the recent adversarial attack on XGNN Li et al. 2024), and compare with the state-of-the-art empirical defense V-InfoR (Wang al. 2023c). We evaluate their effectiveness by allowing the attacker to change two non-explanatory edges in the graph and taking the fraction of different explanatory edges (before and after the attack) as the metric. The test results are shown in Table 4. We can observe that: Our XCNNCert not only achieves the theoretical defense performance and higher explamation accuracy, but also shows much better empirical defense performance than V-InfoR under the powerful attack. This is possibly due to our subgraph division and voting scheme design, which is "inherently" robust to the strongest attack it dilutes the adversarial perturbation effect into subgraphs, and at the same time, the number of subgraphs that are affected can be bounded. In contrast, V-InfoR is an empirical defense that constrains the attack capability and is unable to defend against the strong attack.
4.2.4 COMPLEXITY ANALYSIS OF XGNNCERT
Our XGNNCert divides each hybrid graph into T subgraphs and applies a base GNN explainer to explain each subgraph. The final explanation is obtained via voting the explanation results of the T subgraphs. whose computational complexity is negligible. Hence, the dominant computational complexity of XGNNCert t is T times of the base GNN explainer's s. For instance, PGExplainer has a complexity of V + [.), where S is the number of optimization steps, and [V] and |E| are the number of nodes and edges, respectively. Therefore, XGNNCert with PGExplainer as the base explainer has complexity V + EE). Note that the explanation on T subgraphs can be run in parallel, as they are independent of each other. Furthermore, each hybrid subgraph needs to store p ? more edges from the complete graph, where an edge is represented as pair of node indexes in the implementation. Hence, the extra memory cost per graph is V(PT)V(3) We highlight that the extra computation and memory cost is to ensure the robustness guarantee. In other words, our XGNNCert rt. obtains robustness-efficienny tradeoff
9

---

Published as a conference paper at ICLR 2025
5 RELATED WORK
Explainable GNNs: XNNGs can be classified into decompesition-busel gradient-based, surrogate- based, generation-bused perturbation -baeed, and causality-baxee methods. Decomposition-buse methods (Schnake et al.] 2021 Feng et al. (022) treat the GNN prediction as a score and decompose it backward seee-bb-layer until reaching the input. The score of different parts of the input indicates the importance to the prediction. Gradient-base -based methods (Baldassarre & Azizpour 2019 Pope et al. (2019) take the gradient (implies sensitivity) of the prediction wrt. the input graph, and the sensitivity is used to explain the graph for that prediction. Surrogate-baset methods (Vu & Thai 2020
Pereira 2023) replace the complex GNN model with simple and interpretable surrogate model.
Generation-base methods (Lin et al. 202T; Sui et al., 2022 Shan et al., 2021 Wang et al. 2023d)
use generative models to generate explanations. E.g. RCExplainer (Wang et al.) (023d) applies reinforcement learning to generate subgraphs as explanations. Perturbation bassodd methods Ying
ct al. 2019; Luo et al., 2020; Wang et al. 2021b, et al., 2022) uncover the important subgraph as explanations by perturbing the input graph. Causality-basse methods (Behnam & Wang 2024)
explicitly build the structural causal model for a graph, based on the common assumption that a graph often consists of a underlying causal subgraph. It then adopts the trainable neural causal model (Xia 202T to learn the cause-effect among nodes for causal explanation.
ct al.
Adversarial attacks on GNN classifiers and explainers: Almost all existing method focus on attacking GNN classifiers They are classified as test-time attacks (Dai et al., 2018 Zügner et al.
2018 Ma et al. 2020; Mu et al.) |021 Wang et al.] 2022a 2023a
2024) and training time attacks
(Xu et al. 2019 Zügner & Günnemann 2019 Wang & Gong. 2019 Zhang et al. b0 Wang et al.
2023a). Test-time attacks carefully perturb test graphs so that many them misclassified by pretrained GNN classifier, while training- waining-time attacks carefully perturb training graphs during training, such that the learnt GNN classifier mispredicts as many test graphs as possible. (Li et al. 2024) is the only method on attacking GNN explainers. It is a black-box attack (i.e., attacker has no knowledge about XGNN) that aims to corrupt GNN explanations while preserving GNN predictions.
Certified defenses for GNN classifiers with probabilistic guarantees: Existing certified de- fenses (Bojchevski et al. 2020 Wang et al., 2021a Zhang et al. 202Tb) are for GNN classifiers-they guarantee the same predicted label for testing graph with arbitrary graph perturbation. For instance, Wang et al. (2021a) generalized randomized smoothing (Lecuyer et al.] 2019, Cohen et al. 2019 Hong et al. 2022) from the continuous domain to the discrete graph domain. Zhang et al. (202 lb) extended randomized ablation (Levine & Feizi 2020c) to build provably robust graph classifiers
2019,,Cohen
However, these defenses only provide probabilistic guarantees and cannot be applied to XGNNs.
Majority voting-based certified defenses with deterministic guarantees: This strategy has been widely used for classification models against adversarial tabular data (Hammoudeh & Lowd 2023). adversarial 3D points (Zhang et al., 2023), advensarial patches (Levine & Feizi [020b)] Xiang et al.
2021), adversarial graphs (Xia et al. 2024 Yang al. 2024 L & Wang 2025), and data poisoning attacks (Levine& & Feizi, [020a]] Jia et al. 2021] Wang et al. 2022b Jia et al. 2022). Their key
differences are creating problem-specifie voters for majority voting. However, these defenses cannot be applied to robustify GNN explainers, which are drastically different from classification models.
Certified defenses of explainable non-graph models. A few works (Levine al. 2019 Liu et al.
2022 Tan & Tian 2023) propose to provably robustify explainable non-graph (image) models against adversarial perturbations. These methods mainly leverage the idea of randomized smoothing (Lecuyer
et al. 2019 Cohen et al. 2019) and only provide probabilistic certificates.
6 CONCLUSION
We propose the first provably robust XGNN (XGNNCert) against graph perturbation attacks. XGNNCert first generates multiple hybrid subgraphs for given graph (via hash mapping) such that only bounded number of these subgraphs can be affected when the graph is adversarially perturbed. We then build a robust voting classifier and a robust voting explainer to aggregate the prediction and explanation results on the hybrid subgraphs. Finally, we can derive the robustness guarantee based on the built voting classifier and voting explainer against worst-case graph perturbation attacks with bounded perturbations. Experimental results multiple datasets and GNN classiferrseexllanerrs validate the effectiveness of our XGNNCert. In future work, we will enhance the certified robustness with better subgraph generation strategies and design node permutation invariant certified defenses.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
We thank the anonymous reviewers for their insightful reviews. This work was partially supported by the Cisco Research Award and the National Science Foundation under grant Nos. ECCS-2216926, CCF-2331302, CNS-2241711 and CNS-2339686.
REFERENCES
Chirag Agarwal, Owen Queen, Himabindu Lakkaraju, and Marinka Zitnik. Evaluating explainability for graph neural networks. Scientific Data, 10(1):144, 2023.
Mohit Bajaj, Lingyang Chu, Zi Yu Xue, Jian Pei, Lanjun Wang. Peter Cho-Ho Lam, and Yong Zhang. Robust counterfactual explanations graph neural networks. 34:5644-5655, 2021.
Federico Baldassarre and Hossein Azizpour. Explainability techniques for graph convolutional networks. JCML Workshop, 2019.
Arman Behnam and Binghui Wang. Graph neural network causal explanation via neural causal models. In ECCV, 2024.
Aleksandar Bojchevski, Johannes Gasteiger, and Stephan Günnemann. Efficient robustness certificates for discrete data: Sparsity-aware randomized smoothing for graphs, images and more. In ICMI., 2020.
Nicholas Carlini, Anish Athalye, Nicolas Papernot, Wieland Brendel, Jonas Rauber, Dimitris Tsipras, lan Goodfellow, Aleksander Madry, and Alexey Kurakin. On evaluating adversarial robustness. arXiv, 2019.
Jeremy M Cohen, Elan Rosenfeld, and J Zico Kolter. Certified adversarial robustness via randomized smoothing. arXiv preprint a902: 02918, 2019.
Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, and Le Song. Adversarial attack on graph structured data. In ICML, 2018.
Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with leamable structural and positional representations. In ICI.R, 2022.
Qizhang Feng, Ninghao Liu, Fan Yang. Ruixiang Tang, Mengnan Du and Xia Hu. Degree: Decom- position based explanation for graph neural networks. In ICLR, 2022.
Thorben Funke, Megha Khosla, Mandeep Rathee, and Avishek Anand. Zorro: Valid, sparse, and stable explanations in graph neural networks. IEEE TKDE, 2022.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NIPS, 2017.
Zayd Hammoudeh and Daniel Lowd. Feature partition aggregation: fast certified defense against union of 1_0 attacks. In The Second Workshop New Frontiers in Adversarial ML, 2023.
Hanbin Hong, Binghui Wang, and Yuan Hong. Unicr: Universally approximated certified robustness via randomized smoothing. In ECCV, 2022.
Zhongyu Huang, Yingheng Wang, Chaozhuo Li, and Huiguang He. Going deeper into permutation- sensitive graph neural networks. In ICML, pp. 9377-9409, PMLR, 2022.
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. In Proceedings of the AAAI Conference 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 on Artificial Intelligence, 2022.
11

---

Published as a conference paper at ICLR 2025
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 NeurlPS, 2020.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létournaa,, and Prudencio Tossou. Rethinking graph transformers with spectral attention. In NeurlPS, 2021.
Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. In 2019 IEEE Symposium on Security and Privacy (SP), pp. 656-672. IEEE, 2019.
Alexander Levine and Soheil Feizi. Deep partition aggregation: Provable defenses against general poisoning attacks. In ICLR, 2020a.
Alexander Levine and Soheil Feizi. (de) randomized smoothing for certifiable defense against patch attacks. In NeurlPS, 2020b.
Alexander Levine and Soheil Feizi. Robustness certificates for sparse adversarial attacks by random- ized ablation. In AAAI, 2020c.
Alexander Levine, Sahil Singla, and Soheil Feizi. Certifiably robust interpretation in deep learning. arXiv preprint arXiv: /905. 1ttp:/9055.22.. /2/05, 2019.
Jiate Li and Binghui Wang. Agnncert: Defending graph neural networks against arbitrary perturba- tions with deterministic certification. USENIX Security, 2025.
Jiate Li, Meng Pang, Yun Dong, Jinyuan Jia, and Binghui Wang. Graph neural network explanations are fragile. In ICML, 2024.
Wanyu Lin, Hao Lan, and Baochun Li. Generative causal explanations for graph neural networks. In ICML, 2021.
Ao Liu, Xiaoyu Chen, Sijia Liu, Lirong Xia, and Chuang Gan. Certifiably robust interpretation via rényi differential privacy. Artificial Intelligence, 313:103787, 2022.
Andreas Loukas. What graph neural networks cannot learn: depth vs width. In ICLR, 2020.
Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong. Haifeng Chen, and Xiang Zhang. Parameterized explainer for graph neural network. In NeurIPS, 2020.
Jiaqi Ma, Shuangrui Ding, and Qiaozhu Mei. Towards more practical adversarial attacks graph neural networks. In NeurlPS, 2020.
Siqi Miao, Miaoyuan Liu, and Pan Li. Interpretable and generalizable graph learning via stochastic attention mechanism. In ICML, 2022.
Jiaming Mu, Binghui Wang, Qi Li, Kun Sun, Mingwei Xu, and Zhuotao Liu. hard label black-box adversarial attack against graph neural networks. In CCS, 2021.
Felix Mujkanovic, Simon Geisler, Stephan Günnemann, and Aleksandar Bojchevski. Are defenses for graph neural networks robust? 35:8954-8966 2022.
Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro, Relational pooling for graph representations. In ICML, 2019.
Pál András Papp. Karolis Martinkus, Lukas Faber, and Roger Wattenhofer. Dropgnn: Random dropouts increase the expressiveness of graph neural networks. In NeurlPS, 2021.
Tamara Pereira, Erik Nascimento, Lucas E Resck, Diego Mesquita, and Amauri Souza. Distill n' n'cxplain: explaining graph neural networks using simple surrogates. In AISTATS, 2023.
Bastian Pfeifer, Anna Saranti, and Andreas Holzinger. Gnn-subnet: disease subnetwork detection with explainable graph neural networks. Bioinformatics, 38, 2022.
12

---

Published as a conference paper at ICLR 2025
Phillip E Pope, Soheil Kolouri, Mohammad Rostami, Charles E Martin, and Heiko Hoffmann.
Explainability methods for graph convolutional neural networks. In CVPR, 2019.
Bhavtosh Rath, Xavier Morales, and Jaideep Srivastava. Scarlet: explainable attention based graph neural network for fake news spreader prediction. In PAKDD, 2021.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. In ICLR, 2020.
Thomas Schnake, Oliver Eberle, Jonas Lederer, Shinichi Nakajima, Kristof T Schüitt, Klaus- Müller, and Grégoire Montavon. Higher-order explanations of graph neural networks via relevant walks. IEEE TPAMI, 2021.
Caihua Shan, Yifei Shen, Yao Zhang, Xiang Li, and Dongsheng Li. Reinforcement learning enhanced explainer for graph neural networks. In NeurIPS 2021, December 2021.
Yongduo Sui, Xiang Wang, Jiancan Wu, Min Lin, Xiangnan He, and Tat-Seng Chua. Causal attention for interpretable and generalizable graph classification. In KDD, 2022.
Zeren Tan and Yang Tian. Robust explanation for free the cost of faithfulness. In ICML, 2023.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
Minh Vu and My Thai. Pgm-explainer: Probabilistic graphical model explanations for graph neural networks. In NeurIPS, 2020.
Binghui Wang and Neil Zhenqiang Gong. Attacking graph-based classification via manipulating the graph structure. In CCS, 2019.
Binghui Wang, Jinyuan Jia, Xiaoyu Cao, and Neil Zhenqiang Gong. Certified robustness of graph neural networks against adversarial structural perturbation. In KDD, 2021a.
Binghui Wang, Youqi Li, and Pan Zhou, Bandits for structure perturbation basedd black-box attacks to graph neural networks with theoretical guarantees. In CVPR, 2022a.
Binghui Wang, Meng Pang, and Yun Dong. Turning strengths into weaknesses: A certified robustness inspired attack framework against graph neural networks. In CVPR, 2023a.
Binghui Wang. Minhua Lin, Tianxiang Zhou, Pan Zhou, Ang Li, Meng Pang, Hai Li, and Yiran Chen. Efficient, direct, and restricted black-box graph evasion attacks to any-layer graph neural networks via influence function. In WSDM, 2024.
Qianwen Wang, Kexin Huang, Payal Chandak, Marinka Zitnik, and Nils Gehlenborg. Extending the nested model for user-centric xai: A design study gnn-based drug repurposing. IEEE TVCG, 2023b.
Senzhang Wang, Jun Yin, Chaozhuo Li, Xing Xie, and Jianxin Wang, V-infor: A robust graph neural networks explainer for structurally corrupted graphs. In NeurIPS, 2023c.
Wenxiao Wang, Alexander Levine, and Soheil Feizi. Improved certified defenses against data poisoning with (deterministic) finite aggregation. In ICML, pp. 22769 22783. PMLR, 2022b.
Xiang Wang, Yingxin Wu, An Zhang, Xiangnan He, and Tat-Seng Chua. Towards multi-grained explainability for graph neural networks. In NeurIPS, volume 34, pp. 18446-18455 2021b.
Xiang Wang, Yingxin Wu, An Zhang, Fuli Feng, Xiangnan He, and Tat-Seng Chua. Reinforced causal explainer for graph neural networks. IEEE TPAMI, pp. 2297-2309, 2023d.
Xiaogi Wang and Han Wei Shen. GNNInterpreter: A probabilistic generative model-level explanation for graph neural networks. In ICLR, 2023.
Felix WU, Tianyi Zhang, Amauri Holanda de Souza Jr, Christopher Fifty. Tao Yu, and Kilian Q Weinberger. Simplifying graph convolutional networks. In ICML, 2019.
13

---

Published as a conference paper at ICLR 2025
Zhenxing Wu, Jike Wang, Hongyan Du, Dejun Jiang, Yu Kang, Dan Li, Peichen Pan, Yafeng Deng, Dongsheng Cao, Chang- Yu Hsich, et al. Chemistry-intuittyy explanation of graph neural networks for molecular property prediction with substructure masking, Nature Communications, 14(1):2585, 2023.
Kevin Xia, Kai-Zhan Lee, Yoshua Bengio, and Elias Bareinboim. The causal-neural connection: Expressiveness, Icarnability, and inference. In NeurIPS, 2021.
Zaishuo Xia, Han Yang, Binghui Wang, and Jinyuan Jia. Gnncert: Deterministic certification of graph neural networks against adversarial perturbations. In ICLR, 2024.
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 USENIX Security, 2021.
Kaidi Xu, Hongge Chen, Sijia Liu, Pin- Yu Chen, Wei Weng, Mingyi Hong, and Xue Lin. Topology attack and defense for graph neural networks: An optimization perspective. In IJCAI, 2019.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? ICLR, 2019.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? In ICLR, 2019, URL httppp:://peeeeevvee
Yuxin Yang, Qiang Li, Jinyuan Jia, Yuan Hong. and Binghui Wang. Distributed backdoor attacks on federated graph learning and certified defenses. In CCS, 2024.
Ziduo Yang, Weihe Zhong. Lu Zhao, and Calvin Yu-Chian Chen. Mgraphdta: deep multiscale graph neural network for explainable drug-targe binding affinity prediction. Chemical science, 13(3): 816-833, 2022.
Zhitao Ying. Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. GNNExplainer: Generating explanations for graph neural networks. In NeurIPS. 2019.
Hao Yuan, Haiyang Yu, Jie Wang, Kang Li, and Shuiwang Ji. On explainability of graph neural networks via subgraph explorations. In ICML, 2021.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- saint: Graph sampling based inductive learning method. In ICLR, 2020.
Jinghuai Zhang, Jinyuan Jia, Hongbin Liu, and Neil Zhenqiang Gong. Pointcert: Point cloud classification with deterministic certified robustness guarantees. In CVPR, 2023.
Shichang Zhang, Yozen Liu, Neil Shah, and Yizhou Sun. Gstarx: Explaining graph neural networks with structure-aware cooperative games. In NeurlPS, volume 35, pp. 19810-19823, 2022.
Zaixi Zhang, Jinyuan Jia, Binghui Wang, and Neil Zhenqiang Gong. Backdoor attacks to graph neural networks. 2021a.
Zaixi Zhang, Jinyuan Jia, Binghui Wang, and Neil Zhenqiang Gong. Backdoor attacks graph neural networks. In SACMAT, 2021b.
Wenhao Zhu, Tianyu Wen, Guojie Song, Xiaojun Ma, and Liang Wang. Hierarchical transformer for scalable graph learning. In IJCAI, 2023.
Daniel Zügner and Stephan Günnemann. Adversarial attacks on graph neural networks via meta learning. In ICLR, 2019.
Daniel Zügner, Amir Akbarnejad, and Stephan Günnemann. Adversarial attacks on neural networks for graph data, In SIGKDD, pp. 2847-2856, 2018.
14

---

Published as a conference paper at ICLR 2025
A PROOFS
A.1 PROOF OF THRORFM 2
When edge is added to deleted from G. only the subgraph G (V, E,,) ) is corrupted after hash mapping, and all the other subgraphs { liti, are unaffected. Note that the complete graph Ge is fixed and all subgraphs built from it are never affected. Then, with Equation 2 only the hybrid subgraph Cj would be corrupted. Further, when M edges from G are perturbed form G, only hybrid subgraphs containing these edges would be corrupted. As some edges may be mapped to the same group index, the different subgraphs between {G } and {G is at most M.
A.2 PROOF OF THFOREM
3
After the graph perturbation, we want to satisfy two requirements: (1) the voting classifier still predicts the class y in the perturbed graph G with more votes than predicting any other class bb E C {y}: (2) the voting explainer ensures at least À edges in Eg are still in Ég, or at most (A: - A) edges in & \ Ek have higher votes than the minimum votes of the edges in &t.
We first achieve (1): Based on Theorem 2 with any M perturbations on a graph G, at most M hybrid subgraphs from {G²z] } can be corrupted. Hence, it decreases the largest votes ny most M, while increasing the second-largest votes Yı, at most M based on Eqn (3). Let fgy and Åi denote the votes of predicting the label y and b on the perturbed graph G. We have fy 2 By M and hg S ny + M. To ensure the voting classifier f still predicts y for the perturbed graph G. we require ny > fus 1-I(p I(y < b) or fty 2 âg - I[y < 6) +)+11 where I(y < b) is due to the tie breaking mechanism (i.e.. we choose label with a smaller number when ties exist). Combining these inequalities, we require my M 2 ny + M T(y < b) + yielding
Fy ne + I(y b) -
M <
2
We now achieve (2): Recall Em the edges in E with M scores in n², which & are edges in the complement of graph G. Similarly, with M perturbed edges, the votes of every explanatory edge E & is decreased at most M, while the votes of every other edge E &c Ex is increased at most based on Eqn (5). Note that the edge E & has the X-th highest votes n, and the edge hMs E EM (E \ Ex) has the (k - A + 1) highest votes n Let nï and n7 denote the votes of the edge and has G for each M. Likewise, we have n n2 M and f S & + M for every hM (note hM depends on M). If the smallest votes 67 of edge I after the perturbation still larger than the largest votes f7 of the edge hMs then at least À edges in & are still in &. This requires: n. > f7, 1(1 < has)) for all hM. where I[I < hu) is due to the tie breaking. Combining these inequalities together, we require n/ M > n + M - I( < hM), VM, yielding
n? -nnar I([ hM) 2M
(10)
By satisfying both requirements, we force
M S min (1 my n4 T(y < b) - .M)),
where M, = max M, s.t. n7 nhar + T(1 < hM)) > 2M.
B PSEUDO CODE ON XGNNCERT
Here provide the pseudo code of our XGNNCert, shown in Algorithm
C EXPERIMENTAL SETUP AND MORE RESULTS
C.I DETAILED EXPERIMENTAL SETUP
Dataset statistics: Table 5 shows the statistics of the used datasets.
15

---

Published as a conference paper at ICLR 2025
Algorithm 1 XGNNCert: Classification, Explanation, and Certified Perturbation Size
Input: Graph (V.&) with explanation edges, base classifier f. base explainer g, hyperparameters: ratio p. ratio y, number subgraphs T, hash function h.
Output: Prediction y, explanation &k, certified perturbation size {Mx, À E [1, } for G
I:
Initialize 7' subgraphs with empty edges {G' = (V,E* = 0), 1 1, ,
Initialize complete subgraphs with empty edges (Gc = (V. = 0). 1, T).
3: Initialize T' hybrid subgraphs with empty edges {G², (V, =, T).
4: Initialize complete edge &c [[u, v). Vu, V <<
5: Initialize votes for all classes {0)le and all edges: n (0) (0]l
6: for Edge &c do Assign index hi(st((u) str(v)] mod +
8: e then
9:
Add into subgraph G by E = {e}
10: end if
11: Add into complete subgraph C by E {e}
12: end for
13: for i E [1. do
14: Add the i-th subgraph G into i-th hybrid subgraph by EjUU E
for E [1, U 1,
16: Randomlize value E 1)
17: if S then
18:
Add the j-th complete subgraph into i-th hybrid subgraph by E E6
19: end if
20: end for
21: end for
22: for Go, [] do
23: Predict G 's label via the base classifier: c= = f(G))
24: Add to the classification vote by I: m =
25: end for
26: Find the class with the most votes: y arg 7Ac CEC
27:
Find class with the second most votes: b arg max The CEC\(V)
28: Calculate the certified bound w.r.t. the classifier: M2 By (()
29: for Ge, i
[1, do
30:
Explain G 's output the base explainer: m' gG' y)
31:
for E G do
32:
if m mi.)) then
33:
n
34: end if
35: end for
36: end for
37: Find the edges with top-k votes in G: E E.tops (n²)
38: Initialize M 0, (M* = 0, 1,... [.]
39: while = do
40: M+=1
41: Find edges with top-M votes Eg \ E: EM = (Eo (o))))pr(n"))
42: for A E [1, kj do
43:
Find the edge 1 E & is with the A-th highest votes v2,". Find the edge E Ex (E Ec) with the (k: 1)-th highest votes nī in n"
44:
45:
if n² - n I(I < h) 2M then
46:
MA M
end if 48: end for
47:
49: end while
50: X E Ai)
51: M, = min( MA, My)
52: end for
53: Return EK (Mr, E [1,
Hy Hyperparameter and network architecture details in training GNN classifiers and explainers:
We have tested the base GNN classifiers with 2 and 3 layers, the hidden neurons (32, 64, 128, 192).
16

---

Published as a conference paper at ICLR 2025
Dataset
Graphs
[V/ex
[Elay
Features
GT Graphs
GT Explanation
Barlau
SG+House
1,000
13.69
15.56
10
693
House Shape
6
SG+Diamond
1,000
10.46
14.03
10
486
Diamond Shupe
5
5
SG-Wheel
1,000
12.76
Wheel Shape
Benzeme
12,000
20.58
43.65
14
6,001
Bensene Ring
6
Flnoride: Flueride-Carbmnyy (FC)
8,6716
21.36
45.37
14
3,254
and C=O
Table 5: Datasets and their statistics.
Ratio p
SG+House
SG+Diamond
SG+ Wheel
Benzene
FC
0.0
0,900
0,925
0,905
0.723
0.674
0,02
0.895
0,920
0,900
0.723
0.692
0.03
0.905
0.935
0,900
0.723
0.692
0.04
0.895
0.925
0.900
0.725
0.662
Table 6: Prediction accuracy of XGNNCert with different (default 0.3).
Hash function
SG+House SG+Diamond
SG+Wheel
Benzene
FC
MD5
0.905
0.935
0.900
0.723
0.692
SHA1
0.905
0.935
0.895
0.718
0.692
SHA256
0.900
0.935
0.905
0.725
0.674
Table 7: Prediction accuracy of XGNNCert with different hash functions. Default is "MDS".
learning rates {0.001, 0.002, 0.005, 0.01) and training epochs (600, 800, 1000, 1200} with the Adam optimizer (no weight decay in the training). Finally, base GNN classifiers all 3-layer architectures with 128 hidden neurons, the learning rate as 0.001, and the epochs as 1000.
For base GNN explainers, simply use the configured hyperparameters in their source code. We set their hidden sizes as 64, coefficient sizes as 0.0001, coefficient entropy weights as 0.001, learning and last temperature as 2. For GSAT, we set its final rate as 0.7, decay interval as 10 and decay rate as 0.1. For Refine, we set its gamma parameter as beta parameter
rates 0.01, and epochs 20. For PG Explainer,
set its first temperature
and tau parameter as 0.1.
Training the GNN classifier and GNN explainer: Traditionally, we only use the training graphs (with their labels) train GNN classifier, which used to predict the testing graphs. XGNNCer however, the voting classifier uses the hybrid subgraphs (the combination of subgraphs from the testing graphs and from the corresponding complete graphs) for evaluation. To enhance the testing performance of our voting classifier, we propose to train the GNN classifier using not only the original training graphs but also the hybrid subgraphs, whose labels are same as the training graphs $
Instead, the GNN explainer is directly trained on raw clean graphs due to two reasons. First, the cost of training the explainer on subgraphs high; Second, some subgraphs do not contain groundtruth explanatory edges, making it unable to explain these subgraphs during training.
C.2
MORE RESULTS
Figure
Figure show the certified perturbation size vs. on the three GNN explainers.
Figure Figure show the certified perturbation size of XGNNCert p, 7, h on PGExplainer,
respectively, Additionally, Table and Table 7 show the prediction accuracy of XGNNCert vs. p and h, respectively. We the results are close, implying XGNNCert is insensitive p and h.
Figure 12 shows the explanation results when the GNN model deceived. We see that explaining wrong predictions yields explanation results that not meaningful.
'We observe the wrong prediction rate on our test hybrid subgraphs is relatively high, if we use the GNN classifier trained only on the raw training graphs. For instance, when 7' = 30, the wrong prediction rate could be range from 35% to 65% on the five datasets. This is because the training graphs used to train the GNN classifier and test hyhrid subgraphs have drastically different distributions.
17

---

Published as a conference paper at ICLR 2025
7.5
1-30
1e30
T-30
1-50
4.5
T:20
T+90
8
1-10
Te50
14
(a) SG+Wheel
(b) FC
Figure 6: Certified perturbation size over all testing graphs vs. À on PGExplainer.
7.5
1-50
300
1.5
(a) +
(b) DGamondd
(c) SG+ Wheel
T:30
Tw330
3.0
T-50 22
25
Tw70
$ 2.0
0.
(d) Beneze
(e) FC
Figure 7: Certified perturbation size all testing graphs À on ReFine.
10
75
T-20
T-30
T-50
T-50
Tw70
Tw70
45
70
T-50
7-90
30
15
(a) HGuse
(b) SG+Diamont
(c) SG+ Wheel
4.
35
To330
T-50
T-50
T-70
Tw70
$
1-90
T-90
15
10
(d) Beneze
(e) FC
Figure Maximal certified perturbation size over testing graphs vs. on GSAT.
D DISCUSSION
Instability of GNN explainers: We conduct experiments on the well-known GNNExplainer (Ying et al. 2019) to show its unstable explanation results. Particularly, we run it 5 times and show the explanation results Table g where "Std" is the Standard Deviation the explanation accuracy on test data across the 5 runs. and "Change Rate" is the average fraction of different explanation edges among every pair of the 5 runs. We can see both the variance and change rate are large, meaning is unreliable and difficult to pick any of the result to design the robust explainer.
18

---

Published as a conference paper at ICLR 2025
7.5
p-0
p-0
p-0.
p-02
4.5
D-0.4
p:03
87
p:03
p-0.4
14
(a) WG+Wheel
(b) FC
Figure Certified perturbation size over all testing graphs vs. p on PGExplainer.
6.
y-
0.4
8
3.0
0.
(a) SG+Wheel
(b) FC
Figure 10: Certified perturbation size over all testing graphs vs. y on PGExplainer.
NDS
huMDS
h=SHAL
NiSHAA
6.0
h-SHAI
I=-SHA256
(I-5MA256
4.5
11-1hA256
3.0
1.5
00
(a) Souse
(b)
(c) SG+ Wheel
4.0
h-M1S5
$
13
10
(d) Beneze
(e) FC
Figure 11: Certified perturbation size over all testing graphs vs. on PGExplainer.
Dataset
SG+House
SG+Diamond
SG+Wheel
Benzene
FC
Exp. Accuracy
0.624
0.368
0.475
0.276
0.226
Std
9.3%
9.7%
8.1%
10.9%
12.4%
Change Rate
36.8%
64.0%
51.6%
72.6%
76.9%
Table 8: Instability of GNNExplainer
Dataset
Pred. Acc. (Avg)
Pred. Acc. (Std)
Exp. Acc. (Avg)
Exp. Acc. (Std)
Benzene
0.722
0.002
0.466
0.007
FC
0.682
0,012
0.358
0.037
Table Averaged prediction and explanation accuracy of XGNNCert on the two real-world datasets with 5 random node orderings.
Node-order invariant variant GNNs: There exist both node-order invariant GNNs (whose outputs are insensitive to the node ordering) and node-order variant GNNs (whose outputs depend on the node ordering). Node-order invariant GNNs typically use, e.g., the mean and convolution
19

---

Published as a conference paper at ICLR 2025
House
Diamond
Wheel Ground-
Benzene
FC
House
Diamond
Wheel
Benzene
FC
Original Explanation
House
Diamond
Wheel
Benzene FC
GNN Deceived Explanation
Figure 12: Examples of how an explanatory subgraph outputted by PGExplainer changes when GNN deceived. Top Row: Groundtruth Explanation; Middle Row: Explanation under correct predictions; Bottom Row: Explanation when GNN is deceived by graph perturbation (2 edges are perturbed).
aggregator such as GCN (Kipf & Welling 2017), SGC (Wu et al. 2019), GIN (Xu et al. 2019).
GAT (Veličković et al., 2018), GSAGE-mean (Hamilton al. (017)) )). Node-order variant GNNs
Zeng al. 2020), LSTM aggregator (Hamilton et al. (217). relational pooling (Murphy et al. 2019 positional
based on, c.g., random neighbor sampling (Papp et al. 2021 Rong et al., 2020
embedding (Dwivedi al. 2022 Kreuzer al. 2021 Zhu al. 2023).
While node-order invariant GNNs are desirable certain cases, recent works (Loukas) 2020 Papp al. 2021 Huang al. 2022) show node-order variant GNNs can produce better expressivity. This ranges from the classic GSAGE with LSTM to modern graph transformers (Kreuzer et al. 2021 Zhu
al. 2023) Our GNN voting classifier node-order variant due the property of hash function.
To further explore the impact of node permutations on XCNNCert, we randomly permute the input graphs 5 times and report XGNNCert's 's average prediction and explanation accuracies on the two real-world datasets under the default setting in Table 9 We observe that XGNNCert exhibits stable prediction and explanation accuracies across the runs. This demonstrates that, though XGNNCert is not inherently permutation invariant, its classification and explanation performance remain relatively stable node permutations. We hypothesize that one possible reason for this stability is that XGNNCert augments the training graphs with set of subgraphs to train the GNN classifier. This augmentation may mitigate the effect of node ordering, as the subgraphs are much smaller size.
Can this framework be extended to node-level or edge-level tasks? Theoretically, it is possible, needs technique adaptation. For example, the node-level task, we are given a target node and its prediction by a GNN model, then GNN explainers aim to find the subgraph (usually from the target node's 's neighboring graph) that is most important for the target node's s prediction. When applying the proposed framework for certifying node-level explainers, it becomes designing graph division and voting strategy such that: with an arbitrary graph perturbation under a perturbation budget, 1) the voting classifier guarantees the correct prediction for the target node on the perturbed graph, and 2) the voting explainer guarantees the explanation results on the perturbed graph and clean graph are close. The current graph division strategy
applicable as all subgraphs have disjoint nodes, while the target node should be contained in all subgraphs for the node-level task. Hence, a key challenge is how adapt the graph division and voting strategy satisfy 1) and 2). particularly guaranteeing only a bounded number of subgraphs is affected when predicting the target node, while the explanations of these subgraphs' predictions are also retained. We acknowledge it is interesting future work to extend the proposed framework specially for node/edge-level explanation tasks.
20


Reviews:
[{"review_id": "2eSw1wQ4Ip", "reviewer": "Reviewer_d9Hd", "summary": "This paper proposes a novel certified defense framework for GNN explanations, named XGNNCert. In particular, XGNNCert generates hybrid subgraphs using subgraphs of the target graph and subgraphs of the complete graph. Based on the hybrid subgraphs, XGNNCert adopts majority voting based GNN classifier and explainer as the backbone. The authors derive a theoretical guarantee on the certified robustness of GNN classifier and explainer and provide the formula to compute the perturbation budget. Experimental evaluations on various datasets demonstrate that XGNNCert maintains the explanation accuracy and guarantees the preservation of critical explanatory edges under adversarial perturbations.", "questions": "Please see Weaknesses", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Recent works reveal that GNN explanation is vulnerable to adversarial attacks. This paper is the first to propose a certified defense framework against the attacks.\n- The certification has a deterministic guarantee, which makes XGNNCert reliable in real-world scenarios.\n- The experimental results show that XGNNCert achieves desirable certification compared with other empirical defense methods.\n- The paper is well-organized and the writing is easy to follow.", "weaknesses": "- The certification relies on the majority voting mechanism. These can lead to the global information of the target graph being corrupted. For example, in experimental results (Table 1 and Table 2), the performance of XGNNCert in FC dataset decreases consistently compared with the original GNN.\n- In hybrid subgraph generation, how to ensure that the size of $\\{\\mathcal{E}^i\\}$ is uniform? If sizes of subgraphs differ distinctly from each other, it would be better to determine the parameter $p$ more carefully, such as being dependent on each subgraph.\n- XGNNCert requires to generate subgraphs of the complete graph. It can be difficult to scale due to the extra memory cost. This part seems not to be included in the complexity analysis.\n- XGNNCert poses challenges on hyperparameter tuning in real-world implementation. The performance can be sensitive to some hyperparameters such as $T$, $p$, and $\\gamma$, while all of them should locate in a specific range.", "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": "3oabBYk8Jk", "reviewer": "Reviewer_DXMv", "summary": "The paper introduces a new architecture for explainable graph learning that allows to additionally derive a certificate regarding the set of explanations (edges) w.r.t. edge perturbations. This is achieved by splitting the graphs into subgraphs and derive an ensemble-based explainer. In particular, the well-known robustness certification strategy for majority voting classifiers is extended to the set case. The effectiveness of the method is demonstrated on several graph classification datasets.", "questions": "1. How do the hyperparameters $p$ and $h$ effect prediction accuracy? I really like Tables 1 & 2 and think having a similar investigation for $p$ and $h$ in the Appendix would be interesting.\n2. Is certification possible if an edge in the ground truth explanation set is perturbed? In particular, I'm not very convinced of the stealthiness argument in line 102, as a defender would not have access to the ground truth graph, but only the perturbed version (and of course, does not have access to the ground truth explanatory edges, as this would make the method otherwise obsolete). My thinking would be yes, as from a defender perspective the $\\mathcal{E}_k$ are already derived from the perturbed graph and the $\\lambda$ guarantee holding for any graph reachable through $M^*$ edge changes.\n3. Where does the -1 in the robustness guarantee come from? Shouldn't from the proof $M \\le \\lfloor \\frac{n_y-n_b+\\mathbb{I}(y<b)}{2}\\rfloor$ suffice? What am I missing?\n4. Regarding the experiments performed in Table 6, what is the instability of XGNNCert under the same experimental setup?\n5. In the related work, can the authors include one or two sentences about certification of explainable AI in a non-graph context? This would be interesting to the reader, as one could ask the question of what approaches are already out there and if these are directly applicable to the graph domain. \n\nMinor\n* Figure 1: \"Origianl Prediction\" -> \"Original Prediction\" (2x)\n* Line 12: \"learn graph data\" -> \"learn on graph data\"\n* Line 13: \"its robustness\" -> \"their robustness\"\n* Line 18: \"XGNN\" -> \"XGNNs\"\n* Line 53: It could help to first define a certified defense before using the term.\n* Line 265: Writing $|x|$ to denote the number of elements in $x$ is confusing, as it is not written or indicated that $x$ is a set. \n* Line 278/279: \"with\" -> \"within\"\n* Line 354: $M^*$@$\\lambda$ <- is this intended?\n* Line 363/364: \"GNN explaniner\" -> \"GNN explainer\"\n\n\n**References**  \nHamilton, \"Graph Representation Learning\", McGill University 2020  \nHuang et al., \"Going Deeper into Permutation-Sensitive Graph Neural Networks\", ICML 2022  \nWang et al., \"Improved Certified Defenses against Data Poisoning with (Deterministic) Finite Aggregation\", ICML 2022  \nXia et al., \"GNNCert: Deterministic Certification of Graph Neural Networks against Adversarial Perturbations\", ICLR 2024", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* In general, the paper is well-written and nice to follow. Next to the well-written main parts, I want to additionally highlight the very good and thorough overview of related work and contextualization of this work in it given in Section 5.\n* With a certifiably robust XGNN the paper seems to tackle a relevant problem given the brittleness of XGNNs to adversarial attacks.\n* Extending robustness certification (especially w.r.t. ensembles) to explainable sets is non-trivial, conceptually, as well as w.r.t. the proof strategy.\n* Through appropriate experiments, the effectiveness of the method to provide a certain robustness to structure changes is shown. Furthermore, the experiments nicely show the tradeoffs between classic XGNN methods and XGNNCert.", "weaknesses": "1. Currently, the experiments are not reproducible as experimental details are missing about $(i)$ the training strategy (even though Line 312 links to Appendix B for this, Appendix B does not include any experimental details), and $(ii)$ architectural details and hyperparameters of the used base classification and explainer GNNs. This is made even more critical as $(1)$ there is no code submitted for the review or indication of releasing code upon acceptance, and  $(2)$ no reproducibility statement provided. \n2. The $(M_\\lambda, \\lambda)$ robustness definition together with the remark in Line 148 is currently confusing. In particular, for any $\\lambda$, there can be many associated $M_\\lambda$ such that the network is still $(M_\\lambda, \\lambda)$ robust. Thus, $M_\\lambda$ is not uniquely indexed by $\\lambda$. However, by indexing $M$ with $\\lambda$, stating that $M_\\lambda$ is the certified perturbation size, and explicitly remarking it depends on $\\lambda$, it gives the impression as if it should be a unique function of $\\lambda$ and in the first read, it was unclear to me if the authors therefore actually mean the maximal $M_\\lambda$ for a particular $\\lambda$. I think the confusion could be resolved by removing the index $\\lambda$ (it is evident that $\\lambda$ and $M$ have a certain connection and tradeoff) and optimally, also introduce the concept of a maximal $M$ after the definition with a different letter (e.g., $M^*$ as used in Thm. 3, or now $M_\\lambda$, as the the maximal $M$ is uniquely determined by a given $\\lambda$). \n3. The goal of the work stated in lines 141-144 does not align with the contribution of the paper. In particular, the paper designs a concrete XGNN architecture based on ensembles to be able to (for the first time) derive robustness certificates. However, Eq. 1 defines a very different goal, namely optimizing over function spaces defining the XGNN and GNN classifiers, to find those functions leading to the highest certified robustness. However, the optimization over function spaces to maximize certified robustness is never mentioned or tackled in the subsequent paper. My recommendation is to remove Eq. 1, as the problem tackled by the paper is already very well motivated and formulated before providing this very different goal description. Otherwise, questions such as \"what function spaces do we optimize over\", or \"do we have convergence guarantees\", or similar, need to be asked and answered. As a third alternative, one could not state it as the goal of the current work, but a general goal the whole field/literature tries to answer/converge to.\n4. Generating subgraph indexes via the proposed hash mapping has first been proposed and done by Xia et al. (2024), I would expect to make clear somewhere that their hashing is used, potentially just by stating this and citing Xia et al. (2024) in the beginning of the second paragraph in Section 3.1 (e.g., \"We use the hash function (e.g., MD5) to generate the subraph indexes as done in Xia et al. (2024).\"). Furthermore, regarding majority voting-based certified defenses, the work of Wang et al. (2022) already divides the input data into non-overlapping parts (in contrast to what the paper mentions in lines 526/527). Even though this work is qualitatively different, I expect the work to be cited and the statement corrected when this is explicitly discussed in lines 526/527.\n5. The method is not permutation invariant. The authors discuss this in Appendix C, which however, is not linked in the main draft (please link to it). GNNs are usually developed with the goal to be permutation invariant (Hamilton 2020), and to me, it feels odd if an XGNN explanation is dependent on the concrete node order. In particular, node-order sensitivity can improve expressivity (and generalization) in the face of non-discriminatory node features (Huang et al. 2022), but I do not see that this property is particularly relevant for the developed XGNNCert as all used datasets seem to have discriminatory node features (nor any argument given that the concrete usage of permutation sensitivity improves expressivity). Addressing the permutation invariance is not critical for me to recommend acceptance, but I would like to at least see an experiment showing how brittle or stable the performance (classification and explanation-wise) of XGNNCert is to different permutations of the adjacency matrix. \n6. From the sentence at line 93-94, I first had the impression that the method can be applied to node classification tasks. However, Appendix C (again not linked) states that this is not possible without adaptation. I recommend to make this clear in the main draft when introducing the background or method and link to the discussion in Appendix C.\n7. In Section 3.3 the authors mention multiple times a statement similar to the one found in Line 276: \"$\\bar{\\mathcal{E}}_M$ [are] the edges in $\\bar{\\mathcal{E}}$ with top-$M$ scores in $n^\\gamma$\". Until reading and understanding the proof it was unclear to me if such a statement means either $(i)$ the edges in $\\bar{\\mathcal{E}}_M$ that are among the top-$M$ edges in $n^\\gamma$ given all edges (i.e., $|\\bar{\\mathcal{E}}_M|\\le M$); or $(ii)$ $\\bar{\\mathcal{E}}_M$ are the top-$M$ scored edges in $\\bar{\\mathcal{E}}$, i.e. $|\\bar{\\mathcal{E}}_M|=M$. Making this clear before providing Thm. 3 would greatly improve readability of Section 3.3 and the Thm. 3 in particular.\n8. Figure 4 and 5 feel repetitive to Figure 3. Maybe, it could be more interesting to show the impact of $p$ and $\\gamma$ also in the main draft (i.e., Figures similar to Fig. 9 & 10). Also note that in a first read, I was overwhelmed by Line 431 linking to Figures 3-11 all at once and it was not clear to me, if I should look at that figures now and how to find all the in-between figures.\n\nI think the paper has the potential to be a good contribution to the ICLR community. If the reproducibility weakness is addressed, I will raise my rating to a borderline score. If additionally my other weaknesses and questions are appropriately addressed, I am considering changing my score to accept (8).", "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": "uf8XW1lVvG", "reviewer": "Reviewer_Z8ry", "summary": "This paper proposes a certified defense method to mitigate the risk of an attacker who aims to mislead the GNN explanation. In order to achieve this goal, the calculate the maximum perturbation size to perturb in order to alter the prediction (explanation) of a graph.", "questions": "Plz see the weakness.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper is well written. \n2. The authors provide a reasonable motivation for the study (such as giving an motivating example in the introduction). \n3. The proposed method empirically efficacy to obtain certified robustness and it would not hurt the original performance. \n4. The method is potential to be applied for various GNN models.", "weaknesses": "Although the authors give a good motivation example (in the introduction section), I am still not fully convinced by the importance of the proposed study. For example, if one GNN builder aims to explain or understand their GNN model's prediction via GNN explainers, will there still be a high risk that the graph data is perturbed by an attacker? An perturbation operation could possibly easily identified by the GNN builder. \n\nBesides, I am also wondering the tightness of the proposed certified robustness. In Figure 5, the authors only provide the calculated perturbation bounds. How close are them to the real minimum perturbation budget?", "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": "enfQ3AR8cS", "reviewer": "Reviewer_adpV", "summary": "This work first studies the robustness of Explaining Graph Neural Network (XGNN) under graph perturbation attack and proposes an explainable defense mechanism. By generating hybrid subgraphs in which most of the designed voting classifier and voting explainer will give the correct prediction, this method avoids the XGNN performance degradation on both GNN's prediction and explanation under a worst-case attack. At the same time, the author provides a theoretical guarantee of the proposed defense's robustness.", "questions": "1. The author mentions the attacker can input a perturbed graph into the drug analysis tool. How can the attacker access the data in the realistic application?\n\n2. The author mentions that both the GNN classifier and the GNN explainer are essential for making correct explanations. Can these two models be combined into one model to defend against the graph perturbation attack rather than ensuring both model's accuracy?\n \n3. While the author emphasizes the robustness benefits of XGNNCert, can the author show more results against different attacks? For example, shorten the content of 4.2.1 and 4.2.2 and expand 4.2.3 by showing more results on more GNN models and comparing the proposed method with more baselines.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The writing is well-structured, and the contributions are clearly stated.\n\n2. The author provides a detailed explanation of the attack, the defense, and the theoretical guarantee.", "weaknesses": "1. The author claimed their method can be applied to any GNN classifier and explainer but did not show any results on different models. Only one type of classifier and explainer is used in the experiment.\n\n2. A lot of space is spent on parameter analysis of the proposed method, which may be combined as an ablation study.\n\n3. There is an explanation accuracy gap between XGNNCert and Baselines on datasets Benzene and FC in Table 1, where XGNNCert performs quite worse.\n\n4. The text in Figure 2 may need to be more visible.", "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 (Poster)