GStarX: Explaining Graph Neural Networks with Structure-Aware Cooperative Games
Authors: Shichang Zhang
Yozen Liu
Neil Shah
Yizhou Sun
Venue: NeurIPS 2022 Accept (2022)
Keywords: Graph Neural Networks
Explainablity
Cooperative Game Theory
Deep Learning

Abstract: Explaining machine learning models is an important and increasingly popular area of research interest. The Shapley value from game theory has been proposed as a prime approach to compute feature importance towards model predictions on images, text, tabular data, and recently graph neural networks (GNNs) on graphs. In this work, we revisit the appropriateness of the Shapley value for GNN explanation, where the task is to identify the most important subgraph and constituent nodes for GNN predictions. We claim that the Shapley value is a non-ideal choice for graph data because it is by definition not structure-aware. We propose a Graph Structure-aware eXplanation (GStarX) method to leverage the critical graph structure information to improve the explanation. Specifically, we define a scoring function based on a new structure-aware value from the cooperative game theory proposed by Hamiache and Navarro (HN). When used to score node importance, the HN value utilizes graph structures to attribute cooperation surplus between neighbor nodes, resembling message passing in GNNs, so that node importance scores reflect not only the node feature importance, but also the node structural roles. We demonstrate that GStarX produces qualitatively more intuitive explanations, and quantitatively improves explanation fidelity over strong baselines on chemical graph property prediction and text graph sentiment classification. Code: https://github.com/ShichangZh/GStarX 


GStarX: Explaining Graph Neural Networks with Structure-Aware Cooperative Games
Shichang Zhang'
Yozen Liu Neil Shah Yizhou Sun'
University of California, Los Angeles Snap Inc.
(shichang, yzsun)@cs ucla. edu
2[yliu2, nshah)@snap.com com
Abstract
Explaining machine learning models is an important and increasingly popular area of research interest. The Shapley value from game theory has been proposed as prime approach to compute feature importance towards model predictions on images, text, tabular data, and recently graph neural networks (GNNs) on graphs. In this work, we revisit the appropriateness of the Shapley value for GNN explanation, where the task to identify the most important subgraph and constituent nodes for GNN predictions. We claim that the Shapley value is a non-ideal choice for graph data because is by definition not structure-aware. We propose Graph Structure-aware eXplanation (GStarX) method to leverage the critical graph structure information to improve the explanation. Specifically, we define scoring function based on a new structure-aware value from cooperative game theory proposed by Hamiache and Navarro (HN). When used to score node importance, the HN value utilizes graph structures attribute cooperation surplus between neighbor nodes, resembling message passing in GNNs, so that node importance scores reflect only the node feature importance, but also the node structural roles. We demonstrate that GStarX produces qualitatively more intuitive explanations, and quantitatively improves explanation fidelity over strong baselines on chemical graph property prediction and text graph sentiment classification) !
Introduction
Explainability is crucial for complex machine learning (ML) models sensitive applications, helping establish user trust and providing insights for potential model improvements. Many efforts focus on explaining models on images, text, and tabular data. In contrast, the explainability of models on graph data is yet underexplored. Since explainability can be especially critical for many graph tasks like drug discovery, and interest in deep graph models is growing rapidly, further investigation of graph explainability is warranted. In this work, we study graph MI. explanation with graph neural networks (GNNs) as the target models, given their popularity and widespread use for graph machine
learning tasks
42 29
38
34
33 45
ML explinabillit, important features are identified, and the Shapley value 330 has been deemed as "fair" scoring function for computing feature importance. Originally from cooperative game theory, many values, including the Shapley value, have been proposed for allocating a total payoff to players in game. When used for scoring the feature importance of data instance, the model prediction is treated as the total payoff and the features are considered as players. In particular, for an instance with features {I1.... }. ). the Shapley value of its ith feature is computed via aggregating mii, S), which are the marginal contributions of æ; to sets of other features æs C ( 2.,) {æ;). Each æg called coalition. Each m(i, S) is computed the difference between model outputs for
Code available at hatpps://iithu: com cow/Shi cta./SShhccan22//Sttrr
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

quile good natured and way spend
Shapley weights
Manginal
F U
[
weights
1/3
1/2
good
natureed
p12, (T))
P (1)
1/4 and
not
P(3. (1))
1/6
spend
way
1/3
Figure 1: Explanations on graphs with structure- aware values (like HN) offers advantages over non-structure-avee awwre values (like Shapley). (a) Synthetic graph (left): The Shapley value assigns weights to m(i, 5) only based on size of øs, while the HN value assigns weights considering structures and in particular gives zero weight to the disconnected sts. (b) Text graph (middle): For a sentence classified as positive, the ("not", "good") coalition shouldn't be considered when they are not connected by "bad". (c) Chemical graph (right): For a chemical graph with mutagenic functional group -NO2, the importance of the atom N (node 1) is better recognized if decided locally within the functional group.
as U } and æs, e.g., difference of probability belonging target class for these two set of features, and it is meant to capture the interaction between æ; and æs. The Shapley value is widely used for explaining ML models on images, text, and tabular data, when the features pixels, words, and attributes 22 24
The Shapley value has recently been extended to explain GNNs graphs through feature importance scoring as above, where features are nodes [9] or supernodes [44]. We argue that the Shapley value is non-ideal choice for (super)node importance scoring because its contribution aggregation is non-structure-avare The Shapley value aggregation assumes no structural relationship between æ;; and æg even though they are both parts of the input graph (a review of the Shapley value is in Section 2.2). Since the graph structure generally contains critical information and is crucial to the success of GNNs, we consider properly leveraging the structure with better structure-aware scoring function.
We propose Graph Structure-gware eXplanation (GStarX), where we construct stmucture-aware node importance scoring function based on the Mamiache-Navaryy (HN) value (15) from cooperative game theory. Recall that GNNs make predictions via message passing, during which node representations learned by aggregating messages from neighbors. Message passing aggregates both feature and structure information, resulting in powerful structure-awar models (5). The HN value shares a similar idea message passing by allocating the payoff surplus generated from the cooperation between neighboring players (nodes). When used as scoring function to explain node importance, the HN value captures both features and structural interactions between nodes (details in Section ) Figure a)) shows an example comparing the Shapley value and the HN value. In this example, their difference boils down to different aggregation weights of marginal contributions, where the former is uniform and the latter is structure-aware (details in Section 3.2 In summary, our contributions are:
Identify the non-structure-ave aware limitation of the Shapley value for GNN explanation. Introduce the atructure-awar aware HN value from cooperative game theory to the graph machine learning community and connect it to the GNN message passing and GNN explanation.
Propose a new HN-value- based GNN explanation method GStarX, and demonstrate the superiority of GStarX over strong baselines for explaining GNNs chemical and text graphs.
2 Preliminaries
2.1 Graph neural networks
Consider graph G with (feature-enriched) nodes V and edges E. We denote G as G A), where X E R denotes d-dimensional features of n nodes in V, and A E (0, 10 denotes the adjacency matrix specifying edges E. GNNs make predictions on g by learning representations via the pressage-pussingg mechanism. During message passing, the representation of each node E V updated by aggregating its own representation and representations (messages) from its neighbors. We denote the set of neighbors as (u). This aggregation is recursively applied, so collect
2

---

messages from its multi-hop neighbors and produce structure-awarr representations 5 With h denotes the representation of node at iteration I, and AGGR(: denotes the aggregation operation, e.g. summation, the representation update is shown in Equation
AGGR(h (-1), thg (i E((()))
2.2 Cooperative games
cooperative game denoted by (N, v), is defined by set of players N (I....,,)) n), and a characteristic function funtriito v 2 - R. takes a subset of players S S N, called coalition, and maps it to a payoff o(S), where v(0) := 0. A solution function is a function maps each given game (Ni v) to 6(N, v) E _" The vector cNN, v), called solution, represents a certain allocation of the total payoff ((N) generated by all players to each individual, with the ith coordinate (N v) being the payoff attributed to player i. (NN, u) is also called the "value" of the game when it satisfies certain properties, and different values were proposed to name solutions with different properties [30 [5).
The Shapley value is one popular solution of cooperative games. The main idea is to assign each player a "fair" share of the total payoff by considering when player cooperates with a coalition S, the total payoff v(S U {i)) may be very different from vSS) + v(f}) because of i's interaction with S. Thus the marginal contribution of to S is defined as by m(2,S) ] U (z}) (S). Then the formula of the Shapley value for i is shown in Equation 2 where marginal contributions to all possible coalitions C N Mi) are aggregated. The first identily in Equation shows that the aggregation weights are first uniformly distributed among coalition sizes (outer average), then uniformly distributed among all coalitions with the same size (inner average).
possible player interactions. For example,
Average over & Average over s.t. [S] =
[S] -SS 1)1 m(i, S) (2)
(. =
Σ
m(i,S) = Σ
n!
k=
SC S|=k
SENYO
Games with communication structures. Although the Shapley value is widely used for cooperative games, its assumption of fully flexible cooperation among all players may not be achievable. Some coalitions may be preferred over others and some may even be impossible due to limited communica- tion among players. Thus, (26) uses graph G as the communication structure of players to represent cooperation preference. A game with a communication structure is defined by a triple (N, u, 9), with N being the node set of G. This game formulation is more practical than fully flexible cooperation when cooperation preference is available. Several values with different properties have been proposed for such games 26
3 18 including the HN value [15]
GNN explanation via feature importance scoring
3.1 Problem formalization
general approach to formalize an ML explanation problem is through feature importance scoring
24 o). where features may refer to pixels of images. words of text, nodes/cdgesssubbraphhh of graphs. Let f()) denote a to-be-explained GNN, g = (V,X, A) denote an input graph, and 0 < 7 1 denote sparsity constraint to enforce concise explanation. GNN explanation via subgraph scoring is aimed to find a subgraph g that maximizes a given evaluation metric EVAL (s.))) which measures the faithfulness of g regarding making predictions with f(-), i.e.
arg (v))(f()
When the task is graph classification and f(-) outputs a one-sum vector f()) E [0. 11 containing probabilities for & belongs to C' classes, an example EVAL can be the prediction probability drop for removing y from G, i.e EVAL(J(), 9, = ([()),.- [f(') with c" arg max,
In practice, since the number of subgraphs combinatorial in the number of nodes, the objective is often relaxed to finding set of important nodes or edges first and then inducing the subgraph
3

---

25 9 A more tractable objective of finding the optimal set of nodes S S V is given by
S arg max SC SCV.1915TVV IES
Σ (C)
(4)
Existing methods often boil down to Equation with different scoring functions (SCORE), and finding proper SCORE is non-trivial. One example of SCORE is to evaluate each node i directly as SCORE(f(-). g. = [f((i))le- However, this choice misses interactions between nodes and corresponds to trivial case in GNNs where no pessage-passing is performed for {2}. Another possibility is to use EVAL as ScoRF, e.g., (CORE(J()),
[f(]]]_ - [(()(())) However, this again fails to capture interactions between nodes; for example, two nodes i and may be both important but also complimentary, so their contribution to G can only be observed when they are missing simultaneously.
3.2 Scoring functions from cooperative games
Given the challenges for defining a proper SCORE, solutions to cooperative games, like the Shap- ley value, have been proposed with f(-) as the characteristic function, i.e. SC
(.(19), (()) 44 9]. However, existing works only use the non-structure-aware Shapley value. In contrast, values defined on games (NV v, 9) with communication structures G are naturally structure- aware but were never considered GNN explanation. Below we discuss the non-structure-aware limitation of the Shapley value in detail and motivating structure-aware values with practical exam- ples in GNN explanation.
The Shapley value is defined on games (N, v), which by definition takes no graph structures. It assumes flexible cooperation between players and uniform distribution of coalition importance that only depends on |.S] (see Equation 2 Even if a G is given and the game is defined as (N,v,9) G), the Shapley value will overlook G when aggregating mii S). contrast, structure-aware values on (N, 9. can be interpreted as weighted aggregation of coalitions with more reasonable weights. Although different solutions Φ(N, v, G) have their nuances in weight adjustments [I3] [5] 26 (8),
they share two key properties: (1) the weight is zero if and S are disconnected because they are interpreted as players without communication channels [26), and (2) the weight is impacted by the nature of connections between i and S because it is easier for better-connected nodes to communicate.
synthetic example. We take the HN value (definition in Section 4.1 as an example structure- aware value and compare it to the Shapley value in simple graph in Figure [a). To compute ø1 (N, u, G). both values aggregates m1. for S E {0. [2), (3); (2.3]). The Shapley value first assigns a uniform weight 3 to three different |S], and then splits weights uniformly for the |S||
case to be 6. However, the HN value assigns weight zero for S {3} because and 3 disconnected in coalition {1,3) 3} and are assumed to be two independent graphs that shouldn' 't interact (property (1)). Their interaction is rather captured in the S = {2, 3} case, when I and 3 are connected by the bridging node 2, and this case is also downweighted from to 7. as 3 is relatively far from 1 (property (2)).
practical example. The good properties of structure-aware values can help explain graph tasks. The example in Figure [Tb) is from GraphSST2 (dataset description in Section [5.]), where the graph for sentiment classification is constructed from the sentence "is still quite good-natured and not bad way to spend hour" with edges generated by the Biaffine parser (1).. Assuming model can correctly classify it as positive. Intuitively, "good" and "not a bad" are central to the human explanation. To compute the Shapley value of the word "good", the coalition "not good" will diminish the positive importance of "good", despite the two words lacking any direct connection. A structure-awars value can instead eliminate the ("not", "good") coalition, and only consider interactions between "not" and "good" (in fact, "not" and any other word) when the bridging "bad" appears, hence better binding "not" with "bad" and improving the salience of "good". In Section 5.2 we revisit this example to observe impacts of aructure-awarente empirically.
A similar objective can be defined as S over edges E. We define it over nodes as nodes often contain richer features than edges and are flexible. One advantage of this choice will be made clear in Section 5.2

---

4 GStarX: Graph Structure-aware eXplanation
We propose GStarX, which uses structure-aware HN-value-based SCORE to explain GNNs. We first state the definition of the HN value in cooperative game theory (4.1) and then connect it to the GNN message passing (4.2). and finally give the GStarX algorithm for GNN explanation 4.3
4.1 The HN value
Let (N, u. () be game with a communication structure 9 and S S N be coalition. Let $ = (i)( US to be the union of S and its neighbors in G. Let S/g be the partition of S conttiniin connected components in G, i.e., S/G { = j or and j are connected in S by & of g E 5). Let GiS] be the induced subgraph of S in G. For example, in Figure [b), when S = "an", "hour"), 8 will be ("is", "good", "an", "hour", "spend"), S/G will be [T"is"), ("an", "hour")), and G[S] will be the subgraph with a two-node component an hour and a single node component is
Definition 4.1 (Surplus). The surplus S) generated by coalition S cooperating with its neighbor j is defined
p(i,S) = v(Su u(S) - v((i))
(5)
Intuitively, p(j. .) is generated because is actively cooperating. Thus, when evaluating a fair payoff to S, portion of P(j.S) should be added to its own payoff v(S). This idea leads to the next definition of associated games regarding the original games, where surplus allocation is performed.
Definition 4.2 (HN Associated Game). Given 0 S T 1 representing the portion of surplus that will be allocated to a coalition S for its cooperation with other players. The HN associated game (N, u 9) of (N, v, 9) defined as
v(S)+ +T
Σ P(i.S) if S// =1
(6)
JESYS
(S)
(T)
otherwise
TES/S
The HN value is a solution on (N, c, 9). It is computed by iteratively constructing a series of HN associated games until it converges to limit game (N, ē, G. In other words, we first construct ot from v by surplus allocation. Then we construct et* from u by allocating the surplus generated from the v. and so on. The convergence of the limit game is guaranteed and the result 7 is independent of r under mild conditions as shown in [15.. The HN value of each player uniquely determined by applying i to that player, i.e. Φz (N, 9) o((i)). We state the formal definitions of the limit game and the uniqueness theorem of the HN value in Appendix E.2
4.2 Connecting GNNs and the HN surplus allocation through the message passing lens
Both the GNN message passing (MP) and the associated game surplus allocation (SA) are iterative aggregation algorithms, with considerable alignment. In fact, SA on each singular node set 5 (i) exactly MP: Equation becomes instantiation of Equation 1 with AGGR(a, b) a + Σ, j by on scalar node value and neighbor set b. These algorithms differ in that SA applies more broadly to | 1 cases; it treats S as a supernode when nodes in S form connected component in G, and handles disconnected S component-wis via Equation 7
We illustrate SA using a real chemical graph example. The molecule shown in Figure [c) is taken from MUTAG (dataset description in Section 5.Ip. It is known to be classified as mutagenic because of the -NO2 group (nodes 1, 2, and 3) [8]. When we compute v ({1)), the surplus p(2. {1}), p(3, {1}), and p(4, {1}) are allocated to node I (like messages passed to a central node in GNN), Then surplus are aggregated together with v (((1)) following Equation 6 to form ((1]).
For graphs, the SA approach has two advantages over the uniform aggregation approach used in the Shapley value: (1) The aggregated payoff each vf is structure-aware, like representations learned by GNNs [. and (2) the iterative computation preserves locality, which is preserved by GNNs 3. other words, these two properties mean close neighbors heavily influence each other due to cooperation in many iterations, while far away nodes less influence each other due to little
5

---

Algorithm 1 GStarX: Graph Structure-Aware Explanation
Algorithm 2 The Compute-HN Function
Input: Graph 9 with nodes V = {ui..... J. trained GNN f(-), empirical expectation fo hyperparameter T, max sample size m, number of samples J, sparsity Get the predicted class c" arg max,
Input: Graph instance & with nodes
{ui...., characteristic function v, hypepparametterrr 7.
for S in 2 do Compute payoff o(5) (Eq. end for
Define characteristic function u(S) = (gs)) fo- if m then
Φ Compute-HN(G, V, ()),
Construct matrix H (r,n.g) (Eq. [6)]
else
repeat
e = Compute-HN-MC(G, V, v()), T,,,
H HH
end
until H converges Get the limit game ē Hu (Eq.
Sort è in descending order with indices { Anf
= |>|v|
Assign the first n entries of ö to Return: e
Return: 8 {U u Um
cooperation. In the MUTAG example, since the local -NO2 generates high payoff for the mutagenicity classification, locally allocating the payoff helps us better understand the importance of the nitrogen atom and the oxygen atoms. Whereas aggregating over many unnecessary coalitions with far-away carbon atoms can obscure the true contribution of -NO2. We will revisit this example in Section 5.2
4.3 The GStarX algorithm
We now state our algorithm for explaining GNNs with GStarX. Notice that GStarX scores nodes in graph but not each dimension of node features. Feature dimension importance explanation an orthogonal perspective that can be added top of GStarX. We leave this extension as a future work. GStarX formulates the GNN explanation problem as feature importance scoring problem. where nodes are scored to find the optimal node-induced subgraph as we introduced in Section 3.1 essentially implements and solves the objective in Equation 4 where an HN-value- based ScoRE is used. To such SCoRE, game, and then apply the formula in Equation 6 and /7] Suppose the inputs are a graph 9 with nodes V = (u...... U, and label y {I. C}. ). GNN f-)) outputs probability vector f fG) [0, 1]c, and the predicted class c* = arg max (99)) Let V be players, and let the normalized probability of the predicted class be the characteristic function v:
need to define the players and the characteristic function of the
v(S) = [[( fa ASCV
(8)
Here the normalization term So- = E [[ is the expectation over a random variable G represent- ing a general graph. In practice, approximate it using the empirical expectation over all 9 in the dataset. SCORE will be the HN value of the game, i.c., SCORE(f()) g. i) = o.(V, G) o((i)).
Given SCORE, solve the objective by first computing the scores R" then selecting the top | scores greedily as in Algorithm Practically, like other game-theoretic methods, the exact computation of the HN value is infeasible when the number of players is large. We thus do an exact computation for small graphs (the if-branch) and Monte-Carlo sampling for large graphs (the else-branch). The Compute- function is shown in Algorithm 2 where the H stands for matrix form of the associated game defined in Definition 4.2 (See Appendix E.2 and E.3 for details of the matrix form and algorithms for Compute- Compute-HN-MG), Also, even though the algorithm is stated for graph classification, GStarX works for node classification as well. This can be easily seen since GNNs classify nodes u, by processing an ego-graph centered ug the task can be converted to graph classification with the label of u, used as the label of the ego-graph. We focus on graph classification in the main text for simpler illustration and discuss more about node classification in Appendix B
5 Experiments
5.1 Experiment settings
Datasets. We conduct experiments on datasets from different domains including synthetic graphs, chemical graphs, and text graphs. A brief description of the datasets is shown below with more detailed statistics in Appendix A.I

---

Chemical graph property prediction. MUTAG [8, BACE and BBBP 39 contain chemical molecule graphs for graph classification, with atoms as nodes, bonds as edges, and chemical properties as
graph labels.
Text graph sentiment classification. GraphSST2 and Twitter 44 contain graphs constructed
from text. Nodes are words with pre-trained BERT embeddings as features. Edges are generated by the Biaffine parser [12]. Graphs are labeled as positive or negative sentiment.
Synthetic graph motif detection. BA2Motifs [25] contains graphs with a Barabasi-Alll Albert (BA) base graph of size 20 and a 5-node motif each graph. Node features are 10-dimensional all-one vectors. The motif can be either house-like structure cycle. Graphs are labelled in two classes based on which motif they contain.
GNNs and explanation baselines. We evaluate GStarX by explaining GCNs [9 on all datasets in our major experiment in Section 5.2 In the ablation study in Section 5.3 we further evaluate on
GIN [40] and GAT [36] on certain datasets following [44]. All models are trained to convergence with hyperparameters and performance shown in Appendix A.2 We compare with strong baselines representing the SOTA methods for GNN explanation: GNNExplainer [41,, PGExplainer (25). SubgraphX [44), GraphSVX 19], and OrphicX (21) In particular, SubgraphX and GraphSVX use
Shapley-walue-basee scoring functions.
Evaluation metries. Evaluating explanations is non-trivial due to the lack of ground truth. We follow 44 43 to employ Fidelity, Inverse Fidelity (Inv-Fidelity), and Sparsity as our evaluation metrics. Fidelity and Inv-Fidelity measure whether the prediction faithfully important to the model prediction by removing the selected nodes or only keeping the selected nodes respectively. Sparsity promotes fair comparison by controlling explanations to have similar sizes, since including more nodes generally improves Fidelity and Inv-Fidelity, and explanations with different sizes are not directly comparable. Ideal explanations should have high Fidelity, low Inv-Fidelity, and high Sparsity, indicating relevance and conciseness. Equations 9 show their formulas.
Fidelity(G, 9) = (T()) (5(
(9)
Inv-Fidelity(G.g) [f(9))- [f(g)).-
(10)
Sparsity(G.g))
19///99
(11)
Fidelity and Inv-Fidelity are complementary and are both important for good explanation g. Fidelity justifies the necessity for g to be included to predict correctly. Inv-Fidelity justifies the sufficiency of standalone g to predict correctly. As they are analogous to precision and recall, we draw an analogy to the Fl score to propose a single-scalar-metris "harmonic fidelity" (H-Fidelity), where we normalize them by Sparsity and take their harmonic mean; see Appendix A.3 for the formula.
Hyperparameters. GStarX includes three hyperparameters: T for the allocated surplus in the associated game, m as the maximum graph size to perform exact HN value calculation, and J as the number of samples for the MC approximation. In our experiments, we choose T 0.01 since we need < 2 for convergence (Appendix (E22) and all graphs in the datasets above have less than 200 nodes. For m and J, bigger values should be better for the MC approximation, and we found v 10 and J = work well empirically.
5.2 Evaluation results
Quantitative studies. We report averaged test set H-Fidelity in Table We conduct different runs to get results with Sparsity ranging from 0.5-0.85 in 0.05 increments (Sparsity cannot be precisely guaranteed, hence it has minor variations across methods) and report the best H-Fidelity for each method. GStarX outperforms others 4/6 datasets and has the highest average. We also follow [4] to show the Fidelity vs. Sparsity plots for all sparsity in Appendix A.4
Qualitative studies. We visualize the explanations of graphs in GraphSST2 in Figure 2 and compare them qualitatively. We show explanations selected with high and comparable Sparsity on a positive (upper) graph and a negative (lower) graph. GStarX concisely captures the important words for sentiment classification without including extraneous ones for both sentences. Baseline methods generally select some-but-not-al important sentiment words, with extra neutral words as well. Among baselines, SubgraphX gives more reasonable results. However, cannot cover two groups of important nodes with a limited budget because it can only select connected subgraph as the explanation; e.g.
7

---

"is still quite good natured and not a bad way to spend an hour"
xtll
sulle
xsll
guiee
qute
saturel
poot
rarkure
good
poof
untaed
"the title 's lameness should elue you on how bad the movic is."
lite
Iiee
Iile
Iile
alc
's
Linace
Jaool
Dic
Tbc
shoudd
clse
yo0
Cite
In
Clie
Yon
clac
you
cisc
your
cluc
baal
moviic
bad
movie
bad
move
bad
15
nowi
Ical
mavic
Ieal
how
GNNixplaner
Killspllaeer
SubgraphX
GeapaSVXX
OrpaicX
Figure 2: Explanations sentences from GraphSST2. We show the explanation of one positive sentence (upper) and one negative sentence (lower). Red outlines indicate the selected nodes/edges as the explanation. GStarX identifies the sentiment words more accurately compared baselines.
GNNExplainer
PGExplainer
SubgraphX
Fox 0.764 hrloec
"Grond Truth"
GraghS VX
OrphicX
GStaxX
Figure 3: Explanations on a mutagenic molecule in MUTAG. Carbon atoms (C) are in yellow, nitrogen atoms (N) are blue, and oxygen atoms are in red (O). Dark outlines indicate the selected nodes/edges as the explanation. We report the explanation Fidelity (fide), Inv-Fidelity (inv-fide), and H-Fidelity (h-fide). GStarX gives a significantly better explanation than other methods in terms of these metrics.
to cover the negative word "lameness" in the lower sentence, SubgraphX needs at least three more nodes along the way, which will significantly decrease Sparsity while including undesirable, neutral words. Moreover, we discussed in Section 3.2 that the Shapley value will downgrade the positive importance of the word "good" for the upper sentence. Comparing the normalized contribution scores of our HN-value-bast
method GStarX and the Shapley-based method GraphSVX, contribution of "good" is higher in ours: 0. vs. 0.0371.
We visualize explanations selected with high and comparable Sparsity of a mutagenic molecule from MUTAG in 3 Explanations on chemical graphs are harder evaluate than text graphs as they require domain knowledge. MUTAG has been widely used benchmark for evaluating GNN explanations because human experts recognize -NO2 as mutagenic (8) which makes MUTAG dataset with "ground truth"] Surprisingly, we found that GStarX generates much better H- Tidelity/Fideiitylln--ddde
than other methods and even the "ground truth" by only selecting the -O in -NO2 as explanations. In particular, the -0.234 Inv-Fidelity of GStarX means the selected subgraph has an even better prediction result than the original whole graph (0 Inv-Fidelity) and the ground truth (-0. 1-0.143 Inv-Fidelity) because nodes not significant to the GNN prediction are removed. Fidelity metrics of baselines are inferior to GStarX because they include other non-discriminative carbon atoms despite they capture -NO2 to some extent. This suggests that even though human experts identify -NO2 as the "ground truth" of mutagenicity, the GNN only needs -0 to classify mutagenic molecules. With the goal being understand model behavior, GStarX explanation is better. Moreover, SubgraphX is the only baseline that has better H-Fidelity than the "ground truth", but it
*Carbon rings were also claimed as mutagenic by human experts. but we found it is not discriminative as they exist in both mutagenic and -on-maaggenic molecules in MUTAG.
8

---

Table The best H-Fidelity (higher is better) of 8 different Sparsity for each dataset. GStarX shows higher H-Fidelity on average and on 4/6 datasets.
Dataset
GNNExplainer
PGExplainer
SubgraphX
GraphSVX
OrphicX
GStarX
BA2Motifs
0,4841
0.4879
0.6050
0.5017
0.5087
0.5824
BACE
0,5016
0.5127
0,5519
0,5067
0.4960
0.5934
BBBP
0,4735
0,4750
0,5610
0,5345
0,4893
0,5227
GraphsST2
0,4845
0.5196
0.5487
0.5053
0.4924
0,5519
MUTAG
0.4745
0.4714
0.5253
0.5211
0,4925
0.6171
Twitter
0,4838
0.4938
0,5494
0.4989
0.4944
0,5716
Average
0.4837
0.4934
0.5569
0.5114
0.4952
0.5732
Table 2: GStarX shows higher H-Fidelity for both GAT on GraphSST2 and GIN on MUTAG.
Dataset
GNNExplainer
PGFxplainer SubgraphX
GraphSVX
OrphicX
GStarX
GraphSST2
0.4951
0,4918
0,5484
0,5132 0.5592
0.4997 0.5152
0.5542
NUTAG 0.5042
0.4993
0.5264
0.6064
only capture -NO2 because its search algorithm requires the explanation be connected, so its Inv-Fidelity is not optimal. In fact, GNNExplainer, PGExplainer, and SubgraphX can never generate explanations including only disconnected -O without -N like GStarX, because the former two solve the explanation problem by optimizing edges (as opposed to Equation 4 and the latter requires connectedness. More MUTAG explanation visualizations are in Appendix
5.3 Ablation study and analysis
Model-agnostic explanation. GStarX makes no assumptions about the model architecture and can be applied explain various GNN backbones. We use GCN for all datasets in the major experiment above for consistency, and we now further investigate performance on two more popular GNNs: GIN and GAT. We follow 44 to train GIN on MUTAG and GAT on GraphsST2 and show results in Table 2 For both settings, GStarX outperforms the baselines, which is consistent with results on GCN.
Efficiency study. The GStarX algorithm scales in O(J) with practical J xx V/. Following 44 study the empirical efficiency of GStarX by explaining 50 randomly selected graphs from BBBP. We report the average run time in Table Our results for the baselines are similar to 44 GStarX is not the fastest method, but it is more than two times faster than SubgraphX. Since explanation usually doesn't 't have strict efficiency requirements in real applications, considering GStarX generates higher- quality explanations than the baselines, we believe the time complexity of GStarX is acceptable.
Explanation sparsity study. To further study whether the obtained scores by GStarX are sparse, we follow [1] to evaluate an entropy-basse based sparsity measure on model output scores. We show the all datasets, and compare them with three reference score distributions on all n nodes in a graph. 1) An upper bound: Uniform(n). which represents the least sparse output. 2) A practical lower bound: Uniform(0.25** which represents very sparse outputs with only top 25% of nodes. 3) 70.25 which is a more realistic version of case 2). Results in Table 4 show the average entropy-basee sparsity of GStarX is much lower than Uniform(n) and close to (oisson(0.255n)) which justifies the GStarX outputs are indeed sparse. A more detailed discussion of this metric and these three reference distributions in Appendix A.5
average GStarX entropy-bast -bsed sparsity
Related work
GNN explanation aims to produce an explanation for GNN prediction on given graph, usually as subgraph induced by important nodes or edges. Many existing methods work by scoring nodes or edges and are thus similar to this work. For example, the scoring function of GNNExplainer [41] is the mutual information between a masked graph and the prediction on the original graph, where soft masks on edges and node features are generated by direct parameter learning. PGExplainer (55 uses the same scoring function as [41 but generates a discrete mask on edges by training an edge mask predictor. SubgraphX 4 uses the Shapley value as scoring function on subgraphs
As some baselines take over 24 hours full GraphSST2, randomly select 30 graphs for this analysis.

---

Table 3: Average running time on 50 graphs in BBBP
Method
GNNExplainer
PGExplainer
SubgraphX
GraphSVX
OrphicX
GStarX
Time(s)
11.92
0.03 (train 720) 75.96
3,06
0.15 (train 915)
31.24
Table 4: The entropy-based sparsity scores of GStarX vs, three reference distributions, which shows GStarX outputs are indeed sparse.
Dataset
BA2Motifs
BACE
BBBP
GraphSST2
MUTAG
Twitter
GStarX
2.1352
2.4481
2.3290
2.3282
2.2434
2,2114
Uniform(n)
3,2189
3,5080
3.0728
2.8698
2.8612
2,9833
Uniform(0.25
1.8326
2.1217
1.6893
1.4855
1.4749
1.5970
Poisson(0.25*n))
2.3204
2.4686
2.2416
2.1336
2.1323
2.15
selected by Monte Carlo Tree Search (MCTS), and GraphSVX 9 uses least-square approximation to the Shapley value to score nodes and their features. While SubgraphX and GraphSVX were we show in Section 33] the Shapley value they
shown to perform better than prior alternatives, try to approximate is non-ideal as it is non-structure-aware. Although SubgraphX and GraphSVX use T--hop subgraphs and thus technically they use the graph structure, such structure usage are very limited in achieving structure-awarenes awareness as we show in Appendix G While there are many other GNN explanation methods from very different perspectives, i.e. gradient analysis
[23] model
decomposition M, surrogate models [37], and causality (20 21), we defer their details to Appendix given their lesser relevance.
Cooperative game theory originally studies how to allocate payoffs among a set of players in a cooperative game. Recently, certain ideas from this domain have been successfully used in feature importance scoring for ML model explanation [22 32 (24). When used for model explanation, data features becomes players the game, e.g. pixels for images, and the value of the game gives feature importance scores. The vast majority of works in this line, like the ones cited above, deem the Shapley value 300 to be the only choice. In fact, there are many other values with different properties and used in different situations in cooperative game theory. However, to the best of our knowledge, only mentions the Myerson value (26] in the context of proposing a connected Shapley (C-Shapley) value for explaining sequence data, and it is not directly comparable to ours for graph data. A detailed discussion of the Myerson value and the C-Shapley value can be found in Appendix F Our work follows the cooperative game theory approach to explain models on graph data using the HN value [13, which as we show is a better choice than the Shapley value given its
7 Conclusion and future work
In summary, we study GNN explanation on graphs via node importance scoring. We identify the non-structure-awaan challenge of existing Shapley-value-bar based approaches and propose GStarX to assign importance scores to each node via a structure- between the HN value surplus allocation and GNN message passing. GStarX demonstrates its superiority over strong baselines on chemical and text graph classifications. A limitation of GStarX is that the importance of different node feature dimensions this extension, which could be done by scoring a subset of nodes together with a subset of features each time. Another future direction the Shapley value, more values are possible for explaining ML models. For graph data, edge-based values like [2] can potentially be applied an alternative edge-based objective like Equation Other values may be appropriate to more data types beyond graphs.
HN value. We also build connections
explained. One future work is to add
exploit the rich cooperative game theory literature. Beyond
Acknowledgement
This work was partially supported by NSF III-1705169, NSF 1937599, NSF 21 2119643, Okawa Foundation Grant, Amazon Research Awards, Cisco research grant USA000FP288889, Picsart Gifts, and Snapchat Gifts.
10

---

References
[1] Federico Baldassarre and Hossein Azizpour. Explainability techniques for graph convolutional networks, 2019.
[2] Peter Borm, Guillerom Owen, and Stif Tijs. On the position value for communication situations. SIAM Journal on Discrete Mathematics, 5(3):305-320, 1992.
[3] Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. arXiv preprint arXiv: wtw.1112........ 2013.
[4] Jianbo Chen, Le Song, Martin J. Wainwright, and Michael I. Jordan. L-shapley and c-shapley: Efficient model interpretation for structured data. In International Conference on Learning Representations, 2019.
[5] Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? arXiv preprint arXiv:2002.04025, 2020.
[6] Piotr Dabkowski and Yarin Gal. Real time image saliency for black box classifiers. arXiv preprint 1rXiv:1705.07888 708.07877.7.... 2017.
[7] Morton Davis and Michael Maschler. The kernel of a cooperative game. Naval Research Logistics Quarterly, 12(3):223-252) 1965.
[8] Asim Kumar Debnath, Rosa L Lopez de Compadre, Gargi Debnath, Alan J Shusterman, and Corwin Hansch. Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity. Journal of medicinal chemistry, 34(2):78--777, 1991.
[9] Alexandre Duval and Fragkiskos D Malliaros. Graphsvx: Shapley value explanations for graph neural networks. arXiv preprint 11X.v:2104.1042. 2021.
[10] Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
[11] Thorben Funke, Megha Khosla, and Avishek Anand, Zorro: Valid, sparse, and stable explana- tions in graph neural networks. arXiv preprint (1.Kii:22150066660 2021.
[12] Matt Gardner, Joel Grus, Mark Neumann, Oyvind Tafjord, Pradeep Dasigi, Nelson Liu, Matthew Peters, Michael Schmitz, and Luke Zettlemoyer. Allennlp: deep semantic natural language processing platform. arxiv preprint arxiv: wtw.:::803.06660 2018.
[13] Gérard Hamiache. A value with incomplete communication. Games and Economic Behavior, 26(1):59-78, 1999.
[14] Gérard Hamiache, Associated consistency and shapley value. International Journal of Game Theory, 30(2):279-289, 2001.
[15] Gérard Hamiache and Florian Navarro. Associated consistency, value and graphs. International Journal of Game Theory, 49(1):227-249, 2020.
[16] S Hart and A Mas-Colell. Potential, value, and consistency. Econometrica, 57(3)5589-614, 1989.
[17] Qiang Huang, Makoto Yamada, Yuan Tian, Dinesh Singh, Dawei Yin, and Yi Chang. Graphlime: Local interpretable model explanations for graph neural networks, 2020.
[18] Atsushi Kajii, Hiroyuki Kojima, and Takashi Ui. A refinement of the myerson value. IMS Preprint Series, 25, 2006.
[19] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv: 1609: (000002902, 2016.
[20] Wanyu Lin, Hao Lan, and Baochun Li. Generative causal explanations for graph neural networks.
In International Conference Machine Learning, pages 6666-6679, PMLR, 2021.
11

---

[21] Wanyu Lin, Hao Lan, Hao Wang, and Baochun Li. Orphiex: A causality latent variable model for interpreting graph neural networks. arXiv preprint arXiv:2203.15209 2022.
[22] Stan Lipovetsky and Michael Conklin. Analysis of regression game theory approach. Applied Stochastic Models in Business and Industry, 17(4):319-330 2001.
[23] Meng Liu, Youzhi Luo, Limei Wang, Yaochen Xie, Hao Yuan, Shurui Gui, Haiyang Yu, Zhao Xu, Jingtun Zhang. Yi Liu, Keqiang Yan, Haoran Liu, Cong Fu, Bora M Oztekin, Xuan Zhang, and Shuiwang Ji. DIG: A turnkey library for diving into graph deep learning research. Journal of Machine Learning Research, 22(240)::-9, 2021.
[24] Scott M Lundberg and Su-In Lec. A unified approach to interpreting model predictions. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems 30, pages 4765-4774. Curran Associates, Inc., 2017.
(25] Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang. Parameterized explainer for graph neural network. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 19620-19631. Curran Associates, Inc., 2020.
[26] Roger B Myerson. Graphs and cooperation in games. Mathematics of operations research, 2(3):225-229, 1977.
[27] Bezalel Peleg. On the reduced game property and its converse. International Journal of Game Theory, 15(3):187-200, 1986.
[28] Phillip E Pope, Soheil Kolouri, Mohammad Rostami, Charles E Martin, and Heiko Hoff- mann. Explainability methods for graph convolutional neural networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10772-10781, 2019.
[29] Aravind Sankar, Yozen Liu, Jun Yu, and Neil Shah. Graph neural networks for friend ranking in large-scale social platforms. In Proceedings of the Web Conference 2021, pages 2535-2546, 2021.
[30] Lloyd Shapley. A value fo n-person games. Ann. Math. Study28, Contributions to the Theory of Games, ed. by HW Kuhn, and AW Tucker, pages 307-317, 1953.
[31] Al Sobolev. Characterization of the principle of optimality for cooperative games through functional equations. Mathematical Methods in the Social Sciences, Vipusk, 6:92-151, 1975.
[32] Erik Štrumbelj and Igor Kononenko. Explaining prediction models and individual predictions with feature contributions. Knowledge and information systems, 41 (3):647-665, 2014.
[33] Xianfeng Tang, Yozen Liu, Xinran He, Suhang Wang, and Neil Shah. Friend story ranking with edge-contextual local graph convolutions. In Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining, pages 1007-1015, 2022.
[34] Xianfeng Tang, Yozen Liu, Neil Shah, Xiaolin Shi, Prasenjit Mitra, and Suhang Wang. Knowing your fate: Friendship, action and temporal explanations for user engagement prediction on social apps. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pages 2269-2279 2020.
[35] Lester G Telser. The usefulness of core theory in economics. Journal of Economic Perspectives, 8(2):151-16, 1994.
[36] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv:1110.11000: 2017.
[37] Minh Vu and My T. Thai. Pgm-explainer: Probabilistic graphical model explanations for graph neural networks. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 12225-12235. Curran Associates, Inc., 2020.
12

---

[38] Shiwen Wu, Fei Sun, Wentao Zhang, Xu Xie, and Bin Cui. Graph neural networks in recom- mender systems: survey. ACM Computing Surveys (CSUR), 2020.
[39] Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh Pappu, Karl Leswing, and Vijay Pande. Moleculenet: a benchmark for molecular machine learning. Chemical science, 9(2):513-553) 530, 2018.
[40] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv: S.l.:::811.0082666 2018
[41] Rex Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovee. Gnnexplainer: Generating explanations for graph neural networks. Advances in neural information processing systems, 32:9240, 2019.
[42] Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pages 974-983, 2018.
[43] Hao Yuan, Haiyang Yu, Shurui Gui, and Shuiwang Explainability in graph neural networks:
A taxonomic survey. arXiv preprint arXiv:2012.15445, 2020.
[44] Hao Yuan, Haiyang Yu, Jie Wang, Kang Li, and Shuiwang Ji. On explainability of graph neural networks via subgraph explorations. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 12241-12252. PMLR, 18-24 Jul 2021.
[45] Tong Zhao, Tianwen Jiang, Neil Shah, and Meng Jiang. A synergistic approach for graph anomaly detection with pattern mining and feature learning. IEEE Transactions on Neural Networks and Learning Systems, 2021.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [No]
(d) Have you read the ethics review guidelines and ensured that your paper conforms them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions of all theoretical results? [N/A]
(b) Did you include complete proofs of all theoretical results? [N/A]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (c.g., code, data, models) or curating/relcasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any assets either in the supplemental material URL? [No]
13

---

(d) Did you discuss whether and how consent was obtained from people whose data you' re using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "s1ak2Hr5_lq", "reviewer": "Reviewer_9p2U", "summary": "The paper proposes a structure aware scoring function, referred to as HN value, to explain decisions of a GNN for the task of graph and node classification. HN value originally proposed in reference [6] of the paper has its roots in cooperative game theory like Shapley values but unlike Shapley values, it is structure aware.  An algorithm called GStarx is proposed which computes HN values corresponding to nodes in a graph later presented as explanations. Higher the HN value higher the node importance. The superiority of the method is demonstrated via experiments in 6 graph classification datasets. ", "questions": "1. I am still wondering about the lack of feature importances in the explanation. For a graph we are given nodes, their features and the connections. The current paper address the problem of finding the most important nodes, which might be reasonable for the datasets used currently in the paper. But for real world datasets both for node and graph classification, node features may play an important role. How do or can we find feature importances together with node importances with the current methodology? \n\n2. Definition 4.2 is a bit confusing.  It seems like the condition |S/G|=1 will only be satisfied if the induced graph on nodes in S is a clique.  But intuitively, the first condition should correspond to graph induced on S to be a connected subgraph. The authors should elaborate on definition 4.2 a bit more and justify the choice even if it was originally proposed in [6]. The example given in lines starting from 180 is too simple as it only considers the case when |S|=1.\n\n3. In the GStarX algorithm, what is f^0_c^*?\n\n4. It is not clear if the obtained explanations are actually sparse as the importance scores are continuous. For example, a method can lead to a uniform importance score distribution over the nodes, i.e., all nodes are almost equally important. One should use entropy based metric for sparsity as proposed in https://arxiv.org/abs/2105.08621  to show that indeed the importance score distribution is not very uniform.\n\nOne minor question: What does HN stand for? I even looked up in the original paper [6], could not find the full form!", "limitations": "One of the main limitations of this work is that there is no direct way to compute feature importances while explaining a decision which might be very important in some real world datasets and applications. Consequently in presence of feature explanations more evaluation metrics might be required as one can just not simply remove a feature while computing fidelity/faithfullness as argued in https://arxiv.org/abs/2105.08621\n\nThe authors should explicitly acknowledge this limitation while still providing examples of application areas for example for text graphs or graphs with dense feature representations extracted using some unsupervised representation learning methods. In those cases, providing additional feature explanations might not be useful as the features themselves are not directly interpretable. \n", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The paper proposes a new scoring function based on cooperative game theory to find node importances.\n2. The paper is well written and structured. \n3. The overall study is carried out well with various concerns, regarding application to node classification, comparison to closely related work based on C-Shapely, at least addressed in the Appendix.\n\nWeaknesses:\n1. The proposed method can only be applied to find node importances ignoring the differing feature importances. Note that a GNN uses both node features and structure to make predictions. Some of the features might be more important than others towards a decision.\n2. There are a few clarifications required based on the current text which I also elaborate under Questions. \n\n\n\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "o0nWt3eJc0k", "reviewer": "Reviewer_Wfcz", "summary": "- This paper proposes a new GNN explanation method called Graph Structure-aware eXplanation (GStarX) based on HN value from the cooperative game theory, and claims it is able to leverage the critical graph structure information and improve the GNN explanation.\n-  This paper also tries to explain why and how this method is more effective compared with existing methods based on Shapley Value claimed to be non-structure-aware. \n- Experiments conducted on chemical graph property prediction and text graph sentiment classification are used to demonstrate that GStarX produces qualitatively more intuitive explanations, and quantitatively improves explanation fidelity\n", "questions": "- Why the fidelity is used as the only metric for evaluation? How about metrics such as AUC and accuracy used in some other GNN explanation papers?\n- Is the evaluation in Table 1 (with 8 different Sparsity) meaningful or fair?\n- Algorithm 1 illustrates the main framework of the paper, but it seems Algorithm 3 is equally important for better understanding. It may be more appropriate to include Algorithm 3 in the main body of the paper. \n", "limitations": "There is no potential negative societal impact of this paper.", "rating": 7, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- Strengths\n    - This paper is first to apply HN-Value (borrowed from game theory) to GNN explanation and illustrates its effectiveness. \n    - Compared with non-structure-aware GraphSVX, HN value utilizes graph structures to attribute cooperation surplus between neighbor nodes, so that node importance scores reflect not only the node feature importance, but also the structural roles.\n    - SubgraphX is also structure-aware for GNN explanation, but it has limitation of only generating one single connected subgraph as explanation. GStarX can overcome the issue by generating multiple disconnected subgraphs as explanation.\n- Weaknesses\n    - The paper does not clearly explain how Equation 6 and 7 are transformed into the form of matrix multiplication in Algorithm 3, and some necessary explanations are needed for better understanding.\n    - The paper claims that \"Connecting GNNs and the HN surplus allocation through the message passing lens\" and uses a molecule example shown in Figure 1 (c) to demonstrate  the connection between structure-aware HN value and the GNN message passing. A graph for sentiment classification in Figure 1(b) is used to qualitatively show that the structure-aware HN value can eliminate the inappropriate word coalition. But for better understanding, it seems there is lack of clear illustration using a unified explanation mechanism, which can naturally connecting these examples of message passing and elimination.\n    - The example in Figure 1 (b) is only qualitatively studied, and for consistency and better illustration, it should be included in section 5 with the detailed quantitative analysis.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "hEUVB0RVAjP", "reviewer": "Reviewer_ketX", "summary": "The explainability of GNNs is crucial for modeling graph data. This work is based on the HN value instead of the Shapley value to explain the GNNs, which involve the graph structure information.  ", "questions": "Please describe the original theoretical contribution of the paper.\n\n", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n\nThe proposed method is quite clearly defined. Most of the time, I enjoyed reading this paper because of its clear and concise introduction to the preliminaries of this work (including Shapley value and HN value). Considering graph structure information via HN value to explain the GNNs is reasonable. The experiments have demonstrated the effectiveness of the proposed GStarX algorithm. \n\nCons:\n\nOne limitation of the approach is its lack of technical originality. Although using the HN value is interesting and innovative on this issue, this paper did not provide any original theoretical analysis on the benefit of leveraging graph structure information via HN value to explain the GNNs. Meanwhile, for the examples in Figure 1, only comparing the basic Shapley method is not enough to demonstrate the advantages over other SOTA methods. And, for Figure 1 (b), it is hard to say whether the coalition {“not”, “good”} contributes negatively when using the GNNs to model two unconnected nodes: “good” and “not”.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept