Evaluating Post-hoc Explanations for Graph Neural Networks via Robustness Analysis
Authors: Junfeng Fang
Wei Liu
Yuan Gao
Zemin Liu
An Zhang
Xiang Wang
Xiangnan He
Venue: NeurIPS 2023 oral (2023)
Keywords: Post-hoc Explainability
Explanation Evaluation
Graph Neural Network
Robustness Analysis
TL;DR: This work draws inspiration from the notion of adversarial robustness and introduces a novel evaluation metric, termed OOD-resistant Adversarial Robustness (OAR).

Abstract: This work studies the evaluation of explaining graph neural networks (GNNs), which is crucial to the credibility of post-hoc explainability in practical usage. Conventional evaluation metrics, and even explanation methods -- which mainly follow the paradigm of feeding the explanatory subgraph and measuring output difference -- always suffer from the notorious out-of-distribution (OOD) issue. In this work, we endeavor to confront the issue by introducing a novel evaluation metric, termed **O**OD-resistant **A**dversarial **R**obustness (OAR). Specifically, we draw inspiration from the notion of adversarial robustness and evaluate post-hoc explanation subgraphs by calculating their robustness under attack. On top of that, an elaborate OOD reweighting block is inserted into the pipeline to confine the evaluation process to the original data distribution. For applications involving large datasets, we further devise a **Sim**plified version of **OAR** (SimOAR), which achieves a significant improvement in computational efficiency at the cost of a small amount of performance. Extensive empirical studies validate the effectiveness of our OAR and SimOAR.

Evaluating Post-hoc Explanations for Graph Neural Networks via Robustness Analysis
Junfeng Fang', Wei Liu't Yuan Gao', Zemin Liu', An Zhang", Xiang Wang". Xiangnan He
University of Science and Technology of China,
National University of Singapore www..uuu.......... ffjf, 110118, yw {zeminliu, an_ zhang) @nus edu. ag,
(xiangvang1225
com
Abstract
This work studies the evaluation of explaining graph neural networks (GNNs), which is crucial the credibility of post-hoc explainability in practical usage. Conventional evaluation metrics, and even explanation methods - which mainly follow the paradigm of feeding the explanatory subgraph to the model and mea- suring output difference - mostly suffer from the notorious out-of-distribution (OOD) issue. Hence, in this work, we endeavor to confront this issue by intro- ducing novel evaluation metric, termed OOD-resistant Adversarial Robustness (OAR). Specifically, we draw inspiration from adversarial robustness and eval- uate post-hoc explanation subgraphs by calculating their robustness under at- tack. On top of that, an elaborate OOD reweighting block is inserted into the pipeline to confine the evaluation process to the original data distribution. For applications involving large datasets, we further devise a Simplified version of OAR (SimOAR), which achieves significant improvement computational efficiency at the cost of a small amount of performance. Extensive empirical studies validate the effectiveness of our OAR and SimOAR. Code is available at /stps::/githae com//Mangooilllr//Siiiinnn /Sm0ARR
Introduction
Post-hoc explainability has manifested its extraordinary power to explain graph neural networks (GNNs) [ 3]4, Given a GNN-generated prediction for graph, it aims to identify an explanatory subgraph, which is expected to best support the prediction and make the decision-makin -akiing process more credible, fair, and understandable 5 7]. However, the reliable evaluation of explanation quality remains key challenge. As primary solution, Human supervision seeks to justify whether the explanations align with human knowledge ( 99. but is often too subjective, thus hardly providing quantifiable assessments. Another straightforward solution is quantitatively measuring the agreement between the generated and ground-truth explanations, such as Precision and Recall 10 Unfortunately, access the ground truth is usually unavailable and labor-extensive, thereby limiting the scope of evaluations based on this method.
has been prevailing to quantita- tively evaluate the explanation's 's predictive power as compared to the full graph, without exploiting the human supervision and ground truth. The basic idea is to first remove the unimportant features and feed the remaining part (i.e., explanatory subgraph) into the GNN, and then observe how the prediction changes. The prediction discrepancy instantiates Accuracy
Recently, a compromised paradigm Feature Removal 12
13
g and Fidelity 9 of the
Liiu Wei is equal contribution to this paper. "Corresponding authors. Xiang Wang and Xiangnan He also affiliated with Institute of Artificial Intelligence, Institute of Dataspace, Hefei Comprehensive National Science Center.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Ingut
Explanation
Input
Explanation
Generative graph
Input
Constrained attack OOD score
O
0.3
GNN muragenic
GNN ''mutagencc
GNN mullgennc
GNN mutagenic
Explanation
comparc
compaar
LIX
Metri feed the explamation solely and compare the outcome
Metric complement the explanation
GNN
GNN
generative model compare the outcome.
mmutagenic
00.68
Region where model trained
arain
generative model
L
Data
40.54
10.27
Subgraph
Dataset
oo0
'Do0- mutageoic
Input
26 t
muiagenic
qunoss correlatoo
0,54x0.240 27xd.3 www.eeeeeeeeee..................
0.68-0.5+0.40-000
subgraph of distribution where model is trained.
Cavya:
Cower: the generative model always takes NH2 as the infilling part given Cl-.
Marti: generate instances via constrained
attack and reweight them by OOD scores.
(a) removal-based evaluation
(b) generation-bast evaluation
(c) our OAR evaluation
Figure 1:
Pipelines and flaws of different evaluation methods. In the "Input" graph, -NH₂ is considered as the ground truth explanation for its mutagenicity. Best viewed in color.
explanation, reflecting "how accurate and faithful the explanation is to recover the prediction of the input graph". Despite the prevalence, these removal-buas based metries usually come with the caveat of Specifically, as the after-removal subgraphs are likely
the out-of-distributioo (OOD) issue [14 13
16), the GNN forced to handle these off-manifold inputs and easily gets erroneous predictions [1 18 Take F as example. For the full molecular graph, the GNN classifies it as "mutagenic", which reasonable due to the presence of mutagenic - NH2 group; whereas, when taking the subgraph, i.e., non-mutagenic C-CI group solely as the input, the GNN surprisingly maintains its output "mutagenic". Clearly, the prediction on the explanatory subgraph might be skeptical, which easily deteriorates the faithfulness of the removal-based evaluations.
to lie off the distribution of full graphs 15
18 17 are beginning to mitigate the OOD issue via the Generation- based metrics. Instead of directly feeding the to-be-evaluated subgraph into the target GNN, they use generative model [19 200 to imagine and generate a new full graph conditioned on the subgraph. These methods believe that the generation process could infill the subgraph and pull it closer to the original graph distribution. As Figure (b) shows, comparing the predictions on this new graph and the original graph could be the surrogate evaluation. While intuitively appealing. the generative models easily inherit the data bias and inject it into the infilling part. Considering Figure (b) again, since molecules in the Mutagenicity dataset comprising non- mutagentaee chloride (-CI) always carry amino (-NH2). generative model is prone to capture this occurrence bias and tend to infill -NH with the Cl-involved subgraphs. This bias not only exerts on the generations but also makes the evaluation inconsistent with the GNN behavior: in the generative model, -CI is assigned with more "mutagenic" scores as it usually accompanies the mutagenic partner -NH2; in contrast, the GNN finds no "mutagenic" clues in - Cl. In nutshell, the generation-based metries show respect the data distribution somehow but could be inconsistent with GNNs' behavior and lose control of the infilling part.
In sight of this, recent efforts
Scrutinizing these removal- and generation- metrics (as summarized in Figure I). we naturally raise question: "Can we design metric that respects the data distribution and GNN behavior simultaneously?" To this end, we draw inspiration from adversarial robustness [1 and propose a new evaluation framework, OAR (OOD-resistant Adversarial Robustness), to help reliably assess the explanations. As shown in Figure (c). OAR encapsulates two components: constrained attack and OOD reweighting, which respect the GNN behavior and data distribution, respectively. Specifically:
Intuitively, perturbations on label-irrelevant features should be ineffective to the GNN prediction, while those on lelevatt features are supposed to be impactful and destructive to the prediction [1). Hence, for the original input graph, the attack model performs perturbations constrained on the complementary part of its explanation. This perturbing game aims to naturally take control the "infilling" process, making the explanatory subgraph less influenced by its infilling.
Having obtained set of perturbed graphs, the reweighting component estimates the OOD score of each perturbed graph, which reflects the degree of distribution shift from the original data

---

distribution. Then, we feed these graphs into GNN and reweight their predictions with OOD scores. The sum of weighted predictions can quantitatively evaluate the importance of the target subgraph.
We validate the effectiveness of QAR in evaluation tasks across various start-of-the-art explanation methods, datasets, and backhone GNN models. OAR has manifested surprising consistency with the metrics like Precision, Recall and Human Supervision. Furthermore, to better generalize to the large datasets, we also provide a Simplified version of OAR (SimOAR) achieving significant improvements in computational efficiency at the expense of a small amount of performance degradation. Our main contributions can be summarized as follows:
We propose a novel metric, OAR for evaluating GNNs' explainability. which tries to resolve the limitation of current removal- and generative-baset evaluations by taking both data distribution and GNN behavior into account (Section 2.2).
We provide simplified version of OAR, SimOAR for better generalization the evaluation tasks involving large datasets, which greatly shortens the execution time while only sacrificing a small amount of performance (Section 2.3).
Experimental results demonstrate that our OAR/SimOAR outperforms the current evaluation metries by a large margin, and further validate the high efficiency of SimOAR (Section
2 Methodology
In this section, we propose evaluation method for the explainability of GNNs from the perspective of adversarial robustness. We start with the notation of GNNs and its explainability in Section After that, we detail our evaluation metric, OAR via three progressive steps (Section 2.2p. In Section 2.3 we provide a simplified version of OAR called SimOAR for applications demanding more efficientexxccution execution.
2.1 Problem Formulation
Graph neural networks (GNNs). GNNs have achieved remarkable success due to their powerful representation ability. Without loss of generality, we focus on the graph classification task this work: well-trained GNN model f' takes a graph G as the input and outputs its probabilities y over classes {I.... C.}, i.e., y = f(g) E RC. Typically, G is an undirected graph involving the node set V and the edge set E. We first introduce the feature of node U, E V as d-dimensional vector and collect the features of all nodes into X R Then we define an adjacency matrix A E R | | to describe graph topology, where Ann if the edge connecting nodes u and v exists, i.e., (u, v) E E otherwise Ave O. Based on these, G can be alternatively represented as G = (A, X).
Explainability for GNNs. Upon the GNN model f. explanation techniques of GNNs generally study the underlying relationships between their outputs y and inputs G. They focus on explainability w.rt. input features, aiming to answer "Which parts of the input graph contribute most to the model prediction?" ?". Towards this end, explainers typically assign an importance score to each input feature (i.e., node v or edge (v,, v2)) to trace their contributions. Then they select the salient part (e.g.. subset of nodes or edges with top contributions) as the explanatory subgraph G. and delete the complementary part G5 G.G We formulate the explanation method as h and yield the above process as G. = h(G, J).
2.2 Resissttt Adversarial Robustness
Retrospecting the removal- and generation- based evaluations, we emphasize that both these classes come with inherent limitations. Specifically, Removal-based metrics pay less heed to the data distribution thus forcing GNNs to handle off-manifold instances, while generation-based metrics are inconsistent with GNN behavior and lose control of the infilling part. Fortunately, in this section, we claim that it is possible to get the best of and avoid the pitfalls of both worlds removal-based and generation- based metrics - by taking both GNN behavior and data distribution into account.
To meet these challenges, we claborate our evaluation metric, OOD-resistant adversarial robustness (OAR) via three progressive steps: in the first step, we formulate the adversarial robustness tailored for GNNs explanations, which naturally conforms to the GNN behavior; in the second step. we introduce tractable and easy-to- to-yy--ommmleennt objective of above adversarial robustness; in the third step, we introduce an elaborate OOD reweighting block which confines the overall evaluation process to the original data distribution.
STEP 1: Formulation of Adversarial Robustness. We prioritize the introduction of adversarial robustness in machine learning 22 23 that motivates method. Concretely, given a machine
3

---

Input 7R
Constrained Attack
model behavior
data distributinn)
Evaluntion
0.66
0.40
L I.
0.3
0.2
0.46
Explanation
GNN
x
T0.54
0.27
0.3
compare
Dataset
OOD reweighting block
reciprecal of recunsiruction loss: 1/L recon
encoder
decoder
original
Irain
VGAE
output
Figure 2: The pipeline of OAR, which takes both model behavior and data distribution into account.
learning model, imput æ and subset of the input 2, S 2, the adversarial robustness of x, denotes the minimum perturbation leading to the wrong prediction, on the condition that perturbation is only imposed on 2, [22]. Inspired by this idea, we define the adversarial robustness of GNN explanation G.. and formulate as the minimum adversarial perturbation 5 on the structure of complementary subgraph Gg. More formally,
Definition 1. Given a GNN model f. an input graph G = (A, X) with prediction y and explanation Ge. suppose that G' (A' is the graph generated by adding and deleting edges in G, the adversarial robustness of explanation G. is defined as:
8g. min A'
|Awe
Avull
NEV
VEV
(1)
s.t. arg max f(g'), # arg max ys
Σ
Σ
|Awv - An = 0,
WEV, vEVika
where V and V. are the node sets g and Gs, respectively.
Defimition 7 iidetifiees the quality of explanation 9s as the difficulty of reversing the prediction by perturbing features not belonging G, solely. That is, when G, is fixed, the more difficult it is to fool the model by perturbing its complementary, the more important G, is. The key intuition behind this inference is: if an explanation comprises most of the label-relevant features, it is conceivably hard to change the prediction by manipulating the remaining features that are label-irrelevant Thus, according to Definition]] 7 we can find that: a good explanation would yield high adversarial robustness 5 and vice versa, which naturally conforms to the GNN behavior.
It seems that adversarial robustness is the feasible metric to evaluate the GNNs' explanations. However, there are still two matters standing in the way of its adoption: 1) Is its objective (i.e., Equation (T) tractable and easy implement? 2) Does it respect the data distribution?
STEP 2: Finding a Tractable Objective. To answer the first question, we argue that Equation is hard to realize and sometimes even intractable owing to two possible reasons:
The primary reason is that adversarial attacks may fail find any adversarial example, since solution satisfying two conditions in Equation (I) simultaneously may not exist. In other words, if the explanation G. is precise enough, manipulating features in the complementary part G; which are mainly aabel-irrelevant.
almost impossible reverse the prediction via
is notoriously hard to search for the minimum adversarial perturbation å in most cases. Current attack methods (24 25 typically turn to find an alternative sub-optimal solution. Thus, leveraging these methods could introduce additional bias and threaten the fairness of evaluation.
To address these issues and make the evaluation objective tractable and easy to implement, we first formulate the inference derived from Definition 7:
Proposition 1. When the high quality explanation G. is anchored (fxed), perturbations restricted to the complementary part Gs have weak influence on the model prediction.
While Definition 7 evaluates the explanations via the adversarial robustness 8, Proposition Iidicatess more straightforward way to the tractable evaluation objective from its dual perspective. To be more specific, Definition quantifies perturbation on G. causing change of prediction; conversely, Proposition quantifics change of prediction caused by perturbation on G. More formally,

---

Given GNN model f. an input graph G = (A, with prediction y and explanation Is. suppose that g' X') is the graph generated by adding and deleting edges in G, the approximate adversarial rohustness 8* of 19, is defined as:
Definition 2.
9. = Eg (f(g")o ye)
S.t. c = arg max yj:
ΣΣ
|Au -Auol = 0,
(2)
NEV, VEV,Ya
where V. refers to the node set of 9s; denotes the predicted class of9 by model J; J(G"), represents the probability value of J (G') for the given class
Stemmed from Definition 2 the evaluation method to quantify the adversarial robustness of GNN explanations is more explicit and computationally convenient. As shown in Figure 2 for the to-be- evaluated subgraph 9N (i.e., C-CI in red dotted box), we anchor it and randomly perturb the remain part 93 to get graphs G' (i.e., molecules in green dotted box). Then the prediction of G' with the prediction of the original graph G. If they are close, most features in G5 must be label-irrelevan. Hence,
compare the expectation of
assign high quality for the explanation G..
So far, there is only one question left: how to ensure that the aforementioned evaluation process respects the data distribution?
STEP OOD Reweighting Block Tailored for GNNs. Before elaborating our OOD block, we first retrospect that in most scenarios, a tiny perturbation would not induce large distribution shifts along the imput space, thanks to the approximate continuity of imput features (e.g., image pixels in computer vision). Unfortunately, the structural features of GNNs' inputs adjacency matrix comprising of Os and 1s - are discrete thus only one perturbation (e.g., adding or deleting an edge) could induce large distribution shifts, and further violate the underlying properties, such as node degree distribution [26]. graph size distribution [27 and domain-speciff constraints (28).
Thus, it is pivotal to construct an OOD reweighting block for assessing whether the generated graph G' deviates from the data manifold. This block is expected to assign an "OOD score" the degree of distribution shift between G' and original graph g - to each G'. However, it is non-triviae to quantify the degree OOD [29]. Inspired by the great success of graph anomaly detection [30] 33 32 33 34),
we treat the OOD instance as the "anomaly" since it is isolated from the original data distribution, and naturally employ the common usage module of anomaly detection - variational graph auto-encoder (VGAE) [19] containing an encoder and decoder to instantiate our OOD reweighting block. Additionally, the great success of diffusion generative models has been recognized recently [35] (6].
and thus this domain is deferred for future investigation.
Concretely, as shown in Figure 2 the preparation for evaluations is training the VGAE model on the dataset 'D where input graph 9 is sampled. After that, we can leverage the reconstruction loss to approximate the degree of OOD for any generated instance g'. To be more specific:
Given G' = (A', (A','') X'), the encoder first learns a latent matrix Z according to A' and X', where z; corresponds to the node of in G'. Note that 2, is assumed follow the independent normal distributions with expectation μ4; and variance of. Formally:
A Il
M
dl 2 A' X
alzz A' X
II
Nizz m4 diag(o))))
(3)
1=1
where μ and parameterized by two two-layer GCNs 377 called GCN, n and GCN.. Then, the decoder recovers the adjacency matrix A' based on Z:
| |Ad
p(A
p(4
2 2,,
(4)
1
with (A4y==1 Fi, 23) o22 2;);
where o(.) is the logistic sigmoid function.
The OOD score of G' is given by the normalized reciprocal of the reconstruction loss Crecon (g'), log Z), with Z = μ GCN, (A', (A',x')
Crecon
(5)
5

---

Since VGAE is trained on the dataset D, g' straying far from the data distribution of D would get the high reconstruction loss Crecon. Thus, as the reciprocal of Erecon the OOD score of g' must be low. Conversely, if G' is in distribution, it would gain a high OOI) score because it is easy to be reconstructed. Based on this, our OOD block can mitigate the impact of OOD instances. Specifically, the OOD score is utilized as the weight of each prediction when calculating the expectation of the generated graph's 's prediction. This allows for the marginalization of instances with low OOD scores, as shown in the gray dotted box of Figure 2
Overall evaluation process. As the last piece of the OAR puzzle, i.e. OOD reweighting block has been instantiated, let's revisit Figure 2 and summarize the overall process of OAR:
1. Before evaluate the explanatory subgraph Gs+ the OOD reweighting block (i.e., VGAE) is trained on the dataset 'D where input graph & is sampled.
2. Then, fix the 9, and randomly perturb the structure of the complementary part G3 to get g'.
3. Each g' is fed into GNN f and VGAE simultaneously to audit prediction and OOD score. Both GNN's behavior and data distribution are taken into consideration in this step.
4. At last, according to the predictions and their weights (i.e., OOD scores), we calculate the weighted average of the generated graphs' predictions. The closer this average to the original prediction of G. the higher the quality of the explanation G3 is.
The pseudocode and the tricks expedite computations are detailed in Appendix A
2.3 A simplified version of OAR
To better generalize to large datasets and reduce the computational complexity, we provide simplified version of OAR called SimOAR in this section. Compared with OAR, SimOAR achieves a significant improvement in computational efficiency the expense of small amount of performance degradation. Concretely, SimOAR is mainly motivated by three empirical inferences after executing OAR:
The most time-consuming part of OAR is its preparatory work, i.e,, training OOD reweighting block, especially for large datasets. For example, on the dataset MNIST superpixels (38 containing 70,000 graphs, the converged process of VGAE occupies 93.7% of OAR's ' execution time.
In the course of generating G', the number of perturbation operations is roughly proportional to the degree of distribution shift given by the OOD block. For example, the graph 9 created via deleting one edge typically gets a higher OOD score than the graph 922 created via deleting five edges. For two generated graphs generated via the same perturbation times, they generally get similar reconstruction losses and are assigned similar OOD scores.
Based on these, to expedite computations and simplify the OAR, we deactivate the OOD reweighting block (i.e., deleting all the sketches in gray dotted boxes in Figure 2 in OAR. As compensation for data distribution, in the original graph G to a pre-defined minor value R. Since the generated graphs typically share similar reconstruction losses and OOD scores while R is fixed, we directly calculate their average prediction to approximate their excepted prediction. The pseudocode and more implementation details of SimOAR are provided in Appendix A
restrict the ratio of the number of perturbations to the number of edges
It is worth noting that despite the potential existence of a few generated graphs g' in SimOAR that fall outside the distribution, the performance of SimOAR still significantly surpasses that of current evaluation methods w.r./ consistency with both metries based on ground truth and human supervision. Hence, in light of the efficiency of the SimOAR, we strongly advocate for its adoption as predominant alternative to prevalent removal-basee evaluation metrics. At the heart of SimOAR and central thesis of this paper- is the perspective that, during evaluation, rather than deleting all non-explanee non-explanatory nodes and then gauging the resultant output variations, it is more insightful to randomly delete a portion of the non-explanatory nodes multiple times and then gauge the average output variations.
3 Experiments
We present empirical results to demonstrate the effectiveness of our proposed methods OAR and SimOAR. The experiments aim to investigate the following research questions:
RQI: How is the evaluation quality of OAR and SimOAR compared to that of existing metrics?
RQ2: How is the generalization of OAR and SimOAR compared to that of existing metries?
RQ3: What is the impact of the designs (e.g., s,, the OOD reweighting block) on the evaluations?

---

Table 1: Overall evaluation scores and rankings of explainers under different evaluation methods. Symbol (.) indicates the rank of explainers. Our methods, i.e., OAR and SimOAR are bold and the best-performing methods are denoted with the superscript asterisk.
SA
GradCAM
GNNExplainer
PGExpliner
CXPlain
ReFine
Recall
84.53 88.12-00m(
(6.83
a5
s4.77
72. (2
RM
37mf7 35.39
43.324199(0)
29.25
27. 27.78 (8)
41 1
0.73
BA3
DSE
43.08
41.38=175(9))
22.25+21440)
37.92-255())
24. 24.60
=29g1
0.73
OAR
93.1224au()
86
80. 19.
65 (5.48_377(0)
59. 39.69
71 71.02244559)
1.00*
SimOAR
84.39
83 (3/44)48/(9)
62,52
50.02.22ar(0)
55.49
60.42
0.93
Recall
82.08=aod
27.00
60.09=49:(4)
44.39 55.85
74.19=332(9)
RM
51.15
79.084431()
(0.45
47.72
64.60
0.67
TR3
DSE
37.32:235(4)
44.82+220(2)
33.71
35.65 (3)
39.49
0.73
DAR
(5.23
87.51
72.63-5aa939
(9.06=4x2(0)
51.61
63.82=5..())
0,93*
SimOAR
88.4516000)
76.37
53,542446 (5)
62.98
75.59
0.86
Recall 43.98-aod/))
44.39:
54.63:00.54)
40.13
38.9622a2(5)
47. 1o/
RM
21.34
19. (9
22.23+11o2(8)
25 (5.04=03;())
27.15
17.58
0.33
MNIST-sp
DSE
30.37
29.1 29.19221983)
14.03
28
21.32.122/0 22.95
0.20
OAR
46.28:2246())
64.18
82.22:44.5()
63.88-344(0)
11.37
(5.43=444(9))
0,93*
SimOAR
54.72+332(4)
69.8 (9)
79.69
52.93
76.40=22e
0,93*
Recall
41.12.nno/0
44, (4.44)))(())
(5.95
71.22aas(())
64
77.73236711
RM
(5.60
(7.39=am(0)
82.32+447(2)
87.11-23((1)
76.49:3.5(()
81.76224459
0.73
MUTAG
DSE
38.03+336(9)
32.36=2w49))
40.28+1.2(8)
49.18-255())
29.06+1.440)
43.19=2149)
0.67
52.10a1s6(9)
53.192581(8)
63.352229(4)
88.46_2ay(2)
67.1922m099)
22.81
1.00*
SimOAR
75.45a231(9)
7L07ssag(0)
85.65
(1.48-29g(
76.3243.8(4)
89:40=36
0.80
3.1 Experimental settings
To evaluate the effectiveness of our method, we utilize four benchmark datasets: BA3 39 TR3
177. Mutagenicity 44) 41] and MNIST-sp (38], which are publicly accessible and vary terms of domain and size. Moreover, to generate the explanations of the graphs in the datasets mentioned above, we adopt several state-of-the-arr post-hoc explanation methods, i.e., SA [IO), GradCAM [42),
GNNExplainer (T], PGExplainer 43 CXPlain 44 and ReFine [39]. The prevailing metrics
removal- evaluation (RM for short) and generation- based evaluation, i.e. DSE 17 are
selected as the baselines. Detailed experimental details can be found in Appendix B
3.2 Measurement metric
We elaborate on the measurement metric of existing evaluation methods in this part since how to fairly define the quality of an evaluation method is critical to our research.
Ground-truth explanations. We first follow the prior studies [1]] 45 43 and treat the subgraphs coherent to data generation procedure or human knowledge as ground truth. Although ground truth might not conform the decision-making process exactly, it contains sufficient discriminative information to help justify the quality of explanations. Moreover, it's worth emphasizing again that our method does not depend on ground truth, and gathering ground truth is only for fair comparison.
Consistency with metric based on ground -trund explanations. Specifically, given a to-be-evaluated subgraph G. and its corresponding ground-truth explanation GCT we use Recall as the gold evalua- tion metric defined as Recall(G.) = E& N / where E, and ECT are the edge set of G. and GCT; |- denotes the cardinal function of set. Hence, for any evaluation method, its consistency with Recall to quantify its performance via Kendall correlation T [46] defined as:
calculate
2 7 ((")).n. = nnn + 1)
(sgn (r² ppr--in rr) = sgn (s' 35--51 s())
(6)
J:= are pair of Recall values and evaluation scores; sgn(-) is the sign function and I(-) is the indicator function. The bigger 7 is, the higher the evaluation scores consistent with Recall values, and thus the better the evaluation method is.
where ) and { J
Consistency with human intuition. The consistency between evaluation results and human intuition also an important reference. In view of the high subjectivity of human intuition, we organized a large-scale user study engaging 100 volunteers. Results are shown in Appendix C
7

---

BA3
TR33
MNIIS- sp
1.0
1.0
DSE
OAR
SimOAR
-.MM
0AA
SmoOAR - DSS
0.5
StmDDAR - DSE
0.6
0.6
0.4
0.4
0.30
0.20
0.0
GNNExplater PGrnapaaerr CXPtuner
0.00
0.33
0.67
1.00
0.0
0.2
0.4
0.6
0.5
1.0
MNIST-sp
BA3
MUTAG
0.66
1.0
1.0
RM
DSE
OAR
SimOAR
RM
SimDAR A-D
0.6
0.5
0.4
0.
0.30
--OAR
RRM
SimOAR
0.20
GndCAM
GNNiiglane PGExptainer
0.00
0.25
0.50
0.75
1.00
0.0
0.5
1.0
(x) Correlation between evaluation muttres and Recall
(b) Cousistency between Recall and evaluation metries
Figure The performance of various evaluation metrics. (a) Correlation between metrics and Recall across various backbone explainers, where the vertical axis represents the normalized Kendall rank correlation. (b) Consistency between Recall and the scores provided by metrics. The more monotonously increasing the curve is, the better the evaluation metric is. Best viewed in color.
Limited by space, further exhibit and discuss more detailed implementations and results in Appendix B including but not limited to the generalization of OAR involving the evaluation of the post-hoc explanations for node classification task and the inherent explanations.
3.3 Study of explanation evaluation (RQ1)
As a preparation for the experiments. we first collect the explanatory subgraphs {9i} for a set of graphs {g') and the corresponding well-trained GNN model f. We denote the evaluation score on G based on RM, DSE and our OAR and SimOAR by SRM SiSE SÓAR and SSimAR respectively. For more faithful comparison, we present both the explainer-level correlation defined as T.
T =T
Ei Recall (g
NEH E Ei
i.h
and the instance-level correlation NEEH)
defined as T, = += (Recall (C:) N ( [s)) where * can be RM, DSE, OAR, and SimOAR:
A means the subgraph 9 is extracted by explainer h, H the set of explainers. The explainer-level results, under all evaluation methods, on all datasets, are presented in Table [ Moreover, considering the instance-level results share a similar tendency, we presented the representative results on BA3 and MNIST-sp Figure (a). According Table and Figure 3 (a) we can find that:
Observation 1: OAR outperforms other methods in all cases. Substantially, Kendall rank corre- lation greatly improves after leveraging the paradigm of adversarial robustmess. The most notable case is the explainers' rank on BA3 and MUTAG, where r 1.00 achieves a tremendous increase from the RM and the DSE. It demonstrates the effectiveness and universality of OAR/SimOAR and verifies that OAR/SimOAR can be leveraged to boost the quality of evaluations.
Observation 2: SimOAR performs little worse than OAR, but still significantly improves over the strongest baselines. To be more specific, the average score of SimOAR is 7.83% less than that of OAR, but still, 42.6 22.62% higher than RM and 37.45 37.45% higher than DSE. It demonstrates that SimOAR is adequate for the task of explanation evaluations in most cases.
Further analysis of the results presented in Table reveals that:
Observation 3: OAR/SimOAR presents a more fair and faithful comparison among explainers.
The rankings provided by the OAR and SimOAR are highly consistent (i.e., -" = 0.928 on average) with the references, while the removal- and generation-base rankings unsurprisingly pale by
comparison. These empirical results give us the courage to leverage OAR and SimOAR to evaluate emerging explanation methods in the future.
3.4 Study of generalization (RQ2)
Although the experiment provided 3.3 detailed and fair, we contend that the generalization of OAR and SimOAR is still unexamined. Specifically, specific explainer always has a preference

---

for certain patterns, and thus the explanatory subgraphs extracted by it often have similar structures. Therefore, the experimental results based on limited explainers may not generalize well other existing or future explainers, especially those based on different lines of thought.
As it is impractical for to cover all these explainers, we resort directly generalizing the to- be-evaluated subgraphs. That is, we make use of fake explanatory subgraphs which are randomly sampled from the full graph. The detailed sampling algorithm and settings can be found in Appendix C. In these settings, the best case is that the evaluation score is monotonically increasing w.F.t. the Recall level, which indeed reaches the best consistency. Average normalized scores under all evaluation methods are shown in Figure (b), which indicate that:
Observation 4: OAR/SimOAR greatly improves the consistency between evaluation scores and Recalls, which indicates that our method has tremendous potential to perform well on other explainers. Conversely, removal- and generation-based methods negatively correlated with the importance involving the set of to-be-evaluated subgraphs which get high Recalls.
3.5 Study of designs (RQ3)
Effectiveness of OOD block. We first focus on
Original Graph
Generated Graph
Generated Graph 2
the effectiveness of the OOD block. The most immediate impact of OOD block on OAR can be estimated by comparing the performance of OAR and SimOAR, which can be also deemed as the ablation experiments. Hence, we turn to qualitatively analyze the OOD block via some case studies shown in Figure 4 where all the OOD scores belonging to the same datasets are normalized to the range of 0 to 1. Based on the information conveyed in Figure the following observation can be made:
OOD
OOD Surre
OOD
0.64
OOD
ODD Score: 0.44
OOD
Score:
Score: 0.72
OOD
ODD Soores
ODD
Score:
Score:
0.69
0.85
Observation OOD block can assign the lower weights to the subgraph which vio- lent the underlying properties of the full graph. For example, graph properties of chemical molecules, such as the valency rules, impose some constraints on syntactically valid molecules. Hence, the invalid molecular subgraphs, which destroy the integrity of the carbon ring by simply removing some bonds (edges) or atoms (nodes) are assigned low scores by the OOD block.
Figure 4: Case studies for OOD reweighting block with the graphs randomly selected from datasets MNIST-sp. MUTAG, and BA3 arranged from top to bottom. Best viewed in color.
Time complexity. To further explore the ef- ficiency of our evaluation method and the de-
Table 2: Per-graph time consumption. (ms)
signed module in it, we count the running time
BA3
TR3
MNIST-sp
MUTAG
of the evaluation process on every single graph
RM
0.1
0.10=nor
0.15
0.13
and average the time over the entire test set to
DSE
1.73a0m
1.60
2.12
1.88
obtain per-graph time consumption. The com-
OAR
1.1610.8
1.321006
1.7710.0
1.781003
parison is provided in Table 2 According to
Table 2 we can find that:
SimOAR
0.8419.07
0.65
1.03
0.961006
Observation 6: SimOAR greatly reduces the execution time. Concretely, the execution speed has nearly doubled after leveraging the metric of SimOAR. This significant improvement in efficiency corresponds to the original intention of SimOAR and verifies the success of SimOAR's 's design.
4 Related Work & Further Discussion
OAR & Contemporary Evaluation Metrics. Apart from the qualitative evaluation methods based on human intuition, recent literature categorizes quantitative metrics into four primary categories: accuracy, faithfulness, stability, and fairness [47 48 49 50 52). Notably, Precision and Recall metrics align with the accuracy category, while our proposed OAR and SimOAR fall under the faithfulness category. Among these methods, the most recently proposed faithfulness metric GEF 49), which however omits guantification of the distribution shift in subgraphs. Nevertheless,

---

have exhibited the experimental comparison between GEF and our metrics w.Z the latest dataset SHAPEGGEN 49 in Appendix [3
OOD & GNNs Explainability The OOD issue is one of the most critical challenges in the post-hoc
explainability domain currently [T6 53 To sidestep this challenge, many studies have pivoted
towards the development of inherently explainable GNNs []5 54]. Notwithstanding the complexity of the task, efforts such as FIDO [55] are making significant successes addressing the OOD problem within post-hoc explanations. Concurrently, CGE [56] leverages the lottery ticket hypothesis [57 58 59 60 61 to craft the cooperative explanation for both GNNs and graphs, wherein the OOD challenge is potentially mitigated through the EM algorithm. GIBE [62] delves into the intersection of the OOD issue and regularization, viewing it through the lens of information theory. Furthermore, MixupExplainer [63] and CoGE [64] navigate the OOD problem from the generation and recognition stances, respectively.
Simultaneously, the evaluation of inherent explanations encounters the same hurdles as post-hoc ex- planations: it's challenging quantify in the absence of the ground truth. Fortunately, by introducing an additionally well-trained GNN, OAR can be employed to evaluate inherent explanations in similar way evaluate post-hoc explanations. The experimental results shown Appendix [
Limitations & Concerns. While we acknowledge the effectiveness of our methods, we also recognize their limitations. Concretely, despite utilizzig SimOAR to expedite the evaluation process, our paradigm remains more overcome this constraint, a probable solution is summarizing the optimal number of perturbations and implementing a self-adaptive extraction module to select the perturbed features.
compared to the conventional cemoval-bases metric. To
Furthermore, we recognize potential apprehensions regarding the migration of trust issues from the black-box GNN to the equally non-transparent VGAE. Nevertheless, we posit that the repercussions of this are substantially mitigated in our streamlined method. Specifically, SimOAR bypasses VGAE in favor of employing transparent heuristics for perturbation generation, effectively addressing the aforementioned trust concerns. It's noteworthy that, while SimOAR's 's performance may be marginally below or comparable to OAR's s, consistently exceeds other benchmarks. This emphasizes VGAE's restrained impact and reaffirms recommendation of SimOAR over OAR.
Conclusion
In this paper, we explored the evaluation process of GNN explanations and proposed a novel evaluation metric, O0D-resistant adversarial robustness (OAR). OAR gets inspiration from the notion of adversarial robustness and evaluates the quality of explanations by calculating their robustness under attack. addresses the inherent limitations of current removal- and generation- based evaluation metrics by taking both data distribution and GNN behavior into account. For applications involving large datasets, we introduce simplified version of OAR (SimOAR), which achieves a significant increase in computational efficiency at the cost of small amount of performance degradation. This work represents an initial attempt exploit evaluation metries for post-hoc GNN explainability from the perspective of adversarial robustness and resistance to OOD.
Ethics Statement
This work is primarily foundational in GNN explainability, focusing the development of more reliable evaluation algorithm. Its primary aim is to contribute to the academic community by enhancing the understanding and implementation of the evaluation process. We do not foresee any direct, immediate, or negative societal impacts stemming from the outcomes of our research.
Acknowledgments
This work was supported by the National Natural Science Foundation of China (9227010114 14, 62121002) and the University Synergy Innovation Program of Anhui Province (GXXT-2022-040).
References
[1] Vijay Prakash Dwivedi, Chaitanya K. Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. CoRR, 0aw.2003.00982,2220
10

---

[2] Tianyi Zhao, Yang Hu, Linda R. Valsdottir, Tianyi Zang, and Jiajie Peng. Identifying drug. target interactions based on graph convolutional network and deep neural network. Briefings Bioinform., 22(2):111-21500, 2021.
[3] Zhiwei Guo and Heng Wang- A deep graph neural -aasr mechanism for social recommendations. IEÉE Trans. Ind. Informatics, 17(4))2776 2783,, 2021.
[4] Kun Wang. Yuxuan Liang, Pengkun Wang, Xu Wang, Pengfei Gu, Junfeng Fang, and Yang Wang. Searching lottery tickets graph neural networks: dual perspective. The Eleventh International Conference Learning Representations, 2023.
[5] Minh N. Vu and My T. Thai. Pgm-explainer: Probabilistic graphical model explanations for graph neural networks. NeurlPS, 2020.
[6] Wanyu Lin, Hao Lan, and Baochun Li. Generative causal explanations for graph neural networks. In ICML, volume 139, pages 6666-6679, 2021.
[7] Michael Sejr Schlichtkrull, Nicola De Cao, and Ivan Titov. Interpreting graph neural networks for NLP with differentiable edge masking. In ICLR, 2021.
[8] Hao Yuan, Haiyang Yu, Shurui Gui, and Shuiwang Explainability in graph neural networks: A taxonomic survey. CoRR, 2ts/20022.15445, 2020.
[9] Hao Yuan, Haiyang Yu, Jie Wang, Kang Li, and Shuiwang Ji. On explainability of graph neural networks via subgraph explorations. In ICML, volume 139, pages 12241-12252. PMLR, 2021.
[10] Federico Baldassarre and Hossein Azizpour. Explainability techniques for graph convolutional networks. CoRR, abs/1905. 13686, 2019.
[11] Zhitao Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gnnexplainer: Generating explanations for graph neural networks. In NeurlPS, pages 9240-9251, 2019.
[12] Leo Breiman. Random forests. Mach. Learn., 45:5-32, 2001.
[13] Giles Hooker and Lucas Mentch. Please stop permuting features: An explanation and alterna- tives. CoRR, abs/1905.03151, 2019. 2019.
[14] Haoyang Li, Xin Wang, Ziwei Zhang, and Wenwu Zhu, Out-of-distribttion generalization on graphs: A survey. CoRR, abs/2202.07987. 2022.
[15] Siqi Miao, Mia Liu, and Pan Li. Interpretable and generalizable graph learning via stochastic attention mechanism. ICML, pages 15524-15543, 2022.
[16] Ying-Xin Wu, Xiang Wang, An Zhang, Xiangnan He, and Tat-Seng Chua. Discovering invariant rationales for graph neural networks. CoRR, abs/2201. 2022.
[17] Ying-Xin Wu, Xiang Wang, Zhang, Xia Hu, Fuli Feng, Xiangnan He, and Tat-Seng Chua. Deconfounding to explanation evaluation in graph neural networks. CoRR, abs/2201 108802, 2022.
[18) Christopher Frye, Damien de Mijolla, Tom Begley, Laurence Cowton, Megan Stanley, and Ilya Feige Shapley explainability the data manifold. In 9th International Conference Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021, 2021.
[19] Thomas N. Kipf and Max Welling. Variational graph auto-encoders. CoRR, abs/1611.00 1.07308. 2016.
[20] Diederik P. Kingma and Max Welling. Auto-encoding variational bayes. In 2nd International Conference on Learning Representations, ICL. 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014.
[21] Thomas Fel, Melanie Ducoffe, David Vigouroux, Rémi Cadène, Mikael Capelle, Claire Nicodeme, and Thomas Serre. Don't lie to me! robust and efficient explainability with verified perturbation analysis. CoRR, abs/2202.07728, 2022.

---

[22] Cheng- Yu Hsieh, Chih-Kuan Yeh, Xuanqing Liu, Pradeep Kumar Ravikumar, Seungyeon Kim, Sanjiv Kumar, and Cho-Jui Hsieh. Evaluations and methods for explanation through robustness analysis. In 9th International Conference on Learning Representations, ICIR 2021, Virtual Event, Austria, May 3-7, 2021, 2021.
[23] Yongduo Sui, Tianlong Chen, Pengfei Xia, Shuyao Wang, and Bin Li. Towards robust detection and segmentation using vertical and horizontal adversarial training. In 2022 International Joint Conference on Neural Networks (IJCNN), pages 1-8. IEEE, 2022.
[24] Daniel Züggner, Amir Akbarnejad, and Stephan Günnemann. Adversarial attacks neural networks for graph data. Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2018, London, UK, August 19-23, 2018, pages 2847-2856, 2018.
[25] Daniel Zügner and Stephan Günnemann. Adversarial attacks on graph neural networks via meta learning. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, 2019.
[26] Jure Leskovec, Jon M. Kleinberg, and Christos Faloutsos. Graphs over time: densification laws, shrinking diameters and possible explanations. In Proceedings of the Eleventh ACM SIGKDD International Conference Knowledge Discovery and Data Mining, Chicago. Illinois, USA, August 21-24, 2005, pages 177-187, 2005.
[27] Beatrice Bevilacqua, Yangze Zhou, and Bruno Ribeiro. Size- invariant graph representations for graph classification extrapolations. In Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, pages 837-851, 2021.
[28] Qi Liu, Miltiadis Allamanis, Mare Brockschmidt. and Alexander L. Gaunt. Constrained graph variational autoencoders for molecule design. In Advances in Neural Information Processing Systems 31: Annual Conference Neural Information Processing Systems 2018, NeurIPS
2018, December 3-8, 2018, Montréal, Canada, pages 7806-7815, 2018.
[29] Haoyang Li, Xin Wang, Ziwei Zhang, and Wenwu Zhu. OOD-G. GNN: out-of--iisriibutin generalized graph neural network. CoRR, abs/2112.03806, 2021.
[30] Xiaoxiao Ma, Jia Wu, Shan Xue, Jian Yang, Quan Z. Sheng, and Hui Xiong. A comprehensive survey graph anomaly detection with deep learning. CoRR, abs/2106.07174 78, 2021.
[31] Yuan Gao, Xiang Wang, Xiangnan He, Zhenguang Liu, Huamin Feng, and Yongdong Zhang. Alleviating structural distribution shift in graph anomaly detection. In WSDM, pages 357-365. ACM, 2023.
[32] Xian Teng, Muheng Yan, Ali Mert Ertugrul, and Yu-Ru Lin. Deep into hypersphere: Robust and unsupervised anomaly discovery in dynamic networks. In Proceedings of the Twenty- Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018, July 13-19, 2018, Stockholm, Sweden, pages 2724-2730, 2018
[33] Yuan Gao, Xiang Wang, Xiangnan He, Zhenguang Liu, Huamin Feng, and Yongdong Zhang. Addressing heterophily in graph anomaly detection: A perspective of graph spectrum. In WWW, pages 1528-1538. ACM, 2023.
[34] Yuan Gao, Xiang Wang, Xiangnan He, Huamin Feng, and Yong-Dong Zhang. Rumor detection with self-supervised learning on texts and social graph. Frontiers Comput. Sci., 1744),,7461, 2023.
[35] Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. In NeurlPS, 2020.
[36] Prafulla Dhariwal and Alexander Quinn Nichol. Diffusion models beat gans on image synthesis. In NewrIPS, pages 8780-8794, 2021.
[37] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR (Poster), 2017.
12

---

[38] Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodolå, Jan Svoboda, and Michael M. Bronstein. Geometric deep learning on graphs and manifolds using mixture model cnns. In CVPR, pages 5425-5434 2017.
[39] Xiang Wang, Ying-Xin Wu, An Zhang, Xiangnan He, and Tat-Seng Chua. Towards multi- grained explainability for graph neural networks. In NeurIPS, pages 18446-18458, 2021.
[40] Jeroen Kazius, Ross McGuire, and Roberta Bursi. Derivation and validation of toxicophores for mutagenicity prediction. Journal of medicinal chemistry, (8:1))112-3222 2005.
[41] Kaspar Riesen and Horst Bunke. IAM graph database repository for graph based pattern recognition and machine learning. In SSPR/SPR, pages 287-297, 2008
[42] Ramprasaath R. Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra. Grad-cam: Visual explanations from deep networks via gradient-based localization. In IEEE International Conference on Computer Vision, ICCV 2017, Venice, Italy, October 22-29, 2017, pages 618-626, 2017.
[43] Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang. Parameterized explainer for graph neural network. In NeurIPS, 2020.
[44] Patrick Schwab and Walter Karlen. Cxplain: Causal explanations for model interpretation under uncertainty. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[45] Hao Yuan, Jiliang Tang, Xia Hu, and Shuiwang Ji. XGNN: towards model-Ievel explanations of graph neural networks. In KDD, pages 430-438, 2020.
[46] Eulalia Szmidt and Janusz Kacprzyk. The spearman and kendall rank correlation coefficients between intuitionistic fuzzy sets. In EUSFLAT Conf, pages 521-528. Atlantis Press, 2011.
[47] Anna Himmelhuber, Mitchell Joblin, Martin Ringsquandl, and Thomas A. Runkler. Demystify- ing graph neural network explanations. In PKDD/ECML Workshops (1), volume 1524, pages 67-75, 2021.
[48] Benjamín Sänchez-Lengeling. Jennifer N. Wei, Brian K. Lee, Emily Reif, Peter Wang, Wes- ley Wei Qian, Kevin McCloskey, Lucy J. Colwell, and Alexander B. Wiltschko. Evaluating attribution for graph neural networks. In NeurlPS, 2020.
[49] Chirag Agarwal, Owen Queen, Himabindu Lakkaraju, and Marinka Zitnik. Evaluating explain- ability for graph neural networks. CoRR, abs/2208.09 099399, 2022.
[50] Chirag Agarwal, Marinka Zitnik, and Himabindu Lakkaraju. Probing GNN explainers: A rigorous theoretical and empirical analysis of GNN explanation methods. In AISTATS, volume 151, pages 8969-8996, 2022.
[51] Lukas Faber, Amin K. Moghaddam, and Roger Wattenhofer. When comparing to ground truth is wrong: On evaluating GNN explanation methods. In KDD, pages 332-341, 2021.
[52] He Zhang, Bang Wu, Xingliang Yuan, Shirui Pan, Hanghang Tong, and Jian Pei. Trustworthy graph neural networks: Aspects, methods and trends. CoRR, hiss/2205.07424, 2022.
[53] Yongduo Sui, Xiang Wang, Tianlong Chen, Meng Wang, Xiangnan He, and Tat-Seng Chua. Inductive lottery ticket learning for graph neural networks. Journal of Computer Science and Technology, 2023.
[54] Gang Liu, Tong Zhao, Jiaxin Xu, Tengfei Luo, and Meng Jiang. Graph rationalization with environment-based augmentations. In KDD, pages 1069-1078, 2022.
[55] Chun-Hao Chang, Elliot Creager, Anna Goldenberg, and David Duvenaud. Explaining im- age classifiers by counterfactual generation. 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, 2019.
13

---

[56] Junfeng Fang, Xiang Wang, An Zhang, Zemin Liu, Xiangnan He, and Tat-Seng Chua. Coopera- tive explanations of graph neural networks. WSDM, pages 616-624. ACM, 2023.
[57] Ari S. Morcos, Haonan Yu, Michela Pagannni, and Yuandong Tian. One ticket to win them all: generalizing lottery ticket initializations across datasets and optimizers. In NeurIPS, pages 4933 4944,9433322 2019.
[58] Kun Wang, Yuxuan Liang, Pengkun Wang, Xu Wang, Pengfei Gu, Junfeng Fang. and Yang Wang. Searching lottery tickets in graph neural networks: A dual perspective. In The Eleventh International Conference on Learning Representations, 2022.
[59] Yongduo Sui, Xiang Wang. Jiancan Wu, Min Lin, Xiangnan Hc, and Tat-Seng Chua. Causal attention for interpretable and generalizable graph classification. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 1696-1705, 2022.
[60] Tianlong Chen, Yongduo Sui, Xuxi Chen, Aston Zhang, and Zhangyang Wang. A unified lottery ticket hypothesis for graph neural networks. ICML., pages 1695-1706, 2021.
[61] Yanfang Wang. Yongduo Sui, Xiang Wang, Zhenguang Liu, and Xiangnan He. Exploring lottery ticket hypothesis in media recommender systems. International Journal of Intelligent Systems, 37(5):3006-3022 3024, 2022.
[62] Junfeng Fang, Wei Liu, An Zhang, Xiang Wang, Xiangnan He, Kun Wang, and Tat-Seng Chua. On regularization for explaining graph neural networks: An information theory perspective. 2022.
[63] Jiaxing Zhang, Dongsheng Luo, and Hua Wei. Mixupexplainer: Generalizing explanations for graph neural networks with data augmentation. KDD, pages 3286-3222 128666296. ACM. 2023.
[64] Lukas Faber, Amin K. Moghaddam, and Roger Wattenhofer. Contrastive graph neural network explanation. CoRR, abs/2010. 13663, 2020.
[65] Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
[66] Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. CoRR, abs/1710. 10ts//700,,000,, 2017.
[67] Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful are graph neural networks? In ICLR. OpenReview.net, 2019.
14

---

A Algorithms
Algorithm| presents the pscudocode of the evaluation process of our proposed method OAR. The pseudocode of SimOAR can be obtained by removing the line 1, 6, and and simply modifying line 9 into "s + N.d= >; y For clarity, we put the step of feeding adversarial graph gl into the target GNN and the VGAE under the for-loop. However, when implementing in real code, can batch all those Nadv adversarial graphs and feed them at one time, after sampling process finished, to expedite computation. Meanwhile, Algorithm| 2 presents the sampling process of fake explanatory subgraphs for general evaluation.
Algorithm Evaluation Process OAR
Input: Trained GNN f; To-be-evaluated subgraph G, and its corresponding original graph 9 and dataset D; Perturbation ratio Rt Number of adversarial graphs Nadv
Output: Evaluation score $
1: Train a standard VGAE on according to 19
2: < arg max, (G)::
3: for 11,,..... Nado do
4: G*(+) +- randomly deleting [R |Egl] edges from 9 while fixing Gg-
y(i) + f(g"())
5:
c(t)
6:
Frecon + caleulated according to Equation using the trained VGAE.
7: end for
8: WOOD
(8)
1/200
i 2, ... Nadu.
Σ, 1/c/2
9:
Σ; w WOD y/0
Algorithm 2 Sampling Fake Explanatory Subgraphs for General Evaluation
Input: Dataset D = - g G Number of Recall levels Nz; Number of sampled subgraphs per graph Neas: Size of sampled subgraph Kaub Output: Pairs of Recall level and corresponding subgraphs (Iu: {G i =
1, N.....,,,u)))
1,2 NN
for 1.2..... No do 1 for = 1......, N do
2:
Lb t k-1
3:
4:
KGT + the number of edges in the ground-truth explanation of g
5:
K Koss t L KG
6:
Kneg- t K sub Kpos
7:
for j = 1, ..,............
Nout do
8:
God + a connected subgraph, randomly sampled from G, with K Kpss edges in the ground truth explanation and Kneg edges not in it.
9: end for
10: end for
end for
B Experimentals
B.1 Experimental Details
All experiments are conducted on Linux machine with NVIDIA GeForce RTX 3090 (24 GB) GPUs. CUDA version is 1 11.6 and Driver Version is 510.39.01. All codes are written under Python 3.9.13 with PyTorch 1.13.0 and PyTorch Geometric (PyG) 2.2.0. We adopt the Adam optimizer throughout all experiments.
Overall, for each dataset, a target GNN classification model well-trained first. Then the explainers are built on the GNN and generate explanations for its prediction on the dataset. After that, the explanation evaluation methods evaluate how well the explanations are. Our work stands the last level.
15

---

Study MNIST-sp
class
Original Graph
High Quality
Human Intuition
Low Quality
Explanation
Explanation
Explanation 3
Explanation
Explanation 5
2
DAR SimOAR RSS DS0
DAR SIMOAR XIM UN8
DAR SIMOAK
RM DNK
DME SimUAR JUM 1391
CAR SimUAAL IEM US!
OAR SImOAR RM DSE
OAR SHBOR XMM DSE
OAR SISOAR RME DSE
OAR SIBOAR RM DSE
OAR SENOARL RMM DSE
OAR simOAll IIM DSE
DARL SIBOAR HDM DSE
DAR SIMOAR JUM DSE
OAR SHIAAR RMM DNS
OAR SIBOAR XM DSB
SIMDAAL
SiODAR
SinOAR
SimOOR
Figure 5: Study cases. For each row, the explanations are ranked based on average rankings given by volunteers. Highlighted evaluation method below each explanation means that the method has given the explanation the highest score compared to other explanations in that row. Best viewed in color.
Target GNNs, GNNs have garnered significant recognition for their prowess encoding graph Amidst the vast landscape of GNNs, GIN (67) distinguishes itself with its superior encoding aptitude. In sight of this, the target GNNs for BA3, TR3,, and Mutagenicity have the same structure, which is two-layered GIN followed by two-layered MLP with 32 hidden channels. They are trained with max epochs equal to 20, 200, and 200 respectively, batch size equal 128, and learning rate equal 0.001. The target GNN for MNIST-sp is adapted from an example by PyG, trained with the number of epochs equal to 20, batch size equal to 64, and initial learning rate equal to 0.01. Before training, we randomly split BA3, TR3, and Mutagenicity into train and test sets with ratios of 90% and 10%, respectively, while adopting the split provided by PyG for MNIST-sp. During training, we reserve data of the same size the test set from the train set as the validation set and save the model which reaches the highest classification accuracy on the validation set for later use.
data [37 66
67 34 58
Explainers. We have implemented six state-of-ther -hthe-rrt post-hoc explainers. namely, SA, GradCAM, GNNExplainer, PGExplainer, CXPlain, and ReFine, as claimed in Section 3.1 to generate explanatory subgraphs. Here we give a brief introduction to them:
SA [10] captures the gradients w.e.. adjacency matrix of the input features in the process of backpropagation and directly treats them the importance scores.
GradCAM [42] takes one step further over SA via improving the gradients w.e.. the input features like edges by using context within the graph convolutional layers.
GNNExplainer [1] directly learns an adjacency matrix mask by maximizing the mutual informa- tion between GNN's prediction and distribution of possible subgraph structures.
PGExplainer [43] adopts deep neural network to parameterize the generation process of explana- tions, which makes natural approach explaining multiple instances collectively.
'Reference code for the target GNN of MNIST-sp: htw.s//ggggg/p///ggg.../oooo/o// feeercccbbeaakkkeeaaaateteeeeeee
16

---

Table 3: Average consistency scores of different evaluation metrics (corresponding to Table in the main paper).
SHAPEGGEN
TR3
MUTAG
MNIST
BA3
GEF
0.800
0.734
0.800
0,934
0.734
SimOAR
0.800
0.867
0.800
0.934
0.934
OAR
0.867
0.934
1.000
0.934
1.000
Table 4: Correlation between metrics and Recall across explanatory subgraphs in four node classifica- tion datasets in (corresponding to Figure 3
(a) in the main paper).
BA-Shapes
BA CA-Cmmunity
Tree-Cycles
Tree-Grid
RM
0.312
0.321
0.295
0.411
DSE
0.406
0.377
0.343
0.384
OAR
0.542
0.560
0.489
0.440
SimOAR
0.527
0.535
0.471
0.431
CXPlain 44
treats the explanations as a causal learning task and trains causal explanation models
that learn to estimate to what degree certain inputs cause outputs in the to-be-explained model.
ReFine (39 leverages the pre-trate pre-training explanations to exhibit global explanations and the fine- tuning explanations adapt the global explanations in the local context.
The default hyper-paramen
suggested by those papers are adopted, as whether the explainers are at their optimal state is secondary to our work. Among these explainers, SA, GradCAM, and GNNExplainer directly take the to-be-explained graph as input, while the rest three need to be trained on set of graphs, i.e., the train set in our case, in advance. We only use the explanations extracted from graphs in the test set for evaluation.
Evaluation Methods. Finally, we arrive at the explanation evaluation level. There are four evaluation methods, i.e., removal-based evaluation, DSE, OAR, and SimOAR, to be considered. Removal-based evaluation directly feeds the explanatory subgraph into the target GNN and gets its prediction, on the predicted class of the original graph, as the evaluation score, which does not involve any details. For DSE, we make use its public source code and follow its paper to set hyper-parametent As for our method OAR/SimOAR, we have summarized the entire process of OAR in Algorithm|] I Here present more details on how the VGAE is trained. The encoder involves two two-layered GCNs for obtaining and each of which is realized with hidden channels equal to 256 and output channels equal to 128, while the two GCNs share the first layer. The dataset split process is the same as the training of the target GNNs. We train the VGAE model on the train set with the number of epochs equal to 100, batch size equal to 256, and learning rate equal to 0.001. The model that reaches the lowest loss on the validation set is saved for later OOD reweighting.
B.2 More Quantitative Results
Here, we sequentially present the experimental results 1) comparison between GEF (4] and our metrics w.r. the latest dataset SHAPEGGEN and the other datasets (Table (). 2) correlation between metrics and Recall across explanatory subgraphs in four node classification dataset (Table 4 and 3) correlation between metrics and Recall while evaluating the explanations generated by the inherent explainable GNN, GSAT [15] via introducing an additionally well-trained GIN [7] as the model f
in Algorithm 1 (Table 5)
Note that while evaluating explanations in node classification tasks, for each node in the input graph, we construct an ego graph for it based on the number of layers in the baseline GNN. Then, the explanation task for node classification can be transferred to the explanation task for graph classification. Furthermore, the remaining hyperparameters and methods in our OAR/SimOAR remain unchanged.
Source code of DSE: https: tettps://anooyooote 4open htiee/ssccinc/////SS--2222
17

---

Table 5: Correlation between metrics and Recall while evaluating the explanations generated by the inherent explainable GNN, GSAT (corresponding Figure (a) in the main paper).
BA3
MUTAG
TR3
MINST
RM
0.376
0.381
0.402
0.337
DSE
0.411
0.425
0.417
0.319
OAR
0.613
0.590
0.585
0.606
SimOAR
0.598
0.572
0.552
0.581
C User Study
In order to measure the consistency between evaluation results and human intuition, we organized large-scale user study engaging 100 volunteers. Each volunteer asked check 5 groups of graphs, which contain an instance from MNIST-sp, its predicted class, and 5 randomly sampled subgraphs from this instance, and try to rank these 5 subgraphs according how well they serve as explanations of the prediction based on intuition. We exhibit partial results in Figure 5 According these results we can find that our evaluation methods iee. OAR and SimOAR show the highest consistency with human intuition.
18


Reviews:
[{"review_id": "Na3V4xxjTA", "reviewer": "Reviewer_QMrv", "summary": "This paper studies the explainability evaluation of GNNs, and proposes a new evaluation paradigm. Inspired by adversarial robustness, it uses a generative model (VGAE) to fulfill the explanation subgraph, randomly perturbs the fulfilled parts, and uses the OOD scores of perturbed graphs to measure the importance of explanation subgraph. Experiments are done on several datasets and show the improved evaluation quality w.r.t. diverse criteria.", "questions": "1.\tWhy name the random perturbation as adversarial robustness, which usually performs adversarially perturbation? Does it mean that “How adversarial are random perturbations against the original data distribution, which are measured by OOD score”?\n2.\tHow many perturbed subgraphs are needed?\n3.\tWhat is the influence of VGAE quality on the OAR performance?\n", "limitations": "N/A", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1.\tThis paper summarizes the removal- and generation-based evaluation protocols well, and points out their drawbacks w.r.t. post-hoc explainability. It resolves these drawbacks by calculating the robustness of explanations under attack and OOD-reweighting. This motivation is clear and reasonable.\n2.\tIn terms of technical contributions, the evaluation of explanation robustness is well-designed. It first gives an adversarial robustness-related definition, and then transfers it into a tractable objective and designs an OOD-reweighting block (i.e., an external VGAE) to solve the objective. Moreover, a computationally efficient variant is also proposed.\n3.\tThe experiments are sufficient to demonstrate the effectiveness of the proposed method, w.r.t., explanation evaluation, generalization, model design, and user study.\n4.\tI appreciate the diverse criteria used in the paper, especially the “consistency of ground-truth explanations and human intuition”.\n5.\tThe presentation of the proposed method is clear.\n", "weaknesses": "1.\tRegarding adversarial robustness, the proposed measurement is based on perturbing the subgraphs. I have two questions: (1) why name the random perturbation as adversarial robustness, which usually performs adversarially perturbation? Does it mean that “How adversarial are random perturbations against the original data distribution, which are measured by OOD score”? (2) How many perturbed subgraphs are needed? I think these concepts are essential to understand the proposed evaluation method. Hence, more clarification is needed.\n2.\tThe OOD reweighting block is implemented by VGAE, hence, the proposed method seems heavily dependent on the VGAE quality. However, many studies show the generative ability of VGAE is suboptimal and degenerated. It would be better to analyze the influence of VGAE quality on the OAR performance.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Dear Reviewer QMrv:**\n\n**Thank you for the thoughtful feedback! Your constructive criticism has been invaluable in refining our work. Below, we give point-by-point responses to your comments. Hope that our responses could address all your concerns!**\n\n\n>*W1 & Q1: Does the adversarial robustness mean that “How adversarial are random perturbations against the original data distribution, which are measured by OOD score”?*\n\nThanks for your concern. Yes, it does. \n\nHere are two more reasons why we named our methods OAR (OOD-resistant **adversarial** robustness): \n\n- First, the starting point of our methods is finding the minimum perturbation leading to the wrong prediction (Line 128-132 in the main paper). However, this target is proved to be hard to reach and sometimes even intractable in the scenario given in the paper (Line 144-151). Thus, we transfer to approximate it from its dual perspective. That is, calculating the largest changes of outputs under the attacks. Hence, **our approach is essentially derived from the adversarial attack.**\n\n- Moreover, here are the imposed objective and the target of the *adversarial attack* and *our attack in OAR*, which are similar with each other:\n\n|               |    &emsp; &emsp;&emsp; &emsp; &emsp; &emsp; Objective  |   &emsp; &emsp;&emsp; &emsp; &emsp; &emsp;Target  | \n|:-------------:|:--------:|:--------:|\n|     Adversarial Attack    |   **selected part of input** (*which is selected by the attack algorithm*)   |   **perturb output as much as possible** (*until flip the outputs*)    |   \n|     Attack in Our OAR   |   **selected part of input** (*which is selected by the explanations*)  |   **perturb output as much as possible** (*to see the robustness*)   |  \n||||\n\nMoreover, following your suggestion, we have added these clarifications into the Introduce Section in the reversion. We believe that this will greatly increase the readability, coherence, and comprehensibility of the article.\n\nThanks again for your valuable suggestion!\n\n>*W2 & Q2: How many perturbed subgraphs are needed?*\n\nPlease refer to Line 160-161 in Appendix, where we point out that for BA3, TR3, and MUTAG, the number of perturbed subgraphs $N_{perturb}$ is 20, while for MNIST-sp, the number of perturbed subgraphs $N_{perturb}$ is 50 owing to its large size.\n\n>*W3 & Q3: What is the influence of VGAE quality on the OAR performance?*\n\nThanks for your concern. The quality of VGAE will have a certain impact on the performance of OAR, but it is not significant. Here is the reason:\n\n- The simplified version of OAR -- SimOAR (which can be viewed as the case that the VGAE is poorly trained and produces random scores) -- performs close to OAR. It indicates that the performance of VGAE does not significantly impact OAR's performance, and further demonstrates that the effectiveness of our OAR and SimOAR is mainly attributed to the preferable paradigm, instead of the other module (e.g., VGAE). \n\n**Once again, we sincerely appreciate your time and effort in reviewing our paper. Your constructive criticism has been invaluable in refining our work, and we are more than happy to add clarifications to address any additional recommendations and reviews from you!**\n\n**Best,**\n\n**Authors**\n"}, {"review_id": "vB8XGhKwcE", "reviewer": "Reviewer_xH8P", "summary": "This paper presents a new evaluation metric OAR for evaluating post-hoc explanation methods for GNNs. OAR has two main advantages in that it does not need ground-truth labels and in that it prevents finding spurious explanations based on out-of-data-distribution phenomena. The paper focuses on graph classification: The input for this explanation is a subgraph of the graph for which we want to explain a prediction. The proposed method OAR, creates several permutation of the original graphs, where it is allowed to only permute edges **not** in the explanation. A generative model forces those permutations to not leave the training data distribution. The less the permutations can change the model prediction the better an explanation we consider the subgraph. Experiments validate the effectiveness of OAR.\n", "questions": "Could you expand on the setup used for the user study? The previous years (e.g., https://neurips.cc/Conferences/2021/PaperInformation/PaperChecklist) included a paper checklist of what to consider and the details in Appendix D are quite short.\n\nThe study on MNIST explanations seems to be very dependent on the layout of the explanation subgraph (maybe even more so than the choice of what nodes to put there). Can you expand on how you created the graph layout? Are superpixel nodes positioned where they are placed in the image?\n\nDoes the permutation space for the targeted adversarial attacks allow adding and deleting nodes? Or are the attacks constrained to happen in the given adjacency matrix?\n\nOAR itself makes no assumptions on the size of the explanation, but it seems it is easier to get good explanations the larger the explanation graph is: there is less attack space for adversarial permutation and a larger fixed graph likely helps for low OOD scores. I wonder if OAR would benefit from a component that penalizes surplus nodes in the explanation?\n\nCould the method be expanded to also support node classification? One naive angle might be to extract the receptive field of each node and use OAR on those graphs?\n\nFrom what I understand, an important motivation is the fight of out-of-distribution data. This motivates the generative graph model to find and remove outliers. On the other hand, it seems that SimOAR performs similarly without using such a model but a budget(?) on perturbations. Can we maybe do something simpler than the generative model, for example, looking at spectra?\n\nSome of the works linked above showed that the BA and tree based datasets have flaws and GNNs do not always use all the data present in the ground truth. Could these also influence your experiments?\n", "limitations": "Addressed by the authors", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper tackles an important topic, GNN explanation, in an ambitious way: To evaluate different explanation methods unsupervised, without access to ground truth explanations.\n\nThe paper is in a good shape (apart from the introduction+related work): The writing is clear and allows for understanding most of the paper in the first or second read. The figures are helpful for understanding and well connected to the text. The experiments chosen by the authors make sense and I appreciate the authors also running a user study.\n", "weaknesses": "I do not like the approach the authors have taken for the related work in this paper. The first section is a hybrid of related work and introduction, and I feel it serves neither well. I am missing a concise motivation and a broader context of the paper from this section. The actual related work is in Appendix A, which I would prefer to be in the main paper. I also think that there is an important branch of work missing [1-5]. These works discuss general properties that we may want an explanation method and an evaluation setup to adhere to. I think it would benefit the paper to discuss how OAR is compatible/incompatible with these proposals. These works also offer some alternative benchmarks for evaluation instead of the flawed BA and tree-based (TR) datasets. \n[1] Himmelhuber et al: Demystifying Graph Neural Network Explanations\n[2] Sanchez-Lengeling et al. Evaluating attribution for graph neural networks\n[3] Agarwal et al. Evaluating explainability for graph neural networks\n[4] Agarwal et al. Probing GNN explainers: A rigorous theoretical and empirical analysis of GNN explanation methods\n[5] Faber et al. When comparing to ground truth is wrong: On evaluating GNN explanation methods\n\nThere is also one paper discussing out-of-distribution versus explanation for GNNs [6] that might be worth discussing/comparing to.\n[6] Faber et al. Contrastive graph neural network explanation\n\nI am not convinced about the explanations that the method produces. Generally, we want to create explanations to make humans understand what is happening. For this, every step to create the explanation is ideally human inspectable. Here, it seems like we are transferring the trust problem from the GNN to the VGAE. This becomes the blackbox that somehow determines if the results are good or bad and we cannot inspect this blackbox. For example, using recall on ground-truth data makes for a good explanation metric because us humans can see *why* the explanation is supposedly good.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your valuable comments. We hope that the following reply could address your concerns!\n\n\n>**W1: Concerns about the Introduction and the missing related work [1-5].**\n\nThanks for bringing this point to us. Following your suggestions, we have implemented the following changes in the response and our revision:\n\n1. **Introduction & Related Work Organization**. The 'Introduction' section has been revamped to streamline previous studies. The 'Related Work' section has been added into the main paper.\n\n2. **Literature View**. We appreciate your introduction to references [1-5] and have incorporated them into the 'Related Work' section. These papers primarily classify current metrics into four categories: accuracy, faithfulness, stability, and fairness. Notably, OAR align with the 'faithfulness' metric.\n\n3. **Evaluation Metric & Dataset**. Drawing from references [1-5], we've specifically adopted the contemporary faithfulness metric, GEF [3], and the latest synthetic dataset, SHAPEGGEN [3], to enhance our paper. We utilized these resources to perform additional experiments, with the outcomes presented in the table below and Table 1 of the main paper. \n\n||SHAPEGGEN|TR3|MUTAG|MNIST|BA3|\n|:-:|:-:|:-:|:-:|:-:|:-:|\n|GEF|0.800|0.734|0.800|0.934|0.734|\n|SimOAR|0.800|0.867|0.800|0.934|0.934|\n|OAR|0.867|0.934|1.000|0.934|1.000|\n|||||\n\n> **W2: [6] might be worth discussing/comparing to.**\n\nThanks for your suggestion. We have incorporated a discussion on CoGE [6] in our revision. \n\nIn essence, although CoGE can determine if a subgraph is associated with the OOD class, it fails to provide a precise score delineating the OOD degree, making it coarser compared to OAR. \n\nMoreover, CoGE is more aligned with explanation methodologies rather than functioning as an evaluation framework, which is why we did not select it as a baseline. \n\nWe hope this classification addresses your concerns!\n\n> **W3: Concerns about transferring the trust problem from the GNN to the VGAE.**\n\nThank you for highlighting this important aspect. While we recognize the concerns of transferring trust to VGAE with OAR, we assert that its impact is relatively minimal for several reasons:\n\n1. **VGAE-guided OAR**. Indeed, the trust and accuracy of VGAE is important to evaluate the explanation faithfully. However, we are optimistic that as generative research (e.g., diffusion models) advances, emerging generation ability will mitigate this limitation.\n\n2. **VGAE-free SimOAR**. Our streamlined variant, SimOAR, sidesteps VGAE altogether. Instead, it utilizes transparent heuristics for perturbation generation. This strategic choice inherently counteracts the transfer of trust issues from GNN to VGAE.\n\n3. **Performance Insights**. As Table 1 shows, SimOAR is slightly worse or on par with OAR, but outperforms all baselines. This underscores the idea that VGAE's influence is minimal.\n\nWe're grateful for your insightful suggestions, and we will incorporate them into the reversion.\n\n>**Q1: Expand the setting of user study following checklist.**\n\nThanks for your suggestions. We have detailed the setting following checklist and incorporated it into our revision:\n\n1. **Instructions.** Each participant was asked to check 5 groups of graphs as shown in Appendix D and answer which subgraph is best preserves digital information.\n2. **Risks.**  Our user study do not have any risks.\n3. **Wage.** The participants in our user study were volunteers. \n\n>**Q2: How to creat the MNIST-sp?**\n\nWe created the MNIST-sp according to [1]. Specifically, the node features are the pixels' values and the  pixels' centers. Edges are the spatial distance between the superpixel centers.\n\n*[1] Geometric deep learning on graphs and manifolds using mixture model cnns. CVPR. 2017*\n\n>**Q3: Does the attacks allow adding and deleting nodes?**\n\nNo, our attacks are only allowed to happen in the given adjacency matrix. We will explore the addition/deletion of nodes in future work.\n\n>**Q4: If OAR would benefit from penalizing surplus nodes.**\n\nFollowing your recommendations, we integrated the L1-norm for explanation size control. Experiments exhibted in the following and the Table 1 of the main paper, verify that the Component you suggested indeed enhances our methods.\n\n||TR3|MUTAG|MNIST|BA3|\n|:-:|:-:|:-:|:-:|:-|\n|SimOAR|0.867|0.800|0.934|0.934|\n|SimOAR+L1|**0.934**$\\uparrow$|0.800|0.934|**1.000**$\\uparrow$|\n|OAR|0.934|1.000|0.934|1.000|\n|OAR+L1|0.934|1.000|**1.000**$\\uparrow$|1.000|\n|||||\n\n>**Q5: Could OAR work for node classification?**\n\nYes, it can. Here are the results on four node classification datasets following [1]:\n\n||BA-Shapes|BA-Community|Tree-Cycles|Tree-Grid|\n|:-:|:-:|:-:|:-:|:-:|\n|RM|0.312|0.321|0.295|0.411|\n|DSE|0.406|0.377|0.343|0.384|\n|OAR|**0.542**|**0.560**|**0.489**|**0.440**|\n|SimOAR|0.527|0.535|0.471|0.431|\n|||||\n\n*[1] GNNExplainer: Generating Explanations for Graph Neural Networks. NIPS 2019*\n\n>**Q6: Can we do something simpler than VGAE, like spectra?**\n\nYes, we can. Spectra is the commonly used techniques in anomaly detection. Considering their typically work for nodes classification, we use the Manhattan distance between the spectrum as the OOD degree and exhibit the results:\n\n||MUTAG|BA3|TR3|MNIST|\n|:-:|:-:|:-:|:-:|:-:|\n|OAR|0.567|0.503|0.483|0.455|\n|SimOAR+Spectra|0.511|0.459|0.449|0.433|\n|||||\n\nBased on these we find that the performance of spectra is inferior to that of VGAE. \n\n>**Q7: Could BA3 and TR3 influence experiments?**\n\nThanks for your concern. We believe that they will not. Here are two reasons: \n\n- First, although ground truth in BA3 and TR3 might not conform to the decision-making process exactly, they contain sufficient discriminative information to help justify the quality of explanations. \n\n- Second, even after excluding the potentially problematic datasets BA3 and TR3, we still have other datasets like MUTAG and MNIST-sp, and our methods also achieved the best performance on these datasets across various settings.\n"}, {"review_id": "KzIw1x6dZc", "reviewer": "Reviewer_uvv7", "summary": "The paper proposes a novel evaluation metric called OOD-resistant Adversarial Robustness (OAR) to address the issue of assessing the credibility of explanations provided by graph neural networks (GNNs). The paper criticizes existing evaluation methods that fail to consider out-of-distribution (OOD) data and can produce inconsistent results. OAR overcomes these limitations by calculating the robustness of explanatory subgraphs under attack and incorporating an OOD reweighting block. The paper also introduces a simplified version of OAR called SimOAR for more efficient evaluation of large datasets. Experimental results show that OAR outperforms current evaluation metrics and demonstrates consistency with metrics like Precision, Recall, and Human Supervision .", "questions": "Listed in Weakness.", "limitations": "Yes.", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1. This work tackles an important research gap on evaluating the explanation for GNN.\n2. The paper is well-written and easy to follow. \n2. The authors conduct experiments, and the results demonstrate the advantage of their proposed method.", "weaknesses": "1. Figure 1 is kind of hard to follow. It could be better if authors can refine it.\n2. Some experiment setting is missing. For example, what is the setting of the GAE? What is the number of the generated graph?\n3. Lack of related work, and some important reference is missing. For example, the authors could add a section introduce the explanation methods for GNN according to [1].\n\n[1]  Zhang, He, et al. \"Trustworthy graph neural networks: Aspects, methods and trends.\" arXiv preprint arXiv:2205.07424 (2022).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "*Dear Reviewer uvv7:*\n\n*We gratefully thank you for your valuable comments! Here we meticulously give point-by-point responses to your comments. Hope that our responses could address your concerns!*\n\n>**W1: Figure 1 is kind of hard to follow. It could be better if authors can refine it.**\n\nThanks for your concern. Following your suggestion, we have made significant refinements to improve its clarity. The refined version provides a more coherent representation of the information it conveys, as shown in the new added *Supplementary PDF*.\n\nThe following are some specific modifications: \n\n- We have extracted the common parts of Figure 1 (a), Figure 1 (b), and Figure 1 (c), and placed them together to avoid repetition. We have also added appropriate textual descriptions to make them easier to understand. \n\n- We have increased the font size to match the text in the main body. \n\n- We have provided detailed illustrations of Figure C (our algorithm OAR) to demonstrate the process of our algorithm more intuitively and smoothly.\n\nWe hope that the revised Figure 1 now effectively supports the content and contributes to the comprehension of our research.\n\nThanks again for your valuable suggestion!\n\n>**W2: Some experiment setting is missing. For example, what is the setting of the GAE? What is the number of the generated graph?**\n\nThanks for your concern. For the setting of the GAE, please refer to **Line 138-140** in Appendix C;  for the number of the generated graph, please refer to **Line 160-161** in Appendix C, where we point out that for BA3, TR3, and MUTAG, the number of perturbed subgraphs $N_{perturb}$ is 20, while for MNIST-sp, the number of perturbed subgraphs $N_{perturb}$ is 50 owing to its large size.\n\nWe agree with your concern about the absence of these important parameters in the main paper. Hence, following your suggestion, **we have moved them from the Appendix C to the Experimental Setup** section in the main paper of the revised version. We hope that this modification could enhance the readability and reproducibility of our paper.\n\n>**W3: Lack of related work, and some important reference is missing. For example, the authors could add a section introduce the explanation methods for GNN according to [1].**\n\nThanks for your concern. Based on your recommendation, we have included the missing reference [1] within the Related work section in the main paper, ensuring proper attribution to the original work. \n\nFurthermore, following your suggestion, we have introduced the current trustworthy GNNs from six aspects (robustness, explainability, privacy, fairness, accountability, and environmental well-being) in the Related Work following [1].\n\nBy incorporating these suggested changes, we believe that we have enriched the manuscript and provided readers with a more comprehensive understanding of the explanation methods for GNN.\n\n[1] Zhang, He, et al. \"Trustworthy graph neural networks: Aspects, methods and trends.\" arXiv preprint arXiv:2205.07424 (2022).\n\n*Thank you for drawing our attention to these important aspects. Your valuable feedback has greatly enhanced the quality of our research. If you have any further **recommendations** or require additional **clarification**, please do not hesitate to let us know.*\n\n*Best,*\n\n*Authors*\n"}, {"review_id": "WFowJ1OlBD", "reviewer": "Reviewer_vGHJ", "summary": "This paper presents a new metric, OOD-resistant Adversarial Robustness (OAR), for evaluating post-hoc explanation methods for Graph Neural Networks (GNNs). Inspired by adversarial robustness, OAR performs random perturbations on the complementary part of the explanation result, reducing the impact of the Out-Of-Distribution (OOD) issue common in previous removal-based metrics and ensuring consistency with GNNs' behavior compared to generation-based methods. The authors further introduce an OOD reweighting block, which measures the OOD score of each perturbed sample, allowing for the marginalization of OOD instances, and the OOD score is assigned via the reconstruction loss of a Variational Graph Auto-Encoder (VGAE) pre-trained by each dataset, inspired by graph anomaly detection methods. Extensive evaluations and ablation studies demonstrate that OAR aligns more closely with the ground truth.\n\n\n\n\n\n\n \n", "questions": "- I am not quite sure if the usage of \"adversarial\" and \"attack\" in OAR would be clear. I thought there would be some adversarial training in OAR but in fact the authors just got inspiration from them and OAR does not really do adversarial things.\n\n- How is the metric RM calculated mathematically? Is it fidelity? Can the authors provide its formulation?", "limitations": "- This paper focuses on the explanation of graph-level tasks. How would this generalize to other types of tasks as a metric?\n- There are works showing post-hoc explanation methods are always suboptimal in terms of finding label-relevant patterns and therefore proposing self-explainable models and pretrain-finetuning framework, e.g., GSAT. This may limit the future impact of OAR if it is only for post-hoc methods. Can the idea in OAR help self-explainable methods?\n", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- This work summarizes and addresses a critical and emerging issue in post-hoc explanation methods for GNNs, and the proposed metric is intuitive and can mitigate issues that may happen in previous removal-based and generation-based methods, offering significant benefits to the research community.\n- The authors conduct extensive experiments, demonstrating the potential of the proposed metric as a superior evaluation tool for post-hoc explanation methods.\n- It is interesting to see OOD score can be measured using graph anomaly detection methods (and that works).\n- This paper is well-written and well-motivated.", "weaknesses": "- As an evaluation metric, OAR introduces an additional component that requires training on the original dataset used for the GNN. This process makes things complex, time-consuming, and may accumulate errors, making it tricky for different research groups to compare methods across various datasets.\n\n- SimOAR somewhat addresses the above concern, but it does so at the expense of performance. From current experiments (w/ six backbone methods), the performance degradation seems to be significant.\n\n- Though I am generally satisfied with evaluating six backbone explanation methods, the inclusion of more baselines would provide a more comprehensive statistical overview, given that this paper aims to introduce a metric for future community use. It would also be beneficial to include different types of post-hoc methods, such as decomposition, surrogate, and generation-based methods, among others.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "*Dear Reviewer vGHJ:*\n\n*Thank you for the thoughtful feedback! Your constructive criticism has been invaluable in refining our work. Below, we give point-by-point responses. Hope our responses could address your concern!*\n\n>*W1 & W2: Concern about the training process in OAR, while SimOAR addresses the above concern but degrades the performance.*\n\nThanks for your concern. We agree that the training process of OAR is complex and time-consuming. In fact, we have delved into this issue in **Appendix F** (Line 175-185) of the main paper. Specifically, \n\n1. We believe that  learning distribution information from this training process  is inevitable to address the problem of OOD. Here is the reason: \n\n    - Explanation (which is indeed the process of sampling subgraphs from inputs) would inevitably introduce the risk of OOD. While to measure this OOD, it is necessary to obtain the distribution information.\n\n2. Although SimOAR is a compromise which degrades the performance, we believe that the experimental results of OAR and SimOAR precisely demonstrate the potential optimization space. Concretely, **OAR and SimOAR represents two extremes:** OAR accurately acquires distribution to combat OOD, while SimOAR completely abandons this acquisition to improve efficiency. It naturally inspired the future optimized directions: \n    - On the one hand, we can find a balance between accuracy (OAR) and speed (SimOAR) to adapt to different tasks.\n    - On the other hand, we can explore more efficient generative algorithms that require less acquisition of distribution information, such as diffusion models, to optimize both accuracy and speed simultaneously.\n\n>*W2: It would also be beneficial to include different types of post-hoc methods.* \n\nThanks for your suggestion. Following your guidance, we have conduct additional experiments across three types of post-hoc methods to validate the effectiveness of our OAR. Limited by the short rebuttal time, we only select one method for each type (*i.e.*, decomposition: **GNN-LRP**, surrogate: **PGMExplainer**, generation: **XGNN**) on BA3 and MNIST-sp. Moreover, we noticed that you are interested in **GSAT** in the following comments, hence, we also conduct the **GSAT** (in its post-hoc mode).\n\nHere are the results (corresponding to Figure 3 in the main paper): \n\n|||BA3|||\n|:-:|:-:|:-:|:-:|:-:|\n||PGMExplainer|GNN-LRP|XGNN|GSAT|\n|RM|0.341|0.355|0.307|0.386|\n|DSE|0.409|0.412|0.367|0.370|\n|OAR|**0.488**|**0.525**|**0.505**|**0.463**|\n|SimOAR|0.463|0.500|0.482|0.432|\n||||||\n\n|||MNIST-sp|||\n|:-:|:-:|:-:|:-:|:-:|\n||PGMExplainer|GNN-LRP|XGNN|GSAT|\n|RM|0.302|0.323|0.287|0.342|\n|DSE|0.314|0.340|0.341|0.317|\n|OAR|**0.546**|**0.583**|**0.520**|**0.554**|\n|SimOAR|0.542|0.548|0.499|0.530|\n||||||\n\nWe will continue to conduct more complete experiments across other post-hoc methods and add them into the reversion.\n\n>*Q1: Concern about the usage of  \"adversarial\" and \"attack\".*\n\nWe are sorry for making you confused. Specifically, our adversarial robustness mean that “How adversarial are random perturbations against the original data distribution, which are measured by OOD score”?\n\nHere are two more reasons why we named our attack as **adversarial attack**: \n\n- First, the starting point of our methods is finding the minimum perturbation leading to the wrong prediction (Line 128-132 in the main paper). However, this target is proved to be hard to reach and sometimes even intractable in the scenario given in the paper (Line 144-151). Thus, we transfer to approximate it from its dual perspective. That is, calculating the largest changes of outputs under the attacks. Hence, **our approach is essentially derived from the adversarial attack.**\n\n- Moreover, here are the imposed objective and the target of the *adversarial attack* and *our attack in OAR*, which are similar with each other:\n\n||Objective|Target|\n|:-:|:-:|:-:|\n|Adversarial Attack|**selected part of input** (*which is selected by the attack algorithm*)|**perturb output as much as possible** (*until flip the outputs*)|\n|Attack in Our OAR|**selected part of input** (*which is selected by the explanations*)|**perturb output as much as possible** (*to see the robustness*)|\n||||\n\n>*Q2: How is the metric RM calculated mathematically?*\n\nIn our paper, Removal-based metric (RM) is employed to quantify the fidelity of the explanations. More formally, for an input graph $G$ and an explanation (subgraph) $G_s$, RM believes that a good explanation should have a large $f(G)-f(G_s)$, where $f$ is the GNN.\n\n>*L1: How would OAR generalize to other tasks?*\n\nThanks for your concern. Following your comments, we have conducted experiments across several prevalent **node classification** datasets following [1]. \n\nHere are the results:\n\n||BA-Shapes|BA-Community|Tree-Cycles|Tree-Grid|\n|:-:|:-:|:-:|:-:|:-:|\n|RM|0.312|0.321|0.295|0.411|\n|DSE|0.406|0.377|0.343|0.384|\n|OAR|**0.542**|**0.560**|**0.489**|**0.440**|\n|SimOAR|0.527|0.535|0.471|0.431|\n||||||\n\nAccording to these results, we can find that our OAR and SimOAR can work well for the task of node classification.\n\n*[1] GNNExplainer: Generating Explanations for Graph Neural Networks. NIPS 2019*\n\n>*L2: Can the idea in OAR help self-explainable methods?*\n\nThanks for your concern. Yes, it can. The evaluation target of OAR is the explanation (subgraph). Hence, any algorithm which generate explanations can be evaluated by OAR. \n\nFollowing your concern, we have conducted the experiments on GSAT:\n\n|||GSAT|||\n|:-:|:-:|:-:|:-:|:-:|\n|| BA3 | MUTAG | TR3 |MINST|\n|RM|0.376|0.381|0.402|0.337|\n|DSE|0.411|0.425|0.417|0.319|\n|OAR|**0.613**|**0.590**|**0.585**|**0.606**|\n|SimOAR|0.598|0.572|0.552|0.581|\n||||||\n\nThese results validate that our OAR can help self-explainable methods.\n\n*Once again, we sincerely appreciate your time and effort in reviewing our paper. Your criticism has been invaluable in refining our work, and we are more than happy to add clarifications to address your concerns!*\n\n*Best,*\n\n*Authors*"}]

Author rebuttal:
Dear Reviewers:

We gratefully thank you for your valuable comments! We were encouraged to hear that our work has **clear and well-written presentations** (by all Reviewers), **well-designed and interesting technical contributions** (by Reviewer QMrv and vGHJ), **extensive and sufficient experiments** (by all Reviewers), which **addresses a critical and emerging issue** to the research community (by Reviewer uvv7 and vGHJ). 

Here we meticulously give point-by-point responses to your comments, and further add the additional experiments and figures into the one-page supplementary PDF. Especially, we have taken measures to enhance the structure of the Introduction and Related Work section, and provided a more rigorous definition of our methods. Furthermore, we have provided a more detailed description of our experimental settings and included a wider range of representative baselines and datasets for conducting additional experiments. We hope that our responses adequately address all your concerns and meet the expectations of the conference committee.

Once again, we sincerely appreciate your time and effort in reviewing our paper. Your constructive criticism has been invaluable in refining our work, and we are more than happy to add clarifications to address any additional recommendations and reviews from you!

Best, 

Authors 


Meta-review: The reviewers are all excited about this work and unanimously recommended acceptance. 

Among all strengths that reviewers mentioned, this paper is particularly well motivated and focuses on a very important problem, tackling a gap between on evaluating the explanation for GNN. The detailed discussion on the drawbacks of different evaluation protocols is also appreciated. The experimental study is solid, with user study and diverse criteria.
Decision: Accept (oral)