GNNX-BENCH: Unravelling the Utility of Perturbation-based GNN Explainers through In-depth Benchmarking
Authors: Mert Kosan
Samidha Verma
Burouj Armgaan
Khushbu Pahwa
Ambuj Singh
Sourav Medya
Sayan Ranu
Venue: ICLR 2024 poster (2024)
Keywords: graph neural network explanations
factual explanations
counterfactual explanations
Primary area: datasets and benchmarks

Abstract: Numerous explainability methods have been proposed to shed light on the inner workings of GNNs. Despite the inclusion of empirical evaluations in all the proposed algorithms, the interrogative aspects of these evaluations lack diversity. As a result, various facets of explainability pertaining to GNNs, such as a comparative analysis of counterfactual reasoners, their stability to variational factors such as different GNN architectures, noise, stochasticity in non-convex loss surfaces, feasibility amidst domain constraints, and so forth, have yet to be formally investigated. Motivated by this need, we present a benchmarking study on perturbation-based explainability methods for GNNs, aiming to systematically evaluate and compare a wide range of explainability techniques. Among the key findings of our study, we identify the Pareto-optimal methods that exhibit superior efficacy and stability in the presence of noise. Nonetheless, our study reveals that
all algorithms are affected by stability issues when faced with noisy data. Furthermore, we have established that the current generation of counterfactual explainers often fails to provide feasible recourses due to violations of topological constraints encoded by domain-specific considerations. Overall, this benchmarking study empowers stakeholders in the field of GNNs with a comprehensive understanding of the state-of-the-art explainability methods, potential research problems for further enhancement, and the implications of their application in real-world scenarios.

Published as a conference paper at ICLR 2024
GNNX-BENCH: UNRAVELLING THE UTILITY OF PERTURBATION-BASEDD GNN EXPLAINERS THROUGH
IN-DEPTH BENCHMARKING
Mert Kosan 1x| Samidha Verma Burouj Armgaan", Khushbu Pahwa", Ambuj Singh Sourav Medya', Sayan Ranu²
University of California, Santa Barbara
Indian Institute of Technology, Delhi Rice University
University of Illinois, Chicago*
mertkosan@ com, kp660rice, edu, ambujacs ucsb.edu, medyaQuica (sami dha. verma, burouj. armgaan, sayanranu @cse. aitddac.....
ABSTRACT
Numerous explainability methods have been proposed to shed light the inner workings GNNS. Despite the inclusion of empirical evaluations in all the proposed algorithms. the interrogative aspects of these evaluations lack diversity. As a result, various facets of explainability pertaining to GNNS, such comparative analysis of counterfactual reasoners, their stability to variational factors such as different GNN architectures, noise, stochasticity in non-convex loss surfaces, feasibility amidst domain constraints, and so forth, have yet be formally investigated. Motivated by this need, we present a benchmarking study on perturbation- based explainability methods for GNNs, aiming to systematically evaluate and compare a wide range of explainability techniques. Among the key findings of our study, we identify the Pareto-optimal methods that exhibit superior efficacy and stability in the presence of noise. Nonetheless, our study reveals that algorithms are affected by stability issues when faced with noisy data. Further- more, have established that the current generation of counterfactual explainers often fails to provide feasible recourses due to violations of topological constraints encoded by domain-specific considerations. Overall, this benchmarking study empowers stakeholders in the field of GNNS with a comprehensive understanding the oftte-of-thheatt explainability methods, potential research problems for further enhancement, and the implications of their application in real-world scenarios.
INTRODUCTION AND RELATED WORK
GNNs have shown sate-of-the-an performance in various domains including social networks Man- chanda et al. (2020); Chakraborty et al. (2023), biological sciences Ying et al. (2021) 1); Rampášek et al.
(2022): ; Ran an al. (2022), modeling of physical systems Thangamuthu et al. (2022); Bhattoo et al.
l) and traffic modeling Gupta et al. (2023) Jain et al. 2021); Wu et al. (201) Li al. (2020). Unfortunately. like other deep-learning models, GNNS are black boxes due to lacking transparency and interpretability. This lack of interpretability is significant barrier to their adoption in critical domains such as healthcare, finance, and law enforcement. In addition, the ability to explain predictions is critical towards understanding potential flaws in the model and generate insights for further refinement. To impart interpretability to GNNS, several algorithms to explain the inner workings of GNNS have been proposed. The diversified landscape of GNN explainability research is visualized in Fig. We summarize each of the categories below:
(2022 2023 Bishnoi et al. (2023), event detection Cao et al. (2021); Kosan et al. (2021)
Model-level or global explanations are concerned with the overall behavior of the model and search for patterns in the set of predictions made by the model. XGNN Yuan et al. (2020). Gi.G-Explainer Azzolin et al. (2023), Xuanyuan al. Xuanyuan al. (002)). GCFExplainer Huang et al. 2023).
Model-level:
Both authors contributed equally to this research.
Work done prior joining Visa Inc.

---

Published as a conference paper at ICLR 2024
Graph Network Explanations
Instance Invel
Model-level
GradientsFeatures
Decormposiion
Perturhation
Surrogall
CAM
GNNExplaire
HC-Explinner
CF-GNNExptaii
Grophiimee
GCF Explainer
SA
Excilatioo BP
PGDxpaanns
oF?
CLEAR
Exploiner
Counterfactual
Crwo-CAM
GNN-URP
Fachual
Subgraphx
Counteriactual
Factual
Countetfccuul
PoM-Esspanee
Factual
Muarytonn
Factual
Fictual
TAGExdla
Fartual
Figure 1: Structuring the space of the existing methods on GNN explainability,
Instance-level or local explainers provide explanations for specific predictions made by model. For instance, these explanations reason why a particular instance input is classified or predicted a certain way.
Instance-level:
Gradient-based: They follow the idea of the rate of change being represented by gradients. Additionally, the gradient of the prediction with respect to the input represents the prediction sensitivity to the input. This sensitivity gives the importance scores and helps in finding explanations. SA and Guided-BP Baldassarre & Azizpour (2019), Grad-CAM Pope et al. (2019).
Decomposition-basee They consider the prediction of the model to be decomposed and distributed backward in layer-by-laye fashion and the score of different parts of the input can be construed its importance the prediction. CAM and Excitation- Pope et al. (2019), GNN-LRP Schnake et al. T202T)
Perturbation-bassed They utilize input perturbations to identify important subgraphs serving as factual or counterfactual explanations. GNNExplainer Ying et al. (2019b), PGExplainer Lut Luo et al.
2020)) SubgraphX Yuan et al. (2021). GEM Lin et al. (2021a), IAGExplainer Xie et al. (2022).
CF4 ln et al. (2022). RCExplainer Bajaj et al. (2021). CF-GNNeellainer Lucie et al. (2022).
CLEAR Ma et al. (2022), Shan et al. (2021 y Abrate & Bonehi (202T); Wellawatte et al. (2022)
Surrogate: They
the generic intuition that in a smaller range of input values, the relationship
between input and output can be approximated by interpretable functions. The methods fit simple
and interpretable surrogate model in the locality of the prediction. GraphLime Huang al. (2022).
Relex Zhang et al. (2021). PGM--xpplaiie Vu & Thai (2020).
The type of explanation offered represents crucial component. Explanations can be broadly classified into two categories: factual reasoning and counterfactual reasoning.
Factual explanations provide insights into rationale behind a specific prediction by identifying the minimal subgraph that is sufficient yield the same prediction the entire input graph.
Counterfactual explanations elucidate why a particular prediction was not made by presenting alternative scenarios that could have resulted in different decision. In the context of graphs, this involves identifying the smallest perturbation to the input graph that alters the prediction of the GNN, Perturbations typically involve the removal of edges modifications node features.
1.1 CONTRIBUTIONS
In this benchmarking study, we systematically study perturbation-basee factual and counterfactual explainers and identify their strengths and limitations in terms of their ability to provide accurate, meaningful, and actionable explanations for GNN predictions. The proposed study surfaces new insights that have not been studied existing benchmarking literature Amara et al. (2022): A Agarwal et al. (See. App. J for details). Overall, we make the following key contributions:
Comprehensive evaluation encompassing counterfactual explainers: The benchmarking study encompasses seven factual explainers and four counterfactual explainers. The proposed work is the first benchmarking study on counterfactual explainers for GNNS.
Novel insights: The findings of our benchmarking study unveil stability noise and variational factors and generating feasible counterfactual recourses as two critical technical deficiencies that naturally lead us towards open research challenges.
Codebase: As by-product, a meticulously curated, publicly accessible code base is provided (https://github. com/idea aaaeeaaaiiiiggii hidd/gnn-x benchh))
2

---

Published as a conference paper at ICLR 2024
Table Key highlights of the perturbation factual methods. The "NFE" column implies Node Feature Explanation. "GC" and "NC" indicate whether the dataset is used for graph classification and node classification respectively.
Method
Subgraph Extruction Strutegy
Scoring function
Construints
NFE
Tank
Nature
GNNExplainer
Continuous relaxation
Mutual Information
Size
Yes
GC+NC
Transductive
PGExplainer
Parameterized edge selection
Mutual Information
Size, Connectivity
No
GC+NC
Inductive
TAGExplainer
Sampling Granger Causalty+Auboeeuudde Autoencoder
Mutual Information
Size, Entropy
No
GC+NC Inductive
GEM
Contribution
Connectivity
No
GC+NC Inductive
SubgraphX
Monte Carlo Search
Shapley Value
Size, Counectivity
Transductive
2 PRELIMINARIES AND BACKGROUND
We use the notation G = (V, E) to represent a graph, where V denotes the set of nodes and & denotes the set of edges. Each node v, V is associated with feature vector 2; E IRd. We assume there exists a GNN & that has been trained on 9 (or a set of graphs).
The literature on GNN explainability has primarily focused on graph classification and node classifi- cation, and hence the output space is assumed to categorical. In graph classification, we are given set of graphs as input, each associated with class label. The task of the GNN + is to correctly predict this label. In the case of node classification, class labels are associated with each node and the predictions are performed
nodes. In a message passing GNN of l layers, the embedding on a node is a function of its E-hop neighborhood. We use the term inference subgraph to refer to this é-hop neighborhood. Henceforth, we will assume that graph refers the inference subgraph for node classification. Factual and counterfactual reasoning over GNNS are defined as follows.
Definition (Perturbation-bue based Factual Reasoning) Let & be the input graph and (g) the pre- diction on G. Our task is to identify the smallest subgraph Gs S G such that ((G) (GGs).
Formally, the optimization problem expressed as follows:
Gs arg
min G'Cs, 4(G) ((G)) ||(()))
Here, AlGs) denotes the adjacency matrix Gs. and ||(G))) is its LI norm which is equivalent to the number of edges. Note that if the graph is undirected, the number of edges is half of the LI norm. Nonetheless, the optimization problem remains the same.
While subgraph generally concerns only the topology of the graph, since graphs in our case may be annotated with features, some algorithms formulate the minimization problem in the joint space of topology and features. Specifically, in addition to identifying the smallest subgraph, we also want to minimize the number of features required to characterize the nodes in this subgraph.
Definition 2 (Counterfactual Reasoning) Let G be the input graph and (G) the prediction on G. Our task is introduce the minimal set of perturbations to form new graph G such that (G)) # (('"). Mathematically, this entails to solving the following optimization problem.
g arg
min
dūst(G)
G'EG, (G)))
where dist(G G') quantifies the distance between graphs G and G and G is the set of all graphs one may construct by perturbing G. Typically, distance is measured as the number of edge perturbations while keeping the node set fixed. In case multi-class classification, one wishes to switch to target class label(s), then the optinization objective is modified as G* = arg mingres, eG, #(G"== dist(g,9) G"), where C is the set of desired class labels.
2.1 REVIEW OF PERTURBATION BASED GNN REASONING
Factual (Yuan et al. 22022; Kakkad al. 2023)): : The perturbation schema for factual reasoning usually consists of two crucial components: the subgraph extraction module and the scoring function module. Given an input graph G. the subgraph extraction module extracts a subgraph G.; and the scoring function module evaluates the model predictions ((G.) for the subgraphs, comparing them with the actual predictions (G). For instance, while GNNExplainer Ying et al. (2019a) identifies an explanation in the form of subgraph that have the maximum influence the prediction, PG- Luo explainers, TAGEEppaiinrr Xie et al. (2022) takes two-step approach where the first step has
Explainer Luo et al. (2020) assumes the graph to be a random Gilbert graph. Unlike the existing
3

---

Published as a conference paper at ICLR 2024
Table 2:
Key highlights of the counterfactuals methods. "GC" and "NC" indicate whether the dataset is used for graph classification and node classification respectively.
Method
Explanation Type
TTask
Targel/Method
Nature
RCIxxpliner Bajui et al. 202. CF Tan
Instance level
GC+NC
Neural Network
Inductive
Instance level
GC
Original graph
Transductive
CF-GNNEXPEann Cisieer
2022
Instance level
NC
Inference subgraph
Transductive
CLEAR Ma af
Instance level
GC+NC
Variational Autoencoder
Inductive
embedding explainer trained using a self-supervised training framework without any information of the downstream task. On the other hand, GEM Lin et al. (2021a) uses Granger causality and an autoencoder for the subgraph extraction strategy where as SubgraphX Yuan et al, (2021) employes a monte carlo tree search. The scoring function module uses mutual information for GNNExplainer, PGExplainer, and TAGExplainer. This module is different for GEM and SubgraphX, and uses casual contribution and Shapley value respectively. Table | |ummmarizes the key highlights.
Counterfactual (Yuan et al. )2022)): The four major counterfactual methods are JF-GNNExplainer Lucic et al. (2022), CF Tan et al. 2022). RCExplainer Bajaj et al. (2021) J. and CLEAR Ma et al. (2022). They are instance- level explainers and apply to both graph and node classification tasks except for CE-GNNExplainer which is only applied to node classification. In terms of method, CF-GNNExplainer aims to perturb the computational graph by using binary mask matrix. The corre- sponding loss function quantifies the accuracy of the produced counterfactual and captures the distance (or similarity) between the counterfactual graph and the original graph, whereas, CF2 Tan al. (2022) extends this method by including a contrastive loss that jointly optimizes the quality of both the factual and the counterfactual explanation. Both of the above methods are transductive. As an inductive method, RCExplainer Bajaj et al. (202T), aims to identify a resilient subset of edges to remove such that it alters the prediction of the remaining graph while CLEAR Ma et al. (2022) generates coun- terfactual graphs by using graph variational autoencoder. Table summarizes the key highlights.
BENCHMARKING FRAMEWORK
In this section, we outline the investigations we aim to conduct and the rationale behind them. The mathematical formulation of the various metrics are summarized in Table B Comparative Analysis: We evaluate algorithms for both factual and counterfactual reasoning and identify the pareto-optimal methods. The performance is quantified using explanation size and sufficiency Tan et al. (2022). Sufficiency encodes the ratio of graphs for which the prediction derived from the explanation matches the prediction obtained from the complete graph Tan et al. (2022). Its value spans between 0 and 1. For factual explanations, higher values indicate superior performance. while in counterfactual lower is better since the objective is to flip the class label.
Stability: Stability of explanations, when faced with minor variations in the evaluation framework, is crucial aspect that ensures their reliability and trustworthiness. Stability is quantified by taking the Jac- card similarity between the set of edges in the original explanation vs. those obtained after introducing the variation (details in In order to evaluate this aspect, we consider the following perspectives:
Perturbations in topological space:
If we inject minor perturbations to the topology through a small number of edge deletions or additions, then that should not affect the explanations.
Model parameters: The explainers are deep-learning models themselves and optimize a non- convex loss function. As consequence of non-convexity, when two separate instances of the explainer starting from different seeds are applied to the same GNN model, they generate dissimilar
Table 3: The various metrics used to benchmark the performance of GNN explainers.
Sufficiency($S- El =(01)))
(G' , ...., G"): graph
[C]
g6: explanation subgraph of gf
Neecssity(A) >:19 10002)
Gg (G). 03..53..... G3 explanation set.
[+]
R G - gb
Stabilit(Ex. [Ex
R [R² R....... R= residual graph set. +. 2s. bhg the models trained on G. Gs. R. All models are trained on the same labels. o(G))) the pretictionn of the model on G (B): the test accuracy of d:
Reproducibility" (R )
ACCrv
ACC(())
Reproducibility" (R ) aCC!9
4

---

Published as a conference paper at ICLR 2024
explanations. Our benchmarking study investigates the impact of this stochasticity the quality and consistency of the explanations produced.
Model architectures:
cesssag-passiigg GNNS follow similar computation framework, differing mainly in their message aggregation functions. We explore the stability of explanations under variations in the model architecture.
Necessity: Factual explanations are necessary if the removal of the explanation subgraph from the graph results in counterfactual graph (i.e., flipping the label).
Reproducibility: We measure two different aspects related to how central the explanation is towards retaining the prediction outcomes. Specifically, Reproducibility" measures if the GNN is retrained on the explanation graphs alone, can it still obtain the original predictions? On the other hand, Reproducibility" measures if the GNN is retrained on the residual graph constructed by removing the explanation from the original graph, can it still predict the class label? The mathematical quantification of these metrics is presented in Fig. 3 Feasibility: One notable characteristic of counterfactual reasoning is its ability to offer recourse options. Nonetheless, in order for these recourses to effective, they must adhere to the specific domain constraints. For instance, in the context of molecular datasets, the explanation provided must correspond to a valid molecule. Likewise, if the domain involves consistently connected graphs, the recourse must maintain this property. The existing body of literature counterfactual reasoning with GNNS has not adequately addressed this aspect, gap we address in our benchmarking study.
Table 4: The statistics of the datasets. Here, "F" and "CF" in the column " "X-type" indicates whether the dataset is used for Factual or Counterfactual reasoning. "GC" and "NC" in the Task column indicates whether the dataset used for graph classification and node classification respectively.
#Graphs
#Nodes
#Edges
#Features
#Classes
Task
FIF
MUTAGENICITY Riesen & Bunke 2006
Kazius al.
2005
4337
131488
133447
14
GC
F+CF
PROTFINS Barywardt al 2005
Dobson & Doip 2005
1113
43471
81044
32
GC
F+CF
MMBB
Vishwanathan
1000
19773
96531
136
GC
F+CF
AIDS Ivanoy el al 2019
2000
31385
32390
42
2
GC
F+CF
20/9
188
3371
3721
GC
F+CF
NC11 Wale al 2005
4110
122747
132753
37
2
GC
GRAPH-SSTEL 2 Yuznn
70042
714325
6442283
768
GC
Dobson & Dong 2003
1178
334925
843046
89
2
GC
REDDIT-B Fantrost Vishwanathan
2015
2000
859254
995508
3063
GC
F
DOBG-MOLIIE ITV AAlmiI Cerl 2013
41127
1049163
2259376
GC
TREE-CYCLES Yu 2019
871
1950
10
NC
CF
TREE-GRI Yilgg ar
2019
3410
NC
BA DA-SHAPES T Ting aral 20196
700
4100
10
NC
CF
EMPIRICAL EVALUATION
In this section, we execute the investigation plan outlined in 3 Unless mentioned specifically, the base black-box GNN is GcN. Details of the up (e.g., hardware) are provided in App. A Datasets: Table 4 showcases the principal statistical characteristics of each dataset employed in our experiments, along with the corresponding tasks evaluated on them. The GRID, and BA-SHAPES datasets serve as benchmark graph datasets for counterfactual analysis. These datasets incorporate ground-truth explanations Tan et al. (2022): Lin al. (2021a); Lucie et al.. (2022). Each dataset contains an undirected base graph to which predefined motifs are attached to random nodes, and additional edges are randomly added to the overall graph. The class label assigned to node determines its membership in motif.
TREE-
4.1 COMPARATIVE ANALYSIS
Factual Explainers: Fig. 2 iillustrates the sufficiency analysis of various factual reasoners in relation to size. Each algorithm assigns a score edges, indicating their likelihood of being included in the factual explanation. To control the size, we adopt greedy approach by selecting the highest- scoring edges. Both CF2 and RCEXPLAINER necessitate parameter to balance factual and counterfactual explanations. We set this parameter to 1, corresponding to solely factual explanations.
Insights: No single technique dominates across all datasets. For instance, while RCEXPLAINER performs exceptionally well in the MUTAG dataset, it exhibits subpar performance in IMDB-B and GRAPH-SSTE Similar observations are also made for GNNEXPLAINER in REDDIT-B B vs. MUTAG and NCI1. Overall, we recommend using either RCEXPLAINER GNNEXPLAINER the preferred choices. The spider plot in Fig, Q more prominently substantiates this suggestion. GNNEXPLAINER is transductive, wherein it trains the parameters the input graph itself. In contrast, inductive
5

---

Published as a conference paper at ICLR 2024
Froteins
1.00
1.0
Suffciency
0.7
0.40
0.0
0.80
IM086-8
AIDS
NC1
0.03
0.00
0.0
0.00
0.7
0.75
0.0
0.70
0.5
0.65
Graph: SST2
DD
RECOITB
1.00
0.75
0.98
0.01
0.70
SyRtC
0.65
0.91
0.35
0.92
0.35
0.92
0.88
0.40
0.47
10
15
20
25
15
20
size (Redges the explanation)
PGExplalner
TAGExplsiner
RCExplainer
GNNExclainer
SubgraphX
Figure 2: Sufficiency of the factual explainers against the explanation size. For factual explanations, higher is better. We omit those methods for dataset that threw an out-of-memory (OOM) error.
methods use pre-trained weights to explain the input. Consequently, transductive methods, such as GNNEXPLAINER, the expense of higher computation cost, has inherent advantage in terms of optimizing sufficiency. Compared to other transductive methods, GNNEXPLAINER utilizes loss function that aims to increase sufficiency directly. This makes the method a better candidate for sufficiency compared to other inductive and transductive explainers. On the other hand, for RCEXPLAINER, we believe that calculation of decision regions for classes helps to increase its generalizability well robustness.
In Fig. 2. the sufficiency does not always increase monotonically with explanation size (such as PGEXPLAINER in Mutag). This behavior arises due the combinatorial nature of the problem. Specifically, the impact of adding an edge to an existing explanation on the GNN prediction is function of both the edge being added and the edges already included in the explanation. An explainer seeks to learn a proxy function that mimics the true combinatorial output of set of edges, When this proxy function fails to predict the marginal impact of adding edge, could potentially select an edge that exerts a detrimental influence on the explanation's 's quality.
Table 5: Sufficiency and size of counterfactual explainers on graph classification. Lower values are better for both metrics. OOM indicates that the technique ran out memory.
Matas
Matagsuicity
Protcias
IMDB-B
oaha-mellir
Methed/ Mettc Meric
Suftic.l
Size]
Suffie.
Stzel
Suffic.]
Size.
Suffie.
Sizo).
Suffie..
Stoel
Suffe.)
Size.
RCFsppiiner
0)
0.50
2.7%
0.95
3.25
Dn
8.07
0.36
30.45
CLEAR
1611
00M
0.01
00M
21882
00M
Counterfactual Explainers: Tables and present the results on graph and node classification.
Insights graph classification (Table 5): RCEXPLAINER is the best-performing explainer across the majority of the datasets and metrics. However, it is important to acknowledge that RCEXPLAINER'S sufficiency, when objectively evaluated, consistently remains high, which is undesired. For instance, in the case of AIDS, the sufficiency of RCEXPLAINER reaches a value of 0.9, signifying its inability to generate counterfactual explanations for 90% of the graphs. This

---

Published as a conference paper at ICLR 2024
Table 6: Performance of counterfactual explainers on node classification. Shaded cells indicate the best result in a column. Note that only CF-GNNEXPLAINER and CF² can explain node classification. In these datasets, ground truth explanations are provided. Hence, aceuracy (Acc) represents the percentage of edges within the counterfactual that belong to the ground truth explanation.
Tree-Cycles
Tree-Grid
Bhapes
Method Metric
Suflic.
1
Sulfic
Acc(S))
Sullic
Acc(R)) 1
CV-GNNEX
0.5 0.08
1,03
0.36
100.0=00
0.09
0.06
1.42 0.35
92.70
4.99
0.37 =
0.05
1.37 0.59
91.3 4.36
CP (o
+ 4.56 + 1.48 74.71 18.70
0:00
0.02
7.0
14,29 +
0.25
4,24 1.70
+ 12.28
observation suggests that there exists considerable potential for further enhancement. We also note that while CLEAR achieves the best (lowest) sufficiency in AIDS, the number of perturbations it requires (size) exorbitantly high be useful practical use-cases.
Insights on node classification (Table 6 We observe that CF-GNNEXPLAINER consistently outperforms CF2 (a indicates the method be entirely counterfactual). We note that our result contrasts with the reported results in CF² Tan et al. (2022). where CF² was shown to outperform A closer examination reveals that in Tan et al. (2022), the value of a was set to 0.6, placing a higher emphasis on factual reasoning. It was expected that with = O. counterfactual reasoning would be enhanced. However, the results do not aligm with this hypothesis. We note that in CF the optimization function is combination of explanation complexity and explanation strength. The contribution of a is solely in the explanation strength component, based on its alignment with factual and counterfactual reasoning. The counterintuitive behavior observed with a is attributed to the domination of explanation complexity in the objective function, therehy diminishing the intended impact of a. Finally, when compared to graph classification, the sufficiency produced by the best methods in the node classification task is significantly lower indicating that it is an easier task. One possible reason might be the space of counterfactuals is smaller in node classification.
UT-GGNEXPLAINER
Mutagenictt
Proteins
AIDS
poocard Sinilanty
0.8
0.8
0.7
0.7
0.6
0.50
0.5
0.1
0.4
0.5
0.60
(noise)
PGExplaier
TAGiExlainer
CP
RCEiplatner
GNNMExpaanner
GEM
Subgraphx
Figure 3: Stability of factual explainers in Jaccard similarity of explanations under topological noise. Here, the æ-ticks (Noise) denote the number of perturbations made to the edge set of the original graph. Here, perturbations include randomly sampling x(denoted axis) negative edges and adding them to the original edge set (i.e., connect a pair of nodes that were previously unconnected).
4.2 STABILITY
We next examine the stability of the explanations against topological noise, model parameters, and the choice of GNN architecture. In App. C we present the impact of the above mentioned factors on other metrics of interest such as sufficiency and explanation size. In addition, we also present
impact of feature perturbation and topological adversarial attack in App. C
Insights on factual-stability against topological noise: Fig. 3 illlustrates the Jaccard coefficient as a function of the noise volume. Similar to Fig edge selection for the explanation involves a greedy approach that prioritizes the highest score edges. clear trend that emerges is that inductive methods consistently outperform the transductive methods (such as CF² and GNNEXPLAINER). This is expected since transductive methods lack generalizable capability to unseen data. Furthermore, the stability is worse denser datasets of IMDB-B since due to the presence of more edges, the search space of explanation is larger. RCEXPLAINER (executed at a = 1) and PGEXPLAINER consistently exhibit higher stability. This consistent performance reinforces the claim that RCEXPLAINER is the preferred factual explainer. The stability of RCEXPLAINER can be attributed to its strategy of selecting subset of edges that is resistant changes, such that the removal of these edges
7

---

Published as a conference paper at ICLR 2024
Table 7: Stability in explanations provided by factual explainers across runs. We fix the size to 10 for all explainers. The most stable explainer for each dataset (row) corresponding to the three categories of lus2, lus3 and 2us3 are highlighted through gray, yellow and cyan shading respectively.
PGExplainer
TAGEsplainer
C12
RCExplainer
GNNExplainer
Dataset/ Seeds
1os2
1ve3
20s3
1vs2
1ss3
2vx3
1ve2
18s3
2vx3
1ee22
18s3
20s3
1vs2
1ss3
20s3
Mutagenicity
0.69
0.75
0.62
0.76
0.78
0.74
0.77
0.77
0.77
0.75
0.71
0.71
0.46
0:17
0.17
Proteins
0.38
0.51
0.38
0.35
0.48
0.46
0.34
0.34
0.35
0.88
0.85
0.91
0.28
0.28
0.28
Mutag
0.5
0.54
0.51
0.36
0.43
0.72
0.78
0.79
0.79
0.86
0.92
0.87
0.57
0.57
0.58
IMDB-B
0.67
0.76
0.67
0.67
0.60
0.56
0.32
0.32
0.32
0.75
0.73
0.70
0.18
0.19
0.18
AIDS
0.88
0.87
0.82
0.81
0.83
0.87
0.85
0.55
0.85
0.95
0.96
0.97
0.80
0.80
0.80
NCII
0.58
0.55
0.64
0.69
0.81
0.65
0.60
0.60
0.60
0.71
0.71
0.94
0.44
0.44
0.44
Table 8: Stability of factual explainers against the GNN architecture. We fix the size to 10. We report the Jaccard coefficient of explanations obtained for each architecture against the explanation provided over GCN. The best explainers for each dataset (row) are highlighted in gray, yellow and eyan shading for GAT, GIN, and GRAPHSAGE, respectively. GRAPHSAGE is denoted by SAGE.
PGEsplainer
TAGExplainer
CF2
RCExplainer
GNNExplainer
Dataset/ / Architecture
GAT
GIN
SAGE
GAT
GIN
SAGE
GAT
GIN
SAGE
GAT
GIN
SAGE
GAT
GIN
SAGE
Mutagenicity
0.63
0.65
11.00
0.21
0.25
0.32
0.52
0.47
0.54
0.56
0.52
0.46
0.13
0.12
0.13
Proteins
0.22
0.45
0.18
0.28
0.28
0.41
0.42
0.28
Murag
0.57
0.58
0:68
0.60
0.65
0.64
0.58
0.56
0.62
0.47
0.76
0.54
0.55
0.57
0.55
IMDB-B
01:88
0:25
0.50
0.11
0.35
0.17
0.17
0.23
0.17
0.30
0.33
0.26
0.17
0.17
0.17
AIDS
0.81
0.85
0.87
0.83
0.83
0.84
0.80
0.80
0.50
0.81
0.85
0.81
0.8
0.8
NC11
0.39
0.41
0.37
0.45
0.17
0.38
0.37
0.38
0.38
0.19
0.53
0.52
0.37
0.38
0.39
significantly impacts the prediction made by the remaining graph [Bajaj et al. (202T). PGEXPLAINER also incorporates a form of inherent stability within its framework. It builds upon the concept introduced in GNNEXPLAINER through the assumption that the explanatory graph can be modeled as a random Gilbert graph, where the probability distribution of edges is conditionally independent and can be parameterized. This generic assumption holds the potential to enhance the stability of the method. Conversely, TAGEXPLAINER exhibits the lower stability than RCEXPLAINER and PGEXPLAINER, likely due to its reliance solely gradients in a task-agnostic manner Xie et al. (2022). The exclusive reliance on gradients makes it more susceptible to overfitting, resulting in reduced stability.
Insights on factual-stability against explainer instances: Table presents the stability of expla- nations provided across three different explainer instances on the same black-box GNN. A similar trend is observed, with RCEXPLAINER remaining the most robust method, while GNN exhibits the least stability. For GNNEXPLAINER, the Jaccard coefficient hovers around 0.5, indicating significant variance in explaining the same GNN. Although the explanations change, their quality remains stable (as evident from small standard deviation in Fig. 2 This result indicates that multiple explanations of similar quality exist and hence a single explanation fails to complete explain the data signals. This component is further emphasized when we delve into reproducibility (S 4.3).
Insights on factual-stability against GNN architectures: Finally, we explore the stability of explainers across different GNN architectures in Table 88] which has not yet been investigated in the existing literature. For each combination of architectures, we assess the stability by computing the Jaccard coefficient between the explained predictions of the indicated GNN architecture and the default GCN model. One notable finding is that the stability of explainers exhibits strong correlation with the dataset used. Specifically, in five out of six datasets, the best performing explainer across all architectures is unique. However, it is important to highlight that the Jaccard coefficients across architectures consistently remain low indicating stability against different architectures is the hardest objective due to the variations in their message aggregating schemes.
4.3 NECESSITY AND REPRODUCIBILITY
We aim to understand the quality of explanations in terms of necessity and reproducibility. The results are presented in App. D and E Our findings suggest that necessity is low but increases with the removal of more explanations, while reproducibility experiments reveal that explanations do not provide a comprehensive explanation of the underlying data, and even removing them and retraining the model can produce similar performance to the original GNN model.
8

---

Published as a conference paper at ICLR 2024
4.4 FEASIBILITY
Counterfactual explanations serve as recourses and are expected to generate graphs that adhere to the feasibility constraints of the pertinent domain. We conduct the analysis of feasibility on molecular graphs. It is rare for molecules to be constituted of multiple connected components Vismmra & Laurenço (2000). Hence, we study the distribution of molecules that are connected in the original dataset and its comparison to the distribution in counterfactual recourses. We measure the p-value of this deviation. App. A.7 presents the results.
4.5 VISUALIZATION- BAASD ANALYSIS
We include visualizations of the explanations in App. F Our analysís reveals that statistically good performance does not always align with human judgment indicating an urgent need for datasets annotated with ground truth explanations. Furthermore, the visualization analysis reinforces the need to incorporate feasibility as a desirable component in counterfactual reasoning.
CONCLUDING INSIGHTS AND POTENTIAL SOLUTIONS
Our benchmarking study has yielded several insights that can streamline the development of ex- planation algorithms. We summarize the key findings below (please also see the App. for our recommendations of explainer for various scenarios).
Performance and Stability: Among the explainers evaluated, RCEXPLAINER consistently out- performed others in terms of efficacy and stability to noise and variational factors ($ 4.1 and 4.2).
Stability Concerns: Most factual explainers demonstrated significant deviations across explainer instances, vulnerability to topological perturbations and produced significantly different set of explanations across different GNN architectures. These stability notions should therefore be embraced as desirable factors along with other performance metrics.
Model Explanation vs. Data Explanation: Reproducibility experiments ($ 4.3 revealed that retraining with only factual explanations cannot reproduce the predictions fully. Furthermore, even without the factual explanation, the GNN model predicted accurately on the residual graph. This suggests that explainers only capture specific signals learned by the GNN and do not encompass all underlying data signals.
Feasibility Issues: Counterfactual explanations showed deviations in topological distribution from the original graphs, raising feasibility concerns ($ 4.4.
Potential Solutions: The aforementioned insights raise important shortcomings that require further investigation. Below, we explore potential avenues of research that could address these limitations.
Feasible recourses through counterfactual reasoning: Current counterfactual explainers pre- dominantly concentrate on identifying the shortest edit path that nudges the graph toward the decision boundary. This design inherently neglects the feasibility of the proposed edits. Therefore, it is imperative to explicitly address feasibility as objective in the optimization function. One potential solution lies in the vibrant research field of generative modeling for graphs, which has yielded impressive results Goyal et al. (2020); You al. (2018); /Vinnac et al. (2023). Generative models, when presented with an input graph, can predict its likelihood of occurrence within a domain defined by set of training graphs. Integrating generative modeling into counterfactual reasoning by incorporating likelihood of occurrence as an additional objective in the loss function presents a potential remedy.
Ante-hoc explanations for stability and reproducibility: We have observed that if the explana- tions are removed and the GNN retrained on the residual graphs, the GNN is often able to recover the correct predictions from our reproducibilty experiments. Furthermore, the explanation exhibit significant instability the face of minor noise injection. This incompleteness of explainers and instability is likely manifestation of their post-hoc learning framework, wherein the explanations are generated post the completion of GNN training. In this pipeline, the explainers have no visibility to how the GNN would behave to perturbations on the input data, initialization seeds, etc. Potential solutions may lie on moving to an ante-hoc paradigm where the GNN and the explainer are jointly trained Kosian et al. (2033) Miao et al. (2022) Fang al. (2023).
These insights, we believe, open new avenues for advancing GNN explainers, empowering researchers to overcome limitations and elevate the overall quality and interpretability of GNNS.

---

Published as a conference paper at ICLR 2024
6 ACKNOWLEDGEMENTS
Samidha Verma acknowledges the generous grant received from Microsoft Research India to sponsor her travel ICLR 2024. Additionally, this project was partially supported by funding from the National Science Foundation under grant #IIS-2229876 and the CSE Research Acceleration Fund of IIT Delhi.
REFERENCES
Carlo Abrate and Francesco Bonchi. Counterfactual graphs for explainable classification of brain networks. In KDD, pp. 2495-2504, 2021.
Chirag Agarwal, Owen Queen, Himabindu Lakkaraju, and Marinka Zitnik. Evaluating explainability for graph neural networks. 2023.
Miltiadis Allamanis, Earl T Barr, Premkumar Devanbu, and Charles Sutton. A survey of machine learning for big code and naturalness. ACM Computing Surveys (CSUR), 51(4):1-37, 2018.
Kenza Amara, Zhitao Ying, Zitao Zhang, Zhichao Han, Yang Zhao, Yinan Shan, Ulrik Brandes, Scbastian Schemm, and Ce Zhang. Graphframex: Towards systematic evaluation of explainability methods for graph neural networks. In The First Learning on Graphs Conference, 2022. URL
https://openrreveew. https///ppenreiie..eeffommm
Steve Azzolin, Antonio Longa, Pietro Barbiero, Pietro Lio, and Andrea Passerini. Global explainabil- ity of GNNs via logic combination of learned concepts. In The Eleventh International Conference on Learning Representations, 2023. URL https://openreviiw net/forum "o--bummYYYddOOO
Mohit Bajaj. Lingyang Chu, Zi Yu Xue, Jian Pei, Lanjun Wang, Peter Cho-Ho Lam, and Yong Zhang, Robust counterfactual explanations on graph neural networks. In A. Beygelzimer, Dauphin, P. Liang. and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL htttps://opeeeeiieeeee//f/uuuu Iddiii/GGGS_SA5MM
Federico Baldassarre and Hossein Azizpour. Explainability techniques for graph convolutional networks. arXiv preprint arXiv: /905. 13686, 2019.
Ravinder Bhattoo, Sayan Ranu, and NM Krishnan. Learning articulated rigid body dynamics with lagrangian graph neural network. Advances in Neural Information Processing Systems, 35: 29789-29800, 2022.
Ravinder Bhattoo, Sayan Ranu, and NM Anoop Krishnan. Learning the dynamics of particle-based systems with lagrangian graph neural networks. Machine Learning: Science and Technology, 2023.
Suresh Bishnoi, Ravinder Bhattoo, Sayan Ranu, and NM Krishnan. Enhancing the inductive biases of graph neural ode for modeling dynamical systems. ICLR, 2023.
Karsten M Borgwardt, Cheng Soon Ong. Stefan Schönauer, SVN Vishwanathan, Alex Smola, and Hans-Peter Kriegel. Protein function prediction via graph kernels. Bioinformatics, 21(pppp__ i47-i56. 2005.
Yuwei Cao, Hao Peng, Jia Wu, Yingtong Dou, Jianxin Li, and Philip S Yu. Knowledge-preserving incremental social event detection via heterogeneous gnns. In Proceedings of the Web Conference 2021, pp.
2021.
Pritish Chakraborty, Sayan Ranu, Krishna Sri Ipsit Mantri, and Abir De. Learning and maximizing influence in social networks under capacity constraints. In Proceedings of the Sixteenth ACM International Conference on Web Search and Data Mining, pp. 733-741, 2023.
Asim Kumar Debnath, Rosa L Lopez de Compadre, Gargi Debnath, Alan J Shusterman, and Corwin Hansch. Structure-action relationship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity. Journal of medicinal chemistry, 34 (2):786-797, 1991.
10

---

Published as a conference paper at ICLR 2024
Paul D Dobson and Andrew Doig. Distinguishing enzyme structures from non-enzymes without alignments. Journal of molecular biology, 330(4):771-783, 2003.
Junfeng Fang, Xiang Wang, An Zhang, Zemin Liu, Xiangnan He, and Tat-Seng Chua. Cooperative explanations of graph neural networks. Proceedings of the Sixteenth ACM International Conference Web Search and Data Mining, pp. 616-624, 2023.
Nikhil Goyal, Harsh Vardhan Jain, and Sayan Ranu. Graphgen: a scalable approach domain- agnostic labeled graph generation. In Proceedings of The Web Conference 2020, pp. 1253-1263, 2020.
Mridul Gupta, Hariprasad Kodamana, and Sayan Ranu. FRIGATE: Frugal spatio-temporal forecasting on road networks. In 29th SIGKDD Conference on Knowledge Discovery and Data Mining, 2023. URL hutps//oppnneeview. 2id
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS' 17, pp. 1035-1035, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 9781510860964.
Qiang Huang, Makoto Yamada, Yuan Tian, Dinesh Singh, and Yi Chang. Graphlime: Local interpretable model explanations for graph neural networks. IEEE Trunsactions on Knowledge and Data Engineering, 2022.
Zexi Huang, Mert Kosan, Sourav Medya, Sayan Ranu, and Ambuj Singh. Global counterfactual explainer for graph neural networks. In Proceedings the Sixteenth ACM International Conference on Web Search and Data Mining, pp. 141-149, 2023.
Sergei Ivanov, Sergei Sviridov, and Evgeny Burnaev. Understanding isomorphism bias in graph data sets. Geometric Leurning and Graph Representations ICLR Workshop. 2019.
Jayant Jain, Vrittika Bagadia, Sahil Manchanda, and Sayan Ranu. Neuromir: Robust & reliable route recommendation road networks. Advances in Neural Information Processing Systems, 34: 22070-20 22082, 2021.
Jaykumar Kakkad, Jaspal Jannu, Kartik Sharma, Charu Aggarwal, and Sourav Medya. A survey on explainability graph neural networks. arXiv preprini arXiv:2306.0/ 09588, 2023.
Jeroen Kazius, Ross McGuire, and Roberta Bursi. Derivation and validation of toxicophores for mutagenicity prediction. Journal of medicinal chemistry, 48(13312-3320 2005.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks.
arXiv preprint 1609:::00..2990000 2016.
Mert Kosan, Arlei Silva, Sourav Medya, Brian Uzzi, and Ambuj Singh, Event detection on dynamic graphs. arXiv preprint arXiv:2 12/42, 2021.
Mert Kosan, Arlei Silva, and Ambuj Singh. Robust ante-hoc graph explainer using bilevel optimiza- tion. arXiv preprint arXiv:2305. 157455 2023.
Xiucheng Li, G. Cong. and Yun Cheng. Spatial transition lcarning road networks with deep probabilistic models. 2020 IEEE 36th Intermational Conference on Data Engineering (ICDE), pp. 349-360, 2020. URL httpps:/app..emmnniischhht http:///saaaaaaaaaoooooooooaoaaa orrg/C/oouuull:::111866633
Wanyu Lin, Hao Lan, and Baochun Li. Generative causal explanations for graph neural networks. In International Conference Machine Learning, pp. 6666-6679. PMIR, 2021a.
Wanyu Lin, Hao Lan, and Baochun Li. Generative causal explanations for graph neural networks. In ICML, 2021b.
Ana Lucic, Maartje A Ter Hoeve, Gabriele Tolomei, Maarten De Rijke, and Fabrizio Silvestri. Cf- gnnexplainer: Counterfactual explanations for graph neural networks. In AISTATS, pp. 4419-4511, 2022.
11

---

Published as a conference paper at ICLR 2024
Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang. Parameterized explainer for graph neural network. Advances in neural information processing systems, 115196220-196311 2020.
Jing Ma, Ruocheng Guo, Saumitra Mishra, Aidong Zhang, and Jundong Li. Clear: Generative counterfactual explanations graphs. arXiv preprint arXiv:2210.08445 2022.
Sahil Manchanda, Akash Mittal, Anuj Dhawan, Sourav Medya, Sayan Ranu, and Ambuj Singh. Gcomb: Learning budget-constrained combinatorial algorithms over billion-sized graphs. Advances in Neural Information Processing Systems, 1-20000022000 2020.
Siqi Miao, Mia Liu, and Pan Li. Interpretable and generalizable graph learning via stochastic attention mechanism. In International Conference on Machine Learning, pp. 15524-15543. PMLR, 2022.
Phillip E Pope, Soheil Kolouri, Mohammad Rostami, Charles E Martin, and Heiko Hoffmann. Explainability methods for graph convolutional neural networks. In Proceedings of the JEEF/CVF conference on computer vision and pattern recognition, pp. 10772-10781, 2019.
Mario Alfonso Prado-Romero, Bardh Prenkaj, Giovanni Stilo, and Fosca Giannotti. survey on graph counterfactual explanations: Definitions, methods, evaluation, and research challenges. ACM Computing Surveys, 2023.
Ladislav Rampášek, Mikhail Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Do- minique Beaini. Recipe for General, Powerful, Scalable Graph Transformer. Advances in Neural Information Processing Systems, 35, 2022.
Rishabh Ranjan, Siddharth Grover, Sourav Medya, Venkatesan Chakaravarthy, Yogish Sabharwal, and Sayan Ranu. Greed: neural framework for learning graph distance functions. In Advances in Neural Information Processing Systems, 2022.
Kaspar Riesen and Horst Bunke. lam graph database repository for graph based pattern recognition and machine learning. In Joint IAPR International Workshops on Statistical Techniques in Pattern Recognition (SPR) and Structural and Syntactic Pattern Recognition (SSPR), pp. pp. 287-297. Sprinnrr, 2008.
Thomas Schnake, Oliver Eberle, Jonas Lederer, Shinichi Nakajima, Kristof T Schüit,, Klaus-Robert Müller, and Grégoire Montavon. Higher-order explanations of graph neural networks via relevant walks. IEEE transactions on pattern analysis and machine intelligence, 44(11):7581-756 2021.
Caihua Shan, Yifei Shen, Yao Zhang, Xiang Li, and Dongsheng Li. Reinforcement learn- ing enhanced explainer for graph neural networks. In NeurIPS 2021, December 2021. URL
Richard Socher, A. Perelygin, J.Y. Wu, J. Chuang, C.D. Manning, A.Y. Ng. and C. Potts. Recursive deep models for semantic compositionality over a sentiment treebank. EMNLP, 1631:1631-1642, 01 2013.
Juntao Tan, Shijie Geng, Zuohui Fu. Yingqiang Ge, Shuyuan Xu, Yunqi Li, and Yongfeng Zhang. Learning and evaluating graph neural network explanations based on counterfactual and factual reasoning. Proceedings of the ACM Web Conference 2022, WWW '22, pp. 1018-1027, 2022.
Abishek Thangamuthu, Gunjan Kumar, Suresh Bishnoi, Ravinder Bhattoo, NM Krishnan, and Sayan Ranu. Unravelling the performance of poysics-informed graph neural networks for dynamical systems. In Advances in Neural Information Processing Systems, 2022.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations. 2018. URL http:////weeevvevevee/////nnnnna
Clement Vignac, Igor Krawezuk, Antoine Siraudin, Bohan Wang, Volkan Cevher, and Pascal Frossard. Digress: Discrete denoising diffusion for graph generation. In The Eleventh International Confer- on Learning Representations, 2023. URL http://pppnneeiiieeeee//mmmdnddd
12

---

Published as a conference paper at ICLR 2024
Philippe Vismara and Claude Laurenço. An abstract representation for molecular graphs, pp- 343-366. 04 2000. ISBN 9780821809877. doi: 10. 10000/dmmaes0051/26
Minh Vu and My T Thai. Pgm-explainer: Probabilistic graphical model explanations for graph neural networks. Advances in neural information processing systems, 53:12225-12235, 2020.
Nikil Wale, Ian A Watson, and George Karypis. Comparison of descriptor spaces for chemical compound retrieval and classification. Knowledge and Information Systems, 14(3):347-375, 2008.
Xingchen Wan, Henry Kenlay, Binxin Ru, Arno Blaas, Michael Osborne, and Xiaowen Dong. Adversarial attacks on graph classifiers via bayesian optimisation. Thirty-Fifth Conference on Neural Information Processing Systems, 2021.
Geemi P Wellawatte, Aditi Seshadri, and Andrew D White. Model agnostic generation of counterfac- tual explanations for molecules. Chemical science, (3(13):3677-3705 2022.
Hao Wu, Ziyang Chen, Weiwei Sun, Baíhua Zheng, and Wei Wang. Modeling trajectories with recurrent neural networks. In Proceedings of the 26th International Joint Conference on Artificial Intelligence, IJCAI' 17, pp. 3083-3090, 2017.
Yaochen Xie, Sumeet Katariya, Xianfeng Tang, Edward Huang. Nikhil Rao, Karthik Subbian, and Shuiwang Ji. agnostti graph explanations. NeurlPS, 2022.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neu- ral networks? In International Conference on Learning Representations, 2019. URL https: //openreview //openreview.me/fforum/// net/forummiddrrGGiiiAAkkk
Han Xuanyuan, Pietro Barbiero, Dobrik Georgiev, Lucie Charlotte Magister, and Pietro Lió. Global concept-based interpretability for graph neural networks via neuron analysis. 2023.
Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pp. 1365-1374, 2015.
Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie-Yan Liu. Do transformers really perform badly for graph representation? A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL https::/openrevieww netfoorummxd-Ooeooooooo
Rex Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gnnexplainer: Generating explanations for graph neural networks. Advances in neural information processing systems, 32:9240, 2019a.
Zhitao Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gnnexplainer: Generating explanations for graph neural networks. Advances in neural information processing systems, 32, 2019b.
Jiaxuan You, Rex Ying, Xiang Ren, William L. Hamilton, and Jure Leskovec. Graphrnn: Gener- ating realistic graphs with deep auto-regressive models. In Jennifer G. Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference Machine Learning, ICML 2018. Stock- holmsmässan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learn- ing Research, pp. 5694-669700 PMLR, 2018. URL http://procceeiing..oo mlr. plr.prrsss/v800/you hat::/0yyoooooahhaoo html
Hao Yuan, Jiliang Tang, Xia Hu, and Shuiwang Ji. Xgnn: Towards model-level explanations of graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. pp. 430 430, 2020.
Hao Yuan, Haiyang Yu, Jie Wang, Kang Li, and Shuiwang Ji. On explainability of graph neural networks via subgraph explorations. In ICML, pp. 12241-12252. PMLR, 2021.
Hao Yuan, Haiyang Yu, Shurui Gui, and Shuiwang Ji. Explainability in graph neural networks: A taxonomic survey. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.
Yue Zhang, David Defazio, and Arti Ramesh. Relex: A aggostic relational model explainer. In Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society, pp. 1042-1049, 2021.
13

---

Published as a conference paper at ICLR 2024
APPENDIX
A EXPERIMENTAL SETUP
All experiments were conducted using the Ubuntu 18.04 operating system on an NVIDIA DGX Station equipped with four V100 GPU cards, each having 128GB of GPU memory. The system also included 256GB of RAM and 20-core Intel Xeon E5-2698 2.2 GHz CPU.
The datasets for factual and counterfactual explainers follow an 80:10:10 split for training, validation and testing. We explain some of our design choices below.
For factual explainers, inductive explainers are trained on the training data and the reported results computed the entire dataset. We also report results only test data (please Sec. A.3 comparing only inductive methods. Transductive methods are run on the entire dataset. For counterfactual explainers, the inductive explainers reported results are computed on the test data. Since transductive methods do not have the notion of training and testing separately, they are run only on the test data.
trained the training data, and the
A.1 BENCHMARK DATASETS
Datasets for Node classification: The following datasets have node labels and are used for the node classification task.
TREE-CYCLES Ying et al. (2019b): The base graph used this dataset a binary tree, and the motifs consist of 6-node cycles (Figure D(a)), The motifs connected to random nodes in the tree. Non-mot Non-motif nodes are labeled while the motif nodes are labeled
TREE-GRID Ying al. (2019b): The base graph used in this dataset is binary tree, and the motif is a x 3 grid connected to random nodes the tree (Figure D(b)). Similar to the tree-cycles dataset, the nodes are labeled with binary classes (0 for the non-motif nodes and I for the motif' nodes).
BA-SHAPES Ying al. (201b)): The base graph in this dataset a Barabasi-Alber (BA) graph. The dataset includes house-shaped structures composed of nodes (Figure D (c)). Non-motif nodes are assigned class 0, while nodes at the top, middle, and bottom of the motif are assigned classes 1, 2, and 3, respectively.
2
(b)
(c)
Figure D: Motifs used in (a) Tree-Cycles, (b) Tree-Grid and (c) BA-Shapes datasets for the node classification task. Please note the following. (i) Tree-Cycles and Tree-Grid have labels 0 and 1 for the non-motif and the motif nodes, respectively. Hence, all nodes in (a) and (b) have label 1. (ii) BA-Shapes dataset has 4 classes. Non- ootif nodes have labels motif nodes have integral labels depending on the position in the house motif. The other labels are (top node). 2 (middle nodes) and 3 (bottom nodes). They are represented in (c).
Datasets for Graph Classification: The following datasets are used for the graph classification task and contain labeled graphs.
MUTAG Ivanov et al. 2019) and Mutagenicity Riesen & Bunke 20088); Kazius et al. (2005): These are graph datasets containing chemical compounds. The nodes represent atoms, and the edges represent chemical bonds. The binary labels depend the mutagenic effect of the compound
Ivano
14

---

Published as a conference paper at ICLR 2024
bacterium, namely mutagenic non mottaenng.... MUTAG and Mutagenicity datasets contain 188 and 4337 graphs. respectively.
AIDS: Ivanov et al. (2019) This dataset contains small molecules. The nodes and edges are atoms
and chemical bonds, respectively. The molecules are classified by whether they are active against the HIV virus or not.
Proteins Borgwardt et al. 2005); Dobson & Doig 2003) and DD Dobson & Doig (203)): These
datasets are comprised of proteins categorized into enzymes and non-enzymes. The nodes represent
amino acids, and an edge exists between two nodes if their distance is less than 6 Angstroms.
NCI1 Wale al. (008); This dataset is derived from cheminformatics and represents chemical compounds as input graphs. Vertices in the graph correspond to atoms, while edges represent bonds between atoms. This dataset focuses on anti-cancer screenings for cell lung cancer, with chemicals labeled as positive or negative. Each vertex is assigned an input label indicating the atom type, encoded using a one-hot- monehoo-nnnoing scheme.
IMDB-B Yanardag & Vishwanathan (2015): The IMDB-B BINARY dataset is a collection of movie collaboration networks, encompassing the ego-networks of 1,000 actors and actresses who have portrayed roles in films listed on IMDB. Each network is represented as graph, where the nodes correspond to the actors/actresses, and an edge is present between two nodes if they have shared the screen in the same movie. These graphs have been constructed specifically from movies in the Action and Romance genres, which are the class labels.
REDDIT-B Yanardag Vishwanathan (2015): REDDIT-BINARY dataset encompasses graphs representing online discussions on Reddit. Each graph has nodes representing users, connected by edges when either user responds to the other's comment. The four prominent subreddits within this dataset are IAmA, AskReddit, TrollXCCromosomes, and atheism. IAmA and AskReddit are question/ansser-basee. communities, while TrollXChrrmosomes and atheism are discussion-bases communities. Graphs are labeled based on their affiliation with either a question/ansser-basee or discussion based community.
GRAPH-SST2 Yuan et al.] (2022): The Graph-SST2 dataset is graph- dataset derived from the SST2 dataset (Socher et al. (013), which contains movic review sentences labeled with positive negative sentiment. Each sentence in the Graph-SST2 dataset is transformed into graph representation, with words as nodes and edges representing syntactic relationships capturing the sentence's 's grammatical structure. The sentiment labels from the original SST2 dataset are preserved, allowing for sentiment analysis tasks using the graph representations of the sentences. ogbg-molhiv /Allamanis et al. (2018): ogbg-molhiv is a molecule dataset with nodes representing atoms and edges representing chemical bonds. The node features represent various properties of the atoms like chirality, atomic number, formal charge etc. Edge attributes represent the bond type. We study binary classification task on this dataset. The task is to achieve the most accurate predictions of specific molecular properties. These properties are framed as binary labels, indicating attributes like whether molecule demonstrates inhibition of HIV virus replication or not.
A.2 DETAILS OF GNN MODEL & USED FOR NODE CLASSIFICATION
We use the same GNN model used in CF-GNNEXPLAINER and CF2. Specifically, it is Graph Convolutional Networks Kipt & Welling (016) trained on each of the datasets. Each model has graph convolutional layers with 20 hidden dimensions for the benchmark datasets. The non-linearity used is relu for the first two layers and log softmax after the last layer of GCN. The learning rate 0.01. The train and test data are divided in the ratio 80:20. The accuracy of the GNN model & for each dataset is mentioned Table
Table I: Accuracy of black-box GNN T on the datasets used for node classification, for evaluation of counterfactual explainers. + is GCN Kipf Welling (2016) for this task
Dataset
Train accuracy
Test Accuracy
Tree- CreeeSycles
0.9123
0.9086
Grri
0.8434
0.8744
BA-Shapes
0.9661
0.9857
15

---

Published as a conference paper at ICLR 2024
A.3 DETAILS OF BASE GNN MODEL O FOR THE GRAPH CLASSIFICATION TASK
Our GNN models have an optional parameter for continuous edge weights, which our case represents explanations. Each model consists of 3 layers with 20 hidden dimensions specifically designed for benchmark datasets. The models provide node embeddings, graph embeddings, and direct outputs from the model (without any softmax function). The output is obtained through one- layer MLP applied to the graph embedding. We utilize the max pooling operator to calculate the graph emhedding. The dropout rate, learning rate, and batch size set to 0, 0.001, and 128, respectively. The train, validation, and test datasets are divided into an 00:10:10 ratio. The algorithms run for 1000 epochs with early stopping after 200 patience steps on the validation set. The performance analysis of the base GNN models ( (Kipf & Welling 2016); Veličković et al. 20188; Xu et al. (2019), Hamilton al. (2017) for each graph classification dataset is presented in Table
Table J: Test accuracy of black-box GNN o trained for the graph classification task, averaged over 10 runs with random seeds. We train multiple GNNS for this task to test explainers for stability against GNN architectures.
Dataset
GCN
GAT
GIN
GraphSAGE
Mutagenicity
0.8724 + 0.0092
0.8685 + 0.0111
0.8914 : 0.0101
0.8749 + 0.0059
Mutag
0.925 = 0.0414
0,8365 = 0.0264
0.9542 + 0.0149
0.8323 + 0.0445
Proteins
0.8418 +1: 0.0144
0.8362 1 0.0269
0.8352 0.0165
0.8408 0.0124
IMDB-B
0.8318 = 0.0197
0.8292 0.015
4.854400002
0.8373 = 0.0093
AIDS
0.999 + 0.0005
0.9971 + 0.0068
0.9797 + 0.0099
0.9903 + 0.0088
NCI1
0.8096 = 0.015
0.8365 = 0.0201
0.8303 0.0137
Graph-SST2
0.957 + 0.001
0.9603 + 0.0009
0.9552 + 0.0014
0.9611 + 0.0011
DD
0.736 + 0.0377
0.7312 0.048
0.7693 = 0.0238
0.7541 + 0.0415
REDDIT-B
0.8984 + 0.0247
0.8444 0.0266
0.6886 + 0.1231
0.8733 + 0.0196
ogbg-molhiv
0.9729 = 0.0002
0.9722 = 0.0010
0.9726 = 0.0003
0.9725 = 0.0005
A.4 DETAILS OF FACTUAL EXPLAINERS FOR THE GRAPH CLASSIFICATION TASK
In many cases, explainers generate continuous explanations that can be used with graph neural network (GNN) models, which can handle edge weights. To be able to use explanations our GNN models, we map them into [0, 1] using sigmoid function if not mapped. While generating performance results, we calculate top-k edges based on their scores instead of assigning a threshold value (c.g., 0.5). However, there are some approaches, such as GEM and SubgraphX, that do not rely on continuous edge explanations.
GEM employs a variational auto-encoder to reconstruct ground truth explanations. As result, the generated explanations can include negative values. While our experiments primarily focus on the order of explanations and do not require invoking the base GNN in the second stage of GEM, we can still use negative explanation edges.
On the other hand, SubgraphX ranks different subgraph explanations based their scores. We select the top 20 explanations and, for each explanation, compute the subgraph. Then, we enhance the importance of each edge of particular subgraph by incrementing its score by 1. Finally, we normalize the weights of the edges. This process allows us to obtain continuous explanations as well. Moreover, since SubgraphX employs tree search, its scalability is limited when dealing with large graphs. For instance, in the Mutagenicity dataset, obtaining explanations for 435 graphs requires approximately 26.5 hours. To address this challenge, we restricted our analysis to test graphs when calculating explanations using SubgraphX. It is important to include this disclaimer, working only subset of graphs may introduce potential biases or noises in the results.
A.5 FACTUAL EXPLAINERS: INDUCTIVE METHODS ON TEST SET
The inductive factual explainers are run only on the test data and the results reported in Figure E The results are similar to the ones where the methods are run on the entire dataset (Figure Consis- tent with the earlier results, PGEXPLAINES consistently delivers inferior results compared to other
16

---

Published as a conference paper at ICLR 2024
baseline methods, and no single technique dominates across all datasets. Overall, RCEXPLAINER could be recommended as one the preferred choices.
Mutagenicity
Proteins
Mutag
1.00
1.0
Suficiency
0.8
0.90
0.85
0.6
0.80
0.4
0.75
0.2
IMDB-8
AIDS
NC11
1.00
0.95
0.8
Sufticleccy
0.90
0.7
0.85
0.75
0.60
0.70
Graph-SST2
1.00
0.98
0.60
Surticency
0.35
0.94
0.5
0.50
0.92
0.90
0.45
0.88
0.40
(#edges
explamation)
PGExplainer
TAGExplainer
RCExplainer
+
GEM
Figure E: Sufficiency of the inductive factual explainers against the explanation size only test data. For factual explanations, higher is better. We omit those methods for dataset that throw an out-of-memory (OOM) error and are not scalable.
A.6 CODES AND IMPLEMENTATION
Table shows the code bases we have used for the explainers. We have adapted the codes based our base GNN models. Our repository, httpp::/ggthub..oom./t com//dea iitd/gnn- bebenchhnn-bbbhh/////e includes the adaptations of the methods to our base models.
Table K: Reference of code repositories.
Method
Repository
PGEaplaine Lao al.
2020
httpo/lgituub comnil en ar Hoo.HHiij//RR
TAGEspkinst Xie
2023
RCExplance
lills:Adlvlloper htwp://wwww..........///////.ooe
GINNExplainer Ying el
901bb
https//gituu..co comii httphiiiihh.mmm/maaaaaaaaaaaa art.HaaaiHH.EEEE........ haw.:a/ww.....aaaaemmeeeeeeeeere
GFM
(iem/
SubgrapiX] Yuan
2021
htlp:///illb..oo
A.7 FEASIBILITY
Counterfactual explanations: As shown in Table L we observe statistically significant deviations from the expected values in two out of three molecular datasets. This suggests a heightened probability of predicting counterfactuals that do not correspond to feasible molecules. This finding underscores
17

---

Published as a conference paper at ICLR 2024
Table L: Assessing the statistical significance of deviations in the number of connected graphs between the test set and their corresponding counterfactual explanations on molecular datasets. Statistically significant deviations with v-luuee< 0.05 are highlighted.
RCEXPLAINER
CF
Dataset
Expected Count
Observed Count
p-valoe
Expected Count
Observed Count
p-value
Mutagenicity
233.05
70
< 6000000
206.65
0
< 00000001
Mutag
9
0.55
1
0.13
AIDS
17.6
8
0.00001
1.76
0
0,0001
a limitation of counterfactual explainers, which has received limited attention within the research community.
The feasibility metric is commonly used in the context of counterfactual graph explainers because it measures how feasible it is achieve specific counterfactual outcome. In other words, it assesses the likelihood of a counterfactual scenario being realized given the constraints and assumptions of the underlying base model. On the other hand, factual explainers aim to explain why a model makes a certain prediction based on the actual input data. They do not involve any counterfactual scenarios, explainers may use other metrics such as sufficiency and reproducibility to provide insights into how the model is making its predictions. Therefore, we have used feasibility metrics for factual explanations.
Factual explanations:
the feasibility metric is not relevant in this context. Instead, factual
B SUFFICIENCY OF FACTUAL EXPLANATIONS UNDER TOPOLOGICAL NOISE
We check the sufficiency of the factual explanations under noise for four different datasets. Figure demonstrates the results, including when there is no noise (i.e., when X 0). We set the explanation size (i.e., the number of edges) to units. We observe that, most cases, increasing noise results in decrease in the sufficiency metric for the Mutagenicity and AIDS datasets, which is expected. However, for the Proteins and IMDB-B datasets, even though there are still drops for some methods, others remain stable in sufficiency across different noise levels. This demonstrates that, despite the changes explanations caused by noise, GNN may still predict the same class under noisy conditions.
Mutagenicity
Proteins
AIDS
1.00
Suftclery
0.65
0.900
0.84
0.875
0.75
0.50
0.850
0.88
PGExplalnor
TAGExolalner
CF?
RCExplainar
GNNExplal alnor
GEM
Figure F: Sufficiency of factual explainers under topological noise.
C STABILITY
In addition to stability against topological noise, different seeds, and different GNN architecture, we also analyze stability against feature perlubation and stability against topological adversarial attack.
For feature perturbation, we first select the percentage of nodes to be perturbed (X% E {10, (10,20, 30, 50)).. Then, perturbation operation varies depending on the nature of node features (continuous or discrete). For the Proteins dataset (continuous features); for each feature f. we com- pute its standard deviation o.. Then we sample value uniformly random from A [-0.1, 0.1]. The feature value fa is perturbed to fa + A x a For other datasets (discrete features), for each selected node, flip its feature to randomly sampled feature.
For topology adversarial attack, we follow the flip edge method from Wan et al. 202 with a query size of one and vary the number flip count across datasets.
18

---

Published as a conference paper at ICLR 2024
C.I FACTUAL EXPLAINERS
Stability against feature perturbation:
Figure iillstraaes the outcomes, demonstrating a continuation of the previously observed trends. Among these trends, we that there one clear winner for both datasets. However, PGEXPLAINER performs better than most datasets in both datasets (with discrete and continuous features), On the other hand, the transductive method GNNEXPLAINER performs very poorly in both datasets compared to other methods (i.e., inductive), which further provides evidence that transductive methods are poor in stability for factual explanations.
Mutagenicity
Proteins
0.75
jaccare Simlbrly
0.70
0.9
0.8
0.00
0.55
0.50
10
Perturbation 156)
IGExplainer
TAGExplainer
RCExplainer
CANEsplainer
Figure G: Stability of factual explainers against feature perturbation in Jaccard similarity. The stability of explanations drops when the perturbation percentage increases. GNNEXPLAINER (transductive) is the worst method for these two datasets.
Adversarial attack on topology: Figure demonstrates the performance of four factual methods on these evasion attacks for four datasets. The behavior of the factual methods is similar to the topological noise attack explained in Section 4.2 and the feature perturbations results. When an adversarial attack is compared to random perturbations (Fig. 3 observe higher deterioration in stability, which expected since adversarial edge flip attack aims every possible edge in the graph rather than only considering nonexistent edges. Similar feature perturbation, GNNExplainer (transductive) is affected more by the adversarial attack.
Mutageridly
INDB-6
0.9
jaccard Sintaatt
0.6
0.8
0.5
0.5
05
0.4
0.3
0.2
PGPxplainer
TaGEsplainer
RCExplainer
CNNEEppliner
Figure H: Stability of factual explainers against random edge flip in Jaccard similarity. The stability of explanations drops when the flip count increases. GNNEXPLAINER (transductive) is the worst method for these datasets.
C.2 COUNTERFACTUAL EXPLAINERS
Stability against topological noise: In this section, we investigate the influence of topological noise on datasets on both the performance and generated explanations of counterfactual explainers. For inductive methods (R (RCEXPLAINER and CLEAR), we utilize explainers trained on noise- free data and only infer the noisy data. However, for the transductive method CF2, we retrain the model using the noisy data.
Figure prrsents the average Jaccard similarity results, indicating the similarity between the coun- terfactual graph predicted as an explanation for the original graph and the noisy graphs at varying levels of perturbations. Additionally, demonsteemosssrates the performance of different explainers in terms of sufficiency and size as the degree of noise increases. This provides insights into how these explainers handle higher levels of noise.
19

---

Published as a conference paper at ICLR 2024
RCExplainer outperforms other baselines by significant margin in terms of size and sufficiency across datasets, as shown in Fig. J However, the Jaccard similarity between RCExplainer and CF2 for counterfactual graphs is nearly identical, shown in Fig. [ CF2 benefits from its transductive training on noisy graphs. CLEAR's results are not shown for Proteins and Mutagenicity datasets due scalability issues. In the case of IMDB-B dataset, CLEAR is highly unstable in predicting counterfactual graphs, indicated by low Jaccard index (Fig. D. Additionally, CLEAR demonstrates high sufficiency but requires large number of edits, indicating difficulty in finding minimal-edit counterfactuals (Fig. D
Overall, RCExplainer seems be the model of choice when topological noise is introduced, and is significantly faster than CF² because it is inductive. Further, it is better than CLEAR as the latter does not scale for larger datasets and inferior in terms of sufficiency and size as well.
Mutagericily
1.0
1.0
3.0
0.2
0.0
0.0
(
CLEAR
Figure Stability of counterfactual explainers against topologiaal noise (Jaceard). We omit CLEAR for Mutagenicity and Proteins as it throws OOM error for these datasets. The absence of markers representing CF2 in the Protein dataset's plot indicates that counterfactual graphs were not predicted at the corresponding noise values by the method. Overall, RCExplainer performs best in terms of the Jaccard index.
Mutagenicity
1.0
Suftrierry
6.0
0.0
(nolse)
RCExplainer
CLEAR
(a) Sufficiency
Mutageniclly
Proteins
200
200
150
150
30
X (nnise)
RCExplainor
(b) Size
Figure J: Performance evaluation of counterfactual explainers against topological noise. We omit CLEAR for Mutagenicity and Proteins as it throws an OOM error for these datasets. RCExplainer is more robust to noise in both metrics: (a) sufficiency and (b) size.
20

---

Published as a conference paper at ICLR 2024
Stability against explainer instances: Table M provides an overview of the stability exhibited among explainer instances trained using three distinct seeds. Notably, we observe a substantial Jaccard index, indicating favorable stability, in the case of RCEXPLAINER and CF² explainers. Conversely, CLEAR fails to demonstrate comparable stability. These findings align with the outcomes derived from Table 5 Specifically, when RCEXPLAINER and CF2 are successful in identifying a counterfactual, the resultant counterfactual graphs are obtained through small number of perturbations. Consequently, the counterfactual graphs exhibit similarities to the original graph, rendering them akin to one another. However, this trend does not hold for CLEAR, as it necessitates a significantly greater number of perturbations.
Table M: Stability against explainer instances. Note that stability with respect to a graph is computable only if both explainer instances find their counterfactual. "NA" indicates no such graph exists.
RCExplainer
CF2
CLEAR
Datasct/ / Seeds
1es2
les3
20s3
1ua2
1es3
2043
1cs2
1063
2va3
Mutagenicity
0.96 #0.06
0. #0.04
0.98 =0 03
0.90 #0.09
0. 0.89 #0.1
0.89 #0. 11
OOM
OOM
0OM
Protcins
0.95 +0.0
0.94 20.0
0.90 0.90
NA
NA
NA
00M
00M
00M
Mutag
0.98 #0.03
0.98 +0.03
+..0
+0.0
+0.0
40.0
0.55 +0.01
0.53
0.54 40.02
IMDB-B
1.0 =0.D
40.01
0.96
0.95 #0.0K
0.28
0.27 20.0
0.28 a0.
AIDS
0.84 #0.04
0.96 #0.06
0.84 +0.04
NA
1.0 =0.0
NA
0.19 #0.02
0.20 +0.03
0.19 40.04
ogbg-molbiv
0.99 #0.03
0.99 #0.00
0.99 =0.04
0.801 +0. 149
0.764
#0.14
0.784
10.144
OOM
00M
00M
Similarly, as additional results, we also present the variations in terms of sufficiency (Table N) and the explanation size (Table [ produced by the methods using three different seeds. In terms of sufficiency, the methods show stability while varying the seeds. However, the results are drastically different for explanation size. Table [ present the results. We observe that RCEXPLAINER is consistently the most stable method while CF² is worse. The worst stability is shown by CLEAR and this observation is consistent with the previous results.
Table N: Stability of sufficiency produced by counterfactual explainers against the explainer instances (seeds). The best explainers for each dataset (row) are highlighted in gray, yellow and cyan shading for seeds 1, 2, and 3, respectively. OOM indicates that the explainer threw an out-of-memory error.
RCExplainer
CF
CLEAR
Dataset/ / Seeds
2
2
2
3
Mutagenicity
0.4 20.06
0.40 =0.05
0.41 #0.05
0.50 #0,05
0.49 =0.06
0.52 20.05
0OM
00M
0OM
Proteins
0.96 20.02
0.96 20.02
0.96 20.02
1.0
1.0
0.98 20.02
00M
00M
00M
Mutag
10.12
0.6
0.55
+0.12
0.9
0.55 #0.1
+0.1
0.65
IMDB-B
0.72 11
=0.11
0.72 #0.11
+0.07
0.82
0.82
088 #0.07
0.96 +0.02
0.002
0.96 #0.02
AIDS
0.91 +0.04
0.91 =0.04
0.91 =0.04 04
0.98
+0.02
1.0
0.99 =0.01
0.84 +0.03
0.80
0.83 =0.04
ogbg-molhiv
0.90 =0.02
0.88 =0.01
0.90 =0.01
0.96 +0.01
0.97 =0.00
0.96 =0.00
0OM
O0M
00M
Table O: Stability of explanation size produced by explainers against the explainer instances (seeds). NA indicates the inability to find a counterfactual. OOM indicates that the explainer threw out-of- memory error. The best explainers for each dataset (row) are highlighted in gray, yellow and cyan shading for seeds 1, 2, and 3, respectively.
RCFxplainer
CF2
CLEAR
Dataset / Seods
1
2
2
3
3
Mutagenicity
1.01 10.19
10.0
1.25 20.0
2.78 10.98
2.85 #1.07
2.95 +1.37
00M
OOM
OOM
Proteins
1.0
1.0
NA
3.0
00M
00M
Mutag
1.1 40,22
1.0
1.0 20.0
1.0 40.0
1.25 20.35
1.0 40000
41.62
15.6 #1.86
19.05 #1.31
IMDB-B B
1.0
1.0
1.0 +0.0
8.57 +4.99
8.29 #4.50
9.01 +5.58
218.62 +0.0
182.25 #0.0
181.38 +0.0
AIDS
1.0
1.0
1.0 10.0
5.25 10.35
NA
6.0 40.0
164.95 147.93
162.32
245.70
185.29 478.92
ogog-mooltiv
1..0
1.0 40.0
1.02 40.42
10.45 +4.43
9.69
#4.18
10.24 +4.87
00M
0OM
00M
Stability against GNN architectures: Table shows the stability of the explainers across different GNN architectures. Similar to factual setting (Table 8), we assess the stability by computing the Jaccard coefficient between the explained predictions of the indicated GNN architecture and the default GCN model. Unsurprisingly, the stability of the explainer highly depends on the dataset.
21

---

Published as a conference paper at ICLR 2024
RCEXPLAINER is also the most stable among all the explainers, and the produced high values indicate that the method is agnostic towards the variations in different message aggregating schemes of the architectures.
We further look into the stability of the counterfactual methods in terms sufficiency (Table Q and the explanation size (Table R across different GNN architectures. The sufficiency results (Table Q show large variations produced by the same method on the same dataset due to the different architectures and message passing schemes. For instance, RCEXPLAINER produces sufficiency of 10 and .93 on the AIDS dataset for GAT and GIN, respectively. In terms of explanation size(Table R). RCEXPLAINER stable against different GNN architectures. However, consistent with previous stability results, CF is more unstable than RCEXPLAINER and the worst stability is shown by CLEAR.
Table P: Stability of counterfactual explainers against the GNN architecture. We report the Jaccard coefficient of explanations obtained for GAT, GIN and GRAPHSAGE against the explanation provided over GCN. The higher the Jaccard, the more is the stability. The best explained for each dataset (row) are highlighted in gray, yellow and cyan shading for architectures GAT, GIN, and GRAPHSAGE, respectively. GRAPHSAGE is denoted by SAGE. NA indicates one both of the architectures were unable to identify a counterfactual for the graphs. OOM indicates that the explainer threw an out-of-memory error.
RCEXplainer
CLEAR
Dataset Architecture
GAT
GIN
SAGE
GAT
GIN
SAGE
GAT
GIN
SAGE
Mutagenicity
0.95 +0.05
0.94 #0.06
0.95 #0.03
0.79 +0.13 13
0.75 #0.16
0.84 #0,10
OOM
0OM
OOM
Proteins
0.88 +0.0
NA
0.88 +0.0
NA
NA
NA
0OM
00M
00M
Mutag
0.94 10.0
NA
0.90 20.02
NA
NA
NA
0.86 10.0
NA
0.72 20.04
IMDB-B
0.99 #0.01
0.98 #0.0
0.98 #0.01
NA
0.93 #0.0
NA
0.60 #0.0
0.70 #0.0
0,76 #0.0
AIDS
0.89 +0.03
NA
NA
0.74 #0.0
0.73 40.11
D.72 20.12
0.25 40.04
0.54 #0.04
D.66 40.04
ogbg-mothiv
0.96 10.02
0.96
10.01
0.96
20.02
0.63 10.12
0.13 10.14
0.61 #0.16
00M
00M
0OM
Table Q: Stability in terms of sufficiency of counterfactual explainers against the GNN architectures. OOM indicates that the explainer threw out-of-memory error. The best explainers for each dataset (row) are highlighted in gray, yellow, cyan, and pink shading for GCN, GAT, GIN, SAGE, respectively, RCExplainer outperforms other basclines majority of the datasets and architectures. CLEAR also is stable in terms of sufficiency but has a much larger explanation size compared to other baselines(Refer Table R
RCEXplaneer
CF¹
CLEAR
Datsset/ Archnecture
OCN
GAT
GIN
SAGE
OCN
GAT
GIN
SAGE
GCN
GAT
GIN
SAGE
Musagmicity
00.00.06
0.344004 +004
0.5 4004
0.59 +0.05
0.50:4005
0,64
0.57 -0.06
00004005
ODM
00M
00M
0OM
Proteins
0.96 #0.02
038 20.04
0.3 50.0
0.66 00.8
1.0:000
1.0000
0.76
O0M
00M
00M
00M
Mitag
20.12
0.79
1.0:000
0.45 #0.19
0.920.12
09
0.45 20.33
0.7
0.55 #0.1
0,8
10:000
0.5 20.1
IMDB-B
0.72
20.02
60.06
0.39 =0.04
0.51 20.07
1..000
20.02
3.96 =0.02
0.64 20.08
10.1
AIDS
0.91
20.04
20.03
0.86 =0.05
0.08 a0.02
20.01
0.96
3.84 =0.03
0.74 20.04
ogbp-molhii
0.90 +0.00
0.50-0.0
0.56 +0.01
0.20 +0.00
0.96 +0.01
0.96 -0.01
0.90
0..0
00M
00M
00M
nOM
Table R: Stability of explanation size produced by explainers against different GNN architectures. OOM indicates that the explainer threw out-of-memory error. NA indicates that the explainer could not identify counterfactual for the graphs. The best explainers for each dataset (row) are highlighted in gray, yellow, cyan, and pink shading for GCN, GAT, GIN, SAGE respectively. RCExplainer outperforms other counterfactual baselines.
GIN
RADE
Maragnncly
0.11
2.0
13
1 8:29
2.8 =: 1.1
2.00
5 255
1.61
COM
DOM
OOM
DOM
10:200
12:00
157 3.25
4.:1:011
2/22 1.22
284
COM
DOM
OOM
DOM
10::00
14
374 $41
NA
AIDS
10::00
10:000
NA
4.33 1:97
22284
200.09 20
Stability to feature noise: Table presents the impact of feature noise on counterfactual explana- tions in Mutag and Mutagenicity. We observe that CF² and CLEAR are markedly more stable than
22

---

Published as a conference paper at ICLR 2024
RCEXPLAINER in Mutag. This outcome is not surprising, considering that RCEXPLAINER exclu- sively addresses topological perturbations, while both CF² and CLEAR accommodate perturbations encompassing both topology and features. In Mutaganecity, RCEXPLAINER exhibits slightly higher stability than CF²
Table S: Stability of counterfactual explainers against feature perturbation on "Mutag" and "Muta- genecity" datasets. We do report results for CLEAR Mutagenicity since it runs out of GPU memory.
(a) Mutag
RCEapaine:
Suffiiinry
Softicemmy
Sullidng
O too s00s))
0.4 # 0.12
1.10 # 0.22
1.0 # 0.0
0.30 0.12
1.0 0.0
1.0 0.0
0.66 = 0.1
17.15
1.02
1.0 # 0.0
1.0
MA
NA
6.6 0.2
2:17 0:331
0.19 0.0
0.55 0.1
16.35 1.65
0.98 0.01
0.75 2 0.22
10 2.00
NA
0:5 1 0.18
1.06 0.00
NA
0.55 1 0.1
18:1:::000
0.55 2:0.0
1.0.1: 0.0
NA
NA
0.6.2 0.3
1:0 1:0:0:00
0.29 0.0
0.55 1:55::00 0.1
19:14::2.0 2:9.
0.57 2:0.00
1.0:1: 0.0
NA
NA
0.6::.0.2
2.8 2.00
0.29 $ 0.0
0.55 0.1
14.7 1.78
0.58 1: 0.00
1.0:::0. 0.0
NA
NA
0.8
1.0
NA
9.50 0.1
16.00 4: 2.48
0.54
(b) Mutagenicity
RCEXpaaiee:
Suffssincy
Suffscency
too aoss))
0.4 # 0.05
1.01 = 0.10
1.0 2 0.0
0.00 a 0.00
2.78
a 0.98
1.0 0.0
10
0.44 0.04
1.01 0.19
0.96 2: 0:04
0.49 0.94
2.11 1.00
0.92 = 0.06
20
0-417 3: 0.06
10:2:00 0.0
0.35 2 0.04
0.53 0.06
1.73 2 0.94
0.88 0.08
30
0.50
0.04
1.0 0.0
0.94
4: 0.04
0.61
0.04
1.68 2: 0.91
0.60 0.00
40
0.52
0.05
1.0 0.0
0.90 0.06
0.54 0.05
1.47:2000 0.773
0.87 0.00
50
1.0: 0.0
0.90 0.06
0.67
0.01
1.54 8:
0.86 0.08
Mutagenicity
Proteins
0.08
Necessity
0.4
0.06
0.3
0.4
0.2
0.20
0.45 0.5
0.40
Necessty
0.15
0.30
0.30
0.2
0.25
0.1
0.15
0.00
0.10
(#edges in the explanation)
PGExpleiner
TAGExplainer
RCExplainer
GNNExplainer
GEM
SubgraphX
Figure K: Necessity of various factual explainers against the explanation size. The necessity increases with the removal of the explanations.
23

---

Published as a conference paper at ICLR 2024
D NECESSITY: RESULTS FOR SEC. 4.3
For necessity, we remove explanations from graphs and measure the ratio of graphs for which the GNN prediction on the residual graph is flipped. We expect that removing more explanations will lead to more necessity: however, we do not necessarily expect necessity to be higher because our factual explainers are not trained to make the residual graph counterfactual. Fig. K presents the necessity performance on six datasets for all factual methods with varying explanation sizes from I to 10. The trend aligns with our expectations, the removal of more explanations increases the necessity. The value of necessity varies between datasets. Proteins and IMDB-B datasets have graphs with larger sizes (in terms of the number of edges), which aligns with the small necessity score. On the other hand, datasets with relatively smaller graphs have higher necessity scores. Note that our factual methods do not optimize residual graphs be counterfactuals; this might be another reason for the low values.
REPRODUCIBILITY RESULTS FOR SEC.
Reproducibility can measured two different ways. (1) Retraining using only explanation graphs called Reproducibility+* (2) retraining using only residual graphs called Reproducibility"" Both metrics is a ratio of an GNN accuracy compared to the original GNN accuracy. We provide the math definitions in Table In figures, separated SubgraphX to independent table, because could only obtain explanations of test graphs for SubgraphX (refer to our disclaimer in Sec, A.4)
Mutagenicity
Mutag
0.95
0.90
1.025
0.85
1.000
0.8
0.80
0.975
0.75
0.950
0.6
0.70
0.925
0.65
0.900
0.60
0.875
IMDB-B
AIDS
NC11
1.00
1.00
0.90
0.95
0.96
0.85
0.90
0.94
0.92
0.85
0.75
0.80
0.75
0.86
0.65
9
10
8
9
10
size (#edges in the explanation)
PGExplainer
TAGExplainer
CF2
RCExplainer
GNNExplainer
GEM
Figure L: Reproducibility+ of factual explainers against size. Performance tends to rise with more edges in the explanations; however, small number of edges does not guarantee performance of 1.0.
explanation)
Munagenicity
0.02
1.07
0.02
1.05
0.02
1,03 0.02
0.97
Mulag
0.88
0.43
0.43
0.76 0.5
1,08
0.11 0.52
0.22
0.45
1.08 1.0.
0.36 1.4.3
0.97 0.0.2
1.08 1.00
IMDB-B B
1.07
0.16
1.1.1
1.05 1 0.15
1.08 0.06
1.00 000:1:00 0.08
1.07 1 0.08
1.05 0.06
1.06 1.0.6
1.00 0.0.5
1 1.00
AIDS
102
10200 0.0
1.0 0.
0.000.0
10 0.01
100 0.01
0.99
2: 0.01
10 0.000
1.0 0.
10:000000
NCTI
1.05-000 0.04
1.00 + 0.03
1.09 + 0.03
1,08 0.02
1.00 + 0.02
1.00
0.02
1,07 + 0.03
1.07 +0003
1.05 0.03
101 +.04
Table Reproducibility* in SubgraphX. Since we use small number of graphs for SubgraphX, the variance of the results very high, thus unreliable.
24

---

Published as a conference paper at ICLR 2024
Figure C Table illluttrae the Reproducibility" performance of seven factual methods against the size of explanations for six datasets. Reproducibility increases with more edges in the explanations for the most cases, expected. However, reaching score of 1.0 is challenging the most crucial edges. This suggests that explanations do not capture the full picture for GNN predictions.
when selecting
Figure M and Table U illustrate the Reproducibility" performance of seven factual methods against the size of explanations for six datasets, Reproducibility remains high even when the most crucial edges from the graphs are removed. This demonstrates that the explainers hardly capture the real cause of the GNN predictions.
Mutagenicity
Proteinss
Mutag
1.00
0.98
Regreducibiitty
1.00
0.94
0.8
0.92
0.96
0.7
IMDB-8
AIDS
NC11
1.005
1.02
1.000
1.06
Reproductbility
1.04
1.00
0.995
1.02
0.98
0.990
1.00
0.98
0.985
0.96
0.96
0.980
0.94
2
10
10
(#edges the explanation)
PGExplainer
TAGExplainer
CF2
RCExplainer
GNNExplainer
GEM
Figure M: Reproducibility" of factual explainers against size. Even when the most crucial edges are taken out, the performance still remains close to 1.0.
Size (Redges the explanation)
Datasett
5
10
Mutagenicity
1.06
0.05
1.01 1. 0.02
1.01 1. 0.00
1.01 1. 0.00
1.0 0.05
10.1 0.05
1.01 1.1:1000 0.03
0.99 1.0.0
0.03
0.99 1
Mulag.
1.8 0.1
1 2: 1131
1137 2 0.32
1 2: a.
0.97 à: 0.32
0.97 0.32
108 0.0
1.08 2: 0.
108 2:00
1.08 4: 0.00
IMDB B
0.82-122 0.28
0.96
0.86
0.27
0.85 1
0.86 0.28
0.82 0.82
0.8
0,85 0.225
0.85
AIDS
1.0
1.0 0.01
1.0
1.0
10=
0.99 0.01
1.0+0.m
1.00000
0.89
Table U: Reproducibility" in SubgraphX. Since we use small number of graphs for SubgraphX, the variance the results are very high, thus unreliable.
VISUALIZATION OF EXPLANATIONS
In Figs. N and O we engage visual analysis of the explanations provided by various GNN explainers. The graphs presented in these figures represent mutagenic molecules sourced from the Mutag dataset. Several insights emerge from this analysis.
Factual: The mutagenic attribute of the molecule in Fig. stems from the presence of the NO₂ group attached to the benzene ring Ying et al. (2019b), 19); Debnath et al. [1991). As a result, the optimal explanation entails pinpointing this specific benzene ring in conjunction with the NO₂ group. Notably, we observe that while certain explainers identify fragments of this subgraph, with CF2 achieving the highest overlap, many also highlight bonds originating from regions outside the authentic explanatory context. Adding to the intrigue, the explanation offered by RCEXPLAINER stands out due to its compactness, resulting in commendable statistical performance. However, this succinet explanation
25

---

PGExplainer Published as a conference paper at ICLR 2024
lacks meaning in the eyes of domain expert. Consequently, pressing need arises for real-world datasets endowed with ground truth explanations, a resource that the current field unfortunately lacks. Counterfactuals: Fig. Oillustrates two molecules, with Molecule 1 (top row) being identical to the one shown in Fig. N The optimal explanation involves eliminating the NO2 component, a task accomplished solety by CF2 in the case of Molecule 1. While the remaining explanation methods can indeed alter the GNN prediction by implementing the changes described in Figure two critical insights emerge. First, statistically, RCEXPLAINER considered better explanation than C1² since its size is compared to 3 of CF However, our interaction with multiple chemists clearly indicated their preference towards CF² since eliminates the entire NO2 group. Second, chemically infeasible explanations are common as evident from CLEAR for both molecules and CF² in molecule 2. Both fail to adhere valency rules, a behavior also noted See.
CF2
RCExplainer
GEM
SubgraphX
GNNExplainer
TAGExplainer (1)
"AGExplainer (2)
Figure N: Visualization of factual explanations mutagenic molecule from the Mutag dataset. The explanations contain the edges highlighted in red.
Moleoule
Motecule
CF2
RCExplainer. (Failed to find counterfactual)
CLEAR
Figure O: Visualization of counterfactual explanations on Mutag dataset. Edge additions and deletions are represented by green and red colors respectively.
G ADDITIONAL EXPERIMENTS ON SPARSITY METRIC
Counterfactual explainers: Sparsity is defined as the proportion of edges from the graph that is
retained in the counter-factuse Yuan al, (2022); value close to is desired. In node classification, we compute this proportion for edges in the No. i.c., the Ê-hop neighbourhood of the target node v. We present the results sparsity metric node and graph classification tasks in Table V and W
26

---

Published as a conference paper at ICLR 2024
LF-GGNEXPPAINEE continues outperform (Table V). The results are consistent with our earlier results in Table Similarly, Table [ shows that RCExplainer continues to outperform in the case of graph classification (carlier results show similar trend in T
respectively. For node classification,
Factual explainers: For experiments with factual explainers, report results of the necessity metric on varying degrees of sparsity (Recall Fig. K). Note that size acts as a proxy for sparsity in this case. This is because sparsity only involves the normalized size where it is normalized by the number of total edges. So sparsity can be obtained by normalizing all perturbation sizes in the plots to get the sparsity metrie. For counterfactual explainers, we do not supply explanation size as a parameter. Hence, computing the sparsity of the predicted counterfactual becomes relevant.
Table V: Results on sparsity of counterfactual explainers for node classification. CE-GNNExxpaiierr consistently produces the best results that are shown in gray.
Method/Dataset
Tree-Cycles
Tree-Grid
BA-Shapes
UT-GNNEEPPAAIH AINER
0.93 #0.02
0,95 40.03
0.99 +0.00
CF2
0.52 #0.14
0,58 +0.14
0.99 +0.00
Table W: Results on sparsity of counterfactual explainers for graph classification. Best results are shown in gray. RCEXPLAINER consistently outperforms the other methods.
Mathod/Dataset
Mutagenicity
Matag
Proteins
AIDS
IMDB-B
oghg- molhi
RCExplainer
0.96 +0.00
0.94 #0.01
0.94 +0.02
0.91 +0.00
0.98 #0.00
0.96 +- 0.00
CF
0,90 #0.01
0.94 =0.0
NA
0.99 20.01
0.89 #0.04
0.62 #0.05
CLEAR
20.06
H TAGEXPLAINER VARIANTS
TAGExplainer has two stages. We define TAGExplainer (1) as when we apply only the first stage and get explanations, whereas TAGExplainer (2) applies both stages. Figure compares performance of these two variants.
I FACTUAL EXPLAINERS ON OGBG-MOLIIV
Figure R demonstrates a new dataset OGBG-Molhiv for three factual explainers. On this dataset, three factual methods are close to each other in terms of sufficiency performance.
J EXISTING BENCIMARKKING STUDIES ON GNN EXPLAINABILITY
GraphFrameX Amara et al. (202)) and GraphXAI Agarwal et al. (2023) represent two notable benchmarking studies. While both investigations have contributed valuable insights into GNN explainers, certain unresolved investigative aspects persist.
Inclusion of counterfactual explainability: FraphFrame and GraphXAI have focused factual explainers for GNNs. Prado-Romero et al.] (2023) has discussed methods and challenges, but benchmarking on counterfactual explainers remains underexplored.
Achieving Comprehensive coverage: Existing literature encompasses seven perturbation-base factual explainers. However, GraphFrameX and GraphXAI collectively assess only GnnEx- plainer Ying et al. (2019b). PGExplainer Luo et al. (2020), and SubgraphX Yuan et al. (2021). Empirical investigations: How susceptible are the explanations to topological noise, variations in GNN architectures, or optimization stochasticity? Do the counterfactual explanations provided align with the structural and functional integrity of the underlying domain? To what extent do these explainers elucidate the GNN model as opposed to the underlying data? Are there standout explainers that consistently outperform others in terms of performance? These are critical empirical inquiries that necessitate attention.
27

---

Published as a conference paper at ICLR 2024
Mutagenicity
Proteins
Mutag
1.0
0.85
0.9
0.90
Sufficiency
0.80
0.8
0.7
0.75
0.80
0.5
0.75
0.4
IMDB-B
AIDS
NC11
0.800
0.80
0.95
Sufficleccy
0.75
0.750
0.90
Graph-SST2
DD
REDDIT-B
1.000
0.625
0.395
0.52
Sufticlency ency
0.900
0.985
0.50
0.900
0.525
0.48
0.500
0.475
0.46
0.450
10
15
20
25
10
15
20
25
10
15
20
25
size (#edges in the explanation)
TAGExplainer (1)
TAGExplainer (2)
Figure P: Sufficiency of TAGExplainer variants against size. Applying the second stage does not help much for TAGExplainer.
28

---

Published as a conference paper at ICLR 2024
Mutagenicity
REDDIT-B
0.8
Proteins
0.6
0.2
PGExplainer
DD
Mutag
TAGExplainer
CF2
RCExplainer
GNNExplainer
GEM
SubgraphX
Graph-SSTZ
IMDB-B
NCI1
AIDS
Figure Q: Spiderplot for sufficiency performance averaged for different sizes of explanations. Even though there is no clear winner method, GNNEXPLAINER and RCEXPLAINER appear among the top performers in the majority of the datasets. We omit those methods for dataset that throw an out-of-memory (OOM) error and are not scalable.
@gbg_mollts
0.990
0.988
Sufficiency
0.986
0.984
0.982
0.980
15 size (#edges the explanation)
PGExplainer
TAGExplainer
RCExplainer
GNNExplainer
Figure R: Sufficiency of the factual explainers against the explanation size for ogbg-molhin dataset.
29

---

Published as a conference paper at ICLR 2024
Instance-specific
GNNExplainer
GC/NC
Generalization
Data
RCExplainer
Task
*
TAGExplainer
Reasoning
CF
NC
CF-GNNEXplainer
Task
GC
RCExplainer
Figure S: Flowchart our recommendations of explainers in different scenarios. Note that "F", "CF", "NC", "GC", and "*" denote factual, counterfactual, node classification, graph classification, and generalized tasks respectively.
K RECOMMENDATIONS IN PRACTICE
The choice of the explainer depends various factors and we make the following recommendations.
For counter-factual reasoning, we recommend RCExplainer for graph classification and CF-GNNExplainer for node classification.
For factual reasoning, if the goal is do node graph classification, need to first decide if we need an inductive reasoner or transductive. While an inductive reasoner is more suitable we want generalize large volumes of unseen graphs, transductive suitable for explaining single instances. In case of inductive, we recommend RCExplainer, while for transductive GNNExplainer stands out the method of choice. These two algorithms had the highest sufficiency on average. In addition, RCExplainer displayed stability in the face of noise injection.
For different task generalization beyond node and graph classification, one can consider using TAGExplainer.
In high-stakes applications, we recommend RCExplainer due to consistent results across different runs and robustness noise.
For both types of explainers, the transductive methods are slow. So, if the dataset is large, it is always better to use an inductive explainer over transductive ones.
While the above is guideline, emphasize that there is one-size- fits-all benchmark for selecting the ideal explainer. The choice depends on the characteristics the application in hand and/or the dataset. The above flowchart takes these factors into account streamline the decision process. We have now added flowchart to help the user in selecting the most appropriate. This recommendation has also been added flowchart (Fig. S).
30


Reviews:
[{"review_id": "9dJsGYaaIa", "reviewer": "Reviewer_PPUE", "summary": "The authors applied a benchmark evaluation to measure various GNN explainers' performances. A brief review of GNN explainer classification is introduced, then seven perturbation-based factual explainers and four perturbation-based counterfactual explainers are selected to conduct the benchmark test. Stability, necessity, reproducibility, feasibility, and comparative analysis are chosen to be evaluation criteria.  Size, fidelity, and accuracy are regarded as metrics. Finally, after the empirical evaluation, the authors provided some insights and directions expected to lead researchers enhance the overall quality and interpretability of GNNs.", "questions": "Authors may want to try to offer some new solutions to the discovered limitations of existing GNN explainers. Finding out these limitations is just a start of a research work. For instance, the feasibility concerns about counterfactual explainations appear due to the deviations in topological distribution. Authors can keep working in this direction and find out some methods to improve feasibility.", "limitations": "", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1) A comprehensive introduction about how GNN explainers work and how GNN explainers are classified is provided.  Clear Figure 1 demonstrates research interest of the paper.\n2) Various perturbation-based GNN explainers are selected to evaluate their performances, increasing the soundness of conclusions. The selected explainers are published from 2003 to 2022, covering the development of GNN explainers for decades.Multiple runs were conducted to deal with randomness.\n3) Detailed appendix proves the rigor of experiments.  Comparative analysis is conducted to reveal some kay outcomes' features.  Many clear figures demonstrate the reasonability of conclusion.", "weaknesses": "1) Lack of creativity and significance: The authors conducted an evaluation to measure many explainers' performances, but did not come up with a novel solution to overcome the discovered challenges.  Also, the conclusions are not insightful enough with further analysis. Based on this reason, it is hard to regard this paper as a research paper.\n2) Poor layout: The layout of words and tables is too dense, such as Table 1, 4, 5, and 8. Numbers inside table are too small and hard to read.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KN0B5PO2l8", "reviewer": "Reviewer_NT8w", "summary": "This work presents a benchmark for perturbation-based GNN explanation methods. Within the benchmark, this work provides a comprehensive comparison between both the factual and counter-factual explanation methods. This work conducts the comparison on various datasets, including 10 graph classification and 3 node classification ones. The experiments compare 7 GNN explanation methods in terms of the size of the perturbation, the sufficiency (percentage of the subgraphs that yield the same results as using full graph), and accuracy (the percentage of correct explanation). The results give a relative comparison among the seven methods. Furthermore, this work conducts a comparison of the methods regarding the stability with regard to noise injected into the underlying graph, different seeds of training explanation models, and variations in model architectures. Lastly, this work also provides an open-sourced codebase, making the benchmark accessible for public use.", "questions": "- It would be better to clearly define how the sufficiency score is computed. \n- Do the authors have any explanation for why the RCExplainer and the GNNExplainer have the highest sufficiency scores? It would be helpful to provide a more structured and conceptual comparison between the explanation methods. \n- What is the definition and scale of the noise shown in Figure 3?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This work provides an extensive evaluation of perturbation-based GNN explanation methods in terms of both performance and stability. The comprehensive results give a quantitative comparison of existing explanation methods. \n- Besides performance, this work also considers the stabilities of GNN explanation methods. This provides a new aspect for evaluating GNN explanation algorithms. \n- This work provides an online repository of the proposed benchmark, making the evaluations accessible for a broader range of users.", "weaknesses": "- The conclusions from the empirical comparison are not clear. It would be better to summarize the conclusions from the empirical comparison and provide conceptual insights, such as how would the results guide the future design of GNN explanation methods. \n- Discussion of the existing works needs more structure. Current discussion of the related works are based on the summary for each method. It would be better to provide more structures of the current works, such as what methods the existing ones share in common. \n- Details of the empirical studies need to be further elaborated. Please see Questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "E5AjAGbDrr", "reviewer": "Reviewer_ac1w", "summary": "This paper comprehensively studies the existing methods of explaining GNN predictors, including factual explainers and counterfactual explainers. The investigation is carried out in terms of stability, necessity/reproducibility, and feasibility for counterfactual explainers. And some conclusion of these investigations is obtained by extensive empirical evaluations.", "questions": "The notations of A(G_s) in Equation 1 should be A(G').\nIn definition 2, the prediction of the perturbated graph is defined to be different from the counterpart of the original graph. I think this is valid for binary classification. For multi-classification problems, the counterfactual reasoning should be associated with a pre-assigned label.\nThe definitions of fidelity, necessity, and reproducibility seem to be vague. The fidelity in section 4 (under figure 2) is not clear, \"some works have used the term fidelity instead of sufficiency\" has no citations. The authors do not clearly give the definition of necessity and reproducibility and only give the intuition of these metrics (e.g. measures if ). This makes it difficult to figure out the metrics.\nThe measurement of feasibility which is defined as the number of connected graphs is somehow one-sided. Are there other measurements that can characterize the topological properties? And the relationship between defining the similarity with the topological properties of the test dataset and the feasibility measurement should be discussed and justified.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "This paper investigates a critical problem of GNN predictors, that is the explainability pertaining to GNNs. Specifically, the counterfactual explanation is an important and meaningful explainer, which is worthy of studying. This paper fulfills the vacancy of the research on benchmarking it. The empirical evaluation is extensive and comprehensive. Therefore, the resulting conclusions from the experiments are solid and reliable.", "weaknesses": "I believe there is some space for improvement in the paper's presentation. I suggest some important metrics, such as necessity and reproducibility can be expressed in mathematical equations. This can bring convenience for readers to understand the concepts.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VecQTDftU0", "reviewer": "Reviewer_aTj3", "summary": "This paper presents a benchmarking study on perturbation-based explainability methods for GNNs and aims to evaluate a wide range of explainability techniques.", "questions": "Please see the weaknesses stated as above.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1、This paper provides a detailed and comprehensive description of the existing explainers for GNNs and compares different explanation methods in a clear way. \n2、This paper provides a large of experiments to evaluate algorithms for both factual and counterfactual reasoning explanation methods and considers the different perspectives that may affect the performance of the explanations including topology, model parameters, and model architectures.\n3、The metrics for evaluating the explainers for GNNs are reasonable.", "weaknesses": "1、Whether adversarially adding the number of edges has an impact on the sufficiency of the factual explainers leading to different experimental results in Figure 2 or Table 4\n2、Most experimental results do not seem to provide explanations about the experimental phenomena and comparisons of the advantages and disadvantages of different explanation methods. For example, why the stability of CF^2 has dropped significantly on the IMDB-B and AIDS datasets in Fig. 3.\n3、For the experimental results of stability against topological noise, why are the GEM and SubgraphX not used.\n4、There are differences between different factual explainers on different datasets. Is there a benchmark to select a proper explainers in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)