FlowX: Towards Explainable Graph Neural Networks via Message Flows
Authors: Shurui Gui
Hao Yuan
Jie Wang
Qicheng Lao
Kang Li
Shuiwang Ji
Venue: ICLR 2022 Submitted (2022)
Keywords: Deep learning
Graph Neural Networks
Explainability

Abstract: We investigate the explainability of graph neural networks (GNNs) as a step towards elucidating their working mechanisms. While most current methods focus on explaining graph nodes, edges, or features, we argue that, as the inherent functional mechanism of GNNs, message flows are more natural for performing explainability. To this end, we propose a novel method here, known as FlowX, to explain GNNs by identifying important message flows. To quantify the importance of flows, we propose to employ the concept of Shapley values from cooperative game theory. To tackle the complexity of computing Shapley values, we propose an approximation scheme to compute Shapley values as initial assessments of flow importance. We then propose a learning algorithm to refine scores and improve explainability. Experimental studies on both synthetic and real-world datasets demonstrate that our proposed FlowX leads to improved explainability of GNNs.

Under review as a conference paper at ICLR 2022
FLOWX: TOWARDS EXPLAINABLE GRAPH NEURAL NETWORKS VIA MESSAGE FLOWS
Anonymous authors Paper under double-blind review
ABSTRACT
We investigate the explainability of graph neural networks (GNNs) as step towards elucidating their working mechanisms. While most current methods focus on explaining graph nodes, edges, or features, we argue that, as the inherent functional mechanism of GNNs, message flows are more natural for performing explainability. To this end, we propose a novel method here, known as FlowX, to explain GNNs by identifying important message flows. To quantify the importance of flows, we propose to follow the philosophy of Shapley values from cooperative game theory. To tackle the complexity of computing all coalitions' marginal contributions, we propose an approximation scheme to compute Shapley- values initial assessments of further redistribution training. We then propose learning algorithm to train flow scores and improve explainability. Experimental studies both synthetic and real-world datasets demonstrate that our proposed FlowX X leads to improved explainability of GNNs.
INTRODUCTION
With the advances of deep learning, graph neural networks (GNNs) are achieving promising per-
formance many graph tasks, including graph classification (Xu et al. 2019 Gao & Jil 2019
Chen et al. 2020). node classification (Kipf & Welling
2017
Velickoićć et al. 2018 Wu et al.
2019), and graph generation (Luo et al. 2202 You al. 2018 Many research efforts have been
made to develop advanced graph operations, such as graph message passing (Kipf & Welling 2017 Veličković al. 2018 Li al. 2019). graph pooling (Yuan & 2020 Zhang et al. [018]] Ying ct al. 2018)), and 3D graph operations (Schütt et al. [2017] | Klicpera et al. 2020). Deep graph models usuall ly consist of many layers of these operations stacked on top of each other interspersed with nonlinear functions. The resulting deep models are usually deep and highly nonlinear and complex. While these complex systems allow for accurate modeling, their decision mechanisms are highly elusive and not human-intelligible Given the increasing importance and demand for trustworthy and fair artificial intelligence, it is imperative to develop methods to open the black-box and explain these highly complex deep models. Driven by these needs, significant efforts have been made to investigate the explainability of deep models on images and texts. These methods are developed from
different perspectives, including studying the gradients of models (Simonyan al. 2013] Smilkoy
et al.
2017
Yang et al., (2019), mapping hidden features to input space (Zhou et al. 2016 Selvaraji ju
al.
2017 occluding different input features (Yuan al. [0200a] Dabkowski & Gal |017]] Chen
et al.
2018 9 and studying the meaning of hidden layers (Yuan et al. 2019 Olah et al. 2018 Du
al.
2018 etc. In contrast, the explainability of deep graph models is still less explored. Since
graph data contain limited locality information but have important structural information, it is usually not natural directly extend image or text based methods to graphs. Recently, several techniques have been proposed to explain GNNs, such as XGNN (Yuan et al. (020b)). GNNExplainer (Ying) et al. 2019), PGExxlainer (Luo al. 2020), and SubgraphX (Yuan et al. 202T). etc. These methods mainly focus explaining graph nodes, edges, features, or subgraphs.
In this work, we observe and argue that message flows are the inherent functional mechanism of GNNs and thus are more natural and intuitive for studying the explainability of GNNs. To this end, we propose a message flow based explanation method, known as FlowX, to explain GNNs. FlowX attributes GNN predictions message flows and studies the importance of different message flows. We first develop a systematic framework that lays the foundation on message flows for naturally explaining the message passing in GNNs. With our framework, the FlowX first quantifies

---

Under review as a conference paper at ICLR 2022
the importance of flows by following the phylosophy of Shapley values. Since message flows cannot be directly quantified to calculate marginal contributions, we propose an approximation scheme as the initial assessments of different flows. We then propose learning-bas bastng algorithm taking advantages from the initial assessments to capture important flows in predictions. We conduct extensive experiments on both synthetic and real-world datasets. Experimental results show that our proposed FlowX outperforms existing methods significantly and consistently. Both quantitative and qualitative studies demonstrate that our proposed FlowX leads improved explainability of GNNs.
RELATED WORK
2.1 GRAPH NEURAL NETWORKS
With the advances of deep learning, several graph neural network approaches have been proposed to solve graph tasks, including graph convolutional networks (GCNs) (Kipf & Welling 2017 7) graph
attention networks (GAT') (Veličković et al.) 2018), and graph isomorphism networks (GINs) (Xu et al. 2019), etc. They generally follow a message-passing framework to learn graph node features. Specifically, the new features of target node are Iearned by aggregating messages flows passed from its neighboring nodes. Without loss of generality, we consider the input graph as a directed graph with nodes and m edges. The graph denoted as = (V, E), where V {U1,..... .......,"1 Un denotes nodes, and E = {eih} represents edges in which eij is the directed edge v; vz. Then it can be represented by feature matrix X E Rgdx and an adjacency matrix A E Raxx, Each node i is associated with a dddimennional feature vector x; corresponding to the i-th column of X. The element oij in A represents the weight of eij, and dgj 0 indicates eij does not exist. For the t-th layer in GNNs, the message aggregation procedures can be mathematically written as a two-step computation
Aggregate: S* === =x=x x 'A',
(1)
Combine: X (S"),
(2)
X. where X E [Rd Xm denotes the node feature matrix computed by the t-th GNN layer and X Here M-) denotes the node feature transformation function at layer t and A' is the connectivity matrix at layer Note that we name the elements in A' as layer edges and ai. indicates the layer edge connecting node j and & in layer f. For example, in GCNs, the transformations are defined as a (W* and A' D- (A + I)D where W E Rd xde- is a trainable weight matrix, (-)) denotes the activation function, I is an identity matrix to add self-loops to the adjacency matrix, and D denotes the diagonal node degree matrix. We can stack 7 GNN layers on top of each other to form a T -layeer network, and the network function can be expressed as
f(g) = 9(M (MTT (X AA
When (() is graph classification model, g(-) generally consists of readout function, such as global mean pooling, and multi-layer perceptron (MLP) graph classifier. Meanwhile, when f() is a node classification model, g(-) represents MLP node classifier.
2.2 EXPLAINABILITY OF GRAPH NEURAL NETWORKS
major limitation of GNNs is their lack of explainability. Thus, different methods have been proposed to explain the predictions of GNNs, such as GraphLime (Huang et al. (020), GNNExplainer (Ying
ct al. 2019), PGExplainer (Luo al. 2020), PGMExplainer (Vu & Thail 2220).. SubgraphX (Yuan
et al. 202T) XGNN (Yuan et al. (020b). and GraphSVX (Duval & Malliaros (02T). These methods
can be mainly grouped into four categories based on the views of their explanations. First, several techniques provide explanations by identifying important nodes in the input graph. For example, GradCAM (Pope et al., (019)) measures node importance by combining the hidden features and gradients; LRP (Baldassarre & Azizpour 2019) and Excitation BP (Pope et al. 2019)) decompose the predictions into several terms and assign these terms to different nodes; HGGM-Explima (Vu & Thai 2020) builds a probabilistic graphical model by randomly perturbing the node features and employs an interpretable Bayesian network to generate explanations. Second, several existing methods, such GNNExplainer (Ying et al. 2019), PGExplainer (Luo et al. 2020), and GraphMask (Schlichtkruil
2

---

Under review as a conference paper at ICLR 2022
et al. 2021), explain GNNs by studying the importance of different graph edges. These methods follow a similar high-level idea that learns masks to identify important edges while maximizing the mutual information. Next, the recent study SubgraphX (Yuan et al. (021) proposes to explain GNNs via subgraphs. It incorporates the Monte Carlo tree search algorithm to explore subgraphs and employs Shapley values measure the importance. Finally, XGNN (uuan al. 2020b) focuses on model-level explanations, which can provide high-level insights and general understanding, It proposes generate graph patterns that can maximize certain model prediction. While those methods explain GNNs from different views, none of them can provide explanations in terms of message flows and we believe message flows are more natural for performing explainability.
To the best of our knowledge, GNN-LRP (Schnake et al. (2200) is the only algorithm that explains GNNs by relevant walks. The relevant walk is defined as a T-length ordered edge sequence that corresponds to a Tteepp directed path on the input graph. To study walk explainability, GNN-LRP considers the GNN prediction as function and decomposes it using higher-order Taylor expansions to distribute prediction scores to relevant walks. Specifically, by using 7'-order Taylor expansion with a proper root, each term in the Taylor expansion corresponds to a relevant walk and regarded as proposed FlowX shares similar explanation target, i.e., flow/walk,
the importance score. While with GNN-LRP, our method fundamentally different. The GNN-LRP is developed based on score decomposition while our method follows the phylosopy of Shapley values from cooperative game theory as initial assessments and proposes a learning-basee algorithm for the score generation. In addition, GNN-LRP has several constraints on the activation function and bias term used in GNNs while our method can be applied to general GNN models. Furthermore, as the GNN-LRP follows the Gradient Input scheme, may not pass the model parameter randomization test and may not be sensitive to model parameters (Adebayo et al. 2018).
Differences with Other Methods Using Shapley Values: Shapley values are commonly used in explaining machine learning methods. In particular, a recent study proposes a surrogate method, known as GraphSVX (Duval & Malliaros 202T), to explain GNNs with both node and feature masks. Another recent study proposes SubgraphX X (Yuan et al. (021), which employs a search algorithm to explore and identify subgraphs with high Shapley scores. While these methods use Shapley values, there are several fundamental differences. First, proposed method focuses explaining message flows, which are the most basic and natural units for explanations as GNNs are based on message passing schemes. Second, only use Shapley-like values initial approximations to facilitating further training. Experiments show that the learning step is very important. Furthermore, the fundamental difference with GraphSVX is reflected in the fact that, while our method is perturbation-bast based method, GraphSVX is surrogate method (Yuan et al. 2020c). Due to these differences, we show in experiments that our FlowX achieves more natural and improved performance as compared with other methods.
THE PROPOSED FLOWX
While existing methods mainly focus explaining GNNs with graph nodes, edges, subgraphs, we propose to study the explainability of GNNs from the view of message flows. We argue that message flows are the fundamental building blocks of GNNs and it is natural to study their contributions towards GNN predictions. With our message flow framework, we propose a novel method, known as FlowX, to investigate the importance of different message flows. Specifically, we follow the phylosophy of Shapley values (Kuhn & Tucker 1953) from game theory and propose an marginal contribution approximation scheme for them. In addition, learning- -aased algorithm is proposed to improve the explainability of message flows.
3.1 MESSAGE FLOW VIEW OF GNNS
We consider deep graph model with T' GNN layers. Each GNN layer aggregates 1-hop neighboring information to learn new node embeddings. Hence, for any node, the outgoing messages are transmitted within its T-hop neighbors. Then the outputs of GNNs be regarded as function of such transmitted T Ttsepp messages, which are named as message flows in this work. Formally, we introduce the concept of message flows and message carriers follow:
3

---

Under review as a conference paper at ICLR 2022
Definition 1: Message Carrier. We use the connectivity matrix to represent the carriers for message flows. Given the connectivity matrix A at layer i, the layer edge äl represents the message carrier with which the message passes from node e2 to By at layer t.
Note that use the superscript t to distinguish the message carriers in different layers since their corresponding message flows are different. Then the set of all message carriers, i.e., all layer edges, is defined as A {.... "ū Puv
Guue ... and |A| [E] x T.
Definition 2: Message Flow. In a T-aayer GNN model, we use Fisk...em to denote the message flow that starts from node 2 in the input layer, and sequentially passes the message to node vy, M..--. Ug until to node Um in the final layer T", The corresponding message carriers can be represented as {āty Sk:.... ................ }.
In T-layer GNN model, all message flows start from the input layer and end with the final layer so that their lengths equal to T. For the ease of notations, we introduce the wildeard * to represent any valid node sequence and F denote the message flow set. For example, we can use Fij. Falms and Fijetm denote the message flow sets that share the same message carrier aly. a?m- or both of them, respectively. In addition, we employ another wildcard ? denote any single node and ? ?(1) to represent any valid node sequence with nodes. For example, Fr{3 means the set of valid 2-step message flow with 3 nodes. Note that the following property of message flow sets also holds:
Fij-lm Fije F=
(3)
The final embeddings of node Um are determined by all incoming message flows to node Umm which can be denoted as F.m. Since the output of the GNN model is obtained based on the final node embeddings, then it is reasonable to treat the GNN output as the combinations of different message flows. Hence, it is natural to demystify GNN models by studying the importance of different message flows towards GNN predictions.
3.2 SAMPLING MARGINAL CONTRIBUTIONS AS INITIAL ASSESSMENTS
While explaining GNNs with message flows seems to be promising, it is still crucial to properly measure the importance of those message flows. Hence, in this work, our Flow proposes to follow the philosophy of Shapley value (Kuhn & Tucker 1953) to use the marginal contributions in different flow sets as the initial assessments flow importance. is noteworthy that our initial assessments are not computing real Shapley values. Shapley value is solution concept in cooperative game theory and used to fairly assign the game gain to different players. When considering marginal contributions in GNN explanation tasks, score as the total game gain. Formally, given the trained GNN model f(() and the input graph G, we use F. to denote the set of all valid flows, i.e., all players in the game. Then given any flow Fk mathematically define the contribution of as
treat the message flows as different players and the GNN prediction
6(Fh=
Σ W(PDD(f (P -FP)) PEF.(FF)
where ((IP)) is a weight function assigned to each term in the summation; denotes the possible coalition group of players, and o(-) denotes the flow score. Here I (PU(FF) S(P) is the marginal contribution of flow Fkt for a particular coalition group, which can be computed by the prediction difference between combining Fk with the coalition group P and only using P. Note that
Eq. is equivalent to the classic Shapley value when W(IP)) |P|( |-11__1-1 where | is the
F.
set size. To compute the flow score ((Fk), we need to enumerate all possible coalition groups and considers different interactions among players. However, it time-consuming to consider all possible coalition; thus, sample several marginal contributions to approximate the final flow score. Note that it is not possible to compute importance score with Eq. 44) for message flows since we cannot remove individual message flows from the GNN model and the finest component we directly remove is the layer edge. For example, when removing the layer edge ā.j. the whole flow set F.j. is removed from the model. In addition, enumerating all possible coalition groups is time-consuming when the input graph is large-scale and the GNN model is deep. Hence, in our Flow we propose an approximation scheme to compute Eq. based on Monte Carlo (MC) sampling (Strumbelj & Kononenko 2014).
4

---

Under review as a conference paper at ICLR 2022
1" iteration
2 iteration
1
Flows
112
1/2
4
Figure 1: An illustration of our initial assessments via sampling marginal contributions. For each MC sampling step, we iteratively remove one layer edge until all layer edges are removed. In this example, the removed layer edges are shown in bold and purple lines while the corresponding message flows are shown in arrow lines. For example, in the first iteration, we remove the layer edge between oi and 2/2 from the first GNN layer and compute the marginal contribution. Then three message flows are removed and the contribution scores are averaged and assigned to these three message flows.
Algorithm 1 INITIAL APPROXIMATIONS OF FLOW IMPORTANCE SCORES.
1: Given trained GNN model f(.) and an input graph, the set of all layer edges is represented as A. For each message flow FK two |A| -iimenssio vectors S(F*) and C(F*) denote its importance scores and removing index counts respectively. In addition, A denotes the set of removed layer edges and F is the set of removed message flows.
2: Initialize S.) and C(-) as zeros for all message flows.
3: for step from to Monte Carlo sampling step M do
4: Initialize the removed sets empty that A and F = 0.
5: Randomly shuffle and permute the layer edge set A, denoted as Ar(i).
6: for j from to |A| do
7: Select the j-th layer edge in Ax(i). denoted as atm-
Block the layer edge at in GNN model f(-). then the removed flows are E1
8:
F((t (t-- ((t-1))m((TT)) (F ((((())))))((--)))
9:
Compute the prediction difference that 8j = f(A) A) f(A) (Āu (A Update Ā = Au ât and f = F
10:
11:
Compute averaged score that 5y = 83/12 FF)
12:
for each flow 5k in Fi do
13:
Update S(F*) = ((F*)(()))))))))))))))) + sy.
14:
Update C(F+) = C(F)) +1
15:
end for end for
16:
end for
18: For each message flow Fk, compute our marginal contribution vector S(F)) = //FF))/C(F))
Formally, let M denote the total number of MC sampling steps. For the i-th sampling step, we use T(i) to represent random permutation of |A| E x T elements. Then the set of all layer edge A is permuted based on (i). denoted as AA(ii) that ( = ([]()) In each step i, we iteratively remove one layer edge from An(s) following the order, and compute the marginal contribution. An
illustration of our proposed sampling algorithm is shown in Figure ] We use A to denote the set of removed layer edges and FF to denote the set of removed message flows, which are initialized as Ā Ā= 0 and F = 0 in the beginning of each MC sampling step. For the iteration in sampling step i, the j-th element of An(s) is removed and we assume the removed layer edge is atm- Then the computation operations can be mathematically written
8j = ((A A) f(A) atm))
(5)
Ā = Au (attm)
(6)
F) 1100-1)mm7(T-)
F
F = F FF 116m
(8)
5

---

Under review as a conference paper at ICLR 2022
where Fi denotes the removed message flows in iteration by removing a Note that it is not equivalent to F: since the flows in previous iterations. Then the score is averaged that 5j - sj/ | and we assign 8j each flow in F.. By repeating such operations until all layer edges are removed, we can obtain |A] marginal scores and assign them to the corresponding flows. Note that the order information in Ax(i) is important since in the earlier iterations, the removed flows F are interacting with larger coalition group A \ (Á U dmm) and in the later iterations the coalition groups are small. Altogether, the steps of our marginal contribution sampling are shown Algorithm |
may be already removed in the
After M MC sampling steps, our method explores M permutations of layer edge set and each flow is sampled to obtain M marginal contributions. For each flow Fkk we use a |Al-dimensional vector to store its marginal contributions, denoted as S(F*), where [[j is the importance score obtained when F= is removed in the iteration j. If the flow is removed mutiple times in the iteration j for different MC sampling steps, the scores averaged, which also means scores obtained from coalitions with same sizes are weighed equally. Then it raises the question that how to convert S(F)) to the final importance score of F The final importance score will be a Shapley value approximation if we simply compute the summation of the elements in 5(F)). While Shapley values promising, the approximations may not be accurate since M is always set as M << |A]! for the sake of computation efficiency. Moreover, the importance of the early iterations when more layer edges exist in the model should be different to the importance of later iterations when only few layer edges exist in diverse situations. Hence, directly computing the summation of the scores in ((F)) may not be suitable.
3.3 LEARNING IMPORTANCE SCORES
With our obtained score vectors S(F)), we propose to regard these values initial assessments of flow importance and learn an associated importance scores with designed redistribution trick. We target to learn weights for combining the elements in S(F)) to obtain the final importance score for each flow, which means to learn W(P) in Eq. 4
Formally, given the input graph and GNN model f()), we obtain marginal contribution vector S(FR) for each message flow. Then the only trainable weight vector w is initialized to all equal to 0.5 with random noise, which shares the same dimension of [S(F))], ]. Note that the weights are shared among all message flows in the same graph. Then S(F)) can be combined via a dot product with w. Next, the flow importance is converted to layer edge importance by simply summing up the scores of all flows sharing a particular layer edge as the message carrier. Mathematically, it can be written as
s(F+) = S(F") w
WF* E F.
(9)
s ((d)))= = Σ s(F)
(10)
FiEF
where s(-) denotes the importance score for layer edges and flows; F = F:ttt-1)a (T---- Then based on s(at,), we can obtain a mask indicating the importance of different layer edges, denoted as M:
M = g(3).
(1I)
where & denotes all layer edges' importance scores. 9(-) is defined as exponential redistribution operation that including an input normalization, an element-wise exponential scaling (x) = x" (r
is hyper-parameter), and an output normalization. We provide more intuitions in Appendix A.3
Note that the mask is normalized so that each element is in the range [0. 1]. By applying the mask to layer edges, important layer edges are restricted and the model prediction becomes
i = [(Combine -M)),
(12)
where is the prediction vector and Combine - .M) means layer edges masked out based on the values of M. Intuitively, if important layer edges are restricted, then the prediction should change significantly. Hence, ý is encouraged to be different from the original prediction by learning proper

---

Under review as a conference paper at ICLR 2022
weights Specifically, employ the negative cross-entropy loss that can be formally expressed as
m ((9 - Σ 1 = c} log
(13)
where y is scalar representing the predicted class of the original graph 9, m is the number of classes, [ denotes the indicator function, and U. is the new predicted probability for class c. After training, the final importance scores for different flows can be obtained via Eq. (9)
EXPERIMENTAL STUDIES
4.1 DATASETS AND EXPERIMENTAL SETTINGS
Datasets. We employ seven different datasets to demonstrate the effectiveness of our proposed
FlowX with both quantitative studies and qualitative visualization results. These datasets are BA- Shapes Ying et al. 20199) BA-LRP (Schnake et al. 22020). ClinTox (Wu et al. (0188). Tox21 (Wu et al. 2018). BBBP (Wu al. 2018). BACE (Wu al. 2018). BA-INFE, and Graph-SST2 (Yuan et al. 2020ch. which include both synthetic and real-world data. First, BA-Shapes is cadecclassificationn synthetic dataset that is built by attaching house-like motifs to the base Barabási-Alber graph where the node labels are determined by their own identifies and localizations in motif's Then, BA-LRP is a graph-classifiction synthetic dataset that includes Barabási-Albert graphs and the two classes node-degree concentrated graph and evenly graph. Next, ClinTox, Tox21, BBBP, and BACE are real-world molecule datasets for graph classification. The chemical molecule graphs in these datasets labeled according to their chemical properties, such whether the molecule can penetrate blood-brain barrier. Finally, Graph-SST2 is a natural language sentimental analysis dataset that converts text data graphs. These graphs are labeled by their sentiment meanings. Note that the BA-INFE dataset is a synthetic dataset for Accuracy comparisons and the results are reported in the appendix. We also report the properties and statisties of these datasets in Appendix B Table
GNN Models. In our experiments, we consider GCNs (Kipf & Welling 2017) and GINs (Xu et al., 2019) as our graph models for all datasets. We adopt 2-layer GNNs for node classification and 3-layer GNNs for graph classification. The graph models are trained to achieve competitive performance and
the details are reported in Table 2
Baselines. With the trained graph models, we quantitatively and qualitatively compare our FlowX with eight baselines, including GradCAM (Pope et al., 2019). DeepLIFT (Shrikumar al. (017).
GNNExplainer (Ying et al. 2019), PGExplainer (Luo al.) 2020), PGMExplainer (Vu & Thai 2020
SubgraphX (Yuan et al. 2021). GNN-GI (Schnake et al. 2020). GNN-LRP (Schnake et al. 2020
Note that since these methods cannot be directly compared, we set the explanation target to graph edges for fair comparisons that the explanations are converted to edge importance scores if needed. More implementation details about explanation methods setting and GNN models can be found in the supplementary material. We used the datasets and implementations of the comparing algorithms in the DIG library (Liu et al. 2021). We will release our code after the anonymous review period.
4.2 QUANTITATIVE STUDIES
We first quantitatively compare different explanation methods. We follow the existing studies Yuaan ee al. 2020c Pope et al. 2019) and employ two metrics to evaluate the explanations: Fidelity and Sparsity Good explanations should be faithful the model and capture the discriminative features for the predictions. When such input features are removed, the original predictions should change significantly. The Fidelity score measures the change of predicted probabilities when removing important input features identified by different explanation methods. Higher Fidelity scores indicate the removed features are more important to the predictions and hence the explanations are more faithful to the model. In addition, the other desired property of explanations is sparsity. To encourage the explanations to be more buman-intelligible, they should contain fewer but more important features. Hence, we also employ the Sparsity metric which measures the percentage of input features that are identified as important. Higher Sparsity scores indicate that fewer features are identified as important in the explnattions. The formulations and details of these metrics discussed in the appendix C
7

---

Under review as a conference paper at ICLR 2022
pe-Shapes (GIN)
BA-LRP (GIN)
Tox21 1 (GIN)
Clin Tox (GIN)
0.50
0.25
0.60
0.40
0.20
Fidelity
Fidesity
0.30
Fidelity
0.15
Fidelity
0.40
0.40
0.10
0.20
0.20
0.05
0.00
0.7
0.5
0,7
0.9
0.6
0.8
0.7 Sparsity
0.9
Sparsity
Sparsity
BBBP (GIN)
BACE (GIN)
Graph (GIN)
0.50
0.40
-2-- GradCAM
0.40
0.60
DeepLIPT
FieeRt
0.30
Fidelity
0.30
-Ou PSExplainer
0.- GNNExolainer
0.40
PGMMxxpiiner
0.20
SubgraphX
0.10
0.10
GNN-CI
CNN-LAP
0.00
0.5
0.6
0.7 Sparsity
0.8
0.9
0.5
0.6
0.7 Sparsity
0.8
0.5
0.5
0.6
0.7 Sparsity
0.8
0.9
Figure 2: Comparison of Fidelity values by nine methods on seven datasets with GINs under different Sparsity levels.
Table I: Results of ablation studies of our method on GCNs. FlowX' denotes our FlowX without Shapley initial assessments and FlowX" denotes FlowX without learning refinement.
Sh-Shs
BA-LRP
CliaTox
Tox21
BBBP
BACE
Graph-SST2
FlowX
0.40+0.03
0.1740.10
0.3420.08
0.1720.05
0.3940.17
0.32+0.06
0.22+0.09
#
0.4140.00
0.52+0.00
0.32+0.07
0.1920.04
0.4920.11
0.50+0.06
0.2620.11
FlowX 0.42+0.01
0.51+0.01
0.38=0.06
0.22+0.04
0.57=0.11
0.51+0.03
0.32=0.13
It is noteworthy that these metrics highly correlated since the predictions tend to change more when more input features are removed. Then explanations with higher Sparsity scores tend to have lower Fidelity scores. Hence, we argue that the Fidelity scores need be compared under similar Sparsity level. Specifically, we control the Sparsity scores of explanations and compare the corresponding Fidelity scores. For each dataset, we randomly select 100 samples and conduct such quantitative evaluations. The results are reported in Figure 2 where we show the plots of Fidelity scores with respect to different Sparsity levels. Obviously, FlowX performs better on all of the real-world datasets that FlowX consistently achieves higher Fidelity across all Sparsity levels. Meanwhile, the results on synthetic datasets are competitive when the Sparsity is low and our FlowX still performs significantly better with high Sparsity levels. Note that method is shown to achieve stable performance on different datasets and GNN models, which is promising for the applications and generalizations of FlowX. Meanwhile, our proposed method, GNN-LRP, and GNN-GI perform better than the other methods, which indicates the superiority of the methods based on flows and walks. Note that GNN-LRP achieves good results on synthetic datasets but surprisingly, it is not better than GNN-GI on real-world datasets. In addition, PGExplainer only obtains competitive results on simple synthetic datasets but not on complex real- wolldorld datasets. Note that, for SubgraphX. its subgraph explanations are not directly comparable so we convert its subgraph explanations to edge explanations. It performs well on the BA-IRP and BBBP datasets but not as expected on the other datasets. We believe the reason may be that such converting destroys the continuousness and completeness of its subgraph explanations. Last but not least, we wish to mention that the comparisons using edge actually limit the performance of the fowebased methods due to explanation granularity changes. More results and time comparisons are also reported in the appendix.
4.3 ABLATION STUDIES
To demonstrate the effectiveness of our proposed learning- based algorithm in Section 3.3 study the performance when only using the average of our Shapley initial assessments as the importance scores without further learning, denoted FlowX*. In addition, to show the Shapley initial assessments
8

---

Under review as a conference paper at ICLR 2022
DeepLIFT
GmdCAM Fidelity: 0.1427
GNNExplainer Fidelity: 0.2957
Fidelity: 0,2550
2
GNN-GI
GNN-LRP
FlowX
Fidelity: 0.1970
Fidelity: 0.2216
Fidelity: 0.5416
Sample explanation results of different methods. Note that explanations are shown as directed edges (highlighted red arrow lines) and self-loops (red circles around atoms). In addition, motifs are emphasized by dashed circles and numbered from I to 5.
Figure 3:
necessary, study the method only using the learning algorithm with randomly initialized scores for different flows, denoted as F We compare our Flow with these two baselines on GCN models, and the results are reported in Table Obviously, for all datasets, the FlowX and FlowX* outperform FlowX significantly, showing that the Shapley initial assessments are appropriate and necessary. In addition, for synthetic datasets, the FlowX and FlowX" show competitive performance, which indicates our initial assessments can obtain reasonable results for simple models and datasets. However, FlowX obtains significantly better performance on complex real-world datasets than FlowX*, showing the effectiveness of our proposed learning-basse algorithm. More experimental details will be attached in the supplementary material.
4.4 VISUALIZATION OF EXPLANATION RESULTS
Finally, report the visualization results of different explanation methods in Figure 3 Specifically, we show the explanations of molecule graph from Clin'Tox dataset. The smiles string of this input graph is (CCCCCCPPCCCEOOI--))I----C--
and the model to be explained is 3-layer GCN model. In this input graph, motifs I and 2 form a Carboxylate Anion; motif 4 and 5 both contain an Ammoniumyl while motif 3 corresponds motifs in the explanation and obtains the highest Fidelity score. It indicates that those motifs are indeed important for the model make predictions. In addition, we can conclude that the model combines these motifs for the predictions since we generally observe that explanations with more motifs chosen tend have higher Fidelity scores. Furthermore, we find that DeepLIFT identifies all motifs but focuses more on the self-loops of atoms. However, its Fidelity score is much lower than GNNExplainer who only identifies four motifs but focuses on the information transmissions between atoms. Hence, we believe the interactions among different atoms contribute more to the model predictions, which further indicates the Shapley value a promising solution for studying the explainability of GNN models. More visualization results reported in the supplementary material.
CF2 group. It is clear that our FlowX finds all
CONCLUSIONS
We study the explainability of deep graph models, which are generally treated as black-boxes. From the inherent functional mechanism of GNNs, we propose FlowX to explain GNNs by studying message flows. Our FlowX first computes Shapley values approximations as initial assessment and then incorporates a learning refinement. Extensive experiments demonstrate our FlowX achieves significantly improved explanations.

---

Under review as a conference paper at ICLR 2022
REPRODUCIBILITY STATEMENT
Several efforts are made to ensure the reproducibility of our work. To demonstrate the details of
proposed algorithm, we provide the rigorous description of our approach's first stage in Algorithm [
the second stage learning process in Subsection 3.3 and the concrete setting in appendix [34 For
experiments, besides the detailed description of datasets and evaluation metrics in Section we
provide model configurations, training details, target mapping, and metrics details in appendix B and
appendix C
Our implementations will be publicly available once the paper is published.
REFERENCES
Julius Adebayo, Justin Gilmer, Michael Muelly, Ian Goodfellow, Moritz Hardt, and Been Kim. Sanity checks for saliency maps. Advances in Neural Information Processing Systems, 31:9505-9515, 2018.
Federico Baldassarre and Hossein Azizpour. Explainability techniques for graph convolutional networks. arXiv preprint arXiv: 1905. 13686, 2019.
Jianbo Chen, Le Song, Martin Wainwright, and Michael Jordan. Learning explain: An information- theoretic perspective on model interpretation. In International Conference on Machine Learning, pp. 883 892. PMLR, 2018.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International Conference on Machine Learning, pp. 1725-1735. PMLR, 2020.
Piotr Dabkowski and Yarin Gal. Real time image saliency for black box classifiers. In Advances in Neural Information Processing Systems, pp. 6967-6976, 2017.
Mengnan Du, Ninghao Liu, Qingquan Song. and Xia Hu. Towards explanation of dnn-based prediction with guided feature inversion. In Proceedings of the 24th ACM SIGKDD International Conference Knowledge Discovery Data Mining, pp. 1358-1367, 2018.
Alexandre Duval and Fragkiskos D Malliaros. Graphsvx: Shapley value explanations for graph neural networks. arXiv preprint arXiv:2104.100 10482, 2021.
Hongyang Gao and Shuiwang Ji. Graph U-Nets. In Proceedings of the 36th International Conference on Machine Learning. pp. 2083-2092, 2019.
Qiang Huang, Makoto Yamada, Yuan Tian, Dinesh Singh, Dawei Yin, and Yi Chang. Graphlime: Lo- cal interpretable model explanations for graph neural networks, arXiv preprint a7Xiv:2001.06216. 2020.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017.
Johannes Klicpera, Janck Groß, and Stephan Günnemann. Directional message passing for molecular graphs. arXiv preprint arXiv:2003.03/23 2020.
Harold William Kuhn and Albert William Tucker. Contributions to the Theory of Games, volume Princeton University Press, 1953.
Guohao Li, Matthias Muller, Ali Thabet, and Bernard Ghanem. Deepgens: Can gens go as deep as cnns? Proceedings of the IEEE/CVF International Conference on Computer Vision, pp- 9267-9276 2019.
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 Oztekin, Xuan Zhang, and Shuiwang Ji. DIG: A turnkey library for diving into graph deep learning research. arXiv preprint arXiv:2103.1 / 12608, 2021.
10

---

Under review as a conference paper at ICLR 2022
Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang. Parameterized explainer for graph neural network. Advances in Neural Information Processing Systems, 33, 2020.
Youzhi Luo, Keqiang Yan, and Shuiwang Ji. GraphDF: A discrete flow model for molecular graph generation. Proceedings of The 38th International Conference on Machine Learning, 2021.
Chris Olah, Arvind Satyanarayan, Ian Johnson, Shan Carter, Ludwig Schubert, Katherine Ye, and Alexander Mordvintsev. The building blocks of interpretability. Distill, 2018. doi: undefined. httpss//diitill.ub///0 Shbuilding-blckkss
Phillip Pope, Soheil Kolouri, Mohammad Rostami, Charles Martin, and Heiko Hoffmann. Explainability methods for graph convolutional neural networks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 10772-10781, 2019.
Michael Sejr Schlichtkrull, Nicola De Cao, and Ivan Titov. Interpreting graph neural networks for nlp with differentiable edge masking. 2021.
Thomas Schnake, Oliver Eberle, Jonas Lederer, Shinichi Nakajima, Kristof T. Schütt, Klaus-Robert Müller, and Grégoire Montavon. Higher-order explanations of graph neural networks via relevant walks, 2020.
Kristof T Schütt, Pieter-Jan Kindermans, Huziel E Sauceda, Stefan Chmicla, Alexandre Tkatchenko, and Klaus-Rohert Müller. Schnet: A continuous-fitte convolutional neural network for modeling quantum interactions. arXiv preprint arXiv:/706.00566, 2017.
Ramprasaath R Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra. Grad-cam: Visual explanations from deep networks via gradient-basee localiza- tion. In 2017 IEEE International Conference on Computer Vision (ICCV), pp. 618-626. IEEE, 2017.
Avanti Shrikumar, Peyton Greenside, and Anshul Kundaje. Learning important features through propagating activation differences. 2017.
Karen Simonyan, Andrea Vedaldi, and Andrew Zisserman. Deep inside convolutional networks: Visualising image classification models and saliency maps. arXiv preprint arXiv:13/2.6600 13/2.6034, 2013.
Daniel Smilkov, Nikhil Thorat, Been Kim, Fernanda Viégas, and Martin Wattenberg. Smoothgrad: removing noise by adding noise. arXiv preprint 1Xxx:1706.00822 2017.
Erik Strumbelj and Igor Kononenko. Explaining prediction models and individual predictions with feature contributions. Knowledge and information systems, 41(3):647-666 2014.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua
Bengio. Graph Attention Networks. International Conference on Learning Representations, 2018
URL httph::p////m /estps://opeereevee http://ppeeeeeiieeee net/ forum iid accepted poster.
Minh N Vu and My T Thai. Pgm-explainer: Probabilistic graphical model explanations for graph neural networks. 2020.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Sim- plifying graph convolutional networks. In International conference on machine learning, pp. 6861-6871. PMLR, 2019.
Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh Pappu, Karl Leswing, and Vijay Pande. Moleculenet: benchmark for molecular machine learning. Chemical science, 9()::133-330 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? In International Conference on Learning Representations, 2019. URL https /oopenevviww..o .nt/ rote://ommmmmdddyy6105333
Fan Yang, Shiva K Pentyala, Sina Mohseni, Mengnan Du, Hao Yuan, Rhema Linder, Eric D Ragan, Shuiwang Ji, and Xia Hu. Xfake: explainable fake news detector with visualizations. In The World Wide Weh Conference, pp. 3600-3604, 2019.

---

Under review as a conference paper at ICLR 2022
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. In Advances in Neural Information Processing Systems, pp. 4800-4810, 2018.
Zhitao Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gnnexplainer: Generating explanations for graph neural networks. In Advances in neural information processing systems. pp. 9244-99222 92559255,2222 2019.
Jiaxuan You, Bowen Liu, Rex Ying. Vijay Pande, and Jure Leskovec. Graph convolutional policy network for goal-directed molecular graph generation. In Proceedings of the 32nd International Conference on Neural Information Prucessing Systems, pp. 6412-6422, 2018.
Hao Yuan and Shuiwang Ji. StructPool: Structured graph pooling via conditional random fields. In Proceedings of the 8th International Conference Learning Representations, 2020.
Hao Yuan, Yongjun Chen, Xia Hu, and Shuiwang Ji. Interpreting deep models for text analysis via optimization and regularization methods. In AAAI-19: Thirty-Third AAAI Conference on Artificial Intelligence. Association for the Advancement of Artificial Intelligence, 2019.
Hao Yuan, Lei Cai, Xia Hu, Wang, and Shuiwang Interpreting image classifiers by generating discrete masks. IEEE Transactions Pattern Analysis and Machine Intelligence, 2020a.
Hao Yuan, Jiliang Tang, Xia Hu, and Shuiwang Ji. XGNN: Towards model-level explanations of graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 430-438, 2020b.
Hao Yuan, Haiyang Yu, Shurui Gui, and Shuiwang Ji. Explainability in graph neural networks: taxonomic survey. arXiv preprint arXiv:2012.15445 2020c.
Hao Yuan, Haiyang Yu, Jie Wang, Kang Li, and Shuiwang Ji. On explainability of graph neural networks via subgraph explorations. arXiv preprint 15X 2021.
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In AAAI, volume 18, pp. 4438 3348,444,,1 2018.
Bolei Zhou, Aditya Khosla, Agata Lapedriza. Aude Oliva, and Antonio Torralba. Learning deep features for discriminative localization. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 2921-2929, 2016.
12

---

Under review as a conference paper at ICLR 2022
A ALGORITHM ANALYSIS & INTUITIONS
A.1 MESSAGE FLOW INTUITION
Message flows can provide multi-hop dependence association, i.e., the reason of a given node why is labeled as susceptible will be explained by message flow beginning from an affected node to the given node in a virus infection dataset. Therefore, the explanation is that the message flow transmits the affection information from the affected node to the given node making it susceptible one. The upper figures of Figure. show that how a node's 's message can be transmitted from the node to which node across which path.
A.2 COMPLEXITY ANALYSIS
Message flows. Considering the total number of message flows |F its loose upper bound is |F| = O(EE)²) With the consideration of connectivity, given the largest outgoing degree of nodes in the graph d4, the tighter upper bound of the number of message flows is |F| = ((E((d))))))
Marginal contribution sampling. It is noticeable that the deep model's forward operations are the most time-consuming operations, denoted as O(Ty). Without any parallel consideration, the time complexity of marginal contribution sampling is Tice = -(M]A When we consider parallel implementations, the most simple improvement is to use the GPUs acceleration to move line 9-15 out of the two loops and to make line 8 executed in ((1), which leads to the time complexity Timex = O AA| + TT)) ). The space complexity should be considered because there is big flow score matrix Sepn = (M Fl). As for the graphic memory requirement, this parallel implementation consumes Sppu = O(M S where O(S,) = O + |T )dT'+ + +Sp) is the deep model memory denotes the number of nodes; Sp is the model's parameter memory complexity. In our implementation, there is a trade-off that we only parallelly calculate the model outside the innermost loop, so that our time complexity is Ties O(M( + TTy) and the space complexity of GPUs is Sppa = (())))))
complexity; here, IV|
A.3 TRAINING DILEMMA & EXPONENTIAL REDISTRIBUTION
We observe that the training is challenging as it often even leads to a worse result after training. The difficulty comes from that the training target is unusual. We not only require the important layer edges" scores to be trained to be their high- value local optimums with correct rankings but also require that all of the unimportant ones, not including those negative contribution elements, are trained to be low values because of the ranking requirement. The problem is that because the unimportant layer edges exert nearly no impact on the model results, their scores are trained to be the values that are largely random, which causes an unimportant layer edge's score may be larger than an important one because it is random (it may be arbitrary high or low). This is not what we expected. In brief, these random scores severely interfere with the ranking of scores of the important. Therefore, exponential redistribution is designed to solve this problem as shown in Eq. the gradients of the exponential scaling g (x) = x" decide that the high scores trained while the low scores are likely to be trapped in a low-value zone with gradients closed to zeros. Intuitively, considering the simplest 2-order exponential scaling g (x) x² = x x. this function can be regarded as using x as an attention map to mask itself so that high scores become easier to train while it is contrary to the low scores. It is noticeable that the use of exponential redistribution requires a relatively reasonable initialization, in order to give important elements lower possibility to be initialized into the low-value zone, which leads to longer training time. Hence, we initialize scores according to the marginal contribution results we obtain from the last stage so that unimportant factors are set into the low-value zone and will be likely to be trapped there having no interference to the high score ranking, while important layer edges are normally trained. Note that the final scores are not refined Shapley values, because the Shapley-like initialization only serves as heuristic values for the starting of exponential redistribution. Worth mentioning that the use of regularization terms like the size of masks and the information entropy does not work, and the use of Gumbel softmax for encouraging discreteness is useless either because both of them cannot solve the real problem.
where be sensitively
13

---

Under review as a conference paper at ICLR 2022
Table 2: Statistics and properties of seven datasets. Note that denotss node classification, and "GC" denotes graph classification. nodes (largest) denotes the number of nodes of the largest graph in the dataset for the split of explanations.
Datasets
Task
graph
# nodes (largest)
GCN Accuracy
GIN Accuracy
BA-Shapes
Synthetic/NC
700
90.29%
89.57%
BA-LRP
Synthetic/GC
20000
20
97.95%
100%
BA-INFE
Synthetic/GC
2000
39
99.00%
99.50%
Clintox
Real/GC
1478
136
93.96%
93.96%
Tox21
Real/GC
7831
58
88.66%
91.02%
BBBP
Real/GC
2039
100
87.80%
86.34%
BACE
Real/GC
1513
73
78.29%
80.26%
Graph-SST2
Real/GC
70042
36
90.84%
90.91% %
B EXPERIMENTAL SETTINGS
B. DEEP GRAPH MODELS
We first introduce the details of the GNN models we try to explain. For all GNN models, we employ two message passing layers for node classification (BA-Shapes (Ying al. 2019)) and three for graph classification tasks (ClinToxx Tox21, BBBP, BACE (Wu et al. 2018 BA-LRP (Schnake al. 2020,, Graph-SST2 (Yuan al. )020c In addition, the final classifier consists of two fully-connected layers. For graph classification tasks, the average pooling is used to convert node embeddings to graph embeddings. In addition, the feature dimensions message passing layers and fully-connected layers set to 300. We apply the ReLU function as the activation function after each message passing layer and fully-connected layer. In addition, the dropout is applied between two fully-connected layers. Note that we consider both GCNs and GINs for all datasets. For the GCN layer, employ the original normalized Laplacian matrix Á D- (A T)D- For the GIN layer, two fully-connected layers with the ReLU function are employed as the multilayer perceptron (MLP).
B.2 TRAINING SETTINGS
The models on different datasets use different learning rates and decay settings. Generally, we set the learning rate to 1 x 10-3 and the learning rate decay equal to 0.5 after 500 epochs. For datasets BA-LRP and Graph-SST2, the total number of epochs 100 while we train models for 1000 epochs on the other datasets. All datasets are split into the training set (80%), validation set (10%), and testing set (10%). All experiments are conducted using one NVIDIA 2080Ti GPU.
B.3 TARGETS OF EXPLANATIONS
Since different techniques focus on different explainable targets, such as nodes, edges, walks, flows, etc., these methods cannot be directly compared. For fair comparisons, convert all explainable targets to graph edges. First, GNNExplainer and PGExplainer provide edge-level explanations so their results directly used. Second, for flow-based methods and walk-based methods, including GNN-GI, GNN-LRP, and our FlowX, we convert the flow (walk) importance to edge importance by summing the total contribution of message flows (walks) that go through particular edge. In addition. for node-based methods such as GradCAM (Pope al.] 2019) and DeepL.FT (Shrikumar et al. (017). the node importance is mapped to edge importance that the contribution of an edge is the averaged contribution of its connected nodes. Specially, for subgraph-basee method SubgraphX (Yuan et al., 202T), we pick the explainable subgraph out, then assign the edges this subgraph instead of nodes as the explanation. Note that the absolute values of contribution are not important since the metrics focus on their relative rankings. The Figure. shows how to map from message flows to edges.
B.4 FLOWX SETTINGS
At the first stage, the MC sampling time is set as 30. At the second stage, we randomly initialize the weight vector of our learning refinement from the uniform distribution [0. 0.1). During the training,
14

---

Under review as a conference paper at ICLR 2022
BA-LRP
ClinTox
Tox21
BA-Shapes
Figure 4: An illustration showing how to convert message flow contribution to edge contribution. The top row shows the the flow view of explanations while bottom row shows the corresponding edge view. In the top row, we use red and blue flows to denote the positive and negative contribution respectively. In the bottom row, bold red arrow lines denote important edges.
we apply learning rate equal to 0.3 without learning rate decay and train the weight vector for 500 iterations. Meanwhile, we adopt
for exponential redistribution.
FlowX' & FlowXt. FlowX" can be implemented by replacing the weight vector w in section 3.3 with constant vector w' that w' = 1/|w/ where [w] is the length w. FlowX* implemented with similar pipeline as GNNExplainer (Ying al., (019). Instead of training the weights to obtain edge mask, we use flow mask to indicate the flow importance scores. The flow mask can be considered the weighted flow scores in our FlowX. In addition, we do not apply exponential scaling to FlowXi, The rest FlowXt the same as the learning refinement part in our FlowX.
C EVALUATION METRICS
Mathematically, K-elass classification dataset with N samples be represented as ((X,, y:)
1, 1,2,...,NN N). where (X,, A,) is the input graph and yi is the ground-truth label of the i-th sample. The predicted class of GNN model is ú argmax f A,), Here the output of f(X,, A.) is a K K-length vector, in which each element denote the probability of the corresponding class. Formally, we define the algorithm's explanation as column vector my that represents mask on explainable targets where the number of targets is |rngg- In this mask, the explanation method marks each selected target as value 1, otherwise O. The source of the mask is vector & with the same shape that stores the contribution score of each explainable target. Intuitively, we prefer to assign targets with 1s in the r the corresponding scores é; are relatively high. With these notations, we introduce the metrics employed for quantitative comparison.
Fidelity. Following the metrics mentioned in the graph explainability survey (Yuan et al. 2020c). we choose the metric Fidelity to measure the faithfulness of the explainability methods to the model. Mathematically, Fidelity is defined as:
N Fidelity = N A.) - (x,
(14)
where fm, (X,,A) denotes the output class 's's probability when masking out the edges based on rn. Specifically, we keep the value unchanged for the explainable targets that are marked as in rit, while setting the other explainable targets as O. Note that m, 1 rn is complementary mask where an all-one vector that has the same shape as m. In the evaluation period, the higher Fidelity indicates the better performance of the explainability algorithm. Intuitively, Fidelity represents the predicted probability dropping after occluding the important features. Therefore, Fidelity can measure whether the chosen features are important to the predictions from the model's perspective.
15

---

Under review as a conference paper at ICLR 2022
Table 3: The averaged time of eight algorithms.
GradCAM DeepLIFT GNNExplainer PGExplainer GNN-GI GNN-LRP SubgraphX FlowX
Time (ms)
14
15
353
N/A 704
5993
407784
4501
Table 4: Comparisons between FlowX and other methods in terms of average Fidelity over different Sparsity levels on GCNs. Bold and underline scores respectively denote the best and the second best results. In addition, because SubgraphX cannot control and reach all the Sparsity levels as we need, we cannot compare it with others in this table.
BA BA-Shapes
BA-LRP
ClinTox
Tox21
BBBP
BACE
Graph-SS3 SST2
GradCAM
0.39+0.09
0.50=0.03
0.23+0.07
0.1020.02
0.30+0.12
0.29=0.06
0.18+0.08
DeepLIFT
0.42+0.04
0.42+0.13
0.31
0.1420.03
0.37+0.12
0.42+0.08
0.22+0.11
GNNExplainer
0,41+0.01
0.45=0.11
0.23+0.09
0.09=0.03
0.3240.14
0.2420.08
0.1740.09
PGExplainer
0.38+0.07
0.4320.12
0.2020.10 10
0.02+0.00
0.1420.07
0.1020.05
0.0740.04
PGMExplainer
0.38+0.06
0.35#0.16
0.25+0.06
0.08=0.01
0.25+0.06
0.17=0.01
0.1640.06
GNN-GI
0.40+0.02
0.45=0.10
0.31+0.07
0.16=0.03
0.43+0.08
0.29=0.02
0.31+0.14
GNN-LRP
0.41#0.00
0.52=0.01
0.32+0.08
0.1420.03
0.35+0.
0.25=0.05
0.21
FlowX
0.42+0.01
0.51=0.01
0.38+0.06
0.22=0004
0.57+0.11
0.51=0.03
0.32+0.13
Sparsity. In order fairly compare different techniques, we argue that controlling the Sparsity (Popel ct al. 2019 Yuan et al., 2020c) of explanations is necessary. Mathematically. Sparsity is defined as:
N Σ 1=1
Σ mikl k=1 mis
Sparsity = N
(15)
mh
higher Sparsity score means fewer explainable targets are selected. Note that the selections of targets are determined by the ranking of the contribution score in é, It is noteworthy that these two metrics are highly correlated since the predictions tend to change more when more input features are removed. Then explanations with higher Sparsity scores tend to have lower Fidelity scores. For fair comparisons, we compare different methods with similar sparsity levels.
D EXPERIMENTAL RESULTS
In this section, we provide additional quantitative comparisons and visualization results.
D. QUANTITATIVE RESULTS
We report the guantitative results of GCN and GIN models in Table 4 and Table 5 Obviously, our method obtains the best averaged Fidelity score for 5 out 7 GCN models. Note that the performance competitive for synthetic dataset BA-Shapes and BA-LRP and method performs significantly better on the complex real-world datasets. In addition, we show the plots of Fidelity scores with respect to different Sparsity levels for all datasets and GCN models in Figure 5 Clearly, the performance of our method is stable and better.
Accuracy comparisons:
To further demonstrate the effectiveness of our proposed method, conduct experiments to compare the explanatory accuracy of three methods that usually evaluated in terms of accuracy. The results are reported Table These results are obtained from a synthetic graph classification dataset BA-INFE. Each graph includes base BA-graph and four types of motifs. Two classes of motifs are attached (2 motifs denote the one property. for another; let's denote them as class/property A and B). We first connect the same number (1 3) of each class's 's motifs to the base graph. Then we attach to 3 extra motifs from one of the classes (for example, class A) to the base graph; thus, the number motifs in class A is more than class B, representing the graph tends to have the specific property (property A). The ground -touts of a graph are the elements in those motifs including edges (undirected) and self- connections. The number of ground-trute elements that are covered by explanation edges is denoted as the hit number. The accuracy is defined as (hit number) (total number of ground-truth elements).
16

---

Under review as a conference paper at ICLR 2022
Table 5: Comparisons between FlowX and other methods in terms of average Fidelity over different Sparsity levels on GINs. Bold and underline scores respectively denote the best and the second best results. In addition, because SubgraphX cannot control and reach all the Sparsity levels as we need, we cannot compare it with others in this table.
BA -h-Shapes
BA-LRP
ClinTox
Tox21
BBBP
BACE
Graph-SST2
GradCAM
0.22+0.06
0.38=0.15 5
0.34+0.12
0.13+0.04
0.24+0.06
0.47=0.03
0.15+0.08
DiepLIFT
0.56+0.07
0.38=0.
0.44+0.14
0.12=0.04
0.21#0.06
0.48=0.03
0.20#0.10
GNNExplainer
0.53+0.17
0.38=0.16 16
0.35+0.15
0.01=0.01
0.22+0.07
0.41=0.06
0.12+0.06
PGExplainer
0.31+0.13
0.32=0.19
0.17+0.10
0.01=0.01
0.07+0.06
0.17=0.08
0.05+0.04
PGMExplainer
0.64+0.09
0.22+0.15
0.31+0.10
0.07=0.01
0.18+0.03
0.38=0.02
0.14+0.05
GNN-GI
0.63#0.09
0.19=0.12
0.51+0.11
0.16=0.02
0.2840.06
0.50+0.02
0.27+0.12
GNN-LRP
0.67:0.01
0.38=0.14 14
0.49+0.11
0.15#0.03
0.24
0.41=0.02
0.26+0.12
FlowX
0.69:0.01
0,46#0.03
0.55+0.08
0.23#0.03
0.47+0.06
0.67=0.04
0.29
Table 6: Comparisons between FlowX and three methods in terms of average Accuracy with 0.9 Sparsity on GCNs.
GNNExplainer
PGExplainer
PGMExplainer
FlowX
GCN
0,2528 0.2917
0.2199 0.2143
0.3612 0.3748
0.5266
GIN
0.4265
We also show the time cost of different methods Table 3 Specifically, we report the averaged computation time for 40 graphs in the ClinTox (Wu al. 2018 dataset. shows that FlowX performs the best with a reasonable time cost.
D.2 EXPLANATION VISUALIZATIONS
We provide additional examples to visually compare the explanations by six methods. The results are reported in Figure. 6 and 7 We can conclude that the message interactions between nodes are more important than self-loops. For example, in Figure. 0 all of DeepLIFT, GNNExplainer, and FlowX identify the motifs; however, FlowX attributes more the node interactions and obtain higher Fidelity score.
17

---

Under review as a conference paper at ICLR 2022
Shapes (GCN)
Tox21
0.45
A
0.25
0.40
0.20
Edelity
Rideity
Fideity
0.15
0.30
0.10
0.20
0.20
0.25
0.05
0.20
0.10
0.5
0.6
0.7
0.8
0.9
0.5
0.6
0.7
0.8
0.9
0.5
0.6
0.7
0.8
0.5
0.5
0.7
0.8
0.9
Sparsity
Sparsity
Spansity
Sparsity
BBBP (GCN)
BACE (GCN)
Graph-SST2 (GCN)
0.60
0.50
0.40
-0 DespUFT
Fidelity
Fideiity
0.40
Fidelity
0.30
GNMExplaner
PGixppainer
0.30
PGMExplinne
0.20
0.20
- Subgraphx
0.20
CNN-C1
0.10
GNI-LRR
0.7 Sparsity
0.5
0.00
0.8
Flowx
Sparsity
Sparsity
Figure 5: Comparison of Fidelity values by nine methods on seven datasets with GCNs under different Sparsity levels.
GradCAM Fidelity: 0,1479
DeepLIFT Fidelity: 0,3951
GNNExplainer Fidelity: 0,3847
GNN-GI Fidelity: 0.5148
GNN-LRP Fidelity: 0.3563
FlowX Fidelity: 0.6224
Figure 6: Sample explanation results of different methods on Tox21.
18

---

Under review as a conference paper at ICLR 2022
GradCAM Fidelity: 0.2201
DeepLIFT Fidelity: 0.2583
GNNExplainer Fidelity: 0.3052
GNN-GI Fidelity: 0.2832
GNN-LRP Fidelity: 0.2259
FlowX Fidelity: 0.4049
Figure Sample explanation results of different methods on ClinTox.
19


Reviews:
[{"review_id": "pEztCmjGv-o", "reviewer": "Reviewer_bCqP", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper presents a novel approach to address explainability in Graph Neural Networks but has several key points that remain unaddressed.\n\nStrengths:\n1. The proposed work is the first method that leverages message flow in GNNs to generate explanations for node- and graph-classification tasks.\n2. Leveraging Shapley values for estimating the importance score of message flows is an interesting approach.\n3. Extensive qualitative and quantitative experiments on both synthetic and real-world datasets.\n\nWeaknesses:\n1. The notations are inconsistent and confusing at times. For instance, $M$ denotes both the total number of Monte-Carlo sampling steps and the obtained mask from FlowX.\n2. In the initial assessment using Shapley value approximations, the removal of one edge causes the removal of multiple message flows. The contribution scores are then uniformly averaged and assigned to the different message flows. Note that this can cause spurious distribution of scores causing higher importance to message flows that were not useful for a given node- or graph-classification task, especially in the final layers.\n3. The notion of refining the Shapley importance scores is intuitive, but the use of optimization tricks like exponential scaling and encouraging discreteness can bias the refinement step to obtain edge masks that achieve better scores using the evaluation metrics in Sec. 4.\n4. What does the weight vector $w$ represent in Eq. 9? Is it just some kind of mapper function that translates Shapley scores to edge mask scores?\n5. The flow importances are converted to layer edge importance by simply summing up the scores of all flows sharing a particular layer edge as the message carrier. Would this cause the distribution of the layer edge importance scores to be skewed?\n6. The authors did not use any baselines when comparing different explanation methods in Sec. 4 and why were the scores calculated using just 100 samples? Was it for computational complexity? If yes, then mentioning the error bar in the results would increase the significance of Sec. 4.\n7. In Table 2, FlowX* performs on-par with FlowX on many datasets which questions the use of the refinement stage. An intuitive explanation for such behavior would be great.\n\nThank you for submitting a well-thought work! ", "summary_of_the_paper": "With explainability in Graph Neural Networks (GNN) still in a nascent stage, most graph explanation methods generate explanations in terms of nodes, node features, edges, or sub-graphs. GNN's are essentially message-passing networks, where every node has access to a local view of the graph created by the propagation of neural messages (embeddings) along edges in the node’s local neighborhood. However, none of the previously proposed GNN explainability methods consider message-flows as possible explanations. The paper proposes FlowX to identify important message flows by employing concepts of Shapley values, where an approximation scheme is used to estimate the Shapley values as initial assessments of flow importance. Finally, a learning algorithm is proposed to refine and map the message flow importance to edge mask explanations, where experimental studies on both synthetic and real-world datasets show the improvement of explanations using FlowX.", "summary_of_the_review": "Check the main review.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "gLhkPNCAjB", "reviewer": "Reviewer_ef9t", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n1. It is interesting that this paper uses important message flows as the explanation of GNN. Most existing methods use nodes, edges, or subgraphs to explain GNN.\n2. The proposed method is tested on several datasets. Ablation study is employed to evaluate the importance of two stages. The experiments also show the time cost of different methods.\n3. The paper is well structured and organized.\n\nWeaknesses:\n\n1. This paper lacks human intuition for using important message flows as an explanation of GNN. The practical significance of information flow as an explanation is not clear. Some practical examples may help readers to understand.\n2. The contribution is somewhat incremental given existing explainers, for example, SubgraphX. Although a learning-based function is proposed to refine the importance score of flows, it is not sufficiently innovative.\n3. In the experiments, some baselines are missing, such as Gem[1], GraphSVX. \n4. In addition to using fidelity and sparsity as metrics, the accuracy of the explainer w.r.t. a ground truth explanation is also an important metric, which appears in GNNExplainer and other explanation-related papers. \n5. Fidelity score performance on seven datasets with GCNs under different sparsity levels is inferior, which shows that the proposed method may not be effective. \n6. In Table 4, comparisons between FlowX and other methods in terms of average fidelity over different sparsity levels are conducted. This comparison method is confusing and unconvincing to me. The average Fidelity score has no practical significance, and a high average fidelity score cannot indicate the effectiveness of the method.\n\n[1] Wanyu Lin, Hao Lan, Baochun Li. Generative Causal Explanations for Graph Neural Networks. ICML 2021.\n\nMinor points: The definition of s should be clear, s represents both marginal contribution and importance score. The definition of k in F_k is not clear.\n", "summary_of_the_paper": "This paper explains GNNs by identifying important message flows. The authors use the concept of Shapley Value in Cooperative Game Theory and calculate Shapley Value as the initial assessments of flow importance score. A learning-based algorithm enables the refinement of important scores. Experiments are evaluated on both synthetic and real-world datasets.", "summary_of_the_review": "Though this paper proposed a different way to explain GNNs, using message flows instead of nodes/ edges/ subgraphs, it lacks clear intuition of the novelty of using message flow. Relevant work is missing. Contributions are somewhat incremental compared with the existing Sharpley-value-based approaches for GNN explanation. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "YgMKwPHRbx", "reviewer": "Reviewer_aAaM", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper tackles a significant problem (i.e., the explanation of Graph Neural Network) through a novel perspective: the importance of message flows. The paper is well-structured, with clear motivation and relation to existing baselines. It provides the reader with basic preliminary knowledge, describes the proposed method step by step, and evaluates its relevance. There are experiments with several datasets and baselines, as well as a small ablation study. So overall, I would say that this is an interesting work.\n\nHowever, I am a bit skeptical about the authors’ approach, which involves computing the importance of message flows from edge importance in each layer of the GNN model, before converting it back to edge importance for each GNN layer—ultimately provided as an explanation. Indeed, since the marginal contribution of message flows cannot be directly computed via current GNN models, the paper calculates the marginal contribution of each edge for every GNN block. Then, it attributes this computed importance to all message flows containing this edge, without distinction; and repeats this for all possible edges and several Monte Carlo iterations. Finally, it re-defines GNN layer edge importance as the sum of each message flow containing those edges. As a result, in my opinion, considering message flows adds a great amount of computational complexity and storage requirement capacity while it can only bring limited additional information; since the finest granularity layer for GNN is edges in different layers.\n\nAlthough this method seems very computationally expensive, the paper does not offer a proper complexity study, which appears essential. In addition to looping $M$ times on all edges of the graph in different GNN layers, it mentions storing matrices of size $|\\mathcal{A}| = |E| \\times T$ for each message flow, where the number of message flows is already difficult to track and grow exponentially with the number of edges. On the same note, the paper approximates all possible coalitions of players by sampling $M$ coalitions. There is no mention of how many Monte Carlo iterations $M$ are needed in practice (for the obtained results). Does $M$ relate to the size of the graph? Furthermore, at the end of Section 3.2, I believe there are $2^{\\mathcal{|A|}}$ possible coalitions, not $|A|!$, since the order of element matters in Shapley values.\n\nIn Section 3.3, the paper proposes a learning-based algorithm to refine the initial assessments. In fact, to the best of my understanding, it learns to weight the marginal contribution of a player when added to a given coalition of players, depending on the size of the existing coalition. This extension, although nice and formulated in a learnable fashion, is not entirely novel as it was suggested by “A unified approach to interpreting model predictions” (Lundberg, 2017). This simplification aside, it would be interesting to see the distribution of the weight $w$ to see if a trend emerges—validating or not the intuition of SHAP.\n\n**Interpretation.** The paper produces explanations for edges in different GNN layers. How can we leverage those, for instance, to spot which molecule is important for protein-function prediction? Or to spot if an Amazon product is a computer or not? The output explanation of the proposed method is not easy-to-understand for a human, especially as the number of GNN layers increases. Besides, it only targets graph structure and ignores features.\n\n**Figure 1** seems not to be really helpful. It probably could have been more informative. Why are self-loops removed for simplicity? I do not believe it makes things more simple. Also, for node classification tasks, is the importance of a message flow from a node to itself really used?\n\n**The notation is confusing.** For instance, $M$ refers to the number of MC samples as well as masks in 3.3. In Algorithm 1, it divides a vector by a vector (without saying it’s an element-wise division). In equation (9) it mentions element-wise operations, please mention dot product and do not confuse the reader with element-wise vector operation s(Hadamard product). The notation ‘For all’ in equation (10) is not rigorous, it should be in the sum.\n\n**Regarding the evaluation.** The Accuracy metric is not used. I would have liked to see how FlowX compares to SOTA baselines on the evaluation conceived by GNNExplainer, and followed by most other baselines. Very few node classification datasets.\n\nPGM-Explainer seems to be missing from Figure 1 - first graph. Also, why is no time associated with PGExplainer in the Supplementary Material?\n\nHow does FlowX's performance vary for different values of $M$? How is $M$ chosen in practice?\n\n", "summary_of_the_paper": "FlowX is an explanation method for Graph Neural Networks. It derives importance measures for message flows, which are inherent function mechanisms of GNNs. These measures are initialized with a Monte Carlo approximation of the Shapley Values from Game Theory, applied to message flows. They are refined by learning a linear transformation, before being converted back to layer edge importance score ultimately provided as an explanation. Various experiments are performed to assess the relevance of the proposed explainer.", "summary_of_the_review": "In a word, although this constitutes important work with a rather nice original intuition, the technical contribution is limited, the concept of Shapley Values was already leveraged by two GNN explainers (SubgraphX and GraphSVX -- which are not both used in the evaluation), and the evaluation is a bit light.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "EF_86HEfNvZ", "reviewer": "Reviewer_ctC1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n1). The idea is novel and interesting. Basically, to use message flows as the explanation is reasonable for GNNs. \n\n2). The writing is clear and easy to follow.\n\n3). The validation is also supportive for proof of the validity of the proposed framework.\n\nCons:\n1). The initial generation of candidate sets of flows and the permutation algorithm seems to be time-consuming. The authors are required to analyze the time complexity of the proposed algorithm. Although, the authors list the computation time in the appendix, theoretical analysis of the time complexity is also useful. Moreover, in table 1, the author listed the number of graphs, however, to what extent the algorithm can handle large graphs. Thus, it is suggested to list the #nodes of the largest graph in the set. \n\n2). The author adopts sparsity and fidelity as the metric for comparison. This is also used in SubgraphX. However, in PGExplainer and GNNExplainer, they use accuracy as the metric. It is suggested to also report the comparison of the accuracy of different methods.\n\n3).  Typos and grammar errors:\nmaybe not sensitive to model==>maybe not be sensitive to model\nmay not suitable==>may not be suitable\nTowards explanation of==>Towards an explanation of", "summary_of_the_paper": "The paper proposed to identify important message flows as the explanation of the GNN models. To achieve acceptable fast calculation of Shapley values for identifying the message flows, the authors use n Monte Carlo (MC) sampling. ", "summary_of_the_review": "Basically, the idea is interesting and the solution is also sound. I would champion the acceptance. However, I have still some concerns as listed. Thus, I gave a weak acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes an explanation method based on message flows, and shows better performance than the state-of-the-art methods.
The authors addressed most of the reviewer's comments but the reviewers are not enthusiastic.  So I give my evaluation (some concerns are shared with reviewers and were not well addressed in the rebuttal)

Pros:
- State-of-the-art results on edge scoring.

Concerns: 
- The main claim is not supported.  The authors say "we argue that message flows are more natural for performing explainability.  To this end, we propose..."  But I see no such argument after the proposed method is introduced.  Also, no advantage of the flow-based approach is shown.  The experiments only show edge scoring, which ignores the layer-wise edge scoring.  For this task, many existing methods are similar to the proposed approach in the sense that they measure how much information goes through subgraphs.  Although the proposed method shows good performance in edge scoring, this is not necessarily because the proposed method is flow-based, and cannot be evidence of the superiority of flow-based methods.  Fine details of the algorithm can contribute to the performance.  In the rebuttal, the authors mentioned a virus infection dataset as a situation where the flow-based method can do beyond what existing methods can do.  This kind of experiment should be shown in the paper to support the main claim.  
- Difference between flows and walks is unclear.  The authors imply that this paper is the first paper based on the flows, and reviewers understood so.  The authors say a walk is "similar" to a flow but the difference is not explained.  (the authors only talk about the difference in how to compute the score in Schnake et al.)  Essential difference between walks and flows should be explained. 
- The reason why the proposed method performs better than the existing methods is not analyzed.  The authors say they "believe" that this is because the proposed method is based on flows, but what readers want to see is evidence.
- Presentation should be improved.  Some formulations are unclear, e.g., I have no idea what F_?{t} means.  If this would be the best notation the authors think of, it should be explained with a figure.  Use another character if t is not the layer id.  Notation is not consistent, e.g., edges are denoted by e in Section 2.1 while they are denoted by a later.  
- Marginal technical contributions.
- High complexity.  The proposed method seems not scalable even with the crude Monte Carlo approximation with a small number of samples.

With my concerns above and the reviewer's evaluations, I would not recommend acceptance.
Decision: Reject