Venue: ICLR 2022 Conference

Reviews:

final_score: rating: null
review_content: Thanks for the feedback! Considering my concerns are not well addressed, I do not think this paper is qualified enough to be published in ICLR. I will keep my original rating.
review_title: Rebuttal résponse 

final_score: rating: 3: reject, not good enough
review_content: 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.
main_review: Strengths:

1. 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.
2. 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.
3. The paper is well structured and organized.

Weaknesses:

1. 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.
2. 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.
3. In the experiments, some baselines are missing, such as Gem[1], GraphSVX. 
4. 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. 
5. Fidelity score performance on seven datasets with GCNs under different sparsity levels is inferior, which shows that the proposed method may not be effective. 
6. 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.

[1] Wanyu Lin, Hao Lan, Baochun Li. Generative Causal Explanations for Graph Neural Networks. ICML 2021.

Minor 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.

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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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. 
main_review: Pros:
1). The idea is novel and interesting. Basically, to use message flows as the explanation is reasonable for GNNs. 

2). The writing is clear and easy to follow.

3). The validation is also supportive for proof of the validity of the proposed framework.

Cons:
1). 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. 

2). 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.

3).  Typos and grammar errors:
maybe not sensitive to model==>maybe not be sensitive to model
may not suitable==>may not be suitable
Towards explanation of==>Towards an explanation of
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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
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.

However, 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.

Although 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.

In 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.

**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.

**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?

**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.

**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.

PGM-Explainer seems to be missing from Figure 1 - first graph. Also, why is no time associated with PGExplainer in the Supplementary Material?

How does FlowX's performance vary for different values of $M$? How is $M$ chosen in practice?


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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.
main_review: The paper presents a novel approach to address explainability in Graph Neural Networks but has several key points that remain unaddressed.

Strengths:
1. The proposed work is the first method that leverages message flow in GNNs to generate explanations for node- and graph-classification tasks.
2. Leveraging Shapley values for estimating the importance score of message flows is an interesting approach.
3. Extensive qualitative and quantitative experiments on both synthetic and real-world datasets.

Weaknesses:
1. 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.
2. 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.
3. 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.
4. 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?
5. 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?
6. 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.
7. 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.

Thank you for submitting a well-thought work! 
summary_of_the_review: Check the main review.
review_title: null

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