Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper aims to generate valid counterfactual examples (CFE) in a dynamic setting where the model can be retrained in the test time. The goal is to minimize the invalidation rate. Different from previous work, they focus on DNNs. Through a series of theoretical analysis, they propose to maximize the confidence and minimize the Lipschitz constant under the constraint that the CFE x' and x share the same predicted label.  Experiments on tabular datasets show the proposed method reduces the invalidation rate a lot.

main_review: ## Detailed summary
While previous work finds a little higher counterfactual loss leads to lower invalidation rates in linear and well calibrated models. This paper focuses on deep NNs and show that with deep models, this may not hold as higher counterfactual loss does not mean CFE is further from the decision boundary, which invalids the conclusion in linear/well calibrated models. Theorem 1 shows that there exist data points x and x', and decision boundaries H1 and H2 s.t. x' is on H2 but is further to H1 than x, due to the complex decision boundary of DNNs. Lemma 1 further verifies this by showing if x' does not exist, then H1=H2.

It proposes distributional influence (DI), which uses gradient information to explain local decision boundaries (around a sample). Distributional influence is defined as the expected gradient of the output against the input in the local neighbor region of x ($\mathcal{D}_x$).

They find a bound on the change of DI in terms of the model's Lipschitz continuity on the support of $\mathcal{D}_x$. This means finding a high confidence CFE with low Lipschitz constant would likely to have lower invalidation rate. Based on this, they propose to maximize the confidence while minimize the Lipschitz constant under the constraint that the CFE x' and x share the same predicted label. This is transformed into eq.(4) by Proposition 1, where the second term is the maximal slope in Figure 2b. This is further simplified to eq.(5).

In experiments, they use UCI datasets, FICO HELOC and Warfarin Dosing. Note that only binary labels can be used. Results show SNS can lead to much lower invalidation rate. And SNS would lead to a higher counterfactual loss in general, as expected.

## From the above, the strength includes
1. Clear theoretical justification of the proposed method, although there are some imperfections.
2. Good presentation and visualization (e.g., Fig. 2).
3. Relative comprehensive results, considering various datasets, baselines and metrics.

## Weakness includes
1. Only relatively small tabular datasets are used, which is not the most widely used case for DNNs.
2. Some details may need to be further clarified.

# Questions and detailed comments:

How to compute the integral of SNS, what would be the complexity?

There is no causal model built and therefore, why the CFE in this paper is a counterfactual. If it is, which counterfactual distribution is it sampled from?

What is a the x-axis and y-axis of Fig 2? I guess they are two input features but it is better to show them in the figure.

It is not very clear to me which terms are related to confidence in the equation of Theorem 2.

I did not fully get why small change in DI always means low invalidation. I guess this has to be shown formally.

We know DNNs tend to be over-confident for unseen x. Would this result in any issue if we aim to find CFE with high confidence?

What is the effect of relaxing the Lipschitz constant K from the penultimate output to the entire network? Would it increase or decrease, why?

It is better to clarify what is $t$ in Fig 2 since it is only defined in the later pages.

Typo in page 6. zero vector (t=1) --> (t=0)


summary_of_the_review: Copied from above.

## Strength
1. Clear theoretical justification of the proposed method, although there are some imperfections.
2. Good presentation and visualization (e.g., Fig. 2).
3. Relative comprehensive results, considering various datasets, baselines and metrics.

## Weakness
1. Only relatively small tabular datasets are used, which is not the most widely used case for DNNs.
2. Some details may need to be further clarified.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors study how counterfactual explanations of a Deep Neural Network change if the initial training settings are slightly changed. They find that even small changes in the initial training settings lead to huge differences in the counterfactual explanations. They propose a method for computing more robust (i.e. consistent) counterfactual explanations.
main_review: Pro:
 - Interesting and relevant topic
 - Well written (good structure and easy to follow)
 - "Sound" evaluation

Cons:
 - Relevance of counterfactuals could be made more prominent (in the introduction). Why are they so popular? etc.
 - Sec. 4.2 limited to changes in the top layer. I understand that some simplifications are necessary but this particular simplification seems very strong to me.
 - Implementation of SNS: The authors use 10 points to approximate the integral. Why exactly 10? How does the method behave for different number of points? This specific number looks like a magic number that needs further explanations.
 - I miss some comments on the computational complexity of the proposed method (SNS)
summary_of_the_review: Overall an okay paper with only minor (not too critical) issues as pointed out in the main review.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The authors propose a regularisation method that offers increased stability on counterfactual predictions when models are affected by small changes during deployment . The method is based upon a K-Lipschitz constant.
main_review: The paper presents a nicely thought out method on providing points on a manifold that are robust to small sometimes imperceivable  changes on the training parameters. 
However, the reviewer believes that the claims relating to counterfactual are based upon a not so accurate interpretation of causality. 
Firstly I would invite the authors to substitute definition 1 with the appropriate counterfactual definition from the textbook by J. Pearl, 2009, chapter 7. 
Moreover, I am under the impression that the problem of producing non robust counterfactuals is rooted to the fact that the methods explored by the authors do not impose any identifiability constraints that would guarantee the models learning the intended DAGs and producing accurate counterfactuals. As such I fail to understand the expectation that the models should produce correct and robust counterfactuals when there is no explicit constrain on the models to do so. The method proposed in this paper does not refer not attempt to solve any of the aforementioned points
Counterfactual stability in categorical variables , effectively a similar outcome to this paper, was already already explored in [1].

I would invite the authors to look into the field of identifiability and robustness when the appropriate causal inference methods are used and constraints enforced 


[1] Counterfactual Off-Policy Evaluation with Gumbel-Max Structural Causal Models; Oberst and Sontag ; ICML 2019
summary_of_the_review: Overall the paper has merit in terms of identifying examples that are robust upon small changes in the training procedure. The claims regarding to counterfactuals, explainability and causality I believe are a stretch. As such I recommend that the paper is changed such that it is in the proper context
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper focuses on the consistency of counterfactual explanations (i.e., the rate at which counterfactual explanations transfer across different models). The authors show that the consistency of counterfactuals does not necessarily relate to cost (i.e., the distance between input and the counterfactual). They propose an alternative theory: they investigate the relationship between local Lipschitzness and consistent counterfactuals. Based on this idea, they propose a new method (SNS) for generating counterfactual examples. Empirically, they show that SNS creates more consistent counterfactuals than van Looveren et al. and Pawelczyk et al.
main_review: **Novelty/Contribution**:
To the best of my knowledge, the consistency of counterfactuals has not been extensively studied. In my opinion, the main novelty is proposing Stable Neighbor Search (SNS), which finds counterfactuals in more locally Lipschitz regions. The results for SNS are promising -- it outperforms the benchmark methods (Van Looveren and Pawelczyk). 

A second contribution is the discussion of the relationship between Lipschitzness and counterfactual consistency. This contribution is less significant, in my opinion, as it is similar to discussions in the field of adversarial examples. In adversarial example literature, it is well-established that improving the Lipschitzness of a network will improve its adversarial robustness. 

**Correctness**:
Generally, I believe that the central argument of the paper is correct: generating counterfactuals in areas where the network has a smaller Lipschitz constant improves the consistency of counterfactual explanations. However, I am not sure whether the proof of theorem 2 is correct. There are some steps that require further clarification.

Specifically:  
-  what property are you using in the step from lines 35-36 to 37-38? $E(ab)=E(a)E(b)$ requires $a$ and $b$ to be independent, but it's not clear to me why that holds in this case. 
- line 46: $d\sigma (x,w)$ can be both positive and negative, right? As such, I think there should be an absolute value sign around $d\sigma (x,w)$. 
- some unclear notation: $g$ is not defined in the main text -- is it the same as $f$?


**Writing**:
Overall, very well written and easy to follow. However, I do think the authors over-state some contributions in the introduction. For example,
"we prove that counterfactual examples in a neighbourhood where the network has a small local Lipschitz constant are more consistent against changes in the training environment (Theorem 2)". Theorem 2 assumes (1) only a change in the final layer weights and (2) a relu network with a final sigmoid activation. The authors are explicit about this later on, however, I think the introduction should be written more carefully.


**Minor language/formatting suggestions**: 
- Section 3: " ... counterfactuals produce inconsistent outcomes in duplicitous models up to 94% of the time"  This sentence reads as a fact, however it's shown empirically for a specific set of hyperparameters/datasets. There are likely cases when it holds for 100% of the time. As such, perhaps rephrase it as "counterfactuals often produce inconsistent outcomes. Empirically, we've found that it occurs up to 94% of the time."
- Section 4.2, sentence 1: "characterizing the precise effect such as random initialization have on" -> "characterizing the precise effect of hyperparameters, such as random initialization, have on"
- Theorem 2: space missing between w and are in the statement, and a "." instead of a "," after forall $w' \in W$. Perhaps define $h$ as a ReLU network, rather than $f$. The latter makes it easier to read (I was a bit confused about the sigmoid activation/ relu network for a moment).
- Appendix, Proof Theorem 2. Page 16: for the equation numbering, (34), (36) and (38) should not be there. This can be remedied by using * or align in latex.
- the definition of distributional influence should contain w in the main text (to be consistent with the appendix) 

----- 
Post-rebuttal update: I have increased my score as the authors have corrected their proof for Theorem 2. 
summary_of_the_review: 
Overall, I like the paper and enjoyed reading it. However, I am currently recommending a 5 as I am not convinced by the correctness of the claims in the paper. Specifically, I have some concerns about the validity of Theorem 2 (elaborated upon in my main review). If the authors are able to clear up this aspect, I'm happy to reconsider my score.
review_title: null

Meta-review: Most of the discussion centered around whether the underlying question in the literature is setup correctly in terms of its relationship to causality as the question being asked is one of an intervention. The underlying literature makes an attempt at not including things that can't be intervened on like age, but the setup of a "counterfactual" could benefit from a causal take.

Holding that aside, the paper makes progress on an established question though analysis that reveals that the Lipschitz continuity and confidence are important for causality and Stable Neighbor Search for generating counterfactuals.

The most negative reviewer in discussion writes that they're okay with the paper being accepted if the rest of the reviewers are positive. The rest of the reviewers are positive with one mentioning that the paper is well written and interesting in the discussion and that the author replies cleared up the issues about counterfactuals.
Decision: Accept (Poster)