Venue: NeurIPS 2022 Conference

Reviews:

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 paper presents a framework CLEAR to generate counterfactual explanations on graphs. This framework can be helpful for promoting explainability in graph-based prediction models. Specifically, the authors use a graph variational autoencoder to generate the counterfactual graph and employ independent component analysis (ICA) to find causal relations. The generative counterfactual graphs have generalization ability and causality. Experiments show that CLEAR achieves promising performance in various evaluation metrics.
strengths_and_weaknesses: Originality: The paper employs two existing technologies, i.e., graph variational auto-encoder and ICA to generate the counterfactual graph. Although the two components are not new, the topic is novel. One of the contributions, optimization, is not original. Many works have employed various models to generate graphs by gradient-based optimization instead of enumeration, such as GNNExplainer, [1], and [2]. Existing works have proposed many methods, such as information flow [1] and Markov blanket [2], to identify causality among latent variables. What’s the merit of ICA over these existing methods? 

Quality: Technically sound with well-supported claims.  However, the following issues are suggested to be further considered: 1. The evaluation metrics are not sufficient. One important metric for explanations is human interpretability requiring the generated explanations should be compact. The authors should investigate human interpretability. 2. In addition, counterfactual explanations may be used to defend against attackers. The authors are encouraged to conduct experiments on graphs generated by the adversarial attacks to verify the effectiveness of generated counterfactual explanations. 3. The work lacks the evaluation of generalization on the unseen graph.

Clarity: Overall, the paper is well written and easy to understand. However, the following issues need to be clarified. 1. The motivation behind employing ICA to find causality is not clear. 2. Why the team culture is not the cause of grant application in the example of the Preliminaries Section? 3. The grant application example for describing causality in counterfactual explanations is confusing. It is advisable to describe it in mathematical form.

Significance: The method proposed in this paper would be helpful to give counterfactual explanations and promote explainability in graph-based data.

[1] Lin, Wanyu, et al. "Orphicx: A causality-inspired latent variable model for interpreting graph neural networks." Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2022.

[2] Yang, Shuai, et al. "Learning causal representations for robust domain adaptation." IEEE Transactions on Knowledge and Data Engineering, 2021.


questions: 1. The merits of ICA over the existing methods in identifying causality should be highlighted.
2. One important metric for explanations is human interpretability requiring the generated explanations should be compact. The authors should investigate human interpretability.
3. Counterfactual explanations can be used to defend against attackers. The authors are encouraged to conduct experiments on graphs generated by the adversarial attacks to verify the effectiveness of generated counterfactual explanations.
4. The experiments can not well support the claimed contribution in generalization. How to evaluate the generalization ability on unseen graphs? The work lacks the evaluation of generalization on unseen graphs.

limitations: There are no potential negative societal impacts.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: In this work, the authors study the problem of generating counterfactual explanations for graphs using Graph Neural Networks (GNN). In contrast to some existing studies, the work lists three unaddressed counterfactual properties, i.e., i) discrete optimization of graphs, ii) generalization of counterfactuals on unseen graphs, and iii) ensuring causality in the generated counterfactuals without prior knowledge of the causal model. The work leverages a graph variational autoencoder-based framework to propose CLEAR (generative CounterfactuaL ExplAnation geneRator for graphs) that ensures the optimization and generalization of discrete counterfactual explanations for graphs and enforces causality by using an auxiliary variable for estimating the underlying causal model better.
strengths_and_weaknesses: Strengths:
1. The paper nicely enumerates three important desiderata for counterfactual explanation generators for graphs and describes their utilities with respect to counterfactual explanations.
2. The formulation of the objective for the CLEAR framework is clearly explained with proper derivations and descriptions of the individual components.
3. Extensive experiments with both synthetic and real-world graph datasets highlight the effectiveness of the CLEAR framework as compared to the baselines and show the utility of its components.

Weaknesses and Questions:
1. One of the major drawbacks of the work is that they don't detail the perturbation mechanism used for generating counterfactuals. They mention that: "CLEAR aims to generate counterfactuals with slight perturbations on the explainee graph to elicit a desired predicted label" but does not describe the perturbation process. This is crucial for understanding the framework as one of the main challenges in evaluating the reliability of generated counterfactual explanations is efficiently perturbing the input data. The perturbation process for generating similar graphs using very small perturbation is unclear, i.e., how to generate perturbed instances that are not out-of-distribution samples. 

2. It is unclear from Section 4.7 and Appendix C.2 how the generated counterfactuals using CLEAR promote model explainability. The observation that the framework makes correct perturbation to achieve the target label by visualizing the degrees across the decision boundary is intuitive and shown in multiple previous works.

3. The proposed CLEAR framework uses a generative backbone CLEAR-VAE and claims that it can generate counterfactual explanations for unseen graphs. However, it should still require graphs to belong to the same distribution as the training data.

4. The paper details the problem of optimizing counterfactual explanation on graphs due to its discrete nature but then follows the optimization trick used by previous works for generating a counterfactual adjacency matrix.

5. The use of GNNExplainer as a baseline is unclear. The author assigns the given graph label to all the nodes inside the graph. It would be great if the authors explain this a bit more. Are they assigning the same label to all nodes and then generating explanations for a given node? Or are they aggregating all node explanations to generate a graph-level explanation?

6. It would be great if the authors can motivate using causality metric for comparison. It feels that the metric is biased towards the proposed framework as the auxiliary variable can provide additional information to identify the exogenous variables in the structural causal model, which is captured by the CLEAR-VAE training process.
questions: Please refer to the Strengths and Weaknesses section for questions.
limitations: Yes.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The authors present a counterfactual generation method for graphs. The proposed method (CLEAR) aims to perturb a given graph in a way that is still close to the original while changing a classifier prediction and respecting the causality in the data generating process. This is achieved by training a graph VAE conditioned on the target label and an auxiliary variable $S$ used by the original data generating process (an SCM), which helps to identify the causal model. The overall loss encourages counterfactuals to be close (wrt a distance metric) to the original graph while achieving the desired label ($Y^*$) and inferring the correct latent structure by keeping the latent codes $Z$ close to a distribution that is conditioned on $S$ and $Y^*$. In experiments they show that the proposed method achieves a higher number of valid counterfactuals that are more proximal while keeping causal relations than previous state of the art. They also provide an ablation study on the different parts of their model.
strengths_and_weaknesses: Overall Review
===========
Overall, this paper tackles an important problem, the method is sound, and the results are encouraging. Some points could be improved, such as motivating the need of graph counterfactuals, or checking whether the model is repeating the same counterfactual three times. Therefore I recommend "Weak Accept" and I would be happy to raise the score based on the rebuttal and the other reviews.

Strengths
=======
* The problem of understanding the behavior of ML systems is an important one.
* The proposed method is sound and it performs better compared to previous state of the art.
* The authors provide the code, ablations, and information for reproducibility.

Weaknesses
=========
* This work focuses strongly on the method and comparison with previous state of the art but it lacks a bit of perspective on what is the final purpose of this research. Some more motivation in the introduction and some qualitative results showing interesting findings on a real graph would make this work more appealing. I like the example in Section 2, so you can focus more on motivating the problem in general rather than giving more examples in the introduction.
* In the ablation study there is no clear difference between VAE and CLEAR. (The difference is, however, more clear on Figure 4).
* Since the proposed method predicts 3 counterfactuals, it could just predict three times the same (or very similar) graph. This would improve the validity metric while not adding any additional value to the user. Several recent works focus on providing a set of diverse [28, A, B] and non-trivial explanations [C] (unexpected failure modes of the model), that are more useful for the end user. In fact, in Appendix D, the authors acknowledge that optimizing for diversity is a current limitation, but it would be interesting to study whether the VAE is repeating the same graph or producing different graphs. 

[28] Mothilal, Ramaravind K., Amit Sharma, and Chenhao Tan. "Explaining machine learning classifiers through diverse counterfactual explanations." Proceedings of the 2020 conference on fairness, accountability, and transparency. 2020.

[A] Smyth, Barry, and Mark T. Keane. "A Few Good Counterfactuals: Generating Interpretable, Plausible and Diverse Counterfactual Explanations." arXiv preprint arXiv:2101.09056 (2021).

[B] Hvilshøj, Frederik, Alexandros Iosifidis, and Ira Assent. "On Quantitative Evaluations of Counterfactuals." arXiv preprint arXiv:2111.00177 (2021).

[C] Rodríguez, Pau, et al. "Beyond trivial counterfactual explanations with diverse valuable explanations." Proceedings of the IEEE/CVF International Conference on Computer Vision. 2021.



Detailed comments
===============
Originality
-----------
The proposed framework, and particularly the focus on causality preservation when generating counterfactuals, are novel to the best of my knowledge.

Quality
--------
The technical and written quality are good, assumptions are clearly stated, and proofs are provided in the Appendix.

Clarity
-------
Overall, the text is well-written and easy to follow. In section 4.7 I believe that references to Figure 8 should be to Figure 4. In Section 4.8 it is not clear why you do not test $0.1$. Many times you talk about preserving causality and, without any context, it is not clear if you mean that you are reconstructing a causal graph (with directed edges) and you want to preserve edge directions, or if you want the generated graphs to be compatible with the original SCM. After some time reading it becomes clear but it would be better if you made it more clear since the beginning. 

Significance
--------------
Given the increasing impact of machine learning applications in our lives, it is important to better understand how models make their predictions. However, the text does not fully transmit the significance of this work. 

Reproducibility
-----------------
The authors provide code, equations, and the necessary assumptions to reproduce their results.
questions: * Could you better motivate the counterfactual explanation problem in the introduction and the abstract? The idea is that the reader gets the "big picture" before you focus on the concrete problem of improving graph counterfactual methods.
* Could you verify whether your model is or not producing the same counterfactual 3 times? (if it does it is ok, but I think this is important information for the reader to have)
* Could you clarify what causality you want to preserve? (see clarity above)
* Why did you skip 0.1 in the hyperparameter sweep? (see above)
limitations: Yes, the authors include a section in the appendix.
review_title: null

Meta-review: metareview: This paper proposes a new method for producing counterfactuals on graphs. This is performed using a VAE on graphs with auxiliary variables to identify independent components and promote causality. While this work is mainly a combination of existing ideas, the resulting method is not trivial. 

The engaged discussion clarified most of the concerns except a remaining concern around the diversity of the explanations. The reviewer was encouraging to measure (or optimize for) the diversity of explanation. That is, explanations that are significantly different (e.g. orthogonal from each other) in latent space. This is not a ground for rejection but it could improve this work and we encourage the authors to add this feature. 

I recommend acceptance of this paper. 


confidence: Certain
Decision: Accept