Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a decomposition-based explanations method for graph neural networks.  In detail, the authors design a subgraph level interpretation algorithm to reveal complex interactions between graph nodes, so as to achieve the faithful explanation for GNN predictions. They demonstrate the effectiveness of the proposed method on synthetic and real-world datasets. 


main_review: 
The main concern of this paper is the decomposition assumption.  Because of the nonlinearity property in neural networks, how to decompose to the target portion and the background portion for the input features/representations.  It likely has potential interactions between the target portion and the background portion. 

As for the faithfulness issue, there exist a few decomposition-based explanations methods, e.g.,  Layer-wise Relevance Propagation (LRP) [1], Excitation BP [2], and GNN-LRP [3]. Most of their methods are proposed to employ score decomposition.

The subgraph-level interpretation search algorithm has been already explored by others [4]. It would be better if authors can compare with them.

[1] Explainability techniques for graph convolutional networks

[2] Explainability methods for graph convolutional neural networks

[3] Higher-order explanations of graph neural networks via relevant walks

[4] On Explainability of Graph Neural Networks via Subgraph Explorations


It is not easy to understand the description in the qualitative evaluation section, especially the description of Figures 2 and 3. 
Meanwhile, it would be better if authors can compare with other explanations methods in the qualitative evaluation section.

summary_of_the_review: The main concern of this paper is the decomposition assumption.  Because of the nonlinearity property in neural networks, how to decompose to the target portion and the background portion for the input features/representations.  It likely has potential interactions between the target portion and the background portion.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper aims at tackling the black-box nature problem of GNN by introducing a new type of explainable GNN framework called DEGREE (Decomposition based Explanation for GRaph nEural nEtworks). There are mainly two innovations. The first one lies in its ability to track contribution of components in the input graph. The second one is the algorithm for subgraph-level explanation via agglomeration. The model achieves a good compromise between performance and time efficiency.
main_review: Strengths:
S1. The paper innovatively proposes a new explainable framework that decomposes the information into target and background portion. In contrast of previously used approximation-based, perturbation-based, additive feature attribution methods, the authors claim that the newly proposed method has the advantages of higher fidelity and node-level explainability.
S2. Two popular GNN framework GCN and GAT are used as examples for decomposition operation, which demonstrates the methods compatibility to the current mainstream. A new subgraph construction algorithm is also proposed to tackle the problem arising during finding most important subgraphs, i.e., it’s impossible to enumerate all subgraphs.
S3. The quantitative evaluation shows in two metrics: Explanation AUC and time efficiency. The proposed method significantly outperforms other benchmarked methods in at least one of the metrics (some benchmarked methods are only shown for Explanation AUC, not for time efficiency though), potentially making it a new choice under different use scenario. A qualitative evaluation was also included for a visual check of the result quality.
S4. The paper is well organized and clearly written. Figures are provided with descriptive caption, including details needed for comprehension. Datasets includes both synthetic datasets and real-world datasets for diversity.

Weaknesses: 
W1. The transition from absolute contribution scores to relative contribution score in Sec 4.1 is abrupt without detailed reasons. Why are relative scores preferred? Also, if they are preferred, why use absolute score in Sec 3? Providing answers to these two questions will make the logic flow more smoothly.
W2. The exclusion of Graph-SST2 dataset from quantitative evaluation raises the question of whether the model has a poor performance on this dataset and hence has little generalization power. Providing the reasons for not including this dataset makes the benchmarking more supportive for the claimed superior model performance.
W3. The limitation of the model was shown in the wrong prediction example in the qualitative evaluation but was not discussed in detail. What could have caused the wrong prediction and how to circumvent them?
W4. Missing related work that should be discussed: On Explainability of Graph Neural Networks via Subgraph Explorations (ICML 2021)

Minor comments:
1. In Figure 2, I assume the shade of color means the value of the score, but it is probably a better idea to explicitly state it in the caption or have a legend in the figure.
2. It would be preferred to include the statistics such as the number of graphs for synthetic datasets as well.



summary_of_the_review: The paper innovatively proposes to decompose the information flow for explainability and provides a new algorithm to construct subgraphs to reveal more complex interactions. This novel way of explaining graph component contributions give insights into a new explainable GNN framework and is potentially inspiring for other works. The experiments also show its superior performance and time efficiency compared with other methods (although some related work is missing). Thus, I am slightly positive of this paper.

====Post Response====

After reading the author response, they have indeed addressed some of my concerns. However, after also reading through the other reviews and their respective replies, I am inclined to keep the score of "marginally above the acceptance threshold" because I am still more positive towards the work. I have additionally increased the novelty and significance from a 2 to a 3. Thank you for providing the reply, especially the details regarding my original concern about Graph-SST2.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper provides DEGREE, which decomposes the feedforward propagation mechanism of a GNN to understand it. They give realistic decomposition techniques for those typically used layers in GNNs after presenting the key guidelines for developing decomposition-based explanations. They also devise an approach for providing subgraph-level explanation via agglomeration, which makes effective use of graph topology. DEGREE surpasses baselines in terms of fidelity and can capture important structures in graph data, according to experimental results.
main_review: The paper focuses on the explanation of GNN performance, which is an interesting and critical problem. The paper proposes a reasonable method for the problem to decomposite the graph. The experiments are also comprehensive. However, there are still some points required to be clarified.

1,  The new scoring function proposed in the paper uses a random walk process, so will the calculation process has a high time complexity and space complexity (storing sample graphs)?

2, In q · maxv′ r(v′), what is the impact of the hyper-parameter q on the subgraph expansion?

3, The AUC used in the experiments should be explained in detail. For me, I have to search previous works to understand how to use it in GNN explanation issue. It is not friendly to common readers.


summary_of_the_review: The paper is easy to follow and has a reasonable method. Besides, the comprehensive experiments, especially the visualization of results, verify the effectiveness of the proposed method. I surely recommend acceptance after my above doubt is solved.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a decomposition-based explanation method for graph neural networks. The motivation of this paper is that existing works based on approximation and perturbation suffer from drawbacks. To address the issue of existing works, the authors directly decompose the influence of node groups in the forward pass. The decomposition rules are designed for GCN and GAT. Further, to efficiently select subgraph groups from all possible combinations, the authors propose a greedy approach to search for maximally influential node sets. Experiments on synthetic and real-world datasets verify the improvements over existing works. 
main_review: Strengths: 
- The problem studied is of importance and interesting. 
- The paper is generally well organized. 
- Quantitative experiments are done, which is a plus for subjective topics like XAI. 

Weaknesses: 
- Concepts are not defined or hard to follow. See details. 
- Qualitative experiments are hard to follow. See details. 
- Questions/unclear points regarding technical details. See details. 
- The decomposition method seems straightforward, especially the GCN decomposition (as it is largely linear). 

Details. 
- Some technical concepts are not defined or hard to follow. 
    - Section 3.1. The goal of explanation is to find the most important subgraph in $\mathcal{G}$ given $f(\mathcal{G})$. The concept is vaguely defined. What is the concept of 'important'? Further, in the experiments, the task is actually to predict whether a node/edge is important or not. This seems to deviate from the definition. 
    - Section 4. 'We could compute the contribution score of any given node groups'. However, the notion of 'contribution score' is not defined previously. This makes this section hard to understand. 
- Qualitative experiments are hard to follow. 
    - Figure 2. What does it mean 'the process goes from left to right'?
    - The authors claim that 'existing works suffer from adversarial triggering issues (perturbation) or inaccuracy (approximation)'. However, the claim is not supported, especially the perturbation-based drawback of unrealistic structures. I think this point can be better supported by showing examples that perturbation-based methods indeed generate such samples. At this point, I find it hard to evaluate the qualitative experiments. 
- Questions regarding technical details. 
    - Section 3.1, $f: \mathcal{G}\mapsto \mathbb{R}^{|\mathcal{V}|}$ or $\mathbb{R}$. It seems that the formulation only works on binary classification or regression. Can this framework (respectively, DEGREE) be extended to the multi-class setting? 
    - Section 3.3 Intuition (2): ideally there should be little interaction between the target portion and the background portion. However, in graphs, this intuition can hardly be satisfied because nodes are connected to each other. How does the framework work when this intuition does not hold? Or can you provide evidence that this intuition somehow holds in real-world data? 
    - Equation 13, this equation is hard to understand. First, what does it mean $softmax(\mathbf{X}[t])$? Second, what does it mean $\exp(|\mathbf{X}^\gamma[t]|)$? Third, what does it mean to divide vectors with vectors (given that $\mathbf{X}[t]$ is a vector)?

- Minor issues. 
    - Please change the coloring of the figures such that they are visible when printed out. 
    - Section 4.2, how should we initialize $\mathcal{E}$, $\mathcal{S}_i$? How should we tune the parameters $I, q$? 
    - How is the definition of 'importance' in Graph-SST2? 
    - Section 5, last paragraph, 'detect non-linear interactions', what does it mean non-linear interactions? Does it mean language conjunctions such as 'if', 'but'? 
summary_of_the_review: In summary, this paper has its merits. The paper tackles an interesting problem. The proposed framework is generally sound. The paper is organized well in general. However, given its unclear points in experiments and technical details, I do not recommend acceptance at this point. 

====Post Response====

My doubts and suggested weaknesses are addressed partly. I am willing to suggest borderline accept.
review_title: null

Meta-review: This paper proposes a decomposition-based explanation method for graph neural networks. The motivation of this paper is that existing works based on approximation and perturbation suffer from various drawbacks. To address the challenges of existing works, the authors directly decompose the influence of node groups in the forward pass. The decomposition rules are designed for GCN and GAT. Further, to efficiently select subgraph groups from all possible combinations, the authors propose a greedy approach to search for maximally influential node sets. Experiments on synthetic and real-world datasets verify the improvements over existing works. During their initial responses, reviewers suggested that the authors experiment with more baselines and also clarify some of the technical details. The authors revised their manuscript to address several of these comments. So, I am tentatively assigning an accept to this paper.
Decision: Accept (Poster)