Counterfactual Fairness with Partially Known Causal Graph
Authors: Aoqi Zuo
Susan Wei
Tongliang Liu
Bo Han
Kun Zhang
Mingming Gong
Venue: NeurIPS 2022 Accept (2022)
Keywords: causal inference
machine learning
fairness

Abstract: Fair machine learning aims to avoid treating individuals or sub-populations unfavourably based on \textit{sensitive attributes}, such as gender and race. Those methods in fair machine learning that are built on causal inference ascertain discrimination and bias through causal effects. Though causality-based fair learning is attracting increasing attention, current methods assume the true causal graph is fully known. This paper proposes a general method to achieve the notion of counterfactual fairness when the true causal graph is unknown. To select features that lead to counterfactual fairness, we derive the conditions and algorithms to identify ancestral relations between variables on a \textit{Partially Directed Acyclic Graph (PDAG)}, specifically, a class of causal DAGs that can be learned from observational data combined with domain knowledge. Interestingly, we find that counterfactual fairness can be achieved as if the true causal graph were fully known, when specific background knowledge is provided: the sensitive attributes do not have ancestors in the causal graph. Results on both simulated and real-world datasets demonstrate the effectiveness of our method.

Counterfactual Fairness with Partially Known Causal Graph
Aoqi Zuo The University of Melbourne azuo@student. unimelb. edu. au
Susan Wei The University of Melbourne susan. wei wei@unimelb edu. au
Tongliang Liu The University of Sydney tongliang. liu@sydney. edu. au
Bo Han
Hong Kong Baptist University bhanml @comp. hkbu. edu. hk
Kun Zhang
Mingming Gong'
Carnegie Mellon University & MBZUAI kunz @cmu. edu
The University of Melbourne mingming gongdunimelb edu. au
Abstract
Fair machine learning aims to avoid treating individuals or sub-populations un- favourably based sensitive altributes, such gender and race. Those methods in fair machine learning that are built on causal inference ascertain discrimination and bias through causal effects. Though causality- based fair learning attracting increasing attention, current methods assume the true causal graph is fully known. This paper proposes a general method to achieve the notion of counterfactual fairness when the true causal graph is unknown. To select features that lead to counterfactual fairness, we derive the conditions and algorithms to identify ances- tral relations between variables on Partially Directed Acyelic Graph (PDAG), specifically, a class causal DAGs that can learned from observational data combined with domain knowledge. Interestingly, ness can achieved as the true causal graph were fully known, when specific background knowledge is provided: the sensitive attributes do not have ancestors in the causal graph. Results on both simulated and real-world datasets demonstrate the effectiveness of our method.
find that counterfactual fair-
Introduction
With the widespread application of machine learning in various fields (e.g., hiring decisions recidivism predictions [Т and finance 226 (55)), the ethical and social impact of machine learning is receiving increasing attention. In particular, machine learning algorithms are sensitive to the bias in training data, which may render their decisions discriminatory against individual sub-population group with respect to sensitive attributes, e.g., gender and race. For example, bias against African- Americans was found with COMPAS, decision support tool used by U.S. courts to assess the likelihood of defendant becoming recidivist [12].
23
To achieve fair machine learning, large body of methods have been proposed to mitigate bias according to different fairness measures. These methods can be roughly categorized into two groups. The first group focuses devising statistical fairness notions, which typically indicate the statistical
CCorreponnding author
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

discrepancy between individuals or cub--opulattins e.g., statistical parity [14 equalized odds [22]] and predictive parity g Built on the causal inference framework H40 the second group treats the
presence of causal effect of the sensitive attribute on the decision as discrimination 19 25 27
29
699
Among the causal fairness works, counterfactual fairness 29 which considers the causal effect of sensitive attributes on the individual level, has received much attention. Given the true causal graph, Kusner et al. [29] provide the conditions and algorithms for achieving counterfactual fairness in the constructed predictive model. Wu al. 600] and Chiappa [ extend counterfactual fairness by considering path path-specific effects. When the counterfactual effect is unidentifiable, counterfactual faimess can be approximately achieved by lower and upper bounds of counterfactual effects [59].
Existing counterfactual fairness methods assume the availability of a causal directed acyclic graph (DAG) 39 which encodes causal relationships between variables. However, in many real-world scenarios, the causal DAG is often unknown due to insufficient understanding of the system under investigation. An obvious path forward is to infer the causal DAG from observational data using
causal discovery methods 6 9
2d
43 EM 51H53 666) Unfortunately, without strong assumptions
on the data generating process, such as linearity [ and additive noise 24] 4E one cannot uniquely
recover the underlying true causal graph from observational data alone. In the general case, causal discovery methods could output a Markov equivalence class of DAGs that encode the same set of conditional independencies from data, which can be represented by completely partially directed acyelic graph (CPDAG) 541 With additional background knowledge, we can discern more causal directions, which can be represented by maximally partially directed acyelic graph (MPDAG) [4 but we still cannot obtain unique causal DAG.
Following this augment, we have a natural question to answer: can we learn counterfactual fairness with a partially known causal graph represented by MPDAG? I In a causal DAG, if a variable $ has a causal path to another variable T, then S is an ancestor of T and is a descendant of S. Counterfactual fairness deems the prediction to be counterfactually fair if it is function of the non-descendants of sensitive attributes 29]. which are straightforward to identify in DAGs. However, in an MPDAG, with respect to variable S, a variable T' can be either
a definite descendant of S if T is a descendant of S in every equivalent DAG, a definite non-descendant of if T is a non-descendant of S in every equivalent DAG, a possible descendant of S if T is neither a definite descendant nor a definite non-descendant S.
To achieve counterfactual fairness MPDAGs, we need to select the definite non-descendants and some possible descendants of the sensitive attributes that could be non-descendants in the true DAG to make prediction. This comes to the core challenge: the identifiability of the ancestral relation between two distinct variables in an MPDAG. We refer the interested readers to summary of existing identifiability results in Appendix G
In this paper, we assume no selection bias and presence of confounders because the causal discovery algorithms themselves will not work well in such challenging scenarios. Under this assumption, which can also be found in the most related work [4] 55 68) but removing the assumption on a fully directed causal DAG, we make the following main contributions towards achieving counterfactual fairness on MPDAGs:
We provide a sufficient and necessary graphical criterion (Theorem 4.5 to check whether a variable is a definite descendant of another variable on an MPDAG;
Based on the proposed criterion, we give an efficient algorithm (Algorithm 2 to identify
ancestral relations between any two variables on an MPDAG;
We propose the first approach for achieving counterfactual faimess on partially known causal graphs, specifically MPDAGs;
We find that on an MPDAG, counterfactual fairness can be achieved as if the true causal graph is fully known with the assumption that the sensitive attributes can not have ancestors in the causal graph.
*CPDAG is special case of MPDAG without background knowledge, deal with MPDAG generally.

---

2
Background
In this section, we first review the structural causal model, causal graph and counterfactual inference. Then introduce counterfactual fairness criterion and its intuitive implications.
2.1 Structural causal model, causal graph, and counterfactual inference
Structural causal model (SCM) 40 is framework to model causal relations between variables. It is defined by a triple (U, V. F). where V are observable endogenous variables and are unobserved exogenous variables that cannot be caused by any variable in V. F is set of functions fi,..., fa. one for each V2 E V expressing how V, is dependant on its direct causes: V; f((pos U2), where pa, is the observed direct causes of V, and U, is the set of unobserved direct causes of V,. The exogenous U,S are required to be jointly independent. The set of equations induces a causal graph over the variables, usually in the form of directed acyclic graph (DAG), where the directed causes of V; represents its parent set in the causal graph.
Based SCM, one can perform counterfactual inference to answer the problems in the counterfactual world. For example, consider in a fairness context, A, Y and X' represent the sensitive attributes, outcome of interest, and other observable attributes, respectively. For individual U with A = a, = y and = x, a common counterfactual query is: "For this individual u, what would the value of have been had A taken value a't. The solution, denoted as Y
(u) can be obtained by three steps in the deterministic case: Abduction, Action and Prediction 40 Chapter 7.1]. In probabilistic counterfactual inference, the procedure can be modified to estimate the posterior of u and the distribution of (u).
DAGs, PDAGs and CPDAGs. In a directed acyclic graph (DAG), all edges are directed and there is no directed cycle in the graph; when some edges are undirected, we say it is partially directed graph (PDAG), A DAG encodes a set of conditional independence relations based on the notion d-seperation 3 Multiple DAGS are Markov equivalent if they encode the same set of conditional independence relations. A Markov equivalence class of DAG D can be uniquely represented by completed partially directed acyelic graph (CPDAG) g", denoted by [g*].
MPDAGs. The CPDAGs with background knowledge constraint known as maximally oriented [4 which can be obtained by applying Meek's rules RI, R2, R3 and R4 in 12 can be used to construct the MPDAG G from the CPDAG g" and backgroud knowledge B, where the background knowledge B is assumed to be the direct causal information in the form X - Y. meaning that X is a direct cause of Y. The subset of Markov equivalent DAGs consistent with the background knowledge B can be uniquely represented by MPDAG G, denoted by [9]. Both a DAG and a CPDAG can be regarded as special cases of an MPDAG when the background knowledge is completely known and not known, respectively.
PDAGs (MPDAGs)
34
The Algorithm
2.2 Counterfactual fairness
Counterfactual faimess 29 is fairness criterion based SCM 40 Let A, Y and X' represent the sensitive attributes, outcome of interest and other observable attributes, respectively and the prediction of Y is denoted by Y. For an individual with X' = x and A = a, we say the prediction Ý is counterfactually fair if it would have been the same had A been a in the counterfactual world as in the real world that A is a.
Definition 2.1 (Counterfactual fairness). 2
Definition 5) We say the prediction Y is counterfactu-
ally fair if under any context X and A =
P( y| A= a) PU) = y| xx, A=
P
for all y and any value a' attainable by A.
The definition of counterfactual fairness immediately suggests the following approach in Lemma 2.2 to design counterfactually fair model.
Lemma 2.2. 29 Lemma 1] Let be the causal graph of the given model (U,VFF) F). Then y will be counterfactually fair if it is a function of the non-descendants of A.
3

---

Problem formulation
In this section, introduce the task of achieving counterfactual fairness given PDAGS, especially MPDAGs that can be learned from observational data using causal discovery algorithms
53
Lemma 2.2 in Section 2.2 implies learning counterfactually fair prediction can be framed as selecting the non-descendants of to predict Y. If a causal DAG is used to encode the causal relations of all attributes, finding all non-descendants of A is straightforward. However, as mentioned in Section [ given observational data and optional background knowledge about direct causal information, we can only learn CPDAG an MPDAG G, instead of the true DAG D [9]. Unfortunately, not all ancestral relations between and attributes in X' are identifiable in CPDAG or MPDAG.
Therefore, to achieve counterfactually fair prediction, we have two problems to solve:
Identify the type of ancestral relations of any other attributes with A in 9, i.e., identifying the definite non-descensants, definite descendants, and possible descendants of in an MPDAG (Section :
Build counterfactually fair model based on the identified ancestral relations (Section 5
4 Identifiability of ancestral relations in MPDAGs
In this section, we give a sufficient and necessary graphical criterion on identifying the definite ancestral relations between two distinct vertices in an MPDAG. We also provide an efficient algorithm for implementing the proposed criterion. We denote the parents, children, siblings and adjacencies of the node W in graph as pa( 9), ch(W. 9), sib( W. W. and adj (W. 9). respectively. A chord of a path in G is any edge joining two non-consecutive vertices on the path. A path without any chord is called chordless path. In graph G (V, E), where V and E represent the node set and edge set in G, the induced subgraph of G over V' c V is the graph with vertex V and edges between vertices in V", that is E' E. A graph is complete any two distinct vertices are adjacent.
4.1 Graphical criterion on identifying ancestral relations in MPDAGs
We first introduce the term b-possibly causal path 42 in MPDAGs where the prefix stands for background.
Definition 4.1 (b-possibly causal path, b-non-causal path). Definition 1] Suppose p = (S
Vo, .... VE = T) is a path from S to T in MPDAG G. is b-possibly causal in G if and only if no edge V, Vj, s s S k in G, including the edge not on p. Otherwise, p b-non-causal path in G.
Perković al. 42 state that T is definite non-descendant of S in MPDAG g if and only if there no b-possibly causal path from S to T in G. In this section, to identify whether T is a definite descendant of S in an MPDAG, we provide a sufficient and necessary condition.
We introduce the term critical set 11 in CPDAGs as follows.
Definition 4.2 (Critical Set). LI Definition 2) Let G be an CPDAG, S and T be two distinct vertices G. The critical set of with respect
in G consists of all adjacent vertices of lying on at least one chordless possibly causal path from S to T.
Definition can be extended to MPDAGs directly, based which, provide a sufficient and necessary graphical condition in Lemma 4.3 for identifying the definite ancestral relation between two distinct vertices in MPDAG.
Lemma 4.3, Let G be an MPDAG and S, T be two distinct vertices in G, then T is a definite descendant of S in G if and only if the critical set of S with respect to T always contains child of S in every DAG D E [g].
The proof of Lemma is in Appendix B.I Note that we have to enumerate all Markov equivalent
DAGs for checking the condition given in Lemma 4.3 To resolve this problem, we provide a condition in Lemma 4.4 to check the graphical characteristic of the corresponding critical set in the
MPDAG directly. The graphical criterion in Lemma 2.4maa.44aa has been proved by 16 Lemma 2] and S Lemma 1] for CPDAGs. We extend it to general MPDAGs here.

---

Lemma 4.4. Let G be an MPDAG and S. T be two distinct vertices in G. Denote by C the critical set of S with respect to T in G, then C n c = 2 for some DAG D E [9]. if and only if Ø. or C induces a complete subgraph of G but C n ch(S.g) = Ø.
The proof of Lemma is in Appendix B.2
Building on Lemma and Lemma we arrived at the desired sufficient and necessary graphical criterion in Theorem 4.5
Theorem 4.5. Let S and T be two distinct vertices in an MPDAG G, and C be the critical set of S with respect to T in G. Then T is a definite descendant of S if and only if either S has a definite arrow into C, that is C n ch(S, 9) + Ø, or S does not have definite arrow into C but C is non- non-empty and induces an incomplete subgraph of
With Theorem 4.5
we can identify whether T definite descendant of S in an MPDAG by finding all chordless b-possibly causal path from S to T and checking graphical characteristic of the corresponding critical set. We provide an example to illustrate Theorem in Appendix C
4.2 Algorithms
Here we provide an efficient algorithm to identify the ancestral relation between any two distinet vertices in an MPDAG based on the theoretical results in Theorem 4.3 It is straightforward to identify the non-ancestral relation by checking there exists a b-possibly causal path from the source the target. However, discriminating between definite ancestral relation and a possible ancestral relation in an MPDAG by Theorem requires finding the critical set.
According to the definition of the critical set, we need to find all chordless possibly causal paths from the source variable to the target variable first. However, it is cumbersome check whether path is chordless, since it involves considering many edges not on the path. In Proposition 4..7 we propose a more efficient way find critical sets by leveraging the relation between chordless path and definite status path in Lemma 4.6 We first provide the notion of collider and definite status path.
Colliders and Definite Status paths. In path p (S = Vo. V T), if V,-1 V and V; + Vi+i. then we say Vú is a collider on p. If V;-1 and Vi+1 are not adjacent, then the triple (Vi-1, Ve, Vi+1) is called a v-structure collided on V. and V; can be called unshielded collider. A node V; is a definite non-collider on a path p if there is at least one edge out of V, on p or V V/- Vi+1 is subpath of p and Vi-1 is not adjacent with V.+1- A node is of definite status on a path if it is a collider, a definite non-collider or an endpoint on the path. A path is of definite status if every node on p is of definite status.
Lemma 4.6. Let S and T be two distinct vertices in an MPDAG G. If is a chordless path from S to T in G, then p is of definite status.
Proposition 4.7. Let G be MPDAG, S and T be two distinct vertices in G. Denote by OST the critical set of S with respect to T in G. then CsT = EST, where F sT denotes all adjacent vertices of S lying on at least one b-possibly causal path of definite status from S to T in G that there is no chord with S as an endpoint.
Proposition 4.7 implies that, instead of enumerating all chordless possibly causal path from the source vertex the target vertex, we enumerate b- b-possibly causal paths of definite status, excluding paths that contain any chord where the source vertex is an end node. The nodes adjacent to the source vertex on these paths constitute the desired critical set.
The proof of Lemma 4.6 and Proposition 4.7 are in Appendix and Appendix
B.5
respectively.
Following from Proposition 4.7 develop Algorithm I showing how to efficiently find the critical set of S w.r.t. T' in an MPDAG G. Given an MPDAG G, the source vertex S and the target vertex T. the output of Algorithm is the critical set of S w.r.t. T in G. Using the breadth-firss serch- algorithm, Algorithm| searches b-possibly causal path of definite status without any chord ending in S from S to T. A detailed explanation of this algorithm is provided in Appendix D
Finally, we present Algorithm 2 to identify the type of ancestral relation. We first find the critical set C of S with respect to T. When C Ø, there is no b-possibly causal path from S to T, so T we can decide whether T is a
a definite non-descendant of When C # Ø, using Theorem 5 definite descendant possible descendant of S.
5

---

Algorithm Finding the critical set of S with respect to T in an MPDAG
1: Input: MPDAG G, two distinct vertices S and T in G.
2: Output: The critical set C of S with respect T in G.
3: Initialize C = Ø, waiting queue Q = [], and a set H. = Ø,
4: for a E sib(SS) ch(SS) do
5: add (a, a,) to the end of Q,
6: while Q Ø do
7: take the first element (a, o, r) out of Q and add to Hc
8: if T then
9:
add a to C, and remove from all triples where the first element ar;
10: else
11:
for each node / in do if r B or 7
12:
then if T - B or Φ is not adjacent with 3 or T is the endnode then if B and S are not adjacent then
13:
15:
if (a,, T, 3) $ HH and (ax, т, 3) $ Q then
add (a, T, (3) the end of Q.
17: return C
Algorithm 2 Identify the type of ancestral relation of S with respect in an MPDAG
Input: MPDAG G, two distinet variables S and T g.
2: Output: The type of ancestral relation between S and T.
3: Find the critical set C of with respect to T by Algorithm
4: if |C| 0 then
5: return
a definite non-descendant of S.
6: if S has arrow into C C induces incomplete subgraph of G then
7: return a definite descendant of S.
8: return T is possible descendant of S.
Since in Algorithm [ the same triple like (a, db, r) can only be visited at most once, where a sibling child of S in the MPDAG G, is node on a b-possibly causal path of definite status from T without any chord ending in S, and á lies immediately before on such path. The complexity of Algorithm in the worst case is ([sii((S, + ch(S, 9)1 [F()))), where [E(G) is the number of edges in G. Consequently, the computational complexity of Algorithm 2 is ((s((, 9) + ch(S, G) [)))
Counterfactual fairness in MPDAGs
Now, we return to our problem of learning counterfactually fair models via selecting features from X. We will consider two cases: 1) general MPDAG and 2) MPDAG learned with background knowledge that A is a root node.
5.1 General case
We can identify the set definite descendants, possible descendants and definite non-descendants of the sensitive attribute by simply applying Algorithm 2 each pair of sensitive and any other attribute.
which is concluded in Algorithm 4 The detailed description of Algorithm Tis provided in Appendix E
As the computational complexity of Algorithm 2 in the worst case O (ssibsS g) + ch(S, G)
[E) the complexity of Algorithm
3 is directly O( sib,S))
ch(S,)) * E(G) * (V)))
where |E()] is the number of edges and [V( the number of nodes in We consider two
feature selection methods. The first method (called Fair) only selects the definite non-descendants, which ensures counterfactual fairness. However, the number of definite non-descendants in an MPDAG might be too small, resulting in low prediction accuracy. Therefore, we also propose second method (called FairRelax) which uses possible descendants of A increase the prediction accuracy at the cost of violation of counterfactual faimeess.

---

5.2 Under root node assumption
Kusner et al. 29 Section 3.2] mentioned the ancestral closure of sensitive attributes, meaning that typically we should expect the sensitive attribute set A to be closed under ancestral relationships given by the causal graph. For instance, the example that religion can be affected by the geographical place of origin, if religion is a sensitive attribute and geographical place of origin is a parent of religion, then it should also in A. Therefore, A will the root node in most cases except some counterintuitive scenarios. Thus, we consider the following assumption, which is often true in real-world datasets.
Assumption 5.1. The sensitive attribute can only be a root node in causal MPDAG.
For example, 'sex' cannot be caused by factors like 'education' and 'salary'. In an MPDAG G, given Assumption 5.I the ancestral relation between the sensitive attribute and any other attribute fully identified, as shown in the following proposition.
Proposition 5.2. In a MPDAG G with sensitive attribute A, if Assumption 5. holds, then any other attribute is either definite descendant or definite non-descendant of A. Moreover, an arbitrary attribute W is a definite descendant of A if and only if there is a causal path from A to W in g.
The proof of Proposition 5.2 is in Appendix B.6 From Proposition 5.2 it very interesting to see that fitting model with the definite non-descendants of A in G is exactly the same thing as fitting model with the non-descendants of A in the true DAG D. Thus, the counterfactual fairness can be achieved as if the true causal DAG is fully known.
Under Assumption 5. since there is a causal path from A any definite descendant of A. we directly identify whether a target attribute is a descendants of A by checking if there is a causal path from A to the target. To find all definite descendants in MPDAG, algorithm with computational complexity 0(VV + ||E)+ where [V] is the number of nodes and FE] is the number of edges in G. Then the remaining nodes are definite non-descendants of A in G.
can breath first search
6 Experiment
In this section, we illustrate our approach on simulated and real-world dataset by evaluating the prediction performance and fairness of our approach. The prediction performance is evaluated by root mean squared error (RMSE). The counterfactual unfairness can be measured by the discrepancy of the predictions in the real world and counterfactual world for each individual. In addition, unfairness can also be revealed by comparing the distributions of the predictions in two worlds, which coincide the prediction is counterfactually fair.
1) Full is a standard model that uses all attributes, including the sensitive attributes to make predictions. 2) Unaware is model that uses all attributes except the sensitive attributes to make predictions, and 3) Dracle is model that makes predictions with all attributes that are con-descendants of the sensitive attribute given the groundtruth DAG. As mentioned in Section 5 our proposed methods include FairRelax, which makes predictions using all definite non-descendants and possible descendants of the sensitive attribute in an MPDAG, and Fair, which makes predictions using all definite non-descendants of the sensitive attribute in an MPDAG.
Baselines. We consider three baselines:
6.1 Synthetic data
The synthetic data is generated from linear structural equation models according a random DAG, As the simulated DAG is known, we obtain the CPDAG from the true DAG without running the causal discovery algorithms We also add background knowledge to turn CPDAG into its corresponding MDPAG.
We first randomly generate DAGs with d nodes and 2d directed edges from the graphical model Erdōs-Rényi (ER), where chosen from (10, 20, 30, 40). For each setting, we generate 100 DAGs. For each DAG D, two nodes are randomly chosen as the outcome and the sensitive attribute, respectively. The sensitive attribute can have two or three values, drawn from a Binomial([O,1]) or
3 'Given a sufficiently large sample size, current causal discovery algorithms can recover the CPDAG with high accuracy the simulated data (20]
7

---

Multinomial((.1122) distribution separately. The weight, Big, of each directed edges X; - X, in the generated DAG, drawn from a (niform([-2.. -055 u [0.5, 2]) distribution. The data are generated according to the following linear structural equation model:
X;
Σ
B, G, i I,..., n,
(1)
XxEpa(X,)
where 61...., En are independent (N, (.5). Then we generate one sample with size 1000 for each DAG. The proportion of training and test data is splitted as 0.8 0.2. Once the CPDAG g* is obtained, where D E [g"]. we randomly generate the direct causal information A - B as the background knowledge from the edges where A - B is in DAG D, while A - B is in CPDAG g" We show a randomly generated DAG 'D the corresponding CPDAG G and MPDAG G as in Figure see Appendix [F.T For additional experiments based more complicated structural equations and varying amount of possible background knowledge, please refer to Appendix F44 and Appendix F.5
8
We also analyze the model robustness experimentally on causal discovery algorithms in Appendix F.6
Counterfactual fairness. According to the predefined linear causal model, we first generate the counterfactual data given counterfactual sensitive attributes. For each individual, the noise of any counterfactual feature is the same as that in the observational data. In order to evaluate the counterfac- tual fairness of the baseline methods, we sample data from both the original and counterfactual data and fit them with all the models. Here, unfairness can be measured by the absolute difference of two predictions, YAca(o (u) and Y y The results for each model with different graph settings are shown in Table and Figure La Obviously, Oracle and Fair is counterfactually fair, since they do not use any feature that is causally dependant on the sensitive attribute. Full and Unaware have high counterfactual unfairness, while our FairRelax has very low counterfactual unfairness. Additionally, when the model is counterfactually fair, the distributions of the predictions in two worlds should lie on top of each other, in the Oracle and Fair models. Although counterfactual unfairness is exhibited in the other three models, FairRelax is closer to strictly counterfactually fair methods. An exemplary density plot of the predictions of all the models in one original and counterfactual dataset is shown in Figure
Table I: Average unfairness and RMSE for synthetic datasets held-out test set. For each graph setting, the unfairness gets decreasing from left to right and the RMSE gets increasing from left to
right.
Node
Edge
Full
Unaware
FairRelax
Oracle
Fair
RMSE Unfairness
10
20
0.288 + 0.363
0.200 + 0.322
0.023 + 0.123
0.000 4 0,000
0.000 t 0.000
20
40
0.203 + 0.341
0.165 0.312
0.019 + 0.145
0.000 + 0.000
0.000 = 0.000
30
60
0.155
+ 0.304
0.143 0.312
0.020 0.123
0.000 = 0.000
0.000 # 0.000
40
80
0.095 + 0819
0.075 - 0.182
0.009 = 0.055
0.000 = 0.000
0.000 + 0.000
10
20
0.621 t 0.251
0.637 + 0.261
1.031 : 0.751
1.065 + 0.751
1.137 + 0.824
20
40
0,595 + 0.255
0.599 + 0.253
0.818 + 0.488
0.847 + 0.55
0.952 + 0.645
30
60
0.597
+ 0.24
0.601 + 0.242
0.797 + 0.489
0.849 + 0.644
1.024 + 0.908
40
80
0.600 + 0.273
0.601 0.272
0.755 0.441
0.766 = 0.452
0.800 + 0.480
Accuracy. For each graph setting, we report average RMSE achieved on 100 causal graphs by fitting a linear regression model for the baselines and our proposed models in Table and Figure 1b] We can observe that, for each graph setting, the Full model obtains the lowest RMSE, which is not surprising as it uses all features. In addition, our FairRelas methods obtains better accuracy than the strictly counterfactually fair methods Fair and Oracle, which is consistent with the accuracy- fairness trade-off phenomenon. More discussion accuracy- fainness trade-off is included in Appendix H
6.2 Real data
The UCI Student Performance Data Set [TC regarding students performance in Mathematics is used in this experiment. The data attributes include student grade in secondary education, demographic, social, and school related features. It contains 395 students records with 32 attributes. We regard sex as the sensitive attribute in this dataset. Besides, we remove the first, second and final period grade, denoted by GI,G2, and G3 the dataset and generate the value of target attribute Grade as the average of G1,G2, and G3.
8

---

10rotesBledggs E EinodestDeoges EII 30hoded00edggs @ #Dncdes80edges
(enodesSeedgee 2inodes40odges 80nodess 40rodes80:dgge
RIMEE
Full
Unaware
Fairielax
Oracle
Fair
Full
Unswware
FairRelax
Oracle
Fair
(a) Average unfairness for each model and graph setting. (b) Average RMSE for each model and graph setting.
Figure I: Average unfairness and RMSE for synthetic datasets on held-out test set. For each graph setting, the unfairness gets decreasing from left to right, while RMSE has the opposite trend. The extreme unfairness and high RMSE because almost all attributes are descendants of the sensitive attribute in around 10/ 100 randomly generated graphs. This also explains why the standard deviation of unfairness for the model Full, Unware, FairRelax and RMSE for FairRelax, Oracle and Fair is that large in Table
counterfactual data original data
density
(Full)
(Unaware)
Y (FairRelax)
(Oracle)
(Fair)
Figure 2: Density plot of the predicted (u- and Ya-a( (u) in synthetic data.
In this section, first learn the corresponding CPDAG from this dataset leveraging the GES structure learning algorithm (5. which is implemented by a general causal discovery software TETRAD 45 After uploading the preprocessed data, we can learn the CPDAG g* The evolution of the CPDAG MPDAG is shown in Appendix F2
Our experiments are carried out under the root node assumption on the MPDAG G in Figure sex cannot be caused by other variables in the dataset. Due to the space limit, Figure 9c is provided in Appendix F2 Thus, the ancestral relations
as
be fully identified according to theoretical results in Section 5.2 Our algorithm will find all the non-descendants of the sensitive attribute. On
this dataset, the definite descendants of
be identified as (Walc, goout, Dalc, studytime) and all
the other nodes are definite non-descendants of sex.
The counterfactual fairness and accuracy measured in almost the same way as in Section 6. The
details on counterfactual data generation and model fitting can be referred to Appendix The results reported in Table Since under the root node assumption, there is possible descendants of the sensitive attribute, the model Fair and FairRelax give the same RMSE result and both of them achieve counterfactual fairness at the cost of slight accuracy decrease. Instead, the model Full and Unaware are unfair and the Full model is more unfair than Unaware. Besides, the distribution of predictions for the original and counterfactual data for all models have the same trend as the synthetic data. Figure S is the corresponding density plot.
7 Conclusion and discussion
In this paper, we have developed a general approach to achieve counterfactual fairness when the true causal graph is unknown. In order to select features that lead counterfactual fairesss, we propose sufficient and necessary condition and an efficient algorithm to identify the ancestral relations between any distinct vertices MPDAG, which may be applied to more applications.

---

Table 2: Average RMSE and unfaireess for Student dataset on held-out test sets.
Full
Unaware
FairRelax
Fair
Unfairness
0.761 + 0.228
0.250 + 0.085
0.000 = 0.000
0.000 = 0.000
RMSE
3.49 0.292
3.482 1 0.297
3.509 + 0.356
3.509 0.356
counterfactual data
original data
density
649-
Grade (Full)
Grade (Unaware)
Grade (FairRelax)
Grade (Fair)
Figure 3: Density plot of the predicted Grade (u) and Gradesex-a for Student dataset.
Furthermore, intriguing finding is that, under the assumption that the sensitive attribute only be a root node in the graph, there is no possible descendant of the sensitive attribute, so that the fair features be selected correctly whatever the true DAG is. Experiments synthetic and real-world dataset show the effectiveness of our method.
One may claim that the fair prediction could be function of the descendants of the sensitive attributes by balancing the observables, thus making the effect the sensitive attribute canceled out. We agree with this opinion. However, it concerns the structural equations, which are in general unfalsifiable even if interventional data for all variables is available. In this paper, we do not address the assumptions structural equations for achieving counterfactual fairness on MPDAGs. As first step to obtaining a counterfactual fair predictor on an MPDAG, we focus on utilising the property of the causal graph (Level in 29 making prediction with the definite non-descendants (and possible descendants) of the sensitive attribute. But our work can also be extended to the case where "cancel out" could happen the structural equations (or more relaxed, conditional distributions). However, due to the fact that an MPDAG represents set of DAGs with different conditional distributions components and thus enjoy different latent space, the intuitive way to enumerate all DAGs is unrealistic. Addressing such issue on an MPDAG an interesting future direction.
MPDAG. One possible idea is to learn latent variables by specifying
Following prior work on establishing counterfactual fairness bias and the presence of confounders throughout this paper. Yet, another fundamental assumption in these carlier studies in causal modelling is that the causal graph is known, which offers new chance for the bias induced by misspecifying the causal DAG. Our work gives the first method to achieve counterfactual fairness without requiring the causal DAG to be specified. In the presence of selection bias and confounders to demographic parity, which is discussed extensively by Fawkes et al. 17 In this situation, it considerably more difficult provide clear causal interpretation without specifying the causal DAG. This gives rise to an exciting topic to research in future work. Exploring causal discovery algorithms find the ground-trute causal graph the presence of selection bias and confounders and then achieving counterfactual fairness on partially ancestral graphs 46 63), which would be significantly more difficult, another possible future direction.
68 we assumed no selection
causal DAG, counterfactual fairness measure degenerates
8 Acknowledgement
AZ was supported by Melbourne Research Scholarship from the University of Melbourne. SW was supported by ARC DE200101253. TL was partially supported by Australian Research Council Projects DP180 01188003343 103444, DE- 190101473, IC- 100009, DP-220102121, and FT-220100318. BH was supported by NSFC Young Scientists Fund No. 62006202 and Guangdong Basic and Applied Basic Research Foundation No. 2022A15 150 1652. KZ was partially supported by the National Institutes of Health (NIH) under Contract RO1 1559880, by the USF-Convergence Accelerator Track-D award #2134901, by grant from Apple Inc., and by grant from KDDI Research Inc.. MG was supported by ARC DE210101624.
10

---

References
[1] Tim Brennan, William Dieterich, and Beate Ehret. Evaluating the predictive validity of the compas risk and needs assessment system. Criminal Justice and Behavior, 36(1):21-40, 2009.
[2] Irene Chen, Fredrik D Johansson, and David Sontag. Why is my classifier discriminatory? Advances in Neural Information Processing Systems, 31, 2018.
[3] Wenyu Chen, Mathias Drton, and Ali Shojaie. Definite non ancestral relations and structure learning. In 8th Causal Inference Workshop at UAI (causalUAI 2021), 2021.
[4] Silvia Chiappa. Path-specific counterfactual faireess. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 7801-7808, 2019.
[5] David Maxwell Chickering. Learning equivalence classes of bayesian-network structures. The Journal of Machine Learning Research, 2:445-498, 2002.
[6] David Maxwell Chickering. Optimal structure identification with greedy search. Journal of machine learning research, 3(Nov):007-554, 2002.
[7] Yoichi Chikahara, Shinsaku Sakaue, Akinori Fujino, and Hisashi Kashima. Learning individu- ally fair classifier with path-specific causal-effect constraint. In International Conference on Artificial Intelligence and Statistics, pages 145-153. PMLR, 2021.
[8] Alexandra Chouldechova. Fair prediction with disparate impact: A study of bias in recidivism prediction instruments. Big data, 5(2):153-1633 2017.
[9] Diego Colombo, Marloes H Maathuis, et al. Order-independent constraint- causal structure learning. J. Mach. Learn. Res., 15(1):3741-3782 2014.
[10] Paulo Cortez and Alice Maria Gonçalves Silva. Using data mining to predict secondary school student performance. 2008.
[11] William Dieterich, Christina Mendoza, and Tim Brennan. Compas risk scales: Demonstrating accuracy equity and predictive parity. Northpointe Inc, 2016.
[12] Julia Dressel and Hany Farid. The accuracy, fairness, and limits of predicting recidivism. Science advances, 4(1)reaa05580, 2018
[13] Sanghamitra Dutta, Dennis Wei, Hazar Yucksel, Pin-Yu Chen, Sijia Liu, and Kush Varshney. Is there trade-off between fairness and accuracy? perspective using mismatched hypothesis testing. In International Conference on Machine Learning, pages 2803-2813. PMLR, 2020.
[14] Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Proceedings of the 3rd innovations in theoretical computer science conference, pages 214-226, 2012.
[15] Zhuangyan Fang and Yangbo He. Ida with background knowledge. In Conference on Uncer- lainty in Artificial Intelligence, pages 270-279. PMLR, 2020.
[16] Zhuangyan Fang, Yue Liu, Zhi Geng, Shengyu Zhu, and Yangbo He. A local method for identifying causal relations under markov equivalence. Artificial Intelligence, 10366,, 2022.
[17] Jake Fawkes, Robin Evans, and Dino Sejdinovic. Selection, ignorability and challenges with causal fairness. In Fürst Conference on Causal Learning and Reasoning, 2021.
[18] Sorelle A Friedler, Carlos Scheidegger, and Suresh Venkatasubramanian. The (im) possibility of fairness: Different value systems require different mechanisms for fair decision making. Communications of the ACM, 64(4):136-14) 2021.
[19] Sainyam Galhotra, Karthikeyan Shanmugam, Prasanna Sattigeri, Kush R Varshney, Rachel Bellamy, Kuntal Dey, et al. Causal feature selection for algorithmic fairness. 2022.
[20] Clark Glymour, Kun Zhang, and Peter Spirtes. Review of causal discovery methods based on graphical models. Frontiers in genetics, 10:524, 2019.

---

[21] Richard Guo and Emilija Perkovic. Minimal enumeration of all possible total effects in markov equivalence class. In International Conference on Artificial Intelligence and Statistics, pages 2395-2403. PMLR, 2021.
[22] Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. Advances in neural information processing systems, 29:3315-3323 2016.
[23] Mitchell Hoffman, Lisa B Kahn, and Danielle Li. Discretion in hiring. The Quarterly Journal of Economics, 133(2):755-800 2018.
[24] Patrik O Hoyer, Dominik Janzing, Joris M Mooij, Jonas Peters, Bernhard Schölkopf, et al. Nonlinear causal discovery with additive noise models. In NIPS, volume 21, pages 689-696. Citeseer, 2008
[25] Aria Khademi, Sanghack Lee, David Foley, and Vasant Honavar. Fairness in algorithmic decision making: An excursion through the lens of causality. In The World Wide Web Conference, pages 2907-2914, 14, 2019.
[26] Amir E Khandani, Adlar J Kim, and Andrew W Lo. Consumer credit-risk models via machine- learning algorithms. Journal of Banking & Finance, 34(11):2767-2787, 2010.
[27] Niki Kilbertus, Mateo Rojas Carulla, Giambattista Parascandolo, Moritz Hardt, Dominik Janzing, and Bernhard Schölkopf. Avoiding discrimination through causal reasoning. Advances in neural information processing systems, 30, 2017.
[28] Matt Kusner, Chris Russell, Joshua Loftus, and Ricardo Silva. Making decisions that reduce discriminatory impacts. In International Conference on Machine Learning, pages 3591-3600. PMLR, 2019.
[29] Matt Kusner, Joshua Loftus, Chris Russell, and Ricardo Silva. Counterfactual fairness. Advances in neural information processing systems, 30, 2017.
[30] Yue Liu, Zhuangyan Fang, Yangbo He, and Zhi Geng. Collapsible ida: Collapsing parental sets for locally estimating possible causal effects. In Conference Uncertainly in Artificial Intelligence, pages 290-299. PMLR, 2020.
[31] Yue Liu, Zhuangyan Fang, Yangbo He, Zhi Geng, and Chunchen Liu. Local causal network learning for finding pairs of total and direct effects. Mach. Learn. Res., 21:148 1, 2020.
[32] Marloes H Maathuis, Markus Kalisch, and Peter Bühlmann. Estimating high-dimensional intervention effects from observational data. The Annals of Statistics, 37664):313-3114, 2009.
[33] N Martinez and M Bertran. Fairness with minimal harm: A pareto-optimal approach for healthcare. NeurlPS ML4H: Machine Learning for Health, 2019.
[34] Christopher Meek. Causal inference and causal explanation with background knowledge. In Proceedings of the Eleventh conference Uncertainty in artificial intelligence, pages 403-410, 1995.
[35] Aditya Krishna Menon and Robert C Williamson. The cost of fairness in binary classification. In Conference on Fairness, Accountabiliity and Trunsparency, pages 107-118. PMLR, 2018
[36] Joris M Mooij and Tom Claassen. Constraint- causal discovery using partial ancestral graphs in the presence of cycles. In Conference on Uncertainty Artificial Intelligence, pages 1159- 1168. PMLR, 2020.
[37] Razich Nabi and 1lya Shpitser. Fair inference on outcomes. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018
[38] Judea Pearl. Probabilistic reasoning in intelligent systems: networks of plausible inference. Morgan kaufmann, 1988.
[39] Judea Pearl. Causality. Cambridge university press, 2009.
12

---

[40] Judea Pearl et al. Models, reasoning and inference. Cambridge. UK: CambridgeUnivveriiyypresss 19, 2000.
[41] Emilija Perkovic. Identifying causal effects in maximally oriented partially directed acyclic graphs. In Conference on Uncertainty in Artificial Intelligence, pages 530-539. PMLR, 2020.
[42] Emilija Perkovic, Markus Kalisch, and Marloes H Maathuis. Interpreting and using epdags with background knowledge. Proceedings of the 2017 Conference on Uncertainty Artificial Intelligence (UA12017), pages ID-120. AUAI Press, 2017.
[43] Jonas Peters and Peter Bühlmann. Identifiability of gaussian structural equation models with equal error variances. Biometrika, 101(():219-22) 2014.
[44] Jonas Peters, Joris M Mooij, Dominik Janzing, and Bernhard Schölkopf. Causal discovery with continuous additive noise models. 2014.
[45] Joseph D Ramsey, Kun Zhang, Madelyn Glymour, Ruben Sanchez Romero, Biwei Huang, Imme Ebert- -ppoff, Savini Samarasinghe, Elizabeth Barnes, and Clark Glymour. Tetrad toolbox for causal discovery. In 8th International Workshop on Climate Informatics, 2018.
[46] Thomas Richardson and Peter Spirtes. Ancestral graph markov models. The Annals of Statistics, 3024);92-11030 2002.
[47] Anna Roumpelaki, Giorgos Borboudakis, Sofia Triantafillou, and Ioannis Tsamardinos. Marginal causal consistency in constraint- based causal learning. In Causation: Foundation to Application Workshop, UAI, 2016.
[48] Chris Russell, M Kusner, C Loftus, and Ricardo Silva. When worlds collide: integrating different counterfactual assumptions in faimesss. In Advances in neural information processing systems, volume 30. NIPS Proceedings, 2017.
[49] Babak Salimi, Luke Rodriguez, Bill Howe, and Dan Suciu. Interventional fairness: Causal database repair for algorithmic fairness. In Proceedings of the 2019 International Conference on Management of Data, pages 793-810, 2019.
[50] Shubham Sharma, Yunfeng Zhang, Jesús Aliaga, Djallel Bouneffouf, Vinod Muthusamy, and Ramazon Kush. Data augmentation for discrimination prevention and bias disambiguation. pages 358-364, 02 2020.
[51] Shohei Shimizu, Patrik O Hoyer, Aapo Hyvärinen, Antti Kerminen, and Michael Jordan. linear non-gaussian acyclic model for causal discovery. Journal of Machine Learning Research, 7(10), 2006.
[52] Pater Spirtes, Clark Glymour, Richard Scheines, Stuart Kauffman, Valerio Aimale, and Frank Wimberly. Constructing bayesian network models of gene expression networks from microarray data. 2000.
[53] Peter Spirtes and Clark Glymour. An algorithm for fast recovery of sparse causal graphs. Social science computer review, (1):62--7, 1991.
[54] Peter Spirtes, Clark N Glymour, Richard Scheines, and David Heckerman. Causation, prediction, and search. MIT press, 2000.
[55] Latanya Sweeney. Discrimination in online ad delivery. Communications the ACM, 56(5):44- 54, 2013.
[56] Susan Wei and Mare Niethammer. The fairness-accurace pareto front. Statistical Analysis and Data Mining: The ASA Data Science Journal, 15(3):887332, 2022.
[57] Michael Wick, Jean-Baptiste Tristan, et al. Unlocking faimesss: a trade-off revisited. Advances in neural information processing systems, 32, 2019.
[58] Yongkai Wu, Lu Zhang, and Xintao Wu. On discrimination discovery and removal in ranked data using causal graph. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 2536-2544, 2018.
13

---

[59] Yongkai Wu, Lu Zhang, and Xintao Wu. Counterfactual faimess: Unidentification, bound and algorithm. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, 2019.
[60] Yongkai Wu, Lu Zhang, Xintao Wu, and Hanghang Tong. Pe-faimess: A unified framework for measuring causality-bar -ased fairness. Advances in Neural Information Processing Systems, 32, 2019.
[61] Samuel Yeom and Michael Carl Tschantz. Discriminative but not discriminatory: A comparison of fairness definitions under different worldviews. ArXiv, abs//800..0m N0111108..661111 2018.
[62] Jiji Zhang. Causal inference and reasoning in causally insufficient systems. PhD thesis, Citeseer, 2006.
[63] Jiji Zhang. Causal reasoning with ancestral graphs. Journal of Machine Learning Research, 9:1 9:1437-1474, 2008.
[64] Junzhe Zhang and Elias Bareinboim. Equality of opportunity in classification: A causal approach. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 3675-3685. 2018.
[65] Junzhe Zhang and Elias Bareinboim. Fairness in formula. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
causal explanation
[66] K Zhang and A Hyvärinen. On the identifiability of the post-nonlinear causal model. In 25th Conference on Uncertainty Artificial Intelligence (UAI 2009), pages 647-655. AUAI Press, 2009.
[67] Lu Zhang and Xintao Wu. Anti-discrimination learning: a causal modeling-basee baaed framework. International Journal of Data Science and Analytics, 4(1):1-16, 2017.
[68] Lu Zhang, Yongkai Wu, and Xintao Wu. A causal framework for discovering and removing direct and indirect discrimination. In Proceedings of the Twenty-Sixhh International Joint Conference on Artificial Intelligence, 2017.
[69] Lu Zhang, Yongkai Wu, and Xintao Wu. Causal modeling-based discrimination discovery and removal: criteria, bounds, and algorithms. IEEE Transactions on Knowledge and Data Engineering, 31(11):2035-22
2018.
[70] Han Zhao and Geoff Gordon. Inherent tradeoffs in learning fair representations. Advances in neural information processing systems, 32, 2019.
[71] Indre Zliobaite. On the relation between accuracy and faireess in binary classification. In The 2nd workshop Fairness, Accountability, and Transparency in Machine Learning (FATML) at ICML 15, 2015.
14

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're rou're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
15


Reviews:
[{"review_id": "xDaqcLe0za", "reviewer": "Reviewer_UUSP", "summary": "This paper works within a structural causal modeling (SCM) framework for defining fairness of algorithms. Previous literature defining fairness this way assumes knowledge of the relevant SCM, which is a key limitation. The current paper relaxes this assumption to some specific contexts where the SCM is partially known, that is when a maximally partially directed acyclic graph (MPDAG) is available rather than a full directed acyclic graph (DAG). In the MPDAG framework a variable can be a definite descendent, definite non-descendent, or a possible descendent of other variables. This paper provides algorithms for determining which of these relationships holds for a given pair of variables and theorems to establish the correctness of the algorithms. The application to fairness involves considering which variables are definite or possible descendants of a sensitive attribute, and proposing corresponding definitions of fairness based on whether only definite non-descendants are used in the prediction (Fair) or possible descendants are also included (FairRelax) and only definite descendants are excluded. \n", "questions": "Q1: Counterfactual fairness is possible even with definite descendants provided counterfactual changes “cancel out” in the prediction. The current paper gives an incorrect definition on lines 51-53 which is based on a sufficient (but not necessary) condition for counterfactual fairness. \n\nQ2: Should the unfairness of Oracle and Fair methods in the simulations be exactly zero, even in samples? I would think it will be close to zero in each realization and very close to zero on average, with small standard errors- but not necessarily exactly zero.\n\nQ3: Most of the methods proposed in this paper do not seem to be necessarily connected to fairness. Presumably it is of more general interest to determine the ancestral relationships in an MPDAG. Would it make more sense to reframe the paper as a general method within the SCM literature, and its application to fairness just one of the motivating examples? This may also strengthen the paper since, as I point out in Q1, the connection of the current methods to fairness is based on a sufficient condition which may not be necessary, and hence it may not be a strong enough connection for fairness to be a main focus of the paper.\n\nMinor issue: In section 5.1, isn’t the inclusion of “(possibly small)” a bit of wishful thinking? The violation of fairness could also possibly be large. Without knowledge of a specific context to justify either possibility perhaps this speculation should be omitted.\n\nMinor issue: citing preprints instead of published versions, e.g. of [21, 23, 56]\n", "limitations": "The weaknesses and questions above, as well as the limitations inherited by any SCM type of approach which include untestable assumptions. The current paper also acknowledges its assumptions of no confounding or selection bias, but it is reasonable to try to address that in future work rather than all at once.", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: SCM approaches rely on very strong assumptions so it is useful to relax these.\n\nStrength: The simulation results use fairly high dimensional DAGs compared to the common examples considered in counterfactual fairness.\n\nWeakness: Many of the results and basically all of the illustrative figures are in appendices. I think the paper could be improved by reorganization that includes showing examples in the main text, like figures 2, 3, and 6 which are currently in the appendices. As it is now, a reader who is not already familiar with PDAG, CPDAG, MPDAG will not know how to visualize these unless they read the supplementary material, and will struggle to understand the definitions and lemmas. \n\nWeakness: It is possible the technical contribution of the current paper is a relatively small increment, extending Lemma 4.4 from previous work on CPDAGs. Since much of the details is in the appendix I did not review it all carefully enough to compare with the previous papers. This paper could be strengthened by clarifying which parts are new contributions.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["Discrimination / Bias / Fairness Concerns"]}, "extra_text": {}}, {"review_id": "bCP__rlpsp", "reviewer": "Reviewer_Hhvs", "summary": "Given an MPDAG, the authors prove a method that can identify whether a variable is a definite descendant, definite non-descendant, or possible descendant of another variable. Building upon this result, the authors further study the problem of learning counterfactually fair models via selecting features.", "questions": "1. The introduction of b-critical set (Definition 4.2) is not necessary. Since a chordless b-possibly causal path from S to T definitely has no chord, it degenerates to a partially directed path. Therefore, there is no essential difference between the definition of b-critical set and the definition of critical set defined by Fang and He (2020), except that the latter is defined with respect to CPDAGs.\n\n2. It seems to me that Lemma B.2 is flawed. Lemma B.2 states that if $R\\subseteq sib(X, G)$ has a subset that induces a complete subgraph, then there is a DAG $D$ in $[G]$ such that $pa(X, D)=pa(X, G)\\cup R$. If Lemma B.2 is correct, then for any $R\\subseteq sib(X, G)$ that induces a complete subgraph, there is a DAG $D$ in $[G]$ such that $pa(X, D)=pa(X, G)\\cup R$. However, this is impossible. For example, consider a complete graph with 4 variables: $X, S_1, S_2, C$. Every edge except $C\\to S_1$ is undirected. Let $R=\\\\{S_1, S_2\\\\}$. $R$ induces a complete subgraph, but orienting $R\\to X$ and $X \\to C$ will lead to a directed cycle.\n\n3. A minor point. Some cited papers have been published. Please revise the bib to make sure that their latest versions are cited. \n", "limitations": "The limitations of the paper have been addressed.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, I think this paper is relevant, new, and interesting. The paper is well-written and well-organized. The motivation is clearly described and the contribution is also clear. However, there is a technical lemma that seems flawed. Please refer to the detailed questions below.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "aj5YJA8cgkn", "reviewer": "Reviewer_v6YC", "summary": "The paper proposes a mechanism to perform fairness aware feature selection that achieve counterfactual fairness under certain assumptions. \n\n\n", "questions": "Please clarify the connection to related work and how sensitive this approach is with respect to noise in MPDAG.", "limitations": "The authors have clearly discussed their assumptions.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nS1 Fairness aware feature selection is an important problem which is underexplored.\nS2 Problem setting that complete causal graph may not be available is important.\nS3 The paper is easy to follow.\n\n\nWeaknesses\nW1 The critical assumption is that the sensitive attribute does not have any ancestors. Another crucial assumption for the analysis is the absence of confounders. Please discuss the realistic implications of these assumptions and the challenges because of these.\n\nW2 It is unclear how noise in MPDAG would affect the quality of this approach. Please discuss this in light of cases where it is learned from data.\n\nW3 Experiments on real data do not show how their approach is able to ensure fairness of the trained classifier.\n\nW4 Related Work: There is no discussion of these techniques as compared to this recent paper which does not assume knowledge of causal graph and performs feature selection.\n[1] Causal Feature Selection for Algorithmic Fairness. S Galhotra, K Shanmugam, P Sattigeri, KR Varshney. SIGMOD 2022.\n\nW5 Algorithm complexity seems quite high. Please discuss running time on real datasets.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept