Front-door Adjustment Beyond Markov Equivalence with Limited Graph Knowledge
Authors: Abhin Shah
Karthikeyan Shanmugam
Murat Kocaoglu
Venue: NeurIPS 2023 poster (2023)
Keywords: Causal Effect Estimation
Front-door Adjustment
Limited Graph Knowledge
TL;DR: We provide testable conditions to compute the causal effect using front-door-like adjustment without knowing the entire graph under limited structural side information.

Abstract: Causal effect estimation from data typically requires assumptions about the cause-effect relations either explicitly in the form of a causal graph structure within the Pearlian framework, or implicitly in terms of (conditional) independence statements between counterfactual variables within the potential outcomes framework. When the treatment variable and the outcome variable are confounded, front-door adjustment is an important special case where, given the graph, causal effect of the treatment on the target can be estimated using post-treatment variables. However, the exact formula for front-door adjustment depends on the structure of the graph, which is difficult to learn in practice. In this work, we provide testable conditional independence statements to compute the causal effect using front-door-like adjustment without knowing the graph under limited structural side information. We show that our method is applicable in scenarios where knowing the Markov equivalence class is not sufficient for causal effect estimation. We demonstrate the effectiveness of our method on a class of random graphs as well as real causal fairness benchmarks.

Front-door Adjustment Beyond Markov Equivalence with Limited Graph Knowledge
Abhin Shah Massachusetts Institute of Technology abhin@mit.edu
Karthikeyan Shanmugam
Google Research
kartakkeyavv@@oogle.cmm com
Murat Kocaoglu
Purdue University
mkocaoglu@purrue.. edu
Abstract
Causal effect estimation from data typically requires assumptions about the cause-effect relations either explicitly in the form of causal graph structure within the Pearlian framework, or implicitly in terms of (conditional) independence statements between counterfactual variables within the potential outcomes framework. When the treatment variable and the outcome variable are confounded, front-door adjustment is important special case where, given the graph, causal effect of the treatment on the target can estimated using post-treatmett variables. However, the exact formula for front-door adjustment depends the structure of the graph, which is difficult to learn in practice. In this work, we provide testable conditional independence statements compute the causal effect using front-door-lin like adjustment without knowing the graph under limited structural side information. We show that our method is applicable in scenarios where knowing the Markov equivalence class is not sufficient for causal effect estimation. We demonstrate the effectiveness of our method on a class of random graphs as well real causal faimess benchmarks.
Introduction
Causal effect estimation is at the center numerous scientific, societal, and medical questions [Nabi et al., 2019, Castro et al., 2020J. The do(-) operator of Pearl represents the effect of an experiment on causal system. For example, the probability distribution of target variable after setting treatment to is represented by P(y|do(t = t)) and is known an interventional distribution. Learning this distribution for any realization distribution is different from the conditional distribution P(y|t t) as there may be unobserved confounders between treatment and outcome that cannot controlled for.
t' what causal effect estimation entails. This
causal graph, often depicted as a directed acyclic graph, captures the cause-and-effect relationships between variables and explains the causal system under consideration. semi-Markovian causal model represents a causal model that includes unobserved variables influencing multiple observed variables [Verma and Pearl, 1990, Acharya al., 2018]. In eeni-Markovian graph, directed edges between observed variables represent causal relationships, while bi-directed edges between observed variables represent unobserved common confounding (see Figure 1). Given any coni-Markovian
Depending on the context, causal effect estimation sometimes refers to the estimating the difference of assigning t = 1 vs. = 0 on the target variable e.g., Ejy|do(t = 1)] do(r 0)}. This quantity is computable if we can identify Plyldo(t t)) for 1}.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Z
Figure 1: Representative graphs for back-door adjustment (left) and front-door adjustment (right).
graph, complete identification algorithms for causal effect estimation are known. For example, if P(y]do(t t)) is uniquely determined by the observational distribution and the causal graph, the algorithm by Shpitser and Pearl [2006] utilizes the graph to derive an estimand, i.c., the functional form mapping the observational distribution to the interventional distribution.
Certain special cases of estimands have found widespread use across several domains. One such special case is the back-door adjustment [Pearl, 1993] shown in Figure (left). The back-door adjustment utilizes the pre-treatment variable z (that blocks back-door paths) to control for unobserved confounder as follows:
P(y|do(t= t)) Σ
2),
where the do-caleulus rules of Pearl [1995] are used to convert interventional distributions into observational distributions by leveraging the graph structure. However, the back-door adjustment often inapplicable, e.g., in the presence of unobserved confounder between t and y. Surprisingly, in such scenarios, it is sometimes possible to find the causal effect using the front-doot adjustment [Pearl, 1995] shown in Figure (riight). Utilizing the front-door variable z, the front-door adjustment estimates the causal effect from observational distributions using the following formula (which is also obtained through the do-calculus rules and the graph structure):
F(y|do(t- t)) = P(ylt- L', 2) - -(') (1)) 2/t t)
(
Recently, front-door adjustment has gained popularity in analyzing real-world data [Glynn and Kashin, 2017, Bellemare et al., 2019, Hünermund and Bareinboim, 2019] due to its ability to utilize post-treatment variables to estimate effects even in the presence of confounding between t and y. However, in general, front-door adjustment also relies on knowing the causal graph, which may not always be feasible, especially in domains with many variables.
An alternative approach uses observational data to infer a Markov equivalence class, which is a collection of causal graphs that encode the same conditional independence relations [Spirtes et al., 2000]. A line of work [Perkovic et al., 2018, Jaber et al., 2019] provide identification algorithms for causal effect estimation from partial ancestral graphs (PAGs) [Zhang, 2008), a prominent representation of the Markov equivalence class, whenever every causal graph in the collection shares the same causal effect estimand. However, learning PAGi from data challenging in practice due to the sequential nature of their learning algorithms, which can propagate errors between tests [Strobl al., 2019a]. Further, the best of our knowledge, there no existing algorithm that can incorporate side information, such as known post-treatment variables, into PAG structure learning.
In this work, we ask the following question: Can the causal effect be estimated with a testable criteria on observational data by utilizing some structural side information without knowing the graph?
Recent research has developed such testable criteria to enable back-door adjustment without knowing the full causal graph [Entner et al., 2013, Cheng et al., 2020, Gultchin et al., 2020, Shah al., 2022]. These approaches leverage structural side information, such as known and observed parent of the treatment variable t. However, no such results have been established for enabling front-door adjustment. We address this gap by focusing the case of unobserved confounding between t and y, where back-door adjustment is inapplicable. Traditionally, this scenario has been addressed by leveraging the presence of an instrumental variable [Mogstad and Torgovitsky, 2018] or performing sensitivity analysis [Veitch and Zaveri, 2020], both of which provide only bounds in the non-parametric case. In contrast, achieve identifiability by utilizing structural side information.
Contributions. We propose a method for estimating causal effects without requiring the knowledge of causal graph in the presence of unobserved confounding between treatment and outcome. Our approach utilizes front-door-like adjustments based on post-treatment variables and relies on conditional independence statements that can be directly tested from observational data. We

---

require one structural side information which can be obtained from an expert and is less demanding than specifying the entire causal graph. We illustrate that our framework provides identifiability in random ensembles where existing PAG-based methods are not applicable. Further, we illustrate the practical application of our approach to causal fairness analysis by estimating the total effect of sensitive attribute on an outcome variable using the German credit data with fewer structural assumptions. The source code of our implementation is available at https://gg /tt/tggtttbbt/// com/ abhin- Seeinn-shh/FDD--e waw--sshaa/aaaaseeeeeeeta-- centtmmnnttthhhe with- limited- graph.
1.1 Related Work
Effect estimation from causal graphs/Markor equivalence Class: The problem of estimating interventional distributions with the knowledge of the semi-Markovian model has been studied extensively in the literature, with important contributions such as Tian and Pearl [2002] and Shpitser and Pearl [2006]. Perkovic et al. [2018] presented a complete and sound algorithm for identifying valid adjustments from PAGs. Going beyond valid adjustments, Jaber et al. [2019] proposed complete and sound algorithm for identifying causal effect from PAGs. However, our method can recover the causal effect in scenarios where these algorithms are inapplicable.
Effect estimation via front-door adjustment with causal graph: Several recent works have contributed better understanding of the statistical properties of front-door estimation [Kuroki, 2000, Kuroki and Cai, 2012, Glynn and Kashin, 2018, Gupta et al., 2021], proposed robust generalizations [Hünermund and Bareinboim, 2019, Fulcher al., 2020], and developed procedures to enumerate all possible front-door adjustment sets [Jeong et al., 2022, Wienöhst et al., 2022]. However, all of these require knowing the underlying causal graph. By contrast, Bhattacharya and Nabi [2022] verified the front-door criterion without knowing the causal graph using Verma constraint-based methodology. While their method limited a small set of graphs, ours leverages conditional independence, making it applicable to much broader class of graphs. We note that they' re applicable in different settings, depending on what the analyst knows about the problem.
2 Preliminaries and Problem Formulation
Notations. For a sequence of realizations V1, ... , .'a we define r - (ri,"... . For a sequence of random variables ".... fu. we define - (n.
Let denote the indicator function.
Semi-Markovian Model and Effect Estimation. We consider a causal effect estimation task where represents the set of observed features, t represents the observed treatment variable, and y represents the observed outcome variable. We denote the set all observed variables jointly by V - {x, t, }. Let U denote the set of unobserved features that could be correlated with the observed variables.
We assume W A Uul follows Mani-Markovi causal model [Tian and Pearl, 2002] below. Definition 1. A semi-Markovian causal model (SMCM) M is specified as follows:
1. G is a directed acyclic graph (DAG) over the set of vertices W such that each element of the set U has no parents.
Vv E V, let (v) S V and π. (((0 S U denote the set of parent of v in V and U, respectively. P()) is the unobserved joint distribution over the unobserved features.
4. The observational distribution is given by PPvV) = E,, II (( nt (v))]
VVE
5. The interventional distribution when the variables C: V are set to a fixed value r is given by
PPW]do(r- = -r)) -rar
Eu
II vEVVr
(O (v), (V))..
6. For any VI, v2 E V, (f) n (1) (v2) + 0, then vi and v2 have a bi-directed edge in G.
In this work, are interested in the causal effect of t on y, i.e., PP(y)do(= 1)). We define this formally by marginalizing all variables except in the interventional distribution in (3).
Definition 2. The causal effect of (when forced to value t) y is given by:
IP(y (oy] = 1))= Σ PP( (y) ydo(t = t)).
(4)
vibi
3

---

Next, we define the notion of average treatment effect for binary treatment t. Definition 3. The average treatment effect (ATE) of a binary treatment on outcome y is given by ATE Ely]do(t 1)] Ely do(t = 0)].
Next, we define when the causal effect (Definition 2) is said to be identifiable from the observational distribution and the causal graph.
Definition 4. (Causal effect identifiabilitt) Given an observational distribution P(v) and a causal graph G. the causal effect Pyy do(t | = t)) identifiable if it is identical for every semi-Markone Causal model with (a) same graph G and (b) same observational distribution P(v).
In a causal graph G. a path is an ordered sequence of distinct nodes where each node is connected to the next in the sequence by an edge. A path starting at node Wi and ending at node W2 in G is blocked by set w C WW) \ [wi, w2] there exists w E w such that (a) w not collider or (b) w is collider and neither w nor any of it's descendant is in w. Further, Wi and W2 are said to be d-separated by w in G if w blocks every path between Wi and Wa G. Let Wi Il. d Wa |w denote that W1 and W2 are d-separated by in G. Similarly, let W1 Lp Wa w denote that Wi and w2 conditionally independent given w. We assume causal faithfulness, i.c., any conditional independence W1 1p wa w implies d-separation relation Wi da w2 w in the causal graph G.
2.1
Adjustment using pre-treatment variables
is common in causal effect estimation to consider pre-treatment variables, i.e., variables that occur before the treatment in the causal ordering, and identify sets of variables that are valid adjustments. Specifically, a set z C V forms a valid adjustment if the causal effect can be written as P(y]do(f t)) E, P(y|t- = f, z = 2)) = z). In other words, a valid adjustment Z averages an estimate of y regressed on and with respect to the marginal distribution of z, A popular criterion to find valid adjustments is to find a set z C V that satisfies the back-door criterion [Pearl, 2009]. Formally, a set z satisfies the back-door criterion (a) it blocks all back-door paths, i.e., paths between and that have an arrow pointing at and (b) no element of z is a descendant of t. While, in general, back-door sets can be found with the knowledge of the causal graph, recent works (see the survey Cheng et al. [2022]) have proposed testable criteria for identifying back-door sets with some causal side information, without requiring the entire graph
2.2 Adjustment using post-treatment variables
While back-door adjustment is widely used, there are scenarios where no back-door set exists, e.g., when there is an unobserved confounder between t and y. no back-door set can be found from the pre-treatment variables, Pearlian theory can be used to identify post-treatment variables, i.e., the variables that occur after the treatment in the causal ordering, to obtain a front-door udjustment.
Definition 5 (Front-door criterion). set V satisfies the front-door criterion with respect to and y if) z intercepts all directed paths from to y (b) all back-door paths between t and z are blocked, and (c) all back-door paths between z and y are blocked by
If a set z satisfies the front-door criterion, then the causal effect can be written as
P(y]do(t = ()) = plylt = L', = 2) - (()(t=()))pp =|t=== ())
(5)
Intuitively, front-door adjustment estimates the causal effect of t on y as a composition of two effects: (a) the effect of on z and (b) the effect of on y. However, one still needs the knowledge of the causal graph G to find a set satisfying the front-door criterion.
Inspired by the progress in finding back-door sets without knowing the entire causal graph, we ask: Can testable conditions be derived to identify front-door-like sets using only partial structural information about post-treatuoe treatment variables? To that end, we consider the following side information.
Assumption 1. The outcome y is a descendant of the treatment t.
Assumption 2. There is an unobserved confounder between the outcome y and the treatment Assumption 3. b, the set of all children of the treatment t, is observed and known.

---

Assumption 1 is fundamental assumption in most causal inference works, as it forms the basis for estimating non-trivial causal effects. Without it, the causal effect would be zero. Assumption 2 rules out the existence of sets that satisfy the back-door criteria, necessitating a different way of estimating the causal effect. Assumption 3 captures our side information by requiring every children of the treatment to be known and observed. To contrast, the side information in data-driven works on back-door adjustment requires a parent of the treatment to be known and observed [Shah et al., 2022].
Our assumptions imply that b intercepts all the directed paths from to y. Given this, natural to ask whether b satisfies the front-door criterion (Definition 5). We note that, general, this not true. We illustrate this via Figure 2 where we provide a causal graph goog satisfying our assumptions. However, b is not valid front-door set in gloy as the back-door path between and y via z(0 is not blocked by t. Therefore, estimating the causal effect by assuming b is a front-door set might not always give an unbiased estimate. In the next section, we leverage the given side information and provide testable conditions identify front-door-lis sets.
U1
U1
U5
Figure 2: Assumptions I to where i; are unobserved.
The graph glay satisfying
3 Front-door Adjustment Beyond Markov Equivalence
In this section, we provide our main results, an algorithm for ATE estimation, and discuss the relationship to PAG-based methods. Our main results use observational criteria for causal effect estimation under Assumptions to 3 using post treatment variables.
3.1 Causal effect estimation using post-treatment variables
First, we state conditional independence statement implying causal identifiability. Then, we provide additional conditional independence statements resulting unique formula for effect estimation.
Causal identifiability (Definition 4) implies that the causal effect is uniquely determined given an observational distribution P(V) and the corresponding causal graph G. We now show that satisfying a conditional independence statement (which can be tested solely from observational data, without requiring the graph 9) guarantees identifiability. We provide a proof in Appendix D.
Theorem 3.1 (Causal Identifiability). Suppose Assumptions I to 3 hold. If there exists set z C V \ yt such that b a yit, z, then the causal effect of t on is identifiable from observational data without the knowledge of the underlying causal graph G.
While the above result leads to identifiability, it does not provide a formula to compute the causal effect. In fact, the conditional independence b Il a y/ y/t, z alone is insufficient to establish a unique formula, and different causal graphs lead to different formula. To illustrate this, we provide two SMCMs where Assumptions 1 to 3 and b iLt y/t, hold, i.e., causal effect is identifiable from observational data via Theorem 3.1, but the formula is different. First, consider the SMCM in Figure 3(top) with (ZI, 22) where causal effect given by following formula (derived in Appendix D):
Poy|do(t- t))
Σ $1.
Σ Plyl21, 22, t)p(t(l2)) x P( Pbb 21 P(1))
(6)
Next, consider the SMCM in Figure 3(bottom) with z Z where the causal effect is given by the front-door adjustment formula in (5) as z satisfies the front-door criterion. remains to explicitly show that the formula in (6) is different from (5). To this end, we create a synthetic structural equation model (SEM) respecting the graph in Figure 3(top) and show that the formula in (5) gives a non-zero ATE error. In our SEM, the unobserved variable has uniform distribution over 2]. Each observed variable except t is sum of (i) linear combination of its parents with
b
Figure 3: SMCMs on (top) & (bottom) satisfy b a y/t, z but have different causal effect estimation formulae.
5

---

coefficients drawn from uniform distribution over [1,2] and (ii) zero-mean Gaussian noise. The treatment variable is binarized by applying a standard logistic model to linear combination of its parents with coefficients drawn before. The ATE error averaged over 50 runs with 50000 samples each run 0.3842 0.0207. See more experimental details in Appendix G.
Next, we provide two additional conditional independence statements that imply a unique formula for causal effect estimation. Our result is generalized front-door with formula identical to (5) as if were a traditional front-door set. We also offer an alternative formula by utilizing specific partition of obtained from the conditional independence statements. We provide proof in Appendix E.
Theorem 3.2 (A generalized front-door condition). Suppose Assumptions I to 3 hold. Let z S V bt be a set satisfying
b PTt y/t,z,
such that can be decomposed into 2(0) C z aad z0) = 2(0) with
(i) (0) a and
(ii) (0) ll t|b, (t)
(8)
Then, z and - (b, (0) are generalized front-doors, and the causal effect of on y can be obtained using any of the following equivalent formulae: forvvalentformula::
P(y]do(t =)) Σ Σ ((y(2, P())))
P(y|do(t= 1))
Σ Σ ((P(), P((())
(10)
Remark 1. Consider the case where y is child of Then, the sufficient conditions in Theorems 3.1 and 3.2 do not hold because the conditional independence in (7) will not pass as (which follows from Assumption 3). However, in this case, the causal query itself is not identifiable there exists bi-directed edge between y and (from Assumption 2) (see Tian and Pearl [2002, Theorem 4]).
Algorithm 1: ATE estimation using subset search.
Input: nr, t, y, b, 2,Pr
Output: ATE2; ATE,
Initialization; ATE, = 0, ATE, 0, =0
for r 1er=1.... 1...,,................ n, do // Use a different train-test split in each run ATE; = 0, ATE" = 0, = 0; // These are used to average over different subsets that satisfy our conditions for specific train-test split
for z E Z do // Perform
exhaustive search over Z
if CT 1p y/z,t) t) > P. then // Check for (7) where stands for conditional independence
for z (o) C z do // Perform an exhaustive search over to find 2()) and
z ( = z z(() (0);
if min ( (Zl (0) 1p t), C((((() 1pt
r//b ( > Pv)
then // Check for (8)
= 0 + 1, s (b,z()
ATE ATE + Egit =1 Σ. (lyl)
Egar= E. Elylz,
ATE, = ATE, + Ext, En Blyls, (IF('))
Σ Ee Blyls
10:;==11
cz > 0 then
L ATE, = ATE, + ATE ATE, = ATE, + -
if f > then
ATE, = ATE./q, ATE, = ATE./c; // is used to average different
train-test splits.
else
Failed to find z = (2(1), 2(01) satisfying (7) and (8);

---

3.2 Algorithm for ATE estimation
The ATE can be computed by taking the first moment version of (9) or (10). In Algorithm we provide a systematic way to estimate the ATE using Theorem 3.2 by searching for set E - VA (t. y) such that (a) p-value of conditional independence in (7) passes a threshold p. and (b) there exists decomposition pass the threshold pv- Then, for every such z, the algorithm computes the ATE using the first moment
(z(6), z0) such that p-values of conditional independencies in (8)
version of (9), and averages. The algorithm produces another estimate by using (10) instead of (9).
3.3 Relation PAG-based algorithms
Now, we exhibit how our approach can recover the causal effect in certain scenarios where PAG- methods are not suitable. PAGs depict ancestral relationships (not necessarily direct) with directed edges and ambiguity in orientations (if they exist across members of the equivalence class) by circle marks. Figure 4(c) shows the PAG consistent with SMCM Figure 4(a). While we formally define PAGs in Appendix B, we refer interested readers to Triantafillou and Tsamardinos [2015]. The IDP algorithm of Jaber et al. [2019] is sound and complete for identifying causal effect from PAGs.
Consider SMCM in Figure 4(a) where our approach recovers the causal effect as (i) Assumptions 1 to (3), (dt) (7), and (iát) (8) hold (where (ti) and (iti) can be tested from observational data). However, the IDP algorithm fails to recover the effect from the PAG. To see this, consider SMCM in Figure 4(b) which is Markov equivalent
SMCM Figure 4(a), i.e., the PAG in Figure 4(c) also consistent
with SMCM in Figure 4(b). Intuitively, when the strength of the edge between and b is very small but the strength of the edge between f and y very high for both Figure 4(a) and Figure 4(b), causal effect in Figure 4(b) remains high while the causal effect in Figure 4(a) goes to zero.
We note that Assumptions and 3, and (7) do not hold for the SMCM Figure 4(b).
O
b
Z
y
Figure 4: (a) An SMCM satisfying (7) and (8). (b) An SMCM obtained from (a) by modifying the edges between t and b and between and y. (c) The PAG corresponding to SMCM in (a) and (b).
Remark 2. Obtaining a PAG requires a large number of sequential conditional independence tests
where the choice of the next test depends the previous ones [Claassen et al., 2013]. The erroneous tests and orientation steps can potentially alter the structure of the PAG non-locally (see Strobl et al [2016] for an example). This makes it difficult control the false discovery rate for PAG based methods. Moreover, incorporating arbitrary side information into a PAG in a systematic way is still an open problem. In contrast, our approach does not rely on constructing graphical object such as a PAG and the conditional independence tests could be carried out in parallel. Thus, our method can be viewed way to mitigate the issues associated with sequential testing by using structural side information. However, in scenarios where the structural side information is not available, we may have resort PAG-based methods.
4 Empirical Evaluation
We evaluate our approach empirically in ways: (i) we demonstrate the applicability of our method on class of random graphs, (ii) we assess the effectiveness of our method in estimating the ATE using finite samples, and (iit) we showcase the potential of our method for causal fairness analysis.
4.1 Applicability to class of random graphs
In this experiment, we create a class of random SMCMs, sample 100 SMCMs from this class, and check if (7) and (8) hold by checking for corresponding d d-separations in the SMCMs.
7

---

Creation of random SMCMs. Let _ [ denote the dimension of observed variables including t, and y. Let Vi,-. Vy denote a causal ordering of these variables. Our random ensemble depends on two parameters: (?) d S p/2 which is the expected in-degree of variables V2d, ... Vp and (ii) q S p which controls the number of unobserved features. For Σ j S p. we add v, - v, with probability 0.5 if S 2d and with probability d/(j 1) if > 2d. We note that this procedure is such that the expected in-degree of variables V2d, ... Vp is same (and equal to d) which is consistent with other recent work (e.g., Addanki et al. [2020]). Next, for 1 < i < S p. we add V2 +-+ Vi with probability g/p such that the expected number of unobserved features is q(P 1)/2. Then, we choose Ve y, any variable that is ancestor of y but not its parent or grandparent t, and all children of t as b. Finally, we add t +++ if missing.
Results. We compare the success rate of two approaches: (i) exhaustive search for z satisfying (7) and (8) which is exponential in p and (ti) search for a z of size at-most satisfying (7) and (8) which is polynomial in p. We provide the number of successes of these approaches as tuple in Table 1 for various p. d, and q. We see that the two approaches have comparable performances. We also compare with the IDP algorithm by providing it the true PAG. However, it gives 0 successes across various p. d, and q. We provide results for another random ensemble in Appendix G.
Table I:
Number of successes out of 100 random graphs for our methods shown as a tuple. The first method searches exhaustively and the second method searches a with size at-most 5.
10
p=
15
d = 2
d= = 3
d
d= 2
d= 3
d= 4
0.0
(43, 43)
(20, 20)
(21
(27, 26)
(9,9)
(4.2)
q 0.5
(23, 23)
(16, 16)
(7.7)
(18, 17)
(4,3)
(0,0)
= 1.0
(6,6)
(4,4)
(5,5)
(9,9)
(10,9)
(0,0)
4.2 Estimating the ATE
In this experiment, we generate synthetic data using the 6 random SMCMs in Section 4.1 for p 10, d = 2, and g = 1.0 where our approach was successful indicating existence of z (z(9) z such that the conditional independence statements in Theorem 3.2 hold. Then, we use Algorithm 1 to compute the error in estimating ATE and compare against Baseline which uses the front-door adjustment in (5) with z b given the side information in Assumption 3. We provide the results for the same experiment for specific choices of SMCMs including the one in Figure 2 in Appendix G. We also provide the 6 random SMMMSs in Appendix G. We use RCoT hypothesis test [Strobl et al., 2019b] for conditional independence testing from finite data.
Data generation. We use the following procedure to generate data from every SMCM. We generate unobserved variables independently from Unif 2] which denotes the uniform distribution over [1, 2]. For every observed variable V. let π (v) & (I))) ())(()))) Rd+x1 denote the set of observed and unobserved parents of v stacked as a column vector. Then, we generate v E V as
-= a. (v) + 0.1 10 for E V {t} and
Bernoulli(Sigmoidl [a] x())) (11)
where the coefficients a, E Rd4x1 with every entry sampled independently from Unif[1, 2). Also, to generate the true ATE, we intervene on the generation model in (11) by setting t = and t 1.
0.312
Average ATE ennor
0.21
Baseline
For every SMCM, we generate n samples of every observed variable in every run of the experiment. We average the ATE error over 10 such runs where the coefficients in (11) vary across runs. We report the average of these averages over the 6 SMCMs in Figure for various n. While the error rates of Baseline and Algorithm I are of the similar order for Algorithm gives much lower errors for n = 1000 and n 10000 showing the efficacy of our method.
Results.
Exhaustive
60.16
Exhaustive,
0.08
0.000
10
10
Number of samples
100,
Figure 5: Average ATE for Algorithm I and
Baseline vs. number of samples.
8

---

4.3 Experiments with real-world fairness benchmarks
Next, we describe how our results enable finding front-door- adjustment sets in faimess problems. In a typical fairness problem, the goal is ensure that the outcome variable y does not unfairly depend on the sensitive/protected attribute, c.g., race or gender (which we define to be treatment variable t). which would reflect undesirable biases. Often, the outcome is a descendant of the sensitive attribute (as per Assumption 1), and both outcome and sensitive attribute are confounded by unobserved variables (as per Assumption 2). Furthermore, there are be a multitude of measured sensitive-attribur variables that can affect the outcome. This stands in contrast to the usual settings for causal effect estimation, where pre-treatment variables are primarily utilized.
Fairness problems are typically evaluated using various faimess metrics, such as causal fairness metries or observational metrics. Causal metrics require knowing the underlying causal graph, which can be a challenge in practice. Observational criteria can be decomposed into three types of effects [Zhang and Bareinboim, 2018, Plecko and Bareinboim, 2022]: spurious effects, direct effects, and indirect effects (through descendants of sensitive attribute). In some scenarios, capturing the sum of direct and indirect effects is of interest, but even this requires knowing the causal graph.
Now, we demonstrate the application of our adjustment formulae in Theorem 3.2 to compute the sum of direct and indirect effects of the sensitive attribute on the outcome, while separating from spurious effects. The sum of these effects is indeed the causal effect of sensitive attribute on the outcome. In other words, we consider the following faimess metric: Ely]do(( = 1)] - -Bly |d(( 0)]. We assume that all the children of the sensitive attribute are known, which may be easier to justify compared to the typical assumption in causal fairness literature of knowing the entire causal graph.
German Credit Dataset. The German Credit dataset [Hofmann, 1994] is used for credit risk analysis where the goal is to predict whether loan applicant is a good or bad credit risk based on applicant's 's 20 demographic and recio-economic attributes. The binary credit risk is the outcome and the applicant's is age (binarized by thresholding at 25 [Kamiran and Calders, 2009]) is the sensitive attribute t. Further, the categorical attributes are one-hot encoded.
We apply Algorithm 1 with n, = 100 and p. = 0.1 where we search for a set z = =2) z(0) of size most under the following two distinct assumptions the set of all children b of t:
1. When considering b= (# of people financially dependent on the applicant, applicant's savings, applicant's job), Algorithm 1 results in ( = {purpose for which the credit was needed, indicator of whether the applicant was a foreign worker), z(z) = (installment plans from providers other than the rredit-giving bank). ATE, = 0.0125 + 0.0011, and ATE, 0.0105 + 0.0018.
2. When considering b = (# of people financially dependent on the applicant, applicant's savings), Algorithm 1 results in (6 {purpose for which the credit was needed, applicant's checking account status with the bank]. z(") (installment plans from providers other than the credit-giving bank), ATE, = 0.0084 + 0.0008, and ATE, = -0.0046 + 0.0021.
Under the first assumption above, the causal effect using the adjustment formulae in (9) and (10) have same sign and are close in magnitude. However, under the second assumption, the effect flips sign. The results suggest that the second hypothesis regarding b is incorrect, implying that applicant's job may indeed be a direct child of applicant's 's age, which aligns with intuition.
The dataset has only 1000 samples, which increases the possibility of detecting independencies in our criterion by chance, even with the size of constrained. To address this issue, we use 100 random bootstraps with a sample size equal to half of the training data and evaluate the p-value of our conditional independence criteria for all subsets returned by our algorithm. We select the subset z with the highest median p-value (computed over the bootstraps) and use it in our adjustment formulac on a held out test set. To assess the conditional independencies associated with the selected z, we plot a histogram of the corresponding p-values for all these bootstraps. If the conditional independencies hold, we expect the p-values to be spread out, which we observe in the histograms in Figure for the first choice of b. We report similar results for the second choice of b in Appendix G.
We perform a similar analysis on the Adult dataset [Kohavi and Becker, 1996]. With suitable choices of b. Algorithm 1 was unable to find a suitable Z satisfying b Ip y t. This suggests that in this dataset,, there may not be any non-child descendants of the sensitive attribute, which is required for our criterion to hold. More details can be found in Appendix G.
Adult Dataset:

---

b b y/t,
200
1
2/0) 1
1t
count
20
0
0.00 0.25 0.50 0.75 1.00 0.00
0.25 0.50 0.75 1.00 0.00 0.25 0.50 0.75 1.00 p-value
p-value
p-value
Figure 6: Histograms of p-values of the conditional independencies' in (9) and (10) over 100 bootstrap runs for b b= (# of people financially dependent the applicant, applicant's savings, applicant's job).
Conclusion, Limitations, and Future Work
In this work, we proposed sufficient conditions for causal effect estimation through generalized front-door adjustment given structural side information irrespective of the number or complexity of the latent confounders. Our approach can identify causal effect in graphs where known Markov equivalence classes do not allow identification. However, our approach relies primarily on two assumptions: Assumption 2 and Assumption 3.
Assumption 2 plays a crucial role in Theorem 3.2 (see the discussion in Section E.3) as it requires the presence of an unobserved confounder between the treatment variable and the outcome variable. This assumption is necessary for the applicability of our approach. If Assumption 2 does not hold, it implies that there is a set that satisfies the back-door criterion, and existing methods for finding back-door adjustment sets [Entner et al., 2013, Cheng et al., 2020, Shah et al., 2022] can be utilized. This suggests that our results could be derived under the weaker condition that there is an unblockable back-door path between and y. However, many real-world scenarios, the presence of unobserved variables that potentially confound the treatment and the outcome is common, and we expect Assumption 2 to be true.
Assumption 3 is the requirement of knowing the entire set of children of the treatment variable within the causal graph. While this strictly less demanding than specifying the entire causal graph, it may still present practical challenges in real-world scenarios. For instance, in large-scale observational studies or domains with numerous variables, exhaustively identifying all the children may be computationally demanding. It remains unclear whether one can estimate the causal effect using front-door- like adjustment with even less side information, e.g., knowing only one child of the treatment variable or knowing any subset of children of the treatment variable. An important future direction could be to approximate the causal effect when only the children corresponding to weak edges are unknown. Such variations around our condition work. However, until then, one could seek input from domain experts. These experts possess valuable knowledge and insights about the specific domain under study, which can aid in identifying all the relevant variables that serve as children of the treatment.
promising directions for future
The time complexity of Algorithm is exponential due to its search over all possible subsets of observed variables (except t, b, y). While this is inherent in the general case, recent work by Shah et al. [2022] proposed scalable approximation for conditional independence testing using continuous optimization by exploiting the principle of invariant risk minimization, specifically for back-door adjustment without the need for the causal graph. However, extending this approach to multiple conditional independence tests, as required in (7) and (8), remains an open challenge. Therefore. exploring the development of continuous optimization-bar based methods for scalability of front-door adjustment in the absence of the causal graph is crucial. Further, Algorithm could potentially be augmented with ideas from double machine learning and inverse variance weighting for bias and variance reduction.
Lastly, it is important to note that Theorem 3.2 provides only sufficient conditions for causal effect estimation. This means that there may cases where front-door-like adjustment is possible, but the conditions stated in Theorem 3.2 do not hold. Specifically, there could be scenarios, such as when the outcome variable is a child of the children the treatment variable, i.e., y a child of b, where conditions (7) and (8) are not satisfied.
10

---

Acknowledgements
We thank the anonymous reviewers for their comments and suggestions. Murat Kocaoglu acknowledges the support of NSF Grant CAREER 2239375.
References
Acharya, A. Bhattacharyya, C. Daskalakis, and S. Kandasamy. Learning and testing causal models with interventions. Advances in Neural Information Processing Systems, 31, 2018.
R. Addanki, S. Kasiviswanathan, A. McGregor, and C. Musco. Efficient intervention design for causal discovery with latents. In International Conference on Machine Learning, pages 63-73. PMLR, 2020.
M. F. Bellemare, J. R. Bloem, and N. Wexler. The paper of how: Estimating treatment effects using the front-door criterion. Technical report, Working paper, 2019.
R. Bhattacharya and R. Nabi. On testability of the front-door model via verma constraints. In Uncertainty in Artificial Intelligence, pages 202-212. PMLR, 2022.
D. C. Castro, I. Walker, and B. Glocker. Causality matters in medical imaging. Nature Communications, 11(1):1-1,, 2020.
D. Cheng, J. Li, L. Liu, K. Yu, T. D. Lee, and J. Liu. Towards unique and unbiased causal effect estimation from data with hidden variables. arXiv preprint arXiv:2002.1000 2020.
D. Cheng, J. Li, L. Liu, J. Liu, and D. Le. Data-driven causal effect estimation based on graphical causal modelling: A survey. arXiv preprint wxXiv:2208.09500 2022.
T. Claassen, J. M. Mooij, and T. Heskes. Learning sparse causal models is not np-hard. In Proceedings of the Twenty-Ninsh Conference on Uncertainty in Artificial Intelligence, pages 172-181, 2013.
D. Entner, Hoyer, and P. Spirtes. Data-driven covariate selection for nonparametric estimation of causal effects. In Artificial Intelligence and Statistics, pages 256-264. PMLR, 2013.
I. R. Fulcher, I. Shpitser, S. Marealle, and E. J. Tchetgen Tchetgen. Robust inference on population indirect causal effects: the generalized front door criterion. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 82(1):199-2144 2020.
A. N. Glynn and K. Kashin. Front-door sefffrrence-in-diffeeeeee estimators. American Journal of Political Science, 100) 2017.
A. N. Glynn and K. Kashin, Front-door versus back-door adjustment with unmeasured confounding: Bias formulas for front-door and hybrid adjustments with application to job training program. Journal of the American Statistical Association, 113652)):0400-144 2018.
L. Gultchin, M. Kusner, V. Kanade, and R. Silva. Differentiable causal backdoor discovery. In International Conference on Artificial Intelligence and Statistics, pages 3970-3977 3979. PMLR, 2020.
S. Gupta, Z. C. Lipton, and D. Childers. Estimating treatment effects with observed confounders and mediators. In Uncertainty in Artificial Intelligence, pages 982-991. PMLR, 2021.
H. Hofmann. Statlog (German Credit Data). UCI Machine Learning Repository, 1994.
Hünermund and F. Bareinboim. Causal inference and data fusion in econometrics. arXiv preprint /9/2v: 19/2.09944, 2019.
A. Jaber, J. Zhang, and E. Bareinboim. Causal identification under markov equivalence: Completeness results. In International Conference Machine Learning, pages 2981 1-899. PMLR, 2019.
H. Jeong, J. Tian, and E. Bareinboim. Finding and listing front-door adjustment sets. arXiv preprint 1rXiv:2210.053 10.06166, 2022.
Kamiran and T. Calders. Classifying without discriminating. 2009 2nd international conference computer, control and communication, pages 1-6. IEEE, 2009.
11

---

R. Kohavi and B. Becker. UCI machine learning repository, 1996. URL http:://archive.ie. uci. aduumm/dataaset//ddii
M. Kuroki. Selection of post-treatment variables for estimating total effect from empirical research. Journal of the Japan Statistical Society, 30(2):115-128, 2000.
M. Kuroki and Z. Cai. Selection of identifiability criteria for total effects by using path diagrams. arXiv preprint arXiv: 1207.41207 2012.
M. Mogstad and A. Torgovitsky. Identification and extrapolation of causal effects with instrumental variables. Annual Review of Economics, 10:577-613, 2018.
R. Nabi, D. Malinsky, and I. Shpitser. Learning optimal fair policies. In International Conference on Machine Learning, pages 4674-4682. PMLR, 2019.
J. Pearl. [bayesian analysis in expert systems]: Comment: graphical models, causality and intervention. Statistical Science, 8(3):266-269 1993.
Pearl. Causal diagrams for empirical research. Biometrika, $2(4):669-682) 688, 1995.
J. Pearl. Causality, Cambridge university press, 2009.
E. Perkovic, J. Textor, M. Kalisch, and M. H. Maathuis. Complete graphical characterization and construction of adjustment sets in markov equivalence classes of ancestral graphs. The Journal of Machine Learning Research, 2018.
D. Plecko and E. Bareinboim. Causal fairness analysis. arXiv preprint arXiv:2207. 1388,, 2022.
A. Shah, K. Shanmugam, and K. Ahuja. Finding valid adjustments under non-ignorability with minimal dag knowledge. In International Conference Artificial Intelligence and Statistics, pages 5538-5562. PMLR, 2022.
I. Shpitser and J. Pearl. Identification of joint interventional distributions in recursive semi-markovian causal models. Proceedings of the National Conference on Artificial Intelligence, volume 21, page 1219. Menlo Park, CA; Cambridge, MA; London; AAAI Press; MIT Press; 1999, 2006.
Spirtes, C. N. Glymour, and R. Scheines. Causation, prediction, and search. MIT press, 2000.
E. Strobl, L. Spirtes, and Visweswaran. Estimating and controlling the false discovery rate for the algorithm using edge-specific p-values. arXiv preprint arXiv: 1xXi::6607.03775 2016.
E. V. Strobl, P. L. Spirtes, and S. Visweswaran. Estimating and controlling the false discovery rate of the pc algorithm using edge-specific p-values. ACM Transactions on Intelligent Systems and Technology (TIST), 10(5):1-37, 2019a.
E, Strobl, K. Zhang, and S. Visweswaran. Approximate kernel-based conditional independence tests for fast non- -arrmmemttiic causal discovery. Journal of Causal Inference, 7(1), 2019b.
Tian and J. Pearl. general identification condition for causal effects. eScholarship. University of California, 2002.
S. Triantafillou and I. Tsamardinos. Constraint-based causal discovery from multiple interventions over overlapping variable sets. The Journal of Machine Learning Research, 16(1):2147-2205 2015.
V. Veitch and A. Zaveri. Sense and sensitivity analysis: Simple post-hoc analysis of bias due to unobserved confounding. Advances in Neural Information Processing Systems, 13:009,9-11100, 2020.
Verma and J. Pearl. Causal networks: Semantics and expressiveness. In Machine intelligence and pattern recognition, volume pages 69-76. Elsevier, 1990.
M. Wienöbst, van der Zander, and M. Liskiewiez. Finding front-door adjustment sets in linear time. arXiv preprint arXiv:2211.16666 2022.
12

---

J. Zhang. On the completeness of orientation rules for causal discovery in the presence of latent confounders and selection bias. Artificial Intelligence, 172(16617):1873-18886 2008.
Zhang and E. Bareinboim. Fairness in decision-making-ttiee the causal explanation formula. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
13

---

A Broader impact
In this work, we propose algorithm for estimating causal effects from observational studies without relying on expert knowledge of the causal model. Our approach is particularly valuable in scenarios where conducting randomized control trials (RCTs) is challenging unethical, such as in healthcare settings where consensus treatment protocols are often determined based on observational data. While our algorithm shows promise in providing accurate causal effect estimates, it is crucial to address the potential negative impact of incorrect results that may arise from our work.
One significant concern is the possibility of miscalculating the treatment effect due to limitations in testing power at finite sample sizes or the misidentification of certain features as direct children the treatment variable. This introduces the risk of inaccurate estimations, which could have detrimental consequences when making decisions or establishing treatment protocols based on the conclusions derived from algorithm. It is essential approach the interpretation of our algorithm's results with caution and subject them to critical evaluation. It worth noting that the potential for incorrect results not unique to our algorithm but is inherent in most observational studies and effect estimation algorithms. Acknowledging these potential negative impacts emphasizes the need for further research improve the reliability and accuracy of causal effect estimation in observational studies.
B Preliminaries about ancestral graphs
In this section, we provide the definition of partial ancestral graphs (PAGs). PAGs are defined using maximal ancestral graphs (MAGs). Below, we define MAGs and PAGs based on their construction from directed acyclic graphs (DAGs).
A MAG can be obtained from DAG as follows: if two observed nodes and cannot be d-separated conditioned on any subset of observed variables, then (i) xi - X2 is added the MAG if is an ancestor of X2 in the DAG, (ii) X2 - X1 is added in the MAG if x2 is an ancestor of xi in the DAG, and (iil) X1 <-+ X2 is added in the MAG x1 and X2 are not ancestrally related in the DAG. (iv) After the above three operations, if both X1 +-+ X2 and X - X2 are present, we retain only the directed edge. In general, MAG represents collection of DAGs that share the same set of observed variables and exhibit the same independence and ancestral relations among these observed variables. is possible for different MAGs to be Markov equivalent, meaning they represent the exact same independence model.
PAG shares the same adjacencies as any MAG in the observational equivalence class of MAGs. An end of an edge in the PAG is marked with an arrow (>> or <) if the edge appears with the same arrow in all MAGs in the equivalence class. An end of an edge in the PAG marked with a cirele (o) if the edge appears as an arrow (> or <) and a tail (-) in two different MAGs in the equivalence class.
C Rules of do-calculus
In this section, we provide the do-calculus rules of Pearl [1995] that used to prove our main results in the following sections. We build upon the definition of semi-Markovian causal model from Section 2.
For any v E W, let Gv be the graph obtained by removing the edges going into v in G, and let Gy be the graph obtained by removing the edges going out of in G.
Theorem C.1 (Rules of do-caleulus, Pearl [1995]). For any disjoint subsets V1, V2, V3, V4 C W, we have the following rules.
Rule 1: PVyi (do())), V3, v4) (do)())(( Vz)
i/v Il valu2, Vo in Goz-
Rule 2: PPV1 (Vo()) V3. do(w)))) (VV)) V3. Ma)
if IL. V1lV2, V3 in Guave.
Rule 3: PV (V))))); V3, do(w))) P(v, va)
if U V3 G (va)'
where va(v3) the set of nodes in v that are not ancestors of any node in Va in Gug. Pearl [1995] also gave an alternative criterion for Rule 3.
Rule 3a: PP(1 ( V3. do(v))) = IP(vildo(v) vs)
ifv1 Ma. Fv, V22 V3 in Gh.
14

---

where g is the graph obtained from 9 after adding (a) a node Fv,, and (b) edges from Fv, to every node Va.
Also, throughout our proofs, we use the following fact.
Fact 1. Consider any G' obtained by removing any edge(s) from G. For any sets of variables M1, V2, Ma W. if Mi and va are d-separated by Vy in G than Vi and V2 are d-separated by Va G'.
D Causal Identifiability
In this section, we derive the causal effect for the SMCM in Figure 3(to)), i.e., (6), well as prove Theorem 3.1 one by one.
D.I
Proof of (6)
First, using the law of total probability, have
P(y do(t 1))
Σ
P(y|do(( 21, == (12)
#1:22
Now, we show that the two terms in RHS of (12) can be simplified as follows
P(y|do(t t), 21, 22 =2) Σ
P(y|z 21, Z2 22, (')
(13)
P(z: = 21, 2ッ |d = t)) = >
P(z 22 b = b) = = -
(14)
Combining (12) to (14) results in (6).
Proof of (13): We have
P(y|do(t t), 21 = 21, =2
(15)
(g) P(y y do t = =
(16)
P(y yldo( = - do bb)
(17)
( P(y = =1, b2 b))
(18)
Σ Ply , do (1=
b))
(19)
1'
(c)
> Ply t= = =1, =1) = do = b))
(20)
e'
(
Ply- , t = do b))
(21)
P(y -2, t = Zl = =1),
(22)
where (a) and (f) follow from Rule (b) follows from Rule 2, (c), (e), and (g) follow from Rule 3a, and (d) follows from the law total probability.
Proof of (14): From the law of total probability, have
P(2 =1 Zz 22 do( t))
(23)
Σ
P(z = 2o =2
do({ 2z
t), b bbP = bjdo(t= t))
(24)
b
(a)
Σ P(zz=22 2o( = t), b= - b)T /o t), b z P bldo(t t)) (25)
15

---

(
1 -b=== bldo(t t))
blo(t = t))
(26)
b
(27)
(
[1 b-
(28)
b
(c)
Σ
P(zz -1z2=2211 b|] -
- -b bldo(t (), =
(29)
P(zz= 22 b b)p 21 |P bldo(t 1), 21 21)
(30)
( Σ
21 (2 = b b b b = = b|
(31)
b
where (a), (d). and (e) follow from the definition of conditional probability, (6) and (f) follows from Rule 3a, (c) follows from Rule 1, and (g) follows from Rule 2.
D.2 Proof of Theorem 3.1
Let An(y) denote the union of y and the set of ancestors of y, and let GAuly) denote the subgraph of G composed only of nodes in An(y). First, we show that if b Ia yit, holds for some z, then there is no bi-directed path between t to b in G'A(y),
Lemma 1. Suppose Assumptions to 3 hold. Suppose there exists a set S V {t, b, such that d y|t, z. Then, there is no bi-directed path between and gAuly),
Given this claim, Theorem 3.1 follows from Tian and Pearl [2002, Theorem 4]. It remains to prove Lemma 1.
Proof of Lemma 1. We prove this result by contradiction. First, from Assumptions and I E An(y) and by E An(y) for some bu C b. Assume there exists bi-directed path between r and some b E bu in Am(y), Let (tt b) denote the shortest of these paths. This path is of the form f 4-+ V1 +-+
+++ V, <-+ b for some 2 0 where Vi E gA(ry) for every q E [r]. We have the following two cases depending on the value of r.
(i r= 0: In this case, consider the path Ply, b) S P(e, b) in G of the form: y +-+ t +-+ in G (such a path exists because of Assumption 2). The path Ply, b) is unblocked when and z are conditioned on contradicting di ylt.z.
(ii
1: In this case, consider the path P(y, y +-+ t +-. V) 4-+ ... +-+ +-+ b (such a path exists because of Assumption 2). We have the following two scenarios depending on whether the path P(y, b) is unblocked or blocked when f and z are conditioned on. Suppose we condition on f and z.
P(t, in G of the form:
(a) The path P(y, v,, b) is unblocked: In this case, by assumption. b bTد y t, is contradicted.
(b) The path P(y, b) is blocked: We create set such that for any w E w the following are true: (a) w = V, for some g E [r]. (b) w & z, (b) there is no descendant path and some E z, and (c) there no descendant path P(w, , t)
P(w,z) 2) between
between w and t.
In this scenario, w * 0 because P(y, b) is blocked. Let we E w be that node which is closest to b in the path P(y, b). By the choice of we, the path P(we, b) C P(y, b) is unblocked (when t and z are conditioned on). Furthermore, by the definition of w, (a) We E Ggnnrr) (because w. = Vy for some E [r)) and (b) there exists a descendant path P(We, y) between w. and y such that & PP(w,, well & P y) for every z E z. Therefore, the path P(w y) is unblocked (when t and z are conditioned on). Consider the path P' b) obtained after concatenating P(W.: y) and P (We, b) at w.- This path is unblocked (when and are conditioned on) because: (a) P( b) is unblocked, (b) (Wc.: y) unblocked, and (e) there is no collider at w. in this path (because P (We,)) y) is descendant path to y). However, this contradicts b la ylt,z. z.
16

---

E A generalized front-door condition
In this section, we prove Theorem 3.2. We begin by stating few d-separation statements used in this proof. See Appendix F for a proof.
Lemma 2. Suppose Assumptions I to and d-separation criteria in Theorem 3.2, i.e. (7) and (8), hold. Then,
(a) y a Fe|z, b in oh and y a Felz! b in %
(b) t ILd b in Gz.
(c) PTt 2 in g
(d) t LL Fb (0) in gb, and
(e) y a z() in 9b.
Now, we proceed with the proof in two parts. the first part, we prove (9), and in the second part, we prove (10).
E.1
Proof of (9)
First, using the law of total probability, we have
P(y = y do(( = ()) = Σ P(y = y yldo(( = 1),
== = =) = 2|do(t= = 1)).
(32)
Now, we show that the two terms in RHS of (32) can be simplified as follows
P(y = y do t), z 2) = Σ
Ply = =
(33)
1'
P(z = 2 do(( - ()) = Pz 2 1),
(34)
Combining (33) and (34) completes the proof of (9).
Proof of (33): We have
Ply = y/do(t = z),z=23
P(y = do(t = t), z 2, b-b
= b)
(35)
Pyy y do(t t), z, do b))
(36)
PPyy = y z, do b))
(37)
Σ Ply 5/1 z, do b), t t') = f'|z z, do b)),
(38)
where (a) follows from Rule 1, (7), and Fact 1, (b) follows from Rule 2, (7), and Fact 1, and (c)
follows from Rule 3a and Lemma 2(a), and (d) follows from the law of total probability.
Now, we simplify the first term in (38) as follows:
P(y = y/z = z, do = b), t = t')
P(y = 8/z z, b b b,t=t))
(39)
Ply = y|z 2, =,t=t',
(40)
where (a) follows from Rule (7), and Fact Likewise, we simplify the second term in (38) as follows:
P(t = l'ddo = b), z = =) (a) P( = l')do(b = b), (0) = -0) (b) P( = ('|z = 2(0) (41)
(c) P(t = t'),
(42)
17

---

where (a) follows from Rule 1, (8), and Fact 1, (6) follows from Rule 3a and Lemma 2(d), and (c)
follows (8).
Putting together (38), (40), and (42) results in (33).
Proof of (34): From the law of total probability, have
P(zz = z do = t)) Σ Piz z|do(t b= b) bldo(t t)).
(43)
Now, we simplify the first term in (43) as follows:
Pz z z|do(t 1), b)
(44)
( P(z = z (0) |do(t = t), b b) P(z =00 b- = 20)
(45)
( Piz(() 20)) |do(t t), p))((( 2 t, b,z 2()
(46)
@ P(z()) (6) z 20 = t, b -
b) b) P(z ( = f, b = b. zd = =x 21)
(47)
Piz 2|t 1.b b).
(48)
where (a) and (d) follow from the definition of conditional probability, (b) follows from Rule 2, (8), and Fact 1, and (c) follows from Rule 2 and Lemma 2(c). Likewise, we simplify the second term in (43) as follows:
IP bldo(t t)) P(b b/t t),
(49)
where (a) follows from Rule 2 and Lemma 2(b).
Putting together (43), (48), and (49), results in (34) as follows:
Piz = z <do = t)) Σ P(z = 2/t = t. b- b) b = (0)
P(z = z/t = t),
(50)
b
where (a) follows from the law of total probability.
E,2
Proof of (10)
First, using the law of total probability, we have
P(y do = t)) Σ Ply vldo(t = f),b b)P(b bldo(t t)).
(51)
Now, we show that the first term in RHS of (51) can be simplified as follows
P(y = y do
t),b b b)
(52)
Σ
=0 -b b,t=t). t)).
(53)
261
where s (b, z (.). Using (49) and (53) in (51), completes the proof of (10) as follows:
P(y = y/do = f))
(54)
Σ Σ
Fly y/s -,== ())(= (()))((2)))) =0 b, t L)I blt =
(55)
Σ Σ Ply = y = s.t=tt)P(t 14) P(s= s|t=
(56)
where (a) follows from the definition of conditional probability.
18

---

Proof of (53):
From the law of total probability, we have
Ply = v|do(t = t). b b)
(57)
Σ Ply y/b b, =z) do(( =z000 b, do(t t)).
(58)
2(1)
Now, we simplify the first term (58) as follows:
P b = b, z (0)) do(t = 1))
(59)
(a) P(y y do(b b), (
=t))
(60)
( P(y y/do(( b), z( = 2²()
(61)
Fly - b), (0) =1(") =t)P(t I'Ido(b b), =z 20)),
(62)
where (a) follows from Rule Lemma 2(e), and Fact 1, (b) follows from Rule and Lemma 2(a),
and (c) follows from the law of total probability. We further simplify the first term in (62) follows:
P(y = yjdo b), (0) 10) (() (a) Ply = y/b b, (()) = =- 1),
(63)
where (a) follows from Rule 2 and Lemma 2(e). Using (63) and (42) in (62), have
P(y y/b b, ( = 20) 20))d((o do(t t)) Σ Ply = y/b b, z 20, t') =t) t'), (64)
Now, we simplify the second term in (58) as follows:
P(z 2z()) b do(t t))
(a) P(z()) =0 b, t).
(65)
where (a) follows from Rule 2 and Lemma 2(c).
Putting together (58), (64), and (65) results in (53).
E.3 Necessity of Assumption 2
In this section, provide an example signify the importance of Assumption 2 to Theorem 3.2. Consider the semi-Markovins causal model in Figure 7 where Assumptions I and 3 hold but Assumption does not hold.
t
Z
y
Figure 7: An SMCM signifying the importance of Assumption 2
While z ((0)(()) satisfies (7) and (8) where z(i 0. the causal effect is not equal to the formulae in (9) or (10). To see this, we note that the set {a} is back-door set in Figure implying
P(y do(: = =t) Σ P(yla, P().
(66)
Now, we simplify the right hand side of (66) to show explicitly that it not equivalent to (9). From the law of total probability, we have
P(y = Σ P(y|z, t)
(67)
19

---

(a
Σ
Σ e'
P(y|z, a, t))(())) P(z t) (0) Σ Σ P(yzz, t))(t)) P(z t), (68)
where (a) follows because Eg P(()) and (6) follows y is independent of every other variable
conditioned on Plugging (68) in (66), we have
P(y|do((t t)) - (((yZE)))()) (Σ (P(
(69)
Lastly, using the law of total probability, (9) can be rewritten as
P(y|do(t = t)) ( Plylz, C (2 P(z)a, t)Paatt.
(70)
Therefore, the variables and t could be such that (69) is different from (70). We note that similar steps can be used to show that (66) is not equivalent to (10). In conclusion, Assumption 2 is crucial for the formulae in (9) and (10) to hold.
F Proof of Lemma 2
First, we state the following d-separation criterion used to prove Lemma 2(b) and Lemma 2(d). See Appendix F.1 for proof.
Lemma 3. Suppose Assumptions 1 to 3 hold. Then, t PLt b/z(*) in Gc-
Now, we prove each part of Lemma 2 one-by-one.
Proof of Lemma 2(a) In L all edges going into b are removed. Under Assumption 3, this implies that all edges going out of are removed. Now, consider any path P(Fr, y) between Fr and y in of This path takes of the following two forms: (a) F, - .... y or (b) F, - +-+ ... y. In either case, there is a collider at t in P(Ft, y). This collider is blocked when z and b are conditioned on because & z, & b, and t does not have any descendants in Of Therefore, y lL Filz, b in of
Similarly, the collider is blocked when (0)) and b are conditioned on because t & (()) & b, and t does not have any descendants in Gf Therefore, y a F, b in gz
Proof of Lemma 2(b) We prove this by contradiction. Assume there exists at least one unblocked path between t and some b E in Gr. Let Ptt, b) denote any such unblocked path.
Suppose we condition on z z0), From Lemma 3, (rt, , b) is blocked in Gg when 2 is conditioned on. Let be any node which P(t, b) is blocked in G. when z is conditioned on. We must have that E P(t, b) \ (r, b} and v ( Then, the path P(t, v) C P(t, b) is unblocked in 9g when 2 is unconditioned on. However, this contradicts t I1 (6) in G. (which follows from (8) and Fact 1).
Proof of Lemma 2(c) We prove this by contradiction. Assume there exists at least one unblocked path between t and some z(6) E z(0) in Og when b is conditioned on. Let P(t, 2()) denote any such unblocked path.
Suppose, we uncondition on b. From (8) and Fact I, we have d ( in Gg. Therefore, P(t, 20) blocked in G. when b is unconditioned on. Now, we create a set v consisting of all the nodes at which (()) is blocked in Ge when b is unconditioned on. Define the set v such that for any the following are true: (a) v E P(t, 2()) \ (t, 2(0), }. (b) P(t, z()) contains a collider at v in Gr and (c) there exists an unblocked descendant path from v to some
in Gt-
Now, we must have v A since P(t, is blocked G. when b is unconditioned on. Let v. E V be that node which is closest to I in the path P(t, 2())), ), and let P(ve, b) be an unblocked descendant path from to some b b in G. (there must be from the definition of the v). Consider the
path Ptt. b) obtained after concatenating P(t, v.) C P(t, ((0) and P(ve, b). By the definition of
and the choice of V., Ptt, b) is unblocked in Ge since (a) P(t, v.) is unblocked in G., (b) P(ve, b) is
unblocked in Gr, and (c) there no collider at v. in P(t, b). However, this contradicts 1l in G. (which follows from Lemma 2(b)).
20

---

Proof of Lemma 2(d) We prove this by contradiction. Assume there exists at least one unblocked path between t and Fi in go when (+0) is conditioned on. Let P(t, Fb) denote the shortest of these unblocked path. By definition of go, this path has to be of the form: t.... 4- Fb for some b E b. Now, we have the following three cases:
(i P(t, Pb) contains t - b: In this case, because path is a sequence of distinct nodes, P(t. Fb) has to be r - b <- Fb. By assumption, Pt., F%) is unblocked when z(t) is conditioned on. Since there is collider
in P(t, Fb). there exists at least one unblocked
descendant path from b to z when (0) is conditioned on. Let P(b, z(0) denote the shortest of these paths from b to some 2(1) E 20)) go. We note that this path also exists in G and is of the form b -
z(8)
Suppose we uncondition on f0) Consider the path P(t, S P(b, 2() between t and (6) of the form f -> - ... -> ( in G. This path remains unblocked even when 2(0) is unconditioned on as it does not have any colliders. This contradicts (1)) d t (which follows from (8)).
(ii) P(t, Fb) contains t - b, for some bi E such that bj * b: this case, the path P(t, Fb) has to be of the form f -> bj ... b x- Fb- Therefore, there exists at least one collider on the path P(,, Fb). Let v E P(t,, Fb) \ {t, Fb) be the collider on the path P(t, Fb) that closest to bj. Consider the path P(t, v) C P(t, Fb). We note that this path also exists in G V.
and is of the form - bj -
By assumption, P(t, Fb) is unblocked when z (() is conditioned on. Since there is collider at v in Ptt, Fb). there exists at least one unblocked descendant path from to z when
z ( is conditioned on. Let P(v, z0)) denote the shortest of these paths from v to some 20) E E(()) in G. We note that this path also exists in G and is of the form -
2(i)
Suppose we uncondition on 20) Consider the path P(e, 2(0) between t and 2( in g obtained after concatenating P(t, v) C Ftt and P(v, 2()).. This path, of the form
t bj -.... v - > z((), remains unblocked even when ((() is unconditioned it does not have any colliders. This contradicts z(t) 11. (which follows from (8)).
(ii) Pt. Fb)) does not contain - b for every b E By assumption, P(t, Fb) unblocked in gb when z(i) is conditioned on. Therefore, if P(t, Fb) does not contain the edge t ->> b, for any bi E b. there exists a path P(t, b) between to b in G that is unblocked when z() is conditioned on, and takes one of the following two forms:
(a) +- b (b) b. Then, easy to see that the path Ptt, 6) also remains unblocked G. while 20 is conditioned on. However, this contradicts t Il.a b)z(() in G, (which follows from Lemma 3).
t +-+ b.
Proof of Lemma 2(e) We prove this by contradiction. Assume there exists at least one unblocked path between y and some b b in Gb when and z(() are conditioned on. Let P(b. y) denote the shortest of these unblocked path. Therefore, no b, E b, such that b, * b, is on the path P(b. y). i... b, P(b, y). Further, P(b,y) y) takes one of the following two forms because all the edges going of b are removed in Gp: (a) b f-... ........ (b) b +-+ .....
Suppose we condition on 2()) (while t and ( are still conditioned on). From (7) and Fact 1, we have Ma blt, z in Gg. Therefore, the path P(b, y) is blocked in G, when 2(() conditioned on (while t and ( are still conditioned on). Let v be any node at which P(b, y) is blocked in Go when z!o) is conditioned on (while t and (+() are still conditioned on). We must have that E P(b, y) (y, b} and v E 2(o)_ Suppose we uncondition on 20)) (while t and 2() are still conditioned on). Then, the path P(b, v) C y(b,y) is unblocked in Go.
We consider the following two scenarios depending on whether or not P(b, v) contains t. In both scenarios, we show that there is an unblocked path between and v in Gp when we condition on (while t and (i) are still conditioned on).
(i) P(b, v) contains t: Consider the path P(t, v) C P(b, v) which is unblocked in Gb when t and z(! are conditioned on. Further, by the choice of P(b, y), no bi E b is the path
21

---

P(t, v). Therefore, the path P(t, v) in Gb remains unblocked when we condition on (while and z(t) are still conditioned on).
iii P(b, v) does not contain t: Consider the path P(t, v) > P(b, v) (by including the extra edge t b) which takes one of the following two forms: (a) + b b v or (6) t - b +-+ v. Further, by the choice of P(b, y), no bj E b (bi + b) is on the path P(t, v). Suppose we condition on (while t and z(() are still conditioned on). Then, the path Ptt, v) 9, is unblocked because (a) the collider at b is unblocked when b is conditioned on and (b) the path P(b, v) in Gb remains unblocked when b is conditioned on (while and ((0 are still conditioned on).
Now, suppose we uncondition on t (while and 2 are still conditioned on). We have the following two scenarios depending on whether not Ptt, v) in G remains unblocked. In both scenarios, show that there is an unblocked path between and v in 9. when we uncondition on t (while b and z! (8) are still conditioned on).
1. If (t,, v) remains unblocked: In this case, P(t, v) in Pb is unblocked path between and when 2(() and b are conditioned on, as desired.
2. If P(t, v) does not remain unblocked: In this case, it is the unconditioning t (while b and z(t) are still conditioned on) that blocks P(t, v). Now, we create set w consisting of all the nodes at which Ptt. v) is blocked in Gb when t is unconditioned on (while b and ( are still conditioned on). Define the set w such that for any w E w, the following are true: (a) W E Ptt, v) {t, v). (b) P(t, v) contains collider at in Gp. and (c) there exists an unblocked descendant path from W to t in Gg.
Now, we must have w j 0, since P(t, v) is blocked in 9b when is unconditioned on (while b and z(() are still conditioned on). Let E w be that node which is closest to in the path P(t, v), and let P(we. t) be an unblocked descendant path from We to in Go (there must be one from the definition of the set w). Consider the path P'(v, t) obtained after concatenating P(v, w.) C P(t, e, v) and P(We: t). By the definition of w and the choice of w.. P'(v, t) unblocked Gb when t is unconditioned on (while and z(() are still conditioned on) since (a) P(v, W.) is unblocked, (b) P.w... t) is unblocked, and (c) there is no collider at we in P'(v, t). Therefore, we have an unblocked path between t and v in Go when (1) and b are conditioned on, as desired.
To conclude the proof, we note that the existence of an unblocked path between and v E 2(() in Go when (6) and b are conditioned on contradicts z(o) Il. r/b, z(0) Go (which follows from (8) and Fact 1).
F1 Proof of Lemma 3
First, we claim t a b/z in Gr. We assume this claim and proceed to prove the statement in the Lemma by contradiction. Assume there exists at least one unblocked path between t and some b E b in Ge when (60 is conditioned on. Let Ptt, b) denote the shortest of these unblocked path. Therefore, no b such that b, # b not on the path P(t, b), i.e., by & P(t, b).
Suppose we condition on (()) (while z is still conditioned on). From the claim, P(t, b) is blocked in 9g when 2(o) is conditioned on (while z is still conditioned on). Let be any node which P(t, b) is blocked in 93 when z(o) is conditioned on (while z(t is still conditioned on). We must have that v E b) \ {t, b} and v E 2(0), Then, the path P(t, v) C P(t, b) is unblocked in Ge when 2 is unconditioned on (while ( is still conditioned on). Further, no b E b is on the path P(t, v). As a result, the path P(t, v) remains unblocked when b is conditioned on (while (8) is still conditioned on). However, this contradicts t 11 [ b (0) in Gg (which follows from (8) and Fact 1).
Proof of Claim IL. bjz in G:: It remains to prove the claim IL. b/z in Gr. We prove this by contradiction. Assume there exists at least one unblocked path between t and some b E b in G. when z is conditioned on. Let P(t, b) denote any such unblocked path. This path takes one of the following two forms: (a) t- b or (b) t ... because all edges going out of are removed in G..
22

---

Suppose we condition on (while z is still conditioned on). The path P(t, b) remains unblocked because & P(t, b) (a path is a sequence of distinct nodes). Then, the path P(y, b) P(t. of the form (a) +-> t f- ... b..bo or (b) +-+ t 4-+ ... b is unblocked because the additional conditioning on (while z still conditioned on) unblocks the collider However, this contradicts b a ytt, z in Ge (which follows from (7) and Fact 1).
G Experimental Results
In this section, we provide additional experimental results. First, we provide more details regarding the numerical example in Section 3.1. Next, demonstrate the applicability of our method class of graphs slightly different from the one in Section 4.1. Then, we provide the 6 random graphs from Section 4.2 as well as ATE estimation results specific choices of SMCMs including the one in Figure 2. Finally, we provide histograms analogous to Figure for the second choice of b on German credit dataset well details about our analysis with Adult dataset.
G.1 Numerical example in Section 3.1
The observed variables for this example also follow the structural equation model in (11). Also, to generate the true ATE, we intervene on the generation model in (11) by setting t = 0 and t = 1.
G.2 Applicability class of random graphs
As in Section 4.1, create class of random SMCMs, sample 100 SMCMs from this class, and check if (7) and (8) hold by checking for corresponding d-separations in the SMCMs. The class of random graphs considered here is analogous to the class of random graphs considered in Section 4.1 expect for the choice of t. Here, we choose any variable that is ancestor of y but not its parent as This is in contrast to Section 4.1 where choose any variable that is ancestor of y but not its parent or grandparent as t. We compare the success rate of the same two approaches: (i) exhaustive search for z satisfying (7) and (8) and (ii) search for of size at-most satisfying (7) and (8). We provide the number of successes of these approaches as a tuple in Table 2 for various p. d, and As before, we see that the two approaches have comparable performances and the IDP algorithm gives successes across various p. d, and even though it is supplied with the true PAG. Also, as expected the number of successes for this class of graphs is much lower than the class considered Section 4.
Table Number successes out of 100 random graphs for our methods shown as a tuple. The first method searches exhaustively and the second method searches with size at-most 5.
p 10
15
d=
2
d=
3
d= 4
d=2
2
d=3
d 4
0.0
(6, 6)
(3,3)
(1,1)
(11,
(2
11,1)
0.5
(3,3)
(0.0)
(0.0)
(5,5)
(2,2)
(1,1)
1.0
(1,1)
(0.0)
(0.0)
(1,1)
(0.0)
(0.0)
G.3
ATE estimation
We also conduct ATE estimation experiments on four specific SMCMs. The first SMCM is the graph gloy in Figure 2. The remaining graphs, named Gioy i {1, 2,3), are shown in Figure 8, and are obtained by adding additional edges and modifying giov. These SMCMs are designed in a way such that there exists z = (z(), ooo) satisfying the conditional independence statements in Theorem 3.2.
We follow data generation procedure similar to the one in Section 4.2. In contrast, we show the performance of our approach for a fixed n but different thresholds of p-value p.. We average the ATE error over 50 runs where in each run we set 50000. As we see in Figure 9, both the ATE estimates returned by Algorithm I are far superior compared to the naive front-door adjustment using b.
23

---

X1
X2
X1
2
2
Figure 8: The causal graphs used further validate our theoretical results. These are obtained by adding additional edges (shown in red) to G in Figure 2. We denote these graphs (from left to right) by G1md .g and G33 respectively.
average ATE error
0.15
0.3
average ATE
0.10
0.2
0.25
0.25
average ATE error
0.20
0.200
average ATE
0.15
0.15
0.10
0.05
0.00
0.00
boseire 0.00 0.1 0.15 0.2 0.2
0.05 033 0.35 0.2
0.25
baodine
0.06
0.1 0.15 0.2 0.25 0.55 0.1 0.15 0.2 0.25 Eshasstive.
Edhatative,
Ectauntive
Edhauative.
Figure 9: Performance of Algorithm for different p p-value thresholds Pa grog in Figure 2 on top left, on gloy from Figure 8 on top right, go in Figure on bottom left, and on g from Figure on bottom right
In Figure 11, we provide the random SMCMs used in Section 4.2. mentioned in Section 1, we choose the last variable in the causal ordering y and variable that is ancestor of y but not its parent or grandparent as t. We also show the corresponding z = (z()) z(()) satisfying (7) and (8).
G.4 German Credit dataset
As in Section 4.3, we assess the conditional independence associated with the selected Z for the choice of b (# of people financially dependent on the applicant, applicant's savings), Algorithm I results in (6) purpose for which the credit was needed, applicant's checking account status with the bank) via 100 random bootstraps. We show the corresponding p-values for these bootstraps in histogram in Figure 10 below. As expected, observe the p-values to be spread out.

---

p g/t,
2
1 pt
2/0)
1 2d/2/
40
count
20
0.00 U.25 0.50 0.75 1.00 0.00 0.25 0.50 0.75 1.00 0.00 0.25 0,50 0.75 1.00 p-value
p-value
p-value
Figure 10: Histograms of p-values of the conditional independencies (9) and (10) over 100 bootstrap runs for b - of people financially dependent on the applicant, applicant's savings), Algorithm results in z = {purpose for which the credit was needed, applicant's checking account status with the bank).
G.5 Adult dataset
The Adult dataset [Kohavi and Becker, 1996] is used for income analysis where the goal predict whether an individual's income is more than $50,000 using 14 demographic and socio-economic features. The sensitive attribute the individual's sex, either male or female. Further, the categorical attributes are one-hot encoded. As with German Credit dataset, we apply Algorithm I with
100
and P. = 0.1 where we search for set Z = (z(n), (())) of size at most 3 under the following two assumptions on the set of all children b of (1) (which includes wife/husband)) and (2) wife/hushand), individual's occupation). In either case, Algorithm was unable to find suitable satisfying b -p y/z. t. This suggests that in this dataset, there may not be any non-child descendants of the sensitive attribute, which required for our criterion to hold.
{# individual's relationship status (# individual's relationship status (which includes
G.6 Licenses
In this work, we used a workstation with an AMD Ryzen Threadripper 3990X 64-Core Processor (128 threads in total) with 256 GB RAM and 2x Nvidia RTX 3090 GPUs. However, our simulations only used the CPU resources of the workstation.
We mainly relied the following Python repositories (a) networkx (https: http::://newwortee org), www.aalleaaam.rddaaaaaeeeaaaaaaa
(b) causal-learn
al., 2019b] and (d) ridgeCV, (https://githuu. com io/en/latest/), (c) RCoT [Strobl 15a949460/ sklllle earnn harnnliin lileerrrrr.rr saaeeaarmoeeee_rrdddee py). We did not modify any of the code under licenses; we only installed these repositories as packages.
In addition to these, we used two public datasets (a) German Credit dataset (Attps://archit) ics uci, edu/ml/ httmm//aaaaattttttaaatoooo/ / //archive. ics. uci., http///lddaaattss/////aa adult). These datasets are commonly used benchmark datasets for causal fairess, which is why chose them for our comparisons.
and (b) Adult dataset (https:
25

---

XL
(
X-
4
b
200
XL
(0
Figure 11: The SMCMs used in Section 4.2 to compare Algorithm with the Baseline that uses for front-door adjustment. These are the out of the 100 random graphs in Section 4.1 for 10, d = 2, and y 1.0 where our approach was successful indicating existence of z (z()) 2(0) such that the conditional independence statements in Theorem 3.2 hold.
26


Reviews:
[{"review_id": "x9Wj0rUdXe", "reviewer": "Reviewer_ZMBw", "summary": "This paper proposes a method for estimating causal effects between the treatment variable and the outcome variable using front-door adjustment beyond the Markov equivalence class. This method is applicable when there are unobserved confounders between the treatment and outcome variables and does not require knowledge of the entire causal graph, but only limited graph knowledge. The authors introduce three assumptions and the causal identifiability theorem and the generalized front-door condition to achieve the estimation of the Average Treatment Effect (ATE). Through experiments, the paper demonstrates that the proposed framework provides identifiability in random fusion compared to PAG-based algorithms, exhibits lower error rates in ATE estimation compared to baseline, and shows practical applicability in causal fairness analysis.", "questions": "See above.", "limitations": "N/A", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The authors propose testable conditional independence statements for front-door-like adjustment without graph knowledge under limited structural side information.\n- The experimental results show that the proposed method is effective on random graphs and real causal fairness benchmarks.", "weaknesses": "- It seems that the identification of the proposed method highly depends on Assumption 3. Assumption 3 requires knowledge of all direct descendant nodes $b$ of the treatment variables, which is too strong and difficult to achieve in practical scenarios.\n- Compared to PAG-based algorithms, the proposed method in this paper proves its ability to effectively provide identifiability. However, it requires expert knowledge to provide structural information, which may not necessarily demonstrate better applicability than PAG-based methods.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable feedback and time. Below, we respond to their comments:\n\n1. **Assumption 3 requires knowledge of all direct descendant nodes**: \n\nWe agree with the reviewer that requiring the knowledge of all the children of the treatment variable is crucial for our method. An important future direction could be to alleviate this requirement, say, to knowing only a subset of the children. For example, one could think of approximating the causal effect when only the children corresponding to weak edges are unknown. Such variations around our condition are promising directions for future work. We will append this to the discussion on Assumption 3 in the limitations section (Appendix A.2).\n\n2. **Comparing the applicability of our method to PAG-based methods**: \n\nWe thank the reviewer for bringing up this great point. We agree that in scenarios where the structural side information is not available, we may have to resort to PAG-based methods. We will clarify this in the revised version. Additionally, we note that the FCI algorithm (that produces a PAG) involves a sequence of adaptive conditional independence (CI) tests where the choice of the next test depends on the previous ones. Specifically, orientation stages tend to propagate errors in non-trivial ways (for example, https://arxiv.org/pdf/1607.03975.pdf shows how to handle these for the PC algorithm which has only three orientation rules). This gets very involved for the FCI algorithm which has many orientation rules and makes it difficult to control the false discovery rate for PAG based methods. In contrast, the CI tests involved in our method could be carried out in parallel and therefore require little-to-no adaptivity. Thus, our method can be viewed as a way to mitigate the issues associated with adaptive testing by using structural side information.\n\n--- \nWe hope that our response addresses the reviewer's concerns and that they would consider increasing their score."}, {"review_id": "n6EaZG9OpD", "reviewer": "Reviewer_amuY", "summary": "The paper investigates the problem of estimating the average treatment effect of variable \"t\" on variable \"y\" within the Pearlian framework. The paper proposes an algorithm that enables causal effect estimation using a front-door-like criterion while relying on only a limited knowledge about the underlying graph structure.\n\nThe core of the algorithm lies in the search for a subset of obserables \"z\" that satisfies a series of independence criteria, thereby establishing a front-door-like formula using \"z\". The proofs employed in the paper leverage the do-calculus and the identifiability criterion of Tian and Pearl. In addition to its theoretical contributions, the paper also presents empirical demonstrations of the proposed approach across three distinct categories: (1) random Structural Causal Models; (2) synthetic data; and (3) real-world fairness benchmarks.", "questions": "As pointed out by the authors, Assumption 2 is mandatory for the approach to work. This observation is not surprising but somewhat disheartening. It would be valuable to explore if there are any workarounds or alternative approaches to testing this assumption, possibly utilizing Confidence Interval (CI) tests. Given that the available knowledge is limited to only the children of \"t,\" I am not sure if this is possible to test. Further exploration or discussion on potential alternatives or extensions to address this limitation would enhance the paper's robustness.\n\nRegarding the choice of the random class of graphs for the benchmark, it would be beneficial to have an explanation or justification provided in the paper. Understanding the rationale behind the class of graphs considered would provide more insights.\n\nI also suggest to provide a more detailed description of Algorithm 1 in the main paper, as that would enable readers to have a better understanding of the algorithm.", "limitations": "The primary limitation of the paper, in my opinion, is regarding the completeness of the algorithm. The fact that the proposed algorithm is not complete represents a significant drawback. A complete algorithm would have provided a more robust and comprehensive solution to the problem.\n\nAs explained in the paper, Assumption 2 is crucial in order for the search to work which is another crucial downside of this approach.  This reliance on a critical assumption may limit the generalizability of the approach to real-world scenarios where such assumptions may not hold.  Indeed, I feel like finding a workaround or alternative approach to mitigate the reliance on Assumption 2 would greatly enhance the paper's technical as well as practical value.\n\nI believe issues regarding sample complexity are out of the scope of the paper and perhaps be considered for future work.", "rating": 5, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper addresses an important problem in the field of causality research by examining the limitations of existing algorithms for causal effect estimation. It specifically aims at improving on the assumption of having access to the underlying causal graph, which is often not readily available. The main contribution of the paper is the introduction of a method for identifying a set of observables 'z' that enables the generation of a front-door-like formula, thereby improving causal effect estimation under limited graph availability. \n\nThe paper presents a clear problem statement and provides well-presented proofs. By offering an alternative perspective on causal effect estimation, the paper provides valuable insights for tackling this challenging problem.  Overall, the paper makes a meaningful contribution to the field and opens avenues for further research.", "weaknesses": "One potential weakness of the paper is that once the requirement of designing a subset \"z\" satisfying the front-door-like criterion (Eqn (9)) is fixed, the proofs and the proposed independence criteria are relatively straightforward and achievable using the rules of do-calculus and the identifiability criterion.\n\nIt is also not convincing to me how and why the exhaustive search runs fast for the random class of graphs generated in Section 4.1.  The expected number of unobservables is of the order O(p), I am curious to know why the bidirected edges are chosen with probablity q/p?  It would be convincing to see positive results for larger p with more unobservables.\n\nThe in-completeness of the proposed algorithm and the mandatory requirement of Assumption 2 are the two major drawbacks of the paper (Please refer to Limitations for a detailed discussion.)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable feedback and time. Below, we respond to their comments:\n\n1. **How and why does the exhaustive search run fast for the random class of graphs generated in Section 4.1?**:\n\nWe thank the reviewer for this question. We do not claim that the exhaustive search runs fast for the class of random graphs considered in Section 4.1 and we will clarify this in the revised version. The worst-case run-time would still be exponential in $p$. \n\n2. **Why are the bi-directed edges chosen with probability $q/p$?**:\n\nWe choose $q/p$ to be the probability with which a bi-directed edge exists between two observed nodes so that the expected number of unobserved nodes is $q/p \\times p(p-1)/2 = q(p-1)/2$ as the reviewer mentioned. As per the reviewer’s suggestion, we increased the number of unobserved nodes by choosing $q$ to be the probability with which a bi-directed edge exists between two observed nodes. In this case, the expected number of unobserved nodes is $qp(p-1)/2$. We ran simulations with $q \\in$ {0.1, 0.15, 0.2}. As expected, with more confounding, there are almost no conditional independence (CI) tests to exploit, yet there are (roughly 1% in all 3 settings) graphs where our approach still applies. We note that any causal discovery-based approach is expected to suffer even more without any meaningful collection of CIs. We will add these results in the revised version. \n\n3. **Rationale behind the class of graphs considered**:\n\nWe thank the reviewer for the suggestion to add more explanation regarding the choice of random class of graphs. Our choice ensures that every node has the same bounded in-degree in expectation. This is common in recent works, e.g., Addanki et al. 2020, *Efficient Intervention Design for Causal Discovery with Latents*, where every directed edge is added with the same probability as in our work. We are happy to address any more questions that the reviewer may have.\n\n4. **Detailed description of Algorithm 1**:\n\nWe thank the reviewer for their suggestion and will include a detailed description of Algorithm 1 in the main body in the revised version. The variable $c_1$ is used to perform an average over different train-test splits. The variables $c_2$, $ATE^r_z$, and $ATE^r_s$ are used to perform an average over different subsets $\\mathbf{z}$ that satisfy our conditions for a specific train-test split. We will also add more explanation on how the two equations in the algorithm are equivalent to the first moment versions of (9) and (10), respectively.\n\n5. **Completeness of the algorithm**:\n\nTo show the completeness of Theorem 3.2, one would have to show the following -- for every class of graphs where our structural side information holds but our algorithm fails, (i.e., at least one the conditional independencies in (7) or (8) fail to hold), the causal effect is not unique, i.e., the causal effect cannot be identified by the front-door-like formulae in (9) and (10) while only using observational data and not knowing the underlying causal graph.\n\nTypically, this is done by explicitly constructing two causal graphs where the algorithm fails and the causal effects have different values. For example, Shpitser et al. 2008, Complete Identification Methods for the Causal Hierarchy, showed the completeness of their ID algorithm this way through explicit constructions. It is highly non-trivial to show the completeness of our algorithm using a similar approach where there are no specific graphs at hand. However, we do show the importance of (8) via the causal graphs in Figure 3. These graphs are such that our structural side information holds, (7) holds for both, but (8) only holds for the bottom one. Then, we show that causal effects formulae for these graphs are indeed different (see lines 195-215). While we agree that providing additional examples towards full completeness of our algorithm would strengthen our results, we reserve this for future work as it is a highly non-trivial extension.\n\n6. **Workaround for Assumption 2**:\n\nWe thank the reviewer for their comment about Assumption 2. In practice, we believe this assumption is more likely to be true than not. But, we agree with the reviewer that this assumption is a limitation and working around this assumption is an interesting future work. We believe that our results could be derived under the weaker condition that there is a back-door path between $t$ and $y$ which is not blockable. On the other hand, if there is no unblockable back-door path between $t$ and $y$, it may be easier to find back-door adjustment sets. We will append this to the discussion on Assumption 2 in the limitations section (Appendix A.2).\n\n---\nWe hope that our response addresses the reviewer's concerns and that they would consider increasing their score. We believe it is indeed an advantage that our proofs are straightforward and clear in hindsight. However, note that it is not clear a priori that the proposed independence criteria would lead to a single (front-door-like) causal effect formula that spans multiple causal graphs which are not Markov equivalent as we show in this work."}, {"review_id": "lyszRDTzfG", "reviewer": "Reviewer_Mu2q", "summary": "The authors proposed a method for estimating causal effects without requiring the knowledge of fully-specified causal graph, focusing on the case where unobserved confounding between treatment and outcome exists. This approach using a front-door-like adjustment formula has a novel contribution in that it can estimate causal effect using only simple structural side information which can be obtained from an expert and is less demanding than specifying the entire causal graph. The authors provide sufficiency proofs and demonstrate clear graphical criteria (a generalized front-door condition) for the proposed front-door-like adjustment formula. \n", "questions": "I once worked on the same problem a few years ago when I first read Entner’s paper on backdoor criterion but I had no luck. So I am super happy to read this paper!\n\n\nI am wondering whether you can compute the variance of ATE estimation for each selection of S so that we can make use of inverse variance weighting instead of simple average. Further, can you employ double machine learning like approach? (e.g., Jung et al. 2021, https://ojs.aaai.org/index.php/AAAI/article/view/17438)\n\n\nSuggestion:\nIn consideration of the importance of Theorem 3.2 as a sufficient condition, it is recommended to include brief proof sketch not only in the appendix but also in the main body of the paper.\n\n", "limitations": "The author clearly presents the limitations of the methodology proposed in Appendix A.2. As stated by the author, assumption 3 among the three assumptions is undoubtedly a strong assumption, which would require substantial domain knowledge to satisfy it in practical situations. Therefore, it is necessary to exercise caution and ensure sufficient attention when applying the methodology suggested by the author in experimental settings.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The authors present a generalized formula that accounts for the variability of the front-door criterion based on the structure of the graph. They provide sufficient conditions clearly for the formula and demonstrate its validity. Hence, in realistic scenarios where unobserved variables may exist between treatment and outcome, this methodology can be effectively utilized, proving its utility. In order to facilitate understanding for readers, the paper includes comprehensive prerequisite knowledge.\nit is anticipated that the formula proposed in this paper will have high utility. ", "weaknesses": "No specific weakness. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable feedback and time. Below, we respond to their comments:\n\n1. **Using inverse variance weighting + double machine learning**: \n\nWe thank the reviewer for pointing out the possibility of variance and bias reduction using inverse variance weighting and double machine learning. Although it might be hard to non-parametrically estimate the variance for each selection S, perhaps it is possible with parametric assumptions such as linearity. We will add this remark as a possibility in the camera-ready version.\n\n2. **Proof sketch of Theorem 3.2**: \n\nWe thank the reviewer for their suggestion and will include a proof sketch of Theorem 3.2 in the main body in the revised version.\n"}, {"review_id": "QoUwMxH73X", "reviewer": "Reviewer_XvUT", "summary": "Causal effect estimation from data often requires assumptions about the causal relationships, either through explicit causal graph structures or implicit conditional independence statements. When confounding exists, the front-door adjustment becomes important for estimating the causal effect of treatment on the outcome using post-treatment variables. This paper studies testable conditional independence statements to compute causal effects using a front-door-like adjustment without knowing the graph under limited structural information. The effectiveness of the method is demonstrated through experiments on both random graphs and real-world causal fairness benchmarks.", "questions": "1. Assumption 1 alone may not be sufficient. It might also be necessary to explicitly state that variable y is not a child node of variable t.\n\n2. TTheorem 3.1 appears to be incomplete. For example, we have $t\\rightarrow b\\rightarrow y$ and $t\\leftrightarrow y$, where $\\leftrightarrow$ denotes a latent confounder. In this case, b is a cause of y, and the conditional independence between b and y may no longer hold.\n\n3. Some cases present challenges in identifying P(Y|do(t=t)) due to the complexity introduced by latent confounders. It is unclear how to exclude these non-identification cases and handle them appropriately.", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The proposed method enables estimating causal effects without requiring knowledge of the causal graph. Instead, it utilizes front-door-like adjustments based on post-treatment variables, making it applicable even in scenarios with unobserved confounding.\n2. The proposed method relies on conditional independence statements that can be directly tested from observational data. This allows for identifying causal effects using observable information without the need for specifying the entire causal graph.\n3. The proposed method requires only limited structural side information, which can be obtained from an expert. This requirement is less demanding than specifying the entire causal graph, making the approach more practical and feasible.\n\n", "weaknesses": "1. The algorithm presented in the paper relies on stronger assumptions, but the paper does not mention them, raising doubts about the soundness and completeness of the proposed method. My main doubts are listed in the Questions.  \n\n2. Figure 5 appears to have a mislabeled Y-axis. It seems to be \"Average ATE errors\".\n\n\nMinors: \nLine 59, criteria -> criterion\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable feedback and time. Below, we respond to their comments:\n\n1. **Figure 5**:\n\nWe thank the reviewer for pointing out this typo. We will correct this in the revised version.\n\n2. **It might be necessary to explicitly state that $y$ is not a child node of $t$**:\n\nWe thank the reviewer for bringing this up. First, note that if $y$ is a child of $t$ and a bi-directed edge exists between $t$ and $y$ (as stated in line 160), the causal query is not identifiable (see Theorem 4 of Tian and Pearl 2002, *A General Identification Condition for Causal Effects*). Moreover, in this scenario, our desired conditional independencies will not pass as there does not exist a set $\\mathbf{z}$ for which $b \\perp y | \\mathbf{z}, t$ since $y \\in b$. Thus, our algorithm will correctly return “I don’t know” as the answer. We will add a remark in the revised version to make this explicit. \n\n3. **Theorem 3.1 appears to be incomplete ($b \\perp y | \\mathbf{z}, t$ may not hold for the graph $t \\leftrightarrow  y; t \\rightarrow  b \\rightarrow  y$)**:\n\nWe thank the reviewer for mentioning this case. We note that for the traditional front-door graph that the reviewer suggested, our available side information only reveals the edges $t \\leftrightarrow y$ and $t \\rightarrow b$, i.e., it does not reveal the edge $b \\rightarrow y$ as we do not assume the knowledge of the entire graph. **This is not sufficient to identify the causal effect from observational data as the edge between $b$ and $y$ cannot be oriented.** Specifically, the traditional front door graph is not distinguishable from the following two graphs: (a) $t \\leftrightarrow  y; t \\rightarrow  b \\leftarrow  y$  and (b) $t \\leftrightarrow  y; t \\rightarrow  b \\leftrightarrow  y$. For these two graphs, we have $\\mathbb{P}(y|do(t)) = \\mathbb{P}(y)$ which is different from the front-door adjustment formula. Therefore, yes, our algorithm cannot identify the causal effect in the traditional front-door graph but correctly so, since it is not identifiable from the available side information. We will include this discussion in the revised version.\n\n4. **Complexity introduced by latent confounders**:\n\nWe note that our conditions are sufficient irrespective of the number or complexity of the latent confounders. This means that if a causal query is not identifiable, then our conditions will not hold. Thus, the algorithm may say “I don’t know” but it will not make a mistake. For more examples of graphs with multiple latent confounders beyond Figure 2, please have a look at Figure 8 and Figure 11 in the supplementary.\n\n--- \nWe hope that our response addresses the reviewer's concerns and that they would consider increasing their score."}]

Author rebuttal:

Meta-review: This paper shows that one can compute causal effects using front-door adjustment even when the underlying causal graph structure is not fully known. The reviewers were excited by the progress made by this work, and I think this paper will open the door to considering more general situations where limited side-information is available.
Decision: Accept (poster)