GraphTrail: Translating GNN Predictions into Human-Interpretable Logical Rules
Authors: Burouj Armgaan
Manthan Dalmia
Sourav Medya
Sayan Ranu
Venue: NeurIPS 2024 poster (2024)
Keywords: Graph Neural Network
Explainability
Global Factual Explanation
Symbolic Regression
Computation Trees
Primary area: graph_neural_networks
TL;DR: We generate formula based global explainations of graph neural networks using symbolic regression over computation trees identified through Shapley values.

Abstract: Instance-level explanation of graph neural networks (GNNs) is a well-studied area. These explainers, however, only explain an instance (e.g., a graph) and fail to uncover the combinatorial reasoning learned by a GNN from the training data towards making its predictions. In this work, we introduce GraphTrail, the first end-to-end, global, post-hoc GNN explainer that translates the functioning of a black-box GNN model to a boolean formula over the (sub)graph level concepts without relying on local explainers. GraphTrail is unique in automatically mining the discriminative subgraph-level concepts using Shapley values. Subsequently, the GNN predictions are mapped to a human-interpretable boolean formula over these concepts through symbolic regression. Extensive experiments across diverse datasets and GNN architectures demonstrate significant improvement over existing global explainers in mapping GNN predictions to faithful logical formulae. The robust and accurate performance of GraphTrail makes it invaluable for improving GNNs and facilitates adoption in domains with strict transparency requirements.

GRAPHTRAIL: Translating GNN Predictions into Human-Interpretable Logical Rules
Burouj Armgaan, Manthan Dalmia
Sourav Medya Department of Computer Science University Illinois, Chicago, USA
Department of Computer Science & Engineering
IIT Delhi, India
csz228001 @id in.in Santhanddalmia@@yre com
medya@uic.
Sayan Ranu
Department of Computer Science & Engineering and Yardi School of AI IIT Delhi, India sayanranu@cse iitd. in
Abstract
Instance-level explanation of graph neural networks (GNNS) is well-studied area. These explainers, however, only explain an instance (e.g.. graph) and fail to uncover the combinatorial reasoning learned by a GNN from the training data towards making its predictions. In this work, we introduce GRAPUTRAII, the first end-to-end, post-hoc, global GNN explainer that translates the functioning of a black-box GNN model to a boolean formula over the (sub)graph- concepts without relying on local explainers. GRAPHTRAIL unique in automatically min- ing the discriminative subgraph-level concepts using Shapley values. Subsequently, the GNN predictions are mapped to a numan-interpretable boolean formula over these concepts through symbolic regression. Extensive experiments across diverse datasets and GNN architectures demonstrate significant improvement over existing global explainers in mapping GNN predictions to faithful logical formulae. The bust and accurate performance of GRAPHTRAIL makes it invaluable for improving GNNs and facilitates adoption in domains with strict transparency requirements.
Introduction and Related Works
GNNS have witnessed widespread adoption for graph-level prediction tasks due to their impressive performance [35, 14, 46, 11, 41, 18, 38, 32, 5, 12, 53, 22]. Unfortunately, like other deep-learning models, GNNS are considered black boxes due to their lack of transparency and interpretability. This lack of interpretability presents significant barrier to their adoption in critical domains such as healthcare, finance, and law enforcement. Additionally, the ability to explain predictions is crucial for understanding potential flaws in the model and generating insights for further refinement.
Existing Works: To introduce interpretability of GNNs, several algorithms have been proposed in the literature [23]. Fig. in the Appendix, which was originally presented in [23], and now updated by us with more recent works, presents the taxonomy of GNN explainability research. As observed, vast majority of explainers focus on instance-level explanations.
Instance-level (or local) explainers [55, 29, 42, 58, 15, 57, 27, 45, 25, 3, 51, 26, 6, 19] take graph input and identify components within this graph-succh -scch subgraph- thht maximally influence the prediction made by model. This instance-level focus limits its ability to extract patterns utilized by GNNS at global level across multitude of graphs and how these patterns combined into single decision-making rule. The objective of our work to develop an end-to-end
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

global explainer that (1) mines the subgraph concepts used by a black- box GNN model, and then (2) uncovers the boolean logic used by the GNN over these concepts to make its predictions.
Works on global GNN explainers are limited [56, 16, 54, 2]. XGNN [56] and GNNInterpreter [50] generative-moded
based global explainers. Both generate graph that maximally aligns with specified class label. While this generated graph likely contains important features used by the GNN in making its predictions, it may not actually be present in the dataset, limiting its utility for analyzing specific predictions. Additionally, it does not produce a human- interpaatteeree rule explaining the class attributions made by the GNN. Finally, XGNN [56] requires Nomain-specifee validity-rules as input, which affects its generalizability and results in inferior performance [2]. Another work [54] evaluates which base concepts are detected by the neurons of GNN model during predictions and their relative importance. These concepts can be subgraphs or node-level properties, such as degrees. However, this method lacks the ability to automatically mine the concepts. More importantly, this method also does not generate
interpratterre rule for the decision-making process of the GNN.
The closest work ours is GEGEXPLAINER [2], which shares the objective of providing a global explanation of the GNN through a boolean formula over subgraph-level concepts. However, there are significant limitations that need to be addressed:
Dependency on instance-level explainers: GEXPLAIIN does not mine the subgraph concepts in an end-to-end manner. Instead, it relies on an instance-leve explainer (e.g. PGEXPLAINER [29]) to provide these concepts, over which it searches for the combinatorial formula mapping to the GNN predictions. This dependency creates disconnect with the objective, as instance-level explainers lack a global understanding of the model. Our proposed approach develops an end-to-end pipeline that mines concepts based on global trends.
Lack of interpretability due to vector-level concepts: In GLGEXPLAINER, each concept in the formula corresponds to a feature vector and not a subgraph. These vectors represent the embedding of a cluster of subgraphs generated by the instance explainer. Hence, in its original form, the formula is not human-intern iuman-interpretable. To convert into a intaaninterprettble formula, GLGEXPLAINER randomly selects subgraph from the cluster, assuming all subgraphs in cluster are similar. Our investigation ($ 4) reveals that this assumption is rarely true in practice, compromising both interpretability and efficacy.
Lack of robustness: GLGEXXPLIINE shows significant variation in the formula based on the training split used. As our analysis in $ 4 reveals, due to the reliance instance-level explanations, even when data are drawn from the same distribution, the base concept candidates vary, and consequently does the eventual formula.
At this juncture, we note that our work is distinct from the line of research on explainable GNNs [61, 10, 34). Explainable GNNS are designed make explainable predictions rather than explaining the predictions of a black-box GNN.
Contributions: In this work, we present an end-to-end, post-hoc, global GNN explainer called GRAPHTRAIL (TRAnslating GNN Prediction into human-Interprettalle Logical Rules)!, which addresses the limitations outlined above. Specifically,
We formulate the problem of translating a message-passing GNN model for graph classification into huwan-uitteettt -umman-iterrpretable logic formula over subgraph concepts. Unlike existing works, in our formulation, the concepts are not assumed to be an input generated through a decoupled algorithm.
Problem formulation:
Novel methodology: We develop GRAPHTRAN which uses mix of several innovative insights. First, GRAPHTRAUE exploits the fact that message passing GNN decomposes a graph into set of computation trees. This enables GRAPHTRAI to limit the exploration of concepts from an exponential subgraph search space to a linear space of computation trees. The global impact of computation trees is assessed using Shupley values, and then mapped to a boolean formula over concepts using symbolic regression.
Empirical analysis: Extensive experiments across a diverse set of datasets, GNN architectures and pooling function, demonstrate GRAPHTRAIL to significantly surpass existing global explainers in efficacy, human- uuman-interpretabblity data efficiency, and robustness.
'Triil also implies pathway of clues, which aligns with our problem

---

2 Preliminaries and Problem Formulation
Definition (Graph). A graph is defined as 9 = (V, E, X) over a node set V, edge set E {(u, v)
u, E v} and a node feature matrix = {x, v E Vj where X. E IRd the set of features characterizing each node.
Two graphs are termed identical if they are isomorphic to each other.
Definition 2 (Graph Isomorphism). Graph G1 isomorphic graph G2 (denoted as 91 2 G2)
if there exists a bijection between their node sets that preserves the edge connectivity and node
features. Specifically, G1 G2 - 3f V1 - 122 such that: (1) f is a bijection, (2) X. X(()), where x, E ((r) E V2 and (3) v) & if and only if (f(u), f()) E Ez.
Graph 91 is subgraph isomorphic to G2, denoted as 91 S G2. if f is an injection and condition (3) is modified to (u, E & (f(u), f(w)) Ez.
Definition 3 (Graph Classification). In graph classification, we are given a set of train graphs Der -GG,,... Gm.) j. where each graph Gi is lagged with class label V. from the set (Yi..... Ne.. The objective is to train a GNN model & such that given a graph with an unknown class label, the label prediction error is minimized.
Error may be measured using any of the known metrics such cross-entropy loss, negative log- likelihood, etc. Hereon, we implicitly assume & to be a meessgge-passinn GNN [22, 14, 46, 53]. We assume the GNN & returns c-dimensional distribution ability of the j-th class, and (())* = arg max .ef { (G))) denotes the predicted class label.
the class labels, where & (()); is the prob-
Definition 4 (Concepts [2, 21]). Concepts refer semantically meaningful units of information within the data that humans use to analyze and make decisions about that dataset. In the context of graph classification, these concepts correspond subgraphs.
Problem (Global GNN explanation through boolean logic over concepts). Let D be a set of graphs, where each graph is labeled with class from the set ()/,,.. ..ec. Given trained GNN D our objective is to learn a set of e boolean formulas Ui.... :c)). over subgraph-level concepts such that for any graph G. if (())* = Y: then [i( TRUE and vj 4 [2( =FASSE. The candidate spuce of concepts includes all unique subgruphs of the dataset, i.e., C = (S 1 C.
The proposed problem formulation surfaces two key challenges:
1. How do we extract the concepts? Concept extraction poses a significant challenge due to the exponential size of the candidate space. In the worst case, a graph with n nodes can have 2 possible subgraphs. Furthermore, if there are n subgraphs in the dataset, identifying the unique subgraphs requires performing O(n²) graph isomorphism tests. The computation cost of graph isomorphism grows exponentially with graph size.
How do we uncover the boolean logic over the concepts? The number of boolean formulas associated with set of symbols (concepts) increases exponentially with the size of the set. Hence, the scalability challenge further exacerbated.
3 GRAPHTRAIL: Proposed Global Explainer
Fig. presents the pipeline of GRAPUTRAIL GRAPHTRAIL builds on the observation that any message passing GNN decomposes a graph of n nodes into n computation trees. Consequently. only the subgraphs corresponding to these computation trees are processed by the GNN and the rest of the subgraphs are irrelevant to the GNN'S 's predictions. This property allows us to reduce the candidate space size from exponential to linear. Subsequently, the impact of each of the computation trees is assessed through its Shapley Value [43], and the top-k trees are sent to the logic formulator. The Boolean logic revealed by the symbolic regression over these computation trees. Symbolic regression aims to discover concise closed-form mathematical equations that best fit a given set of data [24, 31]. In our context, we constrain the regressor over computation trees with boolean operators and fit to the predictions of GNN. We next elaborate on each of these steps.
3.1 Computation Framework of Message-passing GNNS
GNNS aggregate messages layer by layer. If x, E RRFF the input feature vector for node e E V. then the 9th layer representation of node v is set to h. Xy- In each of the subsequent layers f.
3

---

Graphs
CTrees
Canonization
Unique CTrees
AJAA ANa
Blackbox
Di
Unique
Shap Computation
Concept Vectors
CTree Embeddings
Logical Formula
Filter
Filtered Concepts
Symbolic Regression
Figure 1: Pipeline of the GRAPHTRAIL algorithm.
GNNS draw messages from their neighbors N₂ = {u ( E)} and aggregate as follows:
(u) MsG b
(h Ah
(1)
m. AGGREGATE
(2)
h (h
Here, MsG' and AGGREGATE" can be either pre- pre-defined functions (e.g.. MEANPOOL) or neural networks (e.g., GAT [46]). {-} denotes multi-set since the same message may be received from multiple nodes. The gth layer representation of node v is the embedding generated by passing the aggregated messages through MLP. Finally, the representation of the entire graph is computed as:
hg PooL ((h Ve E V})
(4)
Here, POOL could represent aggregation functions such as MEANPOOL, SUMPOOL, etc., and L is the total number of layers in the GNN. Following the computation of the graph embedding, is mapped to distribution (G) over all class labels by passing h& through MLP.
3.2 Mapping Concepts to Rooted Computation Trees
The message passing architecture of GNNs limits the embedding computation of node within the computation tree rooted at v.
Definition 5 (Rooted Computation Tree T.). computation tree, also known as a receptive field, is fundamental concept in GNNs that describes how information propagates through the graph during the neural network's operation. Formally, given graph G = (V, E, X), a node v E V, and the number of layers L in the GNN, the computation tree T rooted at is defined as follows:
Enumerate all paths (including those with repeated vertices) starting from and extending up to L hops away.
Merge these paths into tree structure where: the root is always and ii) two nodes from different paths are merged if: a) they are at the same depth in their respective paths, and b) all their ancestors in the paths have already been merged. This tree represents how information flows to node v during I, rounds of message passing in the GNN.
Fig. 2 illustrates the process of constructing the computation trees. We now highlight their properties that enable us to compress and process the concept space in tractable manner.

---

Va
For Po,
My Ui
My Mg, M3
Pa P2. V1
uy Ug. Uq
U1
Pg Par Vo
My Mgg M4
M2
My P2. V3
M4 Ugg Mg
51
Paths from 91
Computation tree
Paths from M1 E G2
G2
144
Figure 2: The figure illustrates the process of constructing the computation trees of nodes E Gr and U1 E G2 for L The colors of the nodes represent the node labels. Note that although V1 and U1 are embedded in non noo-isooooppiic L-hop neighborhoods, their computation trees are isomorphic.
Lemma 1. In an L-layered GNN, the computation tree To is sufficient to compute node embedding h. Vu E V.
Proof. In single layer of message-passing, node receives messages from each of its immediate neighbors. Over layers, v collects messages from nodes within L hops. The computation tree T. contains all such paths of length up to I, and hence is sufficient to compute h.-
Lemma 2. T T
h h
Proof. The expressive power of message- passing GNN is upper bounded by the Weisfeiler-Lehman test (1-WL) [53]. This implies that if the L-hop neighborhoods of two nodes are indistinguishable by 1-WL, then their representations will be the same. The 1-WL test cannot differentiate between nodes with identical computation trees [44].
message-passing
Owing to Lemma and Lemma 2, given a graph g EV,E, X). we can decompose it into a multiset of computation trees Tg T. E VB. compute node embeddings h Ve V, and then aggregate them into graph embedding hg (Eq. 4) without incurring any loss of information. This computation structure enables to shrink the candidate space of concepts, originally defined in Prob. 1, to the set of unique computation trees, i.e., C = USeD Tg. The reformulation of the concept space imparts several desirable side-effects.
First, the size of the candidate space of concepts reduces from exponential to ΣygeD [V. which is linear to the graph size (i.c., number of nodes) and the number of graphs in the dataset.
Second, while graph isomorphism has a computational cost exponential to the graph size, rooted-tree isomorphism be performed in time linear to the number of edges in the tree (See App. for de- tails). Therefore, distilling all computation trees to only the unique ones can be done linear time. Third, GNNS may map non-isomorphic L-hop node neighborhoods (subgraphs) to isomorphic computation trees (See Fig. 2). This further reduces the number of concept candidates and, consequently, the computational burden.
3.3 Mining Concepts
To mine concepts from the candidate space, we assess their Shapley values. Shapley value [43] is a co-operative game theoretic technique where players form coalitions and receive payouts based on their contribution to the outcome. Mathematically. the Shapley value vbx(() of player is its average marginal contribution across all possible combinations of features.
S|! (p
|S| 1)! p!
4 (V(V)
Σ
(V(SU (())U())- (0)-
(5)
SC(L.-))MM
Here, p is the total number of players, represents a subset of players excluding player and the value function (.) quantifies the outcome.
With the hypotheses that some combination of computation trees responsible for GNN'S predictions, we aim to leverage Shapley values in identifying this combination. Consequently, the players correspond to computation trees, the value function corresponds to the performance of the GNN when restricted to the chosen subset of computation trees. We set the value function as the negated cross-entropy error of GNN t's prediction (one may use other accuracy measures as well). Thus, Eq. 5 is re-expressed as:
5

---

|S| (IC) - |S| - 1)! (V(SU -V())
(6)
CC|
VS,
where, V(S) = Σ log ① (99),)
VgED
In Eq. 6, (C,.-. CC is the set of unique computation trees, and C₁ denotes the i-th one. Eq. 7 represents the negated cross-entropy error. In Eq. 7, we slightly overload the notation introduced in Def. 3 as follows: assume that the class label information is maintained as c-dimensional one-hot vector. Thus, / is if the true class label of g is j-th label. The GNN returns a distribution over the class labels, where (())) y is the probability of the j-th class, when G is embedded by only considering the computation trees within S. Mathematically, this means modifying Eq. 4 as follows:
h Pool (fh!" Vu E V and T. E ES})
(8)
Finally, select the top-k computation trees with the highest Shapley value concepts. We discuss our procedure for selecting & in the next section ($ 3.4).
3.3.1 Computational Tractability
While we are able to map the problem of concept mining to Shapley Value computations, several computational challenges arise. Firstly, Shapley value computation necessitates sampling all possible subsets of players (computation trees), leading to exponential computation complexity. Secondly, we need to compute hg. i.e., the graph embedding corresponding to each subset of trees S. The naive approach involves: (1) enumerating computation trees rooted in each node, which consumes ((E)) time, (2) performing ( (1) tree isomorphisms detect computation trees contained within S and then (3) computing Eq. 8. Given that Shapley computation requires drawing multiple samples of (Eq. 6), the above pipeline for each sample S prohibitively slow.
Fortunately, there are works to circumvent the first challenge via sampling small set of coalitions with probabilistic approximations [59, 33]. We use the sampling strategy outlined in [28] (see App. for details).
The second challenge is unique since computing Shapley on computation trees of GNNs has not been studied. GraphShap [36], the only other work to study Shapley value the context of explaining graph classification, looks at the specific class of identity-aware graphs, where nodes with unique identities recur across multiple graph views. More importantly, GraphShap is not customized for GNNS and hence the context of computation tree does not arise.
To address the bottleneck of computing Eq. 8, we project each graph into a concept vector.
Definition 6 (Concept vector). Ler C (Ci..... C. } be the set of unique computation trees. The concept vector Cg E ZTo of graph G = E,,E, X) is an m-dimensional vector where the i-th dimension represents the number of computation trees in G that are isomorphic to the i-th concept candidate C. E C. Mathematically. Cgli = 1(u E T = C.Hl
The "concept encoding" box in Fig. 1 illustrates this operation. From Lemma the embedding of the root node of C, depends solely on C.. Hence, we pre-compute and map each C, E C into an embedding h,. By combining Lemma 2 with Eq.4, we deduce that for both MEANPOOL and SUMPOOL, the two most common aggregators can be computed in O(SS)) time. Specifically,
For SUMPOOL, hg Σ
Coll] h;
C.ES
For MEANPOOL, hg M
1
Σ
Coli
x h;
(10)
CLES
Owing to Lemma and Lemma 2, computing the graph embedding simply involves |S] look-ups of vectors instead of fresh rounds of pesssag-passsing
3.4 Generation of Logical Rules through Symbolic Regression
Let us denote the top-k computation trees with the & highest Shapley values as C*. To discover logical rules over C*, we perform symbolic regression. Symbolic regression is branch of regression analysis that aims to discover symbolic expressions from experimental data [31]. Formally, given a set of

---

input-output pairs {xx, 1)) where x, E R is an imput vector, and E IR is the output value (or label). and set of operators, such as addition, subtraction, logarithm, trigonometric functions, boolean logic, etc., the goal is to find a symbolic equation e and corresponding function Se such that Vi, y/ R fx,)..
To perform symbolic regression over computation trees, we first project the concept vector of each graph 9 = (V, X) on the top-k trees C*. This distilled concept vector is denoted as C2 Z where Cg = K E V T. = C.H., with C, representing the 1th ranked computation tree in C* based Shapley value. While symbolic regression can accommodate wide array of operators, mathematical operations such as addition or multiplication are not meaningful when applied to computation trees. Hence, to facilitate human interpretability, we restrict to the boolean operators: conjunction (A), disjunction (V), negation (-), and XOR (#). We aim to learn a symbolic function fo for each class label e predicted by the GNN. Let D. - {g E (())" c} be the subset of graphs where the predicted label is c. The symbolic function fo is identified by minimizing a multi-objective loss function that balances prediction error and model complexity. Formally,
L (fa) = Error(Je) + (ompleezzily)()
(11)
Complerity(fa corresponds the number of boolean operators and variables in fe- a is weighting hyper-parameter. Error corresponds to the number of disagreements with the GNN. Formally,
Error (fc) = Σ 1 1- fc(
+ Σ fc(G)
(12)
VGED.
DDD
Since fe is boolean function, it returns either TRUE (equivalently 1) or FALSE (0).
Symbolic regression poses a combinatorial optimization challenge, as the number of potential functions increases exponentially with the number of symbols, which is k in our case. Fortunately, the area is rich with several studies [31]. We use [8], which leverages a multi-population evolutionary algorithm to efficiently optimize and identify symbolic expressions (See App. C for details).
As depicted in Fig. 1, following the generation of boolean functions, GRAPHTRAIL concludes.
Identifying - the number of concepts: The higher the value of k. the more expressive symbolic regression is to fit to the prediction data by GNN. On the other hand, the computation cost grows monotonically with k. To optimize this balance, we start with a small value of k. and incrementally increase until the accuracy plateaus, similar using the patience parameter to determine the number of epochs in machine learning model training.
4 Experiments
In this section, we evaluate GRAPHTR. RIIL and benchmark its performance in translating predictions of various GNN architectures across diverse datasets and pooling layers. More experiments can be found in the appendix. The codebase of GRAPHTRAIL is shared at https://github.. https///ithub.coo//ieaa com/idea-
sitd/Graph com/idea-itt//raahh
4.1 Experimental Setup
Baselines: As discussed in $ I, GLGEXPLAINER [2] is the only existing algorithm that fits logical formula to GNN predictions, making it our primary baseline. Recall, GLGEXPLAINER generates a formula over vectors representing embeddings of subgraph clusters rather than individual subgraphs, rendering it non-interpretable. The formula is applied to an input graph by first processing it through an instance-level explainer, embedding the explanation subgraphs into feature space, and assigning them to the closest cluster. These cluster vectors are then considered present in the input graph. To make the formula interpretable, each cluster vector is replaced by the subgraph closest to the cluster representation in the embedding space. A subgraph (concept) Gs in the formula is considered present in an input graph & if Gs C G. We term this version GLGEXPLAINER
We use the authors' implementation of GEGEXPLIINER with the recommended parameters and employ PGEXPLAINER [29] the instance-leve explainer, suggested. The implementation of PGEXPLAINER is available in Pytorch Geometric.
Shapley value computation brings the computational bottleneck in the pipeline, which involves calculating the global Shapley value for each computation tree on each graph. This process can become impractical for datasets with large number of graphs. To address this issue, we propose GRAPHTRAIL. -II-S, an efficient version GRAPHTRAIL. Note that we are interested in the ranking according to the Shapley values and not the values themselves. If subset of the
GRAPHTRAIL-S:
7

---

BAMultiShapes
MUTAG
Mutagenicity
NC11
GLG
0.48 = 0.02
0.74 = 0.10
0.62 + 0.03
0.57 = 0.04
GLG-iso
0.00 0.00
0.61 0.20
0.53 + 0.06
0.49 + 0.05
G-TRAIL-S
0.86 + 0.01
0.78 + 0.08
0.72 0.01
0.72 + 0.02
G-TRAIL
0.87 + 0.02
0.82 + 0.09
0.72 + 0.01
0.72 + 0.02
Table 1: Average fidelity of the formulae across three seeds. The best and second best results shown in bold and underlined, respectively. G-TRAIL and GLG represents GRAPHTRAIL and GLGEXPLAINER respectively.
GNN Architecture
Ponl
GCN
GAT
GIN
SUM
MEAN
MAX
G-TRAIL
GLG
G-TRAIL
GLG
G-TRAIL
GLG
G-TRAIL
GLG
G-TRAIL
GLG
G-TRAIL
GLG
Shapes
0.81
0.49
1.00
0.93
0.87
0.48
0.87
0.48
0.88
0.50
0.89
0.52
MUTAG
0.87
0.80
0.74
0.87
0.55
0.82
0.77
0.54
0.78
0,74
Mutagenicity
0.63
0.73
0.72
NCTI
0.75
0.59
0.73
0.65
0.72
0.57
0.72
0.57
0.70
0.59
0.66
0.62
Table 2: Comparison of Fidelity across GNN architectures and POOL layers. The best result in each dataset and category highlighted in bold.
dataset can emulate the entire dataset, the generated ranking is expected to remain the same. Thus. GRAPHTRAIL creates a stratified split of the training dataset that maintains the class ratios and computes the global Shapley values using this subset. The rest of the pipeline remains unchanged, allowing for a more efficient yet effective method. This is also shown in the results from Table 1 where GRAPHTRAIL is slightly inferior to GRAPHTRAIL.
We use four benchmark datasets listed in Table C (App. D). While NCII [49], MUTAG [17], and Mutagenicity [39, 20] are collections of molecules, BAMultiShapes [55] is synthetic dataset specifically curated to benchmark global GNN explainers and associated with ground truth logical explanations. Further details are presented in App. D.
Datasets:
While we benchmark against various GNN architectures and POOL layers (Eq. 4), the default architecture is set to GAT for MUTAG and Mutagenicity and GIN for the other two. We use SUMPOOL as the default across datasets. The accuracies of the GNN architectures across all PoOL choices are presented in Table D in the Appendix. Details the hardware platform, train-val-test splits and other parameters are provided in App. E. All experiments have been repeated with three seeds and we report the means and standard deviations.
Evaluation framework:
Metrics: We evaluate explainer faithfulness using Fidelity; the ratio of graphs where the logical formula matches the GNN class label. Additional metrics can be found in the appendix.
4.2 Fidelity
Is GRAPHTRAIL faithful in translating GNN through logical rules? Table 1 provides the answer with several key observations.
First, both GRAPHTRAN and GRAPHTRAIL-- significantly outperform GLGEXPLAINER GRAPH- TRAIL. computes Shapley values by evaluating all subsets of concepts, while GRAPHTRAILL-S employs faster, sampling- based method. The key reason for the superior performance of GRAPHTRAI and GRAPUTRAILLS over GLGEXPLAINER lies aligning the concept definitions with the fundamental computational units of GNN, namely computational trees. GRAPUTRAIL then mines these concepts with global perspective by analyzing their Shapley values. In contrast, GLGEXPLAINER depends on instance-level explainers, which lack the ability to detect global patterns.
Second, GLGEXPLAINER-io consistently underperforms compared to GLGEXPLAINER. This is because the clusters of instance-level subgraph explanations in GLGEXPLAINER-iS. are not pure (See App. I). Although they are grouped based on embedding distance, their structures vary significantly. Representing a cluster by an exemplar subgraph fails to capture the diversity effectively.
Finally, GLGEXPLAINER results do not match the original results reported in [2]. In App. H, discuss the causes, including the identification of test data leakage in the Mutagenicity data set.
4.3 Robustness
Varying architectures and pooling mechanisms. In Table 2, we present the robustness of GRAPHTRAIL. and GLGEXPLAINER acToss various GNN architectures and PoOL layers. GRAPHTRAIL achieves
8

---

higher fidelity than GLGEXPLAINER across all scenarios. This result further substantiates the superior ability of GRAPHTRAIL in faithfully translating GNN outcomes.
Varying k. Fig. 3 explores the relationship between the number of mined concepts (k) and the fidelity achieved GRAPHTRAIL across various datasets. Recall that higher values of & allow for greater expressivity symbolic regression. Consistent with this, the results exhibit an increasing trend, with fidelity approaching saturation & 50 for most datasets.
1.0
0.9
0.7
0.5
4.4 Data Efficiency
Test
9.4
In Fig. 4, we assess the explainers' effectiveness in low-data regimes by varying the train data volume on the r-axis and mea- suring Fidelity on the y-axis. We expect Fidelity to decrease with lesser data. In GRAPHTRATI, the decrease in Fidelity with lesser data minor, indicating robust efficacy even with limited data and that it can be used in low-resource settings. Notably, the higher average Fidelity and lower standard deviation in GRAPHTRAIL across sizes indicate enhanced stability.
0.2
BAN SELEREEEE
NITI
0.6
100
280
Figure 3: Impact of & (number of concepts) on Fidelity.
BAMultiShapes
MUTAG
Mutagenicity
NCI1
Test Fidelity
0.75
0.75
0. 75
0.75
0.50
0.50
0.50
0.50
0.25
0.25
0.25
0.25
0.00
0.00
0.00
0.00
0 .775
17
2.
0.5
17
0-
GraphTrail
Fraction training dataset
Figure 4: Results the test set fidelity averaged three seeds while varying the training data size.
4.5 Visual Analysis of Rules
Fig. 5 presents the rules inferred by GRAPHTRAIL and GLGEXPLAINER for the datasets MUTAG, Mutagenicity, and BAMultiShapes.
According to [9], compounds with rings and dlectron-attracting group elements conjugated with nitro groups enhance mutagenicity. GRAPHTRAIL identifies both the ring structures as well as the nitro group as identifiers of mutagenicity in this dataset. In contrast, GLGEXPLAINER fails to identify the ring structure.
MUTAG:
Mutagenicity: Prior work [55, 45, 29, 2] often limits the mutagenic behavior in this dataset to NO₂ and N H2, i.c., the nitro and amine groups. However, in [20]. eight general toxicophores are capable of identifying 75% of all mutagens in the dataset (see Fig. F [20]). As seen in Fig. 5, without any supervision, GRAPHTRAIL identifies and incorporates six of them in its formula, viz. aromatic nitro, aromatic amine, nitroso, unsubstituted aromatic systems. The azo-type and the unsubstituted heteroatom- bonded heteroatom groups have not been identified explicitly but potential extensions of two of the identified structures.
cetrroatom-bodder heteroatom, azo-type, and polycyclic
known ground truth logical rules for class labels. While GRAPHTRAIL does not perfectly recover these rules, GRAPHTRAT ATL.'S inferred concepts and their logical combination exhibit greater similarity to the ground truth compared GI.GEXPLAINER" 's results. It should be noted that explainers try to find what the model has learned rather than the ground truth. One striking observation is that GLGEXPLAINER' extracted concepts bear no similarity to the ground truth and two of the prototypes have no graphs in their clusters and are therefore empty. In contrast, GRAPHTRAIL identifies concepts that are isomorphic to the grid and house motifs present in the ground truth.
BA BAMultiShapes: BAMultiShapes
5 Conclusions, Limitations and Future Directions
In this work, we have designed an end-to-end, post-hoc, global graph neural network (GNN) explainer called GRAPHTRAIL. We have formulated the problem of translating cesssae-passsigg GNN model

---

GraphTrail
GiGExplainer
PO
P1
MUTAG
Formula: P1
Fidelity: 0.79
Fidelity: 0.76
P1
Mutagenicitt
9
Formula: po & -P1
Fidelity: 0.65
Fidelity: 0.72
SMMultishapes
P3
P4
P5 Empty cluster
Empty cluster
Fidelity:
Formula:
Single bond
Hydrogen
Carbon
Double bond Nitrogen
Oxygen
(#2
-P1
(#3 -B1
-P5)
Aromatic bond Featureless
(P1 P2 a -PO -23 & -P4 -P5)
And
Fidelity:
Figure 5: Visual inspection of the formulae generated by GRAPHTRAII, and GI.GEXPLAINER. The encircled numbers in Mutagenicity are toxicophore IDs from Fig. F (in Appendix). The structures with two IDs in Mutagenicity can be extended to both toxicophores.
for graph classification into assuming the concepts are pre- rre-generated through separate algorithm. GRAPHTRAIL leverages several novel insights such as the decomposition graphs into computation trees by message-passing GNNs, which reduces the search space for concepts from exponential number of all possible subgraphs to linear space of computation trees. GRAPHTRAI evaluates the impact of these computation trees using Shapley values and then creates a boolean formula via symbolic regression only with the important ones. Extensive empirical analyses across diverse datasets and different GNN architectures demonstrate GRAPUTRAIL effectiveness in capturing the underlying logical relationships within complex GNN models for a wide range of scenarios in a uuman-interpretabbl form.
interprtabaee logic formula over subgraph concepts without
While both GRAPHTRAIL and GLGEXPLAINER express rules as logical combinations of concept's 's presence or absence, they currently lack the ability capture the multiplicity of concept's occurrence within graph. Finally, we believe attempting to interpret GNNs with subgraph level concepts creates dilemma between interpretability and faithfulness to the computational mechanism of GNNS. To elaborate, in GRAPHTRAIL since symbolic regression generates the formula over computation trees, we map back to the graph space, by replacing each computation tree with the most frequent L-hop ego graph that generates this tree. Note, GNNS operate at the level of computation trees. Given any formula a subgraph level, a new formula can be generated with identical fidelity, by simply replacing each subgraph concept with of computation trees (recall Fig. 2). However, when concepts are lowered to computation tree level, human interpetability is compromised. It is worth exploring how the best balance between human interpretability [13] and staying faithful to GNN computation structure can be obtained.
Limitations:
that produces the same set
10

---

6 Acknowledgements
Burouj Armgaan acknowledges the support of the Prime Minister's Research Fellowship (PMRF) for funding this research.
References
[1] Carlo Abrate and Francesco Bonchi. Counterfactual graphs for explainable classification of brain networks. In KDD, page 2495-2504, 2021. (Cited on p. 1 (-)
[2] Steve Azzolin, Antonio Longa, Pietro Barbiero, Pietro Lio, and Andrea Passerini. Global explainability of GNNs via logic combination of learned concepts. The Eleventh International Conference on Learning Representations, 2023. (Cited on pp. 2, 7, 8, 9, 15, and 19 (-)
[3] 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, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021. (Cited on pp. 1 and 15 (-)
[4] Federico Baldassarre and Hossein Azizpour. Explainability techniques for graph convolutional networks. arXiv preprint arXiv: /905. 13686, 2019. (Cited on p. 15 (-)
[5] Vaibhav Bihani, Sahil Manchanda, Srikanth Sastry, Sayan Ranu, and NM Krishnan. Strider- net: graph reinforcement learning approach optimize atomic structures rough energy landscapes. In ICML, 2023. (Cited on 1 +-)
[6] Chirag Chhablani, Sarthak Jain, Akshay Channesh, Ian A Kash, and Sourav Medya. Game- theoretic counterfactual explanation for graph neural networks. In Proceedings of the ACM on Web Conference 2024, pages 503-514, 2024. (Cited on p. (
[7] Yun Chi, Yirong Yang, and Richard Muntz. Canonical forms for labelled trees and their applications in frequent subtree mining. Knowl. Inf. Syst., 8:203-234, 08 2005. (Cited on p. 15
[8] Miles Cranmer. Interpretable machine learning for science with pysr and symbolicregression, jl. arXiv preprint arXiv:2305.01552. 2023. (Cited pp. 7 and 17 (-)
[9] Asim Kumar Debnath, Rosa L Lopez de Compadre, Gargi Debnath, Alan J Shusterman, and Corwin Hansch. Structure-action activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity. Journal of medicinal chemistry, 34(2):786-797, 1991. (Cited on pp. 9 and 15 (-)
[10] Dobrik Georgiev, Pietro Barbiero, Dmitry Kazhdan, Petar Veličković, and Pietro Liò. Algorith- mie concept-based explainable reasoning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 6685-6693, 2022. (Cited p. 2 {-)
[11] Mridul Gupta, Hariprasad Kodamana, and Sayan Ranu. FRIGATE: Frugal spatio-temporal forecasting on road networks. In 29th SIGKDD Conference Knowledge Discovery and Data Mining, 2023. (Cited on p. 1 (-)
[12] Shubham Gupta, Sahil Manchanda. Srikanta Bedathur, and Sayan Ranu. Tigger: Scalable generative modelling for temporal interaction graphs. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 68 6819-6828, 2022. (Cited on 1 +P)
[13] Pantea Habibi, Peyman Baghershahi, Sourav Medya, and Debaleena Chattopadhyay. De- sign requirements for human-centered graph neural network explanations. arXiv preprint arXiv:2405.06917 2024. (Cited p. 10 (-)
[14] William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Proceedings of the 31st International Conference Neural Information Processing Systems, NIPS' 17, page 1025-1035, Red Hook, NY, USA, 2017. Curran Associates Inc. (Cited on pp. 1 and +2)
11

---

[15] Qiang Huang, Makoto Yamada, Yuan Tian, Dinesh Singh, and Yi Chang. Graphlime: Local interpretable model explanations for graph neural networks. IEEE Transactions on Knowledge and Data Engineering, 2022. (Cited on pp. 1 and 15 (-)
[16] Zexi Huang, Mert Kosan, Sourav Medya, Sayan Ranu, and Ambuj Singh. Global counterfactual explainer for graph neural networks. In Proceedings of the Sixteenth ACM International Conference on Web Search and Data Mining, pages 141-149, 2023. (Cited on pp. 2 and 15 +)
[17] Sergei Ivanov, Sergei Sviridov, and Evgeny Burnaev. Understanding isomorphism bias in graph data sets. Geometric Learning and Graph Representations ICLR Workshop. 2019. (Cited on pp. 8 and 17 +-)
[18) Jayant Jain, Vrittika Bagadia, Sahil Manchanda, and Sayan Ranu. Neuromir: Robust & reliable route recommendation on road networks. Advances in Neural Information Processing Systems, 14:22070-22082 2021. (Cited on p. 1 (-)
[19] Jaykumar Kakkad, Jaspal Jannu, Kartik Sharma, Charu Aggarwal, and Sourav Medya. A survey on explainability of graph neural networks. arXiv preprint arXiv:2306.01953 2023. (Cited on
[20] Jeroen Kazius, Ross McGuire, and Roberta Bursi. Derivation and validation of toxicophores for mutagenicity prediction. Journal of medicinal chemistry, 48(1):312-33) 12200, 2005. (Cited on pp. 8, 9, and 17 +)
[21] Been Kim, Martin Wattenberg, Justin Gilmer, Carrie Cai, James Wexler, Fernanda Viegas, et al. Interpretability beyond feature attribution: Quantitative testing with concept activation vectors (Icav). In International conference on machine learning, pages 2668-2677. PMLR, 2018, (Cited on p. ())
[22] Thomas N Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv: 1:X9:v6600002900 2016. (Cited on pp. and 3 (2)
[23] Mert Kosan, Samidha Verma, Burouj Armgaan, Khushbu Pahwa, Ambuj Singh, Sourav Medya, and Sayan Ranu. GNNX-BENCHE Unravelling the utility of perturbation-based GNN explain- ers through in-depth benchmarking. In The Twelfth International Conference Learning Representations, 2024. (Cited on p. 1
[24] John R. Koza. Genetic programming: on the programming of computers by means of natural selection. MIT Press, Cambridge, MA, USA, 1992. (Cited on p. 3))
[25] Wanyu Lin, Hao Lan, and Baochun Li. Generative causal explanations for graph neural networks. In International Conference on Machine Leurning, pages 6666-6679, PMLR, 2021. (Cited on pp. 1 and 15 +))
[26] Shengyao Lu, Keith Mills, Jiao He, Bang Liu, and Di Niu. GOAt: Explaining graph neural networks via graph output attribution. In The Twelfth International Conference on Learning Representations, 2024. (Cited on pp. and 15 +))
[27] Ana Lucic, Maartje A Ter Hoeve, Gabriele Tolomei, Maarten De Rijke, and Fabrizio Silvestri. Cf-gnnexplainer: Counterfactual explanations for graph neural networks. AISTATS, pages 4599-4511, 2022. (Cited on pp. 1 and 15 +2)
[28] Scott M Lundberg and Su-In Lee. A unified approach to interpreting model predictions. Advances in neural information processing systems, 30, 2017. (Cited on pp. 6 and 16 +-)
[29] Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang. Parameterized explainer for graph neural network. Advunces in neural information processing systems, 33: 19600-9913,,, 2020. (Cited on pp. 1, 2, 7, 9, 15, and 19 ())
[30] Jing Ma, Ruocheng Guo, Saumitra Mishra, Aidong Zhang, and Jundong Li. Clear: Generative counterfactual explanations on graphs. arXiv preprint 13.04.2210.08443, 2022. (Cited on p. 15
+)
12

---

[31] Nour Makke and Sanjay Chawla. Interpretable scientific discovery with symbolic regression: review. Artificial Intelligence Review, 57(1):2, 2024. (Cited on pp. 3, 6, 7, and 17 +-)
[32] Sahil Manchanda, Akash Mittal, Anuj Dhawan, Sourav Medya, Sayan Ranu, and Ambuj Singh. Gcomb: Learning congtr-con combinatorial algorithms over billion-sizer graphs. Advances in Neural Information Processing Systems, 10220000-200111 2020. (Cited on p.
())
[33] Sourav Medya, Tiyani Ma, Arlei Silva, and Ambuj Singh. A game theoretic approach for core resilience. In International Joint Conferences on Artificial Intelligence Organization, 2020.
(Cited on 6 (-)
[34] Peter Müller, Lukas Faber, Karolis Martinkus, and Roger Wattenhofer. Graphchef: Learning the recipe of your dataset. ICML 3rd Workshop on Interpretable Machine Learning Healthcare (IMLH), 2023. (Cited on p. 2 +-)
[35] Sunil Nishad, Shubhangi Agarwal, Arnab Bhattacharya, and Sayan Ranu. Graphreach: Position- aware graph neural network using reachability estimations. IJCAI, 2021. (Cited p. I
[36] Alan Perotti, Paolo Bajardi, Francesco Bonchi, and André Panisson. Explaining identity aware graph classifiers through the language of motifs. In 2023 International Joint Conference on Neural Networks (IJCNN,, pages 1-8. IEEE, 2023. (Cited on p. 6 ())
[37] Phillip Pope, Soheil Kolouri, Mohammad Rostami, Charles Martin, and Heiko Hoff-
mann. Explainability methods for graph convolutional neural networks. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 10772-10781, 2019. (Cited on p. 15 ()
[38] Rishabh Ranjan, Siddharth Grover, Sourav Medya, Venkatesan Chakaravarthy, Yogish Sabhar- wal, and Sayan Ranu. Greed: neural framework for learning graph distance functions. In Advances in Neural Information Processing Systems, 2022. (Cited on p. (-)
[39] 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), pages 287-297. Springer, 2008. (Cited on pp. and 17 (-)
[40] Thomas Schnake, Oliver Eberle, Jonas Lederer, Shinichi Nakajima, Kristof T Schütt, 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- 7596, 2021. (Cited on p. 15 +-)
[41] Rishi Shah, Krishnanshu Jain, Sahil Manchanda, Sourav Medya, and Sayan Ranu. Neurocut: neural approach for robust graph partitioning. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD '24 page 2584-248222 2595, New York,
NY, USA, 2024. Association for Computing Machinery. (Cited on p. 1 1)
[42] Caihua Shan, Yifei Shen, Yao Zhang, Xiang Li, and Dongsheng Li. Reinforcement learning enhanced explainer for graph neural networks. In NeurlPS 2021, December 2021. (Cited on
p. 1 ())
[43] L. Shapley. A Value for n- n-Person Games. Contributions to the Theory of Games Il (1953) 307-317., pages 69-79. Princeton University Press, Princeton, 1997. (Cited on pp. 3, 5, and 16 ()
[44] Nino Shervashidze, Pascal Schweitzer, Erik van Leeuwen, Kurt Mehlhorn, and Karsten M. Borgwardr. Weisfeiler-lehman graph kernels. J. Mach. Learn. Res., 12(mll)::539-22511 nov 2011. (Cited on p. 5 ())
[45] 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 page 1018-1027, 2022. (Cited on pp. 1, 9, and 15 +2)
13

---

[46] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liö, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations. 2018. (Cited on pp. 1, 3, and 4 +-)
[47] Samidha Verma, Burouj Armgaan, Sourav Medya, and Sayan Ranu. InduCE: Inductive counter- factual explanations for graph neural networks. Transactions on Machine Learning Research, 2024. (Cited on pp. 1 and 15 (-)
[48] Minh Vu and My T Thai. Pgm-explainer: Probabilistic graphical model explanations for graph neural networks. Advances in neural information processing systems, 33:1 23:112225- 2020.
(Cited on p. 15 ())
[49] Nikil Wale and George Karypis. Comparison of descriptor spaces for chemical compound retrieval and classification. In ICDM, 2006. (Cited on pp. 8 and 17 (-)
[50] Xiaoqi Wang and Han Wei Shen. GNNInterpreter: A probabilistic generative model-level explanation for graph neural networks. The Eleventh International Conference on Learning Representations, 2023. (Cited p. 2-)
[51] Geemi P Wellawatte, Aditi Seshadri. and Andrew D White. Model agnostic generation of counterfactual explanations for molecules. Chemical science, 13(13):367733705 2022. (Cited
on p.
[52] Yaochen Xie, Sumeet Katariya, Xianfeng Tang, Edward Huang, Nikhil Rao, Karthik Subbian, and Shuiwang Ji. Task-agnostic graph explanations. NeurIPS, 2022. (Cited on p. 15 (2)
[53] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019. (Cited on pp. 1, 3, and 5 +2)
[54] Han Xuanyuan, Pietro Barbiero, Dobrik Georgiev, Lucie Charlotte Magister, and Pietro Lió. Global concept-based interpretability for graph neural networks via neuron analysis. In AAAI, 2023. (Cited on pp. 2 and 15 (-)
[55] 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, 2019. (Cited pp. 1, 8, 9, 15, 17, and 19 +2)
[56] 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, pages 430-438, 2020. (Cited on pp. 2 and 15 +))
[57] Hao Yuan, Haiyang Yu, Shurui Gui, and Shuiwang Explainability in graph neural networks:
A taxonomic survey. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022. (Cited on p. 1
[58] Hao Yuan, Haiyang Yu, Jie Wang, Kang Li, and Shuiwang Ji. On explainability of graph neural networks via subgraph explorations. In ICML, pages 12241-12252. PMLR, 2021. (Cited on pp. 1 and 15 +))
[59] Jiayao Zhang, Qiheng Sun, Jinfei Liu, Li Xiong, Jian Pei, and Kui Ren. Efficient sampling approaches to shapley value approximation. Proceedings of the ACM Management of Data, 1(1):1-24, 2023. (Cited on p. 6 ())
[60] Yue Zhang, David Defazio, and Arti Ramesh. Relex: A model-agnostic relational model explainer. In Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society, pages 1042-1049, 2021. (Cited on P. 15 <))
[61] Zaixi Zhang, Qi Liu, Hao Wang, Chengqiang Lu, and Cheekong Lee. Protgnn: Towards self-explaining graph neural networks. AAAI, 2021. (Cited on p. 2 +))
14

---

Appendix
Toxicophore name
Three- membered heterocycle
Unsubstitttd bonded heteroatom
Aliphatic Halide
Polycyclic
Nitro
Amine
Nitroso
Azo-type
Aromatic System
2H NH,
NH, OH
cl, Br,
rings
Substructure representation
aro
aro
N
N
arom. rings
Figure F: The eight toxicophores in the Mutagenicity dataset that are capable of identifying 75% of all mutagens in the dataset [9]. "aro" indicates an aromatic atom. "arom. rings" indicates an atom that part of multiple aromatic rings. The toxicophores identified by GRAPHTRAIL
colored green. Toxicophores and are underlined as they are not explicitly identified but are potential extensions two of the identified structures in Fig.
GNN Explainers
Instance-level
Global-level
Gradients /Features
Decomposition
Perturbation
Surrogate
Excitation-80
GCFExplainer
PGMExplainer
Xuanyuan
GNNEsplainer
RCExplainer CF2
CFONN CLEAR
Factual
PGExplainer
SubgraphX
InducE
GEM
GF
CF
Counterfactual
TAGExplainer
Figure G: Taxonomy of research conducted on explaining GNN predictions. Gradient: SA [4]
Guided-Bi BP [4] Grad-CAM [37]; Decomposition: Excitation-Bi BP [37]. GNN-LRP [40], CAM [37].
GOAT [26]: Perturbation: GNNExplainer [55], PGExplainer [29], SubgraphX [58], GEM [25].
TAGExplainer [52], CF2 [45], RCExplainer B1.Ce-GGNNxplainer [27]. CLEAR [30], InduCE [47];
Surrogate: Graphl.ime [15], Relex [60], PGM-Explainer [48]; Global: XGNN [56], GI.G-Explainer
[2], Xuanyuan et al. [54], GCFExplainer [16].
Rooted Tree Isomorphism
To identify the set of unique computation trees GRAPHTRAIL performs rooted tree-isomorphism. An efficient method for this task involves using canonical labels. The canonical label of graph G is unique representation that remains unchanged under isomorphism, i.e., two graphs G1 and G2 have the same canonical label if and only if they are isomorphic. We construct the canonical label of rooted computation tree through Depth-First Canonical Labeling (DFCF) [7]. From labelled rooted unordered tree we can derive many labelled rooted ordered trees as shown in Fig. There is one-to-one correspondence between a labelled rooted ordered tree and its depth-first string encoding. The ordering of the strings orders the trees and the minimum in the ordering the canonical label. Each string depth-first (preorder) traversal that uses $ to represent backtrack and # to represent
15

---

A
A
A
B
B
B
B
B
B
C
D
ABC$4BD$CE
ABCS#BC$DØ
ABD$C$$BCH
ABC$D$$BCH
Backtrack
End of string encoding
Figure Four rooted ordered trees obtained from the same rooted unordered tree. The alphabets denote the node labels. The strings below each tree are their depth-first traversals.
1, 2,,
#))
3, ()),4)
(1,,1,2,44)
B
9
2, (,,,1,,4
D
c (c,,,,,3
D 2, #,,,,,
E
1, (E,
#) 2, (F)
(E,
Figure I: Example of constructing a Sooth-FisttCCannniee Form of rooted tree. Each vertex is labeled with its identifier and, within parentheses, the ranks of its children, ending with a "hash symbol" to denote the end of the encoding. The rank the vertex its level is placed before the parentheses. After sorting all levels, the tree is then scanned from the top down, beginning with the root, and the children of each vertex are rearranged according to the established order.
the end the string encoding. sorting, # is greater than $ and both these symbols are greater than other labels. The Depth-First Canonical Form constructed by sorting the vertices of rooted unordered tree level by level. At each level, the vertices are sorted first by their labels and then by the ranks of their children at respective levels. Fig. illustraaees the process.
B Shapley Values
SHAP [28] represents the Shapley value explanation (SV) [43] an additive feature attribution method and fits weighted linear regression model to approximate the model's 's output. The weights this model correspond the SVs (contribution of features). specifies the explanation as
M
g(=) = Φn +
Σ かラ
1=1
where g is the model, = E {0, 1j is the coalition vector, M is the maximum coalition size, and
6, R is the SV for feature j. Kernel-SHAP [28] SHAP variant estimate SVs. It calculates SVs via:
Coalition Sampling: It randomly selects subsets of features, coalitions (z4). It assigns weights to each coalition using the SHAP kernel where M total features, | coalition size:
(M - 1)
. (2)
[2] |2])
Predictions: For each coalition, Kernel-SHAP maps the coalition back the original features and obtains a prediction afterwards.
16

---

Fitting: Using the calculated weights and predictions. Kemne--HHAP fits a linear model.
C Symbolic Regression
In symbolic regression, given a set of n input-output pairs (æt, Bi) where 2; E R is an input vector, and y E R is the output value (or label), and set of operators, such as addition, subtraction, etc., the goal is to find a symbolic equation and corresponding function fe such that Vi y/ x fa(x), while also reducing the complexity (number of operators and variable) of the formula. The loss function is presented in Eq. 11. Finding the optimal formula is not computationally tractable since the number formulas grows exponentially with the number of variables and operations. Hence, from the various approximation strategies in the literature [31] we use [8], which leverages evolutionary algorithm.
The process begins by initializing np populations, each with L random expressions of complexity C (3 in our experiments). For each P., a set M, is created to store the expressions with the smallest loss (Eq. 11) at each complexity level within that population. Additionally, global set H is maintained to store the expressions with lowest loss at each complexity across all populations. The algorithm iterates over each population P; for fixed number of epochs, allowing them to evolve. Evolution is driven by running tournaments within each population, where the expression with lowest loss is declared the winner. copy of the winner created and chosen for mutation or crossover, forming E". Mutating an expression involves repeatedly applying random operations from set of operations, e.g., replacing/adding operators and variables. Crossover selects the two best expressions, E1, E2 from the population and swapping random sub sobeexxressions between them, forming E1, E2- The newly formed expression(s) replace the oldest expression(s) in the population.
Once evolution within each population is complete, the sets M, and H are updated with the best expressions. When the set number of epochs are complete, the expression from H with minimum loss is returned.
Dataset details
Table C presents four benchmark datasets used in our experiments. NCI1 [49], MUTAG [17], and Mutagenicity [39, 20] are collections of molecules. The nodes represent different atoms, and the edges are chemical bonds between them. The molecules are classified by whether they are anticancer (NCII) or mutagenic (MUTAG and Mutagenicity). MUTAG, Class 1 is the mutagenic class while in Mutagenicity, Class 0 is mutagenic. BAMultiShapes [55] is synthetic dataset. The dataset is composed of 1,000 Barabasi-Alber (BA) graphs with network motifs attached in random positions. These motifs include house, grid, and wheel structures. Class 0 includes plain BA graphs well as BA graphs augmented with a house, a grid, a wheel, or all three motifs combined. Class consists of BA graphs enriched with combinations of two motifs: house and grid, house and wheel, or wheel and a grid.
BAMultiShapes
Mutagenicity
MUTAG
NCI1
#Graphs
1000
4337
188
4110
Avg. [V]
40
30.32
17.90
29.87
Avg. |8]
87.00
30.77
39.60
32.30
#Node features
10
14
7
37
Table C: Statistics of the datasets.
Further details of empirical framework
All experiments are performed A100 GPU with 40GB of memory and 377 GB RAM with Ubuntu 18.04.
Intel Xeon Gold 6248 processor with 96 cores and NVIDIA
Fach dataset is split into vrainvalidation-tes. sets in the proportion of 70:10:20 The accuracies of all GNN architectures are reported in Table D. All GNNS have been trained with I= 3 layers. We use Adam optimizer with learning rate set to 0.001. Training stops carly after warm-up of 90
17

---

epochs if validation accuracy doesn't it increase for 100 epochs or a total of 1000 epochs elapse. The explainers are evaluated on the test splits.
GCN
GIN
GAT
Sum
Mean
Max
Sum
Mean
Max
Sum
Mean
Max
BAMultiShapes
0.83
0.83
0.82
0.94
0.93
0.91
0.5
0.5
0.5
MUTAG
0.84
0.79
0.74
0.82
0.84
0.87
0.82
0.85
0.71
Mutagenicity
0.79
0.77
0.77
0.79
0.80
0.77
0.77
0.78
0.75
NCI1
0.76
0.76
0.76
0.77
0.78
0.76
0.74
0.74
0.74
Table D: Model accuracy across different GNN architectures and pooling layers for aggregating node embeddings into graph embedding (Eq. 4).
[3]:
edge_ Lists, graph, labels, edge_labe Label Lade_label__ise eet_graph_dett(erpp dataset)
with openi". //tttaser/uuagggniiity... 'rb'1
originel_edjs,ore oerii oriiinaa, Labelss find
we only consider sutagen graphs
and
se selected for gid in range(origtmaladd snjssssseeo (0]):
it np.angnaxi w..arnnxx/origina L Labels (gid1) =s 0 and
(q1d))
selected appendigid)
printi 'nubeer of Lejs Laggaal seleeced_feeturee o Leeatnneessttttseteeeee
graphs with N02 and NH2' [en(selected))
selected labels original_laber Iselected)
selected, edge_ lists [edge_ Lists [i] for selected]
selected_gras
sesgraph_abellsiseeeeeeee
selected edge label H1sts- tabel Hists(1] for 1 selected]
selected_nndee Labe Listss Liitts=inod____1 LUsts(i for i in selected]
number nutagen graphs
Figure Code snippet of instance explainer restricting train set to only those graphs that contain the explanation motifs.
F Contribution of Shapley values
To highlight the impact of using Shapley values for selecting the important computation trees, compare the GRAPHTRAIL' fidelity when the computation trees are chosen based on the Shapley values versus when they chosen random. As evident from Table E, choosing random trees significantly deteriorates the fidelity, indicating the value of Shapley-based selection.
Additional Experiments
In this section, we present additional experiments to further validate our findings. The results are summarized in Tables F, G. H. I, each highlighting different aspects of the derived formulae. Each metric is the weighted average across the classes. These tables provide deeper insights and reinforce the conclusions drawn from our initial analysis.
BAMultiShapes
MUTAG
Mutagenicity
NCI1
Random
0.54 0.03
0.68 + 0.04
0.55 0.01
0.54 - 0.02
Shapley
0.86 0.02
0.82 + 0.09
0.72 0.01
0.72 + 0.02
Table E: The impact of selecting computation trees by considering Shapley values versus random selection.
18

---

Method
BAMultiShapes
MUTAG
Mutagenicity
NCI1
GLG
0.39 0.11
0.70 + 0.05
0.64 0.03
0.49 + 0.16
G-TRAIL
0.87 + 0.01
0.83 + 0.09
0.74 + 0.01
0.74 + 0.01
Table F: Weighted average precision of the generated formulas against the GNN output
Method
BAMuussSShapes
MUTAG
Mutagenicity
NCI1
GLG
0.48 = 0.02
0.74 = 0.10
0.62 0.03
0.57 = 0.04
G-TRAIL
0.86 + 0.02
0.82 = 0.09
0.72 + 0.01
0.72 = 0.02
Table G: Weighted average recall of the generated formulas against the GNN output
Method
BALsultSShapes
MUTAG
Mutagenicity
NCI1
GLG
0.41 + 0.06
0.68 + 0.11
0.61 + 0.03
0.49 + 0.11
G-TRAIL.
0.86 + 0.02
0.82 + 0.08
0.72 + 0.02
0.70 + 0.03
Table H: The weighted average Fl-score of the generated formulas. The weighted version accounts for label imbalance and result in F1-score that is not between precision and recall.
Method
BAlulttSSapess
MUTAG
Mutagenicity
NCI1
GLG
0.46 0.03
0.68 + 0.00
0.55 0.03
0.56 + 0.04
G-TRAIL
0.83 0.03
0.72 0.05
0.65 0.01
0.67 = 0.02
Table I: Accuracy of the generated formulae against ground-truth labels
Reproducibility Analysis GLGEXPLAINER
Our analysis reveals inconsistencies between the findings reported in [2] and our own observations with GLGEXPLAINER. Specifically, the reported results in [2] for Mutagenicity dataset might be inflated due test data leakage. In this dataset, the presence of NO2 and/or NH2 motifs is indicative of a positive class label [55]. However, GLGEXPLAINER utilizes PGEXPLAINER [29] to generate instance explanations. Within GLGEXPLAINER, these explanations are created by excluding training graphs that lack these motifs (see Fig. J for the relevant code snippet from PGEXPLAINER 's repository https://gituu..com/ff results in biased explanations that overemphasize specific motifs. When all training graphs are included, GL.GEXPLAINE produces wider variety of explanations, leading to a decrease in its overall performance.
This approach
For other datasets, GLGEXPLAINER offers instance explanations but lacks transparency regarding the specific PGEXPLAINER settings used to generate them. Despite employing all recommended settings and extensive parameter tuning for PGEXPLAINER, we were unable replicate the instance explana- tions presented by the authors of GLGEXPLAINER. Our email to the authors of GLGEXPLAINER pointing out these inconsistencies did receive a response.
I Cluster Impurity of GLGEXPLAINER
In GI,EE,LLAINER, the formulae are vectors that are called prototypes. Prototypes are representa- tives of clusters of local explanations, and it is assumed that the clusters pure. This essentially
19

---

means that most of the elements in the same clusters will be similar. To verify this claim, we evaluate random graphs from each cluster both classes across different seeds. Figures L. M. and N show the results in all four datasets across different seeds. We make two important observations. First, the clusters are not pure, and the graphs are not similar in the same cluster. For instance, in seed 45 of MUTAG (Fig. K), class O has four types of graphs among five. Second, across classes, there exist similar graphs, which undesired. For example, in the same figure, seed 729 shows three graphs that are similar across classes.
PO
P1
Seed 45
Seed 357
PO
Seed 729
Figure K: A visual depiction of the impure clusters of GIGEEXLAIIERR in MUTAG.
20

---

PO
P1
Seed 45
PO
P1
Seed 357
PO
P1
Seed 729
Figure L: A visual depiction of the impure clusters of GIGEXXLAIINER in Mutagenicity.
21

---

PO
P1
P2
P3
P4
Seed 357
PO
P1
P2
P3
P4
Seed 796
Figure M: A visual depiction of the impure clusters of GI.GEXPLAINEE in BAMultiShaess.
22

---

P1
Seed 45
PO
P1
Seed 1225
P1
Seed 1983
Figure N: A visual depiction of the impure clusters of GI.GEXPLAIIER in NCII.
23

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Sec. 2, 3, and 4.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No NA answer this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much results can be expected to generalize to other settings. is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
Justification: Sec. Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g., independence assumptions, noiseless settings, model well-specification,
asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Sec. 3.2
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.
All assumptions should clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
24

---

Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and I Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experi- mental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Answer: [Yes]
Justification: Sec 4.1, Appendix and C
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of a large language model), releasing of model checkpoint, or other means that are appropriate to the research performed.
example, if the contribution
While NeurlPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of dlosed-source models, it may be that access to the model is limited some way (e.g.. to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Sec. 4 and Appendix B and C. The code has been provided via a github repository. Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines http:::/nips.cccpuull//ee CodeSubmisssionolliey for more details.
While we encourage the release of code and data, we understand that this might not be possible,
so "No" is an acceptable answer. Papers cannot be rejected simply for not including code. unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed run to reproduce the results. See the NeurIPS code and data submission guidelines (https://nips.cc/pll /u/pi/////p/ll///udee/s///////// CodeSubmissioonPollyy for more details.
The authors should provide instructions on data access and preparation, including how to access
the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed
method and baselines. only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.
25

---

At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: Sec. 4 and Appendix B and Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details be provided either with the code, in appendix,
supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Section 4
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1 I-sigma error bars, but one should state it. The authors should preferably report 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experi- ments?
Answer: [Yes]
Justification: Sec. 4 and Appendix C
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud
provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, every respect, with the NeurIPS Code of Ethics http://meeriisccc/maal//ttthiict Answer: [Yes]
Justification: All sections.
26

---

Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consideration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Sec. 1 (positive social impact), Sec. 5 (negative social impact)
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploy- ment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to par- ticular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, is legitimate to point out that improvement in the quality of generative models could be used generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been seraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.
12. Licenses for existing assets
Question: Are the creators original owners of assets (c.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not use existing assets.
. The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL..
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
27

---

For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should wwwpiiihcooe.co//atttaeeeee com/datasets has curated licenses for some be provided. For popular datasets, paperswitheode.
datasets. Their licensing guide can help determine the license of a dataset.
For existing datasets that are re-packaged, both the original license and the license the derived asset (if it has changed) should be provided.
this information not available online, the authors are encouraged to reach out to the asset's
creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: Sec. 4
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mooel as part of their sub- missions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human
subjects.
Including this information the supplemental material is fine, but if the main contribution of the paper involves human subjects, then much detail possible should be included in the main paper.
According the NeurIPS Code Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals Equivalent for Research with Human Sub- jects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applica- ble), such as the institution conducting the review.
28


Reviews:
[{"review_id": "D2E12nm3jO", "reviewer": "Reviewer_8Xmp", "summary": "The authors propose a novel method to provide instance-level GNN explanations that uncover the combinatorial reasoning learned by a GNN from the training data. They do so by mining discriminative subgraph-level concepts using Shapley values and mapping them to human-interpretable boolean formulas over these concepts through symbolic regression.", "questions": "We consider the paper interesting and relevant. Nevertheless, we would like to point to the following improvement opportunities:\n\nGENERAL COMMENTS\n\n(1) - did the authors consider trying their method on some datasets from a different domain / not describing collections of molecules?\n\n(2) - did the authors consider performing some ablation studies to understand, e.g., what is the contribution of selecting trees by considering Shapley values vs. a random selection?\n\n(3) - did the authors consider the statistical significance of the results obtained? E.g., the Wilcoxon signed-rank test.\n\nFIGURES\n\n(4) - All figures: consider a color palette that would be friendly for colorblind people. The following link could be helpful in this regard: https://davidmathlogic.com/colorblind/#%23D81B60-%231E88E5-%23FFC107-%23004D40\n\nTABLES\n\n(5) - Table 1: align numeric values to the right to make differences in magnitude evident. Use the same number of decimals across rows.\n\n(6) - Table 2: report the same number of decimals in all cases. Apart from the averages, the authors are reporting the standard deviation?", "limitations": "The authors have adequately acknowledged the limitations of their work.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- the authors describe a novel instance-level explainability method they designed for GNN models\n- the authors compare their method against a SOTA technique and outperform it\n- the authors assess their method against multiple datasets", "weaknesses": "- the real-world datasets the authors use to assess their method only correspond to datasets describing collections of molecules\n- we miss some ablation studies to understand the contribution of particular components of the proposed technique", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive comments on our work. Please find below our responses to the suggestions and concerns raised.\n\n**Q1/W1: Did the authors consider trying their method on some datasets from a different domain / not describing collections of molecules?**\n\n*Answer:* We note that BAMultishapes is not a molecular dataset. In this dataset, the gap between GraphTrail and GLGExplainer is the highest ($0.87$ vs. $0.51$).\n\n**W2/Q2: What is the contribution of selecting trees by considering Shapley values vs. a random selection?**\n\n*Answer:* We have conducted this ablation study. As evident from the table below, choosing random trees significantly deteriorates the fidelity, indicating the value of Shapley-based selection.\n\nAlgorithm| BAMultishapes | Mutag | Mutagenicity | NCI1\n---|---|---|---|---\nGraphTrail with Shapley | **0.87 +- 0.01**| **0.83 +- 0.08** | **0.72 +- 0.03** | **0.70 +- 0.03**\nGraphTrail with random trees| 0.54 +- 0.03| 0.68 +- 0.04| 0.55 +- 0.01| 0.54 +- 0.02\n\n**Q3 - did the authors consider the statistical significance of the results obtained? E.g., the Wilcoxon signed-rank test.**\n\n*Answer:* We have conducted paired T-tests to measure the statistical significance of the results. The results are presented below, which shows that the improvement obtained by GraphTrail over GLGExplainer is statistically significant.\n\n|BAMultishapes | MUTAG |  Mutagenicity | NCI1|\n|--|--|--|--|\n|t=58.952, $p$-value=$\\approx$ 0 |t=2.908, $p$-value=0.017 | t=23.519, $p$-value=$\\approx$ 0 | t=12.159, $p$-value=$\\approx$ 0|\n\n**Q4 FIGURES\n(4) - All figures: consider a color palette that would be friendly for colorblind people.**\n\n**Answer:** Sure, we will change the color palette as per the guidelines in the link.\n\n**Q(5) - Table 1: align numeric values to the right to make differences in magnitude evident. Use the same number of decimals across rows.**\n\n**Answer:** We will make this correction. \n\n**Q(6) - Table 2: report the same number of decimals in all cases. Apart from the averages, the authors are reporting the standard deviation?**\n\n**Answer:** We will modify the table as suggested. \n\n------\n# Appeal to the reviewer\n\nWith the inclusion of statistical significance tests, ablation study and clarifications, we hope the reviewer finds our manuscript improved. If the reviewer agrees, we would appreciate support for our work by increasing the rating accordingly.", "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": "sN29wi8mZI", "reviewer": "Reviewer_x6B5", "summary": "This paper introduces GraphTrail, an end-to-end global GNN explainer providing logic formulas over sub-graphs level concepts. These concepts are extracted at subgraph level by using the Shapley values and, then, the GNN predictions are mapped into logic via symbolic regression. Different experiments show that GraphTrail is improving wrt other GNN explainers, that has robust and accurate performances.", "questions": "1) \"The objective of our work is to develop an end-to-end global explainer that (1) mines the subgraph concepts used by a black-box GNN model, and then (2) uncovers the boolean logic used by the GNN over these concepts to make its predictions.\" If I understand correctly, your model is a post-hoc GNN explainer, even if I think this is never mentioned in the paper. Or I'm missing something here?\n\n2) What do you mean by \"unique\" subgraph? This has not been defined as far as I see.\n\n3) Obs 1 and 2 are simply theorems (or lemmas) with a proof, also the proofs seem formal to me. So I don't understand why the authors are calling them observations.\n\n4) Is it possible to evaluate the logic rules in terms of accuracy to make the prediction? The fidelity is great, but also the accuracy of the extracted explanations should be evaluated to measure the quality of the extracted explanations for a certain task.", "limitations": "The model limitations have been correctly described.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The problem investigated in the paper is very interesting, the paper is well written and the problem well formulated.\n\n- The way different existing techniques have been combined to design GraphTrail is very interesting.", "weaknesses": "- Some aspects of the comparison against GLGExplainer should be importantly clarified. Also as these two models have such a similar core, more experimental analysis should be done to validate the advantages of GraphTrail wrt to GLGExplainer. \nMoreover, I had a look at the GLGExplainer paper, and the fidelity valued reported there (Table 2 and 4), and the one in this paper are very different, hence I'm asking if Table 2 of GraphTrail paper is actually reliable or there is an explanation for the difference of results reported in the two papers. While here it is claimed that \"both GRAPHTRAIL and GRAPHTRAIL-s significantly outperform GLGEXPLAINER\", the results in the GLGExplainer paper for the fidelity in the  two datasets (on the test set) are:\nBAMultiShapes 0.96 ± 0.03\nMutagenicity 0.81 ± 0.01\nthe results reported in the GRaphTrail paper for GLGExplaier are:\nBAMultiShapes 0.51 ± 0.03\nMutagenicity 0.62 ± 0.02\nHence I'm wondering either the GLGExplainer had a mistake in their implementation, the authors of GraphTrail were not able to correctly reproduce the GLGExplainer performances, or there are some additional hypothesis distinguishing these experiments that I didn't understand.\nSimilarly for the provided explanations in the different datasets (the comparison in Figure 5 here), they seem quite different from the ones reported in the GLGExplainer. This should be clarified in order to understand if actually GraphTrail is performing better or not than on of its main competitor.\n\n- Definition 5 is a bit unclear, could you make it more precise? Even if Fig 2 helps a lot to understand the tree construction.\n\n- I see the computational advantage of only considering Rooted Computation Trees as concepts, but I guess it is tricky in practice to find an L that works for all the graphs in D, and that part of the complexity of the problem is understand the minimum L that make a good explanation.\n\nMinor comments and typos:\n- Please split the rigorous definition from the comment in Definition 4. Hence in practice, the concepts of a graph are all its subgraphs, i.e. this include the original graph itself, disconnected nodes and so on, right?\n- Curiously, in the abstract of GLGExplainer and GraphTrail there is this common sentence:  \"..making GLGExplainer a promising diagnostic tool for learned GNNs.\" and \"..GraphTrail makes it an invaluable diagnostic tool for refining GNNs..\" It seems strange that it is a coincidence, as GraphTrail describes in details the GLGExplainer  paper. I'd suggest to rephrase in a more original way (in addition to having changed the adjective \"promising\" to \"invaluable\").", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**W1(a). Comparison vs GLGExplainer** \n\n**Ans:** The algorithmic foundations of GLG and GraphTrail are significantly different (please see Lines 47-63). These include:\n\n1. **Non-reliance on local explainers:** GLG assumes local explanations as an input and then operates over these to identify the logical formula. GraphTrail observes that relying on local explanations creates a disconnect with the objective, as they lack a global understanding of the model. Hence, GraphTrail mines the concepts directly from the training data.\n\n2. **Concepts:** In GLG, each concept in the formula corresponds to a feature vector and not a subgraph. These vectors represent the embedding of a cluster of subgraphs generated by the instance explainer. Hence, in its original form, the formula is not human-interpretable. To convert into a human-interpretable formula, GLG randomly selects a subgraph from the cluster, assuming all subgraphs in a cluster are similar. We show in App. F that the graphs in a cluster are diverse and hence randomly picking one is not a faithful explanation. GraphTrail doesn't suffer from this issue since the concepts map to computation trees.\n\n3. **Formula construction:** While GLG uses an entropy layer [1] to construct the logical formula, GraphTrail uses symbolic regression.\n\n**W1(b) Conduct additional experiments.**\n\n*Ans.* We have conducted the following experiments, which are reported in `the rebuttal pdf'.\n\n* **Accuracy of generated formulas** against ground-truth (`Table 1`) \n\n* The **statistical significance** of the results via paired T-tests (`Table 2`)\n\n* **Precision, recall and f-score** (`Tables 3-5`) of the generated formulas against GNN output.\n\n**W1(b). ...the fidelity in GLGExplainer, and the one in this paper are different...**\n\n**Ans:** Indeed, GLG is not reproducible. We highlight this explicitly in lines 307-308 of our main draft with a pointer to Appendix D offering a discussion on the possible causes. As we note in Appendix D, there is definite **test data leakage** in the Mutagenicity dataset. We include the screenshot of the corresponding code in Fig G. Specifically, in this dataset, the presence of NO2 and/or NH2 motifs indicate a positive class label (mutagenic). However, a graph may be positive due to other factors (See [2]). GLG alters the train set by **only** including graphs that contain NO2 and NH2. This selection bias dramatically simplifies the explanation task, as the model is essentially fitted to explain NH2 or NO2 presence. When we include all graphs, the result deteriorates. \n\nIn other datasets, GLG has released the instance explanations being used for deriving the global explanation, but not the exact train sets used that generate these instance explanations.  When we run the GLG code (released by authors) on raw datasets using the reported hyper-parameters, the produced instance explanations don't match the released instance explanations. Hence, the fidelity numbers are different.\n\nIf we use the released explanations, the reported results in GLG match. This isolates the reproducibility issue to the generation of instance explanations, similar to our observation in Mutagenicity. \n\nWe had reached out to the authors via email requesting: (i) the pipeline that produce the release explanations, (ii) justification for the train set selection in Mutagenicity. We have not received any response.\n\nFor transparency, our code and datasets are publicly available. Our results can be verified independently.\n\n**W2. Simplify Def. 5**\n\n**Ans:** We'll change it as follows.\n\n> A *computation tree*, also known as a receptive field, is a fundamental concept in GNNs that describes how information propagates through the graph during the neural network's operation. Formally, it is defined as follows.\n> \n> Given a graph $G=(V,E,X)$, a node $v \\in V$ and the number of layers $L$ in the GNN, the computation tree $T^L_v$ rooted at $v$ is constructed as follows:\n> * Enumerate all paths (including those with repeated vertices) starting from $v$ and extending up to $L$ hops away.\n> * Merge these paths into a tree structure where, (i) The root is always $v$, and (ii) Two nodes from different paths are merged if:\n>    a. They are at the same depth in their respective paths, and\n>    b. All their ancestors in the paths have already been merged.\n>This tree represents how information flows to node $v$ during $L$ rounds of message passing in the GNN.\n\n**W3: Determine $L$?**\n\n**Ans:** The value of $L$ is known to us. It represents the number of layers in the GNN being explained. Since each node's embedding is determined by its $L$-hop computation tree, $L$ is not derived and given as input.\n\n**W4: Split Def. 4 from comment. What is the space of concepts?**\n\n*Ans.* Sure.\n\nSpace of concepts: In GLG, the space of all subgraphs includes the graph itself, disconnected nodes, etc. However, GraphTrail notes that a node embedding is solely determined by its $L$-hop neighborhood. Consequently, this space is limited to only the $L$-hop computation tree of each node.\n\n**W5: similar sentence in abstract.**\n\n*Ans.* We will rephrase. \n\n**Q1: ...your model is a post-hoc explainer**\n\n*Ans.* Yes. We'll state this explicitly.\n\n**Q2: What's meant by \"unique\" subgraph?**\n\n*Ans.* A unique subgraph (or tree) refers to a subgraph that is not isomorphic to any other subgraph in the collection extracted from the graph(s).\n\n**Q3: Obs 1 & 2 are theorems/lemmas.**\n\n*Ans.* We'll change to Lemmas. \n\n**Q4: Accuracy of logical rules.**\n\n*Ans.* Added as discussed in W1(a).\n\n[1] Entropy-based logic explanations of neural networks, AAAI'22\n\n[2] Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. Correlation with molecular orbital energies and hydrophobicity. J Med Chem'91\n\n[3] What graph neural networks cannot learn: depth vs width. ICLR'20\n\n------\n# Appeal\n\nIn light of the additional experiments and clarifications, we kindly request the reviewer to reassess the rating of our work.", "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": "2xB2L4kJX3", "reviewer": "Reviewer_Sg1i", "summary": "This paper proposes a novel method for providing global explanations for GNNs by constructing logical formulas that offer easy-to-understand interpretations for each class. The authors first propose using computation trees instead of subgraphs to construct explanations. They then suggest using Shapley values to evaluate the contribution of each computation tree to the classification results. Finally, they derive logical formulas corresponding to each class through symbolic regression. Compared to traditional instance-level explanation methods, this approach can explain the decision-making process of GNNs from a higher level. Moreover, compared to other model-level explanation methods, this method does not require prior knowledge about the dataset and is easier to understand. Overall, this paper is innovative, has a clear approach, and provides convincing experiments.", "questions": "- According to the experimental setups in [EiG-Search](http://arxiv.org/abs/2405.01762), [D4Explainer](https://arxiv.org/abs/2310.19321), and [GLGExplainer](http://arxiv.org/abs/2210.07147), the GNN accuracies trained on the BAMultiShapes, Mutag, Mutagenicity, and NCI1 datasets are higher than those presented in Table D of this paper. Were the GNNs used in this paper's experiments sufficiently trained?\n- In line 225, the top \\( k \\) computation trees with the highest Shapley values are selected and denoted as \\( \\mathcal{C}^{*} \\). From which dataset or set are these computation trees selected? Is this set composed of computation trees from every node of all graphs in the training set?", "limitations": "Apart from the limitations discussed in Section 5 of the paper, in Eq. 7, when calculating \\(\\Phi\\left(\\mathcal{G}^{S}\\right)\\), the GNN may not provide correct classification probabilities for the embedding \\(h^S_{\\mathcal{G}}\\) due to insufficient generalization ability. This can affect the calculation of the Shapley values and, consequently, the overall performance of the method.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- ### Originality\n    - Compared to previous works that employ concept-based explanations for GNNs (e.g., GLGExplainer), the proposed concept vector form is more comprehensible. This concept vector also addresses a significant challenge in subsequent Shapley value calculations. Additionally, this method is end-to-end, reducing complexity.\n    - The use of computation trees instead of instance-level subgraph extractors as concepts results in explanations that better reflect the inherent properties of the dataset and are less influenced by the quality of instance-level explainers. The exploration of Shapley values in the context of graphs is relatively novel. The paper analyzes the reasons for the high complexity of Shapley value calculations on graphs and successfully reduces this complexity through a combination of various methods.\n- ### Quality\n    - This paper starts with the problem of providing global explanations for GNNs, reviewing existing solutions and identifying their shortcomings. It proposes a new approach that uses computation trees and Shapley values to construct concept formulas. The approach is clear, identifying the deficiencies of current methods and proposing solutions. The paper then analyzes the challenges of calculating Shapley values and successfully addresses these challenges using existing methods. This section details the difficulties of computing Shapley values on graphs, providing an effective method for efficient computation.\n    - Next, the paper uses symbolic regression to generate logical formulas from concept vectors. This process is clear and intuitive. Finally, it tests the proposed method on multiple datasets using GLGExplainer as a baseline, evaluating Fidelity, Robustness, and Data Efficiency. The results demonstrate that this is a reliable and effective method. Overall, the paper presents a clear approach, offering a new method for explaining GNNs using logical formulas and an efficient way to compute Shapley values on graphs, with detailed and comprehensive experiments.\n- ### Clarity\n    - The paper provides detailed explanations of the problem definition, relevant concepts (such as Shapley value, concept, graph isomorphism, rooted computation tree), and experimental aspects. It clearly describes the task objectives and provides corresponding mathematical formulations, with strict mathematical definitions of the relevant concepts. The experimental section is well-organized, detailing the GNNs used, the process of selecting the hyperparameter kkk, and the standards used in the explanation process.\n    - Overall, most of the content in this paper is clearly presented and easily understandable by readers.\n- ### Significance\n    - The significance of this paper lies primarily in the construction of subgraphs as concepts using computation trees and the efficient computation of Shapley values on graphs.\n    - First, constructing subgraphs using computation trees greatly reduces the complexity of the search space. Given the message-passing paradigm of GNNs, using computation trees aligns better with the information processing of GNNs compared to other graph structures.\n    - Second, the paper studies methods for computing Shapley values on graphs, proposing an efficient computation scheme based on existing methods. This contributes to the application of Shapley values in the graph domain.", "weaknesses": "- The main weakness of this paper is that it does not adequately describe the specific calculation methods for Shapley values and the symbolic regression methods used. Instead, it merely cites the sources of these methods without providing appropriate descriptions in the text or the appendix. For example, in line 207, it only states that it uses methods from [A unified approach to interpreting model predictions](https://arxiv.org/abs/1705.07874) without further describing the sampling strategy. Similarly, in lines 247-248, it mentions the [multi-population evolutionary algorithm](https://arxiv.org/abs/2305.01582) used for symbolic regression but lacks a basic description of this method. In the appendix, lines 521-526 only state that the [Depth-First Canonical Form (DFCF)](https://dl.acm.org/doi/10.5555/2993947.2993981) is used to convert computation trees to Canonical Form for efficient tree isomorphism testing, but it also lacks specific descriptions.\n- Such a presentation, where the methods are only cited without basic descriptions, makes it difficult for readers to understand the proposed methods. Additionally, Table D in the paper shows the accuracy of the GNNs used in the experiments on various datasets, but the accuracy appears to be lower than that reported in other papers. This may indicate that the GNNs used in the experiments were not sufficiently trained (this issue will be elaborated on in the Questions section).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**W1: The main weakness of this paper is that it does not adequately describe the specific calculation methods for Shapley values and the symbolic regression methods used. Instead, it merely cites the sources of these methods without providing appropriate descriptions in the text or the appendix. For example, in line 207, it only states that it uses methods from A unified approach to interpreting model predictions without further describing the sampling strategy. Similarly, in lines 247-248, it mentions the multi-population evolutionary algorithm used for symbolic regression but lacks a basic description of this method. In the appendix, lines 521-526 only state that the Depth-First Canonical Form (DFCF) is used to convert computation trees to Canonical Form for efficient tree isomorphism testing, but it also lacks specific descriptions.**\n\nAnswer: Due to space constraints, we decided to omit the referred details, as these algorithms serve as tools rather than original contributions of our work. We understand that this decision impacted the comprehension of certain sections. Based on your feedback, we propose to include more detailed descriptions provided in the **`global response` above**. These descriptions will be added to the appendix, with references from appropriate sections in the main manuscript.\n\n**Q1: GNN accuracy in EiG-Search, D4Explainer, and GLGExplainer, are higher. Were the GNNs used in this paper's experiments sufficiently trained?**\n\n*Answer:* GNN accuracies are hard to replicate exactly due to variabilities such as train:test splits and training on a single seed (while we have reported results across three splits and three seeds). Nonetheless, to address this concern, we have taken the exact model weights from EiG-Search and measured the performance of GraphTrail and GLGExplainer. The results are in **Table 6** of the pdf attached to the global response. Consistent with previous results, GraphTrail outperforms by similar margins.\n\n| EiG-Search  | MUTAG         | Mutagenicity  | NCI1          |\n|-------------|---------------|---------------|---------------|\n| GLGExplainer         | 0.56 +- 0.21  | 0.61 +- 0.03  | 0.55 +- 0.01  |\n| GraphTrial  | **0.86 +- 0.06**  | **0.75 +- 0.01**  | **0.72 +- 0.01**  |\n\n**Q2: In line 225, the top $k$ computation trees with the highest Shapley values are selected and denoted as $\\mathcal{C}^{*}$. Is this set composed of computation trees from every node of all graphs in the training set?**\n\n*Answer:* This is correct. \n\n**L1: Apart from the limitations discussed in Section 5 of the paper, in Eq. 7, when calculating $(\\Phi\\left(\\mathcal{G}^{S}\\right))$, the GNN may not provide correct classification probabilities for the embedding $(h^S_{\\mathcal{G}})$ due to insufficient generalization ability. This can affect the calculation of the Shapley values and, consequently, the overall performance of the method.**\n\n*Answer:* As a global GNN explainer, our primary objective is to derive a logical formula that accurately reflects the outputs of the GNN, rather than the ground truth labels. This approach means that even in cases where the GNN's prediction is incorrect due to poor generalizability, our explainer aims to produce a logical formula that predicts the same incorrect label. This fundamental property guides our design choice to compute Shapley values based on the GNN's predictions rather than the ground truth labels. By doing so, we ensure that our explanations faithfully represent the GNN's decision-making process, including any potential errors or biases, thus providing a true reflection of the model's behavior rather than an idealized version of what it should do.\n\n-------\n\n# Appeal to the reviewer:\n\nWe sincerely thank the reviewer for their thoughtful and constructive feedback on our work. In response to the suggestions provided, we have made the following significant improvements to our manuscript:\n\n1. Included detailed descriptions of the additional content recommended by the reviewer.\n2. Provided further empirical evidence demonstrating the efficacy of GraphTrail on an open-source model.\n\nIn light of these improvements, we kindly request the reviewer to *reassess our work and consider adjusting the rating to reflect these enhancements.* We remain open to any further suggestions or queries you may have.", "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": "4NeQg5lMSC", "reviewer": "Reviewer_AvDp", "summary": "The authors introduce a new global explanation generation method for GNNs. Their method uses the fact that message passing GNNs break a graph into a set of computation trees. They use Shapley values to then compute the influence of each computation tree. This is then mapped to a boolean formula over concepts. They note that the search space of trees is linear vs the exponential search space of all possible subgraphs. They compute computation trees as paths for each node. Therefore, there are n possible computation trees; one for each node. After each of the computation trees are evaluated via Shapley values the top-k trees are sent to their logical formulator where logical rules are generated. They then evaluate and compare fidelity scores across several different GNN architectures and datasets. They also evaluate the effect of varying the choice of k.", "questions": "I suggest the author’s add additional experiments that strengthen this method’s claims. Adding other global explanation methods and even instance-level explanations could demonstrate the strengths of this method. \n\nPlease also address all the weaknesses.", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "S1. The paper fills a gap in the literature; utilizing shapley values to generate global explanations of computation trees.\nS2. The idea seems sound and successfully reduces the computationally intractable problem of computing shapley values over all possible subgraphs to just the computational trees of graphs. \nS3. Experimental results seem to support some of the authors’ claims and some ideal behaviour required in interpretable AI can be witnessed.", "weaknesses": "W1. The experimental results are not sufficient to justify this method’s superiority as an explanation method. The fidelity of their explanations just compares to GLG. It is understandable that this is a global explanation method that uses logical rules so it should compare to other similar global explanation methods, there still should be some comparison to other explanation methods. \n\nW2. The explanations generated can be more interpretable than other global explanation methods. However, the explanations are still not very easy to read and can be very long and complex.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1/W1: I suggest the author’s add additional experiments that strengthen this method’s claims. Adding other global explanation methods and even instance-level explanations could demonstrate the strengths of this method.**\n\n*Answer:* We did not compare with any other explainer since none of the existing algorithms generate a logical formula over concepts to explain GNN predictions. Nonetheless, based on this suggestion, we have added three more explainers: GNNExplainer (local) [1], PGExplainer (local) [2] and XGNN (global) [3]. \n\nFor local explainers, which produce an explanation subgraph for each input graph, we generated explanations for all graphs in the training set. We then applied the logical formula as an OR operation over all these subgraphs. In practice, this means that if any of the local explanations from a graph with a GNN-predicted class Y is present in a test graph, then that test graph is predicted to be from class Y.\n\nXGNN, being a global explainer, operates differently. Instead of producing a graph, it uses a graph generator that creates graphs, maximizing the prediction likelihood of a target class label by the GNN being explained. For our comparison, we generated 3 graphs per class from XGNN and, similar to the local explainers, employed a logical formula that is an OR operation over all these explanations.\n\nThe results of this expanded comparison are presented in the table below. Notably, XGNN, despite being a global explainer, shows the weakest performance. This is likely because the graphs it generates are rarely contained (subgraph isomorphic) in any of the test graphs. Local explainers also demonstrate lower efficacy, as their local explanations fail to capture global patterns effectively.\n\n|Algorithm|BAMultiShapes|Mutag|Mutagenicity|\n|--|--|--|--|\nGnnExplainer|0.54| 0.73|0.46 |\nPGExplainer|0.54|0.71|0.44|\nXGNN|0.45|0.30|0.43|\nGLGExplainer|0.51|0.74|0.62|\nGraphTrail|**0.87**|**0.83**|**0.72**|\n\n[1] Rex Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. 2019. GNNExplainer: generating explanations for graph neural networks. NeurIPS '19.\n\n[2] Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang. 2020. Parameterized explainer for graph neural network. In NeurIPS '20. \n\n[3] Hao Yuan, Jiliang Tang, Xia Hu, and Shuiwang Ji. 2020. XGNN: Towards Model-Level Explanations of Graph Neural Networks. In KDD '20. \n\n**W2. The explanations generated can be more interpretable than other global explanation methods. However, the explanations are still not very easy to read and can be very long and complex.**\n\n*Answer:* We acknowledge the potential for further enhancing GNN explainability. However, it's crucial to recognize that in datasets where the underlying property is inherently a function of multiple concepts (such as motifs), the ground-truth logical formula itself may necessarily be complex. This is exemplified in the Mutag and Mutagenicity datasets, where the property is attributed to the presence of eight distinct toxicophores (subgraphs) [4]. Similarly, the BAMultishapes dataset, which provides ground-truth logical formulas, exhibits formula sizes (variables + operators) exceeding 10 for both classes.\n\nGiven these intrinsic complexities, the challenge lies in striking a balance between interpretability and fidelity. Generating concise, easily interpretable formulas while maintaining high fidelity to the underlying data patterns remains an open research problem.\n\n[4] Debnath AK, Lopez de Compadre RL, Debnath G, Shusterman AJ, Hansch C. Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. Correlation with molecular orbital energies and hydrophobicity. J Med Chem. 1991 Feb;34(2):786-97.\n\n-----\n\n# Appeal to the reviewer:\n\nWe appreciate the reviewer's constructive feedback on our work. We have incorporated additional baselines as suggested. We would be grateful if the reviewer could reassess our paper in light of these improvements and consider adjusting the rating accordingly.", "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:
We sincerely thank the reviewers for their insightful and constructive feedback. Below, we provide a comprehensive point-by-point response to their comments. Additionally, **we have attached a PDF document** containing various new empirical analyses as suggested by the reviewers. Key revisions include:

1. Enhanced Empirical Benchmarking:
   * Integration of **three new baselines**: GNNExplainer, PGExplainer, and XGNN 
   * **Additional assessment metrics** (along with Precision, Recall, F1) to measure efficacy of explainers.
   * **Accuracy of the generated formulas** against ground-truth labels.
   * **Statistical Significance** of the results with paired T-tests.
   * **Ablation study** on selection of computation trees with Shapley values vs. a random selection.

2. Clarifications and presentation improvements:
   * Potential reasons behind non-reproducibility in GLGExplainer.
   * Additional details on symbolic regression, canonical label construction, and optimizing Shapley computation.
   * Various other presentation enhancements as suggested by the reviewers

We hope these revisions have strengthened our manuscript. *We kindly request the reviewers to reassess their ratings in light of this rebuttal.* We are open to further engagement with the reviewers for any additional queries or suggestions. 

----------------
## Detailed descriptions of Symbolic Regression, Depth-first canonical form and efficient Shapley computation as requested by Reviewer `Sg1i`

**Symbolic Regression:** 

>In symbolic regression, given a set of $n$ input-output pairs $\{(x_i, y_i)\}_{i=1}^n$, where $x_i \in \mathbb{R}^{d}$ is an input vector, and $y_i \in \mathbb{R}$ is the output value (or label), and a set of operators, such as addition, subtraction, etc., the goal is to find a symbolic equation $e$ and corresponding function $f_e$ such that $\forall i,\: y_i \approx f_e(x_i)$, while also reducing the complexity (number of operators and variable) of the formula. The loss function is presented in Eq. 11. Finding the optimal formula is not computationally tractable since the number of formulas grows exponentially with the number of variables and operations. Hence, from various approximation strategies in the literature [23] and we use [6], which leverages an evolutionary algorithm.
>
> The process begins by initializing $n_p$ populations, each with $L$ random expressions of complexity $C$ (3 in our experiments). For each $P_i$, a set $M_i$ is created to store the expressions with the smallest loss (Eq. 11) at each complexity level within that population. Additionally, a global set $H$ is maintained to store the expressions with lowest loss at each complexity across all populations.
>
>The algorithm iterates over each population $P_i$ for a fixed number of epochs, allowing them to evolve. Evolution is driven by running tournaments within each population, where the expression $E$ with lowest loss is declared the winner. A copy of the winner is created and chosen for *mutation* or *crossover*, forming $E^*$. Mutating an expression involves repeatedly applying random operations from a set of operations, e.g., replacing/adding operators and variables. Crossover selects the two best expressions, $E_1, E_2$, from the population and swapping random sub-expressions between them, forming $E_1^*, E_2^*$. The newly formed expression(s) replace the oldest expression(s) in the population.
>
>Once evolution within each population is complete, the sets $M_i$ and $H$ are updated with the best expressions. Once the chosen number of epochs is complete, the expression from $H$ with minimum loss is returned.

**Depth-first Canonical Form (DFCF):**
>**Canonical Labeling:** *A canonical label of a graph $\mathcal{G}$ is a unique representation that remains unchanged under isomorphisms, i.e., two graphs $\mathcal{G}_1$ and $\mathcal{G}_2$ have the same canonical label *iff* they are isomorphic.*
>
>We construct the canonical label of a rooted computation tree through *Depth-First Canonical Labeling*. From a labelled rooted unordered tree we can derive many labelled rooted ordered trees as shown in `Fig. 1 in the rebuttal pdf`. There is a one-to-one correspondence between a labelled rooted ordered tree and its depth-first string encoding. The ordering of the strings orders the trees and the minimum in the ordering is the canonical label. Each string is a depth-first (preorder) traversal that uses 'dollar' to represent a backtrack and 'hash' to represent the end of the string encoding. In sorting, 'hash' is greater than 'dollar' and both these symbols are greater than other labels.

>The Depth-First Canonical Form (DFCF) is constructed by sorting the vertices of a rooted unordered tree level by level. At each level, the vertices are sorted first by their labels and then by the ranks of their children at respective levels. `Fig. 2 in the rebuttal pdf` illustrates the process. 

**Shapley** 

> SHAP represents the Shapley value (SV) explanation as an additive feature attribution method and fits a weighted linear regression model to approximate the model's output. The weights in this model correspond to the SVs (contribution of features). It specifies the explanation as: $g(z)=\phi_0 + \sum_{j=1}^M \phi_jz_j $
where $g$ is the model, $z\in {0,1}^M$ is the coalition vector, $M$ is the maximum coalition size, and $\phi_j \in R$ is the SV for a feature $j$. 
>Kernel-SHAP is a SHAP variant to estimate SVs. It calculates SVs via:
>* **Coalition Sampling:** It randomly selects subsets of features, coalitions $(z_k)$. It assigns weights to each coalition using the SHAP kernel:
$ \pi(z) = \frac{(M - 1)}{{M \choose x} |z| (M - |z|)} $; $M=$ total features, $|z|=$ coalition size.
>* **Predictions:** For each coalition, Kernel-SHAP maps the coalition back to the original features and obtains a prediction afterwards.
>* **Fitting:** Using the calculated weights and predictions, Kernel-SHAP fits a linear model. 

**Please see the attached pdf.**

Meta-review: Three of the four reviewers agree that the paper should be accepted. The consensus among these reviewers is that the authors describe a novel instance-level explainability method for GNNs, that the experiments are strong, outperforming existing methods, and that the number of datasets in the experiments is extensive. One reviewer tended towards rejecting the paper, but the arguments were short and weak, lacking details. After the rebuttal said reviewer simply acknowledged the rebuttal and did not change their score. Hence, I weigh their assessment of the paper much lower than those of the positive reviewers.
Decision: Accept (poster)