# Causal Feature Selection for Algorithmic Fairness

Sainyam Galhotra  University of Chicago<EMAIL_ADDRESS>,  Karthikeyan
Shanmugam  IBM Research AI<EMAIL_ADDRESS>,  Prasanna
Sattigeri  IBM Research AI<EMAIL_ADDRESS>and  Kush R. Varshney  IBM
Research AI<EMAIL_ADDRESS>
(2022)

###### Abstract.

The use of machine learning (ML) in high-stakes societal decisions has
encouraged the consideration of fairness throughout the ML lifecycle. Although
data integration is one of the primary steps to generate high quality training
data, most of the fairness literature ignores this stage. In this work, we
consider fairness in the integration component of data management, aiming to
identify features that improve prediction without adding any bias to the
dataset. We work under the _causal fairness_ paradigm (Salimi et al., 2019).
Without requiring the underlying structural causal model a priori, we propose
an approach to identify a sub-collection of features that ensure fairness of
the dataset by performing conditional independence tests between different
subsets of features. We use group testing to improve the complexity of the
approach. We theoretically prove the correctness of the proposed algorithm and
show that sub-linear conditional independence tests are sufficient to identify
these variables. A detailed empirical evaluation is performed on real-world
datasets to demonstrate the efficacy and efficiency of our technique.

Causal fairness, feature selection, fair machine learning

††journalyear: 2022††copyright: acmcopyright††conference: Proceedings of the
2022 International Conference on Management of Data; June 12–17, 2022;
Philadelphia, PA, USA††booktitle: Proceedings of the 2022 International
Conference on Management of Data (SIGMOD ’22), June 12–17, 2022, Philadelphia,
PA, USA††price: 15.00††doi: 10.1145/3514221.3517909††isbn:
978-1-4503-9249-5/22/06††ccs: Theory of computation Machine learning theory

##  1\. Introduction

Algorithmic fairness is of great societal concern when supervised
classification models are used to support allocation decisions in high-stake
applications. There have been numerous recent advances in statistically and
causally defining group fairness between populations delineated by protected
attributes and in the development of algorithms to mitigate unwanted bias
(Barocas et al., 2020).111We use the terms _sensitive attribute_ and
_protected attribute_ interchangeably. Bias mitigation algorithms are often
categorized into pre-processing, in-processing, and post-processing
approaches. Pre-processing techniques modify the distribution of the training
data, in-processing techniques modify the objective function of the training
procedure or consider additional constraints in the learning phase, and post-
processing techniques modify the output predictions — all in service of
improving fairness metrics while upholding classification accuracy
(d’Alessandro et al., 2017). Table 1 summarizes a representative set of prior
bias mitigation algorithms.

| Associational | Causal
---|---|---
Pre/Post-processing | (Calmon et al., 2017; Feldman et al., 2015; Kamiran and Calders, 2012) | (Salimi et al., 2019; Chiappa, 2019; Jiang et al., 2019)
In-processing | (Kamishima et al., 2012; Zafar et al., 2017; Calders and Verwer, 2010; Celis et al., 2019; Hardt et al., 2016) | (Nabi and Shpitser, 2018; Russell et al., 2017)
Feature Selection |  |
Discard biased attributes | - | This paper
Table 1. Different categories of fairness techniques.

However, this categorization misses an important stage in the lifecycle of
machine learning practice: data collection, engineering and management
(Schelter et al., 2019; Jo and Gebru, 2020). Holstein et al. (2019) report
that practitioners “typically look to their training datasets, not their ML
models, as the most important place to intervene to improve fairness in their
products”. Data integration, one of the first components of data management,
aims to join together information from different sources that captures rich
context and improves predictive ability. With the phenomenal growth of digital
data, ML practitioners may procure features from millions of sources spanning
data lakes, knowledge graphs, etc (Miller, 2018; Galhotra et al., 2019). They
typically generate exhaustive sets of features from all sources and then
perform subset selection (Zhang et al., 2016a; Konda et al., 2013; Galhotra et
al., 2019). Feature selection is a promising direction for fairness in ML as
it does not require assumptions about data distribution and is robust to
distribution shifts (Diaz et al., 2021), assuming distribution shifts do not
change the structural aspects of the causal model. Some may argue that data
integration is a part of pre-processing but we make this distinction as data
integration does not involve modification of the data distribution and is
considered as the task of a data engineer as opposed to a data modeler.

Filtering methods for feature selection exploit the correlation of features to
identify a subset (Hall, 1999). However, these techniques are ignorant of
sensitive attributes and fairness concerns. For example, consider a dataset
with features $F_{1}$ and $F_{2}$ such that $F_{1}$ provides slightly more
improvement in accuracy than $F_{2}$; however, incorporating $F_{1}$ yields a
classifier that reinforces discrimination against protected groups whereas
incorporating $F_{2}$ yields a classifier with similar outcomes for different
groups. Feature selection techniques that are not discrimination-aware will
prefer $F_{1}$ to $F_{2}$, but $F_{2}$ is a better feature to select from a
societal perspective.

To overcome the fairness limitations of standard feature selection methods, we
study the problem of fair feature selection, specifically in the context of
data integration when we are integrating new tables of features with an
existing training dataset (PK-FK joins) or source selection or generating new
features using transformations (Khurana et al., 2016; Diaz et al., 2021;
Galhotra et al., 2019). Our goal is to identify a subset of new features222Our
algorithms do not assume that all features are presented a priori and works in
case new features are added incrementally. that can be integrated with the
original dataset without worsening its biases against protected groups. As an
additional advantage, the feature selection paradigm is known to be stable
against changes in data distribution as compared to prior techniques that
modify the output predictions or the data distribution to mitigate bias (Singh
et al., 2019). Following the framework of prior fair algorithms (Salimi et
al., 2019; Chiappa and Isaac, 2018; Chiappa, 2019), we assume access to
protected/sensitive attributes which are used to identify the feature subset
that obeys fairness. The identification of features that do not induce
additional bias is tricky because of relationships between non-protected
attributes and protected ones that allow the reconstruction of information in
the protected attributes from one or more non-protected ones. For example, zip
code can reconstruct race information (Ingold and Soper, 2016).

There are two main types of techniques to ensure fairness in data:
Associational and Causal (summarized in Table 1). Associational techniques
look for associative relationships between sensitive attributes and the
prediction outcome to mitigate unwanted biases. However, these techniques are
based on correlation between attributes and fail to capture causal
relationships. There has been a lot of interest in studying causal frameworks
(Chiappa, 2019; Xu et al., 2019; Kusner et al., 2017; Jiang et al., 2019;
Chiappa and Isaac, 2018; Kilbertus et al., 2017; Zhang and Bareinboim, 2018b,
a; Khademi and Honavar, 2019; Khademi et al., 2019; Russell et al., 2017) to
achieve fairness. Due to their ability to distinguish different discrimination
mechanisms, we use _causal fairness_ (Salimi et al., 2019; Loftus et al.,
2018) as our fairness framework. Certain causal approaches assume access to
the underlying causal structure, which is unrealistic in practice (Chiappa,
2019; Xu et al., 2019; Kusner et al., 2017; Jiang et al., 2019; Chiappa and
Isaac, 2018; Kilbertus et al., 2017; Zhang and Bareinboim, 2018b).
_Importantly, we do not make the assumption that we are given the causal graph
(formally, the structure of the causal bayesian network that generates the
data) a priori._

We propose an algorithm SeqSel to identify all new features that when added to
the original dataset still ensure causal fairness. Our algorithm takes as
input a dataset $D$ comprising an outcome variable, sensitive features,
admissible features, and a collection of features that are neither admissible
nor sensitive. A feature is considered _admissible_ if the protected variables
are allowed to affect the outcome through it. For example, consider a credit
card application system that contains gender and race as sensitive attributes,
expected monthly usage as an admissible attribute (it may have a sensitive
attribute as one of its parent but it is permissible for the sensitive
attribute to influence the outcome through this variable), and age and
education level as variables which are neither sensitive nor admissible. A set
of features $\mathbf{X}$ is considered to ensure causal fairness if after
adding these features one could increase accuracy of a subsequently trained
classifier on this new dataset without worrying about causal fairness metrics,
i.e. in effect the subset of features when added does not introduce any
tradeoff between fairness and accuracy and they are safe to subsequent
attempts at building a purely predictive classifier. Our approach operates in
two phases focused towards performing conditional independence tests with
respect to the sensitive attributes and the target variable. These tests help
identify variables that (1) do not capture information about sensitive
attributes, or (2) ensure fairness even if they capture some information about
sensitive attributes. We theoretically prove that both types of these
variables ensure causal fairness and analyze the conditions to identify all
such variables.

The naïve SeqSel algorithm performs a number of conditional independence tests
that grows linearly in the number of features in the dataset. One of the major
shortcomings of extant conditional independence testing methods is that they
generate spurious correlations between variables if too many tests are
performed (Strobl et al., 2019). To overcome this limitation and reduce the
chances of getting spurious results, we propose a more efficient algorithm,
GrpSel, that uses graphoid axioms to show that _group testing_ can reduce the
number of tests to the logarithm of the number of features and additionally
improves the overall efficiency of the pipeline.

Our primary contributions are:

  * •

We formalize the problem of fairness in data integration and feature selection
setting using causal fairness.

  * •

We provide an algorithm that performs conditional independence tests to
identify the variables that do not worsen the fairness of the dataset.

  * •

We prove theoretical guarantees that the variables identified by our algorithm
ensure fairness and identify a closed form expression for variables that
cannot be added.

  * •

We propose an improved algorithm that leverages ideas of _group testing_ to
reduce the chances of getting spurious correlations and has sub-linear
complexity.

  * •

We show empirical benefits of our techniques on synthetic and real-world
datasets.

The paper represents a principled use to address an important problem that has
not been addressed before: fair data integration.

##  2\. Preliminaries

In this section, we review the background on algorithmic fairness and models
of causality.

We denote variables (also known as dataset attributes or features) by
uppercase letters like $X,S,A$, corresponding values in lower case like
$x,s,a$, and sets of attributes or values in bold ($\mathbf{X}$ or
$\mathbf{x}$).

###  2.1. Algorithmic Fairness

The area of algorithmic fairness aims to ensure unbiased output for different
sub-groups identified by specific set of attributes (also known as protected
or sensitive attributes). For example, a loan prediction software should not
discriminate against female applicants (gender is the protected attribute).
The literature on algorithmic fairness considers a set of protected attributes
$\mathbf{S}=\\{S_{1},\ldots,S_{|\mathbf{S}|}\\}$, a target variable $Y$ and a
prediction algorithm $f:\mathbf{V}\rightarrow Y$ where $\mathbf{V}$ denotes
the set of input attributes and the output of $f$ is called the prediction
output or an outcome. Typically, ML tasks train a classifier on a dataset $D$
(comprising of attributes $\mathbf{V}$ and target $Y$) which is assumed to be
distributed according to a distribution $\Pr$. In order to measure the
fairness of $f$ with respect to $\mathbf{S}$, two different types of metrics
have been studied: Associational and Causal.

Associational fairness methods capture statistical variabilities in the
behavior of the prediction algorithm for different groups of individuals. For
example, equalized odds requires that the false positive and true positive
rate of different sub-groups identified by the sensitive attributes is the
same. Other associational fairness measures include Demographic parity,
conditional statistical parity, and predictive parity (Kamishima et al., 2012;
Zafar et al., 2017; Calders and Verwer, 2010; Celis et al., 2019; Hardt et
al., 2016; Calmon et al., 2017). Even though associational methods of
quantifying fairness are very popular, all these methods fail to distinguish
between causal influence and spurious correlations between different input
attributes of the prediction algorithm (Salimi et al., 2019). To this end,
recent methods have proposed to capture the causal dependence of the outcome
on the protected attribute. Before describing these methods, we present a
background on causal graphs.

###  2.2. Causal DAGs

Probabilistic Causal DAG. A causal DAG over a set of variables $\mathbf{V}$ is
a directed acyclic graph $G$ that captures functional dependencies between
these variables. A variable $X_{1}$ is considered to cause $X_{2}$ iff
$X_{1}\rightarrow X_{2}$ in the causal DAG $G$. Each variable in the causal
graph $G$ is functionally determined by its parents and some unobserved
exogenous variables. The causal graph is used as a compact representation to
denote the dependence between different variables. Two variables $X$ and $Y$
are independent when conditioned on $Z$ if $\Pr(Y=y|X=x,Z=z)=\Pr(Y=y|X=x)$ and
is denoted by $X\perp Y|_{\Pr}Z$. To test this condition, we consider a
conditional independence (CI) test (Strobl et al., 2019) that returns if $X$
and $Y$ are independent conditioned on $Z$. An orthogonal line of work has
studied different techniques to efficiently test this condition (Strobl et
al., 2019). The joint probability distribution of a set of variables
$\mathbf{V}$ can be decomposed similar to that of bayesian networks,

(1) $\displaystyle\Pr(\mathbf{V})$
$\displaystyle=\prod_{X\in\mathbf{V}}\Pr(X|\texttt{Pa}(X)),$

where $\texttt{Pa}(X)$ denotes the set of parents of $X$ in the graph $G$.

d-separation and Faithfulness One of the common questions that are answered
using causal DAGs is whether $\mathbf{X}\perp\mathbf{Y}|\mathbf{Z}$, i.e. a
set of variables $\mathbf{X}$ is independent of $\mathbf{Y}$, conditioned on
$\mathbf{Z}$. d-separation between three sets of variables
$\mathbf{X},\mathbf{Y},\mathbf{Z}$, denoted by
$\mathbf{X}\perp\mathbf{Y}|_{d}\mathbf{Z}$, is a sufficient graphical
criterion that syntactically captures observed conditional independencies.
$\mathbf{X}$ and $\mathbf{Y}$ are said to be d-separated given $\mathbf{Z}$,
if all paths between $\mathbf{X}$ and $\mathbf{Y}$ are blocked by $\mathbf{Z}$
(Please refer to the full version (Galhotra et al., [n.d.]) for a formal
definition of blocking and d-separation). Probability distribution of a
dataset $D$ is said to be markov compatible (Pearl, 2009) if d-separation
implies CI with respect to the probability distribution $\Pr$. If the converse
also holds ($X\perp Y|_{\Pr}Z\implies X\perp Y|_{d}Z$ ), the probability
distribution $\Pr$ is considered faithful to the causal graph $G$ (Peters et
al., 2017). We assume throughout this work that $\Pr$ is markov compatible and
faithful to $G$. As CI and d-separation are equivalent under these
assumptions, we ignore the sub-script $\Pr$ or $d$ in subsequent discussions.
Faithfulness is a standard assumption in causal inference, which ensures that
all CI observed in the dataset correspond to d-separations in the
corresponding causal graph (Peters et al., 2017; Lauritzen and Sadeghi, 2018;
Pearl, 2009). Graphoid axioms (Sadeghi, 2017; Lauritzen and Sadeghi, 2018;
Pearl, 2009) are the popular set of properties that are used to infer
conditional independence. We list two axioms that are relevant for this study.

###### Lemma 2.1 (Theorem 1 (Lauritzen and Sadeghi, 2018)).

Consider a dataset $D$ with a causal graph $G$, where the data distribution
$\Pr$ is faithful to the graph $G$.

  1. (1)

Decomposition axiom: If $A\bot B,C|Z$, then $A\bot B|Z$ and $A\bot C|Z$

  2. (2)

Composition axiom: If $A\bot B|Z$ and $A\bot C|Z$, then $A\bot B,C|Z$

###### Proof.

We use the notion of d-separation to prove these results.

_Decomposition axiom:_ If $A\bot B,C|Z$, then all paths from $A$ to any of $B$
or $C$ are blocked given $Z$. Therefore, any path from $A$ to $B\subseteq
B\cup C$ is also blocked given $Z$. Therefore, $A\bot B|Z$. Symmetrically, the
same argument proves that $A\bot C|Z$. Therefore, $A\bot B,C|Z$. ∎

do-operator. Pearl (Pearl, 2009) defined intervention as a modification of the
state of attributes to a specific value and observe its effect. An
intervention on an attribute $X\leftarrow x$ is equivalent to assigning a
value $x$ to the variable $X$ in a modified causal graph $G^{\prime}$, where
$G^{\prime}$ is same as $G$ except that all incoming edges of $X$ have been
removed. According to Pearl (Pearl, 2009), do-operator is equivalent to the
graphical interpretation of an intervention. An intervention
$\texttt{do}(X)=x$ is equivalent to conditioning $X=x$ if $X$ has no ancestors
in $G$.

###  2.3. Causal Fairness

There has been a lot of recent interest in studying the causal impact of
protected attributes on the prediction variable. Causal measures capture the
causal dependence of the prediction variable on the sensitive attributes and
aim to minimize such effects at different population levels.

Admissible Attributes. In an ideal setting, the prediction attribute and the
protected attributes should be d-separated in the causal graph whenever we
intervene on the protected attributes. However, it is a very restrictive and
impractical requirement (Salimi et al., 2019). To improve the usefulness of
this definition, a subset of the attributes are labelled admissible, through
which protected attribute is allowed to impact the prediction attribute. For
example, applicant’s choice of loan type or loan duration in a banking
application. The set of admissible attributes also help to understand the
impact of different attributes on the prediction accuracy and fairness. The
specification of attributes as admissible is application-dependent and are
considered as an input to the problem.

One of the recent causal fairness definitions, interventional fairness (Salimi
et al., 2019) is the strongest notion of fairness that is testable over the
input dataset and correctly captures group level fairness. It assumes that the
input attributes $\mathbf{V}$ consist of admissible attributes $\mathbf{A}$,
through which the sensitive attributes are allowed to influence the prediction
output. The fairness definition in (Salimi et al., 2019) was designed to study
datasets and focused on the target attribute $Y$. We extend this definition to
analyze fairness of ML classifiers by analyzing the effect of sensitive
attributes on $Y^{\prime}$, the prediction output.

###### Definition 2.2 (Causal Fairness).

For a given set of admissible variables, $\mathbf{A}$, a classifier is
considered fair if for any collection of values $a$ of $\mathbf{A}$ and output
$Y^{\prime}$, the following holds:
$Pr(Y^{\prime}=y|\texttt{do}(\mathbf{S})=\mathbf{s},\texttt{do}(\mathbf{A}=\mathbf{a}))=Pr(Y^{\prime}=y|\texttt{do}(\mathbf{S})=\mathbf{s}^{\prime},\texttt{do}(\mathbf{A}=\mathbf{a}))$
for all values of $\mathbf{A}$, $\mathbf{S}$ and ${Y^{\prime}}$.

###### Example 2.3.

Consider a loan prediction software (ger, 2013) that considers demographic
attributes along with credit information and loan preferences. Among input
attributes, race and gender are considered protected and loan preferences like
loan type and duration are generally considered admissible because any bias
due to sensitive attributes is allowed to affect the outcome only if it is
through individual’s preferences. Other attributes like age, zip-code, income,
education, etc are considered neither admissible nor inadmissible.

In this dataset, some features like zip-code have been identified as proxy
features which are causally dependent on race. Using any of these proxy
features for classifier training can inject bias into the system. According to
Definition 2.2, the protected attributes $\mathbf{S}$ are independent of
$Y^{\prime}$ conditioned on $\mathbf{A}$ in the intervened graph (incoming
edges of $\mathbf{S}$ and $\mathbf{A}$ are removed), say $G^{\prime}$. In
other words, $\mathbf{S}$ and $Y^{\prime}$ are d-separated conditioned on
$\mathbf{A}$ in $G^{\prime}$. For more insights about the definition of causal
fairness, we refer the reader to (Salimi et al., 2019). Recent work has also
studied causal fairness in settings where the protected attribute is
unobserved (Galhotra et al., 2021).

Testing causal fairness. Causal fairness is an interventional definition that
is represented using do operators. A straightforward way to test this
definition is to leverage a fully specified causal graph (graph structure and
equations) to estimate the post-intervention probability values. However,
fully specified causal graphs are not available in practice and this
definition can not be tested as is. Instead, we present a sufficient condition
to test for causal fairness.

###### Lemma 2.4.

If conditional-mutual information between the classifier output $Y^{\prime}$
and protected attributes $\mathbf{S}$ is zero when conditioned on the
admissible set $\mathbf{A}$, i.e., $I(Y^{\prime},\mathbf{S}|A=\mathbf{a})=0$
then $Y^{\prime}$ is causally fair.

(a) $X_{2}$ is a biased variable (b) $X_{1},X_{2},X_{3}$ ensure fairness (c)
$X_{1},X_{2},X_{3}$ ensure fairness

Figure 1. Example causal graphs that demonstrate different types of variables.

##  3\. Problem Statement

In this section, we define the problem of feature selection to ensure
interventional fairness and provide high level intuition of the involved
challenges.

Consider a dataset $D$ comprising of a disjoint set of two types of features
(i) Sensitive $\mathbf{S}=\\{S_{1},\ldots,S_{|\mathbf{S}|}\\}$ and (ii)
Admissible $\mathbf{A}=\\{A_{1},\ldots,A_{|\mathbf{A}|}\\}$ along with a
target variable $Y$. Let $\mathbf{X}=\\{X_{1},\ldots,X_{n}\\}$ denote the
collection of $n$ features that are neither admissible nor sensitive and can
be added to $D$ by performing a join between the input dataset and different
datasets from different sources or by feature transformation over a subset of
the features. Let $\mathbf{V}=\mathbf{A}\cup\mathbf{S}\cup\mathbf{X}\cup Y$
denote the exhaustive list of available variables and $Y^{\prime}$ denote the
learnt target variable which has been trained over a subset
$\mathbf{T}\subseteq\mathbf{V}$. Now, we present the definition of causally
fair features that can be added to the original dataset.

###### Definition 3.1 (Causally Fair Features).

For a given set of admissible variables, $\mathbf{A}$, we say a collection of
features $D=\mathbf{A}\cup\mathbf{T}$ is causally fair if the bayes optimal
predictor $Y^{\prime}$, trained on $D$ satisfies causal fairness with respect
to sensitive attributes $\mathbf{S}$.

The goal is to identify the largest subset $\mathbf{T}\subseteq\mathbf{V}$
such that the variable $Y^{\prime}$, trained using these variables is fair.

###### Problem 1.

Given a dataset $D=\\{\mathbf{A},\mathbf{S},Y\\}$ and a collection of
variables $\mathbf{X}$, identify the largest subset
$\mathbf{T}\subseteq\mathbf{X}$ such that the features
$D^{\prime}=\mathbf{A}\cup\mathbf{T}$ is causally-fair.

The goal of our problem is to identify all features that can be considered for
training a classifier without worsening the fairness of the dataset $D$. Note
that $D$ contains only features $\mathbf{S}\cup\mathbf{A}$ to begin with, so
there is no fairness violation as sensitive attributes are allowed to
influence $Y^{\prime}$ through $\mathbf{A}$ and $\mathbf{S}$ are not used for
training. We make the following assumptions about the causal graph:

###### Assumption 1 (Faithfulness assumption).

The causal graph $G$ on $\mathbf{V}$ is faithful to the observational
distribution on $\mathbf{V}$.

This assumption implies that if two variables $A$ and $B$ are connected in the
causal graph, the data cannot result in any spurious conditional independency
of the form $(A\perp B|\mathbf{C})$ for any subset
$\mathbf{C}\subset\mathbf{V}\setminus\\{A,B\\}$. Faithfulness assumption is
one of the most common assumptions in causality and fairness literature
(Chiappa, 2019; Xu et al., 2019; Kusner et al., 2017; Jiang et al., 2019;
Chiappa and Isaac, 2018; Kilbertus et al., 2017; Zhang and Bareinboim, 2018b,
a; Khademi and Honavar, 2019; Khademi et al., 2019; Russell et al., 2017;
Salimi et al., 2019), which is crucial to model the input dataset.

Classifier Training. A new variable $Y^{\prime}$ (prediction variable) is
generated by learning a predictor over the selected subset of features
($\mathbf{A}\cup\mathbf{T}$), and this predictor is the Bayes optimal
classifier with $Pr[Y^{\prime}|\mathbf{A}\cup\mathbf{T}]$ derived from the
observational distribution $P(\mathbf{V})$. It is equivalent to adding
$Y^{\prime}$ as a new node in the causal graph which is a children of all
features that impact the classifier output. We make Assumption 2 to ensure
that one would apply the same Bayes optimal predictor that has been learnt
from observational data to all datasets irrespective of the intervention. This
assumption is crucial to decouple fairness of feature selection from the
training procedure and to theoretically analyze the quality of bias removal in
feature selection. Training the classifier by performing feature engineering
over the identified features satisfies this assumption.

###### Assumption 2.

For evaluating the fairness criterion in Definition 3.1 using hypothetical
interventional distributions, we assume that the mechanism generating
$Y^{\prime}$ is the same as $P[Y^{\prime}|\mathbf{A}\cup\mathbf{T}]$ where
$P(\cdot)$ is the observational distribution.

Problem intuition: According to the definition of causal fairness, the output
distribution of the prediction algorithm should not change when the value of
sensitive variables is changed whenever we intervene on $\mathbf{A}$.
According to do-calculus, intervention on ($\mathbf{A}$) is equivalent to
removal of its incoming edges and conditioning on $\mathbf{A}$. If all paths
from the sensitive variables to the learnt target $Y^{\prime}$ that go through
the variables considered by $f$ are blocked after an intervention on the
admissible variables, then the features considered by $f$ are causally-fair.
We first show that the maximal set of features that ensure causal fairness is
unique.

###### Lemma 3.2.

Consider two different set of attributes $\mathbf{X_{1}}$ and $\mathbf{X_{2}}$
such that $\mathbf{X_{1}}\neq\mathbf{X_{2}}$. If a classifier trained on
$\mathbf{X_{1}}$ and $\mathbf{X_{2}}$ separately is causally fair, then a
classifier trained on $\mathbf{X_{1}}\cup\mathbf{X_{2}}$ is also causally
fair.

###### Proof.

Let $Y_{1}^{\prime}$ and $Y_{2}^{\prime}$ denote the output variable of the
classifier trained on $\mathbf{X_{1}}$ and $\mathbf{X_{2}}$. Let $G^{\prime}$
denote a modified causal graph where incoming edges of $\mathbf{S}$ and
$\mathbf{A}$ are removed. According to the definition of causal fairness, all
paths from the sensitive atrributes to $Y_{1}^{\prime}$ are blocked in
$G^{\prime}$, i.e. $\mathbf{S}\bot Y_{1}^{\prime}|_{G^{\prime}}\mathbf{A}$.
Since, $Y_{1}^{\prime}$ is a child of attributes in $\mathbf{X_{1}}$, all
paths from $\mathbf{S}$ to the parents of $Y_{1}^{\prime}$ are blocked, i.e.,
$\texttt{Pa}(Y_{1}^{\prime})\bot\mathbf{S}|_{G^{\prime}}\mathbf{A}$. We get
the same condition for $\mathbf{X_{2}}$. Let $Y^{\prime}=f(\mathbf{X_{1}\cup
X_{2}})$. We first simplify the LHS of causal fairness definition as follows.

$\displaystyle\Pr(Y^{\prime}=y|\texttt{do}(\mathbf{S})=\mathbf{s},\texttt{do}(\mathbf{A})=\mathbf{a})$
$\displaystyle=\sum_{\texttt{Pa}(Y^{\prime})=\mathbf{c}}(\Pr(Y^{\prime}=y|\texttt{Pa}(Y^{\prime})=\mathbf{c},\texttt{do}(\mathbf{S})=\mathbf{s},\texttt{do}(\mathbf{A})=\mathbf{a})\times$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\Pr(\texttt{Pa}(Y^{\prime})=\mathbf{c}|\texttt{do}(\mathbf{S})=\mathbf{s},\texttt{do}(\mathbf{A})=\mathbf{a}))$
$\displaystyle=\sum_{\texttt{Pa}(Y^{\prime})=\mathbf{c}}\Pr(Y^{\prime}=y|\texttt{Pa}(Y^{\prime})=\mathbf{c})\Pr(\texttt{Pa}(Y^{\prime})=\mathbf{c}|\texttt{do}(\mathbf{S})=\mathbf{s},\texttt{do}(\mathbf{A})=\mathbf{a})$
$\displaystyle=\sum_{\texttt{Pa}(Y^{\prime})=\mathbf{c}}\Pr(Y^{\prime}=y|\texttt{Pa}(Y^{\prime})=\mathbf{c})\texttt{Pr}_{G^{\prime}}(\texttt{Pa}(Y^{\prime})=\mathbf{c}|\mathbf{S}=\mathbf{s},\mathbf{A}=\mathbf{a})$

Since, $Y^{\prime}$ is trained over $\mathbf{X_{1}}$ and $\mathbf{X_{2}}$,
$\texttt{Pa}(Y^{\prime})\subseteq\mathbf{X_{1}}\cup\mathbf{X_{2}}$. Therefore,
$Pa(Y^{\prime})\bot_{G^{\prime}}\mathbf{S}|\mathbf{A}$, implying
$\texttt{Pr}_{G^{\prime}}(\texttt{Pa}(Y^{\prime})=\mathbf{c}|\mathbf{S}=\mathbf{s},\mathbf{A}=\mathbf{a})=\texttt{Pr}_{G^{\prime}}(\texttt{Pa}(Y^{\prime})=\mathbf{c}|\mathbf{A}=\mathbf{a})$.
Following the same simplification on RHS of Definition 3.1, we get that
$\mathbf{X_{1}\cup X_{2}}$ are causally fair. ∎

Using Lemma 3.2, we prove that problem 1 has a unique solution.

###### Lemma 3.3.

Problem 1 has a unique solution $\mathbf{T}^{*}$.

###### Proof.

Suppose, Problem 1 does not have a unique solution. Let $\mathbf{T}_{1}$ and
$\mathbf{T}_{2}$ be two different maximal sets of features that ensure causal
fairness. Using Lemma 3.2, $\mathbf{T}_{1}\cup\mathbf{T}_{2}$ also ensure
causal fairness. Since $\mathbf{T}_{1}\neq\mathbf{T}_{2}$,
$|\mathbf{T}_{1}\cup\mathbf{T}_{2}|>|\mathbf{T}_{1}|,|\mathbf{T}_{2}|$. This
is a contradiction, as $\mathbf{T}_{1}$ and $\mathbf{T}_{2}$ are maximal sets.
Therefore, the assumption that Problem 1 does not have a unique solution is
wrong. ∎

##  4\. Solution Approach

In this section, we first present key properties using an example and
generalize them to discuss our algorithm, SeqSel. Section 4.2 analyzes the
different steps of Algorithm 1 to guarantee causal fairness of identified
features and Theorem 4.3 presents a close-form expression to identify maximal
set of causally-fair features.

###  4.1. Algorithm

One naïve solution to ensure fairness is to consider only the admissible
variables $\mathbf{A}$ for prediction and not add any other feature to the
dataset $D$. This would satisfy the fairness condition but achieve poor
prediction performance as there may be a variable $X\in\mathbf{X}$ that is
highly correlated with the target variable $Y$. Another extreme solution is to
consider all the variables of $\mathbf{X}$ for prediction. This approach would
yield high predictive performance but can have arbitrarily poor fairness. We
propose SeqSel (Algorithm 1) which considers the collection of variables
$\mathbf{A}$, $\mathbf{S}$ and $\mathbf{X}$ to identify the largest subset of
$\mathbf{X}$ which when considered along with $\mathbf{A}$ ensure causal
fairness of the learnt variable $Y^{\prime}$. SeqSel algorithm performs CI
tests over the observed data without explicit knowledge of the underlying
causal graph. We use causal graphs only to illustrate the intuition behind the
different components of our algorithm.

Figure 1 presents different example causal graphs, to understand the solution
approach and identify CI tests that can be performed without inferring the
complete causal graph. These graphs contain sensitive variables $\mathbf{S}$,
admissible variables $\mathbf{A}$, target variable $Y$ along with other
subsidiary variables $X_{i}$’s.

  1. (1)

In all three figures, variables like $X_{1}$ have unblocked paths from
$\mathbf{S}$ to $X_{1}$ but all these paths are blocked by the admissible set.
Therefore, these variables do not capture any new information about the
protected variables. In general, such variables can be identified by checking
if $X_{1}$ is conditionally independent of $\mathbf{S}$ given $\mathbf{A}$,
i.e. $(X_{1}\perp\mathbf{S}|\mathbf{A})$.

  2. (2)

Variables like $X_{3}$ in Figure 1(b) are independent of the sensitive
attributes and can be identified easily by performing CI test between variable
$X$ and $\mathbf{S}$.

  3. (3)

Variable like $X_{3}$ in Figure 1(c) is not independent of $S_{1}$ but is
independent of $S_{1}$ given $A_{2}$. $X_{3}$ ensures causal fairness and can
be identified by testing $X_{3}\perp\mathbf{S}|A_{2}$.

  4. (4)

$X_{2}$ in Figure 1(b) and 1(c) is not independent of $S_{1}$ even with an
intervention on $\mathbf{A}$ and captures sensitive information. However,
$X_{2}$ is independent of $Y$ given $\mathbf{A}$.

Algorithm 1 SeqSel

1:Input: Variables $\mathbf{A},\mathbf{S},\mathbf{X},Y$

2:$\mathbf{C}_{1}\leftarrow\phi$

3:for $X\in\mathbf{X}$ do$\triangleright$ First phase

4: if $\exists A\subseteq\mathbf{A}\text{ such that}(X\perp\mathbf{S}|{A})$
then $\triangleright$ CI test condition

5: $\mathbf{C}_{1}\leftarrow\mathbf{C}_{1}\cup\\{X\\}$

6:$\mathbf{C}_{2}\leftarrow\phi$$\triangleright$ Second phase

7:$\mathbf{X}\leftarrow\mathbf{X}\setminus\mathbf{C}_{1}$

8:for $X\in\mathbf{X}$ do

9: if $(X\perp Y|\mathbf{A}\cup\mathbf{C}_{1})$ then

10: $\mathbf{C}_{2}\leftarrow\mathbf{C}_{2}\cup\\{X\\}$

11:return $\mathbf{C}_{1}\cup\mathbf{C}_{2}$

The different types of variables considered in points 1-3 above do not capture
any sensitive information after intervening on $\mathbf{A}$ or any subset of
$\mathbf{A}$. We denote these variables by $\mathbf{C}_{1}$, identified by
testing CI of $X$ with $\mathbf{S}$ given any subset of $\mathbf{A}$.
Therefore, all paths from $\mathbf{S}\rightarrow X\rightarrow Y$ are blocked
for all these variables. The variables that capture sensitive information but
are independent of $Y$ given all the selected features
$\mathbf{C}_{1}\cup\mathbf{A}$ also do not impact the bayes-optimal
classifier. This shows that all the variables discussed above ensure causal
fairness. Any variable that is not independent of $\mathbf{S}$ and $Y$ even
after intervening on $\mathbf{A}$ is biased and is not safe to be added.
$X_{2}$ in Figure 1(a) is one such example. Consider a variation in Figure
1(b) by adding an edge $X_{3}\rightarrow X_{1}$. Even then $X_{1}$ is a valid
feature to ensure causal fairness. However, $X_{1}\not\perp S_{1}|A_{1}$ and
therefore, the above mentioend CI conditions do not capture such variables.
Specifically, if a variable $X$ has a blocked path from $S$ which forms a
collider at the admissible attribute $A$, then above mentioned CI tests do not
capture $X$ in the set of fair features. We discuss this condition more
formally in Theorem 4.3.

###### Remark 1.

In Figure 1(a), $X_{2}\nrightarrow X_{1}$ because there does not exist any
path from $\mathbf{S}$ to $X_{1}$ which is unblocked given $\mathbf{A}$.

###### Remark 2.

If $\mathbf{C}_{2}$ is conditionally independent of $Y$ given $\mathbf{A},\
\mathbf{C}_{1}$, it may not contribute towards the predictive power of the
Bayes optimal classifier trained on these variables. However, for most
practical purposes the classifier trained can leverage $\mathbf{C}_{2}$ for
better prediction.

Algorithm 1 captures these intuitions to perform CI tests in two phases. The
first phase (lines 3-5) identifies all variables that do not get affected by
sensitive attributes, in the presence of admissible attributes $\mathbf{A}$ or
any subset of $\mathbf{A}$. All these variables do not capture any extra
information about sensitive attributes and are safe to be added to the dataset
$D$. The rest of the variables, $\mathbf{X}\setminus\mathbf{C}_{1}$, capture
information about sensitive attributes which can worsen fairness of the
dataset. The second phase (lines 6-10) identifies the subset such that the
target variable is not affected by their sensitive information in the presence
of admissible attributes. We call this algorithm SeqSel as it sequentially
performs CI tests to select features.

###  4.2. Theoretical Analysis

In this section, we show that the variables identified by SeqSel ensure causal
fairness. We consider the original causal graph $G$ along with a new variable
$Y^{\prime}$ that refers to the prediction variable trained using the
variables $\mathbf{A}$ along with the variables returned by Algorithm 1. We
first show that the variables $\mathbf{C}_{1}$ and $\mathbf{C}_{2}$ identified
by Algorithm 1 maintain causal fairness. For this analysis, we assume that the
target variable $Y$ does not have a child.

###### Lemma 4.1.

Consider a dataset $D$ with admissible variables $\mathbf{A}$ and sensitive
$\mathbf{S}$ and a collection of variables $\mathbf{C}_{1}$. If $\exists
A\subseteq\mathbf{A}$ such that $(\mathbf{C}_{1}\perp\mathbf{S}|{A})$ then
$\mathbf{A}\cup\mathbf{C}_{1}$ is causally fair.

###### Proof.

Given $(\mathbf{C}_{1}\perp\mathbf{S}|{A})$ for some $A\subseteq$, the
variable $X$ does not capture any information about the sensitive variables.
Hence all paths from $\mathbf{S}$ to the target $Y$ that pass through $X$ are
blocked. Mathematically, we consider a causal graph along with $Y^{\prime}$
and evaluate the distribution under the intervention of $\mathbf{A}$ and
$\mathbf{S}$ as follows.

$\displaystyle
Pr[Y^{\prime}|do(\mathbf{S}),do(\mathbf{A})]=\sum_{\mathbf{C}_{1}}Pr[Y^{\prime}|\mathbf{C}_{1},do(\mathbf{S}),do(\mathbf{A})]Pr[\mathbf{C}_{1}|do(\mathbf{S}),do(\mathbf{A})]$
Using Lemma 9 from the full version (Galhotra et al., [n.d.]) $\displaystyle=$
$\displaystyle\sum_{\mathbf{C}_{1}}Pr[Y^{\prime}|\mathbf{C}_{1},do(\mathbf{S}),do(\mathbf{A})]Pr[\mathbf{C}_{1}|do(\mathbf{A})]$
Using Lemma 10 from the full version $\displaystyle=$
$\displaystyle\sum_{\mathbf{C}_{1}}Pr[Y^{\prime}|\mathbf{C}_{1},do(\mathbf{A})]Pr[\mathbf{C}_{1}|do(\mathbf{A})]=Pr[Y^{\prime}|do(A)]$

This shows that any intervention on $\mathbf{S}$ does not affect the variable
$Y^{\prime}$, thereby ensuring causal fairness of the considered features. ∎

The following lemma justifies the addition of $\mathbf{C}_{2}$ to the dataset
$D$ without affecting its causal fairness.

###### Lemma 4.2.

Consider a dataset $D$ with admissible variables $\mathbf{A}$ and sensitive
$\mathbf{S}$, a set of variables $\mathbf{C}_{1}$ satisfying
$(\mathbf{C}_{1}\perp\mathbf{S}|\mathbf{A})$ and a collection of variables
$\mathbf{C}_{2}$ with $(\mathbf{C}_{2}\not\perp\mathbf{S}|\mathbf{A})$, if
$(\mathbf{C}_{2}\perp Y|\mathbf{A},\mathbf{C}_{1})$ then
$\mathbf{A}\cup\mathbf{C}_{2}\cup\mathbf{C}_{1}$ is causally fair.

###### Proof.

We simplify the causal fairness condition as follows:

$\displaystyle Pr[Y^{\prime}|do(\mathbf{S}),do(\mathbf{A})]$
$\displaystyle=\sum_{\mathbf{C}_{1},\mathbf{C}_{2}}\Big{(}Pr[Y^{\prime}|\mathbf{C}_{1},\mathbf{C}_{2},do(\mathbf{S}),do(\mathbf{A})]\times
Pr[\mathbf{C}_{1},\mathbf{C}_{2}|do(\mathbf{S}),do(A)]\Big{)}$ Using Lemma 10
from the full version (Galhotra et al., [n.d.])
$\displaystyle=\sum_{\mathbf{C}_{1},\mathbf{C}_{2}}\Big{(}Pr[Y^{\prime}|\mathbf{C}_{1},\mathbf{C}_{2},do(A)]\times
Pr[\mathbf{C}_{2}|\mathbf{C}_{1},do(\mathbf{S}),do(A)]Pr[\mathbf{C}_{1}|do(\mathbf{S}),do(A)]\Big{)}$
Since $Y^{\prime}$is independent of $\mathbf{C}_{2}$ given $\mathbf{A}$ and
$\mathbf{C}_{1}$
$\displaystyle=\sum_{\mathbf{C}_{1},\mathbf{C}_{2}}\Big{(}Pr[Y^{\prime}|\mathbf{C}_{1},do(A)]Pr[\mathbf{C}_{2}|\mathbf{C}_{1},do(\mathbf{S}),do(A)]\times
Pr[\mathbf{C}_{1}|do(\mathbf{S}),do(A)]\Big{)}$ Summing
$Pr[\mathbf{C}_{2}|\mathbf{C}_{1},do(\mathbf{S}),do(A)]$ over $\mathbf{C}_{2}$
$\displaystyle=\sum_{\mathbf{C}_{1}}Pr[Y^{\prime}|\mathbf{C}_{1},do(A)]Pr[\mathbf{C}_{1}|do(\mathbf{S}),do(A)]=Pr[Y^{\prime}|do(A)]$

This condition shows that $\mathbf{A}\cup\mathbf{C}_{1}\cup\mathbf{C}_{2}$
ensure causal-fairness. ∎

This shows that the features $\mathbf{C}_{1}$ and $\mathbf{C}_{2}$ ensure
causal fairness of the dataset. Using these results, we identify a closed form
expression to identify all variables that ensure causal fairness. Note that
whenever the trained classifier is not bayes optimal, $\mathbf{C}_{1}$ still
ensure causal fairness but the effectiveness of $\mathbf{C}_{2}$ crucially
relies on the optimality of the trained classifier.

###### Theorem 4.3.

Consider a dataset $D$ with admissible variables $\mathbf{A}$, sensitive
$\mathbf{S}$, a set of variables $\mathbf{X}$ with a target $Y$. A variable
$X\in\mathbf{X}$ is safe to be added along with $\mathbf{T}\cup\mathbf{A}$,
where $\mathbf{T}\subseteq\mathbf{C}_{1}\cup\mathbf{C}_{2}\cup\mathbf{A}$
without violating causal fairness iff (i) $(X\perp\mathbf{S}|{A})$ for some
$A\subseteq\mathbf{A}$ or (ii) $(X\perp Y|\mathbf{C}^{\prime},\mathbf{A})$,
where $(\mathbf{C}^{\prime}\perp\mathbf{S}|A)$ or (iii) $X$ is not a
descendant of $\mathbf{S}$ in $G_{\bar{A}}$, where $G_{\bar{\mathbf{A}}}$ is
same as $G$ with incoming edges of $\mathbf{A}$ removed.

###### Proof.

Using Lemma 4.1 and 4.2, we can observe that all the variables
$\mathbf{C}_{1}\cup\mathbf{C}_{2}$ such that
$(\mathbf{C}_{1}\perp\mathbf{S}|{A})$, where $A\subseteq\mathbf{A}$ and
$(\mathbf{C}_{2}\perp Y|\mathbf{C}_{1},\mathbf{A})$ are safe to be added
without worsening the fairness of the dataset. Now consider a variable $X$,
which is not a descendant of $\mathbf{S}$ in $G_{\bar{\mathbf{A}}}$. All paths
from $\mathbf{S}$ to $X$ are blocked when we intervene on $\mathbf{A}$ as all
incoming edges of $\mathbf{A}$ are removed. Therefore it is safe to add $X$
without affecting causal fairness of the dataset.

To show the converse, when $X\not\perp\mathbf{S}|A$, $\forall
A\subseteq\mathbf{A}$ and $X\not\perp Y|C^{\prime},\mathbf{A}$ and $X$ is a
descendant of $\mathbf{S}$ in $G_{\bar{\mathbf{A}}}$, then we show that $X$
can worsen the fairness. We can observe the following properties about $X$:

  * •

$(\mathbf{S}\not\perp{X}|\mathbf{A})$ implies there exists a path from
$\mathbf{S}$ to ${X}$ that is unblocked given $\mathbf{A}$.

  * •

$(X\not\perp{Y}|\mathbf{A},C^{\prime})$ implies that $X$ is predicitve of $Y$
given the features $\mathbf{T}\subseteq\mathbf{C}_{1}\cup\mathbf{C}_{2}$.
Therefore, there will be a direct edge from $X$ to the learned variable
$Y^{\prime}$.

If the paths from $\mathbf{S}$ to $X$ are unblocked in $G_{\bar{\mathbf{A}}}$
then $\mathbf{S}$ to $X$ is unblocked when we intervene on ${\mathbf{A}}$. In
this case, the path from $\mathbf{S}\rightarrow X\rightarrow Y^{\prime}$ is
unblocked and therefore $X$ is a biased variable that violates causal fairness
of the dataset. ∎

SeqSel captures variables that can be identified by performing CI tests.
However, the last condition of Theorem 4.3 requires intervention to identify
other variables. Devising a set of CI tests to identify these variables is an
interesting question for future work.

###### Remark 3.

PC-algorithm (Spirtes et al., 2000), one of the most popular causal discovery
techniques learn the causal graph structure from the data. However, these
techniques are known to work under specific modelling assumptions of the data
and are highly inefficient. The number of CI tests required by such techniques
is generally exponential in the number of input attributes.

Complexity: Algorithm 1 tests conditional independence (CI) of each variable
with $\mathbf{S}$ and $Y$. In the worst case, it requires
$O(2^{|\mathbf{A}|}n)$ CI tests to identify all the variables that do not
worsen the fairness of $D$. In most realistic scenarios, $|\mathbf{A}|$ is a
small constant, yielding overall complexity of $O(n)$, where $n$ is the number
of features. Existing CI testing techniques can generate spurious correlations
between independent variables for large values of $n$. In the next section, we
propose a group testing formulation that reduces this complexity to $O(\log
n)$ tests, thereby improving its accuracy.

###  4.3. Group Testing

Group testing is an old technique that efficiently performs tests on a
logarithmic number of groups of items rather than testing each item
separately. It has not been used in causal inference to identify independent
variables. We use graphoid axioms to show the following two results for any
collection of variables $\mathbf{X}$ and $Z$ justifying the correctness of
group testing in our framework.  Algorithm 2 GrpSel 1:Input: Variables
$\mathbf{A},\mathbf{S},\mathbf{X},Y$
2:$\mathbf{C}_{1}\leftarrow\texttt{first\\_phase}((\mathbf{A},\mathbf{S},\mathbf{X}_{1},Y)$
3:$\mathbf{C}_{2}\leftarrow\texttt{final\\_candidates}((\mathbf{A},\mathbf{S},\mathbf{X}_{1},Y,\mathbf{C}_{1})$
4:return $\mathbf{C}_{1}\cup\mathbf{C}_{2}$

Algorithm 3 first_phase

1:Input: Variables $\mathbf{A},\mathbf{S},\mathbf{X},Y$

2:$\mathbf{C}_{1}\leftarrow\phi$

3:if $\exists A\subseteq\mathbf{A}\text{ such that
}(\mathbf{X}\perp\mathbf{S}|A)$ then

4: $\mathbf{C}_{1}\leftarrow\mathbf{X}$

5:else

6:
$\mathbf{X}_{1},\mathbf{X}_{2}\leftarrow\texttt{random\\_partition}(\mathbf{X})$

7:
$\mathbf{C}_{1}\leftarrow\texttt{first\\_phase}(\mathbf{A},\mathbf{S},\mathbf{X}_{1},Y$)

8:
$\mathbf{C}_{1}\leftarrow\mathbf{C}_{1}\cup\texttt{first\\_phase}(\mathbf{A},\mathbf{S},\mathbf{X}_{2},Y$)

9:return $\mathbf{C}_{1}$

Algorithm 4 final_candidates

1:Input: Variables $\mathbf{A},\mathbf{S},\mathbf{X},Y,\mathbf{C}_{1}$

2:$\mathbf{C}_{2}\leftarrow\phi$

3:if $(\mathbf{X}\perp{Y}|\mathbf{A},\mathbf{C}_{1})$ then

4: $\mathbf{C}_{2}\leftarrow\mathbf{X}$

5:else

6:
$\mathbf{X}_{1},\mathbf{X}_{2}\leftarrow\texttt{random\\_partition}(\mathbf{X})$

7:
$\mathbf{C}_{2}\leftarrow\texttt{final\\_candidates}(\mathbf{A},\mathbf{S},\mathbf{X}_{1},Y,\mathbf{C}_{1}$)

8:
$\mathbf{C}_{2}\leftarrow\mathbf{C}_{2}\cup\texttt{final\\_candidates}(\mathbf{A},\mathbf{S},\mathbf{X}_{2},Y,\mathbf{C}_{2}$)

9:return $\mathbf{C}_{2}$

###### Lemma 4.4.

If $\exists X_{i}\in\mathbf{X}$ such that $X_{1}\not\perp X_{i}|Z$ then
$(X_{1}\not\perp\mathbf{X}\setminus\\{X_{1}\\}|Z)$ for some variables $X_{1}$
and $Z$.

###### Lemma 4.5.

If $(X_{1}\not\perp\mathbf{X}\setminus X_{1}|Z)$ then $\exists
X_{i}\in\mathbf{X}\setminus\\{X_{1}\\}$ such that $(X_{1}\not\perp X_{i}|Z)$
for some $Z$.

These results yield the following two properties that make Algorithm 1 more
efficient.

  * •

If $(X_{1}\not\perp X_{2},X_{3}|Z)$ then $X_{1}\not\perp X_{2}|Z$ or
$X_{1}\not\perp X_{3}|Z$

  * •

If $(X_{1}\perp X_{2},X_{3}|Z)$ then $X_{1}\perp X_{2}|Z$ and $X_{2}\perp
X_{3}|Z$

Algorithm 2 presents an improved version of SeqSel that uses group testing to
remove all the variables that do not satisfy the CI statements shown in
Theorem 4.3. We call this approach GrpSel. GrpSel operates in two phases,
aiming to capture variables $\mathbf{C}_{1}$ and $\mathbf{C}_{2}$,
respectively. The first phase (Algorithm 3) identifies the variables which do
not capture any new information about sensitive variables given
$A\subseteq\mathbf{A}$. It tests the CI between $\mathbf{S}$ and $\mathbf{X}$
given $A\subseteq\mathbf{A}$. If the variables are conditionally independent,
then all the variables $\mathbf{X}$ are identified to maintain causal
fairness. On the other hand, if the variables are conditionally dependent, the
set $\mathbf{X}$ is partitioned into two equal partitions and first_phase
algorithm is called recursively for both the partitions. Algorithm 4, performs
the second phase to identify the variables which are independent of the target
variable $Y$ given $\mathbf{A}$ and $\mathbf{C}_{1}$. This algorithm operates
similarly to first_phase with a different CI test.

Complexity. Algorithm 3 requires a total of $2^{|\mathbf{A}|}k\log n$ tests to
identify all variables $X$ that satisfy $(\mathbf{S}\perp X|{A})$, where $k$
is the number of variables that do not satisfy the condition. The second phase
requires $k^{\prime}\log k$ tests to identify the variables that satisfy CI
with $Y$ where $k^{\prime}$ is the number of variables that do not satisfy the
condition. Therefore, GrpSel has better complexity when the total number of
biased variables $k$ is $o(n/\log n)$.

Figure 2. Classifier fairness and accuracy on MEPS, German, and Compas
datasets.

##  5\. Experiments

In this section, we empirically evaluate our technique along with baselines on
real-world and synthetic datasets. We answer the following research questions.
Q1 Are SeqSel and GrpSel able to ensure causal fairness of the trained
classifier? Q2 How does the quality of classifier trained using different
feature selection algorithms compare in terms of fairness and accuracy? Q3 Is
GrpSel effective in reducing the number of required CI tests?

###  5.1. Setup

Datasets. We consider the following datasets.

  * •

Medical Expenditure  (MEPS) (mep, 2016): predict total number of hospital
visits from patient medical information (Healthcare utilization is sometimes
used as a proxy for allocating home care). We consider two variations denoted
by MEPS(1) and MEPS(2). MEPS(1) considers ‘Arthritis diagnosis’ as admissible
and MEPS(2) considers ‘Arthritis diagnosis’ and ‘Mental health’ as admissible.
Race is considered sensitive. Contains 7915 training and 3100 test records.

  * •

German Credit (ger, 2013) applications. The account status is considered
admissible and person’s age is used as a sensitive attribute. Contains 800
training and 200 test records.

  * •

Compas (Jeff Larson and Angwin., 2016) : predict criminal recidivism from
features such as the severity of the original crime. The number of prior
convictions, age and severity of charge degree are taken as admissible and
race as sensitive. Contains 7200 samples.

  * •

Adult (Asuncion and Newman, 2007) : predict income of individuals. Gender is
considered sensitive and hours per week, occupation, age, education are
considered admissible. Contains $48k$ individuals.

  * •

Synthetic: a synthetically constructed dataset where a feature is constructed
to be highly correlated to a sensitive feature with probability $p$. This
dataset is used for understanding the effect of number of features and the
fraction of noisy features on the complexity of our techniques.

Baselines. We consider the following baselines to identify a subset of
features for the training task.

  1. (1)

A: uses the variables in the admissible set.

  2. (2)

ALL: uses all features present in the dataset.

  3. (3)

Hamlet (Kumar et al., 2016): uses heuristics to identify features which do not
add value to the data set and can be ignored.

  4. (4)

SPred: learn a classifier using an exhaustive set of features to predict the
sensitive attribute. Based on feature importance, we remove the highly
predictive features.

  5. (5)

Capuchin (Salimi et al., 2019): state-of-the-art in-processing technique that
ensures causal fairness by adding or removing tuples.

  6. (6)

Fair-PC: learns the causal graph using PC algorithm (Spirtes et al., 2000) and
uses it to infer features that ensure causal fairness.

Experiment Setup. We evaluate accuracy and fairness of the trained classifier
on the test set. To evaluate fairness, we measure conditional mutual
information (CMI) and absolute odds difference calculated as the difference in
false positive rate and true positive rate between the privileged and
unprivileged groups. We consider the CMI and group fairness metric as a proxy
because zero CMI implies causal fairness which further implies group fairness
and can be easily evaluated from observed data (Salimi et al., 2019). We use
RCIT (Strobl et al., 2019) package in R for CI tests and logistic regression
as the classifier.

Figure 3. (a) Accuracy vs. Abs. odds difference (b) Running time comparison
for varying conditioning set size.

Figure 4. Total number of conditional independence tests vs. $p$, the
percentage of biased variables.

Figure 5. Total number of conditional independence tests vs. $n$ for a fixed
number of biased variables.

###  5.2. Solution Quality

Figure 2 compares the accuracy of the classifier trained with the features
identified by our baselines along with its fairness. ALL learns the most
accurate classifier as compared to all other techniques. However, it achieves
the highest odds difference and hence worst fairness with respect to the
sensitive attribute of the dataset. A maintains high fairness but achieves
quite low accuracy as compared to SeqSel and GrpSel. Hamlet does not identify
features that are highly correlated with sensitive attributes and does not
improve its fairness. SPred identifies a few features that capture sensitive
information but is unable to identify all such features. Hence, it does not
improve the fairness of the classifier as compared to GrpSel. Capuchin and
FairPC are able to improve fairness as compared to ALL but performs worse than
GrpSel and SeqSel. However, accuracy of the learnt classifier is lower for
FairPC than Capuchin, SeqSel, and GrpSel. SeqSel and GrpSel maintain high
fairness with respect to various metrics of fairness without much loss in
accuracy. We calculated feature importance of identified attributes and
identified that a number of attributes identified in the second phase of our
algorithm have non-zero feature importance and contribute towards classifier
prediction.

For MEPS and German datasets, GrpSel and SeqSel are able to identify features
that mitigate the bias and do not lose much in classifier accuracy. However,
all other techniques have higher bias against the protected attribute on
Compas. In this case, we observe that the admissible feature is correlated to
the sensitive attribute, affecting the fairness of the trained classifier. We
empirically swept the p-value threshold from 0.01 to 0.05, and results are
stable and do not impact its performance. As an example, the accuracy of the
trained classifier was 0.83-0.84 on MEPS and within 0.73-0.76 on German on
varying the thresholds. We observed similar behavior on changing the
classifier from logistic regression to random forest.

Table 2 compares the conditional mutual information between the learnt
variable $Y^{\prime}$ (according to GrpSel) and target $Y$ with $\mathbf{S}$
given $\mathbf{A}$.333Some mutual information values were slightly negative
and were truncated to $0$ as suggested by Mukherjee et al. (2019). Across all
datasets, $Y^{\prime}$ is independent of $\mathbf{S}$ even though the original
target variable $Y$ was unfair. This experiment validates the efficacy of our
techniques to identify features that ensure fairness and get rid of the biased
features.

| CMI |  |  | Number of tests
---|---|---|---|---
Dataset |  CMI$(\mathbf{S},Y^{\prime}|\mathbf{A})$ |  CMI$(\mathbf{S},Y|\mathbf{A})$ |  |  | SeqSel | GrpSel
MEPS(1) | 0.0 | 0.015 |  | MEPS(1) | 343 | 247
MEPS(2) | 0.0 | 0.014 |  | MEPS(2) | 420 | 390
German | 0.002 | 0.018 |  | German | 525 | 81
Compas | 0.0 | 0.01 |  | Compas | 257 | 83
Adult | 0.01 | 0.03 |  | Adult | 125 | 23
Table 2. Conditional Mutual Information (Mukherjee et al., 2019) and number of
CI tests required for each dataset

Model Selection. We tested these pipelines by training other ML algorithms
like random forest and Adaboost classifier. Across all datasets, we observe
that SeqSel and GrpSel maintain fairness of the trained classifier while
maintaining high accuracy.

###  5.3. Synthetic Data

In this experiment, we tested the causal fairness metric by simulating
interventions presented in Definition 3.1 and compared with ground truth. We
evaluate GrpSel and SeqSel on multiple synthetic datasets generated using
causal graphs of varied sizes (1000, 3000 and 5000). Across all datasets, we
observed that SeqSel and GrpSel identified majority of the variables that
ensure causal fairness. However, other baselines were not able to identify all
the biased features, thereby leading to biased datasets.

Complexity. The total number of CI tests required by SeqSel and GrpSel are
shown in Table 2. GrpSel requires fewer tests than SeqSel across all datasets.
Since all these datasets contain fewer than 1000 features, the improvement is
not very significant. To understand the difference in complexity of the two
techniques, we perform an extensive simulation study by varying the total
number of features and the fraction of biased variables.

Figure 5 compares the total number of CI tests required to identify variables
that ensure causal fairness. With the increase in total number of features
($n$), the number of tests required by SeqSel grows linearly. However, the
growth of GrpSel is sub-linear and requires fewer tests than SeqSel for larger
$n$. This result is coherent with our theoretical analysis of $O(n)$ tests for
SeqSel and $O(k\log n)$ for GrpSel, where $k$ is the number of biased
variables and $n$ is the total number of features in the dataset.

Effect of $p$. Figure 5 compares GrpSel and SeqSel as a function of the total
fraction of biased variables in the dataset. SeqSel’s complexity is driven by
the total number of features irrespective of the number of biased features.
However, the tests required by GrpSel are dependent linearly on $p$. This
experiment confirms the benefit of using group testing when the total number
of biased variables are fewer than ${(\log n)}/{n}$.

Advantages of Group-testing We now evaluate the benefits of using group-
testing based technique for feature selection. We generated a synthetic
dataset containing $1000$ records and increased the number of features
(denoted by $t$) from $100$ to $1000$ in increments of $100$. We tested the
correctness of GrpSel’s output with the ground-truth calculated from the
causal graph. We observed that around $5$ attributes that are independent of
$S$ are dropped by SeqSel when $t=500$. The spuriousness increases to $\approx
47$ features when $t=1000$. On the other hand, GrpSel did not return any
spurious correlation for $t\leq 900$ features and returned less than $5$
spurious features when $t=1000$. This experiment demonstrates that group-
testing can reduce the chances of getting a spurious output.

###  5.4. Robustness

In this experiment, we changed the test data by modifying the effect of
sensitive attribute on the target variable through specific attributes (by
changing edge weights of the causal graph). This data distribution shift did
not affect the performance of GrpSel or SeqSel and both techniques achieved
$0$ absolute odds difference. In contrast, prior pre-processing techniques led
to an increase in absolute odds difference of upto $15\%$. The evaluation
demonstrated the weakness of pre-processing techniques to generalize to
settings beyond the data distribution of the repaired training dataset. Prior
work has referred to it as over-fitting with respect to fairness (Diaz et al.,
2021).

Running time.  Figure 3(b) compares the running time of CI test run using RCIT
package for varying size of the conditioning set. This experiment shows that
the running time increases linearly with increasing set size but the gradient
is very slow. For example, the running time for the adult dataset increases
from $8$ sec to less than $10$ sec when the conditioning set size increases
from $1$ to $256$. Therefore, performing a CI test with groups of features is
effective.

Among all techniques, we observe that GrpSel and SeqSel execute within 10
minutes for all real-world datasets, and it takes around 1 minute to train a
classifier. Therefore, our techniques learns a fair classifier in less than 11
minutes across all datasets.

##  6\. Related Work

To the best of our knowledge, there is very little related work on
discrimination-aware or fair feature selection. One of the recent papers on
feature construction and exploration (Diaz et al., 2021) has studied the
problem of constructing new features that can help improve prediction without
affecting fairness. Grgić-Hlača et al. (2018) use human moral judgements of
different properties of features (volitionality, reliability, privacy, and
relevance) as the starting point for feature selection. Although they cite
causal fairness definitions as the basis for feature relevance, they do not
use the data to quantify this relevance. Salimi et al. (2019) consider causal
fairness to change the input data distribution as opposed to identification of
a small set of features that ensure causal fairness. Dutta et al. (2020) start
with the causal fairness perspective as well and also use tools from
information theory, but use partial information decomposition to partition the
information contained in the features into exempt and non-exempt portions; the
goal is not feature subset selection, but gaining insight into different types
of discrimination. Nabi and Shpitser (2018) considered causal pathways to
identify discrimination and then train a fair classifier assuming full
knowledge of the underlying causal graph. Zhang et al. (2016b) consider causal
definitions of fairness and devise algorithms that repair the dataset to
ensure fairness. Noriega Campero et al. (2019) and its followup (Bakker et
al., 2019) examine an active feature acquisition paradigm from the perspective
of fairness but do not study the causal notion of fairness.

##  7\. Conclusion

In this paper, we have tackled the problem of data integration — joining
additional features to an initially given dataset — while not introducing
additional unwanted bias against protected groups. We have utilized the
formalism of causal fairness and do-calculus to develop an algorithm for
adding variables that is theoretically-guaranteed not to make fairness worse.
We have enhanced this algorithm using group testing to make it more efficient
(the first use of group testing in such a setting) and shown its efficacy on
several datasets. The extension of our techniques for active learning or
online setting are interesting questions for future work.

## References

  * (1)
  * ger (2013) 2013\.  Uci machine learning repository.  _https://archive.ics.uci.edu/ml/datasets/Statlog+%28German+Credit+Data%29_ (2013).
  * mep (2016) 2016\.  Medical Expenditure Panel Survey.  _https://meps.ahrq.gov/mepsweb/_ (2016).
  * Asuncion and Newman (2007) Arthur Asuncion and David Newman. 2007.  UCI machine learning repository.
  * Bakker et al. (2019) Michiel Bakker, Alejandro Noriega Campero, Duy Patrick Tu, Prasanna Sattigeri, Kush R. Varshney, and Alex Pentland. 2019.  On Fairness in Budget-Constrained Decision Making. In _KDD Workshop on Explainable Artificial Intelligence_.
  * Barocas et al. (2020) Solon Barocas, Moritz Hardt, and Arvind Narayanan. 2020\.  _Fairness and Machine Learning: Limitations and Opportunities_.  https://fairmlbook.org.
  * Calders and Verwer (2010) Toon Calders and Sicco Verwer. 2010.  Three naive bayes approaches for discrimination-free classification.  _Data mining and knowledge discovery_ 21, 2 (2010), 277–292.
  * Calmon et al. (2017) Flavio P Calmon, Dennis Wei, Bhanukiran Vinzamuri, Karthikeyan Natesan Ramamurthy, and Kush R Varshney. 2017.  Optimized pre-processing for discrimination prevention. In _Proceedings of the 31st International Conference on Neural Information Processing Systems_. 3995–4004.
  * Celis et al. (2019) L Elisa Celis, Lingxiao Huang, Vijay Keswani, and Nisheeth K Vishnoi. 2019.  Classification with fairness constraints: A meta-algorithm with provable guarantees. In _Proceedings of the conference on fairness, accountability, and transparency_. 319–328.
  * Chiappa (2019) Silvia Chiappa. 2019\.  Path-specific counterfactual fairness. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 33. 7801–7808.
  * Chiappa and Isaac (2018) Silvia Chiappa and William S Isaac. 2018.  A causal Bayesian networks viewpoint on fairness. In _IFIP International Summer School on Privacy and Identity Management_. Springer, 3–20.
  * d’Alessandro et al. (2017) Brian d’Alessandro, Cathy O’Neil, and Tom LaGatta. 2017\.  Conscientious Classification: A Data Scientist’s Guide to Discrimination-Aware Classification.  _Big Data_ 5, 2 (June 2017), 120–134.
  * Diaz et al. (2021) Ricardo Salazar Diaz, Felix Neutatz, and Ziawasch Abedjan. 2021\.  Automated Feature Engineering for Algorithmic Fairness.  _PVLDB_ (2021).
  * Dutta et al. (2020) Sanghamitra Dutta, Praveen Venkatesh, Piotr Mardziel, Anupam Datta, and Pulkit Grover. 2020.  An Information-Theoretic Quantification of Discrimination with Exempt Features. In _Proceedings of the AAAI Conference on Artificial Intelligence_.
  * Feldman et al. (2015) Michael Feldman, Sorelle A Friedler, John Moeller, Carlos Scheidegger, and Suresh Venkatasubramanian. 2015\.  Certifying and removing disparate impact. In _proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining_. 259–268.
  * Galhotra et al. (2019) Sainyam Galhotra, Udayan Khurana, Oktie Hassanzadeh, Kavitha Srinivas, Horst Samulowitz, and Miao Qi. 2019.  Automated Feature Enhancement for Predictive Modeling using External Knowledge.  _ICDM_ (2019).
  * Galhotra et al. ([n.d.]) Sainyam Galhotra, Karthikeyan Shanmugam, Prasanna Sattigeri, and Kush R. Varshney. [n.d.].  Causal Feature Selection for Algorithmic Fairness, arXiv https://arxiv.org/abs/2006.06053.
  * Galhotra et al. (2021) Sainyam Galhotra, Karthikeyan Shanmugam, Prasanna Sattigeri, and Kush R Varshney. 2021\.  Interventional Fairness with Indirect Knowledge of Unobserved Protected Attributes.  _Entropy_ 23, 12 (2021), 1571.
  * Grgić-Hlača et al. (2018) Nina Grgić-Hlača, Muhammad Bilal Zafar, Krishna P. Gummadi, and Adrian Weller. 2018.  Beyond Distributive Fairness in Algorithmic Decision Making: Feature Selection for Procedurally Fair Learning. In _Proceedings of the AAAI Conference on Artificial Intelligence_. 51–60.
  * Hall (1999) Mark Andrew Hall. 1999\.  Correlation-based feature selection for machine learning.  (1999).
  * Hardt et al. (2016) Moritz Hardt, Eric Price, and Nati Srebro. 2016.  Equality of opportunity in supervised learning.  _Advances in neural information processing systems_ 29 (2016), 3315–3323.
  * Holstein et al. (2019) Kenneth Holstein, Jennifer Wortman Vaughan, Hal Daumé, III, Miroslav Dudík, and Hanna Wallach. 2019.  Improving Fairness in Machine Learning Systems: What Do Industry Practitioners Need?. In _Proceedings of the CHI Conference on Human Factors in Computing Systems_. 600.
  * Huang and Valtorta (2012) Yimin Huang and Marco Valtorta. 2012.  Pearl’s calculus of intervention is complete.  _arXiv preprint arXiv:1206.6831_ (2012).
  * Ingold and Soper (2016) David Ingold and Spencer Soper. 2016.  Amazon doesn’t consider the race of its customers. should it?  _Bloomberg_ (2016).
  * Jeff Larson and Angwin. (2016) Lauren Kirchner Jeff Larson, Surya Mattu and Julia Angwin. 2016.  How we analyzed the compas recidivism algorithm.  _ProPublica_ (2016).
  * Jiang et al. (2019) Ray Jiang, Aldo Pacchiano, Tom Stepleton, Heinrich Jiang, and Silvia Chiappa. 2019\.  Wasserstein fair classification.  _arXiv preprint arXiv:1907.12059_ (2019).
  * Jo and Gebru (2020) Eun Seo Jo and Timnit Gebru. 2020.  Lessons from Archives: Strategies for Collecting Sociocultural Data in Machine Learning. In _Proceedings of the ACM Conference on Fairness, Accountability, and Transparency_.
  * Kamiran and Calders (2012) Faisal Kamiran and Toon Calders. 2012.  Data preprocessing techniques for classification without discrimination.  _Knowledge and Information Systems_ 33, 1 (2012), 1–33.
  * Kamishima et al. (2012) Toshihiro Kamishima, Shotaro Akaho, Hideki Asoh, and Jun Sakuma. 2012.  Fairness-aware classifier with prejudice remover regularizer. In _Joint European Conference on Machine Learning and Knowledge Discovery in Databases_. Springer, 35–50.
  * Khademi and Honavar (2019) Aria Khademi and Vasant Honavar. 2019.  Algorithmic Bias in Recidivism Prediction: A Causal Perspective.  _arXiv_.  arXiv:1911.10640
  * Khademi et al. (2019) Aria Khademi, Sanghack Lee, David Foley, and Vasant Honavar. 2019\.  Fairness in algorithmic decision making: An excursion through the lens of causality. In _The World Wide Web Conference_. 2907–2914.
  * Khurana et al. (2016) Udayan Khurana, Deepak Turaga, Horst Samulowitz, and Srinivasan Parthasrathy. 2016.  Cognito: Automated feature engineering for supervised learning. In _2016 IEEE 16th International Conference on Data Mining Workshops (ICDMW)_. IEEE, 1304–1307.
  * Kilbertus et al. (2017) Niki Kilbertus, Mateo Rojas Carulla, Giambattista Parascandolo, Moritz Hardt, Dominik Janzing, and Bernhard Schölkopf. 2017.  Avoiding Discrimination through Causal Reasoning. In _Advances in Neural Information Processing Systems_. 656–666.
  * Konda et al. (2013) Pradap Konda, Arun Kumar, Christopher Ré, and Vaishnavi Sashikanth. 2013.  Feature selection in enterprise analytics: a demonstration using an R-based data analytics system.  _PVLDB_ 6, 12 (2013), 1306–1309.
  * Kumar et al. (2016) Arun Kumar, Jeffrey Naughton, Jignesh M Patel, and Xiaojin Zhu. 2016.  To join or not to join? thinking twice about joins before feature selection. In _Proceedings of the 2016 International Conference on Management of Data_. 19–34.
  * Kusner et al. (2017) Matt Kusner, Joshua Loftus, Chris Russell, and Ricardo Silva. 2017.  Counterfactual Fairness. In _Advances in Neural Information Processing Systems_. 4066–4076.
  * Lauritzen and Sadeghi (2018) Steffen Lauritzen and Kayvan Sadeghi. 2018.  Unifying Markov properties for graphical models.  _The Annals of Statistics_ 46, 5 (2018), 2251–2278.
  * Loftus et al. (2018) Joshua R Loftus, Chris Russell, Matt J Kusner, and Ricardo Silva. 2018.  Causal reasoning for algorithmic fairness.  _arXiv preprint arXiv:1805.05859_ (2018).
  * Miller (2018) Renée J Miller. 2018\.  Open data integration.  _PVLDB_ 11, 12 (2018), 2130–2139.
  * Mukherjee et al. (2019) Sudipto Mukherjee, Himanshu Asnani, and Sreeram Kannan. 2019\.  Ccmi: Classifier based conditional mutual information estimation.  _arXiv preprint arXiv:1906.01824_ (2019).
  * Nabi and Shpitser (2018) Razieh Nabi and Ilya Shpitser. 2018.  Fair inference on outcomes. In _Thirty-Second AAAI Conference on Artificial Intelligence_.
  * Noriega Campero et al. (2019) Alejandro Noriega Campero, Michiel Bakker, Bernardo Garcia Bulle, and Alex Pentland. 2019.  Active Fairness in Algorithmic Decision Making. In _Proceedings of AAAI / ACM Conference on Artificial Intelligence, Ethics, and Society_. 77––83.
  * Pearl (2009) Judea Pearl. 2009\.  _Causality_.  Cambridge university press.
  * Peters et al. (2017) Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. 2017\.  _Elements of causal inference: foundations and learning algorithms_.  The MIT Press.
  * Russell et al. (2017) Chris Russell, Matt J Kusner, Joshua Loftus, and Ricardo Silva. 2017.  When worlds collide: integrating different counterfactual assumptions in fairness. In _Advances in Neural Information Processing Systems_. 6414–6423.
  * Sadeghi (2017) Kayvan Sadeghi. 2017\.  Faithfulness of probability distributions and graphs.  _Journal of Machine Learning Research_ 18, 148 (2017), 1–29.
  * Salimi et al. (2019) Babak Salimi, Luke Rodriguez, Bill Howe, and Dan Suciu. 2019\.  Interventional fairness: Causal database repair for algorithmic fairness. In _Proceedings of the 2019 International Conference on Management of Data_. 793–810.
  * Schelter et al. (2019) Sebastian Schelter, Yuxuan He, Jatin Khilnani, and Julia Stoyanovich. 2019.  FairPrep: Promoting Data to a First-Class Citizen in Studies on Fairness-Enhancing Interventions.  arXiv:1911.12587.
  * Singh et al. (2019) Harvineet Singh, Rina Singh, Vishwali Mhasawade, and Rumi Chunara. 2019.  Fair predictors under distribution shift.  _arXiv preprint arXiv:1911.00677_ (2019).
  * Spirtes et al. (2000) Peter Spirtes, Clark N Glymour, Richard Scheines, and David Heckerman. 2000.  _Causation, prediction, and search_.  MIT press.
  * Strobl et al. (2019) Eric V Strobl, Kun Zhang, and Shyam Visweswaran. 2019.  Approximate kernel-based conditional independence tests for fast non-parametric causal discovery.  _Journal of Causal Inference_ 7, 1 (2019).
  * Xu et al. (2019) Depeng Xu, Yongkai Wu, Shuhan Yuan, Lu Zhang, and Xintao Wu. 2019.  Achieving causal fairness through generative adversarial networks.  _IJCAI_.
  * Zafar et al. (2017) Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rogriguez, and Krishna P Gummadi. 2017.  Fairness constraints: Mechanisms for fair classification. In _Artificial Intelligence and Statistics_. PMLR, 962–970.
  * Zhang et al. (2016a) Ce Zhang, Arun Kumar, and Christopher Ré. 2016a.  Materialization optimizations for feature selection workloads.  _ACM Transactions on Database Systems (TODS)_ 41, 1 (2016), 2\.
  * Zhang and Bareinboim (2018a) Junzhe Zhang and Elias Bareinboim. 2018a.  Equality of Opportunity in Classification: A Causal Approach. In _Advances in Neural Information Processing Systems_. 3671–3681.
  * Zhang and Bareinboim (2018b) Junzhe Zhang and Elias Bareinboim. 2018b.  Fairness in Decision-Making — The Causal Explanation Formula. In _Proceedings of the AAAI Conference on Artificial Intelligence_. 2037–2045.
  * Zhang et al. (2016b) Lu Zhang, Yongkai Wu, and Xintao Wu. 2016b.  A causal framework for discovering and removing direct and indirect discrimination.  _arXiv preprint arXiv:1611.07509_ (2016).

##  8\.  Proofs

First, we show the following property of do-calculus.

###### Lemma 8.1.

Given a disjoint collection of variables $X$, $Y$ and $Z$ in a causal graph
$G$, such that $(X\perp Y|Z^{\prime})$, where $Z^{\prime}\subseteq Z$, then
$Pr[X|do(Y),do(Z)]=Pr[X|do(Z)]$

###### Proof.

Using the third rule of do-calculus (Equation 10, (Huang and Valtorta, 2012)),
$Pr[X|do(Y),do(Z)]=Pr[X|do(Z)]$ when $X$ is independent of $Y$ given $Z$ in
the graph where incoming edges of $Z$ have been removed. Since, $X\perp
Y|Z^{\prime}$ in $G$ where $Z^{\prime}\subseteq Z$, removing additional
incoming edges will ensure that none of the variables in $Z$ are a collider
and conditioning on $Z\setminus Z^{\prime}$ additionally will still maintain
conditional independence. ∎

###### Lemma 8.2.

Given a dataset $D$ comprising of variables
$\mathcal{A}\cup\mathcal{S}\cup\mathcal{X}$, target variable $Y$ and let
$Y^{\prime}$ be the variable learnt using the feature subset
$\mathcal{T}\cup\mathcal{A}$, then
$Pr(Y^{\prime}|do(\mathcal{A}),do(\mathcal{S}),\mathcal{T})=Pr(Y^{\prime}|do(\mathcal{A}),\mathcal{T})$,
where $T\subseteq\mathcal{X}$

###### Proof.

Based on the assumption about the construction of $Y^{\prime}$ (Assumption 2),
the variable $Y^{\prime}$ is only dependent on the variables in
$\mathcal{A}\cup\mathcal{T}$ in all environments. Given
$\mathcal{A}\cup\mathcal{T}$, the variable $Y^{\prime}$ is independent of
$\mathcal{S}$. The same condition holds even when incoming edges of
$\mathcal{A}$ are removed. Also, $\mathcal{S}$ nodes do not have any incoming
edges. Therefore, on applying the third rule of do-calculus, since
$Y^{\prime}$ is independent of $\mathcal{S}$ in the modified graph where
incoming edges of $\mathcal{A}$ and $\mathcal{S}$ nodes that are ancestors of
$\mathcal{T}$ are removed. Therefore,
$Pr(Y^{\prime}|do(\mathcal{A}),do(\mathcal{S}),\mathcal{T})=Pr(Y^{\prime}|do(\mathcal{A}),\mathcal{T})$
∎

###  8.1. Proof of Lemma $7$

We denote conditional mutual information between two variables $X$ and $Y$
given $Z$ as $I(X,Y|Z)$.

###### Proof.

Using chain rule,
$I(X_{1},\mathcal{X}|Z)=I(X_{1},X_{i}|Z)+I(X_{1},Z|X_{i})\geq
I(X_{1},X_{i}|Z)>0$ ∎

###  8.2. Proof of Lemma $8$

###### Proof.

$X_{1}\not\perp\mathcal{X}\setminus X_{1}|Z$ means that path from $X_{1}$ to
$\mathcal{X}$ is not blocked. Using assumption 1, that the path to atleast one
of $X_{i}\in\mathcal{X}\setminus X_{1}$ is not blocked. Hence, $\exists i$
such that $X_{1}\not\perp X_{i}|Z$. ∎

Figure 6. Example graph where $X_{2}$ is not identified as causally fair by
GrpSel. We omit other nodes for the sake of clarity.

###  8.3. Dataset description

  * •

Medical Expenditure (MEPS)444https://meps.ahrq.gov/mepsweb/: This dataset
comprises of health assessment features (both physical and mental) along with
demographic features. The dataset is used to predict the number of hospital
visits.

  * •

German
Credit555https://archive.ics.uci.edu/ml/datasets/statlog+(german+credit+data)
dataset from UCI repository contains attributes of various applicants and the
goal is to classify them based on credit risk.

  * •

Compas666https://github.com/propublica/compas-analysis was a risk assessment
tool used by courts to determine if a defendant should be released or
retained. This dataset contains features like age, race, prior conviction,
etc.

In addition to the default set of features, we use techniques from (Khurana et
al., 2016) to generate new features, constructed by composition of already
present features.

Setup. We considered the default threshold of p-value to be 0.01 and default
settings of sklearn’s logistic regression classifier. GrpSel and SeqSel were
implemented in R and the classifier training and testing in Python. The code
was run on a laptop with 16GB RAM running MAC OS.

##  9\. Additional Experiments

Our experiments on real-world datasets that compare group fairness metric
(absolute odds difference) and conditional mutual information (CMI) correspond
two ends of the spectrum. Since causal fairness implies group fairness, Figure
2 provides some evidence that our algorithms can potentially ensure fairness.
On the other hand, since GrpSel has low CMI with the target variable given
$\mathcal{A}$ (Table 2), the CMI of $\mathcal{S}$ and $Y^{\prime}$ will be low
even after intervening on $\mathcal{A}$. This experiment guarantees the
effectiveness of our techniques to ensure causal fairness.

To further analyze the ability of our algorithms to ensure causal fairness, we
evaluate GrpSel and SeqSel on multiple synthetic datasets generated using
causal graphs of varied sizes (1000, 3000 and 5000) along with the examples
shown in Figure 1 a-c.

In this experiment, we validated the effectiveness of SeqSel and GrpSel to
identify the variables that ensure causal fairness. Across all datasets, we
observed that SeqSel and GrpSel identified all the variables that ensure
causal fairness. One of the variables in 1000 node dataset was not detected by
our algorithm. We show a small subgraph of this dataset in Figure 6. In this
dataset, variable $X_{2}$ is not identified by GrpSel and SeqSel because
$X_{2}\not\perp S_{1}$ and $X_{2}\not\perp S_{1}|A_{1}$. This is an example
scenario where interventional data is required to identify such variables.

We ran an additional experiment to test the robustness of our techniques with
respect to distribution shift. In this experiment, we varied the effect of
sensitive attribute on the target variable through specific attributes. This
shift in data distribution did not affect the performance of GrpSel or SeqSel
but pre-processing techniques like reweighting777https://aif360.mybluemix.net/
fail to ensure fairnss under the modified distribution.

###  9.1. d-separation

Two nodes X and Y are d-separated if every path between them (should any
exist) is blocked. If even one path between X and Y is unblocked, X and Y are
d-connected. More formally,

###### Definition 9.1 (d-separation).

A path $p$ is blocked by a set of nodes $Z$ if and only if

  1. (1)

p contains a chain of nodes $A\rightarrow B\rightarrow C$ or a fork
$A\leftarrow B\rightarrow C$ such that the middle node B is in Z (i.e., B is
conditioned on), or

  2. (2)

p contains a collider $A\rightarrow B\leftarrow C$ such that the collision
node B is not in Z, and no descendant of B is in Z.

If Z blocks every path between two nodes X and Y, then X and Y are
d-separated, conditional on Z, and thus are independent conditional on Z.