Finding and Listing Front-door Adjustment Sets
Authors: Hyunchai Jeong
Jin Tian
Elias Bareinboim
Venue: NeurIPS 2022 Accept (2022)
Keywords: causality
algorithm
adjustment

Abstract: Identifying the effects of new interventions from data is a significant challenge found across a wide range of the empirical sciences. A well-known strategy for identifying such effects is Pearl's front-door (FD) criterion. The definition of the FD criterion is declarative, only allowing one to decide whether a specific set satisfies the criterion. In this paper, we present algorithms for finding and enumerating possible sets satisfying the FD criterion in a given causal diagram. These results are useful in facilitating the practical applications of the FD criterion for causal effects estimation and helping scientists to select estimands with desired properties, e.g., based on cost, feasibility of measurement, or statistical power.

Finding and Listing Front-door Adjustment Sets
Hyunchai Jeong Purdue University jeong3@purdue edu
Jin Tian Iowa State University jtian@iastate. edu
Elias Bareinboim Columbia University eb#cs columbia. edu
Abstract
Identifying the effects of new interventions from data is a significant challenge found across wide range of the empirical sciences. A identifying such effects is Pearl's front- (FD) criterion [26]. The definition
strategy for
of the FD criterion is declarative, only allowing set satisfies the criterion. enumerating possible satisfying the FD criterion in given causal diagram. These results are useful in facilitating the practical applications of the FD criterion for causal effects estimation and helping scientists select estimands with desired properties, e.g., based on cost, feasibility of measurement, or statistical power.
decide whether specific
this paper, we present algorithms for finding and
Introduction
Learning cause and effect relationships is fundamental challenge across data-driven fields. For example, health scientists developing a treatment for curing lung cancer need to understand how a new drug affects the patient's body and the tumor's progression. The distillation of causal relations is indispensable to understanding the dynamics of the underlying system and how to perform decision-
making in a principled and systematic fashion 27 37 30
23
One of the most common methods for learning causal relations through Randomized Controlled Trials (RCTs, for short) [8] RCT' considered as the "gold standard" in many fields of empirical research and are used throughout the health and social sciences as well as machine learning and AI. In practice, however, RCTs are often hard to perform due to ethical, financial, and technical issues. For instance, may be unethical to submit an individual to a certain condition if such condition may have some potentially negative effects (e.g., smoking). Whenever RCTs cannot be conducted, one needs to resort to analytical methods to infer causal relations from observational data, which appears in the literature as the problem of causal effect identification [26] (2).
The causal identification problem asks whether the effect of holding a variable at constant value x variable Y, written P(Y P(Y]do(X = =)), P(Y (Y))))z)), can be computed from combination of observational data and causal assumptions. One of the most common ways eliciting these assumptions is in the form of causal diagram represented by directed acyelic graph (DAG), where its nodes and edges describe the underlying data generating process. For instance, in Fig. [Ta three nodes X, Z, Y represent variables, directed edge X - Z indicates that X causes Z, and dashed- bidirected edge X <> Y represents that X and Y are confounded by unmeasured (latent) factors. Different methods can solve the identification problem, including Pearl's celebrated do-calculus (26
as well as different algorithmic solutions 40 34 [2).
In practice, researchers often rely identification strategies that generate well-known identification formulas. One of the arguably most popular strategies is identification by covariate adjustment. Whenever set Z satisfies the back-door (BD) criterion [26] relative to the pair X and Y, where X and Y represent the treatment and outcome variables, respectively, the causal effect P(Y (Y))o())) can be evaluated through the BD adjustment formula Σ. P(y| P(2).
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Despite the popularity of the covariate adjustment technique for estimating causal effects, there are still settings in which no BD admissible set exists. For example, consider the causal diagram g in Fig. Ta There clearly exists no set to block the BD path from X to Y, through the bidirected
arrow, X ++ Y. One may surmise that this effect is not identifiable and the only one of evaluating
the interventional distribution is through experimentation. Still, this is not the case. The effect P(Y do(x)) is identifiable from & and the observed distribution P(z, y, 2) over (X, Y, Z) by another classic identification strategy known as the front-door (FD) criterion [26]. In particular, through the following FD adjustment formula provides the way of evaluating the interventional distribution:
P(Y]do(x)) = Σ P(z|z) Σ P()l2'2))P())) P('')
We refer to Pearl and Mackenzie 288 Sec. 3.4] for an interesting account of the history of the FD criterion, which was the first graphical generalization of the BD case. The FD criterion is drawing more attention in recent years. For applications of the FD criterion, see, e.g., Hünermund and Bareinboim [3 and Glynn and Kashin [10]. Statistically efficient and doubly robust estimators have recently been developed for estimating the FD estimand Eq. T from finite samples (9. which are still clusive for arbitrary estimands identifiable in diagram despite recent progress [18
19
5 20 43
Both the BD and FD criteria are only descriptive, i.e. they specify whether a specific set Z satis- fies the criteria or not, but do not provide way to find an admissible set Z. In addition, in many situations, it is possible that multiple adjustment sets exist. Consider for example the causal dia- gram in Fig. [b] and the task of identifying the effect of X on Y. The distribution P(Y (do(z)) can indeed be identified by the FD criterion with set Z (A, B, C} given by the expression in Eq. ( (with Z replaced with {A, B, C')). Still, what if the variable B is costly to measure en- codes some personal information about patients which is undesirable to be shared due ethi- cal concerns? In this case, the set Z = {A, C} also satisfies the FD criterion and may be used. Even when both B and C' are unmeasured, the set Z {A} is also FD admissible.
Z
(a) g
(b) g'
Figure 1: (a) A canonical example of the FD crite- rion where {2} satisfies the FD criterion relative to ({X}, (Y)). In (b), four FD adjustment sets rel- ative to (fX), (Y}) are available: {A}, {A, B}. {A, C). and [,,.
This simple example shows that a target effect can be estimated using different adjustment sets leading to different probability expressions over different set of variables, which has important practical implications. Each variable implies different practical challenges in terms of measurement, such as cost, availability, privacy. Each estimand has different statistical properties in terms of sample complexity, variance, which may play a key role in the study design [31] [1] 32) 36). Algorithms for finding and listing all possible adjustment sets hence very useful in practice, which will allow scientists to select an adjustment set that exhibits desirable properties. Indeed, algorithms have been developed in recent years for finding one listing all BD admissible sets [38 39, 41 29 42
However, no such algorithm is currently available for finding/listing FD admissible sets.
The goal of this paper is to close this gap to facilitate the practical applications of the FD criterion for causal effects estimation and help scientists to select estimand with certain desired properties Specifically, the contributions of this paper are follows:
1.
We develop an algorithm that finds an admissible front-door adjustment set Z in given causal diagram in polynomial time (if one exists). We solve a variant of the problem that imposes constraints I C Z C R for given sets I and R. which allows a scientist to constrain the search to include specific subsets of variables or exclude variables from search perhaps due to cost, availability, or other technical considerations.
2. We develop a sound and complete algorithm that enumerates all front-door adjustment sets with polynomial delay- the algorithm takes polynomial amount of time to return each new admissible set, if one exists, or return failure whenever it exhausted all admissible sets.
'Code is available at att.tpps//ggtttto.mm////aassaaaa http:///.hthttoooooooalaalllllat
2

---

2 Preliminaries
Notation. We write a variable in capital letters (X) and its value as small letters (r). Bold letters, X or represent set of variables or values. We use kinship terminology to denote various relationships in a graph G and denote the parents, ancestors, and descendants of X (including X itself) Pa(X), An(X, (X), and Dx(X), respectively. Given a graph G over set of variables V, a subgraph Gx consists of a subset of variables X S V and their incident edges in G. A graph 9 can be transformed: Ox is the graph resulting from removing all incoming edges to X, and Gx is the graph with all outgoing edges from X removed. A DAG G may be moralized into an undirected graph where all directed edges of 9 are converted into undirected edges, and for every pair of nonadjacent nodes in G that share a common child, an undirected edge that connects such pair is added (22).
A path from a node X to a node Y in 9 is sequence of edges where X and Y are the endpoints of T. A node W on т is said to be a collider if W has converging arrows into W in n, e.g., - W <- or ++ W 4. is said to be blocked by set Z if there exists node W on satisfying one of the following two conditions: 1) W is collider, and neither W nor any of its descendants are in Z. or 2) W is not collider, and W is in Z 225 Given three disjoint sets X, Y. and Z in G, Z is said to d-separate X from Y in G if and only if Z blocks every path from a node in X to a node in Y according to the d-separation criterion (25, and we say that Z is a separator of X and Y in G.
Structural Causal Models (SCMs). We use Structural Causal Models (SCMs, for short) 27 as our basic semantical framework. An SCM is 4-tuple (U, V.F, F, P(u)), where 1) U is a set of exogenous (latent) variables, 2) V is a set of endogenous (observed) variables, 3) F is a set of functions {fv]vey that determine the value of endogenous variables, e.g.,
fv (pay, Uv)) a function with PAv C V (V) and Uv S U, and 4) P(u) is a joint distribution over the exogenous variables U. Each SCM induces causal diagram G [3] Def. 13] where every variable v E V is a vertex and directed edges in G correspond to functional relationships as specified in F and dashed bidirected edges represent common exogenous variables between two vertices. Within the structural semantics, performing an intervention and setting X = x is represented through the do-operator, do(X x), which encodes the operation of replacing the original functions of X (i.e., fx (pax, (x))) by the constant x and induces a submodel Mr and an interventional distribution P(vldo(z))
Classic Causal Effects Identification Criteria. Given a causal diagram G over V, an effect P(y]do(x)) is said to be identifiable in G if P(y do(x)) is uniquely computable from the observed distribution P(v) in any SCM that induces G (27 p. 77J.
A path between X and Y with an arrow into X is known as back-door path from X to Y. The celebrated back-door (BD) criterion (26) provides sufficient condition for effect identification from observational data, which states that if a set Z of non-descendants of X blocks all BD paths from X to Y, then the causal effect P(y) (x))) is identified by the BD adjustment formula:
P(yldo(x)) = Σ 2(ylx,2)P(z)
Another classic identification condition that is key to the discussion in this paper is known as the front-door criterion, which is defined as follows:
Definition 1. (Front-door (FD) Criterion (26) A set of variables Z is said to satisfy the front-door criterion relative to the pair (X, Y) if
1. Z intercepts all directed paths from X to Y,
2. There is no unblocked back-door path from X to Z. and
3. All back-door paths from Z to Y are blocked by X, i... X is separator of Z and Y in Gz.
If Z satisfies the FD criterion relative to the pair (X, Y), then P(y]do(x)) is identified by the following FD adjustment formula (26):
P(y]do(x)) = Σ P(z|x) E P(y))x(2)P(x))
(3)
3

---

3 Finding A Front-door Adjustment Set
In this section, we address the following ques- tion: given a causal diagram G. is there a set Z that satisfies the FD criterion relative to the pair (X, Y) and, therefore, allows us to
Algorithm FINDEDSET G.X,Y.I.R
identify P(y P(y[do(x) (x) by the FD adjustment? We solve more general variant of this ques- tion that imposes constraint I Z C R for given sets and R. Here, are variables that must be included in Z (I could be empty) and R are variables that could be included in Z (R could be V (XXU)). Note the constraint that variables in W cannot be included can be enforeed by excluding W from R. Solv- ing this version of the problem will allow sci- entists to put constraints on candidate adjust-
1: Input: 9 causal diagram; X, Y disjoint sets of variables; I, sets of variables.
2: Output: Z a set of variables satisfying the front- door criterion relative (X, Y) with the con- straint I C 2 C R.
3:
Step
4:
R' <- (
5:
R'' =1 then: return 1
6:
Step 2:
7:
R" {- GGTCAND3RDFDDC X, Y, R')
Rf" =1 then: return
ment sets based practical considerations. In addition, this version will form a building block for an algorithm that enumerates all FI) admissible sets in a given G the algorithm
9:
Step 3:
10:
G' GETCAUSAL.PAHHRRAPHI X, Y)
11:
if TESTSEEP(S X, Y,R") = True then:
LISTFDSETS (shown in Alg. in Section 4 for listing all FD admissible sets will utilize
12:
return Z = R"
13: else: return 1
this result during the recursive call.
We have developed a procedure called FINDFDSET shown in Alg. Ihat outputs a FD adjustment set Z relative to (X, Y) satisfying I _ Z S R. or outputs 1 if none exists, given a causal diagram G. disjoint sets of variables X and Y, and two sets of variables I and R.
Example 1. Consider the causal graph G', shown in Fig. Ib] with X = (X). y= I=
and R {A, B, C, D}. Then, FINDFDSET outputs (A, B, C). With I= {C} and [A,C). FINDFDSET outputs {A, CJ. With I = {D} and R = [A, B, C, DJ, FINDFDSET outputs 1 as no FD adjustment set that contains D available.
FINDFDSET runs three major steps. Each step identifies candidate variables that incre-
1:
function BETCAND2NDFDC(G.X.II
mentally satisfy each of the conditions of the
2: Output: R' with I S R' S R, the set of candidate variables consisting of all the variables
FD criterion relative to (X, Y). First, FIND-
FDSET constructs a set of candidate vari- ables R', with I C R' C R. such that every subset with I C C R' satisfies the sec- ond condition of the FD criterion (i.c., there is no BD path from X to Z). Next, FIND- FDSET generates set of candidate variables R", with I C R" C R', such that for every variable E R" there exists set Z with IC R' and u E that further satisfies the third condition of the FD criterion, that is, all BD paths from to Y are blocked by X. Finally, FINDFDSET outputs set Z that further satisfies the first condition of the FD) criterion Z intercepts all causal paths from X to Y.
V E R such that there no BD path from X to v.
3:
R' < R
4:
for all v V R:
if TESTSSEEEPxx X, v. 0) False then: if u E I then: return 1 else: R' R' ( {v}
6:
8:
end for return R' end function
9:
10:
Figure 2: A function that outputs the set of candidate variables satisfying the second condition of the FD criterion.
Step 1 of FINDFDSET
In Step 1, FINDFDSET calls the function GETCAND2NDFDC (presented in Fig. 2 to construct set R' that consists all the variables v E such that there is no BD path from to v (R' set to empty if there is a BD path from X to I). Then, there is no BD path from X to any set I C Z C R' since, by definition, there no BD path from X to Z if and only if there is no BD path from to any Z.

---

GETCAND2NDFDC iterates through each variable E R and checks if there exists an open BD path from X to u by calling the function TESTSEP(GX X, u. 0) [T. TESTSEP(G, A, B. C) returns True if C is separator of A and B in G, or False otherwise. Therefore, TESTSEP X, 0) returns 9x (i.e., there no BD path from X to v), or False otherwise.
True if 0 a separator X and If TEP returns False, then e is removed from R' because every set Z containing v violates the second condition of the FD criterion relative to (X,Y)
Example 2. Continuing Example I With I 0 and R B, D3 GETCAND2NDFDC
outputs a set R' = {A, B, C). D is excluded from R' since there exists BD path from } to (D), and any set containing D violates the second condition of the FD criterion relative ((X), {Y.).
Lemma (Correctness of GETCAND2NDFDC), GETCAND2NDFDC X, L, R) generates set of variables R' with I C R' C R such that R' consists of all and only variables u that satisfies the second condition of the FD criterion relative (X, Y). Further, every subset Z RR' satisfies
the second condition of the FD criterion relative to (X, Y), and every set Z with I C Z C R that satisfies the second condition of the FD criterion relative to (X, Y) must be subset R'.
Step 2 of FINDFDSET
In Step 2. FINDFDSET calls the function GETCAND3RDFDC presented in Fig. to generate a set R" consisting of all the vari- ables R' such that there exists set Z containing v with S Z S R' that further satisfies the third condition of the FD criterion relative to (X, Y) (i.e., all BD paths from Z to Y other words, R" is the union of all Z with I C Z R' that satisfies the third condition of the FD criterion.
1: function GETCAND3RDFDCCC,, X, Y,
2: Output: R" consisting of all the variables E R' such that there exists set containing with I C Z C R' that satisfies the third condition of the FD criterion relative to (X, Y).
3:
R" <- RR'
blocked by X). In
4:
for all a R':
5:
if GETTDPPCGG X,Y, [o) R') = then:
6:
if E then: return 1 else: R" t -R" \²\(t)
7:
GETCAND3RDFDC iterates through each variable v E R' and calls the function GETDEP(G, X. Y, fo). R') in line 5 Pre- sented in Fig. 4 GETDEP returns a subset Z' C R' (u) such that all BD paths from Z = [w] U Z to Y are blocked by X (if there exists such Z'). If GETDEP returns 1,, then there exists no containing v that sat- isfies the third condition of the FD criterion relative to (X, Y), SO V is removed from R".
8: end for
9: return R"
10: end function
Figure 3: A function that outputs the set of candidate variables potentially satisfying the second and third conditions of the FD criterion.
Example 3. Continuing 2x Given = 0 and R' = (, GETCAND3RDFDC outputs R" {A, B, C} because for each variable v E R", GETDEP finds a set Z' such that {r} U Z' satisfies the third condition of the FD criterion relative to (fX), (Y)). For u = A, Z' = 0, for
B, Z = {A}, and for C, Z' (A).
Next, we explain how the function GETDEP(G, T.T.R works. First, GETDEP constructs an undirected graph M in way that the paths from T to Y in M represent all BD paths from T to Y that cannot be blocked by X in G. The auxiliary function MOR MORALIZE(S) moralizes a given graph into an undirected graph. The moralization is performed on the subgraph over An( X Y) instead of G based on the following property: T and Y are d-separated by X in 9 if and only if X is MBORALIZEGAAnTT.SS
T-Y node cut (i.c., removing X disconnects T and Y) in G'
21
GETDEP performs Breadth-First Search (BFS) from T to Y on M and incrementally constructs subset Z' C R'' T such that, after BFS terminates, there will be no BD path from Z = T Z' to Y that cannot be blocked by X in g. While constructing Z', GETDEP calls the function GETNEIGHBORS(L.. M) (presented in Fig. 8, Appendix) to obtain all observed neighbors of in M.
The BFS starts from each variable v E T. Whenever a non-visited node u is encountered, the set NR, observed neighbors of that belong to R', is computed. NR can be added to Z' because removing all outgoing edges of NR may contribute to disconnecting some BD paths IT from T to Y that cannot be blocked by X in G. In other words, in GruZ NNR, II could be disconnected from T to
5

---

1: function GETDEP(G, X, X,
2: Output: Z' - R' T. a set of variables such that T U satisfies the third condition of the FD criterion relative to Y..
3:
g' < (A.(T.XXUY)
4:
g' < g' with all bidirected edges A ++ B replaced by a latent node LAB and two edges
LAB + A and LAB + B
5:
g" t F
6:
M + MORALIZE(G")) then remove X
7:
Z' 0, Q ' and mark all ' visited
8:
while Q + / do
9:
<- Q.POP()
10:
if u E Y then: return 1
11:
NR. <- GETNEIGHBORS(N) (u, M) R' that are not visited
12:
G" <- TUZ'UURR
13:
M < MORALIZE(G") then remove X
14:
N' < GETNEIGHBORS(A M) that are not visited
15:
NR' (w E NR. there exists incoming arrow into in 9}
16:
N < UR'', Z' < Z' UR.
17:
Q (NN)ER((N) and mark all N as visited
18:
end while
return Z'
20:
end function
Figure 4: A function that facilitates the construction of set that satisfies the third condition of the FD criterion.
Y where II are not disconnected in GruZ. After adding NR Z', .M must be reconstructed in way that reflects the setting where all outgoing edges of NR are removed. BFS will be performed on such modified M..
GETDEP checks if there exists any set of nodes N to be visited further. N consists of two sets: 1) N' all observed neighbors of that are still reachable from even after removing all outgoing edges of NR, and 2) NR' C NR where for every node w E NR, there exists an incoming arrow into in G. All nodes in NR' must be checked because there might exist some BD path from to E Y that cannot be blocked by X in G. If π cannot be disconnected from w to y, then the set Z will violate the third condition of the FD criterion relative to (X, Y).
The BFS continues until either a node y E is visited, or no more nodes can be visited. If GETDEP returns set Z', then we have that all BD paths from T to Y that cannot be blocked by X in have been disconnected in Gz while ensuring that there exists no BD path from to that cannot be blocked by X in G. Therefore, Z satisfies the third condition of the FD criterion relative to (X, Y). Otherwise, if GETDEP returns 1 (i.e., is visited), then there does not exist any Z containing that satisfies the third condition of the FD criterion relative (X, Y). This is because there exists BD path æ from E T to that cannot be blocked by X in 9; removing outgoing edges of all w E R!' that intersect cannot disconnect from / y.-
Example 4. Expanding Example 3 to show the use of function GETDEP. Consider the case when V B. Then, Q = T = (B) and B popped from Q at line We have NR = (A). (A).M. N' 0. NR' {A).N N {A}. and Z' [A}. Since N is inserted to Q at line 17 A is popped
from Q in the next iteration of while loop. Then, NR = 0, N' 0, NR' 0, and = Since Q empty, the while loop terminates and GETDEP returns Z' {A].
Let I = 0. R' (B.C), C). and v = B. Q T {B) and B is popped from Q line 9 NR 0, N' (A), NR' = 0, {A}.
Example 5. Illustrating the use of function GETDEP.
and Z' = 0. Since N is inserted to Q at line 17 u = A is popped from Q in the second iteration
of while loop. NR NR' {C), N' N
{C, D.Y), Z' [C), and Q (C. On
the third iteration, = C' is popped from Q. NR = NR' N' N 0 and Q (D.Y).
the fourth iteration, u D popped from Q. NR NR' = N' N
0 and Q (Y).
Next, = Y popped from Q. Since u E (Y), GETDEP returns 1 at line 10 There exists no set Z' C (R') (T) = {C} such that T TUZ Z' satisfies the third condition of the FD criterion relative to (LX),

---

Lemma 2 (Correctness of GETCAND3RDEDC), GETCAND3RDFDC X.Y.I,R') in Step 2 of Alg. Agenerates set of variables R" where I C R" RR. R" consists of all and only variables such that there exists a subset Z with I C Z S R' and v E Z that satisfies the third condition of the FD criterion relative to (X, Y). Further, every set Z with I C Z R. that satisfies both the second and the third conditions of the FD criterion must be subset of R.".
Remark: Even though every set Z with I Z [ R' that satisfies the third condition of the FD criterion must be subset of R", not every subset Z [ R" satisfies the third condition of the FI) criterion, illustrated by the following example.
Example 6. In Example 3 GETCAND3RDFDC outputs R" = [ [., However, for Z = (B), the BD path {B + A -D + Y) is not blocked by (x); for Z {C}. the BD path {C <- A 4 D + } is not blocked by {X}.
On the other hand, we show that Z = R" itself satisfies the third condition of the FD criterion, as shown in the following.
Lemma 3. R" generated by GETCAND3RDEDC (in Step 2 of Alg. 7 satisfies the third condition of the FD criterion, that is, all BD from R" to Y are blocked by X.
Step 3 of FINDFDSET
Finally, in Step 3, FINDEDSET looks for set S R" that satisfies the first condition of the FD criterion relative to (X, Y), that is, Z intercepts all causal paths from X to Y. To facilitate checking whether a set Z intercepts all causal paths from to Y, we introduce the concept of causal path graph defined as follows.
Definition 2. (Causal Path Graph) Let G be causal graph and X, Y disjoint sets of variables. A causal path graph G' relative to (G. X, Y) is graph over X U Y U PCP(X, Y), where PCP(X, Y) = (De(X)sx (X) (Y))))) constructed as follows:
1. Construct a subgraph G" = +XUYUPCP(X.Y)
2. Construct a graph g' = Xx then remove all bidirected edges from g'.
X, Y) for constructing causal path graph is presented in Fig. in the Appendix.
A function
Example 7. Consider the causal graph g' shown Fig. 1b with X = (X), and Y (Y). The causal path graph G relative to (x), { is shown in Fig. 5b All causal paths from {X} to {Y} in G are present in g".
X
Z
Y
(a) g
(b) g"
causal path graph g' relative to (G. X, Y), we use the function TESTSEP(G', X, Y, Z) to check if Z sep- arator of X and Y in G". Based on the following lemma, Z satisfies the first condition of the FD criterion relative to (X, Y) if and only if TEST- SEP returns True.
After constructing
Figure 5: Two causal path graphs generated from (a) the causal graph in Fig. la and (b) the causal graph in Fig. Tb Both preserve all and only causal paths from (XF to (Y) in the original graphs.
Lemma 4. Let G be a causal graph and X, Y, Z disjoint sets of variables. Let G' be the causal path graph relative (g, X, Y). Then, Z satisfies the first condition of the FD criterion relative to (X. Y) if and only if Z is separator of X and Y in G'.
Given the set R" that contains every set Z with I C Z C R that satisfies both the second and the third conditions of the FD criterion (Lemma 2 J. it may appear that we need to search for a set Z C R" that satisfies the first condition of the FD criterion. We show instead that all we need is to check whether the set R" itself satisfies the first condition which has been shown to satisfy the second and third conditions by Lemma 3 This result is summarized in the following lemma.
A notation introduced by van der Zander et al. 41 to denote the set of variables on proper causal paths
from X to Y.
7

---

Ag
(a) g
(b) g'
(c) g"
Figure 6: Three examples of the FD criterion to demonstrate that total number of FD adjustment sets may be exponential with respect to the number of nodes in graph.
Lemma 5. There exists set Zo satisfying the FD criterion relative to (X. Y) with IC Zo R if and only if R" generated by GETCAND3RDEDC (in Step 2 of Alg. 7 satisfies the FD criterion relative to (X, Y).
Example 8. Continuing Example In Step FINDFDSET outputs Z R" =(A, B,C) since Z a separator of {X} and (Y} in the causal path graph G" in Fig. 5h
The results this section are summarized as follows.
Theorem (Correctness FINDFDSET). Lei be a causal graph, X, Y disjoint sets of variables, and I, R sets of variables such that I Ç R. Then, FINDFDSET(G,) X, Y R) outputs set Z with C Z C R. that satisfies the FD criterion relative (X, Y), or outputs if none exists, in O (n + m)) time, where and represent the number of nodes and edges in G.
Enumerating Front-door Adjustment Sets
Our goal in this section to develop an al- gorithm that lists all FD adjustment sets in causal diagram. In general, there may ex- ist exponential number of such sets, which means that any listing algorithm will take exponential time to list them all. We will instead look for an algorithm that has an in- teresting property known as polynomial delay [38. In words, poly-delay algorithms output the first answer (or indicate none is available) polynomial time, and take polynomial time to output each consecutive answer as well.
Algorithm 2 LISTFDSETS (G, X. Y,I.R
1: Input: G causal diagram; X, Y disjoint sets of
variables; I, sets of variables.
2: Output: Listing front-door adjustment set Z rel-
ative to (X, Y) where I C Z R.
3: if FINDFDSET(G, X, Y,I.R) #1 then:
if = R then: Output
5: else:
f- any variable from R. R
Consider the following example.
7:
LISTFDSETS(G X, YU {v), R) LISTFDSETS X, Y, R, {w})
Example Consider the three causal graphs in Fig. 6 In G shown in Fig. 6al there ists 9 valid FD adjustment sets relative to (LX), (Y)). In G', presented in Fig. 6bb two variables A3 and B3 are added from G, forming additional causal path from X to Y. 27 FD adjustment sets relative to ((X), (Y)) are available in g'. If another causal path X > Aa + Ba Y is added to g', then there are 81 FD adjustment sets relative to (X). (Y)) As shown in Fig. 6c in a graph G" with similar pattern with causal path X A, B, Y. 1,... n, there at least 3" number of FD adjustment sets.
8:
We have developed an algorithm named LISTFDSETS, shown in Alg. 2 that lists all FD adjustment sets relative to (X, Y) satisfying C C with polynomial delay, given causal diagram G, disjoint sets of variables X and Y, and two sets of variables I and R.
Example 10. Consider the causal graph G' shown in Fig. 1b with X = (X). Y (Y). I and
R (A, B, C, D). LIST outputs (A, B, C), (A, B) (A, C, (4) one by one, and finally stops more adjustment sets exist.
8

---

The algorithm LISTEDSETS takes the same search strategy as the listing algorithm LISTSEP A1 that enumerates all BD adjustment sets with polynomial delay. LISTFDSETS implicitly constructs a binary search tree where each tree node N(T', RR) represents the collection of all FD adjustment
sets relative to (X, Y) with I' S S R'. The search starts from the root tree node (I, R), indicating that LISTFDSETS will list all FD adjustment sets Z relative to (X, Y) with IC Z C R.
Upon visiting a node (I', R'), LISTFDSETS first calls the function FINDFDSET (line 3 to decide whether it is necessary to search further from N. If FINDFDSET outputs 1, then there does not exist any FD adjustment set Zo with I' S Zo S R' and there is no need to search further. Otherwise, .N spawns two children, W and Nn2 and LISTFDSETS continues the search over each child separately. Ng in line repre- sents the collection of all FD adjustment sets Z relative to (X. Y) where I' U (v) C Z, C R'. On the other hand, N2 in line 8 represents the collection of all FD adjustment sets Zg where I' C Z2 S R' fe}. N1 and N2 are disjoint and thus the search never overlaps, which is crucial to guarantecing that LISTEDSETS runs in polynomial delay. Finally, a leaf tree node L is reached when I' = R', and LISTEDSETS outputs valid FD adjustment set I'.
AAAND
Inlan
Delede
ABCrAN
A82/A00
AB/10
ACO/AC
ACAAC
A/4
Figure 7: A search tree illustrating the running of LISTFDSETS in Example [1]
Example 11. Continuing from Example TO Fig. shows a search tree generated by running LISTFDSETS((" (X), (Y), 0, { {A, B,C, C, DJ.- Initially, the search starts from the root tree node N10, (A. B, C, D)). Since FINDFDSET returns set {A, B, C). .V branches out into two children ("(AA), [A, B, C, D)) and (0, ( (B,C. C, D)). The search continues from the left child A' until reaching the leaf tree node Ci B, D}, (A, B,C, D)) where FINDFDSET returns 1. LISTFD- SETS backtracks to the parent tree node (1A, B, C), {A, B, C, D}) and then checks the next leaf C2((A, B, C), {A, C)) where FINDFDSET returns a set {A, B, C}. a valid FD admissible set relative to ((X), (Y)). LISTEDSETS outputs {A, B, C}. Next, LISTEDSETS backtracks to the and reaches the leaf Ls( outputs {A, B), and thus LISTFDSETS outputs {A, B}. LISTFDSETS continues and outputs two sets (A.C) and {A] in order. Finally, LISTFDSETS backtracks to the root V and checks the right child N² where FINDFDSET returns I. LISTEDSETS does not search further from A and stops as no more tree node is left to be visited.
tree node N2, (A,
B)) where FINDFDSET
Our results are summarized in the following theorem, which provides the correctness, completeness, and poly-delay complexity of the proposed algorithm. Note that the completeness of the algorithm means that it lists "all" valid sets satisfying the FD criterion. On the other hand, Pearl's 's FD criterion not complete in the sense that there might exist causal effect that can be computed by the FD adjustment formula (Eq. 33) but the set Z does not satisfy the FD criterion.
Theorem (Correctness of LISTFDSETS). Let G be causal graph, X, Y disjoint sets of variables, and I, R. sets of variables. LISTFDSETS(G X, Y.I.R) enumerates all and only sets Z with I C Z C R. that satisfy the FD criterion relative to (X, Y) O(n't (n + m)) delay where n and m represent the number of nodes and edges in G.
5 Discussion and Conclusions
This work has some limitations and can be extended in several directions. First, Pearl's FD criterion is not complete with respect to the FD adjustment formula (Eq. (3). While the BD criterion has been generalized to a complete criterion for BD adjustment [35] it an interesting open problem to come up with complete criterion for sets satisfying the FD adjustment. Second, this work assumes that the causal diagram is given (or inferred based on scientists' domain knowledge and/or data). Although this assumption is quite common throughout the causal inference literature, more recent work has moved to finding BD admissible sets given incomplete or partially specified causal diagrams, e.g., maximal ancestral graphs (MAGs) [1], partial ancestral graphs (PAGs) [29], and completed partially directed acyelic graphs (CPDAGs) [29] There are algorithms capable of performing causal effect identification in data-driven fashion from an equivalence class [4 15 16 [7]. It is an

---

interesting and certainly challenging future work to develop algorithms for finding FD admissible sets in these types of graphs. Some recent work has proposed data-driven methods for finding and listing BD admissible sets, using an anchor variable, when the underlying causal diagram is unknown 6 33 A criterion for testing FD-admissibility a given set using data and an anchor variable also available A Other interesting future research topics include developing algorithms for finding minimal, minimum, and minimum cost FD adjustment sets, which are available for the BD adjustment sets [42], well algorithms for finding conditional FD adjustment sets 13 2 Having said all of that, we believe that the results developed in this paper is a necessary step towards solving these more challenging problems.
After all, we started from the observation that identification is not restricted BD adjustment, and Pearl's FD criterion provides a classic strategy for estimating causal effects from observational data and qualitative knowledge encoded in the form of causal diagram. The criterion drawing more attention in recent years and statistically efficient and doubly robust estimators have been developed for estimating the FD estimand from finite samples.
this paper, we develop algorithms that given causal diagram G. find an admissible FD set (Alg, FIND.DSE.. Thm. I and enumerate all admissible FD sets with polynomial delay (Alg. 2 LISTFDSETS, Thm. ( We hope that the methods and algorithms proposed in this work will help scientists to use the FD strategy for causal effects
estimation in the practical applications and are useful for scientists in study design to select covariates based on desired properties, including cost, feasibility, and statistical power.
References
[1] Elias Bareinboim and Judea Pearl. Causal Inference by Surrogate Experiments: z-ldentifiability. In Nando de Freitas Murphy and Kevin, editors, Proceedings of the Twenty-Eighth Conference on Uncertainty in Artificial Intelligence, pages 113-120. AUAI Press, 2012.
[2] Elias Bareinboim and Judea Pearl. Causal inference and the data-fusion problem. Proceedings of the National Academy of Sciences, 113(27):7345-3322 2016.
[3] Elias Bareinboim, Juan D Correa, Duligur Ibeling, and Thomas Ieard. On pearl's hierarchy and the foundations of causal inference. In Probabilistic and Causal Inference: The Works of Judea Pearl, page 507-556. Association for Computing Machinery, New York, NY, USA, 1st edition, 2022.
[4] Rohit Bhattacharya and Razieh Nabi. On testability of the front-door model via verma con- straints In James Cussens and Kun Zhang, editors, Proceedings of the Thirty-Ei Eighth Conference on Uncertainty in Artificial Intelligence, volume 180, pages 202-212 PMLR, Aug 2022.
[5] Rohit Bhattacharya, Razieh Nabi, and Ilya Shpitser. Semiparametric inference for causal effects in graphical models with hidden variables. arXiv preprint urXiv:2003. 2020.
[6] Debo Cheng, Jiuyong Li, Lin Liu, Kui Yu, Thuc Duy Le, and Jixue Liu. Toward unique and unbiased causal effect estimation from data with hidden variables. In IEEE Transactions on Neural Networks and Learning Systems, pages 1-13, Jan 2022. doi: 10. 109/TNNLS 20221. 3133337.
[7] Doris Entner, Patrik O. Hoyer, and Peter Spirtes. Data-driven covariate selection for nonpara- metric estimation of causal effects. In Carlos M. Carvalho and Pradeep Ravikumar, editors, Journal of Machine Learning Research, volume 31, pages 256-264, Scottsdale, Arizona, USA, 2013.
[8] Ronald A Fisher. Design of Experiments. British Medical Journal, 1(3923):554, 1936.
[9] Isabel R Fulcher, Ilya Shpitser, Stella Marealle, and Eric 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). 32(1):199-214 2020.
[10] Adam Glynn and Konstantin Kashin. Front-door versus back-door adjustment with unmea- sured confounding: Bias formulas for front-door and hybrid adjustments with application to job training program. Journal of the American Statistical Association, 113(523):0040-10
2018.
10

---

[11] Jinyong Hahn. On the role of the propensity score in efficient semiparametric estimation of average treatment effects. Econometrica, 66(2):315-331, Mar 1998.
[12] Yimin Huang and Marco Valtorta. Identifiability Causal Bayesian Networks: Sound and Complete Algorithm. In Proceedings of the Twenty-Firg National Conference on Artificial Intelligence (AAAI 2006), pages 1149-1156. AAAI Press, Menlo Park, CA, 2006.
[13] Paul Hünermund and Elias Bareinboim. Causal inference and data-fusion in econometrics. Technical Report R-51, Causal Artificial Intelligence Lab, Columbia University, Dec 2019.
[14] Amin Jaber, Jiji Zhang, and Elias Bareinboim. Causal Identification under Markov Equivalence. In Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, 2018.
[15] Amin Jaber, Jiji Zhang, and Flias Bareinboim. Causal identification under markov equivalence: Completeness results. In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97, pages 2981-2989, Long Beach,
CA, 2019. PMLR.
[16] Amin Jaber, Jiji Zhang, and Elias Bareinboim. On causal identification under markov equiva- lence. In S. Kraus, editor, Proceedings of the 28th International Joint Conference Artificial Intelligence, pages 1181-6185, Macao, China, 2019. International Joint Conferences on Artifi- cial Intelligence Organization.
[17] Amin Jaber, Jiji Zhang, and Elias Bareinboim. Identification of conditional causal effects under markov equivalence. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché Buc, E. Fox, and Garnett, editors, Advances in Neural Information Processing Systems 32, pages 11512-11520 15200, Vancouver, Canada, 2019. Curran Associates, Inc.
[18] Yonghan Jung, Jin Tian, and Elias Bareinboim. Estimating causal effects using weighting- based estimators. In Proceedings of the 34th AAAI Conference on Artificial Intelligence, pages 11186-10193, New York, NY, 2020. AAAI Press.
[19] Yonghan Jung, Jin Tian, and Elias Bareinboim. Learning causal effects via weighted empirical risk minimization. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 12697-12709, Vancouver, Canada, Jun 2020. Curran Associates, Inc.
[20] Yonghan Jung, Jin Tian, and Elias Bareinboim. Estimating identifiable causal effects through double machine learning. Proceedings of the 35th AAAI Conference on Artificial Intelligence, 2021.
[21] Steffen L Lauritzen. Graphical Models. Clarendon Press, Oxford, 1996.
[22] Steffen L Lauritzen and David J Spiegelhalter. Local computations with probabilities graphical structures and their application to expert systems(with discussion). Journal of the Royal Statistical Society, (0(2):157-22) 224, 1988.
[23] Sanghack Lee, Juan D Correa, and Elias Bareinboim. General Identifiability with Arbitrary Surrogate Experiments. In Proceedings of the Thirty-Fifth Conference Annual Conference on Uncertainty in Artificial Intelligence, Corvallis, OR, 2019. AUAI Press, press.
[24] Sanghack Lee, Juan D Correa, and Elias Bareinboim. Identifiability from a combination of observations and experiments. In Proceedings of the 34th AAAI Conference on Artificial Intelligence, New York, NY, 2020. AAAI Press.
[25] Judea Pearl. Probabilistic Reasoning in Intelligent Systems. Morgan Kaufmann, San Mateo, CA, 1988.
[26] Judea Pearl. Causal diagrams for empirical research. Biometrika, 82(4):669-688, 1995.
[27] Judea Pearl. Causality: Models, Reasoning, and Inference. Cambridge University Press, New York, NY, USA, 2nd edition, 2000.
[28] Judea Pearl and Dana Mackenzie. The Book of Why. Basic Books, New York, 2018.

---

[29] Emilija Perkovié, Johannes Textor, Markus Kalisch, and Marloes H. Maathuis. Complete Graphical Characterization and Construction of Adjustment Sets in Markov Equivalence Classes of Ancestral Graphs. Journal of Machine Learning Research, 18, 2018.
[30] Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Elements of Causal Inference: Foundations and Learning Algorithms. Adaptive Computation and Machine Learning, MIT Press, Cambridge, MA, 2017.
[31] James Robins and Andrea Rotnitzky. Recovery of information and adjustment for dependent censoring using surrogate markers. In Nicholas Jewell, Klaus Dietz, and Vernon Farewell, editors, AIDS Epidemiology: Methodological Issues, pages 297-331, Boston, MA, 1992. Birkhäuser Boston.
[32] Andrea Rotnitzky and Ezequiel Smucler. Efficient adjustment sets for population average causal treatment effect estimation in graphical models. The Journal of Machine Learning Research, 21:1-86, Sep 2020.
[33] Abhin Shah, Karthikeyan Shanmugam, and Kartik Ahuja. Finding valid adjustments under non-ignorability with minimal dag knowledge. In Gustau Calps-Valls, Francisco J. R. Ruiz, and Isabel Valera, editors, Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151, pages 5568-5562. PMLR, Mar 2022.
[34] Ilya Shpitser and Judea Pearl. Identification Joint Interventional Distributions in Recursive semi-Markovian Causal Models. In Proceedings of the Twenty-First AAAI Conference Artificial Intelligence, volume 2. pages
2006.
[35] Ilya Shpitser, Tyler J VanderWeele, and James M Robins. On the validity of covariate adjustment for estimating causal effects. Proceedings of the Twenty Sixth Conference on Uncertainty in Artificial Intelligence (UAI-10), pages 527-536, 2010.
[36] Ezequiel Smucler, Facundo Sapienza, and Andrea Rotnitzky. Efficient adjustment sets in causal graphical models with hidden variables. Biometrika, 109(1):49-65, Mar 2022.
[37] Peter Spirtes, Clark N Glymour, and Richard Scheines. Causation, Prediction, and Search. Springer- New York, 1993.
[38] Ken Takata. Space-optimal, backtracking algorithms to list the minimal vertex separators of graph. Discrete Applied Mathematics, 16600166160-16 2010.
[39] Johannes Textor and Maciej Liskiewicz. Adjustment Criteria in Causal Diagrams: An Algorith- mie Perspective. In Avi Pfeffer and Fabio Cozman, editors, Proceedings of the Twenty-Seventh Conference on Uncertainty Artificial Intelligence (UAI 201 I), pages 681-688, AUAI Press, 2011.
[40] Jin Tian and Judea Pearl. A General Identification Condition for Causal Effects. Proceedings of the Eighteenth National Conference on Artificial Intelligence (AAAI 2002), pages 567-573, Menlo Park, CA, 2002. AAAI Press/The MIT Press.
[41] Benito van der Zander, Maciej Liskiewicz, and Johannes Textor. Constructing separators and adjustment sets in ancestral graphs. Proceedings of UAI 2014, pages 907-916, 2014.
[42] Benito van der Zander. Maciej Liskiewicz, and Johannes Textor. Separators and adjustment sets in causal graphs: Complete criteria and an algorithmic framework. Artificial Intelligence, 270:
1 1-40, 2019.
[43] Kevin Xia, Kai-Zhan Lee, Yoshua Bengio, and Elias Bareinboim. The causal- neural connection: Expressiveness, learnability, and inference. Advances in Neural Information Processing Systems, volume 34, 2021.
12

---

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


Reviews:
[{"review_id": "lNn2AI7i7rd", "reviewer": "Reviewer_879A", "summary": "This paper shows the more detailed steps and pseudo-codes for finding frond-door adjustment sets in causal graphical models. Starting from the definition of front door criteria, this paper goes through the implementation of each criterion and offers a complexity analysis.", "questions": "I think the complex statements are better to be shown in the main text.\n\n\nThis algorithm works by removing nodes from the full set of candidates, which could be all nodes except for the X and Y.\nDoes this algorithm take into account \"evidence variables\"?\nIf we find a full list of FD sets from a causal graphical model, and if we introduce evidence variables, should we restart from the beginning?\n\n\nHave you implemented these pseudo-codes? \nI think it's better to double-check it by implementation on top of proofs and hand-written examples.\nIt is in a polynomial-time algorithm in terms of big-O analysis, but the overall running time may be longer than one might imagine when there are many nodes and edges in the graph. This algorithm can be served as a baseline for possible future works that improve running times and may be useful for implementing do-calculus. They are very close to script languages such as python already, and if possible, showing the results through running the program or providing it as open-source could be even more helpful to scientists who may use this FD strategy for experiment design. \n\n", "limitations": "I think this work is not relevant to this section.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The strength of this paper is showing the detailed steps for implementing frond door criteria in causal graphical models, and it finally extends by listing all frond door sets satisfying Pearl's front door criteria. \nThe weakness is that no demonstration or evaluation is available for given algorithms. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ZCl0Enq0sGn", "reviewer": "Reviewer_yYRf", "summary": "The authors propose a feasible algorithm for listing adjustment sets (one at a time in reasonable time) satisfying the front-door criterion.", "questions": "I did have some questions after having read the paper, which I didn't know how to answer.\n\n* For medical or ethical reasons, it may be necessary to avoid including certain variables in an adjustment set. Is this straightforward to do with this algorithm (i.e., simply not including the prohibited variables in any set in the course of the algorithm), or could it possibly be the case the simply excluding certain variable will prevent allowable front-door adjustment sets from being discovered?\n\n* For ethical reasons (fairness, for example), it may be necessary to disallow certain paths of influence in a model (e.g., race affecting the outcome variable). Can this be done inside the algorithms, or some one have to simply list example front-door adjustment sets and simply ignore the offending examples?", "limitations": "The last sentence addresses societal impacts: \"We hope that the methods and algorithms proposed in this work will help scientists to use the FD strategy for causal effects estimation in the practical applications and are useful for scientists in study design to select covariates based on desired properties, including cost, feasibility, and statistical power.\" This can of course be made more than a hope; perhaps answering questions such as the above (or others) might help make that a reality.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This is very strong paper, very clearly written and easy to follow. The theory and algorithms are clear and make sense. It should be easy to implement the algorithm described. The idea is novel, since no such algorithm currently exists in the literature, and it is significant, since it could easily be incorporated into existing software and used. The only criticism is that it does not include an experimental section in which the algorithm is test for accuracy and speed on particular models.\n\nMinor point.\n\nLine 252, \"no more node\" should be \"no more nodes\".", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "UstovGiQwrb", "reviewer": "Reviewer_tJUN", "summary": "Given the underlying causal diagram, this paper provides two algorithms:\n1. To find an admissible front-door adjustment set in polynomial time (if one exists).\n2. To enumerate all admissible front-door adjustment sets with polynomial delay.\n\nThese algorithms allow constraining the search to include and/or exclude specific subsets of variables which could help selecting estimands with desired properties.", "questions": "Suggestions: \n1. As mentioned by authors in section 1 (line 77) and in section 5 (lines 393-395), there has been a lot of work on finding/listing back-door admissible sets when the underlying DAG/MAG/PAG/CPDAG is known. More importantly, there has also been some work on data-driven approaches for finding/listing back-door admissible sets using only an anchor variable when the underlying causal diagram is not known. For example: (1) Entner et al 2013 -- Data-driven covariate selection for nonparametric estimation of causal effects [https://proceedings.mlr.press/v31/entner13a.html], (2) Cheng et al 2020 -- Towards unique and unbiased causal effect estimation from data with hidden variable [https://arxiv.org/pdf/2002.10091.pdf], (3) Shah et al 2021 -- Finding Valid Adjustments under Non-ignorability with Minimal DAG Knowledge [https://arxiv.org/pdf/2106.11560.pdf]. In order to provide a comprehensive background regarding what is know for finding/listing back-door admissible sets, the authors should also talk about these works.\n2. As mentioned in the weaknesses section above, this paper assumes the knowledge of the underlying causal diagram in order to find admissible front-door adjustment sets. In contrast, the recent work of Bhattacharya and Nabi-- On Testability of the Front-Door Model via Verma Constraints [https://arxiv.org/pdf/2203.00161v1.pdf] -- explores finding admissible front-door adjustment sets in a data-driven manner using only an anchor variable when the underlying causal structure is not known similar to the works mentioned above. The authors should differentiate their work from this work.\n\nTypo:\n1. Did the authors intend to say $3^n$ instead of $2^n$ on line 339?\n", "limitations": "In my opinion, the most important limitation of this work is the requirement of the underlying causal diagram which is acknowledged by the authors in Section 5. This limits the application of this work in most real-world scenarios where the causal diagram is not known. \n\nTherefore, in addition to finding/listing front-door admissible sets from incomplete or partially specified causal diagram as mentioned by the authors (in lines 395-396), it would be useful (for future research) to develop data-driven methods when the underlying causal structure is not known (except an anchor variable) by taking inspiration from the works of Entner et al 2013, Shah et al 2022, Cheng et al 2022, and Bhattacharya and Nabi 2022. ", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1. In my limited knowledge, this paper is one of the first papers to provide algorithms to find/list all admissible front-door adjustment sets (given the underlying causal diagram).\n2. Finding valid front-door sets is an important topic and of relevance to the NeurIPS community. Through this work, the authors take a first step to close the gap between what is known for back-door adjustment sets and what is known for front-door adjustment sets.\n3. By constraining the search space to include/exclude specific subsets of variables, the authors provide flexibility in selecting estimands with different cost, availability, privacy, and statistical power.\n\nOriginality:\n1. The algorithm/approach proposed in the paper relies on a mix of novel concepts (e.g., GETDEP, GETNEIGHBORS) as well as ideas known in the literature (e.g., TESTSEP, LISTSEP). However, the key novelty lies in unifying these concepts to propose FINDFDSET and LISTFDSETS.\n\nWeakness:\n1. This paper assumes the knowledge of the underlying causal diagram in order to find admissible front-door adjustment sets. In most real-world applications, the causal diagrams are unknown and this requirement is quite restrictive. \n\nClarity:\n1. In general, the paper is quite well written. Further, the algorithms and the functions are generally well explained in the text. While the authors do a decent job, the function GETDEP is a bit complicated to understand. I strongly recommend the authors to add running examples covering various scenarios that may arise in this function to make it easier for the readers.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ORlh_KV8gjF", "reviewer": "Reviewer_ebQn", "summary": "The paper develops an algorithm, i.e. FINDFDSE() to find an admissible adjustment set that satisfies the front-door criterion in a given causal DAG. The solution is to solve a variant of the problem that imposes constraints I for given sets I and R.  Based on the algorithm FINDFDSE(), a  sound and complete algorithm is developed to enumerate all front-door adjustment sets with polynomial time.  Moreover, the detailed theoretical analysis supports the soundness of the developed LISTFDSETS() algorithm.\n", "questions": "Q1. is the first weakness.\n\nQ2. In Fig. 1b, If the edge $A\\rightarrow D$ is replaced by $A\\leftarrow D$, is there still an admission front-door adjustment set $\\mathbf{Z]$? If the answer is no, are there some graphical criteria to handle such a case?", "limitations": "1. The causal DAG and the sets $\\mathbf{I}$ and $\\mathbf{R}$  need to be provided. In many real-world applications, this information is not available. Hence, the application of the developed algorithms in this work has limited application at present. \n\n2. For multiple treatments and outcomes $(\\mathbf{X, Y})$, the developed algorithms may only be able to solve very few cases, and most of them return $\\perp$.", "rating": 7, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Strengths:\n1. This work is well-motivated and organised. A large number of examples make the paper easy to follow and understand. \n2. The technical quality of the work is high. The steps of both algorithms are also very clear.\n\n*Weaknesses:\n1. Assumptions are not clear. To my understanding, the given causal DAG is a very specific class of DAGs. For example, $\\mathbf{X}=\\\\{X_1, X_2\\\\}$, $\\mathbf{Y}=\\\\{Y\\\\}$, $\\mathbf{R}=\\\\{A,B,C\\\\}$; the graph is formed: $Y\\leftrightarrow X_1 \\rightarrow A\\rightarrow B\\rightarrow Y$; $Y\\leftrightarrow X_2 \\leftarrow A$; $B\\rightarrow C \\leftarrow X_2$; $C\\rightarrow Y$. $\\forall v\\in \\mathbf{R}$, we have TESTSEP($\\mathcal{G}_{\\underline{\\mathbf{X}}}$, $\\mathbf{X}$, $v$, $\\emptyset$) = FALSE. Thus, FINDFDSET() returns $\\perp$. However, for a single $X\\in \\mathbf{X}$,   FINDFDSET() returns $A$ for $(X_1, Y)$ and $C$ for $(X_2, Y)$, respectively. Therefore, the generalization on $\\mathbf{X}$ may not be perfect.\n\n2. The ``completeness'' is not specified. Furthermore, there is no evidence for completeness. \n\nSome minors:\n1. Definition 1, \"There is no back-door path from $\\mathbf{X}$ to $\\mathbf{Z}$\"  should be \"There is no unblocked back-door path from $\\mathbf{X}$ to $\\mathbf{Z}$\". \n\n2. $\\mathbf{PA}\\_{V}$ and $\\mathbf{pa}\\_{V}$ are not defined.  \n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept