SAME: Uncovering GNN Black Box with Structure-aware Shapley-based Multipiece Explanations
Authors: Ziyuan Ye
Rihan Huang
Qilin Wu
Quanying Liu
Venue: NeurIPS 2023 poster (2023)
Keywords: GNN explainability
Shapley value
Monte Carlo tree search
structure awareness
multi-grained explanation

Abstract: Post-hoc explanation techniques on graph neural networks (GNNs) provide economical solutions for opening the black-box graph models without model retraining. Many GNN explanation variants have achieved state-of-the-art explaining results on a diverse set of benchmarks, while they rarely provide theoretical analysis for their inherent properties and explanatory capability. In this work, we propose $\underline{\text{S}}$tructure-$\underline{\text{A}}$ware Shapley-based $\underline{\text{M}}$ultipiece $\underline{\text{E}}$xplanation (SAME) method to address the structure-aware feature interactions challenges for GNNs explanation. Specifically, SAME leverages an expansion-based Monte Carlo tree search to explore the multi-grained structure-aware connected substructure. Afterward, the explanation results are encouraged to be informative of the graph properties by optimizing the combination of distinct single substructures. With the consideration of fair feature interactions in the process of investigating multiple connected important substructures, the explanation provided by SAME has the potential to be as explainable as the theoretically optimal explanation obtained by the Shapley value within polynomial time. Extensive experiments on real-world and synthetic benchmarks show that SAME improves the previous state-of-the-art fidelity performance by 12.9\% on BBBP, 7.01\% on MUTAG, 42.3\% on Graph-SST2, 38.9\% on Graph-SST5, 11.3\% on BA-2Motifs and 18.2\% on BA-Shapes under the same testing condition. Code is available at https://github.com/same2023neurips/same.

SAME: Uncovering GNN Black Box with Structure-aware Shapley-based Multipiece Explanation
Ziyuan Ye!2." Rihan Huang! Qilin Wul", Quanying Liu
Southern University of Science and Technology. "The Hong Kong Polytechnic University, 'King Abdullah University of Science and Technology, "Carnegie Mellon University (ziyuanye9801, rihanhuang.. work, kyrinwu) (awawalmmmmllcoomm com, liugy@sustech. edu, cn
Abstract
Post-hoc explanation techniques on graph neural networks (GNNs) provide eco- nomical solutions for opening the black-box graph models without model retraining. Many GNN explanation variants have achieved state-of state-of-the-ar explaining results diverse set of benchmarks, while they rarely provide theoretical analysis for their inherent properties and explanatory capability. In this work, we propose Grueture-Awart Shapley-based Multipiece Explanation (SAME) method to ad- dress the structure-aware feature interactions challenges for GNNs explanation. Specifically, SAME leverages an expansion-based Monte Carlo tree search plore the multi-gran gilti-ggriied structure-aware connected substructure. Afterward, the explanation results are encouraged to be informative of the graph properties by optimizing the combination of distinct single substructures. With the considera- tion of fair feature interactions in the process investigating multiple connected important substructures, the explanation provided by SAME has the potential to be as explainable as the theoretically optimal explanation obtained by the Shapley value within polynomial time. Extensive experiments on real-world and synthetic benchmarks show that SAME improves the previous state-of-the fidelity per- formance by 12.9% on BBBP, 7.01 % on MUTAG, 42.3% Graph-SST2, 38.9% on Graph-SSTS, 11.3% on BA-2Motifs and 18.2% on BA-Shapes under the same testing condition. Code is available at http://gtthubccom/mmme2222222e same
Introduction
Graph neural networks (GNNs) have demonstrated a powerful representation learning ability to deal with data non-Euclidean space. However, the explanation techniques for deep learning models on images and text cannot directly apply to understand GNNs 18 O M There is a gap in the
understanding of how GNNs work, which largely limits GNNs' application many fields.
Many GNN explanation techniques aim to examine the extent to which GNNs depend on individual nodes and edges of the graph [22 35
19 24 37.. However, graph features within nodes and edges contribute different amounts of information when considered individually than contextualized with topology [37 39 Therefore, discovering the most important explanation with
more connected components given an input graph and a well-trained GNN raises the additional challenge of handling structure-aware feature interactions. Recently, a number of studies. including GNN- LRP 25), SubgraphX 38 and GStarX 40 have endeavored to address this issue to some extent. Although many of the current GNN explanation techniques have empirically achieved state-of-the-art
"Equal contribution, co-first author.
I Corresponding author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

explainability performance, the design of new GNN explanation techniques mainly relies upon empirical intuition, iterative experiments, and heuristics principles. To the best of our knowledge. the explanatory capability, potential limitations and inherent properties of GNN explanation techniques have not yet been thoroughly studied from a theoretical perspective.
In this work, we propose a novel Structure-Awant Shapley-based Multipiece Explanation (SAME) technique for fairly considering the multi-level structure- feature interactions over the graph by introducing expansion-basse Monte Carlo tree search (MCTS). Our construction is inspired by the recently proposed perturbation-bas -based GNN explanation methods [8 EM, which have proven effective for providing explainability from a cooperative game perspective. We summarize the main differences between SAME and previous work in Table The main contributions and novelties of this work include the following (1) Theoretical aspect: i) We review the characteristies of and highlight several desired properties (see Table I that can be considered by explanation methods for GNNs. ii) We provide the loss bound of the MCTS -based explanation techniques and further verify the superiority of our expansion -based MCTS in SAME compared to previous work 38 in intuitive manner (Sec. 3.2 (2) Empirical aspect: Our experiments cover both real-world and synthetic datasets. The results show that i) SAME outperforms previous SOTA with fidelity and harmonic fidelity metrics under the same testing condition (Sec. 5.11) ii) SAME qualitatively achieves a more
previous methods [2 35
25
explanation compared to previous methods
across multiple datasets (Sec. 5.2)
Table 1: Comparison of the properties of different GNN explanation techniques.
Methods
Grad
GNN
Properties
CAM 22
ONNEsplainer
PUExxlainer
LRP
25
SubgraphX
88 GStex
SAME(Ours)
Graph-level tasks
Node-level tasks
Feature interactions
Structure awareness
Multipiece explanation
Node-wise importance
Substructure-wise importance
Composite-wiee wise importance
Priority- based integration Redundancy consideration
Multipiece explanation is provided in Sec. 3.2. Multi-gran grained imporiance (node/ / substructure composite), priority- based integration and redundancy consideration are presented in See. Detailed mathematical definitions are provided in Appendix B.
Note: Feature interactions and structure awareness are discussed in Sec. 3.]
2 Related Work
Improving the explainability of GNN models in a post-hoc fashion has been a theme in deep graph learning. An intuitive way explain well-trained GNN is to trace the gradient in the models 22 where the larger gradient indicates the higher importance of node or edge of the graph. Previous work has also studied the decomposition-based methods 26 25
which decompose the final prediction into several terms and mark them as the important scores for input features. Another line of GNN ex explanaiion techniques lies in perturbation-basee methods 19 mask for the input graph in various ways to identify the important input feature. SubgraphX (38) as one of perturbation-base based MCTS and finds the most important one via the Shapley value. However, the pruning- based MCTS in SubgraphX leads to a much larger search space and thus causes higher computational costs. Moreover, SubgraphX can only provide a single connected explanation for each graph, which limits its explanatory power in many scenarios that require multipiece explanation. Most recently. GStarX 40 scores node importance based on the Caamiache-Navaree (HN) value. Although GStarX also fairly considers the structure-aware feature interactions, fails to account for the multi-grained importance, which might result in suboptimal explanation. For other categories in GNN explanation
14 which usually obtain
method, samples the subgraphs from the input graph by the pruning-
techniques, including surrogate methods (30
generation-bast methods (36 15]
and
counterfactual based methods
16
we refer readers to recent survey
37

---

3 Theoretical Motivation
Notation and Preliminaries. The well-trained target GNN be explained can be formulated as f: G ++y, Y" where G denotes the space of input graphs and y refers to the related label space. A graph can be denoted feature set and E' E R denotes edge set. Given well-trained GNN model f()) and an input graph G, the goal of GNN explanation is to find the most important explanation G²p from G. Formally, this can be defined as an optimization problem that maximizes the importance of the explanation Gez for given graph with n nodes using an importance scoring function (()()), Gez: G):
G (V, X, E)), where V Æ=x=" represents node set, X [R" x is the node
Ge ez
arg max T(((),, Gez: G);
G.
where each explanation Gh. has n; nodes, and the other nodes not in the explanation can be expressed as (G. = {Ty )j=n.++ It is noteworthy that each explanation Gt,, might contain one or more substructures (i.e., connected components).
3.1 Structure-aware Shapley-based Explanations Satisfies Fairness Axioms
Unlike grid-like images or sequence-like texts, graphs have more complex and abstract structures. The importance scoring function of explanations determines the reliability and explanatory power of the GNN explanation method. Therefore, we present the idea that a comprehensive assessment of the importance of an explanation should consider the feature interactions under the constraints of the input graph's 's topology.
Shapley value (28), originating from cooperative game theory, is the unique credit allocation scheme that satisfies the fairness axioms. This concept is similar to the importance scoring function for explanation with the consideration of feature interactions. Some previous work have brought Shapley value into deep learning explanation methods [18. [4]. In our study, the importance assessment of explanation is treated as cooperative game, where the explanation Gi and all nodes not in the
explanation (G) are the players in the game. Therefore, when scoring the importance of any explanation G a set of players participating in the game can be denoted as:
P; = (Gr Eart Un Un
Un
(G
Inspired by the close connection between feature interactions and Shapley value, we define several desirable properties of importance scoring function for explanation according to fairness axioms:
Property 1. (Efficiency)- The sum importance of all players Pj in P; is the same as the improve- ment of GNN (() on P3 over an empty set, E)AL T( Py. G) = ((P)) S(0).
Property& 2. (Symmetry). For any explanation Gi.n if there exist two other players Pj. Pk (P./Gin that satisfy f (G Up) f(G:. UT), then I(f(-),;; G) = I(f((), Pk, G).
Property 3. (Dummy).. a player Pj makes no contribution to GNN f(-), i.e. S(G Upj) f(G) holds for any G then I(f(-).p,. G) 0.
Property 4. (Monotonicity). Consider two well-trained GNN models fi(-) and f2(+), given an explanation Ge for any player Pj. (i Up;) fi(p) 2 [2(G Up;) - -2((p)) always holds, then T()()), Gi G) 2 ( G
Shapley value can well satisfy the above four fairness Properties I However, the Shapley- importance scoring function attempts to take all nodes in the graph except explanation G into the cooperation game, which not only ignores the topological information of the input graph but also brings huge computational costs. Fortunately, (38] alleviate this issue by modifying the Shapley- based importance scoring function as 'k-hop Shapley', which also makes it structure-aware.
Dpll([Pe.Aoop)) - lps| 11)! (f(p -
I(f(-) G G)
Σ (P G
(2)
Pr
3

---

where I(f(-) Gan. 9) denotes the weighted sum of the marginal contribution of explanation Gz and Pi,shhp {Gest +1, Un.+2:..... Un.+k. includes the nodes within the G as well as the nodes in the k-hop neighbors of G
3.2 Structure-aware Shapley-baser Multipiece Explanation Provide Strong Explainability
The characteristics and properties within graph or node tend to be jointly influenced by more than one high-order connected community of the graph. This implies that the appropriate explanation within this context requires the GNN explanation method to provide the multiple connected substructures simultaneously.
To solve the above challenge, we first define the mathematical formalization of the search processes on graphs by utilizing the MCTS-based GNN explanation methods. Then we propose mathematically coherent framework to explore the explanatory power of MCTS-based GNN explanation methods using computational methods for the multi-armed bandit problem in the MCTS algorithm (20) [3]
Our mathematical framework is based on the hierarchical partitioning of the MCTS search space X. More precisely, the smoothness of the MCTS search space X' can be defined by the inequality If(,,) - [xzz) S 1[x; Fy)) where ((r, xty) refers to the Lipschitz continuity between any two substructures 2y and , in X. It serves
critical metric ascertain the boundedness of the change in the explanation method f(-) concerning the change in input substructures. Assuming that the function f-( is Lipschitz continuous and the is given, an evaluation of the function f()) at any point I, enables us to define an upper bounding function (x) for f(-). This upper bounding function can be refined after each evaluation of f()):
Va X, f(x) S B((x) def min (f(x)) + x,x,,,)),, Isa5e
where metric satisfies the following Assumptions In the context of computational uncertainties associated with MCTS, the evaluation strategy in offers the potential to describe specific numerical estimates within an undefinable space.
Assumption 1. (Local smoothness). There exists at least stage-optimal substructure x² E X of f() (i.e. f(**) = supsex f(x)) and Vx E ((x) - S 1(x, holds.
Assumption (Decreasing diameters). There exists decreasing sequence 8(h) > 0, such that for any depth h 2 0 and for any cell Xn.; of depth h, supx,.; 1(X, I 5(h) holds.
Assumption 3. (Well-shaped cells). There exists v > 0 such that for any depth h 2 0, any cell Kn, contains a I-ball of radius v8(h) centered in Th,t-
With the given assumptions, the search space X' can be partitioned into KH subsets (i.e., cells) Xn, using a K K-ary tree of depth H, where 0 < h < H,O S i < Kh-1, Based on this partitioning method, the MCTS process can be treated as the expansion of this K-ary tree. The root of К K-ary tree (i.e., cell Xo,0) corresponds to the whole search space X. Each cell Xr corresponds to node (h of the tree, where h denotes the depth of the tree and refers the index. Each node (h, i) possesses K children nodes {(h + 1, ixx) hisss s.t. the associated cells {Xh+1.iz < k S K} form a partition of the parent's cell Xr... Consequently, expanding one node requires adding one of its K children to the current tree, which corresponds to subdividing the cell Xn into K children cells (Xr+ 1 1. ......... K1.1.jk J. Assume that there exist a decreasing sequence 8(h) 2 0 that satisfies su,,,. 1(X, Xn.i) S 5(h) for any Xn. The decreasing sequence 5(h) ensures that each cell size reduces with increasing depth.
The search space X' be divided through the above partitioning method according to 5(h), with respect to 1-open balls. Let T, denote nodes of the current tree, and L, denotes the incoming leaves of T, be expanded at round l. Recalling our earlier definition of (h) which was derived from the Lipschitz continuity, we can now generalize it to a new representation that connects to o(h). Formally, it is expressed as:
b f(xh,)) + ((h).
(4)

---

Based on this, we now consider which nodes will be expanded during the search. Note that Assump- tion 2 implies that the v-value of any cell contains xx upper bounds f*. other words, for any cell Nn,; such that x' E Kh.i.
bh. = f(xn,)) o(h) 2 (xhh,)) + (Zh,i, x f
(5)
This means that leaf (h, of K-ary tree will never be expanded if f( 8(h) < f Therefore, under this partitioning strategy, the only set of nodes that will be expanded could be defined as I def Ukzoln. which could be stated as
de (nodes i} such that f( + 5(h) 2 f*)
In
(6)
In order to derive a loss bound, we now define a measure of the quantity of near-optimal states, called near-optimality dimension. For any > O, the set of e-optimal states can be defined as
Xe = {I E X, f(z) 2 f c].
dimension). The n--naa-optimality dimension is the smallest d 2 0 such that there exists C 2 0, for all O, the maximum number of disjoint I-balls of radius N/C with centers in X. is less than Cc-d.
Definition 1. (n-near-optimalle
Definition represents the number of near-optimal states for a function f(-) around its optimal solution. It important optimal states using 1-balls. Instead, it characterizes both f(-) and and depends on the constant. In order to relate this measure to the algorithmic details, we also need to correlate it with the characteristics of the partitioning, specifically the shape of the cells. That is, the near-optimality dimension is dependent on a particular constant, which will be determined accordance with the parameter y as defined in Assumption
that d is not intrinsic property of f(()) as we are packing near-
Lemma 1. Let d be the v-near-optin n-near-optimaalty dimension, and C the corresponding constant. Then I $ C5(h)
Building upon Lemma | we further analyze the loss of the MCTS-based GNN explanation methods across iterations in Theorem [
Theorem 1. Let write li(n) the smallest integer h such that C ((1)<-)) 2 then the loss of the MCTS-based GNN explanation methods is bounded as:
Tn S 8(h(n))
(8)
The loss In reflects the gap between the obtained and optimal explanations over iterations. We aim to bound this loss by 6(h(n)), illustrating that refining the partition of the search space X' reduces the loss, thus better approximating the optimal explanation. We provide a complete description of the mathematical properties and theorem proofs of the framework in Appendix B.2.
Shapley
Shapley
Shop ey
Shopley
Shapley
Optimal explanation
Suboptimal explanations
Node that match ground truth explanation
that ground explanation
Illustration of ground truth explanation and the possible sub-optimal explanations provided by praning-based MCTS explanation techniques.
Figure I:
Leveraging the mathematical underpinnings provided above, as demonstrated in Figure D we employ an example to contextualize the theoretical insights within the GNN explanation. The ground truth
5

---

explanation is highlighted in yellow which includes two connected components. When searching for explanations starting from any node the two components through the pruning-basee MCTS, the nodes in other components are accessible only via the unimportant node which is highlighted in blue. In this situation, given sparsity constraints, the pruning-baset MCTS can only generate the suboptimal explanation. As consequence, regardless of the search trajectory adopted, the diameter of the I-ball remains unyielding, failing to converge to the 7y-naar optimality numerical solution. Therefore, is necessary to design explanation method that can accurately retain important nodes while avoiding irrelevant nodes, thus increasing the likelihood discovering the optimal explanation. This ambition resonates with previously proposed loss bound In I (()())). emphasizing the need for advanced exploration to reduce losses and approximate the optimal explanation with higher precision.
(4)
(b)
(c)
Nade
Important Substructure Set
Optimal Explanation
Rood Nade
Leaf Node
Node-wla
Expansion
Substructurewiis Tree Expansiio
Schstructure wiss Tree Expansion
Update
Update
Node-wise Tree Expansion
Explanation Candidate
Explanation
Leaf Nodie
Figure 2: Overview of Structure-Aware Shapley-based Multipiece Explanation (SAME) method. (a) Important substructure initialization phase aims searching the single connected important substructure. (b) Explanation exploration phase provides a candidate set of explanations by optimizing the combination of different important substructures. (c) The comparison of the final explanation with the highest importance score from the candidate set with the optimal explanation.
4 Structure-awars Shapley-based Multipiece Explanation Method
As we discussed Section 3 the crueture-awar Shapley- based multipiece explanation provides a potential way effectively uncover the GNN black box. In order approximate the optimal Shapley- based explanation, we propose a two-phase framework, Structure-aware Shapley-based Multipiece Explanation (SAME) method, which is composed of (1) important substructure initialization phase and (2) an explanation exploration phase, as shown in Figure.
extend expansion- based Monte Carlo tree search an important substructure initializer to generate connected components not only of high importance but also of multi-graines diversity. In the second phase (Section 4.2), apply the important substructure set as an action set in another expansion-bai based Monte Carlo tree search to explore potential explanations.
In the first phase (Section[4.1)
4.1 Important Substructure Initialization
In this section, propose an expansion-basee MCTS approach for important substructure initializa- tion. is intuitive that favorable initialization should not exclude important substructures at any scale and should not include redundant substructures. Formally, these can be defined as:
Property 5. (Node-wise importance). Given an input graph to be explained, for any node E G. its I(f(-), Ug. G) importance will be considered.
Property 6. (Substructure-vit importance). Given an input graph G to be explained, for any substructure Guu,, S G, its importance T(J(), G G) will be considered.

---

Property 7. (Composite-wue importance). Given an explanation Gooom S G consisting of one or more substructures, its importance ((f Go Coom G) will be considered.
Property 8. (Priority-based integration). Given an explanation G with any size, the node vi HG\. ex) will be added on Gi to get a new explanation G if and only if for any (G)(Ge Ues) IU(),, G U 04, G) > I(((),, G U Ut, G) holds.
Property 9. (Redundancy consideration). Given an explanation Ger S C, Ges V(). G) > T.)()); Gez, G) holds, the new explanation Ge = Gez Vi) will be chosen.
Taking the above properties into account, we propose our expansion-based Monte Carlo tree search for important substructure initialization which aims at providing important connected components of the graph. The detailed Algorithm is presented in Appendix C. Given graph G to be explained, the node in the MCTS is defined as N, which contains the following variables:
N₂ : {G Tu, R2, A,, C., W3}
where G denotes the corresponding substructure of graph G for node N; in the search tree. T; is the visiting time of node N; in the search tree, R2 refers to the the importance (reward) of substructure Gaub- A, represents the action set of node N₁- C; = {N, ز represents a set of children with respect to node N,, and we denote Nj as one of the child nodes obtained through the action a, E A, at parent node N,. W; means the sum of the children's 's rewards.
The expansion- based MCTS is initialized with an empty set, No 0. At the beginning of each iteration, our method will randomly choose an unvisited node from the graph, or choose the node with the highest reward if all nodes have been visited. Then, the tree will be iteratively expanded according to the node-wise free expansion until it reaches leaf node. Specifically, given an MCTS node N,, will only choose the child node within 1-hop neighbors of the associate G to expand, which means that the action set is topology dependent. Therefore, the substructure of any nodes in the search tree will be connected component. During the child node selection, the reward of each child node Rj of N, will be calculated following Equation following the child selection strategy:
Finally, the chosen action is decided
V ExEC. Tk Ir
W3 Т₃
a" arg max + 3R,
(9)
4
where 3 is hyperparameter for balancing exploration-exploitaiion trade-off 4 We define the maximum substructure size as 7, and for any G S G. |G S always holds. After reaching the maximum substructure size, the reward of associated leaf nodes is backpropagated up the tree along the search path, updating all the information stored in each node of the path. The important substructure set includes all nodes in MCTS after performing M1 times iterations.
4.2 Explanation Exploration
In this section, we propose another expansion-bars based MCTS for exploring high-explainable explana- tions. The detailed algorithm is provided in Appendix C. Different from the previous expansion-basee MCTS provided in Section 4.1 I we propose a slight modification on it such that we change the action set from node level to substructure level. As Section 3.2 discussed, this can be useful not only to obtain more flexible explanation results on real-world cases but also to provide the higher potential to approximate the theoretically optimal Shapley- based explanation.
The action set of MCTS in this phase is built upon the substructure set derived from the important substructure initialization phase. Similar to the previous MCTS, at the beginning of each iteration, will randomly select an unvisited substructure from the set, or choose the substructure with the highest reward to expand if all substructures have been visited. Afterward, the substructure tree expansion also follows the Equation ( and ( to develop the tree and provide the explanation candidate. The action set corresponding to each node of MCTS in the phase is the whole substructure set. To further accelerate the exploration, we filter the unimportant substructures by only keeping the top K important substructure in the action set.
7

---

Notice that calculating all possible combinations of either substructures or nodes can definitely obtain the optimal Shapley-base explanation. Nevertheless, such node-wise or substructure-wiss brute force methods lead to O VI) computational complexity, which is an NP-hard problem. We provide feasible solution to approximate the optimal Shapley-based explanation in polynomial time ( + Mr V x E MyKt, (akllapavsstt) ), where M1 and M2 denote maximum number of iterations of the first phase and second phase respectively, " is the maximum substructure size, K refers to the size of the important substructure set and t, is the time budget of MCTS in the second phase. We leave the derivation of the time complexity in Appendix B.4.
Table 2: Comparison of our SAME and other baseline using fidelity.
Dataset
Graph classification
Node classif.
Molecular graph
Semantic graph
Synthetic graph
Methods
BBBP
MUTAG
Graph-SST2
Graph-SSTS
BA-2Motifs Bh-Shapes
Grad CAd
0.226=0.036
0.201
0.257=0.056
0.229::0002
0.472:t0.010
GNNExplainer
35
0.148=0.041 0.188:10.031
0.143:10.041
0.170:10.046
0.442:100026
0.154:1..000
PGExplainer
19
0.147 0.156:10.004
0.219=0.040
0.207:10.036
0.431+:.0111
0.135:10.020
GNN-LRP
25
0.111=0.040 0.253
0.103=00042
0.131
0.146:+00010
0.155++0.000
SubgraphX
38
0.433=0.073 0.379=0.030
0.262=0.027
0.283:10.042
0.493++0.00 0.00
0.181+10.005
GStarX
20
0.117=0.043 0.656=1.00%
0.183=0.050
0.1861100050
0.476:1..014
SAME
0.489 0.034
0.702-+0.125
0.043
0.39
0.549++0.004
0.214++0.000
Relative Improve
12.9%
7.01 %
42.3%
38.9%1
11.3%
18.2%
The fidelity results are averaged across different sparsity from 0.5 to 0.8. The quantitative results are presented in the form of mean + std. The previous SOTA results on different datasets are marked with an underline. Relative Improve denotes the relative improvement of our SAME method over the SOTA methods.
Note:
Experiments
Our objective of the experiments is to understand the following two questions. 1) Are the explanations provided by SAME more informative and faithful compared other methods under the same test conditions? 2) Can SAME provide a more human-intuitive explanation than others? To this end, we perform extensive quantitative and qualitative analysis evaluate the explanatory power of SAME,
following previous literature [8] 40 The SAME is compared with various competitive baselines
and shows state-of-the-art (SOTA) results in all the cases.
Dataset. The experiments are conducted on six datasets with diverse categories, including molecular
graphs (c.g., BBBP [33 and MUTAG M). ). sentiment graphs (c.g., Graph-SST2 and Graph-SST5 [29 and synthetic Barabási-Albes graphs (c.g., BA-2Motifss [1]] and BA-Shapes (35)). We conduct a node classification task for the BA-Shapes dataset, and graph classification tasks for the rest five datasets. More detailed descriptions of datasets are provided in Appendix D.
Metrics. In this work, we use several criteria h to evaluate our approach: (1) Sparsity quantifies how compact are the explanations, and further facilitates fair comparison by restricting the different explanations to the same size. (2) Fidelity determines how informative and faithful are the explanations by removing the selected nodes. (3) Inv-Fidelity measures the explanations from the same aspect as fidelity while it keeps the selected nodes. (4) Harmonic fidelity 40 normalizes fidelity by sparsity and takes a harmonic mean to make different explanations comparable with a single metric. We Ieave detailed mathematical definitions of the above metrics in Appendix E.
Experimental setup. In the important substructure initialization phase, we set the MCTS iteration number Mj to 20. The pnploratioo-xpplittttiii datasets. The substructure size 7 has different settings in different datasets. In the explanation exploration phase, we set the hyperparameter K = 7 for important substructure filtering, M2 = 10 for the MCTS iteration number, and the other hyperparameters of MCTS remain the same as the previous phase. We follow [37] 40 to set other baselines hyperparameters. All methods are implemented in PyTorch 21 and PyG 10. Our experiments are conducted on a single Nvidia V100
trade-off /3 is set to 5 for BBBP and 10 for other
GPU with an Intel Xcon Gold 5218 CPU. We leave the detailed settings in Appendix F.
8

---

Table 3: Comparison of inference time (in seconds) different datasets.
Dataset
BBBP
MUTAG
Graph-SST2
Graph-SSTS
BA-2Motifs
BA-Shapes
Methods
Grad-CAM
22
0.16
0.23
0.39
0.44
0.14
GNNExplainer
35
7.56
1.96
7.64
19.39
1.89
2.72
PGExplainer
10
0.15
0.21
0.35
0.43
0.13
GNN-LRP
25
2.37
1.97
5.84
5.47
3.30
51.77
SubgraphX
K8
26.72
151.75
36.48
71.32
85,50
162.80
GStarX
40
84.54
25.24
30.64
54.49
77.99
SAME
7.86
5.67
6.06
8.83
8.19
14.08
Note: The PGExplainer needs training before inferring the explanation.
Sentence: carefully structured of consciousness that tortured and unsettling but unquestionubly alive."
Grad-CAM
GNNExplainer
PGEXxpainne
of
of
cons.
struct.
carefully
cons.
struct.
Hearefully
cons.
struet.
carcfully
fortured
that
that
fortured
and
unset.
and unset
and unset
GNN-LRP unques but unques.
GStarX alive unquee.
SubgraphX scream of scream a of scream a of screamm struct
SAME(ours)
of
Carefullly cons. struct. carefally coms. stract. carefully coms. stract. tortured that tostured is that tortured is that fortured unset.
curefullyy
that
unset. and
and uaset.
and waset.
alive
unques.
but
alive
unques.
but alive
unques.
but
alive
unquees
Figure 3: Comparison of the explanations Graph-SST2 with GCN classifier.
5.1
Quantitative Analysis
To validate the overall explainability performance, we compare the proposed SAME with series of competitive baselines under different metrics. Table shows the averaged fidelity under different sparsity (i.e., sparsity=(0.5,066000 6.0........)).. The proposed SAME significantly outperforms the previous state-of-the-art on both real-world and synthetic datasets. Specifically, the performance improvement of SAME is 12.9% on BBBP, 7.01% % on MUTAG, 42.3% on Graph-SST2, 38.9% on Graph-SST5, 11.3% on BA-2Motifs and 18.2% on BA-Shapes. Notably, we also demonstrate reliable improvements of SAME over previous SOTA methods in terms of harmonic fidelity different sparsities, with an average improvement of 1.92% on the graph classification task. This result implies SAME has higher ability to discover important components in the graph than all baseline methods. As for the inv-fidelity metric, the explanatory power of SAME is competitive compared with the previous SOTA. Detailed results for harmonic fidelity and inv-fidelity are Appendix G.I. Since the proposed SAME is a model-agnostic method, it works well with GAT and GIN. More comparisons with GraphSVX g and OrphicX [66 are provided Appendix G.3.
The computational cost of SAME and other baselines on different datasets are summarized in Table We show that SAME consistently achieves much lower computational cost compared GStarX and SubgraphX, reflecting its efficiency and robustness. This further verifies that expansion-base MCTS in SAME can work effectively various scenarios.
5.2 Qualitative Analysis
3 presents the visualization comparison of the explanations sentiment graphs. The nodes of adjectives and adverbs are considered to be important for they reveal the attitude of sentence. Thus, the optimal explanation here is therefore the word phrase with positive meaning. In this sense.
Figure

---

GNN-LRP
SubgraphX
GStarX
SA (ourr))))
Grad-CAM
GNNExplaine
PGFxxplainer
Ground Truth
Figure 4: Comparison of the explanations on MUTAG with GIN classifier.
GNN-LRP
SubgraphX
GStarX
SAMF(ourS)
Fidelity:-Oin -0.03 Sparsity 0.
Fidelty: 0.28 Spursity-0.83
Fidelity: 0,50 Sparsity-tt.. 04
Fidelity: 0.99 Spansity:0 07
Grad-CAM
GNNExplainer
PGExxpainne
Ground Truth
Fidelity: Spunsity:0.81
Fidelity: 0.38 Spursity
Fidelity: Sparsity:0.80
Fidelity: Sporsity:0.
Figure 5: Comparison of the explanations on BA-2Motifs with GCN classifier.
SAME can better capture the adjectives-or--adverbs---- graph structures than other baselines. For instance, SubgraphX focuses on adjectives and adverbs but fails to capture the "but" word which bears significant weight under contrasting relationship. Intuitively, without the "but", the contribution of "tortured" and "unsettling" should be negative. GStarX achieves to identify words that consistent with the opinion such as "carefully" and "alive," yet overlooks the crucial transitional relationship between "alive" and "unsettling". Figure 4 shows the visualization of explanations graphs. The ground truth explanations (i.e., functional group ~NO2 of MUTAG are labelled by human experts. We that SAME is able to provide the explanations the same the ground truth. We also illustrate the explanation of the synthetic graph in Figure 5 The ground-truth label all the graphs in BA-2Motifs ground-truth explanation compared to other baselines. We leave more comparisons in Appendix G.2.
molecular
-node-hhuuse-ttuucuue motif. Results show that SAME exactly finds the
Conclusion
Structure-aware Shapley-based Multipiece Explanation provides strong explainability over GNN models, while this ability limited by only using the single connected substructure. Moving forward from the theoretical deduction, we propose the SAME method for explaining GNN, novel perturbation- based method that is aware of input graph structure, feature interactions, and multi-grained importance. Experimental results demonstrate that our SAME consistently outperforms SOTA methods on multiple benchmarks by a large margin with various metrics and provides a more understandable explanation.
Limitations. In the implementation SAME, the Shapley value obtained through approximation following (38). Under this approximation, the faimess axioms discussed in Section 3.1 no longer hold. This also identified as an unsolved issue for Shapley value machine learning by 23 In addition, the scalability of SAME on large graphs can also become a potential challenge. As the time complexity shown in Section 4 the time overhead caused by the increase the number of nodes will become very expensive when scaling up the size of the input graph.
10

---

Acknowledgements
This work was funded in part by the National Key R&D Program of China (202 National Natural Science Foundation of China (62001205), Shenzhen Science and Technology Innovation Committee (2022410129, KCXIZ2020122117340001) Shenzhen-Hone Kong-Macao Science and Technology Innovation Project (SGDX20201 103099800000000 Guangdong Provincial Key Laboratory of Advanced Biomaterials (2022B 22120100)3).
We would like to extend our sincere appreciation to Dr. Jialin Liu for her insightful suggestions on the manuscript composition and the elucidation of definitions.
References
[1] S. Ali, T. Abuhmed, S. El-Sappagh, K. Muhammad, J. M. Alonso-Moral R. Confalomieri, R. Guidotti, J. Del Ser, N. Díaz- Rodrigzzrg and F. Herrera. Explainable artificial intelligence (xai): What we know and what is left attain trustworthy artificial intelligence. Information Fusion, page 101805, 2023.
[2] Bajaj. Chu, Z. Y. Xue, Pei, Wang, C.-H. Lam, and Zhang. Robust counterfactual explanations on graph neural networks. Advances Neural Information Processing Systems, 34:5644- 5655, 2021.
[3] F. Baldassarre and H. Azizpour. Explainability techniques for graph convolutional networks. In Interna- tional Conference Machine Learning (ICML) Workshops, 2019 Workshop Learning and Reasoning with Graph- Structured Representations, 2019.
[4] C. Browne, E. Powley, D. Whitehouse, S. M. Lucas, Cowling, Rohlfshagen. S. Tavener, Perez, S. Samothrakis, and S. Colton. A survey of monte carlo tree search methods. IEEE Transactions on Computational Intelligence and Al in Games, 4(1):1-43, 2012.
[5] I. Covert, S. M. Lundberg, and S.-L. Lee. Understanding global feature contributions with additive importance measures. Advances in Neural Information Procesxing Systems, 33:17212-17223, 2020.
[6] I. C. Covert, S. Lundberg, and S.-I. Lee. Explaining by removing: A unified framework for model explanation. The Journal of Machine Learning Research, 22(1):9777,9566 2021.
[7] A. K. Dehnath, R. L.. Lopez de Compadre, G. Debnath, A. J. Shusterman, and Hansch. Structure-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.
[8] A. Duval and F. D. Malliaros. Graphsvx: Shapley value explanations for graph neural networks. In Machine Learning and Knowledge Discovery in Databases. Research Track: European Conference, ECML PKDD 2021, Bilbao, Spain, September 13-17, 2021, Proceedings, Part 21, pages 302-318. Springer, 2021.
[9] Q Feng, N. Liu, F. Yang, R. Tang, M. Du, and X. Hu. Degree: Decomposition based explanation for graph neural networks. In International Conference on Learning Representations, 2022.
[10] M. Fey and J. E. Lenssen. Fast graph representation learning with pytorch geometrie. arXiv preprint vrXiv:1903..00 923,02428, 2019,
[11] T. Funke, Khosla, M. Rathee, and A. Anand. Zorro: Valid, sparse, and stable explanations graph neural networks. IEEE Transactions on Knowledge and Data Engineering, 2022.
[12] Q. Huang, M. Yamada, Y. Tian, D. Singh, and Y. Chang. Graphlime: Local interpretable model explanations for graph neural networks. IEEE Transactions on Knowledge and Data Engineering, 2022.
[13] R. Kleinherg, A. Slivkins, and F. Upfal. Multi-armed handits in metric spaces. In Proceedings of the fortieth annual ACM symposium Theory of computing, pages 681-690, 2008.
[14] I. Kumar, S. Venkatasubramaniin, Scheidegger, and S. Friedler. Problems with shaplcy-value-basee explanations as feature importance measures. In International Conference on Machine Learning, pages 5491-5500. PMLR, 2020.
[15] W. Lin. H. Lan, and B. Li. Generative causal explanations for graph neural networks. In International Conference Machine Learning, pages
PMLR, 2021.
11

---

[16] W. Lin. H. Lan, H. Wang. and B. Li. Orphicx: A causality-inspiie latent variable model for interpreting graph neural networks. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 13738, 2022.
[17] A. Lucic, M. A. Ter Hoeve, G. Tolomei, M. De Rijke, and Silvestri. Cf-gnnexplainer: Counterfactual explanations for graph neural networks. In International Conference on Artificial Intelligence and Statistics, pages 4499-4511, PMLR, 2022.
[18] S. M. Lundberg and S.-L Lee. A unified approach to interpreting model predictions. Advances in Neural Information Processing Systems, 30, 2017.
[19] D. Luo, W. Cheng, D. Xu, W. Yu. B. Zong. H. Chen, and X. Zhang. Parameterized explainer for graph neural network. Advances in Neural Information Processing Systems, 33:19620-1999 2020.
[20] R. Munos et al. From bandits to conte-carlo tree scarch: The optimistic principle applied to optimization and planning. Foundations and Trends in Machine Learning, 7(1):1-129, 2014.
[21] A. Paszke, S. Gross, S. Chintala, G. Chanan, F. Yang. 7. Vetooo Z. Lin, A. Desmaison, I., Antiga, and A. Lerer, Automatic differentiation in pytorch. 2017.
[22] P. E. Pope. S. Kolouri, M. Rostami, C. E. Martin, and H. Hoffmann. Explainability methods for graph convolutional neural networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10772 177211 2019.
[23] B. Rozemberczki, L. Watson, P. Bayer. H.-T. Yang. O. Kiss. S. Nilsson, and R. Sarkar. The shapley value in machine learning. arXiv preprint arXiv:2202.0555 2022.
[24] M. S. Schlichtkrull, N. De Cao, and I. Titov, Interpreting graph neural networks for nip with differentiable edge masking. In International Conference on Learning Representations, 2021.
[25] T. Schnake, O. Fberle, J. Lederer, S. Nakajima, K. T. Schütt, K.-R. Müller, and G. Montavon. Higher-order explanations of graph neural networks via relevant walks. IEEE Transactions on Puttern Analysis and Machine Intelligence, 44(11):7581-75)) 2021.
[26] R. Schwarzenberg, M. Hübner, D. Harbecke, C. Alt, and L. Hennig. Layerwise relevance visualization in convolutional text graph classifiers. EMNLP-IJCNLP 2019, page 58, 2019.
[27] R. R. Selvaraju, M. Cogswell, A. Das, R. Vedantam, D. Parikh, and D. Batra. Grad-cam: Visual explanations from deep networks via gradient- based localization. In Proceedings of the IEEE International Conference Computer Vision, pages 618-626, 2017.
[28] L. S. Shapley al. A value for n-person games. 1953.
[29] R. Socher, A. Perelygin, J. Wu, J. Chuang, C. D. Manning. A. Y. Ng, and C. Polts. Recursive deep models for semantic compositionality over sentiment treebank. Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pages 1631-1642, 2013.
[30] M. Vu and M. T. Thai. Pgm-explainer: Probabilistic graphical model explanations for graph neural networks. Advances in Neural Information Processing Systems, 12255 2020.
[31] X. Wang, Y. Wu, A. Zhang, X. Hc, and T.-S. Chua. Towards multi multi-grained explainability for graph neural networks. Advances in Neural Information Processing Systems, 34: 18446-18888, 2021.
[32] Z. Wang, L. Cao, W. Lin, M. Jiang, and K. C. Tan. Robust graph meta-learning via manifold calibration with proxy subgraphs. In AAAI Conference on Artificial Intelligence, 2023.
[33] Z. Wu, B. Ramsundar, E. N. Feinberg, J. Gomes, C. Geniesse, A. S. Pappu, K. Leswing, and V. Pande. Moleculenet: a benchmark for molecular machine learning. Chemical Science, 9(2):513-533 2018.
[34] Z. Ye, Y. Qu, Z. Liang, M. Wang, and Q. Liu. Explainable fmri-hased brain decoding via spatial temporal- pyramid graph convolutional network. Human Brain Mapping, 44(7):2911-2935, 2023.
[35] Z. Ying, D. Bourgeois, You, M. Zitnik, and Leskovec. Gnnexplainer: Generating explanations for graph neural networks. Advances in Neural Information Processing Systems, 32, 2019.
[36] H. Yuan, J. Tang, X. Hu, and S. 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 438, 2020.
12

---

[37] H. Yuan, H. Yu, S. Gui, and S. Ji. Explainability in graph neural networks: A laxonomic survey. IEEE Transactions Puttern Analysis and Machine Intelligence, 2022.
[38] H. Yuan, H. Yu, J. Wang, K. Li, and S. Ji. On explainability of graph neural networks via subgraph explorations. In International Conference Machine Learning, pages 12241-12252 PMLR, 2021.
[39] H. Zhang, B. Wu, X. Yuan, S. Pan, H. Tong, and J. Pei. Trustworthy graph neural networks: Aspects, methods and trends. arXiv preprint FrXi:2205.00424 2022.
[40] S. Zhang, Y. Liu, N. Shah, and Y. Sun. Gstarx: Explaining graph neural networks with structure-aware cooperative games. In Advances in Neural Information Processing Systems, 2022.
[41] Y. Zhang, D. Defazio, and A. 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.
13

---

Appendix to "SAME: Uncovering GNN Black Box with Structure-wware Shapley-based Multipiece Explanation"
Contents
A Notations
1
B Theoretical Analysis
2
B.1 Definitions of Desire GNN Explanation Technique Propertics
2
B.2 Discussion about Four Fairness Properties
3
B.3 Detailed Proof of Regret Bound
3
B.4 Analysis of Time Complexity
B.4.1 Important Substructure Initialization Phase
B.4.2
Explanation exploration phase
5
C Detailed Pseudo Code of SAME
5
D Dataset Description
5
E Metrics
8
F Detailed Experimental Settings
F.1 Computation Details
8
F.2 Hyperparameter Scttings
8
G Additional Results
G.1 Results under Other Metrics
9
G.2 Additional Visualization Results
9
G.3 Additional Quantitative Analysis
11
This appendix comprises both theoretical and experimental materials and is structured as follows. Section A presents a notation lable that includes all notations used in this paper. Section B provides the full theoretical analysis. Section C presents detailed algorithms related Section 3 in the manuscript. Section D-F show the detailed settings of the experiments in this work. Section G provides additional quantitative and qualitative results.
A Notations
Table S1 contains the notations organized into three sections, each pertaining to different aspects our paper. These include:
Graph: These symbols are related to graph theory, representing elements such graph nodes, edges, and other attributes of graphs.
MCTS: These symbols represent elements related the Monte Carlo Tree Search (MCTS) algorithm, such MCTS nodes, actions, and rewards.
Importance score: These symbols are used to denote values associated with measuring the importance of explanations our explanation algorithm.

---

Table S1: Notations of the graph (sce top part), MCTS (sce middle part) and importance score (sco bottom part).
Notation
Description
g
The graph set to be explained. For any input graph G E g, G G (V, E.)
V = {11, U,....., un) denotes node set,
E E IRux denotes edge set and X E Roxd denotes node feature set.
ges
The set of the explanation candidates for a given graph G. Gez = {G -=r
where Ge S G, m the number of explanation candidates Each Gz is connected component, and is called substructure Each composite Suub contains more than two nodes substructures.
G sub
Goom
G
Each G refers a possible final explanation, i.c., G (Gonb, Djm1s where I the number of substructures in explanation Ge
T.
The number of visit for node in MCTS The reward of node in MCTS
R,
C
The child set of node in MCTS A set of actions MCTS node to reach its children The reward of all children for MCTS node
A
W
M
The node of the corresponding MCTS of the input graph G. Fach node of MCTS where N₂ is structure containing (G) Tú Rí, As, C, W.). The strategy to choose the best child in MCTS.
be denoted as N₂ E N,,
π
P.
A set of players (including all nodes in the input G). A well-trained GNN model.
f()
The importance score, where employ Shapley value here in this paper. The size of set.
B Theoretical Analysis
B.1 Definitions of Desire GNN Explanation Technique Properties
The following content is detailed definition of desired propertics in Table 1 of the main manuscript.
Graph-level tasks: the GNN explanation method can handle the graph classification/regeess regression tasks.
Node-level tasks: the GNN explanation method can handle the node classification iraeccatttoo/rreeesssiiioo regression tasks.
Feature interactions: given a graph to explained, when measuring the importance of the explanation result Gen, the GNN explanation method can consider the influence of (G/Gez) on the importance of Ger-
Structure awareness: given graph be explained, when measuring the importance of the explanation result Gez, the GNN explanation method sensitive to the topology of the given input graph G.
Multipiece explanation: the GNN explanation method can provide the explanation Gez that be composed of one or more connected components.
Node-wise importance: given any node U; G, its importance I(f(-), 0s G) can be considered by the GNN explanation method.
Substructure-wise importance: given any substructure G G, it can be directly calculated whole through the GNN explanation method to obtain its importance I(f(-), G G). Note that any substructure is a connected component, which has more than one node.

---

Composite-wise importance: given any composite Goom C G consisting of more than two nodes or substructures, it can be directly calculated as whole through the GNN explanation method to obtain its importance I(f()), G Goom: G).
Priority-based integration: given an explanation G2 S G with any size, the node vi E (G/Ggz) will be added by the GNN explanation method on G to get a new explanation, if and only for any node Uk (G/G].) except V4 I(f()), {u, Go G) 2 I(f(), UG U. G) always holds.
Redundancy consideration: given an explanation C C G, if there exist node v; E (G/Gkez that satisfies T(((-), / G) T(((), G G), the GNN explanation technique would not. choose G as the final explanation.
11
Brain Networks Associated with Specific Cognitive Task
Functional Groups Associated with Molecular Property
Social Groups Associated with Single Person
Figure S1: Exaiples of the characteristics and properties within graph or node.
As Figure S1 shows, the characteristics and properties within a graph or node tend to be jointly influenced by more than one high-order connected community of the graph. The "multipiece explanation property is aware of such an attribute by considering whether multiple disconnected pieces are allowed appear together in the explanation output. For example, when "A" and "B" are two orthogonal connected components and the ground truth explanation for prediction is "A and B", then the GNN explanation method has probability of providing the correct "A and B" explanation.
We call a GNN explanation method that has the "structure-awarreess property if it can process the structural information of the input graph, whether through explicit mechanisms, as demonstrated by GstarX, or implicit modalities, as exemplified by SubgraphX and this study.
B.2 Discussion about Four Fairness Properties
Efficiency demonstrates that the aggregated importance of individual substructures is equivalent the prediction of GNN on the entire substructure set. Symmelry and Dummy take into account the equal importance of substructures with the same interactions and the substructures that are completely unimportant, respectively. Monolonicity ensures that the explanation method is consistent in the trend of results between different well-trained GNN models given the same dataset.
B.3 Detailed Proof of Regret Bound
The proper definition of the regret phenomenon that the algorithm or the function f encounters must be considered to make the objective clear. Prior studies have recognized two principal definitions: We recall the Lemma 1 in the main manuscript as follows.
Lemma Let d be the v-near-oplimabily dimension (where is desined in Assumplion 3 of the main manuscript), and C is the corresponding constont. Then (Ta] -6(h)-d.
Proof. From Assumption 3 in the main manuscript, each cell (h contains ball of radius vō(h) centered at Th,i Consequently, if |4x| K Xamn)l exceeds C5(h)-d, this would imply the existence of more than C5(h)-d disjoint 1-balls of radius vo(h), each centered within X80)- This assertion would contradict the definition of d.
We recall the Theorem 1 in the main manuscript as follows.

---

" 2 Then the loss of Let write h(n) the smallest integer h such that C Ei=0 (00))=0 algorillm is bounded as In S 8(h(n)).
Theorem 1.
Proof. Consider the tuple (Amaxe,Jmas to be the node with the maximum depth that. the algorithm expands up to the 7th round. Given that the algorithm's expansion limited to nodes within the set I, we can provide that the total number of nodes expanded, denoted by n, adheres to the following condition:
Amaz
K
I {(h,)) has been expanded]
1=
Amax
t=0
Amaz
8(1)
from Lemma 1. Now from the definition of h(n) we have hmax 2 h(n). Finally, since node (Amaxx Imax) has been expanded, we have that (Amax Jmax) I, thus f(x(n)) 2 fThmmee 2 ft 8(hmaxx f* 5(h(n)).
Corollary 1. Assume that 8(h) = oath for some conslants > O and < 1, if if > 0, then the loss decreases polynomially fost:
C On $ (11 1- 1d n-/d 1/2
If = 0, then the loss decreases exponenlially fast:
In S 0//0011
Proof. From Theorem w.weeever d > we have
k(n)
aT d(h(n))1)-1
n MSC 8(1)
Σ 1=0
Cc-
(1)
7 a-
thus -dh(n)) > C - )d), therefore can also have:
C
< 5(h(n)) S M(x)
(2)
Now, if d = 0 then n < CE 8(1) C(h(n) + 1), and we deduce that the loss is bounded as Tn < 5(h(m)) = n/C-1
B.4 Analysis of Time Complexity
Given a graph (V, we take a single iteration as an example to analyze the time complexity of the expansion-based MCTS in proposed SAME. A single iteration includes four steps: selection, expansion, simulation and backpropagation [1].
B.4.1 Important Substructure Initialization Phase
In this phase, the goal of our SAME is to figure out group of important substructures whose size is smaller than 7. In the selection step, our method chooses an unvisited node from the graph or chooses the node with the highest reward if all nodes have been visited (O([V))). Then, in the expansion step, our method selects the node within 1-hop neighbors whose value is largest

---

according to G, which requires ((1), and adds it to the tree. In the simulation step, only the adjacency node will be appended each time. For the graph G, in the worst case SAME will append all the nodes by visiting all the edges in the graph. Thus, the time complexity of simulation is O[VV] + [B]). For the backpropagation step, since the maximum size of substructure is 7 the depth of the MCTS tree will not exceed y. The time complexity of reward backpropagation is bounded by O(7). Since we perform M, iterations, according to the law of multiplication, the time complexity of the first phase is (M,) x ( https///lllaatoooooooooorrrraaaa x((backpropggation) O(M Mr7/V| x [E])
B.4.2 Explanation exploration phase
In the selection step, the MCTS is initialized with unvisited substructure from Important Substructure Set (size K, where K < (VI) chooses the substructure with the highest reward if all substructures have been visited (O(K)). The expansion step is (11) as we only need to append the substruct with the largest value to the current state. In the following simulation step, our method will append other substructures to the current state until the size exceeds the sparsity limit, which is bounded by O(2*) for finding all possible combination. Notice that O(2*) can be very large, we set a maximum simulation time tg as budget which requires O(t.). Since the final explanation is highly related to the sparsity, the cost of backpropagation step is bounded by o V ((1-sparssitg)) )), where y is the maximum size of each substructure. With M2 iterations, the time x (b(aaekrorpgggaiiin
complexity in this phase is (M2) x (selection) (erpaassion) x (
OM, [Vxx([-pparsitl)
?
Overall, time complexity of SAME is O(MrlV]2 V V x | + M2KL, [I ). As the ts y, K, M1, M2 and sparsity is predefined, therefore SAME is polynomial-time method under these constraints.
C Detailed Pseudo Code of SAME
In this section, we are going to provide a detailed overview of the processes of SAME which includes important substructure initialization and explanation exploration.
Algorithm outlines the process of using Monte Carlo Tree Search (MCTS) to find a set of important substructures, as mentioned in Section 3.1 of the main mamuscript. Algorithm and illustrate the method to discover an optimal explanation from these important substructures, as described in Section 3.2. Algorithm 4 provides detailed description of how the importance of an explanation is assessed using the strctuureewware Shapley value, which was proposed in Section 2.1 of your document. This algorithm outlines the steps necessary to approximate the Shapley value for a given explanation, effectively measuring the contribution of each individual component via sampling.
D Dataset Description
We provide details of the datascts used in our experiments, including BBBP [11], MUTAG [2], BA- 2Motifs [8], BA-Shapes [12], Graph-SST2 [7], and Graph-SST3 [7].
Molecular graphs. We use the BBBP [11] containing approximately 2000 molecular graphs, which are classified into two classes over the property of blood-brain barrier penetration (BBBP). Another dataset MUTAG [2] is collection of molecules with -NO, functional groups. The goal is to predict hee these molecules are mutation-induced.
Barabási- Albert graphs. The BA-2Motifs [8] and the BA-Shapes [12] are used for graph classification and node classification respectively. For cach instance in BA-2Motifs, it a Barabási-Albert graph attached by motifs with a structure either house-like or five-node-cydle-like. The instances are labelled according to the type of motifs they get. The graph in BA-Shapes is Barabási-A Abbert graph with house-structured network motifs. The nodes in the graph will be classified into four classes, with labels 0 for the nodes belonging to the original graph and labels 1-3 for the nodes on the middle, bottom, or top of the house-like structures respectively.
Sentiment graphs. The sentiment graphs are built from real-world text sequences, and labelled according to the semantic meanings. Specifically, the nodes in the graph represent the words with an

---

Algorithm 1: Important Substructure Initialization
Input: f(-), well-trained GNN model; G, graph to be explained; Mi, max iteration number of MCTS; Yi, threshold of max single substructure size; child selection strategy Output: .V, all nodes in MCTS
Initialize the root of the MCTS as No
Goub +0 0
N - {No}
for i 1,,,..... Mi do
Neur t No curPath [No]
Goub t- G
while |Ggus < Maz do
9
forall in the {adj(G do Expand N₂ to get N2
10
G rub Geeub U {uş}
1/ Compute the Shapley-based reward according to Algorithm 4
R3 - I(f()), G)
12
13
N NUNU
14
end
15
Select the child Nuezt and its substructure Grent according to the strategy π
16
Near t Nnezt
Gour +- Gneer
18
cur cur Path & PurP + Nnent.
N + (Neur
19
N1 +- Newr // Nt is leaf node 20
end
22
forall node N Npath, in the PurPath do
23
Tpath, +- T path, +
W path,, &- W path, + I(f(-), G sub. G)
24
25
end
end
Algorithm 2: Explanation Exploration
Input: f(),, well-trained GNN model; G, graph to be explained; M,, set of all the nodes in MCTS; K, number of the top most important structures; K₁, threshold to use MCTS;
M2, max iteration number of MCTS; 72, max explanation size; n, child selection strategy.
Output: Gez, the best explanation.
Sort the A in descending order the corresponding reward R. NR t top K substructures N2..,N..., in A
Ger + [(G.ub., R:
// Find explanations through MCTS in Algorithm 3.
G + MCTS(f()), G, M2, Nmaz, n, Nk)
Gar + 1-r
Sort the Ger in descending order of R. /1 Gaz is the explanation the first element in the sorted Gar
Gez (0

---

Algorithm MCTS Explanation Exploration
Input: (()), well-trained GNN model; G, graph to be explained; M2, max iteralion number of MCTS; 72, threshold of max explanation size; child selection strategy, Nk, the substructure set.
Output: Gez: the explanation set lound in MCTS Initialize the root of the MCTS as N
G t 0, Geo + {Gem) for i i= 1........, M2 do
N <- N₁, cur Path <- [No,, Gez + G
while |G < <12 do
6
forall N2 in the (NK\ cur do
1/ Expand Neur with Nj to get Nj:
7
N2 t -N UN;
G Go suby
// Compute reward according to Algorithm
9
R + I(f(+),G G)
end
11
Select the child N and its substructure Gneat according to the strategy
12
Neur &- N Geu &- Gnent
13
PurPath + PurPath + N N
14 end
15
N/ + Ny our // N2 is a leaf node Gex t Gex UfGGeu
16
ez H)
17
forall node Npath; in the cur Path do
T path, TM +
18
path;
W path: &- W
path, + I(f(-), G G)
19
end
end
Algorithm 4: Importance Scoring via Shapley Value
Input: f(-), well-trained GNN model; G, graph data; G explanation of G; T, sampling times; k number of neighboring hop
Output: Z, importance of G for GNN f(-).
Obtain the h-p neighbor nodes of substructure Gi denoted as {Un++1 Un.t2, Un.tk, }.
Then, the players set P Ps,khop = (G Un:41, Unit2..... )n;kk)
for i= 1, 1.2....., do Randomly sample a set S; C (P)G.e))
Obtain f(S, U (Gr,)) and f(S.) by setting the features of the nodes not in the input structure with zero.
11 m(S G denotes the marginalized contribution
6
m(S,, G f(S, US ((S)).
end
1(f()), G G) + LT m(S, G I, I(f() G G. G)

---

initial embedding from the pre-trained BERT [3] and the edges denote the relationships between the words which are extracted by the Biaffine parser [5]. We take experiments on the Graph-SST2 and Graph-SST3 datasets for the sentiment graphs. Note that both Graph-SST2 and Graph-SST5 are the dalasets for graph classification of two classes and five classes respectively.
E
Metrics
The Fidelity, Inverse Fidelity, and Sparsity formally defined
Fidelity(G, Gez) = [f(G)) [f(G/Ge=)]
(3)
Fidelity (G, Gez) = [f(G)] [f(Gez)
(4)
Sparsity(G. Gez) = |Gez
(5)
G|
Harmonic Fidelity (H-Fidelity) takes harmonic mean of normalized fidelity (N-Fidelity) and normalized inverse fidelity (N-Fidelitym..) According to [15], the H-Fidelity can be formally defined
N-Fidelity(G, Gez) m1 Fidelity(G,, Gez) -Sparsity Gea)
(6)
N- N-Fidelityn. Gez) = Fidelity (G, Gez) ) (1 Sparsity(G,
(7)
H-Fidelity(G, G.z) (1 + mi (1 m2)
(8)
(2 + my m2)
F Detailed Experimental Settings
In this section, provide the computational details and detailed hyperparameter settings different. datascts.
F.1 Computation Details
All experiments performed on single Nvidia V100 GPU with Intel Xeon Gold 5218 CPU. Since it takes more than 24 hours for some basclines to explain the whole dataset, our inference time analysis is implemented by randomly sampling from the datasets. For BBBP, BA-2Motifs and BA-Shapes, we use all the test data. And all the data (train, evaluation and test data) is used for MUTAG dataset. For semantic graphs like Graph-SST2 and Graph-SST5, we randomly choose 30 graphs.
F.2 Hyperparameter Settings
We adhere to the hyperparameter scttings for GNN training as described in [13, 15), detailed in Table $2. For the qualitative analysis, the GCN in Figures 4, S2, and S3 aligns with the settings depicted in Table S2. Moreover, the GIN featured in Figure 3 is trained for 800 epochs with batch size of 64 and without adding self-loops, while all other hyperparamcters remain constant to Table S2.
Table S2: Hyperparameters for training the GCN models different datasets. All quantitative results are verified under the following conditions.
Hyperparaneter
BBBP
MUTAG
Graph-SST2
Graph-SST5 BA-2Motifs BA-Shapes
Layers
3
3
3 [20, 20, 20]
Hidden dimensions
[128, 128, 128)
[188, 128, 128
128,, 128, 128]
[128, 128, 128]
[20, 20, 20]
Dropout
0.0
0.0
0.0
0.0
0.0
0.0
Readout method
max
mean
max
max
mean
identity
Learning rate
0.001
0.005
0.001
0.001
0.001
0.05
Batch size
32
32
128
128
64
# Epochs
200
1000
50
800
Weight decay
5 x 10
0
0
0
5 x 10-4
Add self-loop
Yes
Yes
Yes
Yes
Yes
Yes

---

Table S3: The quality of the explanations from SAME with different hyperparameters.
Table S4: The average inference time (scconds) per sample under different hyperparameterss.
AK
3
3
5
9
1
0.2511
0.3319
0.3548
0.3938
0.4026
0.0990
0.3300
1.289
5.178
15.95
2
0.2851
0.3121
0.3418
0.3652
0.3786
0.0889
0.3129
1.137
3.817
11.88
3
0.2938
0.3180
0.3297
0.3637
0.3741
0.0874
0.3986
0.8344
2.746
7.047
4 0.3134
0.3355
0.3491
0.3610
0.3540
0.0932
0.2846
0.8483
2.296
5.330
5
0.3134
0.3387
0.3504
0.3591
0.3598
0.0914
0.2822
0.8427
2.191
5.796
The hyperparameters in SAME include 7 and K we didn't use time budget in our MCTS. In order to see the effect of these two hyperparameters, we our SAME by randomly selecting 30 graphs from Graph-SST5 datasets using GCN, the fidelity w.r.t. y and K are shown in the Table S3, and we report the average inference time in Table S4. Notice that since we only selected 30 graphs from Graph-SST3 to obtain the results, the results provided in Table S3 might be slightly different from the results given in the main manuscript.
It is noteworthy that y=1 could lead to optimal fidelity in most benchmarks. However, when y is small, the final explanation may be composed of disconnected nodes at different positions in the graph, which usually causes the visualization of explanation results not lumman-undesstnddabl Therefore, we fine-tuned and K according to the visualization of explanation results so that the provided explanations are more numann-ntuuting For the inference time, a larger K leads to a larger search space for the explanation exploration phase. When y is small, the size a single candidate substrucluure small, indicating that we need to select more substructures from the candidates to obtain an explanation with the desired sparsity. Thus, the inference time increases as the depth of scarching grows. The detailed hyperparamcter settings provided in Table $5. For the sentiment network Twitter [13] and molecular network BACE [11], use them to compare SAME with more SOTA explainers in Section G.3
Table S5: The hyperparameters of SAME for different datascts.
Hyperparameter
BBBP MUTAG Graph-SST2 Graph-SST5 BA-2Motifs BA-Shapes Twitter BACE
Y
3
3
K
7
7
G Additional Results
G.1 Results under Other Metrics
Here, we present the results over inverse fidelity and harmonic fidelity under the same experimental settings in Table $2. Table S6 demonstrates that SAME is competitive over the 5/6 datasets. Table S7 reports the harmonic fidelity quantities. SAME outperforms the basclines in all the graph tasks.
G.2 Additional Visnalization Results
We are presenting additional visualization results for BBBP and Graph-SST2 datascts. Figure S2 presents explanations for the BBBP dataset. SAME identifies critical functional groups (for instance, carbonyl group =C=O), which result in a high fidelity score. Figure S3 provides a visualization for the negative label of the Graph-SST2 dataset. In this case, SAME uniquely identifics the word "only," " which contributes to the negative prediction of the GNN due the contrasting relationship establishes.

---

Table S6: Comparison of our SAME and other baseline explainers using
Inverse Fidelity.
Dataset
Graph lasks
Node tasks
Molecular graph
Semantic graph
Synthelic graph
Methods
BBBP
MUTAG
Graph-SST2
Graph-SST5
BA-2Motifs
BA-Shapes
Grad-CAM [9]
0.897+0.029
0.901+0.048
1.006:+0.029
0.937=00.047
0.587+0.009
GNNExplainer [12]
0.829+0.012
0.810++.000
0.855+0.037
0.860=000034
0.562+0.015
0.953=0.032
PGExplainer [8]
0.338+0.036
0.793++0000
0.956++0.036
0.850+00.088
0.582+0.021
0.902=0.008
GNN-LRP [10]
0.670=0.044
0.768=1.001 013
0.784=0.047
0.771=0.041
0.560+0.015
0.988=0.010
SubgraphX [14]
1.010=0.011
L.053=0.011
1.008:10.000
1.022:+0.00
0.906:10.122
0.978=0.034
GStarX [15]
0.939:1.001
1.124
1.002:10.003
1.140=10.031
0.587:10.117
SAME
0.993#0.014
1.095=0.008
1.039=00001 1.058+0.010
0.857+00004
0.881=0.000
Note: The previous SOTA results on different datasets are marked with an underline. Relative Improve denotes
the relative improvement of our SAME method the SOTA methods.
Table S7: Comparison of our SAME and other baseline explainers using Harmonic Fidelity.
Dataset
Graph tasks
Node tasks
Molecular graph
Semantic graph
Synthetic graph
Methods
BBBP
MUTAG
Graph-SS12
Graph-SST5
BA-2Motifs
BA-Shapes
Grad-CAM [9]
0.520++..00
0.527+00002
0.538++0.005
0.529++0.003
0.502++0.014
GNNExplainer [12]
0.504
0.505=0.007
0.507+0.001
0.512:0.001
0.487=1.027
0.51410.001
PGExplainer [8]
0.511#0.000 002
0.500=0.006
0.528:10.00
0.516+0.000
0.493=0.022 0.003
0,504+0.003
GNN-LRP [10]
0.488.10.000
0.50110.003
0.495110.001
0.495-10.002
0.497-10.027
0.518:10.002
SubgraphX [14]
0.560 002
0.55210.002
0.52811.000
0.54110.000
0.548110.00
0.528.10.003
GStarX [15]
0.510++0.002
0.599=0.011
0.533+00.005
0.542+0.005
0.506+0.001
SAME
0.57110.001
0.60410.022
0.540110.021
0.56610.000
0.55410.007
0.51710.000
Relative Improve
1.96%f
0.83%t
1.31%
4.43%f
1.09%1
Note: The previous SOTA results on different datasets are marked with an underline. Helative Improve denotes the relative improvement of our SAME method over the SOTA methods.
Grad-CAM
GNNExplainer
PGExplainer
Fidiity
Fidelity
Fidelity:
GNN-LRP
SubgraphX
GStarX
SAME(ours)
Fidelay;
Fidelit:
Fideliy: 0.31
Fideliy: 0.99
Figure S2: Comparison of the explanations BBBP with GCN classifier.

---

Sentence: "shocking only in that it reveals the filmmaker's bottomless pit of self absorption."
Grad-CAM
GNNExplainer
PGExplainer
that shocking
in
that
shocking
that
shocking
in
it reveals only
reveals
only
it
reveals only
the
pit bottom.
the
bottom, the
pit bottorn
filmma of
absorp. filmma of
absorp. filmma. of
absorp.
% self
SubgraphX self
self
GNN-LRP that shocking that shocking in that shocking that shocking it reveals only reveals only it reveals only
GStarX
SAME(ours)
reveals
the
bottom.
the
pit bottom. the
bottom. the pit
bottom.
filmma.
of
ahsorp.
filmma. of absorp.
filmma. of
absorp.
filmma.
of
absorp.
5
self
self
self
3s self
Figure $3: Comparison of the explanations on Graph-SST2 with GCN classifier for negative prediction.
G.3 Additional Quantitative Analysis
Here we report more quantitative analysis with alternative SOTA methods and datasets. We tested SAME on GAT and GIN, and compared SAME with other SOTA algorithms (GraphSVX [4] and OrphieX [6]- In table S8, We report the averaged fidelity over a sparsity of [0.5, 0.6, 0.8). For the inference time plus fidelity, they are summarized Table S9. SAME not only surpasses the benchmarks' performance by alternative GNN architectures, but also exhibits superior efficiency in elucidating explanations.
Table S8: Comparison of SAME and other baseline explainers with different GNN architccture.
Dataset
GAT
GIN
GCN
Methods
Graph-SST SST2
Graph- 5ST5
Graph-SSee -S22
Graph-SST5 SSST
Twitter
BACE
GraphSVX [4]
-0.0136
-0.0108
0.0839
0.161
0.0691
0.2061
OrphicX [6]
0.071
0.104
0.258
0.176
0.1701
0.3277
SubgraphX [14]
0.060
0.060
0.222
0.254
0.2903
0.3906
GStarX [15]
0.134
0.114
0.274
0.263
0.2501
0.3903
SAME
0.142
0.222
0.400
0.264
0.3127
0.7154
Note: The previous SOTA results on different datasets are marked with an underline.
Table S9:
Comparison of SAME and other benchmarks in both fidelity and inference time (per sample). The architecture of our model GCN.
Methods
GraphSVX
OrphicX [6]
SubgraphX [14] GStarX [15]
SAME
Metric
Twitter BACE
0.0691
0.1701
0.2903
0.2501
0.3127
Fidelity
0.2061
0.3277
0.3906
0.3903
0.7154
Twitter BACE
0.0885 0.0915
0.1942
197.1
36.26 48.81
25.85
Time
0.2361
44.11
26.98
Note: The previous SOTA results on different datasets are marked with an underline.

---

References
[1] C. B. Browne, E. Powley, D. Whitehouse, S. M. Lucas, P. I. Cowling, P. Rohlfshagen, S. Tavener, D. Perez, S. Samothrakis, and S. Colton. A survey of monte carlo tree search methods. IEEE Transactions on Compulational Intelligence and Al in Games, 4(1):1 43, 2012.
[2] A. K. Debnath, R. L. Lopez de Compadre, G. Debnath, A. Shusterman, and C. Hansch. Structure- activity relationship of mutagenic aromalic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity. Journal of Medicinal Chemistry, 34(2):786-797, 1991.
[3] J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova. Bert: Pro-training of deep bidirectional transformers for language understanding. ArXiv, abs/ Abs/1180.04805, 2019.
[4] A. Duval and F. Malliaros. Graphsvx: Shapley value explanations for graph neural networks. Machine Learning and Knowledge Discovery in Databoses. Research Track: European Conference, ECML PKDD 2021, Bilbao, Spain, September 13- 17, 2021, Proceedings, Part II 21, pages 318. Springer, 2021.
[5] M. Gardner, J. Grus, M. Neumann, O. Tafford, P. Dasigi, N. Liu, M. Peters, M. Schmitz, and L. Zettlemoyer. Allennlp: A deep semantic natural language processing platform. 2018.
[6] W. Lin, H. Lan, H. Wang, and B. Li. Orphicx: A cuusality-inspired latent variable model for interpreting graph neural networks. In Proceedings of the IEEE/C CCF Conference on Computer Vision and Pattern Recognition, pages 13729 13738, 2022.
[7] M. Liu, Y. Luo, L. Wang, Y. Xie, H. Yuan, S. Gui, H. Yu, Z. Xu, J. Zhang, Y. Liu, el al. Dig: A turnkey library for diving into graph deep learning research. The Journal of Machine Learning Research, (11):108833
2021.
[8] D. Luo, W. Cheng, D. Xu, W. Yu, B. Zong, H. Chen, and X. Zhang. Parameterizod explainer for graph neural network. Advances in Neural Information Processing Systems, 33:19620 19631, 2020.
[9] P. E. Pope, S. Kolouri, M. Rostami, C. E. Martin, and H. Hoffmann. Explainability methods for graph convolutional neural networks. In Proceedings of the IEEE/CVE Conference on Compuler Vision and Pottern Recognition, pages 10772-10781, 2019.
[10] T. Schnake, O. Eberle, J. Lederer, S. Nakajima, K. T. Schütt, K.-R. Müller, and G. Montavon. Higher-order explanations of graph neural networks via relevant walks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(11):7581 7596, 2021.
[11] Z. Wu, B. Ramsundar, E. N. Feinberg, J. Gomes, C. Geniesse, A. S. Pappu, K. Leswing, and V. Pande. Moleculenet: a benchmark for molecular machine learning. Chemical Science, 9(2):513- 530, 2018.
[12] Z. Ying, D. Bourgeois, J. You, M. Zitnik, and J. Leskovec. Gnnexplainer: Generating explanations for graph neural networks. Advances in Neural Information Processing Systems, 32, 2019.
[33 H. Yuan, H. Yu, S. Gui, and S. Ji. Explainabilitty in graph neural networks: A taxonomic survey. IEEE Transactions Pattern Analysis and Machine Intelligence, 2022.
[14] H. Yuan, H. Yu, J. Wang, K. Li, and S. Ji. On explainability of graph neural networks via subgraph explorations. In International Conference on Machine Learning, pages 12241-12252. PMLR, 2021.
[15] S. Zhang, Y. Liu, N. Shah, and Y. Sun. Gstarx: Explaining graph neural networks with structure- aware cooperative games. In Advonces in Neural Information Processing Systems, 2022.


Reviews:
[{"review_id": "YASBK4ocBQ", "reviewer": "Reviewer_qWxr", "summary": "The paper proposes a novel method for explaining GNNs called SAME. SAME addresses the challenges of structure-aware feature interactions in GNN explanation by using an expansion-based Monte Carlo tree search. The authors evaluate SAME on a variety of benchmarks and show that it outperforms previous state-of-the-art methods. The paper makes contributions to the field of GNN explanation.", "questions": "How scalable is SAME? Shapley-based explainability methods are generally more expensive than gradient-based methods.", "limitations": "Yes.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- SAME addresses the challenges of structure-aware feature interactions in GNN explanation by using an expansion-based Monte Carlo tree search, which is novel\n- The authors evaluate SAME on a variety of benchmarks, and the experiments show that SAME outperforms previous state-of-the-art methods on these benchmarks.\n- The theoretical aspects of SAME are well-developed and provide a good foundation for the proposed method.\n", "weaknesses": "- The authors could provide more information on the limitations of SAME, particularly in terms of the types of graphs and datasets for which it may not perform as well.\n- The authors could provide more insight into the computational complexity of SAME and how it scales to larger graphs and datasets.\n- The technical content is not sufficient, for example, it does not fully use the 9-page limit.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and thorough comments! Below please find our point-to-point responses to your comments.\n\n**Q1. More insight into the computational complexity of SAME and how it scales to larger graphs and datasets.**\n\nFor providing insight into the computational complexity and scalability of SAME, we refine the computational complexity. Please kindly see the relevant answer to this question in *Overall response: Q1*.\n\n**Q2. More information on the limitations of SAME, particularly in terms of the types of graphs and datasets for which it may not perform as well.**\n\nPlease kindly find the related answer to this question in *Overall response: Q2*.\n\n**Q3. How scalable is SAME? Shapley-based explainability methods are generally more expensive than gradient-based methods.**\n\nAs we discussed in our answer to *Overall response: Q2*, our method may take a long time to get an explanation on large graphs, which may be more expensive in time than gradient-based methods. \n\nHowever, would like to point out that the proposed SAME has obtained the SOTA explanation results (see Table 2 in the main manuscript: fidelity = 0.214±0.000) on the current explanation benchmark with the largest graph size (see Table below: BA-Shapes with size = 700) in a relatively short period of time (see Table 3 in the main manuscript: inference time = 14.08s). This indicates that our method has the possibility to work well on larger graphs.\n\nTable. The min / max graph size in different datasets.\n| Datasets | BA-2Motifs | BBBP | Graph-SST2 | Graph-SST5 | BA-Shapes | MUTAG | Twitter | BACE |\n   | :--------: | :----------: | :----: | :----------: | :----------: | :---------: | :-----: | :-------: | :----: |\n   | **Min**  | 25         | 2    | 1          | 2          | 700       | 10    | 3       | 10   |\n   | **Max**  | 25         | 132  | 56         | 56         | 700       | 28    | 73      | 97   |"}, {"review_id": "plvkRw4G42", "reviewer": "Reviewer_8xQs", "summary": "The paper introduces SAME, a novel method for post-hoc explanation of Graph Neural Networks (GNNs). SAME leverages an expansion-based Monte Carlo tree search to explore structure-aware connected substructures and provides explanations that are as explainable as the theoretically optimal Shapley value. Experimental results show that SAME outperforms previous state-of-the-art methods, improving fidelity performance by 7.01% to 42.3% across various benchmarks. The SAME method contributes to the field of GNN explanation by offering theoretical foundations and improved performance. ", "questions": "- Theoretical Analysis: Could you provide more details about the theoretical foundation of the SAME method? Specifically, how does the expansion-based Monte Carlo tree search contribute to the structure-aware explanations, and how does SAME ensure the explanations are as explainable as the theoretically optimal Shapley value?\n\n- Comparative Analysis: In the paper, SAME is shown to outperform previous state-of-the-art methods in terms of fidelity performance. However, could you provide a more thorough comparison with alternative explanation techniques? How does SAME compare to other state-of-the-art methods in terms of interpretability, computational efficiency, and generalizability?\n\n- Limitations and Future Directions: While the results are promising, it would be helpful to have a more comprehensive discussion on the limitations of the SAME method. What are some potential drawbacks or challenges associated with SAME? Additionally, what future research directions do you envision to address these limitations and further improve the method?\n\n- Applicability to Different GNN Architectures: The paper focuses on explaining Graph Neural Networks (GNNs). Could you provide insights into the generalizability of SAME to different GNN architectures? Are there any specific considerations or adaptations required for applying SAME to other GNN models, such as graph attention networks or graph convolutional networks?\n\n- Theoretical Complexity and Scalability: The paper claims that SAME provides explanations within polynomial time. Could you provide more details on the computational complexity of the SAME method? How does the method scale with increasing graph size or complexity? Are there any limitations or considerations regarding the scalability of SAME to larger graphs?\n\n- Insights on Parameters and Hyperparameters: The paper mentions the use of Monte Carlo tree search and distinct single substructures in the SAME method. Could you elaborate on how the parameters and hyperparameters of these components affect the quality of the explanations? Are there any guidelines or insights you can provide to help researchers fine-tune these parameters effectively?", "limitations": "- Limited Discussion on Practical Applicability: The paper primarily focuses on the fidelity performance of the SAME method without discussing its practical applicability or real-world constraints. It would be beneficial to address any potential limitations or challenges in applying SAME to real-world scenarios, such as scalability, interpretability, or sensitivity to noise or perturbations in the input graph.\n\n- Lack of User Evaluation: The paper does not include user studies or evaluations to assess the usefulness or understandability of the explanations generated by SAME. Incorporating user feedback or conducting user studies would provide insights into the effectiveness of SAME from a human-centered perspective.\n\n- Absence of Ablation Studies: The paper does not include ablation studies to analyze the contribution of individual components or design choices in the SAME method. Conducting such studies would help isolate and evaluate the impact of different aspects of the method on the overall performance.\n\n- Limited Dataset Coverage: The paper evaluates SAME on a specific set of benchmarks, both real-world and synthetic. However, it would be valuable to assess its performance on a more diverse range of datasets, including those with different graph sizes, properties, and domains.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Theoretical foundation: The paper introduces the SAME method, which provides a theoretical foundation for post-hoc explanation techniques for Graph Neural Networks (GNNs). This adds credibility and rigor to the proposed approach. \n\n- Structure-aware explanations: SAME addresses the challenge of structure-aware feature interactions in GNN explanations. By leveraging an expansion-based Monte Carlo tree search, SAME explores multi-grained connected substructures, resulting in more informative explanations. \n\n- Improved performance: Experimental results demonstrate that SAME outperforms previous state-of-the-art methods in fidelity performance across various benchmarks. The improvements range from 7.01% to 42.3%, indicating the effectiveness of the proposed method. ", "weaknesses": "- Limited discussion of limitations: The paper lacks a comprehensive discussion of the limitations or potential drawbacks of the SAME method. Addressing the potential shortcomings would strengthen the paper and guide future research directions.\n\n- Limited comparison with alternative methods: While SAME is shown to outperform previous state-of-the-art methods, the paper does not provide a thorough comparison with alternative approaches. Including such a comparison would enhance the understanding of how SAME stands against other techniques.\n\n- Generalizability to different GNN architectures: The paper does not explicitly discuss the generalizability of the SAME method to different GNN architectures. Considering and discussing the potential challenges or adaptations needed for different architectures would enhance the applicability of the proposed method.\n\n- Theoretical complexity and computational efficiency: Although SAME claims to provide explanations within polynomial time, the paper does not provide a detailed analysis of the theoretical complexity or computational efficiency. Further investigation into the computational aspects would be valuable for understanding the scalability of the method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your careful review and comments. Below please find our point-to-point responses to your comments.\n\n**Q1. The theoretical foundation of SAME. How does the MCTS contribute to the Structure-awareness, and how does SAME ensure the theoretically Optimal?**\n\n1. To our best knowledge, no existing work has considered or formalised the theoretically optimal value of MCTS. The core of our theoretical work is to establish a framework for MCTS-based GNN explanation techniques. Under this framework, we define an error bound that can be widely applied to different MCTS-based methods. We show that our method has lower error bounds than another MCTS-based GNN explanation technique (SubgraphX). In order to explain our theoretical work more clearly, we adjusted the content of Section 2. Please see *Overall response: Q5* for detailed a explanation. Therefore, although in section 2.2, we did not consider enough theoretical foundation in the design part of the algorithm, we realized the \"nature closer to the optimal solution\" reflected in the comparison between expansion-based algorithms and pruning-based algorithms.\n\n2. Because we use the **k-hop Shapley value** in the expansion-based MCTS, the interaction between interpretation and neighbor nodes will be considered in the calculation process, so as to achieve structural awareness.\n\n3. In our theoretical work, we define an error bound that can be applied to different MCTS-based methods. We show that SAME has lower error bounds than another MCTS-based GNN explanation technique (SubgraphX). Here we adjusted the content of Section 2. Please see *Overall response: Q5* for detailed a explanation.\n\n**Q2. More thorough comparison in terms of interpretability, computational efficiency, and generalizability?**\n\n1. For **interpretability** and **computational efficiency** of our approach. We compared our method with competitive techniques (see Table 2, 3 in the main manuscript, Table S3, S4 in the Supplementary Material).\n\n   We add new experiments on Twitter and BACE with additional results on GraphSVX and OrphicX (*Overall response: Q4*).\n\n2. For **generalizability** of our approach, we further validate SAME on Graph-SST2 & Graph-SST5 using GIN and GAT (*Overall response: Q3*). In short, SAME does not need further adaptation on different GNN architectures since it is a post-hoc model-agnostic technique. \n\n**Q3. A detailed analysis of the computational efficiency.**\n\nWe refine the computational complexity. Please kindly see the relevant answer in *Overall response: Q1*.\n\n**Q4. Limited discussion of limitations of SAME.**\n\nPlease kindly find the related answer in *Overall response: Q2*.\n\n**Q5. Generalizability of SAME? Specific adaptations for GNN like GAT or GCN?**\n\nAs the SAME is a post-hoc model-agnostic technique, our approach does not need further adaptation or modification for application to different GNN models. For the **generalizability** of our approach, please kindly refer to *Overall response: Q3*.\n\n**Q6. How the parameters and hyperparameters affect the quality of the explanations? Are there any guidelines or insights?**\n\nThe hyperparameters include $\\gamma$ and $K$. We randomly select 30 graphs from Graph-SST5 datasets using GCN, and report the fidelity w.r.t. $\\gamma$ and $K$ in the following table. \n\n| $\\gamma$    \\    $K$ |    1    |    3    |    5    |    7    |    9    |\n| :------------------: | :-----: | :-----: | :-----: | :-----: | :-----: |\n|          1           | 0.25114 | 0.33188 | 0.35484 | 0.39379 | 0.40260 |\n|          2           | 0.28510 | 0.31207 | 0.34179 | 0.36521 | 0.37856 |\n|          3           | 0.29380 | 0.31802 | 0.32966 | 0.36365 | 0.37412 |\n|          4           | 0.31396 | 0.33553 | 0.34911 | 0.36104 | 0.35396 |\n|          5           | 0.31396 | 0.33869 | 0.35042 | 0.35909 | 0.35917 |\n\nAlthough $\\gamma$=1 could lead to an optimal fidelity, the explanation may be composed of disconnected nodes, making the it not human-understandable. Therefore, we fine-tuned $\\gamma$ and $K$ according to the visualization results. The detailed settings are provided in the Table below.\n\n|   Datasets   | BA-2Motifs | BBBP | Graph-SST2 | Graph-SST5 | BA-Shapes | MUTAG | Twitter | BACE |\n| :----------: | :--------: | :--: | :--------: | :--------: | :-------: | :---: | :-----: | :--: |\n| **$\\gamma$** |     3      |  5   |     3      |     3      |     5     |   2   |    3    |  2   |\n|   **$K$**    |     7      |  7   |     7      |     7      |     7     |   7   |    7    |  7   |\n\n**Q7. Limitations in applying SAME to real-world scenarios, such as scalability, interpretability, or sensitivity to noise or perturbations in the input graph.**\n\nThank you for your careful review and suggestions. We answer your questions point-to-point below.\n\n1. We supplement the discussion about **scalability** of our method, please find the related content in *Overall response: Q2*.\n\n2. In terms of the limited discussion about **interpretability**, we beg to differ in that the explanatory benchmark includes synthetic, sentiment and molecular datasets (in Table 2). We also considered different two kinds of fidelity as our metric (in Table S3, S4).\n\n   Note that for some data the explanation with the maximum fidelity cannot match the ground truth. Therefore, when applying to a real-world dataset, it is necessary to use different metrics with actual needs.\n\n3. Considering the **sensitivity to noise or perturbations in the input graph** is not generally an issue for the post-hoc graph explanation technique. Because if a graph explanation technique is robust to noise, it may overestimate or underestimate the well-trained GNN that needs to be explained. \n\nDue to the character limit of the response, for other limitations, please find the corresponding responses in the following comments."}, {"review_id": "8RKgSsWM81", "reviewer": "Reviewer_dDYx", "summary": "The paper introduces a novel method for explaining GNNs called SAME. SAME is theoretically grounded and has some good properties over exisiting methods. SAME uses an expansion-based Monte Carlo tree search algorithm to approximate the optimal Shapley-based explanation, which is proven to be better than pruning-based methods like SubgraphX. SAME has two MCTS stages, first on nodes and then on connected component combinations. SAME is evaluated on six datasets from different sources with diverse categories, including molecular graphs, sentiment graphs, and synthetic BA graphs. The experiments show that SAME outperforms previous state-of-the-art methods and has reasonable inference time.", "questions": "My questions are very related to the weaknesses I mentioned above.\n\n1. Why is it intuitive to conclude the expansion-based method is better than the pruning-based method? Can the authors explain more?\n\n2. If I misunderstood the properties in Table 1 in my weaknesses comment, please point it out.\n\n3. I have some doubts about the time complexity analysis. Can the authors be more detailed about why it is O((M1 + M2)n^2)? Also, other methods, like SubgraphX, do not necessarily have time complexity O(2^n), as SubgraphX considers k-hop neighbors, uses MC approximation, and has a budget for the subgraph size.", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 1, "presentation": 2, "contribution": 2, "strengths": "1. A theoretical assessment of the expansion-based vs. pruning-based explanation methods is great.\n2. The two-stage MCTS approach involving nodes and then components is novel to me and intuitively makes sense.\n3. The proposed SAME framework has good empirical performance.", "weaknesses": "1. The level of detail for different parts of the paper can be adjusted\n\nOne suggestion I have is to shrink section 2.1 by moving some content to the Appendix. Although being clear about what Shapley value is and what the good properties of Shapley value have is important, most of the target readers should be comfortable reading the paper without mentioning all the details explicitly in the main text. For example, properties 1 - 4 should easily follow as long as the set of players P_i is clearly defined. Also, \"k-hop Shapley\" is another fancy term for saying only nodes in the computation graph should be considered. This idea was introduced in SubgraphX, and the idea of computation graph was brought up even earlier in GNNExplainer. All of these being said, the core idea of Section 2.1 can be quickly made clear by defining the set of players and the computation graph as k-hop neighbors. However, a whole page listing out all four properties and formulas (2) and (3) can make the paper seem redundant and suspicious, as these are not original contributions of the paper.\n\nI would suggest spending more space discussing other important things. For example, at the end of Section 2, the authors mentioned that \"It is intuitive to conclude ....\". This kind of discussion can be made more detailed when there is more space.\n\n\n2. Required properties of explanation methods can be made more clear\n\nSeveral properties of GNN explanation methods are introduced in Table 1, and the major role of sections 2 and 3 is to show SAME is better than other methods in terms of these properties. However, I think some of these properties are not well-defined or not reasonably named, making them not the best ways to measure explanation methods.\n\na. Structure awareness. The authors claim that 4 methods satisfy this property and 3 do not. However, Section 2.1 discusses that the way SubgraphX and SAME satisfy the structure awareness is through the \"k-hop Shapley\" idea. I would not say \"k-hop\" is structure independent, but it only trivially uses the structure to construct the computation graph. The structure awareness refers to a different concept from the existing structure-aware idea proposed by GStarX, as the computation of HN naturally involves the structure. Thus, the property here can be misleading.\n\nb. Multiple explanations. By multiple explanations, the authors seem to mean whether multiple disconnected pieces are allowed to appear together in the explanation output. However, the name here only makes sense when these pieces have a \"or\" relationship instead of an \"and\" relationship. For example, when the ground truth explanation for a prediction is \"A and B\". It is not proper to say there are multiple explanations, one being \"A\" and the other being \"B\", because neither of them is a complete explanation. Also, this multiple-explanation idea seems more like a limitation of the SubgraphX method instead of a property in general. SubgraphX assumed connectedness so there will only be one piece, which can be a good assumption instead of a limitation in some cases, but other methods do not make this assumption. In general, I do not think it is a good idea to take an assumption only one method makes and claiming not having it is a required property. \n\nc. Node-wise/Substructure-wise/global importance. I don't feel this categorization makes full sense. If we just look at the definition, global importance implies substructure-wise importance, which further implies node-wise importance. This is because one explanation can be one connected component, which can be one node. How could one method have the global importance property but not the other two? Like GNNExplainer and PGExplainer in Table 1. Also, I believe that if any of these three importance properties is strictly satisfied, the computational complexity will be exponential. How could SAME satisfy them and be a polynomial algorithm?\n\nI hope the authors can better organize these properties so that they 1. do not have conflicts with existing concepts 2. are properly named 3. are more clearly defined and categorized.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your careful review and comments. Below please find our point-to-point responses to your comments.\n\n**Q1. The level of detail for different parts of the paper can be adjusted.**\n\nThank you for your excellent suggestions. We agree that we should adjust the detail for Section 2. We have shorter the description of Section 2.1 and provided more details about Section 2.2 following your advice. Please kindly find the revised version in *Overall response: Q5*.\n\n**Q2. Required properties of explanation methods can be made more clear.**\n\nThank you for giving this thoughtful suggestion. The detailed definitions of the property in Table 1 are as follows.\n\n1. Graph-level tasks: the GNN explanation method can handle the graph classification/regression tasks.\n\n2. Node-level tasks: the GNN explanation method can handle the node classification/regression tasks.\n\n3. Feature interactions: given a graph $G$, when measuring the importance of the explanation result $G_{ex}$, the GNN explanation method can consider the influence of {G/G_{ex}} on the importance of $G_{ex}$.\n\n4. Structure awareness: given a graph $G$, when measuring the importance of explaining the result $G_{ex}$, the GNN explanation method is sensitive to the topology of the given input graph $G$.\n\n5. Multiple explanations: the GNN explanation method can provide the explanation $G_{ex}$ that can be composed of one or more connected components.\n\n6. Node-wise importance: given an input graph $G$ to be explained, for any node $v_i\\in G$, its $I(f(\\cdot),v_i,G)$ importance will be considered by the GNN explanation method.\n\n7. Substructure-wise importance: given an input graph $G$ to be explained, for any substructure $G_{sub_i}\\subseteq G$, its importance $I(f(\\cdot),G_{sub_i},G)$ will be considered by the GNN explanation method.\n\n8. Global importance: given an explanation $G_{ex}^i\\subseteq G$ consisting of one or more substructures, its importance $I(f(\\cdot),G_{ex}^i,G)$ will be considered by the GNN explanation method.\n\n9. Priority-based integration: given an explanation $G_{ex}^j$ with any size, the node $v_i\\in\\{G\\backslash G_{ex}^j\\}$ will be added by the GNN explanation method on $G_{ex}^j$ to get a new explanation $G_{ex}^k$, if and only if for any $v_l \\in \\{G\\backslash (G_{ex}^j\\cup v_i)\\}$, $I(f(\\cdot),G_{ex}^j\\cup v_i,G) > I(f(\\cdot),G_{ex}^j\\cup v_l,G)$ holds.\n\n10. Redundancy consideration: given an explanation $G_{ex}\\subseteq G$, if $I(f(\\cdot), G_{ex}\\backslash \\{i\\}, G)$ $>$ $I(f(\\cdot), G_{ex}, G)$ holds, the new explanation $G_{ex}'=G_{ex}\\backslash \\{i\\}$ will be chosen by the GNN explanation method.\n\nWe agree that the **structure-awareness** mentioned by the reviewer is inconsistent between the ‘k-hop Shapley’ used in our work and HN-value mentioned by GstarX. The structure-awareness defined in our work is a macro definition. If the GNN explanation method can explicitly (e.g. GstarX) or implicitly (e.g. SubgraphX and ours) process structural information of the input graph, we call it has structure-awareness property.\n\nYour understanding of the **multiple explanations** is correct. We also think that subgraphX's method of finding connected substructures is a good assumption, which can make explanation results more in line with human intuition. Indeed, in the first phase of SAME, we also consider the connectivity of substructures when initializing important substructures set with expansion-based MCTS. However, it needs to be admitted that SubgraphX cannot find the explanation that the ground truth contains multiple substructures at the same time, which is one of their limitations. The lack of ability to find explanations where the ground truth contains multiple substructures will limit the usability of the method in many scenarios. Thus, we listed the *multiple explanations* in the property comparison table. \n\nFor the **necessity of distinguishing between Node-wise / Substructure-wise / Global importance**, it is possible for one method to have the global importance property but not the other two. For example in GNNExplainer and PGExplainer, they obtain the explanation by learning a mask for the given graph. Therefore, the explanation results from them only consider the global importance but not substructure-wise importance or node-wise importance. It is also possible for one method to have the node-wise importance property but not the other two. For example, in GstarX, the importance of any substructure is simply the sum of the importance of the node without taking them as a whole to derive the importance. Therefore, it is necessary to distinguish among them.\n\nWe admit that if one method is strictly satisfied any of the above three importance properties, it will lead to an NP-hard problem.  SAME, like other SOTA methods, uses an approximating algorithm to measure the Shapley value and explore the possible global optimal solution with the help of MCTS. \n\nNote that our approach is based on MCTS, but with a novel two-phase expansion-based MCTS version, which is shown to outperform the subgraphX, and outperform or be competitive with other SOTA methods (see Table 2, 3 in the main manuscript; Table S3, S4 in the supplementary material; *Overall response: Q4* for additional experiments for detailed results).\n\n**Q3. More details about time complexity of SAME. And, other methods, like SubgraphX.**\n\nWe refine the computational complexity. Please kindly see the relevant answer to this question in *Overall response: Q1*. As SubgraphX is a pruning-based method, it requires more time in the simulation step, especially when the given graph is very large and the explanation is small. \n\nAs Table 2 and Table 3 in the main manuscript, Table S3 and Table S4 in the supplementary material and additional experiments in *Overall response: Q4* show, our SAME significantly outperform SubgraphX in terms of different explainability metric with shorter inference time on different benchmarks."}, {"review_id": "ozWWPbxDPL", "reviewer": "Reviewer_xcjE", "summary": "A GNN-based Shapley value for GNN explanation is proposed, which is a novel Structure-Aware Shapley-based Multi-Explanation (SAME) technique for fairly considering the multi-level structure-aware feature interactions over an input graph It is computed by an expansion-based Monte Carlo tree search (MCTS) and its main advantage over existing methods is its theoretical foundation.\nExperiments on multiple datasets also highlight practical benefits.\n", "questions": "For what kind of GNNs does the proposed explainer work? Could attention be considered?\n", "limitations": "The limitations have been pointed out under weaknesses and were mostly discussed by the authors. I do not foresee a negative societal impact of this work.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "- **Clarity:**\nTable 1 clearly points out the differences/additional features in comparison to related methods. The figures have been designed with care and are visually appealing. In particular, the appendix contains some beautiful figures. However, some arguments could be made more clear (see weaknesses). Some larger parts of the paper are not well understandable because information is missing (for details see points of minor critique).\n\n- **Originality:**\nTable 1 explains the novelty of SAME relative to competing methods. While all of the listed features are realised by some methods, SAME is able to offer their combination.\nThe authors claim that another distinguishing feature is a theoretical foundation. (However, other Shapley based measures are also benefit from a well established related theory.)\nThe proposed method SAME is quite similar to SubgraphX. Primarily, the pruning-based algorithm is replaced by an expansion-based algorithm. Thus, the main idea and game theoretic framework are not novel.\n\n- **Quality:**\nThe figures are well designed and the text is well structured. The experiments seem standard. The main algorithmic contributions are difficult to understand, however.\n\n\n- **Significance:**\nExperiments suggest a clear improvement over competing methods on multiple datasets.\nOnly some results on synthetic graphs in the appendix are not competitive.\n", "weaknesses": "- The biggest issue is that considerable parts of the paper are not well understandable. The algorithm and the contribution of its parts are not clear. Neither the game theoretic approach is explained. It would also be important to discuss the detailed differences between SAME and the similar approach SubgraphX.\n\n- The Shapley value is only computed approximately (as common).\n\n- The search space cannot be covered completely. Thus, the algorithm has therefore no guarantees to find a global optimum (as common). \n\n- The implications of the Theorem 1 need to be explained better. Currently, it does not seem to provide clear practical value, since the fact that one bound might be better than another one does not imply that the corresponding loss is also smaller..\n\n- Missing literature?\nGraphSVX: Shapley Value Explanations for Graph Neural Networks. ECML PKDD 2021.\n\n- **Reproducibility:** No code has been submitted.\n\n**Points of minor critique:**\n\n- The rules of the underlying multiplayer game are not explained.\n\n- Lines 110-121, which are supposed to explain the main contribution (the algorithm that explores the search space), are not really understandable. At least a correction of the grammar would be helpful. \n\n- Lines 130-134: It is impossible to follow the argument why the proposed algorithm requires fewer smoothness constraints on the function $f$, since the pruning algorithm is not introduced before.\nIt might help to move the discussion of related work to the beginning of the paper.\n\n- Figure 1 is not sufficient to explain the overall approach. The main components are not explained in the text.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your careful review and comments. Below please find our point-to-point responses to your comments.\n\n**Q1. The algorithm and the contribution of its parts are not clear. Neither the game theoretic approach is explained. It would also be important to discuss the detailed differences between SAME and the similar approach SubgraphX.**\n\n1. Detailed algorithm of SAME: Please kindly find the detailed algorithm of our method provided in **Algorithm 1-4** in the Supplementary Material.\n\n2. Contribution: In short, the key contribution of our work includes (1) *Theoretical aspect:*  i) We summarize and refine the characteristics of previous work and formally provide several desired properties (see Table 1 in the main manuscript) that can be considered by explanation methods for GNNs. ii) We provide the loss bound of the MCTS-based explanation techniques and further prove the superiority of our expansion-based MCTS in SAME compared to the previous work. (2) *Empirical aspect:* Our experiments cover both real-world and synthetic datasets. The results reveal that i) SAME consistently and significantly outperforms previous SOTA with different metrics under the same condition. ii) SAME qualitatively achieves a more human-intuitive explanation compared to previous methods across multiple datasets. \n\n   Our work is related to the SubgraphX, but it is different from it because our approach considers multiple explanations, redundancy in explanation, and node-wise importance of the given graph, simultaneously (see Table 1 in the main manuscript). Our approach is based on MCTS, but with a novel two-phase expansion-based MCTS version, which is shown to outperform the subgraphX, and outperform or be competitive with other SOTA methods in both inference time and explainability (see Table 2 and Table 3 in the main manuscript; Table S3 and Table S4 in the supplementary material; *Overall response: Q4* for additional experiments for detailed results).\n\n3. Game theoretic approach: We have revised the Preliminaries in Section 2 to make it more clear. In short, finding the explanation for a given graph $G$ by using an importance scoring function $I(f(\\cdot),G_{ex},G)$ can be formalized as: \n   $$G_{ex}^* = \\mathop{\\arg\\max}\\limits_{G_{ex} \\subseteq G} \\ I(f(\\cdot),G_{ex},G)$$ \n    where each explanation $G_{ex}^i$ has $n_i$ nodes, and the other nodes not in the explanation can be expressed as $\\{G \\backslash G_{ex}^i\\}=\\{v_{j}\\}_{j=n_{i}+1}^n$. Shapley value, as a concept originating from cooperative game theory, is used as an importance scoring function in this work. Therefore, the nodes or substructures or explanations (each explanation contains one or more substructures) can be regarded as a *player* in the game. The payoffs or utility function in the game is the Shapley value. The goal of our method is to find an explanation that can maximize the Shapley value.\n\n**Q2. The Shapley value is only computed approximately (as common).**\n\nIndeed, accurately obtaining the Shapley value has always been a very difficult problem [1]. In order to approach the exact solution of the Shapley value to a certain extent, we adopted the k-hop Shapley (see eqn. 3 in the main manuscript).\n\n**Q3. The search space cannot be covered completely.**\n\nGiven more time, MCTS can explore the search space more thoroughly and return better results. We acknowledge that our approach is not guaranteed to find the global optimum when the given running time is short. However, as MCTS is an \"anytime\" algorithm, the longer it runs, the better the explanation result tends to be.\n\n**Q4. The implications of the Theorem 1 need to be explained better.**\n\nThank you for your advice. We have restructured the article to emphasize the theoretical framework as the main contribution in this part of our study. In particular, we have broadened the scope of our theoretical exploration in juxtaposition with subgraphX and moved the toy examples from the appendix to the main body of the text. We hope this modification emphasizes the importance of this framework in specific application settings and enhances our exposition of theoretical optimality. It is worth noting that we are not comparing different bounds. For a given graph, its optimal interpretation should be the same under our mathematical framework. What we want to emphasize is that the expansion based algorithm can be closer to the optimal explanation than the pruning based algorithm. Please kindly find the detail in *Overall response: Q5*.\n\n**Q5. Missing literature: GraphSVX.**\n\nThank you for sharing this related work; we will add a discussion of them to the related work section in final the version. In short, although GraphSVX and our work both use Shapley value as a value function, the technical aspect of our method is orthogonal to GraphSVX: SAME is a perturbation-based method while GraphSVX is a surrogate method.\n\n**Q6. No code.**\n\nWe have released the code and sent an anonymized link to the AC in a separate comment.\n\n**Q7. Minor critique to Section 2.2 Line 110-121 and 130-134.**\n\nWe apologize for confusing you with the content in Section 2.2. We have revised this section.\n\nWe have modified the overall structure of Section 2.2: firstly, we introduce our mathematical framework; then, under this framework, we emphasize the difference between the pruning algorithm and the expansion-based algorithm, thus making our results clearer. Please kindly find the revised content in *Overall response: Q5*.\n\n**Q8. For what kind of GNNs does the proposed explainer work? Could attention be considered?**\n\nAs the SAME is a *model-agnostic* technique, our approach does not need further adaptation or modification for application to different GNN models. Please kindly find the related experiments in *Overall response: Q3*.\n\n**Reference**\n\n[1] The shapley value in machine learning. 2022."}]

Author rebuttal:
Dear Area Chairs and Reviewers,

We appreciate the valuable feedback and suggestions from the reviewers. Overall, the reviewers deem our paper well written, our method "novel" (qWxr,dDYx) and "effective" (8xQs), our theoretical analysis "well-developed" (qWxr), our evaluation results "standard" (xcjE). They also asserted that the problem studied in our paper "makes contributions to the field of GNN explanation" (qWxr, 8xQs).

In the following content, we make a general response to the questions that several reviewers are concerned about. 

**Q1. More insight and details about the computation complexity of SAME.**

To better analyze the limitation (discuss in Q2) of our proposed method, we refine the computational complexity of our approach as follows.

Given a graph $G=(V,E)$, we take a single iteration as an example which includes selection, expansion, simulation and backpropagation [1].

For the **important substructure initialization phase**, the goal of our SAME is to figure out a group of important substructures in *Important Substructure Set* whose sizes are smaller than $\gamma$. In the *selection step*, our method chooses an unvisited node or chooses the node with the highest reward if all nodes have been visited ($\mathcal{O}(|V|)$). In the *expansion step*, our method selects the node within 1-hop neighbors with the largest value, which requires $\mathcal{O}(1)$. In the *simulation step*, in the worst case SAME will append all the nodes by visiting all the edges in the graph which requires $\mathcal{O}(|V|+|E|)$. For the *backpropagation step*, time complexity is bounded by $\mathcal{O}(\gamma)$, as the maximum size of a substructure (depth of the search tree) is $\gamma$. Since we perform $M_1$ iterations, according to the law of multiplication, the time complexity of the first phase $\mathcal{O}(M_1\gamma|V|^2+M_1\gamma|V|\times|E|)$.

For the **explanation exploration phase**, similar to phase 1, in the *selection step*, the time complexity requires $\mathcal{O}(K)$ since the size of *Important Substructure Set* equals $K$. The *expansion step* requires $\mathcal{O}(1)$. In the *simulation step*, our method will append other substructures to the current state until the explanation size exceeds the sparsity limit, which is bounded by $\mathcal{O}(2^{K})$. We set a maximum simulation time $t_s$ as a time budget that requires $\mathcal{O}(t_s)$ since $\mathcal{O}(2^{K})$ can be very large. The *backpropagation step* is bounded by $\mathcal{O}(\frac{|V|\times(1-sparsity)}{\gamma})$, where $\gamma$ is the maximum size of each substructure. With $M_2$ iterations, the time complexity in this phase is $\mathcal{O}(M_2 K t_s \frac{|V|\times(1-sparsity)}{\gamma})$.

Overall, the time complexity of SAME is $\mathcal{O}(M_1\gamma|V|^2+M_1\gamma|V|\times|E| + M_2 K t_s \frac{|V|\times(1-sparsity)}{\gamma})$. As the $t_s$, $\gamma$, $K$, $M_1$, $M_2$ and $sparsity$ are predefined, therefore SAME is a polynomial-time method under these constraints. 

**Q2. More information about limitations of SAME.**

The limitations of our approach can be summarized as follows.

1. Scalability on large graphs. The time complexity of our method is $\mathcal{O}(M_1\gamma|V|^2+M_1\gamma|V|\times|E| + M_2 K t_s \frac{|V|\times(1-sparsity)}{\gamma})$. 
    For searching large graph ($|V| $ is large) explanation,
    a. $|V|^2$ will become large. 

    b. the $K$ needs to be larger accordingly to find the related explanation. 
    
    c. the $t_s$ needs to be increased so that MCTS can converge. 
    
    d. when the input graph is dense (|E| is large), $|V|\times|E|$ will also become large. 

2. Approximation of Shapley value. For time efficiency, the Shapley value can only be computed approximately. Under this approximation, the fairness axioms no longer hold. This is also identified as an unsolved issue for the Shapley value in machine learning by [2].

**Q3. Generalizability of SAME on different GNN architectures**

Our method does not need further adaptations on different GNN architectures. 

For the generalizability analysis, we tested SAME on GAT and GIN. The results are provided in Table 1 in the uploaded pdf. The results of the other two alternative explanation techniques (GraphSVX [3] and OrphicX [4]) are also provided.


**Q4. Further comparison of our SAME and alternative explanation techniques on other benchmarks**

To make our evaluation more convincing, we add new experiments on the text sentiment network Twitter [5] and molecular network BACE [6]. The results are presented in Table 2 in the uploaded pdf. 

In the following individual response, we address all the raised questions and add some new experiment results to further strengthen our contributions. 

**Reference**

[1] A survey of monte carlo tree search methods. 2012.

[2] The shapley value in machine learning. 2022.

[3] Graphsvx: Shapley value explanations for graph neural networks. 2021.

[4] Orphicx: A causality-inspired latent variable model for interpreting graph neural networks. 2022.

[5] Explainability in graph neural networks: A taxonomic survey. 2022.

[6] MoleculeNet: a benchmark for molecular machine learning.2018.



Meta-review: This paper received consistently positive reviews, and major issues have been resolved during rebuttals.
Decision: Accept (poster)