Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: **Summary**
The paper proposes a procedure for identifying a subgraph $\mathcal{G}_K$ of a given size $K$ (measured by the number of edges) whose output through the GNN function $f$ is as close as possible to that of the full graph $\mathcal{G}$. The proposed method is a greedy approach which starts from an empty graph and gradually adds the next edge by minimizing the difference between the outputs using mutual information. Furthermore, to reduce the computational complexity, a node clustering is done on the graph and the attribution is applied first on the edges between $C$ identified clusters and then transferred to all edges.

**Quality**
The experiments are relatively thorough and the writing is fine.

**Clarity**
The description of the method starts clearly at the high level but then lacks important information when the actual approach is presented in detail towards the end. In addition, more  discussions, motivations, and intuitions are needed for the design choices of the actual algorithm. Also, it is unclear if the main results are obtained using the cluster-based approach or not. Details described below.

**Originality**
While similar methods have been used in the image domain, to the best of the reviewer’s knowledge, the work is original in the context of graph networks. The reviewer believes the approach is better suited for graph networks, due to the feasibility arising from the structuredness of graphs.

**Significance**
The work conducts experiments covering different kinds of datasets as well as graph networks and considers multiple relevant baselines for GNN explanation. The results are, in general, significantly better than the baseline approaches on 3 different criteria. The paper is significant in that the approach is fundamentally different from the baselines and that the results are qualitatively and quantitatively different or better.

**Major technical comments**

*Experiments*
1. the results are obtained on three different datasets based on three different state-of-the-art graph networks and using an average of 5 independent runs.
2. Various graph explanation baselines are considered and the results show clear general improvement over the baselines in the three criteria used by the paper.
3. While the approach can generally be expensive, the time complexity of the cluster-based approach seems to be comparable to GNNexplainer and CXplain.
4. The difference in faithfulness (accuracy) compared to prior works on explaining graph predictions is clear and significant. However, the mere improvement over the baselines is not surprising since the proposed explanation method directly optimizes an objective to mimic the full graph’s function.
5. How is $\mathbf{X}$ obtained in practice? What clustering algorithm has been used for the method?
6. Does table 1 contain the results of the standard causal screening or the cluster-based one? The paragraph on the “influence of cluster numbers” seems to suggest the results in Table 1 belongs to the standard causal screening. If so, what are the results of the cluster-based method for w.r.t. contrastivity and sanity check? What is the computational complexity of the standard vs. cluster-based variant? What number of clusters is used for table 1, if it is cluster-based.

*Theory*
1. The greedy approach selects only *one possible* subgraph that explains the prediction. The distinction between “irrelevant edges” and “redundant edges” should be important here if the goal is to find the “causal” subgraph. Since the paper motivates the approach completely based on causal reasoning, an appropriate discussion is required.
2. How are the super-edges of the supernodes constructed? Does any edge between any nodes of two supernodes induce a single superedge between the two supernodes? Or there can be multiple super-edges connecting the two supernodes? 
3. When doing the attribution on the new “super” graphs, are the intra-supernode edges always present when finding the attribution of superedges? How does this choice affect the goal of finding causal edges? Especially this choice virtually implying that intra-supernode edges are “attributed” when deriving the attribution of super-edges.
4. When constructing Z, why is the original X that contains soft clustering used while the H is obtained using the hard clustering assignments?
5. What is an interpretation of a z representation of a node? Why should the dot product of z vectors be a good proxy for their attribution? Separate arguments are probably needed for intra-supernode and inter-supernode edges.

**Minor technical comments**
+ the qualitative figures are interesting in that it shows the potential ways that the proposed approach can better find the key connections compared to the baselines. 
- It’s better to start the “Task Description” section by something similar to “we define a graph of interest …”.  Otherwise it causes confusion since the definition, only based on edges, is in contrast to the previous paragraph and is only resolved at the end of the current paragraph.
- The statement “Directly optimizing Equation 1 is generally NP-hard” requires citation and/or explanation.
- in eq.3, shouldn’t it read: $|\mathcal{G}_k| = k$?

**Overall**
The paper proposes a different approach compared to the currently-existing explanations for graph networks. This type of “causal” explanation is considerably more feasible for and better fits graph networks thanks to their sparse and modularized structure. Although the results on accuracy are not surprising, they are still useful for applications that are interested in finding substructures responsible for a certain prediction. This is in fact quite commonly useful in many applications dealing with graph networks such chemistry, biology, image understanding, social networks, etc. The paper can greatly be improved on its clarity, especially when it comes to the design choices for the cluster-based variant. That being said, the results are quite convincing such that it empirically validates the approach.
All in all, if the paper is improved on clarity during the revision period, I would lean towards acceptance.

**Post-Rebuttal**
My main concern was regarding the clarity of the paper. I believe it is improved in the revised version, so I increase my rating.

review_title: Good paper with a different and useful approach to the explanation of graph networks but lacks clarity on various occasions

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper proposes a method, called Causal Screening, to improve the interpretability of GNN. Basically, the proposed method adds each edge in GNN in a greedy way by evaluating its causal effect on the prediction. The experimental results show the improved performance of the proposed method compared to others.

Pros:
Overall, the presentation is clear and the idea is interesting. 

Cons:
However, I have the following two concerns. 
1. First, Eq. (1) and Eq. (3) do not guarantee to achieve the same graph, because Eq. (3) adds each edge in a greedy way, which may result in a suboptimal graph. To mitigate this issue, besides the forward phrase, the authors may consider adding a backward phase to remove spurious edges. 
2. Second, the formula for causal effect estimation (Eq. (2) and Eq. (4)) seems strange to me. It is different from the normal formula of the potential-outcome estimation. I do not understand why the authors estimate the mutual information between a constant (a particular graph) and the prediction.

If the authors can solve the above problems, I will increase the score.

Furthermore, to better show the efficacy of the proposed method, in the experiments, the authors should vary the graph size and graph density.


Post-rebuttal:
Thanks for the feedback. By optimizing Eq. (3), the learned graph is not guaranteed causal, so I would like to suggest the authors not emphasizing "causal".

review_title: Clear presentation; interesting idea; but the formula does not seem correct

final_score: rating: 7: Good paper, accept
review_content: Summary: The paper introduces a novel method called Causal screening which takes a graph and the prediction made by a GNN, and returns an explanatory subgraph. The method aims to explain GNN models. To be precise, it starts from an empty set as the explanatory subgraph, and incrementally adds the edges, testing them for the individual causal effect.

Strengths: The paper is well-written. It addresses the limitation of many interpretable methods which are based on statistical interpretability, and ignore causal relations. 
I also like the idea to do cluster-by-cluster screening where edges across two clusters serve as a super-edge. I also agree that causal attributions of edges of edges are more reliable than information from gradients, often used to explain models.

I also liked the running example which clarifies the contributions.

Weaknesses: It is interesting to see what is the value of eq. 4 in practical applications.  I can imagine that the value can be quite small, and probably some threshold is needed. I see that doing clustering can leverage this effect. However, doing clustering and working on the clusters can provide quite different results that working on separate edges. One edge which is quite strong can impact the behaviour of the whole cluster. 
I guess that it is interesting to study individual impact of edges on the clusters.

review_title: The paper proposes a method to explain predictions made by GNN. The explanations are presented as a graph. The paper is well-written and reports interesting results.

final_score: rating: 5: Marginally below acceptance threshold
review_content: This work proposes to explain graph neural networks from a causal effect view. The proposed method, Causal Screening, iteratively adds edges into the explanatory subgraph. The goal is to maximize the $do(\cdot)$ calculus, which tries to select an edge such that the prediction probability when feeding into GNNs is close to the original prediction. Experimental results show that the proposed method can outperform other comparing methods.

Strengths:
+ Explaining GNNs is very important and interesting. This work focuses on the causal attribution view, which is a good direction.
+ The proposed “Causal Attribution of A Super-edge” is very useful for large-scale graphs, which can reduce the computational cost.
+ Experimental results show that the proposed method can outperform other methods for some metrics.

Weaknesses:
- The first concern is the motivation of this work. The motivation is coming from the running example in the introduction. It claims that other method leads to confounding association that (shorts, on, man), and (man, has, hand) are correlated with the prediction, rather than causing it. However, this is from the human’s view, not the model’s view. For interpretations, the method needs to explain the model. How do we know (shorts, on, man), and (man, has, hand) are not causing the prediction?
- The proposed method is very straightforward, which is a simple application of the individual causal effect. The technical contribution may not be enough for ICLR publication.
- The proposed method now only considers the edge importance while other comparing methods consider the importance of edges, nodes, and features.
- The computational cost of the proposed method is very high. For each step, it needs to call the GNN multiple times to select a good edge from the candidate.
- The GNN-explainer can obtain much better sanity check scores with the model randomization test, which means the proposed method is less dependent (less faithful) to the model compared with GNN-explainer.

I am willing to adjust my score if my concerns are properly addressed.

=====Update after rebuttal=====

I have read the authors' rebuttal. I am increasing my score to 5 as some of my concerns are addressed. 

1. I do not agree with the responses for the "Motivation --- Causality in Running Example". First, the GNNExplainer tries to maximize to mutual information, which means important edges for the prediction should be kept. Then why does the GNNExplaienr suffer from the confounding association? Second, "individually feeding the top edges into the target GNN" is not convincing. "An  edge is important for the prediction“ does not mean “the prediction score is high when feeding individually”.

2. I still believe the proposed method is very straightforward and the novelty is limited. 


review_title: Official Blind Review #2 

Meta-review: I found the main algorithmic contributions to be interesting and of potential value to practitioners, as highlighted by Reviewer 3. Like several reviewers, I found the causal framing to be confusing, or at least not really to be framed in a framework like Pearl's: the word "confounding" is thrown a few times in the manuscript, but there is no formal sense by which it is linked to what we commonly understand as confounding. We are still talking about what happens inside a predictive model (a deterministic function), not what happens in the real world (the authors are not alone as targets of my observation: my point applies to a lot of the papers in the references, where the causal interpretation is hardly illuminating for those coming from a causal inference background, for instance). The reply to Reviewer 2, for instance, cites [1], which is about Granger causality and has little to do with Pearl's framework. Despite its name, Granger "causality" is a probabilistic concept (or, at best, an idea for identifying non-causality) with a very minimal causal basis besides the use of time ordering. A much more rigorous explanation of confounding in this paper's context needs to be provided. 

That been said: as helpfully highlighted by Reviewer 3 (and summarized without any need to resort to a causal framing), there are several positive contributions added here, which might be of interest to the ICLR audience. The causal framing unfortunately gets in the way without adding clarity.

In its present state, the paper is not yet ready for publication. We hope that the reviewer comments prove helpful for preparing a strong future submission. 
Decision: Reject