# Feature-based Learning for Diverse and Privacy-Preserving Counterfactual
Explanations

Vy Vo  Monash University, AustraliaCSIRO’s Data61, Australia
<EMAIL_ADDRESS>,  Trung Le  Monash University, Australia ,  Van Nguyen
Monash University, AustraliaCSIRO’s Data61, Australia ,  He Zhao  CSIRO’s
Data61, Australia ,  Edwin V. Bonilla  CSIRO’s Data61, AustraliaAustralian
National University, Australia ,  Gholamreza Haffari  Monash University,
Australia and  Dinh Phung  Monash University, AustraliaVinAI Research, Vietnam

(2023)

###### Abstract.

Interpretable machine learning seeks to understand the reasoning process of
complex black-box systems that are long notorious for lack of explainability.
One flourishing approach is through counterfactual explanations, which provide
suggestions on what a user can do to alter an outcome. Not only must a
counterfactual example counter the original prediction from the black-box
classifier but it should also satisfy various constraints for practical
applications. Diversity is one of the critical constraints that however
remains less discussed. While diverse counterfactuals are ideal, it is
computationally challenging to simultaneously address some other constraints.
Furthermore, there is a growing privacy concern over the released
counterfactual data. To this end, we propose a feature-based learning
framework that effectively handles the counterfactual constraints and
contributes itself to the limited pool of private explanation models. We
demonstrate the flexibility and effectiveness of our method in generating
diverse counterfactuals of actionability and plausibility. Our counterfactual
engine is more efficient than counterparts of the same capacity while yielding
the lowest re-identification risks.

Explainable AI, Algorithmic Recourse, Privacy

††copyright: acmcopyright††journalyear: 2023††copyright:
acmlicensed††conference: Proceedings of the 29th ACM SIGKDD Conference on
Knowledge Discovery and Data Mining; August 6–10, 2023; Long Beach, CA,
USA††booktitle: Proceedings of the 29th ACM SIGKDD Conference on Knowledge
Discovery and Data Mining (KDD ’23), August 6–10, 2023, Long Beach, CA,
USA††price: 15.00††doi: 10.1145/3580305.3599343††isbn:
979-8-4007-0103-0/23/08††ccs: Computing methodologies Machine learning††ccs:
Security and privacy Privacy protections

##  1\. Introduction

The eminence of deep neural networks in recent years has proliferated the use
of machine learning in various real-world applications. Such models provide
remarkable predictive performance yet often at a cost of transparency and
interpretability. This has sparked controversy over whether to rely on
algorithmic predictions for high-stakes decision making such as graduate
admission (Waters and Miikkulainen, 2014; Acharya et al., 2019), job
recruitment (Ajunwa et al., 2016), credit assessment (Lessmann et al., 2015)
or criminal justice (Gifford, 2018; Nguyen et al., 2021). Progress in
interpretable machine learning offers interesting solutions to explaining the
underlying behavior of black-box models (Ribeiro et al., 2016; Nguyen et al.,
2022; Vo et al., 2023). One useful approach is through counterfactual
examples111Counterfactual explanation is sometimes referred to as algorithmic
recourse., which sheds light on what modifications to be made to an
individual’s profile that can counter an unfavorable decision outcome from a
black-box classifier. Such explanations explore what-if scenarios that suggest
possible recourses for future improvement. Counterfactual explainability
indeed has important social implications at both personal and organizational
levels. For instance, feedback like ‘getting $1$ more referral’ or ‘being
fluent in at least $2$ languages’ would help unsuccessful candidates better
prepare for future job applications. By advocating for transparency in
decision making, organizations can improve their attractiveness to top talents
while inspecting possible prejudice implicitly introduced in historical data
and consequentially embedded in the classifiers producing biased decisions.

The ultimate goal of this line of research is to provide realistic guidelines
as to what actions an individual can take to achieve a desired outcome.
Desiderata of counterfactual explanations have been extensively discussed in
previous literature (Karimi et al., 2020b; Verma et al., 2020; Guidotti, 2022;
Verma et al., 2022). To be of practical use, a counterfactual explanation
should at least satisfy the following characteristics:

  * •

Validity: By definition, a counterfactual example must change the original
black-box outcome to a desired one.

  * •

Sparsity: Counterfactuals should be close to the original example where a
minimal number of features are modified.

  * •

Actionability: Counterfactual explanations should only suggest actionable or
feasible changes. In particular, changes should be made on mutable features
e.g., Work Experience or SAT scores, while leaving immutable features
unchanged e.g., Gender or Ethnicity.

  * •

Diversity: Diverse explanations are preferable to capture different
preferences from the same user so that they can freely explore multiple
options to select the best fit.

  * •

Plausibility222The terms plausibility and feasibility are often used
interchangeably.: Plausible or realistic counterfactuals are to obey the input
domain and constraints within/among features. For example, Age cannot decrease
or be above $200$.

  * •

Scalability: Inference should be done simultaneously and efficiently for
multiple input examples.

Among these desiderata, diversity emerges as a non-trivial property to
address. Given an instance, a diverse counterfactual engine returns a set of
different counterfactual profiles that should all lead to the desired outcome.
Ensuring that the entire explanation set satisfies validity while dealing with
constraints given by actionability and plausibility poses a computational
challenge. Scalability becomes another important consideration mainly due to
the fact that most of the existing approaches process counterfactuals
separately for each input data point. Furthermore, strongly enforcing sparsity
results in a smaller subset of features that can be changed. This hence can
compromise diversity since we expect counterfactual states to differ from one
to another substantially. On the other hand, there has been a growing concern
over the privacy risks of model explanation (Milli et al., 2019; Sokol and
Flach, 2019; Shokri et al., 2021). Aïvodji et al. (2020) points out that
diverse counterfactual explanations make the system more vulnerable as the
released examples reveal the model decision boundaries and could disclose
sensitive information such as health conditions or financial data. A linkage
attack is one such malicious attempt, which refers to the action of recovering
the identity (i.e., re-identifying) of an anonymized record in the published
dataset using background knowledge. It is often done by linking records to an
external dataset of the population based on the combination of several
attributes (Samarati and Sweeney, 1998; Machanavajjhala et al., 2007; El Emam
and Dankar, 2008). Netflix $1M Machine Learning Contest is a notorious data
breach, in which the company disclosed a dataset of $100$ million subscribers
with their movie ratings and preferences. Narayanan and Shmatikov (2006)
revealed a successful attack of $68\%$ that was easily achieved by cross-
referencing the users’ dates and precise ratings of $2$ movies with a non-
anonymous dataset published by IMDb (Internet Movie Database).

Despite an overwhelming number of counterfactual explanation approaches, only
a few works tackle diverse counterfactual generation (Russell, 2019; Karimi et
al., 2021; Mothilal et al., 2020; Bui et al., 2022; Redelmeier et al., 2021).
However, the trade-offs between diversity and the aforementioned constraints,
including privacy protection, have not been well studied in previous papers
(See Table 1 for comparison). Filling this gap, our work proposes a novel
learning-based framework that effectively addresses all the above desiderata
while mitigating the re-identification risk. From a methodological
perspective, our method diverges markedly from existing approaches in the
following ways:

Firstly, we reformulate the combinatorial search task into a stochastic
optimization problem to be solved via gradient descent. Unlike most previous
methods that perform optimization per-input basis, we employ amortized
inference to generate diverse counterfactual explanations efficiently.
Amortization has been previously adopted wherein a counterfactual generative
distribution is modelled via Markov Decision Processes (Verma et al., 2022) or
Variational Auto-encoders (Mahajan et al., 2019; Pawelczyk et al., 2020; Downs
et al., 2020). On one hand, none of these amortized methods addresses
diversity. On the other, we here take a different approach: we construct a
learnable generation module that directly models the conditional distributions
of individual features such that they form a valid counterfactual distribution
when combined.

Another point of difference of ours lies in the usage of Bernoulli sampling to
ensure sparsity. In prior works, standard metrics such as $\mathrm{L1}$ or
$\mathrm{L2}$ are often used to penalize the distance between the
counterfactual and original data point. Verma et al. (2020) criticizes this
approach as unnatural, especially for categorical features. Avoiding the use
of distance measures, we optimize along a feature selection module to output
the likelihood of the feature being mutated. This module can be adapted to any
user-defined constraints about the mutability of features.

Finally, we go beyond existing approaches by tackling the constraint of
privacy preservation exposed to diverse explanations. The key strategy is to
discretize continuous features and operate the counterfactual generation
engine in the categorical feature space. Discretization is closely related to
the generalization technique used in privacy-preserving data mining (PPDM) (El
Emam and Dankar, 2008; Mendes and Vilela, 2017). It is also treated as a
subroutine to analyze the composition of differential privacy algorithms (Gopi
et al., 2021; Ghazi et al., 2022). The idea is that it is by nature easier to
uniquely identify a profile based on continuous features, so discretization is
expected to increase the quantities of profiles linked back to a certain group
of attributes. Another defense effort against linkage attack can be found in
(Goethals et al., 2022). The paper proposes an algorithm named CF-K that
heuristically searches for an equivalence class for each counterfactual
instance such that every record is indistinguishable from at least $k-1$
others. CF-K is viewed as an add-on that theoretically can be implemented on
top of any counterfactual generative system. However, in practice, this
strategy is extremely expensive since it requires repetitively querying the
model explainer for a possibly larger number of counterfactuals than
requested. Though sharing the same motivation, we here contribute a
counterfactual explanation model with a built-in privacy preservation
functionality.

Our contributions can be summarized as follows:

  * •

We introduce Learning to Counter (L2C) - a stochastic feature-based approach
for learning counterfactual explanations that address the counterfactual
desirable properties in a single end-to-end differentiable framework.

  * •

Through extensive experiments on real-world datasets, L2C is shown to balance
the counterfactual trade-offs more effectively than the existing methods and
achieve diverse explanations with the lowest re-identifiability risk. To the
best of our knowledge, L2C is the first amortized engine that supports diverse
counterfactual generations with privacy-preservation capability.

Table 1. Desiderata comparison of related counterfactual explanation methods.
∗Privacy refers to whether the output data is protected against linkage attack
or re-identification risk. L2C satisfies all of these critical constraints.

Method | Sparsity | Actionability | Diversity | Plausibility | Scalability | Privacy∗
---|---|---|---|---|---|---
L2C (Ours) | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
DICE (Mothilal et al., 2020) | ✓ | ✓ | ✓ |  |  |
COPA (Bui et al., 2022) | ✓ | ✓ | ✓ |  |  |
MCCE (Redelmeier et al., 2021) | ✓ | ✓ | ✓ |  | ✓ |
Coherent CF (Russell, 2019) | ✓ |  | ✓ |  |  |
MACE (Karimi et al., 2020a) | ✓ | ✓ | ✓ |  |  |
MOC (Dandl et al., 2020) | ✓ | ✓ |  | ✓ |  |
CERTIFAI (Sharma et al., 2020) |  | ✓ |  |  |  |
Feasible-VAE (Mahajan et al., 2019) | ✓ | ✓ |  | ✓ | ✓ |
FastAR (Verma et al., 2022) | ✓ | ✓ |  | ✓ | ✓ |
CRUDS (Downs et al., 2020) |  | ✓ |  | ✓ | ✓ |
C-CHVAE (Pawelczyk et al., 2020) |  | ✓ |  |  | ✓ |
CF-K (Goethals et al., 2022) |  |  |  |  |  | ✓

##  2\. Related Works

Recent years have seen an explosion in the literature on counterfactual
explainability, from works that initially focused on one or two
characteristics or families of models to those that can deal with multiple
constraints and various model types. There have been many attempts to
summarize major themes of research and discuss open challenges in great depth.
We therefore refer readers to (Karimi et al., 2020b; Verma et al., 2020;
Guidotti, 2022) for excellent surveys of methods in this area. We here focus
on reviewing algorithms that can support diverse (or at least multiple) local
counterfactual generations.

Dealing with the combinatorial nature of the task, earlier works commonly
adopt mixed integer programming (Russell, 2019), genetic algorithms (Sharma et
al., 2020), or SMT solvers (Karimi et al., 2020a). Another recent popular
approach is gradient-based optimization (Mothilal et al., 2020; Bui et al.,
2022), which involves iteratively perturbing the input data point according to
an objective function that incorporates desired constraints. The whole idea of
diversity is to explore different combinations of features and feature values
that can counter the original prediction while accommodating various user
needs. To support diversity, Russell (2019) in particular enforces hard
constraints on the current generations to be different from the previous ones.
Such a constraint will however be removed whenever the solver cannot be
satisfied. Meanwhile, Mothilal et al. (2020) and Bui et al. (2022) add another
loss term for diversity using Determinantal Point Processes (Kulesza et al.,
2012), whereas the other works only demonstrate the capacity to generate
multiple counterfactuals via empirical results. All of the aforementioned
algorithms are computationally expensive in that input data points are handled
singly and individual runs are additionally required to produce several
counterfactuals. Reducing computational costs, Redelmeier et al. (2021)
attempts to model the conditional likelihood of mutable features given the
immutable features using the training data. They then adopt Monte Carlo
sampling to generate counterfactuals from this distribution and filter out
samples that do not meet counterfactual constraints. Given such a generative
distribution, sampling of counterfactuals can therefore be done
straightforwardly. Amortized optimization is another strategy to improve
inference speed (Mahajan et al., 2019; Pawelczyk et al., 2020; Downs et al.,
2020; Verma et al., 2022).

In response to the privacy warning about model explanations (Milli et al.,
2019; Sokol and Flach, 2019; Shokri et al., 2021), several defense strategies
have been introduced to alleviate the risks. With strong theoretical
guarantees, differential privacy (Dwork et al., 2006) stands out as the
promising solution to preventing member inference attack and model stealing
attack (Shokri et al., 2017; Milli et al., 2019; Aïvodji et al., 2020). With
regards to linkage attacks, CF-K (Goethals et al., 2022) is the only work we
are aware of that tackles linkage attack in counterfactual explanations.

##  3\. Stochastic Feature-Based Counterfactual Learning

###  3.1. Problem setup

Let $\mathcal{X}$ denote the input space where ${\bm{x}}=[x_{i}]_{i=1}^{N}$ is
an input vector with $N$ features of both continuous and categorical types. As
discussed previously, we discretize the continuous features into equal-sized
buckets, which gives us an input of $N$ categorical features wherein each
feature $x_{i}$ has $c_{i}$ levels. We apply one-hot encoding on each feature
and flatten them into a single input vector ${\bm{z}}\in\\{0,1\\}^{D}$ where
$D=\sum^{N}_{i=1}c_{i}$. Concretely, feature $x_{i}$ is now represented by the
vector ${\bm{z}}_{i}\in\mathbb{O}_{c_{i}}$ where the set of one-hot vectors
$\mathbb{O}_{c_{i}}$ is defined as
$\\{0,1\\}^{c_{i}}:\sum_{j=1}^{c_{i}}z_{ij}=1$.

Let $f$ be the black-box classifying function and $y=f({\bm{x}})$ be the
decision outcome on the input ${\bm{x}}$. A valid counterfactual example
$\widetilde{{\bm{x}}}$ associated with ${\bm{x}}$ is one that alters the
original outcome $y$ into a desired outcome $y^{\prime}\neq y$ with
$y^{\prime}=f(\widetilde{{\bm{x}}})$. Let $\widetilde{{\bm{z}}}$ denote the
corresponding one-hot representation of $\widetilde{{\bm{x}}}$.

Actionability indicates that some features can be mutable (i.e., changeable),
while others should be kept immutable (i.e., unchangeable). Without loss of
generality, let us impose an ordering on the set of $N$ features such that the
first $K$ features are mutable features (i.e., the ones that can be modified)
and denote $\mathbb{K}:=\\{1,...,K\\}\subset\\{1,...,N\\}$. For each mutable
feature (i.e., $x_{i}$ or the one-hot vector ${\bm{z}}_{i}$ with
$i\in\mathbb{K}$), we aim to learn a local feature-based perturbation
distribution $P(\widetilde{{\bm{z}}}_{i}\mid{\bm{z}})$ where
$\widetilde{{\bm{z}}_{i}}\in\mathbb{O}_{c_{i}}$, while leaving the immutable
features unchanged.

It is worth noting that our method functions equally well on heterogeneous
data where only categorical features are one-hot encoded while continuous
features are retained at their original values. However, we believe that
performing data discretization (or generalization in terms of PPDM) initially
and deploying the classifiers in the discrete feature space would provide
better privacy protection. For the purpose of comparing our prototype with
existing approaches, we follow the standard practice of explaining
classification models trained on the mixed dataset of continuous and
categorical features. To make it compatible with the discretization subroutine
of our framework, we represent the prediction on a transformed (fully
categorical) input vector with the prediction on the input where the
categorical values associated with mutable continuous features are substituted
with the middle point of the corresponding intervals. We refer to this
mechanism as one-hot decoding, which will be detailed shortly.

###  3.2. Methodology

We now detail how L2C works and addresses each counterfactual constraint. The
explanation pipeline of L2C is depicted in Figure 1.

Figure 1. For illustration purposes only, all features are assumed mutable in
the figure. We first discretize the continuous features of input ${\bm{x}}$
and one-hot encode all features into representations ${\bm{z}}$. For every
feature $i$, the generator $\mathcal{G}$ learns a local perturbation
distribution $\textrm{Cat}({\bm{p}}_{i}|{\bm{z}})$ so that together they form
a distribution of diverse counterfactual representations
$\widetilde{{\bm{z}}}$. Simultaneously, the selector $\mathcal{S}$ learns to
output the distribution $\textrm{Multi-Bernoulli}(\bm{\pi}|{\bm{z}})$
capturing the probability of each feature $i$ being modified. Every feature
sample pair $(\widetilde{{\bm{z}}}_{i},s_{i})$ is passed through an operation
in the blue box, which decides whether to accept the change being made to the
feature $i$ given by $\widetilde{{\bm{z}}}_{i}$. The output is then decoded
into the representations $\widetilde{{\bm{x}}}$ compatible with the black-box
system. $\mathcal{G}$ and $\mathcal{S}$ are jointly trained via back-
propagation according to Eq. (4). Intuitively, $\mathcal{G}$ aims to construct
a “bridge” across the decision boundary travelling from the input to a local
space of counterfactuals.

For each mutable feature ${\bm{z}}_{i}$ with $i\in\mathbb{K}$, we learn a
local feature-based perturbation distribution
$P(\widetilde{{\bm{z}}_{i}}\mid{\bm{z}})$ (i.e.,
$\tilde{z_{i}}\in\mathbb{O}_{c_{i}}$), which is a categorical distribution
$\textrm{Cat}({\bm{p}}_{i}\mid{\bm{z}})$ with category probability
${\bm{p}}_{i}=\big{[}p_{i1},p_{i2},...,p_{ic_{i}}\big{]}$. We form a
counterfactual example $\widetilde{{\bm{z}}}$ by concatenating
$\widetilde{{\bm{z}}}_{i}\sim\textrm{Cat}({\bm{p}}_{i}\mid{\bm{z}})$ for the
mutable features and ${\bm{z}}_{i}$ for the immutable features. To achieve
validity, we learn the local feature-based perturbation distribution by
maximizing the chance that the counterfactual examples $\widetilde{{\bm{z}}}$
counter the original outcome on ${\bm{x}}$. Additionally, learning local
feature-based perturbation distributions over the mutable features allows us
to conduct a global counterfactual distribution
$P(\widetilde{{\bm{z}}}\mid{\bm{z}})$ over the counterfactual examples
$\widetilde{{\bm{z}}}$ defined above. Sampling from this distribution
naturally leads to multiple counterfactual generations efficiently, and we
also expect that individual samples $\widetilde{{\bm{z}}}_{i}$ together can
form diverse combinations of features, thereby promoting diversity within the
generative examples.

As previously discussed, too much of diversity can compromise sparsity.
Dealing with this constraint, for each mutable feature ${\bm{z}}_{i}$, we
propose to learn a local feature-based selection distribution that generates a
random binary variable $s_{i}\sim\textrm{Bernoulli}(\pi_{i}\mid{{\bm{z}}})$
wherein we replace ${\bm{z}}_{i}$ by
$\widetilde{{\bm{z}}}_{i}\sim\textrm{Cat}({\bm{p}}_{i}\mid{\bm{z}})$ if
$s_{i}=1$ and leave $\tilde{{\bm{z}}}_{i}={\bm{z}}_{i}$ if $s_{i}=0$.
Therefore, the formula to update $\widetilde{{\bm{z}}}_{i}$ is

$\widetilde{{\bm{z}}}_{i}=(1-s_{i}){\bm{z}}_{i}+s_{i}\widetilde{{\bm{z}}}_{i}.$

The benefit of having $\bm{\pi}=[\pi_{i}]_{i\in\mathbb{K}}$ is thus to control
sparsity by adding one more channel to decide if we should modify a mutable
feature ${\bm{z}}_{i}$. Appendix D presents an ablation study showing that
without the selection distribution, the perturbation distribution alone can
generate diverse counterfactuals yet requires changing plenty of mutable
features. Meanwhile, optimizing the selection distribution jointly helps
harmonize the trade-off between diversity and sparsity.

###  3.3. Optimization Objective

In this section, we explain how to design the building blocks of our framework
L2C. As shown in Figure 1, our framework consists of two modules: a
counterfactual generator $\mathcal{G}$ and a feature selector $\mathcal{S}$.
The counterfactual generator $\mathcal{G}$ is used to model the feature-based
perturbation distribution, while feature selector $\mathcal{S}$ is employed to
model the feature-based selection distribution.

Specifically, given a one-hot vector representation ${\bm{z}}$ of a data
example ${\bm{x}}$, we feed ${\bm{z}}$ to $\mathcal{G}$ to form
$\mathcal{G}({\bm{z}})=[\mathcal{G}_{i}({\bm{z}})]_{i\in\mathbb{K}}$. We then
apply the softmax activation function to $\mathcal{G}_{i}({\bm{z}})$ to define
the feature-based local distribution (i.e.,
$\textrm{Cat}({\bm{p}}_{i}\mid{\bm{z}})$)) for ${\bm{z}}_{i}$ as

(1)
$p_{ij}({\bm{z}})=\frac{\exp\big{\\{}\mathcal{G}_{ij}({\bm{z}})\big{\\}}}{\sum^{c_{i}}_{k=1}\exp\big{\\{}\mathcal{G}_{ik}({\bm{z}})\big{\\}}},\forall
j=1,...,c_{i}.$

The module $\mathcal{S}$ takes ${\bm{z}}$ to form
$\mathcal{S}({\bm{z}})=[\mathcal{S}_{i}({\bm{z}})]_{i\in\mathbb{K}}$. We then
apply the Sigmoid function to $\mathcal{S}_{i}({\bm{z}})$ to define the
feature-based selection distribution (i.e.,
$\textrm{Bernoulli}(\pi_{i}\mid{{\bm{z}}})$) for ${\bm{z}}_{i}$ as

$\pi_{i}({\bm{z}})=\frac{1}{1+\exp{\big{\\{}-\mathcal{S}_{i}({\bm{z}})}\big{\\}}}.$

To encourage sparsity by reducing the number of mutable features chosen to be
modified, we regularize $\mathcal{S}$ through $\mathrm{L1}$-norm
$\|\bm{\pi}({\bm{z}})\|_{1}$ with
$\bm{\pi}({\bm{z}})=[\pi_{i}({\bm{z}})]_{i\in\mathbb{K}}$.

To summarize, given a one-hot vector representation ${\bm{z}}$ of a data
example ${\bm{x}}$, we use $\mathcal{G}$ to work out the local feature-based
perturbation distribution $\textrm{Cat}({\bm{p}}_{i}({\bm{z}}))$ for every
$i\in\mathbb{K}$. We then sample
$\widetilde{{\bm{z}}}_{i}\sim\textrm{Cat}({\bm{p}}_{i}({\bm{z}}))$ for every
$i\in\mathbb{K}$. Subsequently, we use $\mathcal{S}$ to work out the local
feature-based selection distribution $\textrm{Bernoulli}(\pi_{i}({\bm{z}}))$
for every $i\in\mathbb{K}$. We then sample
$s_{i}\sim\textrm{Bernoulli}(\pi_{i}\mid{{\bm{z}}})$ and update
$\widetilde{{\bm{z}}}_{i}=(1-s_{i}){\bm{z}}_{i}+s_{i}\widetilde{{\bm{z}}}_{i}$
for every $i\in\mathbb{K}$. Finally, we concatenate $\widetilde{{\bm{z}}}_{i}$
for $i\in\mathbb{K}$ and ${\bm{z}}_{i}$ for $i\notin\mathbb{K}$ to form the
counterfactual example $\widetilde{{\bm{z}}}$.

$\mathcal{G}$ and $\mathcal{S}$ are parameterized with neural networks over
total parameters $\theta$. For $\widetilde{{\bm{z}}}$ to be a valid and sparse
counterfactual associated with a desired outcome $y^{\prime}$, we propose the
following criterion

(2)
$\textrm{min}_{\theta}\Big{[}\mathbb{E}_{\widetilde{{\bm{z}}}}\big{[}\textrm{CE}(f(\widetilde{{\bm{z}}}),y^{\prime})\big{]}+\alpha\
\mathbb{E}_{{\bm{z}}}\big{[}\|\bm{\pi}({\bm{z}})\|_{1}\big{]}\Big{]},$

where $f$ is the black-box function, CE is the cross-entropy loss,
$\|\cdot\|_{1}$ is $\mathrm{L1}$-norm, $\alpha$ is a loss weight.

#### One-hot decoding

Recall that $\widetilde{{\bm{z}}}$ formed by concatenating many one-hot
vectors is an incompatible representation to the classifier $f$, which in fact
requires both continuous and one-hot features. We make a design choice of
reconstructing the continuous features by taking the middle point of the range
corresponding to the selected level. Specifically, the input to the one-hot
decoder is $\widetilde{{\bm{z}}}=[\widetilde{{\bm{z}}}_{i}]_{i=1}^{N}$. If the
feature $i$ originally is a categorical feature, we set
$\widetilde{x}_{i}=\widetilde{{\bm{z}}}_{i}$. Otherwise, we set
$\widetilde{x}_{i}=a_{i}+\frac{(2k-1)(b_{i}-a_{i})}{2c_{i}}$, which is the
middle point of the $k$-th interval
$[a_{i}+(k-1)(b_{i}-a_{i})/c_{i},a_{i}+k(b_{i}-a_{i})/c_{i}]$ where
$[a_{i},b_{i}]$ is the original value range of the feature $i$ and
$\widetilde{{\bm{z}}}_{i}$ corresponds to the level $k\in\\{1,...,c_{i}\\}$
(i.e., $\widetilde{{\bm{z}}}_{ik}=1$ and $\widetilde{{\bm{z}}}_{ij}=0$ if
$j\neq k$). Note that one-hot decoding is only applied when a continuous
feature is indicated by $\mathcal{S}$ to be mutable ($s_{i}=1)$. Otherwise, we
revert to the original continuous value. Formally, we rewrite

(3)
$\widetilde{x}_{i}=(1-s_{i})x_{i}+s_{i}\sum_{j=1}^{c_{i}}\widetilde{{\bm{z}}}_{ij}\big{[}a_{i}+\frac{(2j-1)(b_{i}-a_{i})}{2c_{i}}\big{]}.$

To assure model differentiability for training, the one-hot vector
$\widetilde{{\bm{z}}}_{ij}$ is relaxed into its continuous representation by
using Gumbel-Softmax reparametrization trick, which is detailed in Section
3.4.

The final optimization objective is now given as

(4)
$\textrm{min}_{\theta}\Big{[}\mathbb{E}_{\widetilde{{\bm{x}}}}\big{[}\textrm{CE}(f(\widetilde{{\bm{x}}}),y^{\prime})\big{]}+\alpha\
\mathbb{E}_{{\bm{z}}}\big{[}\|\bm{\pi}({\bm{z}})\|_{1}\big{]}\Big{]}.$

#### Plausibility

A counterfactual generative engine needs to ensure explanations are realistic
for real-world applications. There are two common types of plausibility
constraints: Unary and Binary monotonicity constraints. The former deals with
individual features (e.g., Age cannot decrease) while the latter is concerned
with the correlation of a pair of features (e.g., increasing in Education
level increases Age). To handle binary constraints on heterogeneous data is
not as straightforward as unary constraints. We thus delay the discussion on
binary constraints until Section 5.4 and focus on unary constraints in the
main analysis.

Dealing with such a constraint, one can simply eliminate any counterfactuals
violating the constraints during inference time. This however creates
additional computational overhead and may compromise some desiderata. There
are only few attempts addressing feature constraints in counterfactuals,
notably Mahajan et al. (2019); Verma et al. (2022): Verma et al. (2020)
incorporate hard conditions in a Markov Decision process where a feature gets
updated only if the corresponding action does not violate the constraints.
Meanwhile, Mahajan et al. (2019) includes a hinge loss into the loss function
for unary features, while specifically learning a separate linear model for
every feature pair subject to a binary constraint. For L2C, the learnable
local distributions can be used for this purpose conveniently. Our proposed
strategy is to impose rule-based unary constraints on related features in the
optimization process. Technically, for every feature to be perturbed with a
non-decreasing (non-increasing) constraint, we penalize the probabilities
corresponding to lower (higher) levels towards zero by multiplying them with a
positive infinitesimal quantity. Concretely, given a mutable feature $i$ under
monotonic constraints, let $l\in\\{1,...,c_{i}\\}$ denote the current state -
the level corresponding to ${\bm{z}}_{i}$ (i.e., $z_{il}=1$ and $z_{ij}=0$ if
$j\neq l$). Let us denote the restricted set of levels as
$\mathbf{C}_{i}=\\{1,...,l-1\\}$ if the feature is non-decreasing and
$\mathbf{C}_{i}=\\{l+1,...,c_{i}\\}$ if it is non-increasing. The perturbation
distribution $\textrm{Cat}({\bm{p}}_{i}\mid{\bm{z}})$ for ${\bm{z}}_{i}$ given
in Eq. (1) now becomes

(5)
$p_{ij}({\bm{z}})\propto\varepsilon^{\bm{1}_{\mathbf{C}_{i}}(j)}\times\frac{\exp\big{\\{}\mathcal{G}_{ij}({\bm{z}})\big{\\}}}{\sum^{c_{i}}_{k=1}\exp\big{\\{}\mathcal{G}_{ik}({\bm{z}})\big{\\}}},\forall
j=1,...,c_{i},$

where $\bm{1}_{\mathbf{C}_{i}}(.)$ is the indicator function such that
$\bm{1}_{\mathbf{C}_{i}}(j)=1$ if $j\in\mathbf{C}_{i}$ and
$\bm{1}_{\mathbf{C}_{i}}(j)=0$ otherwise, meaning that the probabilities at
the other levels are untouched. We here explicitly force the model to generate
more samples at the higher (lower) levels while maintaining differentiability
of the objective function. We choose $\varepsilon=e^{-10}$ in our experiments,
but any positive value arbitrarily close to zero would suffice.

###  3.4. Reparameterization for Continuous Optimization

Our L2C involves multiple sampling rounds back and forth to optimize the
networks. To make the process continuous and differentiable for training, we
adopt the reparameterization tricks (Jang et al., 2016; Maddison et al.,
2016):

#### 1) Sampling
$\widetilde{{\bm{z}}}_{i}\sim\textrm{Cat}({\bm{p}}_{i}\mid{\bm{z}})$

: To obtain differentiable counterfactual samples, we adopt the classic
temperature-dependent Gumbel-Softmax trick (Jang et al., 2016; Maddison et
al., 2016). Given the categorical variable ${\mathbf{z}}_{i}$ with category
probability $\big{[}p_{i1},p_{i2},...,p_{ic_{i}}\big{]}$. The relaxed
representation is sampled from the Categorical Concrete distribution as
$\widetilde{{\bm{z}}}_{i}\sim\textrm{Cat-Concrete}(\log p_{i1},...,\log
p_{ic_{i}})$ by

$\widetilde{z}_{ij}=\frac{\exp\big{\\{}(\log
p_{ij}({\bm{z}})+G_{j})/\tau\big{\\}}}{\sum^{c_{i}}_{k=1}\exp\big{\\{}(\log
p_{ik}({\bm{z}})+G_{k})/\tau\big{\\}}}.$

with temperature $\tau$, random noises $G_{j}$ independently drawn from Gumbel
distribution $G_{t}=-\log(-\log u_{t}),\ u_{t}\sim\textrm{Uniform}(0,1)$. As
discussed, we apply this mechanism consistently to the one-hot representations
of all features. The continuous relaxation of Eq. (3) can be gained by simply
using the one-hot relaxation $\widetilde{{\bm{z}}}_{i}$.

#### 2) Sampling $s_{i}\sim\textrm{Bernoulli}(\pi_{i}\mid{{\bm{z}}})$

: We again apply the Gumbel-Softmax trick to relax Bernoulli variables of $2$
categories. With temperature $\tau$, random noises $G_{i0}$ and $G_{i1}\sim
G_{t}=-\log(-\log u_{t}),\ u_{t}\sim\textrm{Uniform}(0,1)$, the continuous
representation $s_{i}$ is sampled from Binary Concrete distribution as
$s_{i}\sim\textrm{Bin-Concrete}(\pi_{i},1-\pi_{i})$ by

$s_{i}=\frac{\exp\\{\big{(}\log\pi_{i}({\bm{z}})+G_{i1}\big{)}/\tau\\}}{\exp\\{\big{(}\log(1-\pi_{i}({\bm{z}}))+G_{i0}\big{)}\\}/\tau\\}+\exp\\{\big{(}\log\pi_{i}({\bm{z}})+G_{i1}\big{)}/\tau)\\}}.$

##  4\. Experimental Setup

We experiment with $4$ popular real-word datasets: German Credit (Dua and
Graff, 2017), Adult Income (Kohavi et al., 1996) Graduate Admission (Acharya
et al., 2019) and Student Performance (Cortez and Silva, 2008). For each
dataset, we select a fixed subset of immutable features based on our domain
knowledge and suggestions from (Verma et al., 2022). We reserve the privacy
analysis for German Credit and Adult Income datasets, which contain personal
financial information and various attributes through which data subjects can
be re-identified (Goethals et al., 2022). While implementing the black-box
classifiers and the baseline methods, we standardize numerical features to
unit variance and one-hot encode categorical features. Note again that, for
our method only, we discretize numerical features into equal-sized buckets and
decode the numerical features back to their original representations whenever
necessary to consult the black-box model. Appendix A describes our tasks and
model design in greater detail. Our code repository can be accessed at
https://github.com/isVy08/L2C/.

Table 2. Description of quantitative evaluation metrics. $\mathbb{C}$ denotes
a set of counterfactual examples generated by an algorithmic recourse approach
for a given input instance.

Desiderata |  Metric |  Description
---|---|---
Validity |  Validity |  Proportion of samples in $\mathbb{C}$ can counter the original black-box decision outcome.
Coverage |  Coverage $=100\%$ if there exists at least $1$ valid counterfactual in $\mathbb{C}$.
Sparsity/Actionability |  Sparsity |  Proportion of features kept unchanged, averaged over the number of samples in $\mathbb{C}$.
Diversity |  Diversity |  Hamming distance of a pair of counterfactual samples across all features where numerical features are discretized. The metric is averaged over all pairs of samples in $\mathbb{C}$.
Sparsity – Diversity Balance |  Harmonic mean |  F-measure of Diversity and Sparsity = $2\cdot\texttt{Diversity}\cdot\texttt{Sparsity}/(\texttt{Diversity}+\texttt{Sparsity})$.
Plausibility |  Unary |  Proportion of examples $\mathbb{C}$ meeting the unary monotonic constraints, averaged over the number of features subject to constraints.

#### Performance metrics

Following the past works Mothilal et al. (2020); Redelmeier et al. (2021);
Verma et al. (2022), Table 2 outlines the commonly used metrics for
quantitatively assessing the desirability of counterfactual explanations. As
for diversity, a widely adopted measure is the pairwise distance between
counterfactual examples, with distance defined separately for numerical and
categorical features (Mothilal et al., 2020; Redelmeier et al., 2021). Though
this approach is meaningful for interpreting categorical features, we however
find it quite obscure for numerical features. This motivates us to discretize
numerical features again when computing Diversity, which captures how often a
feature gets altered as well as how much the change is - specifically via how
often it switches to a different categorical level. The computation of
Diversity only considers valid counterfactuals, so if valid counterfactuals
are none, Diversity is set to zero. It is worth noting that there
fundamentally exists a trade-off between sparsity and diversity. To quantify
how well a method can balance these two properties, we suggest taking Harmonic
mean of Diversity and Sparsity, motivated by the development of F1-score in
measuring Precision against Recall. For metrics used in privacy analysis,
refer to Section 5.2.

#### Evaluation setup

We consider a general setting of binary classification where a counterfactual
outcome $y^{\prime}$ is opposite to the original outcome $y$, whether $y$ has
label $1$ or $0$. From each method, we generate a set of $100$ counterfactual
explanations. During generation, most methods, including ours, require
multiple iterations of searching for the optimal set of counterfactuals based
on the optimization constraints. To assure a fair comparison on efficiency, a
global maximum time budget of $5$ minutes is imposed to search for a set of
$100$ counterfactuals per input sample. We compare our method top-performing
baselines that support diverse counterfactual explanations: DICE (Mothilal et
al., 2020), MCCE (Redelmeier et al., 2021) and COPA (Bui et al., 2022). DICE
offers several search strategies: Random, KD tree, or Genetic algorithm. DICE-
KDTree was consistently reported to fail across datasets (Verma et al., 2022),
so we exclude it from our evaluation. We do not consider MACE (Karimi et al.,
2020a) since it is extremely expensive on large datasets (Verma et al., 2022)
and often fails to converge in our experiments, nor MOC (Dandl et al., 2020)
due to the lack of Python implementation.

##  5\. Results and Discussion

###  5.1. Counterfactual Explanation Desiderata

We first study whether an algorithmic recourse approach generates a set of
diverse counterfactuals without sacrificing the other desiderata. Note that
COPA has only been shown to work effectively on linear classifiers. Table 3
reports the average results over $5$ model initializations. Appendix E
provides several illustrative examples for qualitative assessment.

Under the same time budget, our method L2C succeeds in generating $100\%$
valid counterfactuals with full coverage. Together with DICE, L2C first
satisfies the most important criterion of a counterfactual explanation and
resolves the trade-off against validity. Recall that we have specified a fixed
set of immutable features for each dataset, based on which we can work out the
minimum sparsity threshold a counterfactual explanation should adhere to
(i.e., % immutable features). Actionability can then be assessed by comparing
Sparsity with this level to determine if a method satisfies the mutability of
features. An adequate explanation must achieve at least this level of
sparsity. MCCE evidently fails to fulfill this constraint on Adult Income and
Student Performance datasets.

Our reported results here are obtained under no other conditions than the
constraints related to feature immutability and monotonicity described in
Table 7. Nevertheless, we would like to highlight the flexibility of our
framework in controlling the quality of counterfactual generations during
inference. Users can freely specify any sparsity threshold or additional
conditions of interest to filer out unsatisfactory examples without re-
training or re-optimization as in methods like DICE. Specifically, DICE
employs gradient search directly on each query according to a selected set of
weighting hyperparameters for each term in the objective function. To get a
less sparse or more diverse example than the current generation, one needs to
activate a new search routine.

Too many constraints or too much sparsity clearly affects the diversity level
of the counterfactual set. Maintaining a high Harmonic mean scores while
satisfying almost all feature constraints demonstrates that L2C can
effectively manage these trade-offs. The fact that L2C converges to valid
counterfactuals with minimal violation in such a short inference time can be
attributed to the practice of injecting hard constraints during optimization
and global training does enhance the effect. It certainly helps circumvent the
burden of heuristically eradicating violated samples. Notice also that our
quantitative results align with the descriptions in Table 1. None of the
diverse counterfactual explanation approaches address plausibility thoroughly
whereas those reported to support the feasibility of features do not guarantee
diversity. Appendix C provides empirical evidence for this claim, in which we
compare L2C with popular amortized algorithmic recourse approaches and
demonstrate our consistent superiority in generating diverse explanations
efficiently without violating the required constraints (See Table 8).

Table 3. Desirability of counterfactual explanation methods. $\downarrow$
Lower is better. $\uparrow$ Higher is better. Bold / Underline indicates the
best / second-best performance for each dataset. Time records total inference
time in seconds.

Method | Sparsity (%)$\uparrow$ | Diversity (%)$\uparrow$ | Harmonic Mean (%)$\uparrow$ | Validity (%)$\uparrow$ | Coverage (%)$\uparrow$ |  Unary (%)$\uparrow$ | Time(s)$\downarrow$
---|---|---|---|---|---|---|---
German Credit (Logistic Regression) - Min Sparsity: $20.00\%$
L2C (Ours) |  61.35 |  37.31 | 46.39 | 100.00 | 100.00 | 99.06 |  18
DICE-Random | 88.23 | 15.29 | 26.06 | 100.00 | 100.00 |  90.81 | 1,150
DICE-Genetic | 43.45 | 37.56 |  40.29 |  62.87 |  90.24 | 56.66 | 17,615
COPA | 57.88 | 18.88 | 28.47 | 44.00 | 44.00 | 84.31 | 17,583
MCCE | 28.76 | 33.40 | 30.91 | 48.74 | 100.00 | 58.76 | 2
Adult Income (Neural Network) - Min Sparsity: $30.77\%$
L2C (Ours) |  45.70 | 28.11 | 34.80 | 100.00 | 100.00 | 97.62 |  444
DICE-Random | 89.26 | 9.05 | 16.44 | 100.00 | 100.00 |  87.15 | 12,332
DICE-Genetic | 41.48 |  26.27 |  32.14 |  92.64 | 100.00 | 72.70 | 505,174
MCCE | 24.93 | 4.58 | 7.74 | 30.63 | 74.76 | 45.79 | 98
Graduate Admission (Neural Network) - Min Sparsity: $14.29\%$
L2C (Ours) |  42.23 |  37.90 |  39.94 | 100.00 | 100.00 | 100.00 | 4
DICE-Random | 66.25 | 30.93 | 42.15 | 100.00 | 100.00 |  85.30 | 412
DICE-Genetic | 23.05 | 47.54 | 31.04 |  92.91 | 100.00 | 66.69 | 6,171
MCCE | 17.39 | 22.98 | 19.51 | 43.79 | 84.60 | 79.11 | 1
Student Performance (Logistic Regression) - Min Sparsity: $38.57\%$
L2C (Ours) |  55.32 |  29.54 |  38.51 | 100.00 | 100.00 | 100.00 | 6
DICE-Random | 87.60 | 13.64 | 23.60 | 100.00 | 100.00 |  98.99 | 2,518
DICE-Genetic | 39.20 | 39.88 | 38.54 |  84.83 | 100.00 | 60.77 | 3,406
COPA | 50.45 | 25.28 | 33.68 | 67.26 | 67.26 | 95.32 | 18,774
MCCE | 25.97 | 24.97 | 25.46 | 60.98 |  93.10 | 67.70 | 1

###  5.2. Re-identification Risk Analysis

#### Preliminaries

We start by reviewing the fundamental concepts related to a public dataset:

  * •

Identifiers: Attributes that uniquely identify an individual. Identifiers can
be a person’s full name, government tax number or driver’s license number.

  * •

Quasi-identifiers: Attributes that themselves do not uniquely identify a
person, but when combined are sufficiently correlated to at least one
individual record. For example, the combination of gender, birth dates and ZIP
codes can re-identify $87\%$ of American residents (Sweeney, 2000).

  * •

Sensitive attributes: Attribute that are protected against unauthorized
access. Sensitive data is confidential and if leaked could harm personal
safety or emotional well-being. Examples are salary, medical conditions,
salary, criminal histories, or phone numbers.

  * •

Equivalence class: An equivalence class is a group of records with identical
quasi-identifiers.

Every public dataset must first be anonymized by removing identifiers.
However, the data may still be vulnerable to re-identification attacks due to
the potential existence of quasi-identifiers. To quantify the level at which a
dataset is susceptible to re-identification risk, the following $3$ metrics
are commonly used:

  * •

k-Anonymity (Samarati and Sweeney, 1998): A dataset satisfies $k$-anonymity if
for each record in the dataset, the quasi-identifiers are indistinguishable
from at least $k-1$ other people also in the dataset.

  * •

l-Diversity (Machanavajjhala et al., 2007): A dataset has $l$-diversity if,
for every equivalence class, there are at least $l$ distinct values for each
sensitive attribute.

  * •

k-Map (El Emam and Dankar, 2008): Given an auxiliary dataset used for re-
identification (e.g., US Census or IMDb dataset in the Netflix example), so-
called the ‘attack’ dataset, a dataset satisfies $k$-map if every equivalence
class is mapped to at least $k$ records in the ‘attack’ dataset.

#### Evaluation metrics

Suppose a company releases an API that permits users to query a set of
counterfactual examples. We now analyze the level of privacy leakage
associated with the output data, by quantifying the percentage of successful
attacks w.r.t the aforementioned metrics. Respectively, we measure (1)
1-Anonymity: % equivalence classes with only $k=1$ member, (2) 1-Diversity: %
equivalence classes with $l=1$ value for a sensitive attribute, (3) 1-Map: %
counterfactual examples exactly matched with any single record in an ‘attack’
dataset. Notice that given a $k$-anonymized dataset, the existence of a one-
to-one mapping with the ‘attack’ dataset means the released dataset fails
k-Map.

#### Experiments

By definition, violations w.r.t k-Anonymity and l-Diversity are computed
against the output set of examples, while k-Map requires an external dataset.
For Adult Income, we choose the validation set as the ‘attack’ set. For German
Credit, there exists multiple versions of this dataset across the literature.
The one used in our main analysis is adopted from (Verma et al., 2022), which
has been subject to pre-processing. We use another version published by Penn
State University333https://online.stat.psu.edu/stat857/node/215/ for re-
identification. We assume these hold-out sets belong to some larger datasets
of population availably accessed by the public. Quasi-identifiers and
sensitive attributes are given in Appendix A. Following Goethals et al.
(2022), we consider the black-box predicted label as part of the quasi-
identifiers.

Let’s first look into the attacks on the raw output explanations presented in
Table 4. We here assume that the attacker’s goal is to collect as many
examples as possible without caring about which one is valid. If the attacker
has no information about how the data is discretized, it is much less likely
to find exact matches in the ‘attack’, thereby reducing the re-identifiability
of L2C data. Now we assume the attacker gets access to both the API and our
discretization mechanism. They therefore could correspondingly discretize the
data in the ‘attack’ set and retrieve the matches. Our analysis assumes this
worse scenario, meaning that for L2C only, we compute 1-Map against the
discretized data. The entries N/A in Table 4 are due to the fact that no
counterfactual example in the data of DICE-Genetic or COPA has matches, so
their robustness remains unverifiable in our experiment. We must highlight
that no match does not necessarily translate to zero privacy risk. We also
note that such a case is different from L2C, whose result is nearly $0.00\%$.
L2C in fact still returns matches for some records wherein we achieve k-Map of
$2-3$ specifically. Overall, L2C yields the lowest re-identifiability risk.
Another interesting observation on German Credit is that although DICE
performs well on k-Anonymity, the number of attacks on l-Diversity is
dramatically high. This sheds light on the limitation of k-Anonymity discussed
in (Machanavajjhala et al., 2007) about Homogeneity attacks and Background
knowledge attacks. Basically, attacking a k-anonymized dataset with a high $k$
can still reveal some private information of the data subjects because
profiles in the same equivalence class are similar (very few distinct values
in sensitive attributes), or the adversary has some background knowledge that
any help narrow down possible values.

#### Privacy under CF-K

We here investigate the effectiveness of the idea behind CF-K proposed in
(Goethals et al., 2022). CF-K searches for an equivalence class for each
counterfactual example and suggests only publishing profiles of at least
$k$-sized equivalence class. Since the authors do not publish their codes,
plus it is hugely time-consuming to run on models like DICE, we extend the
above experiment and examine the effect when every output counterfactual set
is $2$-anonymized. Specifically, for every set of $100$ generations, we remove
records not belonging to any equivalence classes. Given now that the data is
now $2$-anonymized, we evaluate attacks against l-Diversity and k-Map. We also
measure % of valid counterfactuals left in the set, assuming that a user
requests for $100$ per instance. The more valid examples lost from a model
explainer imply that it will be more costly to search for sufficient
equivalence classes for every instance. Figure 2 depicts that in most cases,
$k$-anonymization enhances the protection of the sensitive attributes but does
greatly compromise the validity of the output explanations.

The purpose of $k$-anonymization is to ensure when attacked, an individual
remains indistinguishable from at least $k-1$ others. However, notice that
$k$-anonymization does not prevent k-Map against which the number of
successful attacks is still high for DICE and MCCE. The threat is thus no less
severe when the attacker is interested in the re-identifiability of both
datasets. If the released data contains the sensitive information that is
missing from the ‘attack’ dataset, and given the fact that $1$-diversity
remains well above zero for all methods, the attacker could easily infer
private information of every linked record. To this end, generalizing the data
as done in L2C is proved to be useful to prevent such an inference attack. It
is also observed that combining CF-K with L2C in particular significantly
improves the anonymity of our counterfactual data. We therefore believe that
the integration of L2C with other privacy techniques in the cybersecurity area
would yield a more effective safeguard.

Table 4. Successful attacks on counterfactual explanation methods. Bold /
Underline indicates the lowest / second-lowest privacy risk for each dataset.
1-Diversity is evaluated on $2$ most sensitive attributes as shown in the
columns 2 & 3.

Method | 1-Anoy.$\downarrow$ | 1-Diversity$\downarrow$ | 1-Map$\downarrow$
---|---|---|---
German Credit
L2C (Ours) | 62.15% |  67.09% | 71.60% | 0.21%
DICE-Random |  55.15% | 82.75% | 89.96% |  23.67%
MCCE | 62.83% | 65.40% |  76.95% | 26.64%
DICE-Genetic | 15.36% | 90.19% | 95.80% | N/A
COPA | 87.61% | 89.41% | 89.24% | N/A
Adult Income
L2C (Ours) | 5.07% | 14.90% | 39.58% | 0.00%
DICE-Random | 72.21% | 91.28% | 93.07% | 3.31%
MCCE | 15.19% | 66.42% |  72.36% |  1.77%
DICE-Genetic |  15.11% |  65.32% | 87.54% | N/A

Figure 2. Privacy risk comparison between the raw output data and the data
subject to $2$-anonymization under the strategy of CF-K. For all metrics,
lower is better. l-Diversity is evaluated on $2$ most sensitive attributes.

###  5.3. Discretization

Discretization is an important pre-processing step in data analysis in which
the problem of optimal discretization with a minimum number of splits is
proved to be NP-Hard (Nguyen and Skowron, 1995; Chlebus and Nguyen, 1998). We
here adopt the unsupervised Equal-frequency discretizer, which splits a
continuous attribute into buckets with the same number of instances444Except
for the features Capital gain and Capital loss from Adult Income which we
convert into binary variables to accurately reflect the semantics of their
data.. More concretely in this experiment, features are quantized using Python
function qcut555https://pandas.pydata.org/docs/reference/api/pandas.qcut.html,
which requires specifying the maximum number of buckets/levels and later
adjusts it depending on the input data distribution. We set the maximum
buckets to be $4$ such that every bucket averagely has $25\%$ of total
observations. Table 13 reports how the numerical features of each dataset are
discretized. We argue that having very few buckets is likely to cause under-
fitting since there are very few useful combinatorial patterns that can
counter the original label. Whereas we need diversity for effective learning,
too many buckets are undesirable since it can hurt generalization due to some
following reasons : (1) each bucket would contain too little data and the
chosen middle value may not represent the bucket well, and (2) the model has
more combinations of features to explore, thus can converge to sub-optimal
combinations that cannot generalize well on unseen test points. In this
regard, we decide to split data into equal-sized buckets in the hope of
balancing the trade-off.

Various discretization methods exist (Ramírez-Gallego et al., 2016). Table 5
analyzes the performance of our method L2C under $3$ other discretization
strategies. The first one is Minimal entropy partitioning (MDP) (Fayyad and
Irani, 1993). It is an old-school supervised approach and one of the most
widely used. MDP determines the binary discretization for a value range by
selecting the cut point that minimizes the class entropy. The algorithm can be
applied recursively on sub-partitions induced by the initial cut point and the
paper proposes using Minimum Description Length
Principle666https://orange3.readthedocs.io/ (Rissanen, 1978) as a stopping
condition. Another strategy is to apply Domain knowledge where feature values
can be grouped based on common demographic or social characteristics. For
example, Age could be translated into different age groups (e.g., Teenagers,
Young Adults, etc.), or TOEFL scores are divided into proficiency levels.
While the aforementioned methods are uni-variate, we also implement a
multivariate approach using Decision tree. Following the motivation of MDP, we
run CART (Breiman et al., 2017) to search for the splits that minimize class
information entropy. Note that we here consider the predicted labels from the
black-box models as the target variable. The goal is to each sure the
prediction on each combination of features is stable as possible. To avoid
fine-grained intervals, we set the minimum number of samples for a split to be
$30$. Our experiment shows that we are still able to achieve $100\%$ of
Validity and Coverage in roughly the same amount of time. We therefore only
present the remaining metrics in Table 5, which here demonstrates a comparable
quality of explanations among different discretization strategies. Given that
L2C performance is relatively insensitive to the choice of discretizers, we
therefore suggest using Equal-frequency for which no labels or external
knowledge is required.

Table 5. Desirability of L2C counterfactual explanations under various
discretization strategies. ∗Proposed method.

Strategy |  Sparsity (%)$\uparrow$ |  Diversity (%)$\uparrow$ |  Harmonic Mean (%)$\uparrow$ |  Unary (%)$\uparrow$
---|---|---|---|---
German Credit - Min Sparsity: $20.00\%$
Equal Freq.∗ |  61.35 |  37.31 |  46.39 |  99.06
MDP |  61.58 |  35.00 |  44.63 |  100.00
CART |  60.92 |  39.85 |  48.18 |  100.00
Domain Know. |  61.73 |  37.56 |  46.70 |  100.00
Graduate Admission - Min Sparsity: $14.29\%$
Equal Freq.∗ |  42.23 |  37.90 |  39.94 |  100.00
MDP |  58.20 |  41.34 |  41.56 |  100.00
CART |  41.80 |  41.34 |  41.56 |  100.00
Domain Know. |  42.17 |  42.30 |  42.22 |  100.00
Student Performance - Min Sparsity: $38.57\%$
Equal Freq.∗ |  55.32 |  29.54 |  38.51 |  100.00
MDP |  55.57 |  28.50 |  37.67 |  100.00
CART |  55.07 |  27.79 |  36.94 |  100.00
Domain Know. |  55.47 |  31.57 |  40.23 |  100.00

###  5.4. Feature Correlational Constraints

While the treatment of unary constraints is straightforward for heterogeneous
datasets, we argue that this is not the case for binary constraints. For
example, suggesting that a person get a Master’s degree at precisely the age
of $34$ is unrealistically rigid. This issue indeed stems from the presence of
continuous features. A direct solution is to allow for more flexible
suggestions through discretization (e.g., suggesting an age range from $30-40$
instead of an exact value at $34$). This indeed aligns with the generative
mechanism of our L2C, which sets us apart from existing works. However,
discretization is currently treated as a subroutine of internal processing,
meaning that in the output examples, the values for the continuous features
are still returned in the numerical format for the sake of consistency.
Therefore, the best strategy would be to have the machine learning classifiers
trained in the discretized feature space accordingly. Practitioners could then
ignore the one-hot decoding stage and deploying L2C for this purpose would be
effortless. In Appendix B, we demonstrate how L2C effectively addresses binary
constraints in this scenario with success rates of 91.54% and 100.00%
respectively on German Credit and Adult Income.

##  6\. Conclusion and Future Work

In this paper, we study the challenges facing algorithmic recourse approaches
in generating diverse counterfactual explanations: how diversity can be
tackled without compromising the other desiderata of an explanation while
preserving privacy against linkage attacks. We analyze how existing engines
fail to resolve the trade-offs among counterfactual constraints and fill the
research gap with our novel framework L2C. Here we target a broad class of
differentiable machine learning classifiers. To fit non-differentiable models
in our framework, one could use policy gradient (Sutton et al., 1999) or
attempt to approximate such models as decision trees or random forests with a
differentiable version (Yang et al., 2018; Lucic et al., 2022). L2C is
currently proposed to deal with re-identification risks of the released
examples. Defense against model stealing and membership inference attacks
however remains exigent. Integrating differential privacy in the framework of
L2C is one interesting research avenue, which we leave for future works to
explore.

##  7\. Acknowledgement

Dinh Phung and Trung Le gratefully acknowledge the support by the US Airforce
FA2386-21-1-4049 grant and the Australian Research Council ARC DP230101176
project. This does not imply endorsement by the funding agency of the research
findings or conclusions. Any errors or misinterpretations in this paper are
the sole responsibility of the authors.

## References

  * (1)
  * Acharya et al. (2019) Mohan S Acharya, Asfia Armaan, and Aneeta S Antony. 2019\.  A comparison of regression models for prediction of graduate admissions. In _2019 international conference on computational intelligence in data science (ICCIDS)_. IEEE, 1–5.
  * Aïvodji et al. (2020) Ulrich Aïvodji, Alexandre Bolot, and Sébastien Gambs. 2020.  Model extraction from counterfactual explanations.  _arXiv preprint arXiv:2009.01884_ (2020).
  * Ajunwa et al. (2016) Ifeoma Ajunwa, Sorelle Friedler, Carlos E Scheidegger, and Suresh Venkatasubramanian. 2016\.  Hiring by algorithm: predicting and preventing disparate impact.  _Available at SSRN_ 2746078 (2016).
  * Breiman et al. (2017) Leo Breiman, Jerome H Friedman, Richard A Olshen, and Charles J Stone. 2017.  _Classification and regression trees_.  Routledge.
  * Bui et al. (2022) Ngoc Bui, Duy Nguyen, and Viet Anh Nguyen. 2022.  Counterfactual Plans under Distributional Ambiguity.  _arXiv preprint arXiv:2201.12487_ (2022).
  * Chlebus and Nguyen (1998) Bogdan S Chlebus and Sinh Hoa Nguyen. 1998.  On finding optimal discretizations for two attributes. In _International Conference on Rough Sets and Current Trends in Computing_. Springer, 537–544.
  * Cortez and Silva (2008) Paulo Cortez and Alice Maria Gonçalves Silva. 2008.  Using data mining to predict secondary school student performance.  (2008).
  * Dandl et al. (2020) Susanne Dandl, Christoph Molnar, Martin Binder, and Bernd Bischl. 2020.  Multi-objective counterfactual explanations. In _International Conference on Parallel Problem Solving from Nature_. Springer, 448–469.
  * Downs et al. (2020) Michael Downs, Jonathan L Chu, Yaniv Yacoby, Finale Doshi-Velez, and Weiwei Pan. 2020.  Cruds: Counterfactual recourse using disentangled subspaces.  _ICML WHI_ 2020 (2020), 1–23.
  * Dua and Graff (2017) Dheeru Dua and Casey Graff. 2017.  UCI Machine Learning Repository.  http://archive.ics.uci.edu/ml
  * Dwork et al. (2006) Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. 2006.  Calibrating noise to sensitivity in private data analysis. In _Theory of cryptography conference_. Springer, 265–284.
  * El Emam and Dankar (2008) Khaled El Emam and Fida Kamal Dankar. 2008.  Protecting privacy using k-anonymity.  _Journal of the American Medical Informatics Association_ 15, 5 (2008), 627–637.
  * Fayyad and Irani (1993) Usama Fayyad and Keki Irani. 1993.  Multi-interval discretization of continuous-valued attributes for classification learning.  (1993).
  * Ghazi et al. (2022) Badih Ghazi, Pritish Kamath, Ravi Kumar, and Pasin Manurangsi. 2022.  Faster Privacy Accounting via Evolving Discretization. In _International Conference on Machine Learning_. PMLR, 7470–7483.
  * Gifford (2018) Richard Gifford. 2018\.  Legal technology: Criminal justice algorithms: Ai in the courtroom.  _Proctor, The_ 38, 1 (2018), 32–33.
  * Goethals et al. (2022) Sofie Goethals, Kenneth Sörensen, and David Martens. 2022\.  The privacy issue of counterfactual explanations: explanation linkage attacks.  _arXiv preprint arXiv:2210.12051_ (2022).
  * Gopi et al. (2021) Sivakanth Gopi, Yin Tat Lee, and Lukas Wutschitz. 2021\.  Numerical composition of differential privacy.  _Advances in Neural Information Processing Systems_ 34 (2021), 11631–11642.
  * Guidotti (2022) Riccardo Guidotti. 2022\.  Counterfactual explanations and how to find them: literature review and benchmarking.  _Data Mining and Knowledge Discovery_ (2022), 1–55.
  * Jang et al. (2016) Eric Jang, Shixiang Gu, and Ben Poole. 2016.  Categorical reparameterization with gumbel-softmax.  _arXiv preprint arXiv:1611.01144_ (2016).
  * Karimi et al. (2020a) Amir-Hossein Karimi, Gilles Barthe, Borja Balle, and Isabel Valera. 2020a.  Model-agnostic counterfactual explanations for consequential decisions. In _International Conference on Artificial Intelligence and Statistics_. PMLR, 895–905.
  * Karimi et al. (2020b) Amir-Hossein Karimi, Gilles Barthe, Bernhard Schölkopf, and Isabel Valera. 2020b.  A survey of algorithmic recourse: definitions, formulations, solutions, and prospects.  _arXiv preprint arXiv:2010.04050_ (2020).
  * Karimi et al. (2021) Amir-Hossein Karimi, Bernhard Schölkopf, and Isabel Valera. 2021.  Algorithmic recourse: from counterfactual explanations to interventions. In _Proceedings of the 2021 ACM conference on fairness, accountability, and transparency_. 353–362.
  * Klys et al. (2018) Jack Klys, Jake Snell, and Richard Zemel. 2018.  Learning latent subspaces in variational autoencoders.  _Advances in neural information processing systems_ 31 (2018).
  * Kohavi et al. (1996) Ron Kohavi et al. 1996\.  Scaling up the accuracy of naive-bayes classifiers: A decision-tree hybrid.. In _Kdd_ , Vol. 96. 202–207.
  * Kulesza et al. (2012) Alex Kulesza, Ben Taskar, et al. 2012\.  Determinantal point processes for machine learning.  _Foundations and Trends® in Machine Learning_ 5, 2–3 (2012), 123–286.
  * Lessmann et al. (2015) Stefan Lessmann, Bart Baesens, Hsin-Vonn Seow, and Lyn C Thomas. 2015.  Benchmarking state-of-the-art classification algorithms for credit scoring: An update of research.  _European Journal of Operational Research_ 247, 1 (2015), 124–136.
  * Lucic et al. (2022) Ana Lucic, Harrie Oosterhuis, Hinda Haned, and Maarten de Rijke. 2022.  FOCUS: Flexible optimizable counterfactual explanations for tree ensembles. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 36. 5313–5322.
  * Machanavajjhala et al. (2007) Ashwin Machanavajjhala, Daniel Kifer, Johannes Gehrke, and Muthuramakrishnan Venkitasubramaniam. 2007\.  l-diversity: Privacy beyond k-anonymity.  _ACM Transactions on Knowledge Discovery from Data (TKDD)_ 1, 1 (2007), 3–es.
  * Maddison et al. (2016) Chris J Maddison, Andriy Mnih, and Yee Whye Teh. 2016\.  The concrete distribution: A continuous relaxation of discrete random variables.  _arXiv preprint arXiv:1611.00712_ (2016).
  * Mahajan et al. (2019) Divyat Mahajan, Chenhao Tan, and Amit Sharma. 2019.  Preserving causal constraints in counterfactual explanations for machine learning classifiers.  _arXiv preprint arXiv:1912.03277_ (2019).
  * Mendes and Vilela (2017) Ricardo Mendes and João P Vilela. 2017.  Privacy-preserving data mining: methods, metrics, and applications.  _IEEE Access_ 5 (2017), 10562–10582.
  * Milli et al. (2019) Smitha Milli, Ludwig Schmidt, Anca D Dragan, and Moritz Hardt. 2019.  Model reconstruction from model explanations. In _Proceedings of the Conference on Fairness, Accountability, and Transparency_. 1–9.
  * Mothilal et al. (2020) Ramaravind K Mothilal, Amit Sharma, and Chenhao Tan. 2020\.  Explaining machine learning classifiers through diverse counterfactual explanations. In _Proceedings of the 2020 conference on fairness, accountability, and transparency_. 607–617.
  * Narayanan and Shmatikov (2006) Arvind Narayanan and Vitaly Shmatikov. 2006.  How to break anonymity of the netflix prize dataset.  _arXiv preprint cs/0610105_ (2006).
  * Nguyen and Skowron (1995) Son H Nguyen and Andrzej Skowron. 1995.  Quantization of real value attributes-rough set and boolean reasoning approach. In _Proc. of the Second Joint Annual Conference on Information Sciences, Wrightsville Beach, North Carolina, Sept 28-Oct 1_. Citeseer.
  * Nguyen et al. (2021) Van Nguyen, Trung Le, Olivier De Vel, Paul Montague, John Grundy, and Dinh Phung. 2021\.  Information-theoretic source code vulnerability highlighting. In _2021 International Joint Conference on Neural Networks (IJCNN)_. IEEE, 1–8.
  * Nguyen et al. (2022) Van Nguyen, Trung Le, Chakkrit Tantithamthavorn, John Grundy, Hung Nguyen, Seyit Camtepe, Paul Quirk, and Dinh Phung. 2022\.  An Information-Theoretic and Contrastive Learning-based Approach for Identifying Code Statements Causing Software Vulnerability.  _arXiv preprint arXiv:2209.10414_ (2022).
  * Pawelczyk et al. (2020) Martin Pawelczyk, Klaus Broelemann, and Gjergji Kasneci. 2020\.  Learning model-agnostic counterfactual explanations for tabular data. In _Proceedings of The Web Conference 2020_. 3126–3132.
  * Ramírez-Gallego et al. (2016) Sergio Ramírez-Gallego, Salvador García, Héctor Mouriño-Talín, David Martínez-Rego, Verónica Bolón-Canedo, Amparo Alonso-Betanzos, José Manuel Benítez, and Francisco Herrera. 2016.  Data discretization: taxonomy and big data challenge.  _Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery_ 6, 1 (2016), 5–21.
  * Redelmeier et al. (2021) Annabelle Redelmeier, Martin Jullum, Kjersti Aas, and Anders Løland. 2021.  MCCE: Monte Carlo sampling of realistic counterfactual explanations.  _arXiv preprint arXiv:2111.09790_ (2021).
  * Ribeiro et al. (2016) Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. 2016\.  ” Why should i trust you?” Explaining the predictions of any classifier. In _Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining_. 1135–1144.
  * Rissanen (1978) Jorma Rissanen. 1978\.  Modeling by shortest data description.  _Automatica_ 14, 5 (1978), 465–471.
  * Russell (2019) Chris Russell. 2019\.  Efficient search for diverse coherent explanations. In _Proceedings of the Conference on Fairness, Accountability, and Transparency_. 20–28.
  * Samarati and Sweeney (1998) Pierangela Samarati and Latanya Sweeney. 1998.  Protecting privacy when disclosing information: k-anonymity and its enforcement through generalization and suppression.  (1998).
  * Sharma et al. (2020) Shubham Sharma, Jette Henderson, and Joydeep Ghosh. 2020\.  Certifai: A common framework to provide explanations and analyse the fairness and robustness of black-box models. In _Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society_. 166–172.
  * Shokri et al. (2021) Reza Shokri, Martin Strobel, and Yair Zick. 2021\.  On the privacy risks of model explanations. In _Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society_. 231–241.
  * Shokri et al. (2017) Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. 2017.  Membership inference attacks against machine learning models. In _2017 IEEE symposium on security and privacy (SP)_. IEEE, 3–18.
  * Sokol and Flach (2019) Kacper Sokol and Peter A Flach. 2019.  Counterfactual explanations of machine learning predictions: opportunities and challenges for AI safety.  _SafeAI@ AAAI_ (2019).
  * Sutton et al. (1999) Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. 1999.  Policy gradient methods for reinforcement learning with function approximation.  _Advances in neural information processing systems_ 12 (1999).
  * Sweeney (2000) Latanya Sweeney. 2000\.  Simple demographics often identify people uniquely.  _Health (San Francisco)_ 671, 2000 (2000), 1–34.
  * Verma et al. (2020) Sahil Verma, John Dickerson, and Keegan Hines. 2020\.  Counterfactual explanations for machine learning: A review.  _arXiv preprint arXiv:2010.10596_ (2020).
  * Verma et al. (2022) Sahil Verma, Keegan Hines, and John P Dickerson. 2022\.  Amortized Generation of Sequential Algorithmic Recourses for Black-Box Models. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 36. 8512–8519.
  * Vo et al. (2023) Vy Vo, Van Nguyen, Trung Le, Quan Hung Tran, Reza Haf, Seyit Camtepe, and Dinh Phung. 2023.  An Additive Instance-Wise Approach to Multi-class Model Interpretation. In _The Eleventh International Conference on Learning Representations_.  https://openreview.net/forum?id=5OygDd-4Eeh
  * Waters and Miikkulainen (2014) Austin Waters and Risto Miikkulainen. 2014.  Grade: Machine learning support for graduate admissions.  _Ai Magazine_ 35, 1 (2014), 64–64.
  * Yang et al. (2018) Yongxin Yang, Irene Garcia Morillo, and Timothy M Hospedales. 2018\.  Deep neural decision trees.  _ICML Workshop on Human Interpretability in Machine Learning._ (2018).

##  Appendix A Experimental Details

###  A.1. Dataset statistics

  * •

German Credit (Dua and Graff, 2017): This dataset includes information of
customers taking credit at a bank. The task is to classify a customer as a
good (label $1$) or bad (label $0$) credit risk.

  * •

Adult Income (Kohavi et al., 1996): The dataset was extracted from the US 1994
census data on adult incomes. The task is to classify if an individual’s
income exceeds $50,000 per year (label $1$) or not (label $0$).

  * •

Graduate Admission (Acharya et al., 2019): The set contains data of Indian
students’ applications to a Master’s program. The original target variable is
an ordinal variable on the scale of $[0-1]$ indicating the chance of a student
being admitted, where $1$ indicates the highest chance. We set a threshold of
$0.7$ and re-categorize students as either ”having a higher chance” ($\geq
0.70$-label $1$) or ”having a lower chance” ($<0.70$-label $0$). The binary
classification task is to determine if a student profile has a higher chance
of being successful at their application.

  * •

Student Performance (Cortez and Silva, 2008): This dataset records the
performance of students at two schools Gabriel Pereira and Mousinho da
Silveira. The task is to predict if a student achieves a final score above
average (label $1$) or not (label $0$). The train and test splits contain data
of students from these two schools separately (Bui et al., 2022).

Table 7 summarizes the experimental settings for every dataset. Regarding the
underlying black-box models, we experiment with Logistic Regression for the
linear classifier and Neural Network for the non-linear classifier. We train
linear classifiers on German Credit and Student Performance, and non-linear
classifiers on Graduate Admission (with $3$ layers and $40$-dimensional hidden
units) and Adult Income (with $3$ layers and $30$-dimensional hidden units).
For each task, we further sample $20\%$ random observations of the training
sets as validation sets and train $5$ black-box models with the same
architecture but with different initializations. Since we have specified a
fixed subset of immutable features, we therefore can derive the minimum
sparsity level an explanation method should obey as

$\textrm{Min Sparsity}=\frac{\textrm{No. immutable features}}{\textrm{Total
no. features}}$

###  A.2. Model Design

We parameterize $\mathcal{G}$ and $\mathcal{S}$ with neural networks of $3$
and $2$ layers respectively. Each layer consists of a dense layer and a ReLU
activation, except the last layer of $\mathcal{S}$ takes Sigmoid activation to
produce a probability vector. The final layer of $\mathcal{G}$ is another
dense layer that outputs a logit vector of the same dimension as the input,
representing the counterfactual distribution. We set the sparsity loss
coefficient $\alpha=1e-4$ and use the same architecture for all tasks. We
train our model with Adam optimizer for $200$ epochs, at $\tau=0.2$ and a
learning rate of $1e-4$.

##  Appendix B Feature Constraints of Discretized Black-box Models

We here demonstrate how binary constraints can be effectively addressed within
L2C framework for realistic explanations. We use the same model architecture
and experimental setup, except that the data now is initially discretized and
the black-box classifiers are trained on the discretized feature space. Not
only would this help produce more realistic suggestions but it would also
enhance privacy protection. We reuse the Equal-frequency strategy for
consistency, yet note that practitioners are highly recommended to consider
generalizing the data in such a way that satisfies the privacy metrics
outlined in Section 5.2. We then run L2C models on German Credit and Adult
Income datasets with feature correlations specified in Table 7: respectively
the constraints Present residence $\rightarrow$ Age and Education level
$\rightarrow$ Age. To enforce the increasing constraint on the child variable
(i.e. Age), we further track the perturbation of the parent variable (i.e.
Present residence, Education level) and apply the Eq. (5) to update the
distribution of samples where the parent variable is indicated (by generator
$\mathcal{G}$) to increase. Table 6 reports the quality of explanations
produced under both types of constraints, where Binary measures the proportion
of examples $\mathbb{C}$ meeting the binary constraints. Here we again
substantiate the effectiveness of L2C in balancing counterfactual constraints.

Table 6. Desirability of counterfactual examples generated from L2C for
explaining a discretized black-box classifiers.

Harmonic Mean (%)$\uparrow$ |  Validity (%)$\uparrow$ |  Unary (%)$\uparrow$ |  Binary (%)$\uparrow$
---|---|---|---
German Credit
48.56% |  100.00% |  98.38% |  91.54%
Adult Income
23.89% |  100.00% |  100.00% |  100.00%

Table 7. Dataset statistics. ∗Features subject to non-decreasing constraints.

Dataset |  German |  Adult |  Graduate |  Student
---|---|---|---|---
|  Credit |  Income |  Admission |  Performance
Train/Dev/Test |  $640/160/200$ |  $28942/7235/9045$ |  $320/80/100$ |  $339/84/226$
No. features |  $20$ |  $13$ |  $7$ |  $14$
Immutable features |  Foreign worker |  Race |  University |  Mother’s edu.
No. liable people |  Sex |  rating |  Father’s edu.
Personal status |  Native country |  |  Family edu. support
Purpose |  Marital status |  |  First period grade
Feature constraints∗ |  Age |  Age |  Research |  Age
Present employment |  Education level |  experience |
Present residence |  |  |
Duration |  |  |
Feature correlations |  Increasing Age increases Present residence |  Increasing Education level increases Age |  |
Quasi-identifiers |  Age, Job |  Age |  |
Foreign worker |  Sex |  |
Personal status |  Race |  |
Present employment |  Relationship |  |
Present residence |  Marital status |  |
Property, Housing |  |  |
Sensitive features |  Credit amount |  Capital gain |  |
Savings account |  Capital loss |  |
Black-box model |  Logistic Regression |  Neural Network |  Neural Network |  Logistic Regression
Test accuracy |  $67.00\%$ |  $85.53\%$ |  $90.60\%$ |  $94.69\%$
Min Sparsity |  $20.00\%$ |  $30.77\%$ |  $14.29\%$ |  $38.57\%$

##  Appendix C Amortized Baselines

Table 8 compares L2C with popular amortized approaches: Feasible-VAE (Mahajan
et al., 2019), CRUDS (Downs et al., 2020) and FastAR (Verma et al., 2022)
across desiderata. We now provide the experimental setup for the amortized
baseline models. Whereas the non-amortized algorithms are run directly on the
testing sets, for amortized methods, we train the base generative models on
the training sets and use the testing sets only for evaluation. We tune the
base generative models under various different hyper-parameter settings via
grid search and report the best results. We determine the best settings via
two metrics: Coverage and Diversity. When there is a trade-off, Coverage is
chosen to be the deciding criterion.

Specifically, for Feasible-VAE (Mahajan et al., 2019), we tune the hidden
dimensions of the VAE encoder within $\\{10,30,50,70,90\\}$ and regularization
term on Validity within $\\{42,62,82,102,122\\}$. For CRUDS (Downs et al.,
2020), the base model is a Conditional Subspace Variational Auto-encoder (Klys
et al., 2018). In the original paper, the network only has $1$ hidden layer of
$64$ nodes, which we find to be of low capacity. We thus experiment with $2$
layers and different hidden dimensions within $\\{16,32,64\\}$. For FastAR
(Verma et al., 2022), the hyper-parameters include manifold distance $\lambda$
and entropy loss coefficient. Across datasets, Verma et al. (2022) shows the
best Coverage under $\lambda=0.1$. We thus set $\lambda=0.1$ as well in our
experiments, while focusing on tuning the latter hyper-parameter within
$\\{0.01,0.05,0.1,0.5,1.0\\}$. For the remaining hyper-parameters, we adopt
the best values reported by the authors. A pre-trained FastAR model can only
interpret one decision outcome chosen as the desired one (often the positive
label). We must therefore train separate FastAR models on the positive and
negative subsets and combine the results. We further find that although it is
straightforward to obtain multiple generations in a single model, FastAR
algorithm is optimized for one optimal counterfactual state for a given input.
Thus in the hope of achieving better diversity, we train $100$ different model
initializations and accordingly collect a set of $100$ explanations for
evaluation. The inference time accumulates as a result, which is the reason
why our reported results on time efficiency for FastAR are different from what
are reported in the authors’ paper.

##  Appendix D The Role of Feature Selector

We now validate the importance of learning the local feature-based selection
distribution via the feature selector $\mathcal{S}$. We first remove
$\mathcal{S}$ from L2C framework and replace the probability vector
$\bm{\pi}({\bm{z}})$ with a binary mask vector ${\bm{m}}\in[0,1]^{N}$ where
$m_{i}=1$ if $i\in\mathbb{K}$ (i.e., a mutable feature) and $m_{i}=0$
otherwise. We thus use $m_{i}$ in substitution of $s_{i}$ to update the
counterfactual representations $\widetilde{{\bm{z}}_{i}}$ as previously done.
We only optimize the generator $\mathcal{G}$ to learn the feature-based
perturbation distribution, and the training objective Eq. (4) excludes the
regularization term for sparsity accordingly. Figure 3 investigates the
performance of L2C under this alternative setup, in comparison with the
proposed method that jointly optimizes $\mathcal{S}$ and $\mathcal{G}$. L2C
still achieves $100\%$ of Validity and Coverage, so we only report the
relevant metrics.

One drawback of omitting the Selector component is that we lose the
flexibility in tailoring the quality of counterfactual generations to
potential user preferences. It is seen that the Selector introduces
significant sparsity to gain an effective balance for the trade-off against
diversity. Furthermore, these results support our claim about the role of the
generator $\mathcal{G}$ in that the perturbation distribution alone can yield
impressively diverse explanations with sparsity remaining under the required
maximum level. This is a benefit of learning an entire feature distribution in
that sometimes an output sample falls into the original input value i.e.,
$\widetilde{{\bm{z}}_{i}}={\bm{z}}_{i}$ while combining adequately with other
features.

##  Appendix E Qualitative Examples

Table 14 \- 17 illustrate some examples of our generated counterfactuals for
each dataset. For illustration purposes only, we report the discretized values
for numerical features where the edge values of each numerical interval are
rounded to the nearest whole number. Immutable features are italicized.

Table 8. Desirability of amortized counterfactual explanation methods.
$\downarrow$ Lower is better. $\uparrow$ Higher is better. Bold / Underline
indicates the best / second-best performance for each dataset. Time records
total inference time in seconds.

Method | Sparsity (%)$\uparrow$ | Diversity (%)$\uparrow$ | Harmonic Mean (%)$\uparrow$ | Validity (%)$\uparrow$ | Coverage (%)$\uparrow$ |  Unary (%)$\uparrow$ | Time(s)$\downarrow$
---|---|---|---|---|---|---|---
German Credit (Logistic Regression) - Min Sparsity: $20.00\%$
L2C (Ours) |  61.35 | 37.31 | 46.39 | 100.00 | 100.00 | 99.06 | 18
FastAR | 95.93 | 0.68 | 1.33 |  95.79 |  95.79 | 99.87 | 10,605
F-VAE | 45.93 | 1.59 | 3.06 | 100.00 | 100.00 | 74.41 |  36
CRUDS | 29.72 |  14.21 |  19.18 | 60.00 | 60.00 | 71.31 | 42,920
Graduate Admission (Neural Network) - Min Sparsity: $14.29\%$
L2C (Ours) | 42.23 | 37.90 | 39.94 | 100.00 | 100.00 | 100.00 | 4
FastAR |  27.97 | 1.32 | 2.35 |  87.41 |  87.41 |  85.28 | 5,405
F-VAE | 7.71 | 1.48 | 1.84 | 100.00 | 100.00 | 44.60 |  16
CRUDS | 11.31 |  17.38 |  13.40 | 60.28 | 76.00 | 49.00 | 21,460
Student Performance (Logistic Regression) - Min Sparsity: $38.57\%$
L2C (Ours) |  55.32 |  29.54 | 38.51 | 100.00 | 100.00 | 100.00 | 6
FastAR | 81.86 | 1.44 | 2.77 |  97.71 | 97.71 |  99.76 | 16,370
F-VAE | 27.37 | 7.68 | 11.92 | 100.00 | 100.00 | 69.68 |  36
CRUDS | 24.06 | 33.64 |  28.55 | 62.12 | 100.00 | 100.00 | 39,571

Figure 3. Analysis of L2C performance when the selector $\mathcal{S}$ is
removed.

##  Appendix F Additional Analysis on Discretizers

In the main paper, we have proven that the quality of L2C explanations is
relatively insensitive to the choice of discretizers. This means that we can
achieve interpretability without compromising the desiderata of a
counterfactual explanation. Here we conduct an additional privacy analysis for
similar purpose. In Table 9, we report our privacy analysis results on German
dataset across different discretization strategies. We reuse the settings
reported in the paper. It is observed that there is a same pattern with the
desiderata analysis: regardless of the choice of discretizers, the performance
of L2C compared to the baseline methods remains relatively stable.

Table 9. Privacy of L2C counterfactual explanations under various
discretization strategies on German dataset. ∗Proposed method.

Strategy |  1-Anoy. $\downarrow$ | 1-Diversity $\downarrow$ |  1-Map $\downarrow$
---|---|---|---
Equal Freq.∗ | 62.15% | 67.09% | 71.60% | 0.21%
MDP | 59.03% | 66.52% | 68.40% | 0.10%
CART | 65.88% | 69.24% | 74.25% | 0.18%
Domain Know. | 60.85% | 65.84% | 70.07% | 0.23%

For L2C, it is also possible to leverage different discretization methods on
different features. In practice, this strategy is highly recommended based on
user demand and/or human knowledge. In Tables 10 and 11 , we report the
performance of L2C on Adult dataset under Mixed discretization strategy.
Specifically, we randomly assign one of the four mentioned strategies (Equal
Frequency/MDP/CART/Domain Knowledge) to every continuous feature. The results
are averaged over $5$ different random initializations. It is seen that the
performance of L2C is well above the baselines where the privacy level remains
rather stable again.

Table 10. Desirability of L2C counterfactual explanations under mixed
discretization on Adult dataset. ∗Proposed method.

Strategy |  Sparsity (%)$\uparrow$ |  Diversity (%)$\uparrow$ |  Harmonic Mean (%)$\uparrow$ |  Validity (%)$\uparrow$ |  Coverage (%)$\uparrow$ | Unary (%)$\uparrow$ |  Time (s)$\downarrow$
---|---|---|---|---|---|---|---
Equal Freq.∗ | 45.70 | 28.11 | 34.80 | 100.00 | 100.00 | 97.62 | 444
Mixed | 43.62 | 38.83 | 41.00 | 100.00 | 100.00 | 100.00 | 378

Table 11. Privacy of L2C counterfactual explanations under mixed discretization on Adult dataset. ∗Proposed method. Strategy |  1-Anoy. $\downarrow$ |  1-Diversity $\downarrow$ |  1-Map $\downarrow$
---|---|---|---
Equal Freq.∗ | 5.07% | 14.90% | 39.58% | 0.00%
Mixed | 5.53% | 15.39% | 38.43% | 0.00%

##  Appendix G Degree of Feature Mutability

Following the setting from previous works, we currently limit our discussion
to binary states of mutability (i.e., whether a feature gets changed or not).
However, in practice, actionability should further deal with the difficulty
level associated with mutable features, also among their categorical levels.
Although this extension remains beyond existing works and ours, it can be seen
that L2C can be flexibly modified to handle these scenarios. We here sketch
some ideas for future works to explore.

Based on human experts, one can define a (constant) cost vector
$\phi\in[0,1]^{K}$ that reflects the (relative) level of difficulty among
mutable features (where $K$ is the number of mutable features and
$\sum^{K}_{i=1}\phi_{i}=1$). Recall in Section 3.3 that the feature-based
selection distribution (i.e., Bernoulli($\pi_{i}|z$)) for every feature $i$ is
given as

$\pi_{i}(z)=\frac{1}{1+\exp{\big{\\{}-\mathcal{S}_{i}(z)}\big{\\}}}.$

We want the features with high-cost values to be sampled less likely, meaning
to have a low probability of being changed. To lower such a probability, while
facilitating differentiable training, for every feature $i$, one can re-define
the feature-based selection distribution as $(1-\phi_{i})\times\pi_{i}(z)$, or

$\pi_{i}(z)=(1-\phi_{i})\times\frac{1}{1+\exp{\big{\\{}-\mathcal{S}_{i}(z)}\big{\\}}}.$

Another cost vector can also be defined for each categorical level of a
feature. One could reuse our mechanism to handle Unary constraints in Equation
(5) to explicitly force the model to generate more samples at the low-cost
levels (See Lines 494 - 520). Let $\phi_{ij}$ denote the cost of category $j$
of feature $i$, the perturbation distribution can be re-defined as

$p_{ij}(z)\propto(1-\phi_{ij})\times\frac{\exp\big{\\{}\mathcal{G}_{ij}(z)\big{\\}}}{\sum^{c_{i}}_{k=1}\exp\big{\\{}\mathcal{G}_{ik}(z)\big{\\}}},\forall
j=1,...,c_{i},$

##  Appendix H L2C under high dimensionality

Aware of the fact that high-dimensionality and sparsity can affect any
systems’ performance, we conduct an additional analysis to investigate the
performance of L2C on a high-dimensional textual dataset. We choose the use
case of Email Spam
Detection777https://archive.ics.uci.edu/ml/datasets/spambase where the feature
set is the vocabulary of the entire corpus and each word is considered a
binary feature (indicating whether a word appears in an email or not). A
possible scenario is an attacker somehow gains access to the detector and
would like to build a model explainer that can tell which word should be
removed in order to fool the detector.

This dataset contains up to $2,136$ features (after flattening), thus being
extremely sparse. To make it comparable, we reuse the same model architecture
and training settings in the other datasets. Table 12 reports the Validity and
Inference Time (per input when generating a set of $100$ samples) of L2C
explanations on this dataset, compared with the other datasets of smaller
scale.

Table 12. Validity and Time Efficiency of L2C w.r.t feature size.

Dataset | No. Features | Validity | Time per input
---|---|---|---
Graduate Admission | 34 | 100% | 40 ms
Student Performance | 48 | 100% | 30 ms
German Credit | 78 | 100% | 90 ms
Adult Income | 109 | 100% | 50 ms
Spam Detection | 2,136 | 87% | 13 s

We observe that for some extremely sparse data points, it is indeed difficult
to find enough valid counterfactuals within the time budget of 5 minutes,
leading to a total decrease in validity and an increase in the average
inference time, compared to the smaller datasets. However, even for such a
challenging dataset, L2C still works on a large number of inputs to achieve an
overall accuracy of $87\%$. If we compare L2C with DiCE - the closest baseline
in performance (also the most popular), we posit that L2C is more scalable
since DiCE iteratively perturbs every single feature, hence would be
catastrophically expensive when dealing with text data. Furthermore, we argue
that if the dataset contains more of the categorical features, it poses the
same serious issue to all counterfactual generation systems. Sparsity and
curse of dimensionality are thus long-standing problems in this research area,
which would result in a dedicated paper altogether. To address it may require
more careful investigation into the model design and hyper-parameter tuning,
which we leave open for future works.

Table 13. Discretization of numerical features in each dataset.

Feature name | Bucket values | No. Data points
---|---|---
German Credit
Duration (Months) | ( 4 , 12 ] | 359
( 12 , 18 ] | 187
( 18 , 24 ] | 224
| ( 24 , 72 ] | 230
Credit Amount | ( 247 , 1367 ] | 250
( 1367 , 2320 ] | 250
( 2320 , 3971 ] | 250
| ( 3971 , 18425 ] | 250
Age | ( 19 , 27 ] | 291
( 27 , 33 ] | 225
( 33 , 42 ] | 249
| ( 42 , 75 ] | 235
Adult Income
Age | ( 18 , 30 ] | 14,260
( 30 , 45 ] | 17,727
( 45 , 60 ] | 10,387
| ( 60 , 75 ] | 2,848
Capital gain |  $\leq$ 0 | 41,432
| ¿ 0 | 3,790
Capital loss |  $\leq$ 0 | 43,082
| ¿ 0 | 2,140
Hours per week | ( 0 , 20 ] | 3,602
| ( 20 , 40 ] | 27,843
| ( 40 , 100 ] | 13,777
Graduate Admission
GRE score | ( 290 , 312 ] | 189
( 312 , 322 ] | 148
( 322 , 340 ] | 163
TOEFL score | ( 92 , 104 ] | 176
( 104 , 110 ] | 175
( 110 , 120 ] | 149
Undergraduate GPA | ( 7 , 8 ] | 170
( 8 , 9 ] | 163
( 9 , 10 ] | 167
Student Performance
Age | ( 15 , 16 ] | 289
( 16 , 17 ] | 179
( 17 , 22 ] | 181
School absences | ( -0 , 4 ] | 466
( 4 , 32 ] | 183
First period grade | ( -0 , 10 ] | 252
( 10 , 13 ] | 245
( 13 , 19 ] | 152
Second period grade | ( -0 , 10 ] | 228
( 10 , 13 ] | 269
( 13 , 19 ] | 152

Table 14. Counterfactual examples from German Credit dataset. *DM: Deutsche
Mark

German Credit | Original input | Counterfactuals
---|---|---
| (Bad credit risk) | (Good credit risk)
Duration (months) | 12 - 18 | 24 - 72 | 18 - 24 | 12 - 18 | 18 - 24 | 12 - 18
Credit amount (DM) | 1367 - 2320 | 1367 - 2320 | 1367 - 2320 | 1367 - 2320 | 247 - 1367 | 247 - 1367
Age | 19 - 27 | 19 - 27 | 19 - 27 | 19 - 27 | 19 - 27 | 42 - 75
Checking account (DM) | no account | 200+ | no account | 200+ | under 200 | Under 0
Credit history | paid back duly | no credit taken | paid back duly | paid back duly | paid back duly | other credits
Purpose | furniture | furniture | furniture | furniture | furniture | furniture
Savings account (DM) | under 100 | under 500 | 1000+ | 1000+ | under 100 | under 100
Present employment since | 1 - 4 | 1 - 4 | 1 - 4 | 7+ | 1 - 4 | 1 - 4
Installment rate | Under 20 | Under 20 | Under 20 | Under 20 | Under 20 | Under 20
Personal status | Male | Male | Male | Male | Male | Male
divorce | divorced | divorced | divorced | divorced | divorced
Other debtors | none | none | guarantor | none | none | guarantor
Present residence since | 7+ years | 7+ years | 7+ years | 7+ years | 7+ years | 7+ years
Property | no property | no property | no property | insurance | real estate | no property
Other installment plans | none | none | none | none | none | none
Housing | rent | rent | rent | rent | own | own
No. existing credits | 1 | 1 | 1 | 1 | 1 | 1
Job | skilled | skilled | skilled | skilled | skilled | skilled
No. people being liable | 0 - 2 | 0 - 2 | 0 - 2 | 0 - 2 | 0 - 2 | 0 - 2
Telephone | No | Yes | Yes | No | No | No
Foreign worker | No | No | No | No | No | No

Table 15. Counterfactual examples from Adult Income dataset.

Adult Income | Original input | Counterfactuals
---|---|---
| (Low income) | (High income)
Age | 18 - 30 | 18 - 30 | 18 - 30 | 18 - 30 | 18 - 30 | 18 - 30
Capital gain | No | Yes | Yes | No | No | Yes
Capital loss | No | Yes | Yes | Yes | Yes | Yes
Hours per week | 20 - 40 | 20 - 40 | 20 - 40 | 20 - 40 | 20 - 40 | 20 - 40
Work class | Self-employed | Self-employed | Self-employed | Self-employed | Self-employed | Self-employed
Highest Edu. Level | 12 | 15 | 14 | 12 | 14 | 12
Marital status | Married-civ-sps. | Married-civ-sps. | Married-civ-sps. | Married-civ-sps. | Married-civ-sps. | Married-civ-sps.
Occupation | Craft repair | Other service | Adm clerical | Armed forces | Protective service | Sales
Relationship | Not in family | Wife | Other relative | Wife | Own child | Wife
Race | Black | Black | Black | Black | Black | Black
Sex | Female | Female | Female | Female | Female | Female
Native country | Hungary | Hungary | Hungary | Hungary | Hungary | Hungary

Table 16. Counterfactual examples from Graduate Admission dataset.

Graduate Admission | Original input | Counterfactuals
---|---|---
| (Low chance) | (High chance)
GRE Score | 290 - 312 | 290 - 312 | 312 - 323 | 290 - 312 | 290 - 312 | 290 - 312
TOEFL Score | 92 - 104 | 104 - 110 | 104 - 110 | 110 - 120 | 110 - 120 | 92 - 104
Undergraduate GPA | 7 - 8 | 8 - 9 | 9 - 10 | 9 - 10 | 8 - 9 | 9 - 10
University Rating | 2 / 5 | 2 / 5 | 2 / 5 | 2 / 5 | 2 / 5 | 2 / 5
Statement of Purpose | 2 / 5 | 2 / 5 | 5 / 5 | 2 / 5 | 2 / 5 | 2 / 5
Letter of Recommendation | 2.5 / 5 | 4 / 5 | 2.5 / 5 | 2.5 / 5 | 2.5 / 5 | 2 / 5
Research Experience | No | No | No | Yes | No | Yes

Table 17. Counterfactual examples from Student Performance dataset.

Student Performance | Original input (Fail) | Counterfactuals (Pass)
---|---|---
Age | 16 - 17 | 16 - 17 | 16 - 17 | 16 - 17 | 16 - 17 | 16 - 17
School absences | 0 - 4 | 0 - 4 | 0 - 4 | 4 - 32 | 0 - 4 | 4 - 32
First period grade | 10 - 13 | 10 - 13 | 10 - 13 | 10 - 13 | 10 - 13 | 10 - 13
Second period grade | 0 - 10 | 13 - 19 | 13 - 19 | 13 - 19 | 13 - 19 | 13 - 19
Mother’s education | Primary | Primary | Primary | Primary | Primary | Primary
Father’s education | None | None | None | None | None | None
Weekly study time | 2 - 5 hours | 2 - 5 hours | 2 - 5 hours | 2 - 5 hours | 5 - 10 hours | 4 - 10 hours
Family educational support | No | No | No | No | No | No
Wanting higher education | Yes | Yes | No | No | Yes | Yes
Internet access at home | Yes | No | Yes | Yes | No | No
In a romantic relationship | Yes | No | No | No | Yes | Yes
Free time | Moderate | High | Moderate | Moderate | Moderate | High
Going out frequency | Very often | Very often | Very often | Rarely | Very often | Very Often
Health status | Good | Good | Good | Very good | Good | Good