Interventional Fairness on Partially Known Causal Graphs: A Constrained Optimization Approach
Authors: Aoqi Zuo
Yiqing Li
Susan Wei
Mingming Gong
Venue: ICLR 2024 poster (2024)
Keywords: trustworthy machine learning
causal inference
fairness
Primary area: societal considerations including fairness, safety, privacy

Abstract: Fair machine learning aims to prevent discrimination against individuals or sub-populations based on sensitive attributes such as gender and race. In recent years, causal inference methods have been increasingly used in fair machine learning to measure unfairness by causal effects. However, current methods assume that the true causal graph is given, which is often not true in real-world applications. To address this limitation, this paper proposes a framework for achieving causal fairness based on the notion of interventions when the true causal graph is partially known. The proposed approach involves modeling fair prediction using a Partially Directed Acyclic Graph (PDAG), specifically, a class of causal DAGs that can be learned from observational data combined with domain knowledge. The PDAG is used to measure causal fairness, and a constrained optimization problem is formulated to balance between fairness and accuracy. Results on both simulated and real-world datasets demonstrate the effectiveness of this method.

Published as a conference paper at ICLR 2024
INTERVENTIONAL FAIRNESS ON PARTIALLY KNOWN CAUSAL GRAPHS: A CONSTRAINED OPTIMIZATION APPROACH
Aoqi Zuo', Yiqing Li Susan Wei' Mingming Gong
School of Mathematics and Statistics, The University of Mclbourne School of Data Science, Fudan University
Mohhaedd bin Zayed University of Artificial Intelligence
azuo@studens unime www.mel...uuu.......m...... edu. Segingli20@fucciee edu. en {susan. wei, mingming. gong e @un simemeli 1b. edu. au
ABSTRACT
Fair machine learning aims to prevent discrimination against individuals or sub- populations based sensitive attributes such gender and race. In recent years, causal inference methods have been increasingly used in fair machine learning to measure unfairness by causal effects. However, current methods assume that the true causal graph is given, which is often not true in real-world applications. To address this limitation, this paper proposes framework for achieving causal fair- ness based on the notion of interventions when the true causal graph is partially known. The proposed approach involves modeling fair prediction using Partially Directed Acyelic Graph (PDAG), specifically, a class of causal DAGs that can be learned from observational data combined with domain knowledge. The PDAG is used to measure causal fairness, and constrained optimization problem is for- mulated to balance between fairness and accuracy. Results on both simulated and real- real-world datasets demonstrate the effectiveness of this method.
INTRODUCTION
Machine learning algorithms have demonstrated remarkable success in automating decision-making processes across a wide range domains (c.g., hiring decisions (Hoffman et al. 2018), recidivism predictions (Dieterich et al. 2016 Brennan et al. 2009), and finance (Sweeney) 2013 Khandani et al., 2010).. providing valuable insights and predictions. However, it has become increasingly evident that these algorithms are not immune biases in training data, potentially perpetuating discrimination against individual or sub-population group with respect to sensitive altributes, e.g.. gender and race. For example, bias against female was found in recruiting tool built by one of Amazon's 's AI team to review job applicants' resume in period of time (Kodiyan 2019).
To achieve fair machine learning, various methods have been proposed with respect different fair- ness measures. These methods can be broadly classified into two groups. The first group focuses on developing statistical fairness measures, which typically indicate the statistical discrepancy between individuals or sub-populations, e.g., statistical parity (Dwork et al., 2012). equalized odds (Hardi al., 2016), and predictive parity (Chouldechoval 2017). The second group is grounded in the causal inference framework (Pearl et al., 2000). which emphasizes understanding the causal rela- tionships between the sensitive attribute and decision outcomes and treats the presence of causal effect of the sensitive attribute the decision discrimination (Zhang et al. 2017,Killertus
al. 2017 Kusner et al. 2017 Zhang & Bareinboim, 201 al Nabi & Shpitser [018 || Wu et al. 2019b
Khademi al. | 2019 Chiappa 2019 Russell al. 2017 Zhang et al.] 2018 Zhang & Wu 2017
Kusner et al. 2019 Salimi et al. 20199 Wu et al.) 2018 Galhotra et al. 2022 Zuo et al. 2022).
Causality based fairness notions defined within the framework of Pearl's ladder of causation,
which encompasses interventions and counterfactuals. Build on the highest rung and also the most
fine-grained type of inference in the ladder, counterfactual faimess (Kusner al. 2017
Chiappa

---

Published as a conference paper at ICLR 2024
2019 Russell et al., 2017, Wu et al. 2 requires the full knowledge of structural causal model or the computation of counterfactuals in the sense of Pearl et al. (200). thus posing extra challenges compared to the one based on interventions. As the most basic and general notion of causal fairness that is testable with observational data, the interventional fairness assesses the unfairness as the causal effect of the sensitive attribute the outcome on paths defined by specific attributes. In this paper, we aim to achieve interventional fairness.
The majority of existing methods for ensuring causal fairness assume the presence of a causal di- rected acyclic graph (DAG) (Pearl 2009), which encodes causal relationships between variables. However, in many real-world scenanios, it very difficult fully specify the causal DAG due to a limited understanding of the system under study. One potential approach is to use causal discovery methods to deduce the causal DAG from observational data (Spirtes & Glymour 1991, Colombo
et al. 2014, (Spirtes et al. 2000a; Chickering 2002b) [Shiiiuu et al.] 2006) Hoyer et al. 2008
Zhang & Hyvärinen| 2009 Peters et al.) 2014] Peters Bühlmann, 2014). However, determining
the true underlying causal graph solely based on observational data is challenging without strong
assumptions about the data generation process, such as linearity (Shimizu et al. 2006) or additive noise (Hoyer et al. 2008 Peters et al. 2014). In general cases, causal discovery methods may pro- duce a Markov equivalence class of DAGs that capture the same conditional independencies in the data, represented by completely partially directed acyclic graph (CPDAG) (Spirtes al. (0000b] Chickering 2002b; MMek 1995 Andersson et al.) 1997| CCickering 2002a). Although incorporat- ing additional background knowledge allows for the discermment of more causal directions, resulting in maximally partially directed acyclic graph (MPDAG) (Meek 1995), it is still unlikely to obtain a unique causal DAG.
Following this line of inquiry, a natural question arises: Can we learn interventional fairness when only have partially knowledge of the causal graph, represented by an MPDAG? D Inspired by Zuo et al. (2022), one straightforward way to achieve fair predictions for interventional fairness is to identify the definite non-descendants of the sensitive attribute an MPDAG (see Section [.1 While this approach guarantees interventional fairness, disregarding the descendants results in a no- table decline performance. Thus, we propose constrained optimisation problem that balances the inherent competition between accuracy and fairness (see Section 3.2). In our approach, to measure interventional fairness in MPDAGs, variables. Interestingly, this modeling technique gives rise to another causal MPDAG, which allows us discuss the identification of interventional fairness criterion formally.
model the prediction the effect of all the observational
In this paper, we assume the absence of selection bias and latent confounders since causal discov- ery algorithms themselves faces difficulties in such challenging scenarios. These assumptions align with many recent related work (Zhang et al., [017] Chiappa [2019] Chikahara et al.) [2021] Wu et al.) 2019a). However, we relax the assumption of fully directed causal DAG. Based on these consid- erations, our main contributions on achieving interventional fairness MPDAGs are as follows:
We propose a modeling technique on the predictor, which gives rise to causal MPDAG on which it feasible to perform causal inference formally;
We analyze the identification condition over interventional fairesss measure on the MPDAG;
We develop a framework for achieving interventional fairness on partially known causal graphs, specifically MPDAGs, as a constrained optimization problem.
2 BACKGROUND
2.1
STRUCTURAL CAUSAL MODEL AND CAUSAL GRAPH
The structural causal model (SCM) (Pearl et al. 2000) provides a framework for representing causal relations among variables. It comprises a triple (U, V. F), wherein represents observable en- dogenous variables and U represents unobserved exogenous variables that cannot be caused by any variable in V. The set consists of functions f1, ..., fny each associated with a variable Vú V describing how V2 depends on its direct causes: V. fe(pa,, U.) Here, pa, denotes the observed
As CPDAG is special case of MPDAG without background knowledge, deal with MPDAG generally.
2

---

Published as a conference paper at ICLR 2024
direct causes of V2 and U, is the set of unobserved direct causes of V. The exogenous U,'s required to be mutually independent. The equations in F induce a causal graph D that represents the relationships between variables, typically in the form of a directed acyelic graph (DAG), where the direct causes of Vú correspond to its parent set in the causal graph.
DAGs, PDAGs and CPDAGs. A directed acyclic graph (DAG) is characterized by directed edges and the absence of directed cycles. When some edges are undirected, it is referred to as a partially directed graph (PDAG). The structure of DAG captures collection of conditional independence relationships through the concept of d-separation (Pearl) 1988). In cases where multiple DAGs en- code the same conditional independence relationships, they are considered to be Markov equivalent. The Markov equivalence class of a DAG DD can be uniquely represented by completed partially directed acyclic graph (CPDAG) C, often denoted as [C].
MPDAGs. A maximally oriented PDAGs (MPDAG) (Meek 1995) can be obtained by applying Meek's rules in Meek (1993) CPDAG with background knowledge constraint. To construct an MPDAG G from a given CPDAG C. and background knowledge B, Algorithm I in Perkovic et al. 2017) can be utilized, which the background knowledge is assumed to be the direct causal information in the form X - Y, indicating that X is a direct cause of Y The subset of Markov equivalent DAGs that align with the background knowledge B can be uniquely represented by an MPDAG G, denoted as [9]. Both a DAG and a CPDAG can be viewed as special cases of an MPDAG, where the background knowledge is fully known and unknown, respectively.
Density. A density f over V is consistent with a DAG D = (V,E) if it can be factorized as f(v) IIvev f(., |pa( o;, D)) (Pearl 2009 Perkovic et 2017). A density f of is consistent with an MPDAG G = (V, E) if f consistent with a DAG in [G].
2.2 CAUSAL INFERENCE AND INTERVENTIONAL FAIRNESS
The interventions do = x) or the shorthand do(x) represent interventions that force X to take certain value x. In a SCM, this means the substitution of the structural equation X = fx(1xx: Ux) with = x. The causal effect
set of treatments X on a set of responses can be understood X via the do operator, which can be denoted as f(Y = y (X = x)) or P(yx) Pearl 1995 2009 In the context of an MPDAG g, such causal effect is identifiable if it is possible to be uniquely computed. For a formal definition and a brief review on the causal effect identification problem on MPDAG, please refer to Appendix H
as the post-interventional density of Y when intervening
Build the do-operator, interventional fairness criterion (Salimi al. 2019) is defined upon ad- missible attribute. An admissible attribute is one through which the causal path from the sensitive attribute the outcome is still considered fair. For example, in construction company hiring scenario, the attribute strength is considered as an admissible attribute as it is a valid criterion for assessing job candidates. Despite being causally affected by the attribute gender, the causal path 'gender - strength - hiring decision' should not be regarded as discriminatory.
Formally, let A. Y and X represent the sensitive attributes, outcome of interest and other observable attributes, respectively. The prediction of Y is denoted by Y. We say the prediction Y is interven- tionally fair with respect to the sensitive attributes A if, for any given set of admissible attributes Xad S X, satisfies the following condition:
Definition 2.1 (Interventional fairness). Salimi et al. 2019) We say the prediction Ý is interven- tionally fair with respect to the sensitive attributes if the following holds for any X.d Xad'
P( = v|do(A A = a)) do( = =x,a)) P(Ý = yldo( A aa), do( = =xaa),
for all possible values of y and any value that and X can take.
It is worth noting that other forms of background knowledge, such as tier orderings, specific model re- strictions, or data obtained from previous experiments, can also induce MPDAGs Scheines et al. (1998) al. Hoyer
et al. (2012) (Husser & Bühlmann (201) Eigenmann et al. (0077: Wang et al. (2017) Rothenhäusler et al. (2018)
3

---

Published as a conference paper at ICLR 2024
3 PROBLEM FORMULATION
In this section, we focus on the challenge of attaining interventional fairness in PDAGs, particular MPDAGs that can be learnt from observational data using causal discovery algorithms (Spirtes & Glymour 1991; Colombo et al. [2144] Chickering 2002a). We begin by presenting a basic implica- tion of the definition of interventional fairness as baseline method for achieving fairness. However, to overcome its limitations, we formulate a constrained optimisation problem.
3.1 FAIRNESS UNDER MPDAGS AS A GRAPIICAL PROBLEM
simple but important implication in achieving interventional fairness the following:
Lemma 3.1. Let be the causal graph of the given model (U,VF), Then Y will be interventionally fair if is a function of the admissible set Xad and non-descendants of A.
Zuo et al. (2022) propose a graphical criterion and algorithms for identifying the ancestral relation- ship between two vertices on an MPDAGs which we review in Appendix D.I These findings form the basis for learning (exactly) interventionally fair predictions as indicated by Lemma B.1 How- ever, claim that by including descendants, the prediction accuracy is possible to be improved. We propose a constrained optimisation problem that balances the inherent competition between ac- curacy and fairness.
3.2 e- C-APPROXIMATE INTERVENTIONAL FAIRNESS
We first establish an approximation to interventional fairnsss to address the problem of learning a fair prediction on an MPDAG.
Definition 3.1 (e-Appmxxe Interventional Fairness). predictor V is e-approximate interven- tionally fair with respect to the sensitive attribute A for any value of admissible set X Xad we have that:
IP( vldo(A = a), do(X = xxa)) - P( yl A = a'), do = xaa)l sc
for any a' #
Objective. Our objective is to train a model hg mapping from a subset of observable variables to Y with parameter 0 so as to accurately predict Y while simultaneously achieving e-approximate interventional fairesss. To accomplish this, we minimize the loss function ((j. v) under the fairness
constraint. Given a dataset with n observations {A (4) x(9) y(0)) for i = 1,2,..., n, where x(!) c
x represents the admissible set. For specific intervention on Xad Xad, the objective can be formulated as follows:
min
((). XIP((A=aa....x..)) P(YA-sIX..-x..))
(1)
1=1
where P(YA-a.X... x..) and of & under do(A a, x xad) and do(A a' Xud xud), respectively. The parame- ter A balances the trade-off between accuracy and fairesss. In this paper, we focus on the mod- elling and identification of the objective function for a specific intervention on X If we con- sider multiple values of adds the fairness term in Equation (T) can be replaced with the average of 1( --x.X.)-xx.) P(YA-a'... A'.a''X.==x.. ) over different interventions on Xud-
represent the post-interventional distributions
This formulation raises two key challenges: 1) how to design the model he (for Y) over an MPDAG; 2) when and how P( y) A a, X x,d)) is identifiable using the observational densities within our modeling framework.
4 INTERVENTIONAL FAIRNESS UNDER MPDAGS
As mentioned in Section I the underlying causal DAG D is usually unknown for real-world datasets. At most, we can obtain refined Markov equivalence class of DAGs represented by MPDAG
4

---

Published as a conference paper at ICLR 2024
from the observational data (X, A) and additional background knowledge. In this section, model the predictor as function of all the other observable variables, regardless of whether they (possible) descendants non-descendants of the sensitive attribute. Then we show that such modeling technique leads another MPDAG over A, which facilitates causal inference.
4.1 MODELING AND VERIFICATION
Modeling. We illustrate our modeling technique with Figure 1 Let D (V, E) in Figure la be the underlying causal DAG over the observational variables X and where X A, and be the consistent observational density over V, factorized as f(v) IIv ((: D)). We model the fair predictor y as function ha(x, a) of x and a with parameter 0. Under Pearl's SCM framework, our modeling technique implies
An underlying causal DAG D' over X, and Ý which includes additional edges from V to y for any V V compared with the DAG D, as depicted in Figure lb;
2. The density f over VUÝ, denoted as f(v, ú) f'(lvvf(v)) is consistent with D where
ÿ hg(x, a);
3. The density f(v) is consistent with any MPDAG g3 where D [9] and the density
f(v,j) 1) is consistent with any MPDAG g*, where D' E [[ Figure Ic and Figure ld
are two examples of G and g², respectively.
Xpa
X(4]
X(1
X(2)
X
X(2)
X[3]
X
X(2)
X(3)
X(3)
X13)
(a) DAG D
DAG D
(c) MPDAG
(d) MPDAG g"
Figure 1: (a) is an underlying causal DAG D with three variables X[1]. X(2] and X[3] in X; (b) is causal DAG D* under modeling on y; (c) is an example MPDAG G such that D E [G] (d) an example MPDAG g* such that D [[']]
Next, we introduce Definition 4.1 formalize such modeling strategy.
Definition 4.1 (Augmented-G with Ý). For partially directed graph G (V, E), let G augment G by (i) adding an additional vertex Y; (ii) adding the edge V - Y for each node V E V in G. The resulting graph is denoted g" = =V*, EE",, where V VUY, E EU (V - Y E V).
We call G* the augmented-G with Y.
Although directly learning MPDAG from X, A and V is not feasible due the unobservability of Y. Theorem 4.1 implies that once we obtain the MPDAG from the observational data (X, A) with background knowledge B, the augmented-g with Y. g", is exactly an MPDAG technically such that D* E [G*]. Therefore, the density f(v. ú) is consistent with G
Theorem 4.1. For a DAG D (V,E). , let be an MPDAG consistent with the background knowl- edge such that D E [g]. Let DD' be the augmented-D DD with Y and g" be the augmented-g with Y Then the graph 9* is an MPDAG consistent with the background knowledge B (U(V - ÝIV E V) such that D E [[*]]
Theorem verified by exploring the property of Meek's rules. For more detail, please refer to independent interest as it establishes a general modeling method applicable to any problem. The theorem implies that we can directly model Y on any MPDAG & and remarkably, the resulting augmented-G with Y remains an MPDAG consistent with the given background knowledge. This augmented graph enables various causal inference tasks.
Appendix B.2 Theorem [4. may
5

---

Published as a conference paper at ICLR 2024
4.2 IDENTIFICATION OF FAIRNESS CRITERIA
We denote the augmented MPDAG 9 = (V, E) with Y. where V = X A, by g" In this section, we discuss the identification of the causal quantity P(Ý y|do(A = a), do(Xad = x.d) in Equation (1 on G": when and how we can uniquely express such a causal quantity by the observable densities f(v) over and ((0lv) over g" We start with the general identification problem P(Y y|do(S = s)), where S S V.
Perkovic 2020 Theorem 3.6) establishes the condition and formula for the identification of causal effect P(Y yldo(S = s)) in an MPDAG G* with density f(v, 0). Here, under our modeling strategy on Y. we present such graphical condition over the MPDAG C and represent the identifica- tion formula based on ʃ(v) in 9 and f(ilv) in G in Proposition 4.1 We first provide the notion of partial causal ordering as a preliminary.
Partial Causal ordering Perkovic (2020). Let G (V, E) be an MPDAG. Since 9 may include undirected edges (-), it is generally not possible to establish causal ordering of node set V E V in G. Instead, a partial causal ordering, <, of v' of G is defined as a total causal ordering of pairwise disjoint node sets V.... Kk. h 1. U V₁ v' that satisfies the following condition: if V; Vj and there is an edge between V; E V, and V E Vj in G. then V; - Vú is in G.
Perkovic 2020) develops an algorithm for decomposing a set of nodes as partial causal orderings (PCO) in an MPDAG G. We provide it in Algorithm P in Appendix A which acts an important component for Proposition[4.1 4.1 We denote the parents of the node W graph g as pa(W.g).
Proposition 4.1. Let be a node set in an MPDAG g = ( E) and let V'= = V\S. Furthermore, let (V1,.., Vx) be the output of PCO(V,) The augmented-G with Ý is denoted as G" Then for any density f(v) consistent with and the conditional density [ūlvv entailed by G", we have
1. f(v. 0) = f(6lv) Avv.v (V)))
2. If and only if there is pair of nodes V e v' and S E S such that S V in G. f(v'ldo(s) and f(ū)do(s) are identifiable, and
s(v\ldo(s))= = π s(vilpa(v,,9))
(2)
ViEv'
f(Uldo(s)) f(ll))s(vv = f(ilv)
f(vilpa(v,. 9))dv' Visv'
π
(3)
for values pa( na(v1,9 9) of Pa(vsp v4, 9) that are in agreement with s.
The proof of Proposition 4.1 is based on Perkovic 2020 Theorem 3.6) and Theorem
The
detailed proof is provided Appendix B.3
Example. We provide a simple example to illustrate Proposition 4.1 Consider the MPDAG & and
g* in Figure Ic and Figure Id where g* is the augmented-9 G with Y. The partial causal ordering of
X U A on G is ({A), (X)) f f(x.a) a density consistent with G, g entails a conditional density f(ilx,a) a). Then, by Proposition 4.1 we have f(x, a, 9) f(ilx, (x(() in G". Since there
no pair of nodes and X X such that A X is G, we have [(x]do())) f(x (a) and
((ildo(a)) = f((lx. (x ad in G". For more example, please refer to Appendix C
Dealing with non-identiffcation. In cases where the causal effect of S on Ý is not identifiable, we can list MPDAGs corresponding to all valid combinations of edge orientations for edges V S, where V E v' and S E S. In this case, the causal effect in each MPDAG can be identified as unique functional relationship of the observable density. To address our constrained optimisation problem, we can replace the unfairness term in Equation (T) with the average of unfairness over different MPDAGs. The experimental analysis on unidentifiable cases is provided is Appendix(G.I1
Identification of P(Ý = y)do(A A = a), (o(X.c Xad) in the fairness context. Under the modeling technique that ý = (x a), Proposition 4.1 implies that the causal effect of A U X on γ is identifiable for given set of admissible attributes Xad X if and only if there is no

---

Published as a conference paper at ICLR 2024
pair of nodes X E U and V E VI(AU Xad) such that X V is in G. In such case, f()ldo(a) do(x f(llv) S(vilpa(v), 9))dv' for values pa( v1 9) of Pa(vi, that are in agreement with a and Xnd, where V VI(AUXad) (V1, Vm) = PCO(V', g).
4.3 SOLVING THE OPTIMISATION PROBLEM
Addressing the optimisation problem stated in Equation requires measuring the discrepancy between distributions p(-- y/ do = a, Xad = xad)) and P(Ý = y do = a Xad = xxa)).
Here, employ Maximum Mean Discrepancy (MMD) (Grettoon al., 2007), but other measures can also be utilized. On the other hand, as evident from the identification formula Equation (3), we need to estimate the stable conditional density f(v; [pa(vi, (ovv,)))) ()) and design the model to approximate s' /(ilv). However, computing the MMD of two distributions entailed by a model approximate the integrals involved intractable. As a result, resort Monte Carlo sampling in the identification formula. For convenience, we estimate f(vilpa(vi. 9)) using a conditional multivariate normal distribution, but other conditional density estimation approaches can also be employed. Then we generate the interventional data for under each intervention do( A a, X.d Xad). Finally, neural net can be trained for h(x, a). For more on the MMD formulation and its application in our context, please refer to Appendix
h(x, a)
4.4 APPLICABILITY TO OTHER CAUSAL FATRNESS NOTIONS
Causal fairness notions are defined on different types of causal effects, such as interventional fairness on interventional effects, path-specific fairness nested counterfactual queries, and counterfactual fairness on counterfactual effects. Their identifiability depends on the identifiability of these causal effects. Our proposed method is directly applicable other interventional-basee fairesss notions but not to path-specific causal fairness or counterfactual fairness due to the ongoing challenge of (nested) counterfactual identification over MPDAGs. For more details on the related fairness notions and applicability, please refer to Appendix
5 EXPERIMENT
In this section, we illustrate our approach on both synthetic and real-world datasets. We measure prediction performance using root mean squared error (RMSH) accuracy and assess interventional unfairness by MMD. Here, we focus on the scenario where the admissible variable set empty. Additional experiments involving non-empty admissible variable sets can be found Appendix [
Baselines. We consider three baselines: 1) Fuul 1 model makes predictions using all attributes, in- cluding the sensitive attributes, 2) Unaware model uses all attributes except the sensitive attributes, and 3) IFair r is model mentioned in Section 3.1 which makes predictions using all definite non- descendants of the sensitive attribute in MPDAG Our proposed method is e- IFair, which uses all attributes and implement the constrained optimization problem in Section 3.2
5.1 SYNTHETIC DATA
We first randomly generate DAGS with d nodes and s directed edges from the graphical model Erdös- Rényi (ER), where d is chosen from (5, 10, 20, 30) and the correspongding s is (8, 20, 40, 60). For each setting, we generate 10 graphs. For each DAG D', we consider the last node in topological ordering as the outcome variable and we randomly select one node from the graph as the sensitive attribute. The sensitive attribute can have two or three values, drawn from Binomial([O.1] 1)) or Multinomial((01..2)) distribution separately. The weight, S... of each directed edges X, - X, in the generated DAG, is drawn from a Uniform([-1, -0.1 -0.1]U[0.1. 1]) distribution. The synthetic data is generated according to the following linear structural equation:
X, =
Σ XxEM((X.)
B, +
(4)
"Proposition 4.1 and Theorem D.2 indicate that when the total effect of singleton A on Ý is identifiable in the augmented MPDAG g", the ancestral relationship between A and any other attribute is definite.
7

---

Published as a conference paper at ICLR 2024
where e; independent (N0, 1). Then generate sample with size 1000 for each DAG the observational data. The proportion of training, validation and test data is split as 8
We consider the DAG D over all of the variables, excluding the outcome. As the simulated DAG is known, the CPDAG can be obtained from the true DAG without running the causal discovery algorithms. Once we obtain the CPDAG C, where D [C]. we randomly generate the direct causal information S T as the background knowledge from the edges where S T is DAG D, while 5 T is in CPDAG C. Combining with the background knowledge that is necessary to identify fairness, we can obtain the corresponding MPDAG G. We show a randomly generated DAG D, the corresponding CPDAG C and MPDAG G example in Figure I0 see Appendix G.1
To measure the unfairness, we generate 1000 interventional data points XAta under different inter- ventions on A according to the identification formula. To approximate each term f(valp(( v; 9)) in the formula, we fit a conditional multivariate Gaussian distribution using observational data. The generation of V; is based the fitted density and follows the partial causal ordering. The propor- tion of training and validation for interventional data is split as 8 Besides, we generate 1000 interventional data from the ground-truth SCM for different interventions the sensitive attribute for test. Then we fit all models with the data. The in our optimisation problem is [0, 0.5, 5, 20, 60, 100]. For additional experiments on nonlinear structural equations and varying amounts of background knowledge, please refer to Appendix G.7 and Appendix G.8) respectively. We also ana- lyze the model robustness experimentally when the graph learnt by causal discovery algorithms in Appendix G.9 The model robustness on fitting of conditional densities is provide in Appendix G.
Results. For each graph setting, we report the average unfairness and RMSE achieved on 10 causal graphs in the corresponding trade-off plots in Figure 2 Obviously, both Full and Unawa re meth- ods exhibit lower RMSE but higher unfairness. The IFair method achieves nearly unfairness but at the cost of significantly reduced prediction performance. However, our (-IFa FiFair approach allows for a trade-off between unfairness and RMSE with varying A. For certain values X, we can even simultaneously achieve low unfairness comparable to IFair model and low RMSE com- parable to Full. Exemplary density plots of the predictions under two interventional datasets are shown in Figure 3 The degree of overlap in the distributions indicates the fairness of the predictions with respect to the sensitive attribute. The more the distributions overlap, the fairer the predictions considered to be. More discussion the eecuracy--airreee trade-off is included in Appendix
c-iaar Fal tooee
Full di c-fakk d (Pay Ureware
1.2
211
1.0
Firit
wdl
Unfaimass
Unbiimess
(a)
(a) 5nodes8edges.
(b) 10nodes20edges.
Usoware
RM0E
RMSE
122
(b)
1.15
0.055
0.010
B.115 Unfalmess
0.100
5.00
0.005
Unfa mess
4.500
0.017
Figure 3: Density plots of the predicted YA and YA-o' in synthetic data.
(c) 20nddex40edges.
(d) 30nodes60edges.
Figure 2: Accuracy faimess trade-off.
5.2
REAL DATA
5.2.
THE UCI STUDENT DATASET
Our first experiment with real-world data is based on the UCI Student Performance Data Set (Cortez & Silva, 2008), which contains information about students performance in Mathematics. The dataset consists of records for 395 students, with 32 school-related features. In this dataset, we consider the
"With ample sample size, existing causal discovery algorithms have demonstrated high accuracy in re- covering the CPDAG from simulated data Glymour et al. (2019.
8

---

Published as a conference paper at ICLR 2024
attribute sex the sensitive attribute. We create the target attribute Grade as the average of grades in three tests. Our experiments are carried out on the MPDAG g in Figure TIc Due to the space limit, Figure Tic is provided in Appendix G.2 For details graph learning, interventional data generation and model training, please refer to Appendix G.3
We measure interventional fairess and accuracy using a similar approach described in Sec- tion 5.1 The trade-off plot is shown in Figure 4a The model Full and Unaware exhibit higher unfairness. The model IFair achieves interventionally fairness at the cost of increased RMSE. On the other hand, our e-IFair model strikes a balance between unfairness and RMSE by tuning the values of A. Since the test only contains 19 interventional data for do(sex female) and 20 inter- ventional data for do(sex= = male). the unfairness measure may not be highly accurate. Therefore, we also provide the trade-off plot on the training set in Figure 44b where the unfairness approaches zero for the T r model and e- i-IFaix model with stricter penalties on unfairness. Furthermore, the distribution of predictions on the two interventional datasets follows similar trend as the syn- thetic data, as depicted in Figure 5
Fral p-Fair Faa Urowar
--Tar iTav
150
311-
7.8
(Fu)
(ürasone))
7 Ie-Fas A 255
255 16
5:20
2:24
0.22
0.00
0
Untaimess
5.04
0.06
Figure 5: Density plot of the predicted YA- and YA-a' in Student data.
(a) Test set.
(b) Train set.
Figure 4: Accuracy fairness trade-off.
5.2.2 CREDIT RISK DATASET
The task of credit risk assessment involves predicting the likelihood of a borrower defaulting on a loan. For our experiment, we utilize the Credit Risk Dataset, which contains 11 features related to the repayment capability of 32,581 borrowers. In this dataset, we consider the at- tribute Age as the sensitive attribute and the target variable is Loan_status, which is a binary variable indicating default (1) no default (0). We focus on two specific age groups: 23 and 30, representing the first and third quantiles, respectively. Our experiments are based on the MPDAG G in Figure 13a Due the space limit, it is provided in Appendix G.4 For details on graph learning, interventional data generation and model training, please refer to Appendix
G.5 G.5
Given that the target variable Loan stalus is bi- nary, measure unfaimess using the absolute difference in the means of predictions for the interventions on Age 23 and Age 30. Pre- diction performance is evaluated by accuracy. Since there no non-descendant of Age, we not have the model IFair x for this dataset. The trade-off plot presented in Figure 6aa and the distribution of predictions for the two interven- tional datasets depicted in Figure Both of them follow similar trend previous.
e-Fait
Y
0.175
1.0
Aequary
Prbbabiity
0.125
04
0.01
0.00
1.53
Unfaimess
Accuracy fairness trade-off.
(b) Histogram, where the for e-IFair model is 10 and 150, respectively.
Figure 6: Results on Credit Risk dataset.
6 CONCLUSION
This paper presents a framework for achieving interventional fairness on partially known causal graphs, specifically MPDAGs. By leveraging the concept of interventions and modeling fair pre- dictions as the effect of all observational variables, the proposed approach addresses the limitations of existing methods that assume a fully known causal DAG. Through the analysis of identification criteria and the formulation of constrained optimization problem, the framework provides prin- cipled approach to achieving interventional fairnsss while maximizing data utility. Experimental results simulated and real-world datasets demonstrate the effectiveness of the proposed frame- work. The limitation of this work is that assumes no selection bias or latent confounders. Future work can focus extending the proposed framework and addressing these challenges.

---

Published as a conference paper at ICLR 2024
7 ACKNOWLEDGEMENT
AZ was supported by Melbourne Research Scholarship from the University of Melbourne. This re- search was undertaken using the LIEF HPC-GPGPU Facility hosted the University of Melbourne. This Facility was established with the assistance of LIEF Grant LE170100200. SW was supported by ARC DE200101253, MG was supported by ARC DE210101624.
REFERENCES
Steen A Andersson, David Madigan, and Michael D Perlman. A characterization of markov equiv- alence classes for acyclic digraphs. The Annals of Statistics, 25(2):505-541, 1997.
Chen Avin, Ilya Shpitser, and Judea Pearl. Identifiability of path-specific effects. 2005.
Christopher M Bishop. Mixture density networks. 1994.
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.
Irene Chen, Fredrik Johansson, and David Sontag. Why is my classifier discriminatory? Advances in Neural Information Processing Systems, 31, 2018.
Silvia Chiappa. Path-specific counterfactual fairness. Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 7801-7808, 2019.
David Maxwell Chickering. Learning equivalence classes of bayesian-networf structures. The Journal of Machine Learning Research, 2:445-498, 2002a.
David Maxwell Chickering. Optimal structure identification with greedy search. Journal of machine learning research, 3(Nov):507-554, 2002b.
Yoichi Chikahara, Shinsaku Sakaue, Akinori Fujino, and Hisashi Kashima. Learning individually fair classifier with path-specific causal-effect constraint. In International Conference on Artificial Intelligence and Statistics, pp. 145-153. PMLR, 2021.
Alexandra Chouldechova. Fair prediction with disparate impact: A study of bias in recidivism prediction instruments. Big data, 5(2):153--63, 2017.
Diego Colombo, Marloes H Maathuis, et al. inderiindependen constraint-bard causal structure learning. J. Mach. Learn. Res., 15(1):344133782, 2014.
Paulo Cortez and Alice Maria Gonçalves Silva. Using data mining to predict secondary school student performance. 2008.
William Dieterich, Christina Mendoza, and Tim Brennan. Compas risk scales: Demonstrating ac- curacy equity and predictive parity. Northpointe Inc, 2016.
Sanghamitra Dutta, Dennis Wei, Hazar Yucksel, Pin-Yu Chen, Sijia Liu, and Kush Varshney. Is there trade-off between fairness and accuracy? a perspective using mismatched hypothesis testing. In International Conference on Machine Learning, pp. 2803-2813. PMLR, 2020.
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Proceedings of the 3rd innovations theoretical computer science confer- ence, pp. 214-226, 2012.
Marco Eigenmann, Preetam Nandy, and Marloes H Maathuis. Structure learning of linear gaussian structural equation models with weak edges. arXiv preprint arXiv:1707.07560 2017.
Zhuangyan Fang and Yangbo He. Ida with background knowledge. In Conference Uncertainty in Artificial Intelligence, pp. 270-279. PMLR, 2020.
Emily R Flanagan. Identification and estimation of direct causal effects. 2020.
10

---

Published as a conference paper at ICLR 2024
Sorelle A Friedler, Carlos Scheidegger, and Suresh Venkatasubrammniin.. The (im) possibility of fairness: Different value systems require different mechanisms for fair decision making. Commu- nications of the ACM, 64(4):136-143, 2021.
Sainyam Galhotra, Karthikeyan Shanmugam, Prasanna Sattigeri, Kush R Varshney, Rachel Bellamy, Kuntal Dey, et al. Causal feature selection for algorithmic fairnsss. 2022.
David Galles and Judea Pearl. Testing identifiability of causal effects. In Proceedings of the Eleventh conference on Uncertainty in artificial intelligence, pp. 185-195, 1995.
Clark Glymour, Kun Zhang, and Peter Spirtes. Review of causal discovery methods based on graph- ical models. Frontiers in genetics, 10:524, 2019.
Arthur Gretton, Karsten Borgwardtt Malte Rasch, Bernhard Schölkopf, and Alex Smola. A kernel method for the pasoamppepppoemm.....mm In Advances in neural information processing systems, pp. 513-520, 2007.
Richard Guo and Emilija Perkovic. Minimal enumeration of all possible total effects in a markov equivalence class. In International Conference on Artificial Intelligence and Statistics, pp. 2395- 2403. PMLR, 2021.
Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. Advances in neural information processing systems, 29:3315-3322 -323,, 2016.
Alain Hauser and Peter Bühlmann. Characterization and greedy learning of interventional markov equivalence classes of directed acyclic graphs. The Journal of Machine Learning Research, 13 (1):2409-2464, 2012.
Mitchell Hoffman, Lisa B Kahn, and Danielle Li. Discretion in hiring. The Quarterly Journal of Economics, 133(2):765-8))) 8006665--000000 2018.
Patrik O Hoyer, Dominík Janzing, Joris M Mooij, Jonas Peters, Bernhard Schölkopf. et al. Nonlinear causal discovery with additive noise models. In NIPS, volume 21, pp. 686-696. Citeseer, 2008
Patrik O Hoyer, Aapo Hyvarinen, Richard Scheines, Peter L Spirtes, Joseph Ramsey, Gustavo Lac- erda, and Shohei Shimizu. Causal discovery of linear acyclie models with arbitrary distributions. arXiv preprint arXiv: 1206.326000 2012.
Dmitriy Katz, Karthikeyan Shanmugam, Chandler Squires, and Caroline Uhler. Size of interven- tional markov equivalence classes in random dag models. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 3234-3243. PMLR, 2019.
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, pp- 2907-2914, 2019.
Amir Khandani, Adlar J Kim, and Andrew W Lo. Consumer credit-risk models via machine- learning algorithms. Journal of Banking & Finance, 34(11):777727877, 2010.
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.
Akhil Alfons Kodiyan. An overview of ethical issues in using ai systems in hiring with case study of amazon's 's ai based hiring tool. Researchgate Preprint, pp. 1-19, 2019.
Matt Kusner, Chris Russell, Joshua Loftus, and Ricardo Silva. Making decisions that reduce dis- criminatory impacts. In International Conference on Machine Learning, pp. 3591-3600. PMLR, 2019.
Matt J Kusner, Joshua Loftus, Chris Russell, and Ricardo Silva. Counterfactual fairness. Advances in neural information processing systems, 30, 2017.

---

Published as a conference paper at ICLR 2024
Yue Liu, Zhuangyan Fang, Yangbo He, and Zhi Geng. Collapsible ida: Collapsing parental sets for locally estimating possible causal effects. In Conference on Uncertainty in Artificial Intelligence, pp. 290-299. PMLR, 2020.
Marloes H Maathuis, Markus Kalisch, and Peter Bühlmann. Estimating high-dimensional interven- tion effects from observational data. The Annals of Statistics, 33333)) 2009.
Martinez and Bertran. Fairness with minimal harm: pareto-optimal approach for healthcare. NeurlPS ML4HI: Machine Leurning for Health, 2019.
Christopher Meek. Causal inference and causal explanation with background knowledge. In Pro- ceedings of the Eleventh conference on Uncertainty in artificial intelligence, pp. 403-410, 1995.
Aditya Krishna Menon and Robert C Williamson. The cost of fairesss in binary classification. In Conference on Faireess, Accountability and Transparency, pp. 107-118. PMLR, 2018.
Razieh Nabi and Ilya Shpitser. Fair inference on outcomes. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Preetam Nandy, Marloes H Maathuis, and Thomas S Richardson. Estimating the effect of joint interventions from observational data in sparse high-dimensional settings. 2017.
Judea Pearl. Probabilistic reasoning in intelligent systems: networks of plausible inference. Morgan kaufmann, 1988.
Judea Pearl. Causal diagrams for empirical research. Biometrika, 82(4))669-688, 1995.
Judea Pearl. Causality. Cambridge university press, 2009.
Judea Pearl and James M Robins. Probabilistic evaluation of sequential plans from causal models with hidden variables. In UAI, volume 95, pp. 444-453. Citeseer, 1995.
Judea Pearl et al. Models, reasoning and inference. Cambridge, UK: CambridgeUUniversstyprerss 19, 2000.
Emilija Perkovi, Johannes Textor, Markus Kalisch, Marloes Maathuis, et al. Complete graphical characterization and construction of adjustment sets in markov equivalence classes of ancestral graphs. Journal of Machine Learning Research, 18(220):1-62, 2018.
Emilija Perkovic. Identifying causal effects in maximally oriented partially directed acyclic graphs. In Conference on Uncertainty in Artificial Intelligence, pp. 530-539. PMLR, 2020.
Emilija Perković, Johannes Textor, Markus Kalisch, and Marloes H Maathuis. A complete gen- eralized adjustment criterion. In Proceedings of the Thirty-Firsl Conference on Uncertainty in Artificial Intelligence, pp. 682-691, 2015.
Emilija Perkovic, Markus Kalisch, and Marloes Maathuis. Interpreting and using cpdags with background knowledge. In Proceedings of the 2017 Conference on Uncertainty in Artificial In- telligence (UA12017), pp- ID-1120. AUAI Press, 2017.
Jonas Peters and Peter Bühlmann. Identifiability of gaussian structural equation models with equal error variances. Biometrika, 101(1):219-22) 2014.
Jonas Peters, Joris M Mooij, Dominik Janzing, and Bernhard Schölkopf. Causal discovery with continuous additive noise models. 2014.
Joseph Ramsey, Kun Zhang, Madelyn Glymour, Ruben Sanchez Romero, Biwei Huang. Imme Ebert-Uphoff, Savini Samarasinghe, Elizabeth A Barnes, and Clark Glymour. Tetrad-a toolbox for causal discovery. In 8th International Workshop on Climate Informatics, 2018.
James Robins. A new approach causal inference in mortality studies with sustained exposure cetiood-apliicattinn to control of the healthy worker survivor effect. Mathematical modelling, 1991 1986.
12

---

Published as a conference paper at ICLR 2024
Dominik Rothenhäusler, Jan Ernest, and Peter Bühlmann. Causal inference in partially linear struc- tural equation models. The Annals of Statistics, 46(6A):2904-29)) -9388, 2018.
Chris Russell, M Kusner, Loftus, and Ricardo Silva. When worlds collide: integrating different
counterfactual assumptions in fairness. In Advances in neural information processing systems, volume 30. NIPS Proceedings, 2017.
Babak Salimi, Luke Rodriguez, Bill Howe, and Dan Suciu. Interventional fairness: repair for algorithmic fairness. In Proceedings of the 2019 International Conference on Manage- ment of Data, pp. 793-80 230-800,55 2019.
Causal database
Richard Scheines, Peter Spirtes, Clark Glymour, Christopher Meek, and Thomas Richardson. The tetrad project: Constraint based aids to causal model specification. Multivariate Behavioral Re- search, 33(1):65-117, 1998.
Shubham Sharma, Yunfeng Zhang, Jesús Aliaga, Djallel Bouneffouf, Vinod Muthusamy, and Ra- mazon Kush. Data augmentation for discrimination prevention and bias disambiguation. pp- 358-364, 02 2020. doi: 10.1 10.1145/375527..37556.
Shohei Shimizu, Patrik Hoyer, Aapo Hyvärinen, Antti Kerminen, and Michael Jordan. A linear non-gaussian acyclic model for causal discovery. Journal of Machine Learning Research, 7(10), 2006.
Pater Spirtes, Clark Glymour, Richard Scheines, Stuart Kauffman, Valerio Aimale, and Frank Wim- berly. Constructing bayesian network models of gene expression networks from microurray data. 2000a.
Peter Spirtes and Clark Glymour. An algorithm for fast recovery of sparse causal graphs. Social science computer review, 911):62-72 1991.
Peter Spirtes, Clark N Glymour, Richard Scheines, and David Heckerman. Causation, prediction, and search. MIT press, 2000b.
Latanya Sweeney. Discrimination in online ad delivery. Communications the the ACM, 56(5)4444: 2013.
Yuhao Wang, Liam Solus, Karren Yang, and Caroline Uhler. Permutation based causal inference algorithms with interventions. Advances in Neural Information Processing Systems, 30, 2017.
Susan Wei and Marc Niethammer. The fairness pareto front. Statistical Analysis and Data Mining: The ASA Data Science Journal, 1 15(3):287-302, 2022. doi: https://doi.orr/// 1002/ sam.11560. URL https: htttss://oniineilin
11560
Michael Wick, Jean- can--Bapistte Tristan, et al. Unlocking fairess: trade-off revisited. Advances in neural information processing systems, 32, 2019.
Janine Witte, Leonard Henckel, Marloes H Maathuis, and Vanessa Didelez, On efficient adjustment in causal graphs. The Journal of Machine Learning Research, 21(1):996-10000, 2020.
Yongkai Wu, Lu Zhang, and Xintao Wu. On discrimination discovery and removal in ranked data ing causal graph. In Proceedings of the 24th ACM SIGKDD International Conference on Knowl- edge Discovery Data Mining, pp. 2536-2544, 2018
Yongkai Wu, Lu Zhang, and Xintao Wu. Counterfactual fairness: Unidentification, bound and algorithm. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial In- telligence, 2019a
Yongkai WI, Lu Zhang, Xintao Wu, and Hanghang Tong. Pe-fairness: A unified framework for measuring causality-basee fairness. Advances in Neural Information Processing Systems, 32, 2019b.
Samuel Yeom and Michael Carl Tschantz. Discriminative but not discriminatory: A comparison of fairness definitions under different worldviews. ArXiv, bhs//808.. 08619, 2018.
13

---

Published as a conference paper at ICLR 2024
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, pp. 3675-3685, 2018:t 8a.
Junzhe Zhang and Blias Bareinboim. Fairness decision-makingg-tue causal explanation formula. In Thirly-Second AAAI Conference on Artificial Intelligence, 2018b.
K Zhang and A Hyvärinen. On the identifiability of the post-nonlinear causal model. In 25th Conference on Uncertainty Artificial Intelligence (UAI 2009), pp. 647-655, AUAI Press, 2009.
Lu Zhang and Xintao Wu. Anti-discrimination learning: a causal modeling- based framework. In- ternational Journal of Data Science and Analytics, 4(1):1-16, 2017.
Lu Zhang, Yongkai Wu, and Xintao Wu. A causal framework for discovering and removing direct and indirect discrimination. In Proceedings of the Twenty-Sixte International Joint Conference on Artificial Intelligence, 2017.
Lu Zhang, Yongkai Wu, and Xintao Wu. Causal modeling-based discrimination discovery and re- moval: criteria, bounds, and algorithms. IEEE Transactions on Knowledge and Data Engineering, 31(11):2035-2050 2018.
Han Zhao and Geoff Gordon. Inherent tradeoffs in learning fair representations. Advances in neural information processing systems, 32, 2019.
Indre Zliobaite.
On the relation between accuracy and fairness in binary classification. In The 2nd workshop on Fairness, Accountability, and Transparency in Machine Learning (FATML) at ICML' 15, 2015.
Aoqi Zuo, Susan Wei, Tongliang Liu, Bo Han, Kun Zhang, and Mingming Gong. Counterfactual fairness with partially known causal graph. In Advances in Neural Information Processing Sys- tems, 2022.
14

---

Published as a conference paper at ICLR 2024
Appendix
Table of Contents
A Preliminaries
15
A.1 Existing Results
16
B Detailed proofs
18
B. Proof of Lemma 3.1
18
B.2 Proof of Theorem
18
B.3 Proof of Proposition
20
C An illustration example for Proposition 4.1
21
D Fairness under MPDAGs as a graphical problem
22
D.1 Identifying ancestral relations an MPDAG
22
D.2 Additional identification results
23
MMD in the fairness context
24
Applicability other fairness notions
24
Supplementary experimental results
26
Causal graphs for one simulation
26
G.2
Causal graphs for the UCI Student Dataset
................................
27
G.3
More experimental details the UCT Student Dataset
27
G.4
Causal graphs for the Credit Risk Datasel
29
G.5
More experimental details the Credit Risk Dataset
29
G.6
Experiments involving non non-empty admissible variable set
31
G.7
Experiments based
complicated structural equations
31
G.8
Experimental analysis model performance with varying amount of given do- main knowledge
31
G.9
Experimental analysis on model robustness causal discovery algorihhms
32
G. 10 Experimental analysis model robustness conditional densilies approximation
33
Experimental analysis model performance unidentifiable cases
33
H
Additional related work causal effect identification on MPDAGS
34
Discussion on accuracy-fairnes trade-off
35
A PRELIMINARIES
Graph and Subgraphs. Let G (V, E) denote a graph, where V (X,,... X,,) represents set of nodes (variables) and E represents a set of edges. In our consideration, the graphs can include both directed (-) and undirected (-) edges, with at most one edge allowed between any two nodes. An induced subgraph of G denoted by Gy = (V', E') is subgraph where V s V and E' E where E' consists of all the edges in E that connects nodes in V
Path. In the graph G, a path p from S to T is defined as a sequence of distinct nodes (S. T) where each consecutive pair of nodes is connected by an edge. Let p (S Vo. ..., Ve T) represents a path in graph G. we say p is a causal path from S to T if the direction of the edges follows a pattern V; Vi+1 for all 0
1. On the other hand, if no edge V, V44 exists in G, then p
15

---

Published as a conference paper at ICLR 2024
is a possibly causal path from S to T. If there exists edge V; Vi+1 in G, p considered a non- causal path in G. A cycle in the graph can be categorized as a causal cycle, possibly causal cycle, or whether it represents causal, possibly causal, non-causal path
non-causal cycle, depending from a vertex to itself. A path from S to is said to be proper with respect to only its first node member of S.
Colliders, Skeleton and Pattern. If, a path = (X Vo....,VV = Y), there exists a node V; such that V V2 and Vú Vi+1. then we say V3 is collider on the path p. If V and Vi+1 are not adjacent, then the triple (V--1, V,, Vi+1) is called a v-structure collided on V,, and V22 can be called unshielded collider. For a graph G, the skeleton of the undirected graph obtained by replacing the directed edges in & with undirected edges. The skeleton of 9 with unshielded colliders the skeleton of G with the edges resulting unshielded colliders directed.
MPDAGs Construction. Algorithm mentioned in (Perkovic et al. 2017) summarizes, the process of constructing the maximal PDAG g' from the given maximal PDAG g and backgroud knowledge B. This construction utilizes Meek's s rule shown in Figure 7 Specifically, the background knowledge is assumed to be the direct causal information
the form 5 - T, indicating that a direct cause of T. If Algorithm does not return FAIL, then implies that the background knowledge B and returned maximal PDAG G' are consistent with the input maximal PDAG g.
Algorithm Construct MPDAG (Perkovic et 2017 Meek 1995
1: Inputs: MPDAG G and Background knowledge B.
2: Output: MPDAG G' or FAIL.
3: Let G' 9:
4: while B # Ø do
5: Select an edge (S T} in B;
6: B = (S - T);
7:
if (S - 7 OR (S - T} is in G' then
8:
Orient (S - T in g':
9:
Orienting edges in G' following the rules in Figure until edge be oriented;
10:
else
FAIL;
R1
R2
Figure 7: Meek's 's orientation rules: RI, R2, R3 and R4 (Meek 1995). In each rule, if the graph on the left-hand side an induced subgraph of a PDAG G, the undirected edge that subgraph should be oriented according to the direction indicated on the right-hand side.
Undirected Connected Set. In graph G, set of nodes S is considered undirected connected set, if for any two distinct nodes S; and 5, in S, there exists an undirected path from S, to S in g.
Bucket. Let D be node set in an MPDAG (V,E). If B is maximal undirected connected subset of D in G, we call B a bucket D.
A.1 EXISTING RESULTS
Lemma A.1. (Perkovic et al. 2017 Lemma B.1) Letp (V1..., Vi.) be b-possibly causal definite status path in an MPDAG G. there is node E (1, n 1} such that V, Vi+1, then p V,, Vi)) is a causal path in g.
In some paper, the skeleton of DAG D with unshielded colliders is also called the pattern of D.
16

---

Published as a conference paper at ICLR 2024
Lemma A.2. Perkovic et al. 2017 Lemma 3.6) Let S and T be distinct nodes in MPDAG g. p is b- boposibby causal path from to in G, then a subsequence p of p forms b b-possibly causal unshielded path from S to T in G.
Corollary 3.4) Let D be a node set in an MPDAG G E.. Then there is unique partition D into B Bi.... Bk & z 1 in 9, where Bi...., Bx are buckets in G. That is
Corollary A.1 (Bucket Decomposition). (Perkovic 2020
= U... Bj, and
B Ø. i,j E {1....,k} # j. and
B, a bucket in for each E {1, (......k.. k).
Lemma A.3. (Perkovic 2020 Lemma 3.5) Let D be node set in MPDAG G = (V, E) and let
(B1,... Bk), k 2 1, the outpul of PC D 9) which presented in Algorithm 2 Then for each
i,j E (1, k), B; and Bj buckets in D and if j. then B; < Bj in G.
Algorithm Partial causal ordering (PCO) (Perkovic 2020 Algorithm 1)
1: Inputs: Node set in MPDAG G = (V,E), E).
2: Output: An ordered list B (B,,... Bx), k z of the bucket decomposition of D in g.
3: Let ConComp be the bucket decomposition of V in G;
4: Let ConComp be an empty list;
5: while B # Ø do
6: Let C ConComp:
7: Let C be the set of nodes in ConComp that are not in C;
8: if all edges between C and are into in G then Remove C from ConComp:
9:
10:
Let B = CUD;
11:
if B. Ø then
12:
Add B, to the beginning of B;
Perkovic (2020) introduces a necessary criterion, referred to as amenability by (Perković et al, 2013 Perkovic al. 2017). for the identifiability of causal effects in MPDAGs. This criterion is summarized in Proposition A.I
Proposition A.1. (Perkovic 2020
Proposition 3.2) Let X and Y be disjoint node sets in MPDAG g = (V, E). If there proper possibly causal path from X to Y that starts with an undirected edge in G. then the causal effect of X on Y is not identifiable in G.
In
Perkovic (2020), it is shown that the condition stated in Proposition A. is not only necessary, but also sufficient for the identification of causal effects in MPDAGs. This result is established in Theorem A.
Theorem 3.6) Let X and Y be disjoint node sets in an MPDAG G = (V, E). If there is no proper possibly causal path from X to Y in that starts with an undirected edge, then for any density f consistent with we have
Theorem A.1. (Perkovic 2020
S [bbilpa(b, 9))db 1=1
[(yldo(x))
for values pa(b; 9) of Pa(b; 9) that are in agreement with x, where (B,, B₂) Fco(An( Y, (vix).9) and An( (v.
Corollary A.2 (Factorization and truncated factorization formula MPDAGs). (Perkovic 2020 Corollary 3.7) Let X be a node set in an MPDAG g = (V, E) and let V V\.. Furthermore,
let (V V..,, Vx) be the output of Pco(V,) Then any density f consistent with G we have
1. f(v) = Ivvvv f(vilpa(v...9)
2. If there is no pair of nodes V E v and X E X such that X - V is in G. then f(v'ldo(x))
π f(vilpa(v,, g))dv'
V,ev
17

---

Published as a conference paper at ICLR 2024
for values pa(vi. 9) of Pa(v;,9 9) that are in agreement with x.
Property (Katz al., 2019 Property If node involved any the four Meek rules and if the node does not have an outgoing edge in the original causal DAG, then the oriented edge (in the right hand side of any of the four rules Figure 7 is incident v.
Theorem A.2 (Orientation completeness). (Meek 1995 Theorem 3) The result of applying rules RI, R2 and R3 in Figure to a pattern of a DAG is CPDAG.
Theorem A.3 (Orientation completeness w.r.t background knowledge), (Meek) 1995 Theorem 4) Let be a set of background knowledge consistent with a pattern of a DAG. The result of applying rules RI, R2, R3 and R4 (and orienting edges according B) the pattern is an MPDAG with respect to B.
B DETAILED PROOFS
B.1 PROOF OF LEMMA 3.1
Proof. Let W be any non-descendant A in G. Then P(W do A a)) = P(W]do(A = d')) = P(W) (according the Rule of the do-calculus (Pearl 2009)). Since A-a and WA-a' have the same distribution, for any sensitive attribute, the distribution of Y as function of the non- descendants of A and the intervened admissible variable X is invariant.
B.2 PROOF OF THEOREM 4.
According to the definition of MPDAG, G can be induced from the Markov equivalence class of DAG D (V, E) with background knowledge B. By exploring Meek's rules, specifically, Property 1. we show that 9 is an MPDAG that can be derived from the DAG 'D* with background knowledge B U (V- - ÝIV E V). We provide the details in checking with Meek's rules in this section.
B.2.1 TECHNICAL LEMMAS
In this section, we introduce some lemmas that useful in the proof of Theorem 4.1
Lemma B.1. For a DAG D EV, let D* be the augmented-D with Ý. The CPDAG of D and D' are denoted as C and C*, respectively. Then, compared with C, newly directed edges in C* only contain V y y for some V E V.
Proof. As discussed in Meek Meek (1995). deducing the CPDAG from DAG consists of two phases:
Phase I. Find the skeleton of the DAG with unshielded colliders.
Phase II. On the returned graph by phase I, orient every edge that can be oriented by suc- cessive applications of Meek's rules RI, R2 and R3.
So here, before identifying the difference between two CPDAGs and C*, we first identify the difference between two skeletons with unshielded colliders K. and K",, where K. and K are the corresponding skeletons of the DAG and D* with unshielded colliders, respectively.
Phase I. Compared with D, the new v-structures in D* are edges in (V + ÝiV e V) that form unshielded colliders on ÿ. Therefore, it is obvious that compared with IC, the newly directed edges in K are edges in {V - ÝIV E V) that form unshielded colliders on Y in D".
Phase II. Suppose the application of Meek's rules to IC results the CPDAG C. Next, apply Meek's rules on K." Since the application Meek's 's rules checks one edge per time, orienting edges on K.* equivalent the following recursive two-step procedure:
S1. Check and orient edges that be oriented between any V V:
18

---

Published as a conference paper at ICLR 2024
S2. Check and orient edges that can be oriented between any V E V and Y on the returned partially directed graph from the step SI;
S3. Go to SI until more edges can be oriented.
Clearly, compared with the CPDAG C oriented from K. newly directed edges in C* only contain V - Y for some V E V if and only if any directed edge in C. gets directed in C* and the step SI, S2 and S3 in the above does not orient more edges except V - Y for some V E V compared with C.
We first prove that all directed edges in C get directed in C* by step S1 and step S1 cannot orient more edges except V - Y for some V E V compared with C. Suppose that the CPDAG C is obtained by applying Meek's rules on IC in the sequence seq. We denote the partially directed acyclic graph obtained by applying Meek's rules in the same sequence seq on K. C* J. Since the induced subgraph K over is exactly the graph K. therefore, the induced subgraph of K over V will be oriented exactly as the CPDAG C. Then we check the possibility of the further orientations
on edges between any V E V considering the edge directions between any V E V and Y Property 1. implies that no more edges between any V V can be oriented. The returned partially directed acyelic graph from this step is C²,, 7. Properry 1. also implies that step S2 does not orient more edges except V Y for some E V compared with C. The returned partially directed acyclic graph from step S2 is denoted as C* 1/- Then we move onto step S3 and show that no more edge can be oriented in C*1 1/ any more. Due to the same reason as in step S1 that there is no edge directed out of Y in D", no more edges between any V E V can be oriented. Therefore, the application of Meek's rules on KC* stops here. According to the orientation completeness presented in Theorem A.2 the returned graph C* II is exactly the CPDAG C
Lemma B.2. For DAG D (VV,), let D* be the augmented-D with Y. C and C* be the CPDAG of D and D", respectively. Given additional background knowledge Be that is consistent with C. we denote the returned MPDAG as G when applying Algorithm Don C and Be and as G when applying Algorithm on C* and Be. Then, compared with G, newly directed edges in G" only contain V Y for some E V.
Proof. The proof is similar to the proof of Lemma B.1 According to Lemma B.1 compared with C, the newly directed edges in C* only contain V Y for some V E V. The application of Algorithm|| [ to and Be results the MPDAG G. Next, we apply Algorithm on C* and Be. Since the application of Meek's 's rules checks one edge per time, orienting edges on C* is equivalent to the following recursive two-step procedure:
S1. Check and orient edges that can be oriented between any V E V;
S2. Check and orient edges that can be oriented between any V e V and Ý on the returned partially directed graph from the last step;
S3. Go to SI until no more edges can be oriented.
Clearly, compared with the MPDAG G oriented from C. given the background knowledge Be, newly directed edges in G* only contain V - Y for some V E V if and only if any directed edge in G gets directed in G and the step S1, S2 and S3 in the above does not orient more edges except V - y for some V E V compared with G.
We first prove that all directed edges in & get directed in g by step SI and the step S1 cannot orient more edges except V + Ý for some V E V compared with G. According to Lemma B. the induced subgraph of C* over V exactly the same as the graph C. Suppose that the MPDAG g is obtained by applying Meek's rules on C with the sequence seg. We denote the partially directed acyclic graph obtained by applying Meek's rules with the same sequence seq on C" as G" Since the induced subgraph of C* over V is exactly the graph C, therefore, the induced subgraph of C* over V will be oriented exactly as the MPDAG G. Then we check the possibility of the further orientation on edges between any V V with considering the directions between any V E V and Y. Property 1. implies that more edges between any V E V can be oriented. The returned
19

---

Published as a conference paper at ICLR 2024
partially directed acyclic graph from this step is g Property 1.
also implies that step S2 does not orient more edges except V - Y for some V E V compared with G. The returned partially directed acyclic graph from step S2 is denoted as 9" Then we move onto step S3 and show that more edge can be oriented in 9 r any more. Due to the same reason in step S1 that there is no edge directed out of Y in D'' more edges between any V V can be oriented. Therefore, the application of Meek's 's rules on C* stops here. According to the orientation completeness presented in Theorem A.3 the returned graph 9 II is exactly the MPDAG
Lemma B.3. For DAG D (V, let D* be the augmented-D D with Y. C and C* be the CPDAG of DD and D*, respectively. Given additional background knowledge Be that is consistent with C, we denote the returned MPDAG 9 when applying Algorithm 7 on C and Be. Given the additional background knowledge Be Bc (V YIV V) that is consistent with C", the corresponding MPDAG is denoted as g Then, the MPDAG G" is exactly the augmented-G.
Proof. Algorithm| D can be used to construct the MPDAG from the CPDAG and background knowl- edge, by leveraging Meek's rules. Since Algorithm I checks one background knowledge per time, applying Meek's 's rules to C* and Be. is equivalent to the following two-steps procedures:
S1. Select the background knowledge in B& and check and orient every edge that can be ori- ented in C". The returned partially directed graph is denoted as g",
S2. Select the background knowledge in {V ÝIV V) and check and orient every edge that can be oriented on g",
After the step S1, according to Lemma B.2 compared with G, newly directed edges in g*, only contain V Y for some V V. Then we will show that in the step S2, after orienting V for any V V C* 1, no more edges in V v' for any V, V E V can be oriented.
According to Property I. since there is no such edge directed out of Ý in DV, no more edge between any V V can be oriented. According to the orientation completeness presented in Theorem A.. the returned graph from this step is the MPDAG g", which exactly the augmented-g defined by Definition 4.1
B.2.2 PROOF THEERRE
Proof. Figure 8 shows how all lemmas fit together to prove the Theorem 4.1 Suppose the MPDAG can be constructed from the Markov equivalence class of the DAG D (V. E) with the back- ground knowledge B. Denote the augmented-D with Y by D* and the augmented-G with Y by g*. Following from Lemma B.1 Lemma B.2 and Lemma B.3 we can see that G* can be constructed
from the Markov equivalence class of the D* with the background knowledge Bu(V ÝIV E V} by leveraging Meek's rules. Therefore, the graph G* is still an MPDAG and D* E [[]]].
Lemma B.1
Lemma
B
Lemma
Theorem 4.1
Figure 8: Proof structure of Theorem 4.1
B.3 PROOF OF PROPOSITION
We first show in Proposition B.I sufficient and necessary condition and the formula for the identi- fication of P(ý = y| do s)) in an MPDAG g" based on the consistent density f(v.g). Then, utilizing the relationship between the MPDAG G and g* we derive Proposition 4.1
B.3.1 TECHNICAL LEMMAS
Proposition B.1. Let S be a node set in an MPDAG G (V,E) and let V = V\S. Furthermore, let (V1, (V1...., Vw) be the output of PCO(V, 9) The augmented-g with node is denoted as g" Then for any density f(v, ū) consistent with g", have
20

---

Published as a conference paper at ICLR 2024
1. f(v.0) f(ilv) fvv.vv f(vilpa(vi.
2. If and only if there is no pair of nodes V E v' and S E S such that S - V in g*, f(v'l and f())do(s) are identifiable, and
[(vldo((s)
N [(vilpa(vI,9")) V,EV'
f(āldo(s)) S [(Gl))((vV(d(())) f(olv)
f(vilpa(v; 9"))d'
vivv
for values pa( G*) of Pa(vi, 9*) that are in agreement with s.
Proof. Since in the MPDAG g*, there is the directed edge V - y for any V E V, the output of PCO (VUY, g*) is (V,, .... Vx, 8). The parent of is v. The first statement then follows from the first statement in Corollary A.2
For the second statement, PCC( (n((V,, 9 " PCC(VV ("")). We first prove the sufficiency. That there is pair of nodes V V' and S such that 5 V is in the MPDAG G means $ and V cannot be in the same bucket. Therefore, some of the buckets Vi. i E (I,..., in the bucket decomposition of V will contain only nodes in S. Hence, obtaining the bucket decomposition of V is the same as leaving out buckets Vi that contain nodes in S from VI...., Vk. Following from Then [v, f'vvilpa(v,,))
Theorem A.1 when taking Y V', we have s'v') ((v)) ((ildo(s)) can be identified directly. Next, we show the necessity. According to Proposition A.1 the necessary condition for f(v' (do(s)) ((v) to be identifiable is that there is no pair of nodes V E V and S E S such that 5 V in G" The necessary condition for /($ do(s)) to be identifiable is that there is no proper possibly causal path from S to Ý that starts with an undirected edge in G* Since V Y for any V V, this necessary condition equivalent to the condition that there is no proper possibly causal path from S to V' that starts with an undirected edge in g". This completes the proof of Proposition
B.3.2 PROOF OF PROPOSITION 4.1
Proof. For any density ʃ(v) consistent with the MPDAG G, there exists a DAG D E [G] such that f(v) is consistent with D. Then the density f(v, g) factorized as (v. f(ilv)((v) is consistent with the DAG augmented-D with Y, denoted by D*. Theorem 4.1 implies that f(v, 9) consistent with the MPDAG augmented-G with Y. denoted by g" Therefore, two statements in Proposition B.1 applies here. Besides, we have f(v; ((vi/pa(vin, (vi, g" )) f(v;:l/(vv,.v 9)) for any Vi S V ; if there is no pair of nodes V E V and S S such that V in g", there is pair of nodes V v' and S S such that S V is in G. Modifying the condition for second statement in Proposition B.1 and replacing fVvilpa(v;, (v, g*)) with (vvilpa(v;. leads to Proposition 4.1
C AN ILLUSTRATION EXAMPLE FOR PROPOSITION 411
Consider the MPDAG g (V, E) in Figure 9a where V (A..B.CD..ERR,,,...,.
Figure 9b is the augmented-g with Y, denoted as g* The partial causal ordering of V on G is {[B, C}, E), (M, L}, (D), (D). (N). f(v) is density consistent with g and g" entails a conditional density f(ilv). Then, by Proposition 4.1, we have f(v. [(Vl))((naa m,l, (), (rle) (ddb,)))(m)) (m,,)))))) (),,,))((())) in g². Let V/s. Since there is no pair of nodes S E S and V E V such that S V is in g, we have f(v'ldo(s) = f(nla, m, (ddbb (),(,) c) and f()ldo(s) ((ll)))( m. (twpmm/me.///ttee
F) and V
c)dv in gn
21

---

Published as a conference paper at ICLR 2024
A
E
L
B
E
R
M
R
N
(a) MPDAG
(h) MPDAG g"
Figure 9: (a) is an MPDAG 9: (b) is the extended-g with y, denoted as g".
D FAIRNESS UNDER MPDAGS AS A GRAPHICAL PROBLEM
In this section, first review the graphical criterion and algorithms presented in Zuo et al. (2022) for identifying ancestral relations in an MPDAG, Then as complementary finding to (Zuo et al, 2022 Proposition 5.2), present sufficient and necessary graphical criterion that establishes the condition under which any ancestral relationship with regards to a specific vertex in an MPDAG can be definitively determined.
D.1 IDENTIFYING ANCESTRAL RELATIONS AN MPDAG
We first clarify the types of ancestral relations in an MPDAG. With respect to a variable S, a variable can be either
definite descendant of S if is descendant of S in every equivalent DAG,
definite non-descendant of S if T is non-descendant of S in every equivalent DAG, possible descendant of if T neither definite descendant nor definite descendant of S.
Perkovic et al. (017) state that T a definite non-descendant of S in an MPDAG g if and only if there is no possibly causal path from S to T in G. Zuo et al. (2022) propose a sufficient and necessary graphical criterion to identify whether is definite descendant of S in an MPDAG in
Theorem D.I
We first introduce some terms as a preliminary. In the graph 9, a chord path refers to any edge that connects two non-consecurive vertices the path. Conversely, chordless path is path that does not contain any such edges. A graph is considered complete if every pair of distinct vertices in the graph is adjacent each other. Consider MPDAG denoted G. Let S and T represent two distinct vertices in G. The critical ser of S with respect to in G consists of all adjacent vertices of S that lie at least one chordless, possibly causal path from S to T.
Theorem D.1. (uo et al. 2022 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 T in Then only if either S has definite arrow into C, that is C (h(S,00 g) # Ø, or S does not have definite arrow C but non-empp and induces an incomplete subgraph of G.
definite descendant of S if and
Based on Theorem D.I Zuo et al. (2022) propose Algorithm 3 to identify the type of ancestral
relation between two vertices. The set of definite descendants, possible descendants and definite non-descendants of the sensitive attribute can be identified by leveraging Algorithm 3 on each pair of sensitive and any other attribute. this way, we can select the definite non-descendants to make a counterfactually (and also interventionally) fair prediction
both definite non-descendants and
22

---

Published as a conference paper at ICLR 2024
possible descendants of A to increase the prediction accuracy the cost of a violation of counter- factual (and also interventional) fairness.
Algorithm 3 Identify the type of ancestral relation of S with respect to T in an MPDAG (Zuo al.
2022 Algorithm 2)
1: Input: MPDAG G. two distinct variables S and g.
2: Output: The type of ancestral relation between S and T.
3: Find the critical set C of S with respect to T in G by Algorithm
4: if [[C]= then
5: return I is a definite non non-descendant of S.
6: if S has an arrow into C C induces an incomplete subgraph of g then
7: return T is definite descendant of S.
8: return is a possible descendant of S.
Algorithm Finding the critical set S with respect to T in an MPDAG (Zuo et al. 2022 Algo-
rithm 1)
1: Input: MPDAG G, two distinct vertices S and T in G.
2: Output: The critical set of S with respect to T in G. 3: Initialize C = Ø, waiting queue Q []. and a set H. Ø
4: for a E sib(S) U ch(5) do
5: add S, to the end of Q,
6: while 2 Ø do
7:
take the first element (a,, o, r) out of Q and add it to Hi
8: i T then
9:
add to C, and remove from S all triples where the first element is oç
10: else
11:
for each node B in G do
12:
if + 3 or - then if or o not adjacent with or is the endnode then if B and S are not adjacent then
14:
if (a, T, 3) $ H. and (a, T, () $ then
16:
add (a, T, 3) to the end of Q,
17:
return C
D.2 ADDITIONAL IDENTIFICATION RESULTS
In Zuo et al. (202)), the authors discuss that the root node case (when the sensitive attribute do not have any parent in MPDAG), any ancestral relationship between the sensitive attribute and other attribute is definite in an MPDAG. Here, we claim that the root node assumption is sufficient but necessary and provide complete graphical criterion under which any ancestral relationship with regards to specific vertex is definite on an MPDAG in Theorem D.2
We first introduce a technical lemma Lemma D.I that useful the proof Theorem D.2
Lemma D.1. Let X and W be two distinct vertices in an MPDAG g (V.E), The ancestral relationship between X and W is definite if there is no proper chordless possibly causal path from X W in G that starts with undirected edge.
Proof. Suppose for contradiction that W is possible descendant of A. then there is possibly causal path p from to W. By Lemma A.2 a subsequence p of p forms a chordless possibly causal path from A to W. Suppose p (A Vo..., V/2 = W). As there is no proper chordless possibly causal path from A to W starts with undirected edge, node A must be directed towards Vi A Vi. By Lemma A.1. p" is causal path from A W in G. Therefore, W is definite descendant of A. The ancestral relationship between X and W is definite.
Theorem D.2. Let be a vertex in an MPDAG G (V, E). The ancestral relationship between A and any other vertex definite if and only there are undirected edges connected A in G.
23

---

Published as a conference paper at ICLR 2024
Moreover, an arbitrary attribute W is definite descendant of A if and only there is causal path from to W in G.
Proof. First, we prove the sufficiency. there no undirected edges connected to A in an MPDAG G, for any vertex W, there is no proper chordless possibly causal path from A to W that starts with an undirected edge. According to Lemma D.I] the ancestral relationship between and any other vertex is definite. Next, we prove the necessity. If there is an undirected edge connected to A, such as A W. in G. then there exists a DAG D1 [9] with A < W so that W is the non-descendant of A in D1. Meanwhile, there exists DAG D2 E [9] with A - W so that W is the descendant of in D2, In this way, the ancestral relationship between and the vertex W is not definite.
E MMD IN THE FAIRNESS CONTEXT
The MMD (Maximum Mean Discrepancy) is used measure the distance between two data distri- butions. It is accomplished by mapping each sample to Reproducing Kernel Hilbert Space (RKHS) using the kernel embedding trick firstly and then comparing the samples using a Gaussian kernel. In our context, let ýa (ih, Va and Ya = (ia...,
....,,. 0x'') be the prediction of the samples under intervention do( A a, Xad xad) and do A a', X Xud), respectively, where N₂ and Na' are number of the generated interventional samples under two interventions respectively. Then we can express the MMD" between predictions across different interventions as
N
MMD ($.: )
(1a))
x
N
No.
where sp-) represents the mapping function to RKHS. After substituting the kernel functions for the inner products, then the squared MMD is:
N N
N
N N N.
1
k(Ga
(N,)²
(N
where k-(-) is kernel function. The widely used one is the Gaussian RBF kernel k(x, expp( 1 11²), with bandwidth o.
F APPLICABILITY TO OTHER FAIRNESS NOTIONS
Our proposed method is directly applicable to other interventional-based fairness notions, such as ones defined on total effect (TE) and controlled direct effect (CDE) (Pearl 2009) and no proxy discrimination (Kilbertus et al.) 2017). this section, we provide a detailed review of the related fairness notions and examine the applicability teria to these notions. Similar to the main text, let A, Y and X represent the sensitive attributes, outcome of interest and other observable attributes, respectively. The prediction of Y is denoted by Y. Besides, as in Section 4.2 we denote the augmented MPDAG G (V,E) with Ý, where V X A, by G* TE of on Ý corresponds when X no pair of nodes A A and V VÍA such that A V in G. CDE of A on Y corresponds to X,, = X. is always identifiable under our modeling strategy The causal query no proxy discrimination, p( do p)), where P is the proxy, corresponds to A = P and Xad = Ø.
inapplicability of the proposed identification cri-
identifiable if and only
More specifically, we start with the total causal effect (TE), which is defined as follows: Definition F.1 (Total causal effect). (Pearl 2009 The total causal effect of the value change of A from to a on y ÿ is given by
TE a') P( Oldo = a)) -P =]
"This meets CDE identification criterion an MPDAG proposed hy Flanagan 2020
Theorem 5.4).
24

---

Published as a conference paper at ICLR 2024
The faimess criterion defined total causal effect claims that the prediction Y is fair with spect the sensitive attribute A if P(Ý ū]do{A a)) P( d = a')) holds for all possible values of ý and any value that A can take. This notion corresponds to the no- tion of interventional fairness where Xad = Ø. Under the proposed modelling technique on Y. Proposition 4.1 implies that the term P(Y = dl = a)) is identifiable if and only if no pair of nodes E A and V E V\A such that A V in G. In this case, total causal ef- fect can be expressed as f((ldo(a)) (V Vm) PCO(V', with pa(vi; (vi, 9) representing values of Pa(vi, g) that agree with Definition E.2 (Controlled direct causal effect). (Pearl 2009) The controlled direct effect of the value change of A from a to a on Y = ÿ. while fixing all the other variables X to x is given by
f(lvv) lv,sv ((vilpa(vi, 9))dv' where V = V|A,
CDE(a, p( i) = a, X = x)) p( = =jldo(A A = a', x xx).
The fairness criterion defined on controlled direct causal effect claims that the prediction V is fair with respect the sensitive attribute A if P( ýldo(A a, X x)) = P( i]do(A a' X x)) holds for all possible values of ÿ and any value that A and X can take. This notion corresponds to the notion of interventional fairness where Xud X. Propositioo 4.1 implies that it always identifiable under our modeling strategy and is given by f()ldo(a), do( x)) f(lla, x).
Definition F.3 (No proxy discrimination). (Kilbertus et al. 2017) A predictor y exhibits no proxy discrimination based on the proxy P for any value that P can take,
p(Ý- ý dP p)) p(Ý = =oldoPP=
This fairness criterion corresponds to the interventional faimess where A = P and Xad = Ø. Under the proposed modelling technique on Ý, Proposition 4.1 implies that the term P(ř ildo(P= p)) is identifiable if and only if there exists no pair of nodes P E P and V E V\P such that P - V is in G. In this case, the causal query ff (() can be expressed as f(oldo(p))
J f((lv) Tv,,sv f(vilpa(vr vi, g)),'' where V = V(P, (V Vm) PCO(V', 9), with pa(v;.9) representing values of Pa(v;,9, 9) that agree with p.
Definition F.4 (Path-specific causal effect). (Avin et al. 2005) Given causal path set n, the m-- specific effect of the value change of A from a to a on Y = - through π is given by
(a, = P(ý dl A al|m), do al - P( Oildo( A a)),
where p(Ý ūldo(A = al|=), do A = a) represents the post-intervention distribution of Y where the effect of intervention do( a') is transmitted only along æ while the effect of interven- tion do(A= = a) is transmitted along the other paths.
The fairness criterion defined on path-specific causal effect claims that predictor Y achieves path- specific causal fairness with respect to the sensitive attribute A and the path set π if P PE, (a, a') = 0 holds for all possible value of ú and any value that A can take. However, the term in PE, a'), P(Ý dl A = a' a/|=>), do(A A = al a)). also known as nested counterfactual query; cannot be identified by the formula in Proposition [. on MPDAG. Similarly, our proposed method cannot deal with the counterfactual fairness or path-specific counterfactual fairness defined below. That is because the ongoing challenge of the identification of the counterfactual queries in these notions on MPDAGs, specifically, P(ÝA-a
y|X x, A = a) and P(Ý [(A = o).
Definition F.5 (Counterfactual fairness). (Kusner el al. 2017 Desinition 5) We say the prediction Y is counterfactually fair if under any context X x and A a
PU) = x x, A a) P(AA-a((U))) = 0| x =
for all possible value of and any value attainable by A. Definition F.6 (Path-specific counterfactual fairness). (Chiappa 2019 Wu el al. 2019b) Given a factual condition O = o where O S (A, X, Y) and a causal path set n, predictor Y achieves the path-specific counterfactual fairness if
P(Y (YA= A=al= = / O o) P(LA-a 0|0 = o),
for all possible value of and any value attainable by A.
25

---

Published as a conference paper at ICLR 2024
G SUPPLEMENTARY EXPERIMENTAL RESULTS
G.1 CAUSAL GRAPHS FOR ONE SIMULATION
(a) DAG '
(b) DAG D
M
M
(c) C
(d) MPDAG G
(e) MPDAG g"
Figure 10: (a) is one of the generated DAG D' with 10 nodes and 15 directed edges. The randomly selected sensitive attribute represented by A and the outcome attribute Y; (b) the subgraph of D' over all of the observable variables except Y, denoted by DAG D: (c) is the corresponding CPDAG C such that D [C]: (d) With the background knowledge (A - B, - C, A - D, A - N}, we can obtain the MPDAG g, such that E [9]. The definite non-descendant of can be found to be { (E) by leveraging Algorithm
(e) the extended-G with Ý, denoted as g".
26

---

Published as a conference paper at ICLR 2024
G.2 CAUSAL GRAPHS FOR THE UCI STUDENT DATASET
The causal graphs for the UCI Student Dataset is provided in Figure I1 The attribute in- formation can be found at https: //appii//arciiee.ee ics uci. edu ml/ astatttsteeaaaaaaaaaaaaaaaa Studett + Performance
age
662
oge
schoolaup
achool
schoolsup
school
Vale
Dale
studylime
Dale
studytime
job
arbrress
goout
Mjoh
adddresa
goout
incerree
traveltime
Fjob
internet
traveltime
Fjob
reason
famsup
paid
higher
abseraee
famsup
pord
higher
guardian
notinities
Famaize
tomentie
guardian
actinities
f famssie
romantse
famrre!
Patatus
freetime
nursery
health
famrel
Petatus
freetime
nursery
health
CPDAG C.
(b) MPDAG g'.
age
6ex
uge
schoolaup
achool
W Vale
schoolsup
school
Wale
Dule
studylime
studytime
Medu
M
address
goout
M edu
Mjob
address
goout
internet
traveltime
Fjob
internet
traveltime
Fjob
Pedu
Fedu
/amaray
paid
heer
absenoea
famaup
posi
higher
absenoca
guardinn
potivities
famaise
romentic
guariiian
actiitties
J famasize
romantie
famrel
Pstatus
freetime
nursery
health
famrel
Patatus
freatime
nureery
Realth
(c) MPDAG G.
(d) An arbitrary DAG D in Markov equivalence class of g.
Figure 11: The causal graphs for Student dataset. (a) is the CPDAG C learnt from the observational data; (b) Given the background knowledge that the age is the parent of schoolsup and school, we can have the MPDAG g' by leveraging Meek's rule; (c) Considering the additional background knowledge constraint that the sensitive attribute that cannot have any parent in the graph, we can obtain the MPDAG G; (d) is an arbitary DAG DD in the Markov equivalence class of G.
G.3 MORE EXPERIMENTAL DETAILS ON THE UCI STUDENT DATASET
We employ the GES structure learning algorithm (Chickering 2002a) implemented in TETRAD (Ramsey et al. 2018), a general causal discovery software, to learn the CPDAG from the dataset, ex- cluding the target attribute Grade. After uploading the preprocessed data, we can learn the CPDAG C. The evolution of the CPDAG to MPDAG is shown in Figure II in Appendix G.2 Our experi- ments are carried out the MPDAG in Figure IIc In this dataset, the definite descendants of sex can be identified as (Walc, goout, Dalc, studytime) and all the other nodes are definite non- descendants of sex.
27

---

Published as a conference paper at ICLR 2024
The dataset is divided into three sets: training, validation, and test, in an 8:1:1 ratio. Interven- tional data on sex female and sex = male in the test set is obtained via splitting the test data by different values of On the other hand, the interventional data for training and valida- tion sets are generated according to the causal identification formula. To generate interventional data, we first apply Algorithm [ to the MPDAG in Figure [Tc This gives list of the bucket decomposition of vertices in G: {[ae)), {schoolsup), {school}. (address), (internet), (traveltime), (sex). (Wale), {studytime), (Dalc), {goout), {Mjob, Medu, Fedu), (Fjob). (reason), {famsup, paid, higher), {guardian), {activities), {famsize), {romantic), (famrel), (Pstatus), (frectime), {mursery), (health), (absences)). For each pair of buckets and its parents, we fit conditional multivariate distribution using mixture density networks [Bihhop (1994) for continuous variables and probability contingeney tables for discrete variables. For ex- ample, Figure [2 demonstrates the fitting performance on the attributes school, address, internet and traveltime. Based on the fitted conditional distribution, we generate 395 interventional data points for sex female and sex male, respectively. The proportion for training and val- idation interventional data is 8:2. Additionally, in our c-IFair model, the is set to be it 20 times with different seeds and report [0, 1, 40, 100, 130, 175, 250]. For each model, the average results in the main section.
ordered
travaltme
1.0
school
0.5
0.0
Distribution
Real Gener
1.0
address
0.5
1.0
internet
0.5
0.0
2 traveltime
school
address
internet
Figure 12: The fitting performance the attributes school, address, internet and traveltime in the Student dataset. 'Real' represents the observational data where sex = male, while 'Gener' rep- resents the generated interventional data sex male with the fitted conditional density. To better show the fitting performance, a very small amount of noise is added to discrete variables.
28

---

Published as a conference paper at ICLR 2024
G.4 CAUSAL GRAPHS FOR THE CREDIT RISK DATASET
The causal graphs for the Credit Risk Dataset is provided in Figure 13 The attribute information can be found https: /www. kaggle cotm///ttasett//atteee//eettat
risk dataset
Age
Age
Historical, Length
Emplogment Length
Historical Length
Employment Length
H StmmeSStata
H StatuS
Loun./ntent
Intent
Froome
Income
Ruterest.Rate
Interest.RRte
LoandGrade
Loun.Grade
Hixtorieal Defautt
Loan Amount
Hixtorieal Defautt
Loan Amount
Loan Percent_Income
Loan Percent I Income
(a) MPDAG g.
(b) An arbitrary DAG D in Markov equivalence class of G.
Figure 13: The causal graphs for the Credit Risk dataset. (a) is the learned MPDAG G from the ob- servational data with tier ordering constraint: Age is placed in the first tier, while all other variables are in the second tier; (b) is an arbitrary DAG D in the Markov equivalence class of G.
G.5 MORE EXPERIMENTAL DETAILS ON THE CREDIT RISK DATASET
To obtain an MPDAG over all variables except Loan_status we utilize the GES structure learning algorithm CCickkeing 2002a) implemented in TETRAD. When learning the graph. we consider the tier ordering as background knowledge, where Age is placed in the first tier while all other variables are in the second tier. The resulting MPDAG G is depicted in Figure 13a in Appendix G.4| Since there are no definite non-descendants of Age this dataset, an IFair model is not applicable. The process of interventional data generation and model training follows similar approach as Section 5.2.1
After preprocessing, we focus on two specific age groups: 23 and 30. The age group of 23 consists of 3,413 records, while the age group of 30 has 1,126 records. We divide the whole dataset of 4539 records into three sets: training, validation, and test, using 8:1:1 ratio. Interventional data for the test set is obtained by splitting the test data by Age = 23 and Age= = 30. Similarly, the interventional data for training and validation sets gener- ated according to the causal identification formula. To generate interventional data, we first apply Algorithm 2 to the MPDAG G in Figure 13a This provides us with an ordered list of [Loan__ntent the bucket decomposition of vertices in G: [Age). CitistorriaaLnnnthh (Loan-Grade), (Income, Home__Satuue Employment Length). Defttrli
[Interest_Rate]
Amount), [Loan_Perceee Income)). For each pair of buckets and its parents, we fit a conditional multivariate distribution using mixture density network (iihhop (1994) for continuous variables and probability contingency tables for discrete variables. As an example, Figure [4] demonstrates the fitting performance on the attribute Based the fitted and its parents Income, Amount, Homee_Stauus diistorical conditional distribution, we generate 4539 interventional data points for age = 23 and age = 30, respectively. The proportion for training and validation interventional data is 8:2. Additionally, in our e-IF air model, the À is set to be [2, 4, 6, 10, 15, 150]. For each model, we run it 10 times with different seeds and report the average results in the main section.
29

---

Published as a conference paper at ICLR 2024
Loan Perosnt Incorne
0.75
0.50
0.25
400000
Income
200000
Loan Amount
30000
20000
Distribution Real
10000
Gener
Home Status
Historical Default
0.5 Loan_
0.0
500000
20000 Loan_ AmouAttmtttt
2 Home, Status
Loan_ Percent Income
Income
Historical Default
Figure 14: The fitting performance on the attribute Loan_ Perceet Income and its parents Income, Amount Home Home_Status, Status, observational data where Age 30, while 'Gener' represents the generated interventional data Age = 30 by the fitted conditional density. To better show the fitting performance, a very small amount of noise is added to discrete variables.
Defauut the Credit Risk dataset. 'Real' represents the
30

---

Published as a conference paper at ICLR 2024
G.6 EXPERIMENTS INVOLVING NON-EMPTY ADMISSIBLE VARIABLE SET
For graphs with node d = (5, 10, 20, 30) and the corresponding edge s {8, 20, 40, 60), with the same basic settings and evaluation metrics as Section 5.1 we randomly choose one, one, and three admissible variables for each graph setting respectively. The admissible variable is intervened be the mean of that variable in the observational data. The accuracy fairness trade-off plot is shown in Figure [5] We can see that it follows a similar trend as Section 5.1 For certain values of X, we can simultaneuusly achieve low RMSE comparable to Full model and low unfairness comparable to IFair.
Uroware
Unwvore
Unoware
c-i-air Urowore
1.15
1.10
1.29
1.20
1:15
2.35
mm
1.18
5.00
0.05
0.00
015
0.20
0:00
0.55
0.05
0.03
6.00
3.01
0.03 Unfolmess
3.02
0.04
11 004
0.008
5,012
0.016
(a) SnodesSedges.
(b) 10eddss20edges.
(c) 20nodes40edges.
(d) 30nodes60edges.
Figure 15: Accuracy faimnsss trade-off for the case involving non-empty admissible variable set.
G.7 EXPERIMENTS BASED MORE COMPLICATED STRUCTURAL EQUATIONS
To demonstrate the generality of our method, we generate each variable X; based on non-linear structural equation given by:
X, (x(((XX;) + +e), 100;=1..... I,..., n,
(5)
where the causal mechanism f. is randomly selected from functions such as linear, sin, cos, tanh, sigmoid, and their combinations. The noise term e, is sampled from Gaussian distribution. With the same basic settings and evaluation metrics as described in Section [.1] we present the accu- racy fairness trade-off plot in Figure [6 in solid line. We can see that it follows a similar trend as Section 5.1 For some X, can simultancously achieve low RMSE comparable to Full model and low unfairness comparable to IFair. r. Additionally, we also include the results obtained when the interventional data is generated from the ground-truth structural equations in dotted line. The discrepancy between the two lines reflects the bias introduced by the approximation of conditional densities. The minimal discrepancy observed in Figure [6 suggests that the conditional densities are well fitted. Specifically, we analyze model robustness on the approximation of conditional densities on the linear data in Appendix G.10
G.8 EXPERIMENTAL ANALYSIS ON MODEL PERFORMANCE WITH VARYING AMOUNT OF GIVEN DOMAIN KNOWLEDGE
The performance of baseline models Full and Unaware remain unaffected by the amount of back- ground knowledge. When all ancestral relations between the sensitive attribute and other variables are definite, the performance of IFair model remains consistent regardless of the additional back- ground knowledge. On the other hand, for the e-IFair model, once the causal effect on an MPDAG is identifiable, additional background knowledge does not theoretically impact the performance at given since the same causal identification formula can be applied. However, in practical experi- ments, slight variations may arise due to the error in fitting of different conditional densities. To vary the amount of given background knowledge, we adjust the proportion of the undirected edges' true orientation in CPDAG that is considered the background knowledge. In the '00nodes2eedges' setting, we increase the proportion from 0.1. 0.3, 0.6 to 1.0. The 'BK (%)" value quantifies the proportion of the undirected edges' true orientation that is considered background knowledge. The trade-off plots in Figure[[]jllustee [Tjllustrae this relationship between the amount background knowledge and the resulting tradeoff between fairness and accuracy.
31

---

Published as a conference paper at ICLR 2024
e-IFair
Unaware
1.20
RMSE
1.15
RMSE
1.10
1.10
1.05
1.05
0.00
0.05
0.10
0.15
0.20
0.00
0.02
0.04
0.06
Unfairness
Unfairness
(a) SnodesSedges.
(b) 10nodes20edges.
Gene
Real
Full
E-IFair
IFair Unawan
Gene
Real
Full
E-IFair
IFair Unaware
1.200
1.30
1.25
RMSE
RMSE
1.150
1.125
1.15
0.003
0.006
0.009
0.002
0.004
0.006
0.00:
Unfairness
Unfairness
20nodes40edges.
(d) 30modes60edges.
Figure 16: Accuracy fairness trade-off plots for the non-linear synthetic data. The solid line ('Gene") depicts the results when the interventional data is generated by the fitted conditional densities, while the dotted line ('Real') depicts the results when the interventional data is generated by the ground- truth structural equations.
#u c tuk Urinnre
Full Par Par vhanore
Ful c- & Urawan:
Full (B c-thrr Fol Urowers
1.20
1.29
1.20
1.15
11:15
1.35
115
110
0.54
0.12
D.
0.56
1.06
0.5g
c.24
0.00
1.05
D.D: (d) BK(%)=1.0
0.07
2:08
Unfaimess
(b) BK.
(c) (K(
Figure 17: Accuracy fairness trade-off plots with varying amount of given background knowledge on the graph setting '10nodes2eedges'.
G.9 EXPERIMENTAL ANALYSIS ON MODEL ROBUSTNESS CAUSAL DISCOVERY ALGORITHMS
In Section 5.1 derive the ture CPDAG directly from the known DAG without utilizing any causal discovery algorithm. However, in practical scenarios where the true DAG is unknown, the CPDAG can only be obtained from causal discovery algorithms. To assess the robustness of our model with respect to causal discovery algorithms, we employed the Greedy Equivalence Search (GES) procedure Chickering (2002a) to learn the corresponding CPDAG from the synthetic data. Under the '10nodes20edges' graph setting, Figure (8a provides comparison between the results obtained when the CPDAG is derived from the true DAG and when it learned from the observational data using the GES algorithm. Both sets of results exhibit similar trend, indicating that our model robust to the GES algorithm for causal discovery. Additionally, for reference, we show each case with the scenario where the interventional data is generated from the ground-truth structural equation in Figure 18b and Figure [8c respectively.. Similarly, we obtain analogous results for the "20node44Oedges" graph setting, which displayed in Figure T&d. Figure T8e and Figure T8A
32

---

Published as a conference paper at ICLR 2024
DAG2MPDAG DAG DATA2MPDAG
Gener-
Full c-IFar
-Gene- Real IFair
1.30
RMS
1.20
RMSE
1.20
1.15
1.15
1.10
1.10
1. 1,600
0.025
0.050
0.075
0.050
Unfairness
Unfaimeess
(a) Comparison. (1 (10node220edge)
(b) DAG2MPDAG.
(c) DATA2MPDAG. (1 (10nodes20edge)
(1 (00node220edge)
DAG2MPDAG DATA2MPDAG
1.3
RMSE
1.2
RMSE
RMSE
1.2
1.1
0.01
0.02
0.03
0.02
0.03
0.03
Unfaimess
Unfaimess
Unfaimess
(d) Comparison. (20nodes40edge)
(e) DAG2MPDAG.
(I) DATA2MPDAG.
(20nodes40edge)
(20nodes40edge))
Figure 18: Accuracy fairness trade-off plots analyzing model robustness on causal discovery algo- rithms on the graph settings '00node20edgges' and '20nodes40edges" In (b).(c)((e) and (f), the solid line ("Gene") depicts the results when the interventional data is generated by the fitted conditional densities, while the dotted line ('Real') depicts the results when the interventional data is generated by the ground-truth structural equations.
G.10 EXPERIMENTAL ANALYSIS ON MODEL ROBUSTNESS ON CONDITIONAL DENSITIES APPROXIMATION
Using the same experimental setting as described in Section 5.1 we present the accuracy fairness trade-off plot for linear synthetic data Figure 19 in a solid line. In order analyze the extent to which bias is introduced by approximating conditional densities, we also include the results obtained when the interventional data is generated from the ground-truth structural equations in Figure 19 in dotted line. The discrepancy between the two lines reflect the bias introduced by fitting the conditional densities. The minimal discrepancy observed in Figure suggests that the conditional densities well fitted.
G.11 EXPERIMENTAL ANALYSIS ON MODEL PERFORMANCE ON UNIDENTIHIABLE CASES
Under the graph setting '10nodes20edges" utilizing the same data generation process as in Sec- tion conduct experiments under a scenario where no explicit background knowledge is added for fairness identification. In cases where the MPDAG is unidentifiable, we apply the methodology proposed in Section 4.2 We select four exemplar unidentifiable MPDAGs, encompassing 9 valid MPDAGs separately. Figure 20 shows the prediction and faimess results for each of them, which denoted as 'Unidentifialle" Additionally, we compare these results with ones trained on the ground-truth MPDAGs, wherein the causal effect from A to Y is identifiable, which is denoted by "Identifiable. As depicted in Figure 20 can that the trade-off between accuracy and fair- ness persists in these unidentifiable cases. Interestingly, compared with the prediction learnt solely on the ground-trui truth identifiable MPDAG, the prediction learnt on all possible MPDAGs does not necessarily deteriorate when achieving equivalent levels of unfairness. This could be attributed to the fact that they penalizing different measures fairness.
2 and
33

---

Published as a conference paper at ICLR 2024
E-IFair
E-IFair
1.3
1.2
RMSE
RMSE
1.2
1.1
1.1
1.0
0.0
0.1
0.2
0.00
0.03
0.06
0.09
Unfairness
Unfairness
(a) Snodes8edges.
(b) 10nodes20edges.
Gene
Real
Full
E-IFair
IFair Unaware
Gene Real
Full
E-IFair
IFair Unaware
RMSE
1.2
RMSE
1.20
1.15
0.005
0.010 Unfairness
0.015
0.020
0.003
0.006
0,009
0.012
Unfairness
20nodes40edges.
(d) 30modes60edges.
Figure 19: Accuracy faireess trade-off plots analyzing model robustness on the approximation of conditional densities for the linear synthetic data. The solid line ('Gene") depicts the results when the interventional data is generated by the fitted conditional densities, while the dotted line ("Real') depicts the results when interventional data is generated by the ground-truth structural equations.
1.2
115
122
1275
125
unbmess
Urtammes
6:0
0:3
630
00
11
1.55
05
1.10
1.25
1.75
1.0
125
(a) Example 1.
(b) Example 2.
(c) Example 3.
(d) Examplc 4.
Figure 20: Accuracy fairness trade-off plots analyzing model performance on four exemplar uniden- tifiable cases, which is denoted 'Unidentifiable.. 'Identifiable' denotes the results learnt solely from the ground-truth MPDAG with identifiable results. The solid line ('Gene") depicts the results when the interventional data is generated by the fitted conditional densities, while the dotted line ('Real') ' depicts the results when the interventional data is generated by the ground-truth structural equations.
H ADDITIONAL RELATED WORK ON CAUSAL EFFECT IDENTIFICATION ON MPDAGs
Identifying causal effects from a causal graph that represents observational data under the assump- tion of causal sufficiency is fundamental problem. When the causal DAG is known, it is possible to identify and estimate all causal effects from the observational data (see e.g. Pearl (1995); Pearl & Robins [9955; Robins (188)): Galles & Pearl (1995). In this study, we focus on identifying causal effects in the context of an MPDAG G. We consider causal effect to be identifiable in an MPDAG G if the interventional density of the response can be uniquely computed from G. The
precise definition of identifiability of causal effects is provided in Definition H.1
34

---

Published as a conference paper at ICLR 2024
Definition H.1 (Identifiability of Causal Effects). PPerkovic 2020
Definition 3.1) In MPDAG = G let and Y be disjoint node sets. The causal effect of on Y is identifiable in 9 if f is uniquely computable from any observational density consistent with G.
Hence, there exist no two DAGs D1 and D2 in [9] such that
= f2(v)= f(v), where is an observational density consistent with 9, and 2. [1(y]do(x)) # T2(y)o (d)(x)), where Ji (-(ldo(x)) x)) and J2 [2(-)d((x)) are interventional den- sityies consistent with D1 and D2 respectively.
1. f1(v)=
In recent years, there has been extensive research focused on the identification of causal effects in MPDAGs. One notable contribution in this field the generalized adjustment criterion proposed by Perković et al. (2013); Perkovic et al.] (2017) Perkovi et al. (2018), which provides a sufficient important note that this criterion is not
condition for identifying causal effects. However, necessary for causal effect identification. To address this limitation, Perkovic (2020) introduces a graphical criterion that is both necessary and sufficient for the identification of causal effects in MPDAGs. In addition to the above developments, IDA algorithms and joint-IDA Maathuis et al. 2009 ; Nandy et al. (2017); Perkovic et al. (2017): Witte et al. (2020); Fang & He (2020);
1 Liu et al. 2020 have been proposed for identifying the total effect of variable A on the response Y in MPDAG G. These algorithms consider the orientation configurations of edges connected to variable A and enumerate set of MPDAGs where the total effect is identified. Specifically, Guuo & Perkovic (222)) provide a characterization of the minimal additional edge orientations required to identify given total effect.
I DISCUSSION ON ACCURACY-FAIRNES. TRADE-OFF
The trade-off between accuracy and fairness has been highlighted in numerous studies on algo- rithmic fairness Martinez & Bertran 2019 Zhao & Gordon 2019, Menon & Williamson 2018] Zliobaite 2015 Chen proving farrness measures often comes at the cost of reduced accuracy in machine learning models. However, important to note that the existence of an accuracy-fairnes, trade-off is not universal and depends on the specific data setting. Several recent works have challenged the notion that ac- curacy must always decrease as fairness increases (Dutta et al. 2020 Friedler et al., 202 Yeom & Tschantz 2018). For instance, in the synthetic dataset discussed in Section 5.1 we observed an accuracy fairness trade-off, where improving fairness measures resulted in a decrease in accuracy. However, such trade-off
2018 Wei & Niethammer 2022). These studies highlight that im-
not apparent Figure 15d] The authors in (Wick et al. 2019 Sharma ct al. 2020; Dutta et al. 2020) provide theoretical and empirical insights into when the trade-off ex- ists and when it does not. These findings suggest that the trade-off relationship between accuracy and fairness is context-dependent. It highlights the need for further research to better understand the conditions under which the accuracy fairness trade-off arises and identify strategies to mitigate or overcome it.
35


Reviews:
[{"review_id": "hEqwFQE6NG", "reviewer": "Reviewer_93qw", "summary": "This paper investigates the problem of supervised learning under additional fairness constraints in partially known graphs. Most existing measures of causal fairness constraints require prior knowledge of the directed causal graphs that encode the underlying causal relationships between variables. This paper attempts to relax this assumption. Some previous work, such as Fair proposed by Zuo et al., can achieve causal fairness but discards a lot of covariate information, which impairs the prediction performance. In this paper, we propose a method called IFair to trade-off unfairness and prediction performance by solving a constrained optimization problem. Meanwhile, the paper discusses in detail how to identify some causal estimators with theoretical guarantees and provides concrete examples to illustrate the propositions. The effectiveness of this approach has been confirmed in tests on both simulated and real datasets.", "questions": "Please refer to the weakness part for the questions.\n\n***\n\nAfter rebuttal: Thank you very much to the authors for their answers to our reviews and for improving the paper during the rebuttal period. The modifications bring valuable content. I read also carefully the other reviews and the corresponding answers. My recommendation is \"accept, good paper\".", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "S1: This paper investigates the novel problem of imposing causal fairness constraints for supervised learning in the absence of detailed causal knowledge. \n\nS2: This paper provides a comprehensive discussion of the related work, and it is clearly written and organized. \n\nS3: Fully specifying causal graphs is one of the main challenges in applying causal fairness in practice. The method presented in this paper relaxes the assumption of fully available causal graphs and is highly motivated.\n\nS4: The IFair method does not require input to be a causal DAG, which is hardly obtained in real-world data. Instead, the proposed method accepts a CPDAG or an MPDAG as the input, which is more feasible.\n\nS5: This paper conduct extensive experiments on both synthetic dataset and real-world dataset, which verifies the effectiveness of IFair method.", "weaknesses": "W1: Is the proposed approach still valid when Y is not the last node in the topological ordering, or when the sensitive attribute is not the root node?\n\nW2: Is it necessary for each node to have an arrow pointing to Y in G?\n\nW3: Zuo et al. utilize counterfactual fairness by identifying deterministic non-descendants of sensitive attributes on the MPDAG, which does not seem to require a full understanding of causal graphs. Can the authors provide a more detailed analysis to distinguish between these two approaches?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "VKbRydP4rK", "reviewer": "Reviewer_T67w", "summary": "The authors explore the challenge of causal fair learning with only partial knowledge of the structural causal model. They approach this issue by assuming the causal model is provided in the form of a maximal partial directed acyclic graph (MPDAG). This graph represents a Markov equivalent class of directed acyclic graphs (DAGs) that align with the available knowledge. Using the MPDAG, the authors' algorithm aims to construct a predictor that not only maximizes prediction accuracy but also adheres to interventional fairness, a causal-based definition of fairness. Unlike existing learning algorithms that ensure interventional fairness but fail to manage the accuracy-fairness trade-off, the proposed algorithm introduces a parameter specifically for this purpose. The authors employ key techniques to identify and estimate the intervention distribution of the predicted outcome. This allows them to evaluate the degree of interventional fairness and incorporate it into the optimization problem of the learning algorithm. Experiments using both synthetic and real datasets confirm the algorithm's capability to control the accuracy-fairness trade-off effectively.", "questions": "1. Could the authors shed light on the contributions and advancements made beyond the scope of Perkovic 2020?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper is well-written and easy to follow.\n\n2. Addressing causal-based fairness with only a fragmentary understanding of the causal graph is vital. The primary challenge in enforcing causal-based fairness is constructing an accurate causal graph. This research's ability to guarantee causal-based fairness using an incomplete causal graph widens its relevance to practical scenarios.\n\n3. Incorporating the techniques from Perkovic 2020 into causal fair learning is interesting. As highlighted by the authors, this approach achieves the identification and estimation of the intervention distribution for the predicted label, thus enhancing the control over the accuracy-fairness trade-off.\n\n4. The experimental findings unequivocally validate the proposed algorithm's capability to control the trade-off between accuracy and interventional fairness.", "weaknesses": "1. The algorithm presented seems to be a direct adaptation of the findings from Perkovic 2020. If the intervention distribution over observable endogenous variables can be identified and estimated, it stands to reason that the intervention distribution of the predicted label is also identifable and estimable, given that this label is derived using a known function from the intervened observable endogenous variables. This raises questions about the method's novelity.\n\n2. The approach necessitates the creation and estimation of the generative model for non-admissible attributes. This forms a significant impediment to its application in real-world contexts, especially when the direct causal functions of the partial causal model may not be readily observable.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "pqeE8mM18t", "reviewer": "Reviewer_U24x", "summary": "The paper deals with the problem of learning an interventionally fair classifier when the underlying causal graph is not available. For this purpose, the authors propose to first apply a causal discovery algorithm, resulting in a maximally partially directed graph (MPDAG). Then, the authors add the predictor as an additional node to the causal graph and use identifiability theory for MPDAGs to estimate discrepancies with respect to interventional fairness, which is then added as a penalty to the predictor loss. The method is evaluated on synthetic and real-world data.", "questions": "- In the case of non-identification, the authors propose to replace the penalty term with a sum over all possible MPDAGs by directing the relevant edges. Can the authors provide some intuition/experiments on how this affects the prediction performance? I could imagine that the prediction performance could suffer if the objective is penalized with a large sum of MPDAGs.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper deals with an important topic, as the causal graph of the underlying data-generating process is often unknown in practice\n- The method is theoretically sound, identifiability guarantees and proofs are provided\n- The experimental results indicate the effectiveness of the proposed method", "weaknesses": "- The idea of adding a fairness penalty to the prediction objective and using a trade-off parameter is not novel but has been explored in previous papers with numerous fairness notions (e.g., Quinzan et al. 2022, Frauen et al. 2023). From my understanding, the novelty is combining these ideas with causal discovery and identifiability theory for MPDAGs.\n- Related to the previous point, the paper seems to combine these results in a rather straightforward manner, with limited novel ideas. However, the corresponding theoretical results (e.g., Theorem 4.1) seem sound and no previous work seems to have applied MPDAG identifiability theory to interventional fairness (which, in my opinion, is enough novelty for recommending acceptance, but also justifies why I am hesitant to give a higher score).\n- Applicability in practice: The proposed method seems to be difficult to employ in practice. First, one has to run a causal discovery algorithm to obtain an MPDAG, and then perform conditional density estimation to obtain the fairness penalty. Furthermore, there is no way of automatically choosing the trade-off parameter (even though this point is not specifically a drawback of the method in this paper).\n-  The authors hint at the possibility of extending their approach to other fairness notions. I think the paper would benefit from a more detailed review of related fairness notions in the appendix (e.g., total/direct/indirect effects, path-specific effects, counterfactual fairness), and how the method could (or could not) be extended\n\n--- Post rebuttal response ---\nI thank the authors for their rebuttal. After reading the comments, I continue to be positive about the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)