Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: Context: Counterfactual explanations are a way to locally interpret model decisions for a given input by finding a "nearby" input with a different model decision. As in this paper, we can interpret some distance measure between the original input and its "counterfactual explanation" point as a kind of cost of achieving a different decision, usually for/to an individual who gets a negative decision to understand what they would need to change to receive a positive decision. In a fairness context we can consider differences in such costs between different groups as evidence of unfairness, for example if there are higher costs (on average, say) for individuals from a protected non-discrimination group.

The current paper shows that for a certain class of algorithms producing counterfactual explanations, it is possible for a small, adversarial perturbation of the input to produce a dramatically different explanation. The paper points out that this non-robustness of the algorithms in consideration is important from a fairness or regulatory standpoint by simulating a scenario where a model builder can jointly train a classifier and adversarial perturbation so that an auditor relying on counterfactual explanations (using any of the algorithms in consideration here) can be deceived. The paper shows how to train such models that can hide unfairness by providing a low-cost explanation for a nearby point relative to the higher cost explanation of the original input, and demonstrates the concept with experiments using two datasets and four different counterfactual explanation algorithms in the literature. Experiments also show how to achieve robustness by changing the initialization point for the counterfactual explanation algorithm, by reducing the dimension of the input space, or by otherwise constraining the complexity of the classification model.
main_review: Originality: This paper adds to a literature of others discussing the shortcomings of so-called counterfactual explanations, and to the list of papers showing that adversarial training can reveal shortcomings of a given class of algorithms. But I believe the combination/intersection is original, i.e. to my knowledge it is the first to directly apply adversarial training in such a setup to produce explanations with lower cost and thereby hide unfairness. 

Quality: The results are sound and well-supported by the experiments, the work is mature and relatively complete, and the paper is honest about its assumptions and limitations. 

Clarity: The paper is clearly written and informative.

Significance: The result is very important for the reason that the limitations of counterfactual explanations must be analyzed and become well-known to prevent their widespread misuse.

Suggestions: In my opinion there are two things that could improve the paper. The first, and most important, would be to shift the fairness part of the focus away from "how to train a model that can hide its unfairness" and toward "how to determine if a model is hiding unfairness." The best version of such a shift would require significant revision, possibly including changes of the auditing setup to require different access. The problem is that the paper currently has in-depth instruction on how model owners with bad motives could do something destructive and unethical, with a brief follow-up of some methods that model owners or auditors with good motives could try to avoid this problem. My second suggestion is a minor one and concerns the term "counterfactual explanation." It is an unfortunate fact that a sizeable literature has already adopted this term despite the fact that it misuses the word "counterfactual." There is no explicit causal model or even philosophical assumption from which these explanations justify their use of the word, it is just comparing one input point to another input point. Several of the papers on the limitations of this approach point out this fact, including ones cited in the current paper. I think it might be helpful if the current paper (and any others that continue misusing the term "counterfactual") have some disclaimer early on (e.g. in the introduction) regarding the absence of an actual causal model justification for using the word. This could help some readers avoid confusion. 
limitations_and_societal_impact: No. In addition to my first point under the "Suggestions" above, this paper also uses a crime prediction dataset for one of its experiments without acknowledging the potential dangers and shortcomings of such a task that have been extensively critiqued in other algorithmic fairness papers.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper presents a new research problem regarding the vulnerabilities of counterfactual explanations, and introduces an adversarial model/framework to demonstrate the vulnerabilities of existing algorithms which employ hill-climbing to find counterfactual explanations (and initialize the search at the original data point). Some mitigation strategies for improving the robustness of this type of counterfactual explanation algorithms are also presented.

The work shows that the proposed adversarial model can pass the (recourse) fairness assessments which rely on counterfactual explanations produced by the counterfactual explanation methods using hill-climbing, but in fact is not a fair model as if the other features of an input instance from the non-protected group is perturbed slightly, the counterfactual explanation generated for the instance can be biased (i.e. having a much more desirable recourse). This result demonstrates the potential problem with the counterfactual explanation methods and the fairness assessment scheme based on counterfactual explanations.
main_review: Please find below my detailed comments on the originality, significance, quality, and clarity of the paper.

1. Originality and significance

The problem raised and studied in this paper is novel and has important practical implications for the applications of counterfactual explanations. The proposed adversarial model for demonstrating the problem is also very interesting and convincing. 

2. Quality

The proposed framework/adversarial model is sound and the experiments have shown that it is possible for the manipulation to happen. 

Some questions for consideration though, and some discussion on them may strengthen the paper:

(a) In the experiments feed-forward neural networks are used as adversarial models, and convincing results are obtained based on the models. I wonder how would the results would be if other types of machine learning models are used? Perhaps related to this, in theory, is it always possible or does it require similar effort for the manipulation to succeed, i.e. to obtain the "arbitrary" function f?  Some more discussions on the conditions for the success of the manipulation would be good.

(b) How sensitive the success of the manipulation is to the value of \delta? That is, how the cost reductions in Table 1 would change if we change the value of \delta (around the discovered \delta value)?

(c) Is it a practical assumption that an adversary knows which counterfactual explanation algorithm, \mathcal{A} is used by an auditor? I am not familiar with the practice, but I would guess an auditor would keep such sensitive information away from the organization being audited. 

(d) Is Definition (2.1) a commonly used measure for assessing recourse fairness? If yes, a reference should be added. If not, some discussion may be needed as to why average distances are used and how the use of average distances (instead of other measures) would affect the design and success of an adversarial model. 

3. Clarity

Overall the paper is well written and easy to follow. Below are some minor comments:

(a) About notation: At quite a few places, x^q and \delta are not bold-faced. Please check and correct.

(b) Line 154, page 4: the statement here about x+\delta is understandable, but stating that x+\delta should be "a" counterfactual may be confusing, as readers might get x+\delta and A(x+\delta) mixed up. I could be wrong, but I understand that as indicated in Figure 1, x+\delta does not have to be a real counterfactual as A(x+\delta) is, although the objective of the adversarial model aims to minimize the expectation shown in this line.

(c)  typos: 

*Caption of Figure 1: is higher cost -> has higher cost

*Line 78, page 3: an historically -> a historically

*Line 112, Objective 2 --> Objective in Eq. (2) ?

*Line 208, page 6: State -> States
limitations_and_societal_impact: The authors have touched on the societal impact of the work, but since the paper proposes an adversarial model, it would be good to mention the potential negative impact of the adversarial model (e.g. someone might exploit the model/idea to design their own adversarial attacks for bad purpose).
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper investigates the robustness of existing counterfactual explanation algorithms in terms of bias attributes. The method and experiments make sense.
main_review: The writing is clear and easy to follow and the proposed method is simple yet sound. Just curious if any idea to generalize the method to high-dimensional data like the Image domain.

-------------post rebuttal---------------

After reading other reviews, I'd like to maintain my original score.
limitations_and_societal_impact: yes
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper shows that algorithms used to generate counterfactual explanations are subject to manipulation. The authors provide a technique to adversarially train models that produce unstable counterfactual explanations as well as strategies to mitigate this manipulability.
main_review: The setting being considered here is somewhat contrived, in my view. It supposes that someone building a classifier is required to ensure that the cost of recourse will be equal across two groups, and that an auditor will verify this. However, the entity building the classifier is a bad actor and wants to fool the auditor while actually producing a classifier that has a lower recourse cost for the non-protected group. I'm not convinced that "equal recourse cost" is a meaningful notion of fairness to consider, especially in the Communities and Crime dataset analyzed here. But I'm open to pushback on this.

One major issue I see is that the authors' definition of unfairness appears to require 2 things:
- Roughly equal recourse costs for 2 groups
- Substantial reduction in recourse cost for one of the groups when perturbed by $\delta$
What this doesn't cover is the change in recourse cost for the "protected" group when perturbed by $\delta$ -- if this also results in a similar reduction in recourse cost, then I don't see why this should be considered problematic. This might be possible to address by adding a term to the objective.

Beyond this, the paper is well-written and quite thorough. The experiments provided are natural, and the authors make sure to include robustness checks. They also evaluate a number of mitigation strategies.

Other small comments:
- $G(\cdot, \cdot)$ is used in Lemma 3.1 but I can't find where it's defined -- I assume it refers to the objective in Equation 2.
- It seems strange to refer to it as "Wachter's algorithm" when there are 3 authors on the paper cited.
limitations_and_societal_impact: The authors haven't explicitly discussed potential negative impacts. Given that the paper provides techniques to learn models that look benign but have undesirable social properties, the authors should include such a discussion.
review_title: null

Meta-review: This paper contributes to the growing literature documenting the instability and manipulability of different model explanation techniques.  In this work the authors specifically study counterfactual explanations, which commonly describe how an individual's inputs could change to receive a positive classification.  Overall the reviewers agree that the specific problem formulation tackled in this work is novel and that the work improves our understanding of how models can be adversarially manipulated to produce biased recourse costs by hiding low cost recourse paths.  Reviewers also agreed that the paper is well-developed, overall clearly written, and comprehensive.  

The authors have already proposed additional text discussing the implications of developing adversarial models and issues with the common practice of relying on crime-related data in experiments.  Beyond this, the set of revisions in preparation for the camera-ready is fairly small.  For readers who are unfamiliar with the prior literature on "counterfactual" explanations, I agree with Reviewer EEmF that it would be work clarifying that the term "counterfactual" doesn't have the same meaning here as it does in the context of causal inference. Other reviewers provided lists of requested clarifications/modifications that are all actionable and would improve the clarity and accuracy of the manuscript.

Congratulations on an excellent submission! 
Decision: Accept (Poster)