Actively Identifying Causal Effects with Latent Variables Given Only Response Variable Observable
Year: 2022

Abstract:
In many real tasks, it is generally desired to study the causal effect on a specific target (response variable) only, with no need to identify the thorough causal effects involving all variables. In this paper, we attempt to identify such effects by a few active interventions where only the response variable is observable. This task is challenging because the causal graph is unknown and even there may exist latent confounders. To learn the necessary structure for identifying the effects, we provide the graphical characterization that allows us to efficiently estimate all possible causal effects in a partially mixed ancestral graph (PMAG) by generalized back-door criterion. The characterization guides learning a local structure with the interventional data. Theoretical analysis and empirical studies validate the effectiveness and efficiency of our proposed approach.

heading: 1 Introduction
text: Identifying causal effects is one prominent task throughout empirical sciences. In many real problems, we are generally desired to study the causal effect on a specific target only, i.e. response variable, with no need to identify the thorough causal effects involving all variables. For example, a business person wants to maximize profit. The person has many intervention methods such as lowering price, increasing advertisement investment, improving quality, and so on. A valid approach to guide the decisions is to estimate the causal effect of each variable on the response variable. We call it target effect identification in this paper. After identifying all of these causal effects, the person could see which intervention could lead to the most desired response (profit).
To achieve target effect identification, an ideal method is to intervene on each decision variable with different attainable values and collect the interventional data of the response variable. However, when there are many decision variables and many attainable values for each variable, it will take enormous number of interventions, which is economically unfeasible. Considering that there is usually a large amount of observational data in reality, we hope to exploit mainly the observational data to achieve it.
The main obstacle here is that the causal graph of all involved variables is not available, which makes causal effect identification intractable. Hence, we learn the structure at first. As shown by Verma and Pearl [1], only a Markov equivalence class could be learned with observational data without further assumptions, where there are possibly unidentified causal relations resulting in unidentified causal effects. To reveal these effects, we further learn the causal relations in the Markov equivalence class by introducing a small amount of active hard interventions, i.e., we force some variable to a known value [2, 3, 4]. In practice, generally one can only observe part of variables under interventions rather than all of those, e.g., a business person can observe his profit, but does not know other companies’ profit. To make the method applicable in a broader scenario, we consider an extreme situation that only the response variable is observable, which could be trivially extended to any settings with
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
part of variables observed. In addition, there are usually latent confounders in practical problems. For instance, economic level influences both price and advertising cost, but it is hard to evaluate accurately and thus a latent confounder. In summary, in this paper we learn the causal knowledge where there are latent confounders and only the response variable is observable under interventions.
This problem is very challenging, because the fact that only the response variable is observable disables the approaches designed for situations where all variables are observable [2, 5, 6], while the existence of latent confounders disables the typical solutions [7]. To get a brief understanding of the challenges taken by latent confounders in techniques, consider a graph learned with observational data by traditional causal discovery methods [8]: If there is no latent confounder, the definite adjacent edges of intervened variable X lead to a definite interventional distribution of the response variable Y by back-door criterion [9], which makes it possible to learn the edges of X by the interventional data of Y ; when latent confounders exist, however, the mapping no longer holds. Besides, a partial mixed ancestral graph (PMAG) is commonly used to describe the relation between variables in this condition. The back-door criterion may fail in this case since there possibly exist latent confounders influencing the two variables of some directed edges. Hence, we also need to identify whether such latent confounders exist behind the directed edges, in addition to just learning the causal edges.
To overcome the difficulties above, we provide a graphical characterization that allows us to efficiently find all possible causal effects of the intervened variable on the response variable in a partial mixed ancestral graph. Guided by the characterization, we learn a local structure and identify the presence of latent confounders behind some directed edges by each intervention, which leads to identifying some causal effects on the response variable. After a few active interventions on different variables, our method ACIC, short for ACtive target effect Identification with latent Confounding, could achieve target effect identification. Due to space limit, we present related work and all the proofs in Appendix.

heading: 2 Preliminary
text: We guide readers to Appendix A.1 for the notions including causal graph (G = (V,E)), mixed graph, mark, arrowhead, tail, circle(◦), partial mixed graph, parent, child, spouse, possible directed path, (possible) ancestor, PossAn(X,G), An(X,G), (possible) descendant, PossDe(X,G), De(X,G), adjacent, Adj(X,G), almost directed cycle, collider path, minimal path, ancestral graph, m-separation (m-connecting or active), maximum ancestral graph (MAG,M), discriminating path, Markov equivalent, Markov equivalence class (MEC), partial ancestral graph (PAG), visible,MX , PX , causal effect (P (Y |do(X))), and the common assumptions including positivity and no selection bias. ∗ is a wildcard that denotes any of the marks. For a partial mixed graph, we say it is a partial mixed ancestral graph (PMAG) if there is no directed or almost directed cycle, and denote it by P . Note both MAG and PAG are special cases of PMAG, thus P could also denote PAG. The relation between PMAG and PAG is similar to that between partial directed acyclic graph (PDAG) and completed partial directed acyclic graph (CPDAG) when there is no latent confounder [10]. MAG M is consistent to PMAG P if it belongs to the MEC represented by P (detailed in Appendix A.1). For a directed edge Vi → Vj in a graph, we say the edge is pure if the two variables are not influenced by common latent confounders, denoted by Vi
p−→ Vj . We use a purity matrix to characterize the purity of each edge in a PMAG G, in which 1 is in (i, j) entry only if the directed edge Vi → Vj in G is pure, and 0 otherwise. Note that 0 does not imply that the edge is impure. It is also possible that we are unaware of whether it is pure or the edge is not directed. In the literature, a graphical characterization to imply that there are no latent confounders behind a directed edge in an MAG or PAG is proposed by Zhang [11], where they call it by visibility. Visibility is sufficient but not necessary for purity, which is detailed in Appendix A.2. Thus, given a PMAG, we initialize the purity matrix by setting (i, j) entry to 1 if Vi → Vj is visible and 0 otherwise. For an MAGM,MX˜denotes the graph by removing the directed edges out of X inM that are labeled to be pure in purity matrix. For a PMAG P , see Appendix A.4 for the definition of PX˜ . Since the graph is continuously learned by interventions in this paper, the graph in the process is a PMAG. Hence we present Prop. 1 to guide causal effect identification in a PMAG with the consideration of purity matrix rather than only in a PAG or MAG. It is based on the generalized back-door criterion (GBC) and the graphical condition for the causal effect identifiability by GBC in MAG or PAG proposed by Maathuis et al. [12]. Before that, we introduce D-SEP(X,Y,G) in Def. 1.
Definition 1 (D-SEP(X,Y,G) [12]). Let X and Y be two distinct vertices in a mixed graph G. We say that V ∈ D-SEP(X,Y,G) if V 6= X , and there is a collider path between X and V in G, such that every vertex on this path (including V ) is an ancestor of X or Y in G.
Proposition 1. Let G be a PMAG and W be a purity matrix of G. Suppose X ∈ An(Y,G) and Y are two distinct vertices in G. There exists a generalized back-door set relative to (X,Y ) and (G,W ) if and only if D-SEP(X,Y,GX˜ )∩ PossDe(X,G) = ∅. Moreover, if the set exists, D-SEP(X,Y,GX˜ )is such a set. Denote D-SEP(X,Y,GX˜ ) by D, the causal effect is
P (Y |do(X = x)) = ∫ D P (D)P (Y |D, X = x) dD. (1)
There are two possible unidentifiable cases for P (Y |do(X)) by GBC in Prop. 1. One is that there are many possible causal effects due to the missing of exact structure information, but we do not know which is correct. In this case, we could address it by learning the structure with interventional data. The other unidentifiable case is that the causal effect is unidentifiable by GBC even if we know the MAG and the purity of each edge. We return “Fail” for such X because GBC is not sufficient for identifying the causal effect in this case, and we say GBC fails ( to identify P (Y |do(X))).

heading: 3 The Proposed Approach
text: In this paper, we assume faithfulness, positivity, and no selection bias. Denote the decision variables by X1, · · · , Xp and the response variable by Y . Given the observational data of these variables, our goal is to achieve target effect identification by generalized back-door criterion, i.e., we aim to identify P (Y |do(Xi)) by GBC for each variable Xi, i = 1, 2, · · · , p if GBC does not fail. With the observational data, we can learn a PAG P that the true MAG is consistent to by FCI algorithm [8]. And we initialize a purity matrix by setting (i, j) entry to 1 if the directed edge between the two variables is visible in P and 0 otherwise. The causal effects of some variables on Y are possibly unidentifiable in P by Prop. 1. To identify these effects, we further introduce active interventions and observe Y under those. Beginning from P , in each round our method selects one variable X from Xi, i = 1, · · · , p to intervene and exploits the interventional data of Y to learn the structure, including learning an updated PMAG by revealing circles and updating the purity matrix. The process repeats until identifying all effects P (Y |do(Xi)), i = 1, 2, · · · , p (identifying failing of GBC is also included). Since it is recursive, we just present the method to learn the structure by interventional data in one round. The criterion to select the intervention variable in each round is given at the end.

heading: 3.1 Two direct methods
text: A naive method to learn the structure by interventional data is enumerating each MAGM consistent to the PMAG P . For eachM, P (Y |do(X)) can be estimated with observational data by (1) and we judge whether the estimated causal effect is consistent with the interventional data. By such judgment, we could rule out the MAGs with inconsistent causal effects. Yet, this method is usually impractical since it takes a huge computation complexity mainly from two parts. One part is the exhaustive search in the space of MAGs. As is known to all, the space of MAGs is extremely large. For each searched MAG, we also need to judge whether it is consistent to P1. The other costly part is looking for D-SEP(X,Y,MX˜ ) according to Def. 1 to estimate causal effects by (1) for each MAG. A cleverer approach instead of enumerating is to directly learn a local structure by interventional data, inspired by ACI proposed by Wang et al. [7]. ACI tackles a similar task but assumes no latent confounders. The core of this approach is to find an equivalent condition that could be obtained based on a local structure for causal effect. In this way, there is a bijection between the condition and P (Y |do(X)), by which we could learn a local structure with the interventional data of Y . Specifically, ACI is comprised of three steps: (a) propose Minimal Parental back-door admissible Set (MPS), a variable set that could be obtained by only the orientation of adjacent edges of X , as the equivalent condition for P (Y |do(X)); (b) find all possible MPSs in the partial graph to be learned; (c) identify which MPS is correct by interventional data and learn the adjacent edges of X implied by the MPS.
1For such judgment, we could first obtain an MAG based on P by the procedure of Theorem 2 by Zhang [13], as a representative of P . Then we judge whether the searched MAG is Markov equivalent to this MAG by the necessary and sufficient condition for Markov equivalence by Ali et al. [14], Hu and Evans [15].
However, ACI fails if there are latent confounders. In this situation the adjacent edges of X is not sufficient for identifying causal effects. According to Prop. 1, even though there are the same adjacent edges of X in two MAGs, the causal effects of X on Y are possibly different if they have different D-SEP(X,Y,MX˜ ). See Fig. 1(a) and Fig. 1(b) for example. The method of Malinsky and Spirtes[16] is possibly useful here, which estimates all possible causal effects in P by enumerating the structures in a relatively local region, but the two parts of computational costs above are still large.
Referring to the framework of ACI, we propose the three steps for our setting in the next three sections. Firstly, we propose MCS, as an equivalent condition for P (Y |do(X)) in MAG by GBC in Sec. 3.2. Secondly, we present how to find all MCSs in P by graphical characterization in Sec. 3.3. It is the main challenge here in contrast to ACI. ACI achieves it by considering all possible orientations of adjacent edges of X due to the fact that their proposed MPS merely depends on these edges. In our setting, however, it is unclear which edges MCS depends on. And obviously, enumerating all edges is not efficient. Hence we propose a graphical characterization to guide it. Lastly, we give the method to learn marks and purity matrix by interventional data in Sec. 3.4 with all MCSs found before.

heading: 3.2 The equivalent condition for causal effects
text: By Prop. 1, D-SEP(X,Y,MX˜ ) can be as the adjustment set to identify P (Y |do(X)) when GBC doesnot fail. Thus, we construct the equivalent condition for P (Y |do(X)) based on D-SEP(X,Y,MX˜ ).Note that D-SEP(X,Y,MX˜ ) cannot be used directly since the causal effects are possibly equal inthe MAGs with different D-SEP(X,Y,MX˜ ). See Fig. 1 for an example. The D-SEP(X,Y,MX˜ ) in(a) and (c) are {A,B} and {B}, respectively, but P (Y |do(X)) are equal. The reason is A ⊥ Y |X,B in the two MAGs. When calculating (1), the results are equal after integration on the generalized back-door set. To formalize this situation, we introduce Minimal Conditional Set (MCS) regarding D-SEP(X,Y,MX˜ ) inM. The algorithm to find MCS and the related properties are in Appendix B. Definition 2 (Minimal conditional set regarding D-SEP(X,Y,MX˜ ) (MCS)). LetM be an MAG.X , Y , and D denote the intervened variable, response variable, and the set D-SEP(X,Y,MX˜ ) inM, respectively. D is a subset of D. D is a minimal conditional set regarding D inM if
(1) (Y ⊥ D\D |D ∪ {X})M,
(2) (Y 6⊥ D\D′|D′ ∪ {X})M, for any D ′ ⊂ D.
We call it MCS regarding D-SEP(X,Y,MX˜ ) or MCS for short. Note that MCS is essentially a set ofvariables. For all MAGsM satisfying the conditions of Prop. 1 with the same D, where D denotes the MCS regarding D-SEP(X,Y,MX˜ ) in respectiveM, they have the same causal effect as
P (Y |do(X = x)) = ∫ D P (D)P (Y |D, X = x) dD. (2)
Since structure inference with interventional data is involved, we make an additional assumption as Assumption 1 to match interventional data to causal graph, playing as the role of faithfulness given only observational data or some intervention-related assumptions[17, 7, 6, 18]. The purpose is to avoid that different causal effects in general (e.g. the causal effects P (Y |do(X)) in Fig. 1(a) and Fig. 1(b) ) happen to be equal given some specific observational distributions. Under the assumption,
there is a bijection between MCS and P (Y |do(X)) through (2). Finding all possible causal effects could be converted to finding all possible MCSs. In the next section, we present how to find all possible MCSs in a PMAG by our proposed graphical characterization.
Assumption 1. For two Markov equivalent MAGs M1 and M2 with the same observational distribution, if there are different minimal conditional sets regarding D-SEP(X,Y,M1X˜ ) andD-SEP(X,Y,M2X˜ ) in the respective graphs, then P ( Y |do(X = x) ) are different in the two MAGs.

heading: 3.3 Finding all MCSs in P by graphical characterization
text: At the beginning, we provide an outline of finding possible MCSs regarding D-SEP(X,Y,MX˜ ) inallM consistent to P if GBC does not fail to identify P (Y |do(X)) inM. The justification for the restriction onM is that ifM is the true MAG and GBC fails to identify P (Y |do(X)) inM, there is no MCS matched to the interventional data. We thus cannot identify an MCS by the intervention. In this case it is unnecessary to find MCS in suchM. Hence, we consider the MAGM that satisfies D-SEP(X,Y,MX˜ ) ∩ De(X,M) = ∅, according to Prop. 1. There are three main parts to achieveit. The first part is to enumerate all mark combinations of X . The true MAG is with one mark combination among them. As mentioned earlier, the marks of X are not sufficient for identifying P (Y |do(X)). In another word, MCSs could be different in the MAGs with the same marks at X . Hence, in the second part we propose the graphical condition to indicate when there are different MCSs in the MAGs with the same marks at X . And this graphical condition can be obtained in a partial graph. Based on that, we present the algorithm to find all possible MCSs in P in the third part. We first enumerate all possible mark combinations of X . To denote the PMAGs with deterministic marks atX , we introduce local MAG ofX based onP in Def. 3. For a local MAGM and an MAGM consistent to M , we then present a sufficient and necessary condition for V ∈ D-SEP(X,Y,MX˜ ) inThm. 2, which plays a vital role for the following result involving MCS regarding D-SEP(X,Y,MX˜ ). Definition 3 (Local MAG of X based on P). Given a PMAG P and a variable X , a PMAG M is a local MAG of X based on P if (1)M is with definite marks (arrowheads or tails) at X; (2)M is obtained from P by marking some circles without generating new unshielded colliders or directed or almost directed cycles. We call it local MAG for short if there is no ambiguity and denote it by M , which is different from calligraphicM that denotes MAG.
Theorem 2. Let M be a local MAG of X andM be an MAG consistent to M . Suppose V (V 6= X,Y ) is a variable inM. If D-SEP(X,Y,MX˜ ) ∩ De(X,M) = ∅, then V ∈ D-SEP(X,Y,MX˜ )holds if and only if there is at least one collider path from X to V starting by an arrowhead at X in M such that each variable except for X on the path is an ancestor of X or Y inM.
The advantage of considering local MAG of X rather than P with circles at X is that based on local MAG we could obtain a set of variables, PD-SEP(X,Y,M), as Def. 4. This set implies some variables in D-SEP(X,Y,MX˜ ) and has a good property that if PD-SEP(X,Y,M)\D-SEP(X,Y,MX˜ ) 6= ∅,there must be at least one variable V ∈ PD-SEP(X,Y,M) which is not an ancestor of X or Y inM, as shown by the combination of Thm. 2 and Def. 4. This property is utilized to prove the main result.
Definition 4 (PD-SEP(X,Y,M)). Let M be a local MAG of X andM be an MAG consistent to M . Variable V ∈ PD-SEP(X,Y,M) if and only if V ∈ PossAn(Y,M)\De(X,M)2 and there exists a collider path between X and V in M , where each non-endpoint variable is an ancestor of X or Y in M but not a descendant of X inM. Remark. In the literature, there is a well-defined notion Possible-D-SEP(X,Y ) [8, 19], which is introduced with the similar intention that indicates some variables possibly belonging to D-SEP(X,Y,M). Since ours is pretty different in both required conditions and the restriction on ancestral relations, we use a new name PD-SEP(X,Y,M) to distinguish them.
With the knowledge above, we present our main result in Thm. 3. Perhaps surprisingly, it implies that given a local MAG M , although there are possibly different D-SEP(X,Y,MX˜ ) in distinct MAGM
2Note all the descendants of X inM consistent to M are knowable in M , which is detailed by Lemma 19 in Appendix C.1. Hence PD-SEP(X,Y,M) can be obtained based on M without the further knowledge aboutM.
Algorithm 1 Find all possible MCSs in P input: Intervention variable X , PAG P
1: L← ∅ // It is to record each local MAG M j and corresponding MCSj 2: for each local MAG M j of X based on P by merely marking the marks at X do 3: if there is critical variable set Cj for (X,Y ) in M j then 4: CRITICAL(M j ,Cj ,Sj) // Sj (Sjk below) is the set S defined in Def. 5 in M j (M jk) 5: else 6: L = L ∪ (M j ,MCSj) 7: end if 8: end for 9: function CRITICAL(M j ,Cj ,Sj) 10: for each element Cjk in the power set of Cj do 11: Obtain a new local MAG M jk by orienting F → S for ∀F ∈ Cjk ,∀S ∈ Sj and marking
the critical marks of F ∈ Cj\Cjk as arrowheads 12: if there is critical variable set Cj for (X,Y ) in M jk then 13: CRITICAL(M jk ,Cjk ,Sjk ) 14: else 15: L = L ∪ (M jk ,MCSjk) 16: end if 17: end for 18: end function output: L
consistent to M , the MCSs regarding them are the same if there are no critical variables for (X,Y ) in M . We define critical variables for (X,Y ) in Def. 5, and show an example in Fig. 2, where Ft is a critical variable and the circles colored by red are critical marks.
Definition 5 (Critical variable for (X,Y )). In a local MAG M with a path X ↔ F1 ↔ · · · ↔ Ft−1 ↔ Ft or X ↔ F1 ↔ · · · ↔ Ft−1 ←◦Ft, t ≥ 1, where F1, · · · , Ft−1 ∈ PD-SEP(X,Y,M), Ft is called a critical variable for (X,Y ) if there is a non-empty variable set S relative to Ft defined as follows: S ∈ S if and only if in M (1) S is a child of X,F1, · · · , Ft−1, (2) there is Ft ◦−∗ S, (3) S is at one minimal possible directed path from Ft to Y , and no variable on the path belongs to PD-SEP(X,Y,M). Each circle at Ft on the edge with Ft−1 or S ∈ S is called a critical mark of Ft.
Theorem 3. Let M be a local MAG of X based on a PMAG P . Then condition (1) below is sufficient for condition (2):
(1) there is no critical variable for (X,Y ) in M .
(2) for any an MAGM consistent to M such that (a) D-SEP(X,Y,MX˜ ) ∩ De(X,M) = ∅,(b) X ∈ An(Y,M), it holds that AM = A′M, where AM denotes the MCS regarding D-SEP(X,Y,MX˜ ) inM and A′M denotes the MCS regarding PD-SEP(X,Y,M) inM; Remark. It is noteworthy that all the MAGs consistent to M are Markov equivalent. Hence the MCSs regarding PD-SEP(X,Y,M) in these MAGs are the same, namely, A′M is invariant for differentM. If there is no critical variable as condition (1), then for any MAGM consistent to M , AM = A′M holds according to Thm. 3. We thus conclude AM is invariant for differentM consistent to M , i.e., different D-SEP(X,Y,MX˜ ) in distinctM consistent to M share the same MCS regarding them.
Def. 5 and Thm. 3 form a graphical characterization that allows us to obtain all possible MCSs in all MAGs consistent to a local MAG M . We propose Alg. 1 to find all MCSs in P based on it. Given a PMAG P , it is easy to find local MAGs M based on P by differently marking the circles at X without generating new unshielded colliders and directed or almost directed cycles (Line 2). For each M , if there is no critical variable in M , the
MCS regarding D-SEP(X,Y,MX˜ ) is unique, and it equals tothe MCS regarding PD-SEP(X,Y,M) (Line 6). When there is a non-empty critical variable set C,
the MCSs in the MAGs consistent to M could be different. The reason is that the variable in C could
be the ancestor of X or Y in some MAGs but the non-ancestor in other MAGs, due to the unidentified critical marks. Conditioning on the non-ancestor variables above makes some generalized back-door paths from X to Y active, thus these variables cannot appear in MCS. Hence, we further discuss the critical marks. For any subset Ck of the critical variable set C, there could possibly be some MAG M consistent to M where Ck ⊆ D-SEP(X,Y,MX˜ ) and (C\Ck) ∩ D-SEP(X,Y,MX˜ ) = ∅. Weuse a new local MAG to represent the common parts of these MAGs (Line 10,11). And in the new one, we further consider whether critical variable exists (Line 12). The soundness of Alg. 1 is shown in Lemma 4, i.e. no matter what the true MAGM is, the MCS regarding D-SEP(X,Y,MX˜ ) inMcould be returned as long as D-SEP(X,Y,MX˜ ) ∩ De(X,M) = ∅. Lemma 4. Let P be a PMAG of MAG M. If X ∈ An(Y,M) and D-SEP(X,Y,MX˜ ) ∩De(X,M) = ∅, then the MCS regarding D-SEP(X,Y,MX˜ ) inM and the corresponding localMAG are contained in the output of Algorithm 1.

heading: 3.4 Learning marks and purity matrix by interventional data
text: In this section we propose how to learn marks and purity matrix by the interventional data of Y . After intervening on X , there are three possible situations implied by the interventional data of Y .
(1) X has no causal effect on Y , i.e., P (Y |do(X)) = P (Y ), (2) X has causal effect on Y and it can be identified by GBC, i.e., there exists a generalized
back-door set D such that P (Y |do(X)) = ∫ P (D)P (Y |X,D) dD,
(3) X has causal effect on Y but GBC fails to identify it.
For situation (1), it is trivial to learn the marks by the interventional data according to Prop. 5. Proposition 5. If P (Y |do(X)) = P (Y ), the marks at X are arrowheads in all the minimal possible directed paths from X to Y in a partially mixed ancestral graph.
If P (Y |do(X)) is not equal to P (Y ), it implies that the interventional data accords with situation (2) or situation (3) but is uncertain to us. Hence, we need to find all possible MCSs based on P , then judge whether one of the estimated causal effects with the observational data by (2) is consistent to the interventional data. If so, we can see that the causal effect of X on Y can be identified by GBC in the true MAG. Specifically, we first obtain a group of pairs (M j ,MCSj) by Alg. 1, where M j is a local MAG and MCSj is the corresponding MCS. Let P̂Mj ( Y |do(X = x) ) and P̂ ( Y |do(X = x)
) denote the estimated causal effect in each M j by MCSj and that under real intervention respectively. Disc(P,Q) is the distribution discrepancy between P and Q. If there are m intervention samples( (do(X = x1), Y1 ) , · · · , ( do(X = xs), Ys ) , · · · , ( do(X = xm), Ym) ) , we take MCS? by
MCS? = argmin MCSj m∑ s=1 Disc ( P̂MCSj ( Y |do(X = xs) ) , P̂ ( Y |do(X = xs) )) . (3)
Any distance metric can be used here. Since the attention is not on calculation, we take the expectation difference as the metric for convenience, i.e., MCS? = argminMCSj ∑m s=1|ÊMCSj ( Y |do(X =
xs) ) − Ys|. If the distance between the estimated causal effect by MCS? and interventional data is larger than a given threshold, we think that GBC fails to identify such causal effect. We thus mark such X as “FAIL” and orient some edges by Prop. 6. Otherwise, if there is only one local MAG M∗ corresponding to MCS?, we orient P by M∗. If there are more than one local MAG corresponding to MCS?, we orient P by the common marks of the local MAGs with MCS?. Besides, when GBC does not fail to identify the causal effect, all the edges out of X in the minimal directed paths from X to Y in the PMAG are learned to be pure. Thus we could update the purity matrix accordingly. Proposition 6. In situation (3), let T denote all variables adjacent to X in the minimal possible directed paths from X to Y . For T ∈ T, if for ∀V ∈ T\T , it holds either T 6∈ Adj(V,P) or there is a variable S 6∈ Adj(V,P) such that there is a collider path X◦→ T ↔ · · · ←∗S and every vertex except S on the path is a parent of V , then X → T .
After the learning process above, we can further update the PMAG according to the property of MAG. Zhang [13] proposed ten complete rules with only observational data. However, how to orient PMAG
Algorithm 2 ACIC (ACtive target effect Identification with latent Confounding) input: PAG P by FCI algorithm;
1: Initialize I1 = {V |V ∈ V(P), V ∈ PossAn(Y,P) and P (Y |do(V )) is unidentifiable by Prop. 1 in P} // Record the variables whose causal effects on Y are unidentifiable by Prop. 1 2: Initialize I2 = ∅ // Record the variables whose causal effects are failed to be identified by GBC 3: while I1\I2 6= ∅ do 4: Select a variable X with the maximum number of circles from I1\I2 to intervene 5: if P (Y |do(X)) equals to P (Y ) then 6: Update P by Prop. 5 7: else 8: Find all possible MCSs in P by Alg. 1 and select MCS∗ by Eq. 3 9: if 1m ∑m s=1|ÊMCS∗ ( Y |do(X = xs) ) − Ys| ≤ τ then // τ is a pre-set threshold 10: if there is only local MAG M∗ with MCS∗ then 11: Update P to M∗, and label all the edges out of X in the minimal directed paths
from X to Y pure 12: else there is more than one local MAG M∗1 ,M∗2 , · · · ,M∗k 13: Update P with the common marks in M∗1 ,M∗2 , · · · ,M∗k , and label all the edges
out of X in the minimal directed paths from X to Y pure 14: end if 15: Update P further based on the 11 rules for orienting PAGs with background knowl-
edge, and update the purity matrix if some directed edges are newly identified to be visible 16: else // In this case GBC fails to identify P (Y |do(X)) 17: Update P by Prop. 6 18: I2 = I2 ∪ {X} 19: end if 20: end if 21: Update I1 by Prop. 1 with the updated PMAG P and the updated purity matrix 22: end while output: The estimated causal effect of each variable on Y .
completely with the learned knowledge by interventional data is still an open problem. We add an additional rule referring to the known results for CPDAG [20]. But regretfully, whether the eleven rules are complete is unknown. In the updated graph, some directed edges are newly identified to be visible, thus they are identified to be pure. Hence we could also update the purity matrix accordingly.
Rule 11: If a◦→ b→ c, a, b, c ∈ Adj(d), a 6∈ Adj(c), and a, d, c do not form an unshielded collider, then d→ c.
Proposition 7. Rule 11 is sound.
Combining all the parts above, we present the whole process in Alg. 2. In a PMAG obtained by FCI or learned after interventions, we judge which variables are possible ancestors of Y by Prop 8. If there are variables with unidentified causal effects on Y (Line 1) among them and we are not sure whether GBC fails to identify the effects (Line 3), we select one variable from them to intervene (Line 4) and learn structure by the interventional data (Line 5 - Line 20). Since intervention is expensive in reality, we hope achieving target effect identification with fewer intervention times. Hence, among the variables mentioned above, we greedily intervene on the one with the maximum number of circles. A running example is given in Appendix F to illustrate the detailed procedure of the proposed method. Proposition 8. In a PMAG P , if there is no minimal possible directed path from X to Y , then X cannot be ancestor of Y in any MAG consistent to P . And it holds that X 6∈ PossAn(Y,P).

heading: 4 Theoretical Results
text: In this section, we first prove the identifiability of causal effects3. Then we provide an analysis about the computation complexity of estimating all possible causal effects of each variable X on Y .
3Note when we intervene, we have the information of P (Y |do(X = x). However, we aim to identify P (Y |do(X)) when we say causal effect identification.
Theorem 9. Given the observational distribution of the observed variables, if there exists a valid generalized back-door set for (X,Y ) in the true MAG with the knowledge of the purity of each directed edge, then we can identify this set by only additional data of Y under intervention on X .
Thm. 9 implies causal effect identifiability of each X on Y by interventions. In practice, when we intervene on X , in addition to identifying P (Y |do(X)), our method could learn some marks and the purity of some edges, which lead to the causal effect identification of other variables on Y . Hence we usually make target effect identification by far fewer intervention times than the variable number.
Estimating all possible causal effects takes the main computational cost. The process of estimating possible effects in a PMAG comprises finding all MCSs in Sec. 3.3 and using (2). We analyze the complexity of Sec. 3.3. Since the complexity is strongly related to the graph, it is hard to analyze for a general graph due to the randomness of the skeleton. We consider a special case - the complete graph, which is often considered as the most difficult graph to learn, because it has the most edges and we can learn no marks by only observational data as a result of no conditional independent relationship between the variables. To ensure that the interventional data accords with situation (2) or (3) when finding all MCSs in the PMAG is necessary, we set Y as the descendant of all of X1, · · · , Xp. Due to space limit, we present a brief analysis here, while a detailed version is provided in Appendix E.2.
Proposition 10. LetM be a complete MAG with p+ 1 variables X1, · · · , Xp, Y , where the causal order of the variables except Y is completely random and Y is at the last. Denote the graph obtained by FCI with observational data by P and intervention variable by Xi. And let M be a local MAG of Xi with p− 1− k tails and k arrowheads at Xi. The computational complexity of finding all possible causal effects P (Y |do(Xi)) in all the MAGs consistent to M is O(2k). Further, the computational complexity of finding all causal effects P (Y |do(Xi)) in all the MAGs consistent to P is O(3p).
Let S denote the set of variable that has an edge with an arrowhead atXi. Since the graph is complete, for any subset S1 of S, we could construct an MAGM based onM such that MCS inM is S1, which is detailed in Appendix E.2. Hence there are 2k causal effects of Xi on Y in the MAGs consistent to M . Our method thus achieves the minimum complexity in finding possible causal effects in M .
However, when estimating causal effects of Xi on Y in P , the complexity of our method is O(3p), while there are 2p−1 causal effects in P . The gap is from two aspects. One is the search for critical variables. The other is that the causal effects in MAGs from different local MAGs are possibly equal, while these causal effects are considered separately based on each local MAG. The complexity of the latter part
dominates. While if we do not consider the graphical characterization based on critical variable and adopt the local method of Malinsky and Spirtes [16] in estimating causal effects that enumerates MAGs in a subregion, the complexity is exponentially larger than ours, as shown in Table 1.

heading: 5 Experiments
text: In this section, we apply our method on synthetic dataset to validate the effectiveness and efficiency of the proposed method. The code is developed based on R package “pcalg” [21].
We generate 100 random causal graphs and evaluate the number of correctly identified causal effects. In each graph, there are p = 15 variables and an edge occurs between two variables with probability 0.3. We randomly take 3 variables as latent confounders. And the last observed variable in the causal order is set to the response variable. We generate linear Gaussian data4 according to the causal graph. Based on these information, we know not only the true MAG, but also whether each edge is pure. Hence we have the ground truth causal effect of each variable on the response variable by GBC. Beginning from the PAG obtained by the true MAG, we record the number of correctly identified causal effects under different intervention times with different methods.
4When variables are continuous, the positivity assumption tends to be violated. Here we ignore such risks because the identifiability has been proven and we just want to test whether the proposed method could accurately learn the structure and identify the generalized back-door set.
In our method, we adopt a greedy strategy to select the intervention variable. To verify the feasibility, we design a baseline method ACIC-simple, where we randomly select the intervention variable of which the causal effect on Y has not been identified. To distinguish the methods with different strategies, we call our method ACIC-greedy. There are two additional baseline methods, Do and ACI [7].
For Do, it identifies causal relations by judging whether the distribution of observed variable takes a change under intervention, which idea is applied widely in many active causal discovery methods [2, 3]. Since in these methods all the variables could be observed under intervention, we allow Do to select which variable Xj to observe under intervention instead of observing Y . The results are shown in Figure 3. The superiority of ACIC-greedy to ACIC-simple implies the greedy strategy to intervene helps saving intervention times. The phenomenon that ACIC-greedy is more efficient than Do verifies that exploiting causal effect elaborately could take us more message about the structure. There are many effects wrongly identified by ACI, which indicates the risk of ignoring latent confounders.

heading: 6 Conclusion
text: In this paper, we tackle the problem of identifying the causal effect of each variable on the response variable when the causal graph is unknown and there may exist latent confounders. We present the graphical characterization that allows us to find all possible causal effects in a PMAG. The characterization guides learning structure with the interventional data of only the response variable. Our method can achieve target effect identification effectively and efficiently in both saving intervention times and reducing computational complexity. And they are verified theoretically and empirically.
There are two main aspects to improve the method. One is on how to completely update a PMAG with the learned knowledge by interventional data. The other is on how to reduce the computational complexity further if possible. We look forward to future work that could address these problems.

heading: Acknowledgment
text: This research was supported by NSFC (61921006) and the Collaborative Innovation Center of Novel Software Technology and Industrialization. The authors would like to thank Tian Qin, Jie Qiao, Wei Chen, Peng Zhao, and Zhi-Hao Tan for helpful discussions. We are also grateful to the reviewers for their valuable comments.

Review summaries:
Based on the ancestral graph framework, the authors tackle the problem of identifying an interventional distribution $f (Y | do (X))$ by only observing the outcome $Y$ after each possible intervention. This work extended previous work by Wang et al. assuming no latent variables on the graph. 

This paper develops a method for identifying causal effects on a response variable from observational and interventional data, with the restriction that under interventions only the response variable can be measured. The method does not assume away latent confounders. Theoretical justifications and some empirical evaluations of the method are presented .  

The paper proposes a method to identify the causal effect of each treatment variable on a response variable under latent confounding. The method starts from a PAG and further learning its structure by using the Generalized Backdoor Criterion (GBC) or resorting to interventional data where only the response variable is observed. The process finishes when all effects have been identified. For this, the authors introduce a graphical condition based on the notions of "local MAG" and "critical variables" that allow them to determine the existence of a minimal conditional set (MCS) that is valid for adjustment for some effect P(Y | do(X)).