Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: - This paper proposes a new GNN explanation method called Graph Structure-aware eXplanation (GStarX) based on HN value from the cooperative game theory, and claims it is able to leverage the critical graph structure information and improve the GNN explanation.
-  This paper also tries to explain why and how this method is more effective compared with existing methods based on Shapley Value claimed to be non-structure-aware. 
- Experiments conducted on chemical graph property prediction and text graph sentiment classification are used to demonstrate that GStarX produces qualitatively more intuitive explanations, and quantitatively improves explanation fidelity

strengths_and_weaknesses: - Strengths
    - This paper is first to apply HN-Value (borrowed from game theory) to GNN explanation and illustrates its effectiveness. 
    - Compared with non-structure-aware GraphSVX, HN value utilizes graph structures to attribute cooperation surplus between neighbor nodes, so that node importance scores reflect not only the node feature importance, but also the structural roles.
    - SubgraphX is also structure-aware for GNN explanation, but it has limitation of only generating one single connected subgraph as explanation. GStarX can overcome the issue by generating multiple disconnected subgraphs as explanation.
- Weaknesses
    - The paper does not clearly explain how Equation 6 and 7 are transformed into the form of matrix multiplication in Algorithm 3, and some necessary explanations are needed for better understanding.
    - The paper claims that "Connecting GNNs and the HN surplus allocation through the message passing lens" and uses a molecule example shown in Figure 1 (c) to demonstrate  the connection between structure-aware HN value and the GNN message passing. A graph for sentiment classification in Figure 1(b) is used to qualitatively show that the structure-aware HN value can eliminate the inappropriate word coalition. But for better understanding, it seems there is lack of clear illustration using a unified explanation mechanism, which can naturally connecting these examples of message passing and elimination.
    - The example in Figure 1 (b) is only qualitatively studied, and for consistency and better illustration, it should be included in section 5 with the detailed quantitative analysis.

questions: - Why the fidelity is used as the only metric for evaluation? How about metrics such as AUC and accuracy used in some other GNN explanation papers?
- Is the evaluation in Table 1 (with 8 different Sparsity) meaningful or fair?
- Algorithm 1 illustrates the main framework of the paper, but it seems Algorithm 3 is equally important for better understanding. It may be more appropriate to include Algorithm 3 in the main body of the paper. 

limitations: There is no potential negative societal impact of this paper.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper proposes a structure aware scoring function, referred to as HN value, to explain decisions of a GNN for the task of graph and node classification. HN value originally proposed in reference [6] of the paper has its roots in cooperative game theory like Shapley values but unlike Shapley values, it is structure aware.  An algorithm called GStarx is proposed which computes HN values corresponding to nodes in a graph later presented as explanations. Higher the HN value higher the node importance. The superiority of the method is demonstrated via experiments in 6 graph classification datasets. 
strengths_and_weaknesses: Strengths:

1. The paper proposes a new scoring function based on cooperative game theory to find node importances.
2. The paper is well written and structured. 
3. The overall study is carried out well with various concerns, regarding application to node classification, comparison to closely related work based on C-Shapely, at least addressed in the Appendix.

Weaknesses:
1. The proposed method can only be applied to find node importances ignoring the differing feature importances. Note that a GNN uses both node features and structure to make predictions. Some of the features might be more important than others towards a decision.
2. There are a few clarifications required based on the current text which I also elaborate under Questions. 






questions: 1. I am still wondering about the lack of feature importances in the explanation. For a graph we are given nodes, their features and the connections. The current paper address the problem of finding the most important nodes, which might be reasonable for the datasets used currently in the paper. But for real world datasets both for node and graph classification, node features may play an important role. How do or can we find feature importances together with node importances with the current methodology? 

2. Definition 4.2 is a bit confusing.  It seems like the condition |S/G|=1 will only be satisfied if the induced graph on nodes in S is a clique.  But intuitively, the first condition should correspond to graph induced on S to be a connected subgraph. The authors should elaborate on definition 4.2 a bit more and justify the choice even if it was originally proposed in [6]. The example given in lines starting from 180 is too simple as it only considers the case when |S|=1.

3. In the GStarX algorithm, what is f^0_c^*?

4. It is not clear if the obtained explanations are actually sparse as the importance scores are continuous. For example, a method can lead to a uniform importance score distribution over the nodes, i.e., all nodes are almost equally important. One should use entropy based metric for sparsity as proposed in https://arxiv.org/abs/2105.08621  to show that indeed the importance score distribution is not very uniform.

One minor question: What does HN stand for? I even looked up in the original paper [6], could not find the full form!
limitations: One of the main limitations of this work is that there is no direct way to compute feature importances while explaining a decision which might be very important in some real world datasets and applications. Consequently in presence of feature explanations more evaluation metrics might be required as one can just not simply remove a feature while computing fidelity/faithfullness as argued in https://arxiv.org/abs/2105.08621

The authors should explicitly acknowledge this limitation while still providing examples of application areas for example for text graphs or graphs with dense feature representations extracted using some unsupervised representation learning methods. In those cases, providing additional feature explanations might not be useful as the features themselves are not directly interpretable.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The explainability of GNNs is crucial for modeling graph data. This work is based on the HN value instead of the Shapley value to explain the GNNs, which involve the graph structure information.  
strengths_and_weaknesses: Pros:

The proposed method is quite clearly defined. Most of the time, I enjoyed reading this paper because of its clear and concise introduction to the preliminaries of this work (including Shapley value and HN value). Considering graph structure information via HN value to explain the GNNs is reasonable. The experiments have demonstrated the effectiveness of the proposed GStarX algorithm. 

Cons:

One limitation of the approach is its lack of technical originality. Although using the HN value is interesting and innovative on this issue, this paper did not provide any original theoretical analysis on the benefit of leveraging graph structure information via HN value to explain the GNNs. Meanwhile, for the examples in Figure 1, only comparing the basic Shapley method is not enough to demonstrate the advantages over other SOTA methods. And, for Figure 1 (b), it is hard to say whether the coalition {“not”, “good”} contributes negatively when using the GNNs to model two unconnected nodes: “good” and “not”.
questions: Please describe the original theoretical contribution of the paper.


limitations: N/A
review_title: null

Meta-review: metareview: The paper considered the task of identifying the most important subgraph and constituent nodes for graph-level predictions. It argued that the popular Shapley value is non-ideal since it's not structure-aware. It then proposed a structure-aware method, a scoring function based on the HN value from the cooperative game theory. Empirical results show that the method produces qualitatively and quantitatively improves over strong baselines.

The paper considers an important topic and has made novel and interesting contributions: the discussion that the Shapley value is not ideal for graph explanation, the non-trivial application of the HN value in this context, the well-design method and the thorough study showing its effectiveness. The authors have addressed well the comments by the reviewers.
confidence: Certain
Decision: Accept