Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: The authors propose ZORRO, a post-hoc explanation method for node classification with graph neural network architectures. ZORRO leverages rate-distortion theory to generate masks that select nodes in the target node neighbourhood and their most important features. 

* The problem is very relevant to the GNN community, and I am glad to see more works coming in on this topic.
* The idea of relying on rate-distortion theory is interesting and original, and to the best of my knowledge this is the first time I see it used to tackle this research problem.
* The paper is well structured and organised.
* The original contribution is sufficient.
* Related work is sufficiently well covered.

Nevertheless, the paper suffers from shortcomings:

A) The paper claims that ZORRO can generate multiple, disjoint explanations, apparently all highly faithful. This seems to be at odds with the authors' claim to explain the behaviour of the model. In other words, if I were on the receiving side and I was given multiple _disjoint_ explanations, which one should I trust more? How can explanations shed a light on the  behaviour of models if they are disjoint? I see ZORRO is able to generate overlapping explanations as well (a property compatible for example with example-based technique in XAI literature such as counterfactual explanations), but I have mixed feelings on the effectiveness of disjoint explanations in practice.

B) A drawback of this work is the complete absence of human-based evaluation. I acknowledge explainable AI literature is ripe with examples of accepted papers, but the authors seem to deliberately disregard this aspect (“We [.. ] are not interested if an explanation is congruent to human understanding", Sec1). If humans are not important, then what is the reason you explain your predictions? If the goal is limiting to debugging a model, perhaps the narrative should be revisited. All in all, I believe users should be central in an XAI piece, and papers in this area should help the reader understand if the generated explanations meet users expectations - even in a ML conference such ICLR, even for a 8-page paper.

C) The paper does not include any examples of the generated explanations. It is hard to figure out if the claimed fidelity brings meaningful results in practice, and the reader is left with this doubt. Aside from a full-fledged evaluation campaign (see A. above), some examples would really help make the case. 

D) Experiments do not include any evidence of whether ZORRO explanations work in practice. Besides, as I mentioned above, the author should probably clarify which audience they are targeting (i.e engineers debugging a model, end users trying to understand the reasons for a specific model outcome, etc.)

E) I was expecting experiments to assess the impact of \tau (the user-defined fidelity threshold). The authors experiment with .98 and .85 - and “the choice of \tau has limited influence”, but I would have expected empirical evidence for such statements (i.e. experiments on a wider range of \tau, to assess size and fidelity). If choosing a desired fidelity is not crucial, the paper should show so.

F) There are not experiments on runtime complexity. The reader is left without evidence of how long it takes to generate an explanation for a target prediction.

G) It is unclear if ZORRO achieves more faithful and also smaller explanations than GNNExplainer. Sec 4.2 suffers from clarity issues, as long as Figure 5.

H) Some sections could be better clarified, to help the reader understand important aspects of the work: Example: In sec1, the “notations” paragraph would benefit from proofreading and re-wording. Sec 4.2 could also be refined.

Minor:
* Size matters for explanations, but smaller does not always mean better. For example, in medical decision support systems, some clinicians may prefer longer and more thorough explanations. Your milage may vary. 
* Figure 5 is poorly legible.
* Some typos along the way (e.g. “denotes the binary column vector of selected nodes and Fs denote the binary row vector of selected nodes “ sec 1, “Effectively the complete input is presented as an input” in 4.2)

Questions for the authors:
* Q1) How does ZORRO decide the size of each computational graph to work with (i.e. the size of the neighbourhood)?
* Q1) It is not entirely clear to me how you ZORRO generates multiple explanations? I could not find how this is done in Algorithms 1-3. Could you please clarify?
review_title: Interesting method - but no empirical evidence of whether explanations are meaningful

final_score: rating: 4: Ok but not good enough - rejection
review_content: This work proposes to explain graph neural networks using hard masking techniques. Specifically, it tries to find the node mask $V_s$ and feature mask $F_s$ which can identify the most important information of the input such that the masked information can yield a high fidelity score. This work proposes a greedy method, ZORRO, to explore these hard masks, which can be used as the explanations of the prediction. Experimental results are interesting and promising.  

Strengths:
+ The task is very important. GNNs are very popular but they are mostly treated as black-boxes. Interpreting GNNs is still less studied.
+ Compare with GNN-Explainer, this work focuses on using hard masks to explain GNN predictions. It is a reasonable choice since soft masks, which are used in GNN-Explainer, may introduce new semantic meaning or noise to the node representations since these representations are very sensitive.
+ Experimental results are very interesting. First, there exist multiple explanations for the same input graph that they both lead to high fidelity scores. Second, the proposed method can obtain high fidelity scores than GNN-Explainer and more sparse explanations. In addition, this works studies several types of GNNs, such as GCN, GAT, GIN, APPNP.

Weaknesses:
- The connection between the proposed method and data compression is not convincing. From my understanding, it belongs to the masked-based interpretation methods, which is widely studied in other domains, such as image and NLP. Then I do not think it is something new from other fields--data compression in information theory.
- In the proposed method, all nodes share the same feature mask $V_s$. Is it a proper choice? Is it possible that different nodes may have different important features? Then probably it is better to not share the $V_s$?
- In the proposed method, the ordering information $R_V$ and $R_F$ are stored. It is computed in the beginning and keep fixed for later steps. However, in the later steps, the algorithm will update the $V_S$ and $F_s$, then why do we use the same ordering information? Top nodes, in the beginning, may not be top any more after some nodes/features selected?
- The method itself is very straightforward, which is a simple greedy algorithm. Then I believe the technical contribution may not reach the bar of ICLR.   
- The algorithm is not clearly explained. What’s the meaning of $V_r$, $F_r$, $R_{V_p}$, and $R_{F_p}$, etc.? How are they initialized?
- For the comparisons with GNN-Explainer, we need to see some real examples—explanations for both correct predictions and incorrect predictions. It is not enough to just report numerical numbers.


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

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

I have read the authors' rebuttal. However, my concerns are not well addressed. 

1. There are a lot mask based methods for interpretation in different domains [1] [2] [3] [4]. Existing methods [1][2][3] are providing post-doc explanations for a pretrained model. I still believe "the connection between the proposed method and data compression is not convincing". 

2. I still believe the novelty is limited. 

Hence, I am keeping my score unchanged. 

[1] GNNExplainer: Generating Explanations for Graph Neural Networks, NIPS 2019

[2] Real Time Image Saliency for Black Box Classifiers, NIPS 2017

[3] Learning to Explain: An Information-Theoretic Perspective on Model Interpretation, ICML 2018

[4] Rationalizing Neural Predictions, EMNLP 2016

review_title: Official Blind Review #1

final_score: rating: 5: Marginally below acceptance threshold
review_content: The authors address the problem of explaining the behaviour of graph neural networks (which operate on a computation graph based on their k-hop neighbourhood) such as a graph convolutional network (GCN). 

The core idea is to identify, for each node v in the graph, the nodes and features of the graph most relevant to the behaviour of the GNN for node v. That is, the goal is to find a subgraph of the computation graph associated with a node v in the graph. Importantly, the authors propose to test whether the chosen subgraph is relevant (and the complement wrt the computation graph irrelevant) by adding random noise on the parts deemed irrelevant by their method. 

The method is evaluated through a metric called fidelity, which is the agreement in label output between the behaviour of the original and masked GNN, in expectation over the noise distribution. 

While overall a well-written paper, a source of confusion is the authors tendency to conflate the computation graph and the graph to which the GNN is applied. The most important notion here is S, defined as a subset of the computational graph. When defining this, it is important to also define precisely this computation graph. What does it look like (abstractly, independent of the GNN instance used)? For instance, there is a nice compact way to unify most message-passing neural networks. (see e.g., https://pytorch-geometric.readthedocs.io/en/latest/notes/create_gnn.html) 
When you look at this definition, you see that there are several learnable functions (phi, etc.), the aggregation function, and finally the classification layer. Now, in your definition of a computation graph, what are the nodes? Are the applications of the learnable functions each a node? What about the aggregation (one node?). Again, I think for the reader to fully understand how your explanations S look like, this needs to be rigorously defined. My assumption here was that the computation graph groups computations such that nodes in the computation graph and nodes in the graph to which the GNN is applied coincide. Generally, I think you should spend more effort on section 3. The notation in the argmax statements in section 3.1 is also strange. For instance, S is defined as a pair. So it should be written as argmax F((V_p, {f})). Also, what is the p here? 

Another worry I have is the efficiency of the approach. If your average number of features and nodes that exceed the fidelity threshold is K (the average size of S) and the graph has N nodes and F features, you need to evaluate the GNN KN+KF times to obtain an explanation for one node. For large graphs and/or graphs with numerous features, this can be expensive. And this is for the case when you compute the expectation with one Monte-Carlo sample from the noise distribution.

The most disappointing aspect of the paper, however, is the experimental evaluation. Sure it is interesting to assess the multiplicity and size of explanations. What would be more interesting, however, is to evaluate how faithful your explanations really are. And here is where I have a disagreement with your assumptions. You write “[...] that is completely faithful to the model i.e., the explanation achieves the fidelity value of 1.” But achieving a fidelity of 1 does not mean that your explanation is faithful. We could only know this if you removed the nodes and features and retrained the model with the same seeds/initialization. There is an intricate interplay between the nodes and features during training of a GNN. What you evaluate is how close to the original behaviour the GNN is when you remove certain nodes and features. But I would question whether this is a proper definition of faithfulness. 

My suggestion would be to also run experiments where you retrain GNNs and check whether the behaviour is indeed such that removing the nodes and features your method deems unimportant leads to a minor change in behaviour. 

The synthetic experiments of the GNNExplainer paper are not included. But it makes sense to me to define synthetic graph classes where the presence of certain features/nodes is known to cause the node label by construction. This way one can check whether those features are the ones identified by the XAI method. I would encourage the authors to also run these experiments and compare to the results from the GNN explainer. 

Finally, it is not entirely fair to compare other methods to yours through the notion of fidelity alone. Your method is defined to optimize for it. As I mentioned above, fidelity is one way to measure the quality of a reduced graph but not the only one. It is by no means the only one to measure “faithfulness,” as I have outlined above. For instance, it would also make sense to compare based on the measures introduced in the GNNExplainer paper. 

review_title: Method for explaining GNN behaviour with room for improvement 

Meta-review: The paper provides a simple approach to explaining GNN predictions for each node by greedily selecting nodes or features in each computation graph so as to increase the fidelity score. The fidelity score is based on comparing the original GNN output to what is obtained with noisy versions of the masked nodes/features. While simple, the approach seems somewhat inefficient (efficiency should be assessed/characterized). Also, several improvements to the evaluation expressed in the reviews/discussion (e.g., human evaluation, practical utility, comparison to gradient based methods) would make the submission somewhat stronger. 

Decision: Reject