Actively Identifying Causal Effects with Latent Variables Given Only Response Variable Observable
Authors: Tian-Zuo Wang
Zhi-hua Zhou
Venue: NeurIPS 2021 Poster (2021)
Keywords: causal effect identification
maximal ancestral graph
latent confounders
causal discovery

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.

Actively Identifying Causal Effects with Latent Variables Given Only Response Variable Observable
Tian-Zuo Wang and Zhi-Hua Zhou'
National Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, 210023, China, Pazhou Lab, Guangzhou, 510330, China. (wangtz, (oouzh)@ammie nju. edu. cn
Abstract
In many real tasks, 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.
Introduction
Identifying causal effects is one prominent task throughout empirical sciences. In many real problems, are generally desired study the causal effect 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 lowering price, increasing advertisement investment, improving quality, and so on. A valid approach to guide the decisions 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 the most desired response (profit).
To achieve target effect identification, an idcal 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, will take enormous number of interventions, which is economically unfeasible. Considering that there is usually large amount of observational data in reality, we hope to exploit mainly the observational data to achieve
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 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, further learn the causal relations in the Markov equivalence class by introducing a small amount of active hard interventions, i.c., 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 broader scenario, consider 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 (NcurIPS 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 evaluate accurately and thus 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 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.
2 Preliminary
We guide readers to Appendix A.1 for the notions including causal graph (G = (V,E),, E)), mixed graph, mark, arrowhead, tail, circle(o), partial mixed graph, parent, child, spouse, possible di- recied 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 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 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 the MEC represented by P (detailed in Appendix A.I).
For a directed edge V, + V, in a graph, we say the edge is pure if the two variables are not influenced by common latent confounders, denoted by V, 2 Vy. We use 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 V/2 + Vi 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 latent confounders behind a directed edge in 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 PMAG, we initialize the purity matrix by setting (i, entry to if V; + V3 is visible and 0 otherwise. For an MAG M, MMx denotes the graph by removing the directed edges out of X in M that are labeled to be pure in purity matrix. For 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 PMAG. Hence we present Prop. 1 to guide causal effect identification in a PMAG with the consideration of purity matrix rather than only PAG or MAG. 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, (E,,,XYY,CC, Y,G) in Def. 1.
based on the generalized
2

---

Definition 1 (D-SEP X. G) [12)). Let X and Y be two distinct vertices in mixed graph G. We say that V E D-SEP(X, Y, G) V # X, and there is 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 Let be a PMAG and W be a purity matrix G. Suppose X E AAnAY, G) and Y two distinct vertices in G. There exists a generalized back-door set relative to (X, Y) and (G, W) if and only if DDS-PP(X X, Y, Gx) n (oosDe(X,,o0 G) = 0. 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)xx===)->>> = ( P(D)P(YID.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 unidentifiable by GBC even if we know the MAG and the purity of euch edge. We return "Fail" for such X because GBC is not sufficient for identifying the causal effect in this case, and we say GBC ( to identify P(Y]do(X))
3 The Proposed Approach
In this paper, we assume faithfulness, positivity, and no selection bias. Denote the decision variables by X1.... .x and the response variable by Y. Given the observational data of these variables, our goal is to achieve target effect identification by generalized door criterion, i.c., we aim to identify P(Y]do(X) (d)) by GBC for each variable X,, i 1,2,.. ..................... .P 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, entry to 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 to intervene and exploits the interventional data of Y to learn the structure, updated PMAG by revealing circles and updating the purity matrix. The process
from X,, = 1, 1,
including learning repeats until identifying all effects P(Y (Y)o),))). 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.
3.1 Two direct methods
A naive method to learn the structure by interventional data is enumerating each MAG M consistent to the PMAG P. For each M, 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 Pl, The other costly part is looking for D-SEP Y, Mx) according to Def. I to estimate causal effects by (I) for each MAG.
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 similar task but assumes latent confounders. The core of this approach is to find an equivalent condition that could be obtained based on local structure for causal effect. In this way, there is a bijection between the condition and P(Y (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), 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.
For such judgment, we could first obtain an MAG based on P by the procedure of Theorem 2 by Zhang [13], as 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].
3

---

(b)
(c)
Figure 1: Suppose X Y is pure. The adjacent edges of X are the same in (a) and (b), but the causal effects are different due to the different marks at C. In addition, although D-SEP (X, Y, Mx) are different in (a) and (c), the causal effects of X on Y are the same by (1), since A T Y X, B.
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. 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, M. See Fig. (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 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. 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 Lastly, we give the method to learn marks and purity matrix by interventional data in Sec. 3,4 with all MCSs found before.
3.2 The equivalent condition for causal effects
By Prop. D-SEP(X, Y, Mx) ) can be the adjustment set to identify P(Y P())))XX) when GBC does not fail. Thus, we construct the equivalent condition for P(Y do(X)) P(Y)do(X)) based on D-SEP (X, Y, Y.Mx). Note that D-SEP(X, Y, My) ) cannot be used directly since the causal effects possibly equal in the MAGs with different D-SEP(X, M.). See Fig. for an example. The (-SEP(X, Y, Mx) in (a) and (c) are (A, B} and [B}. respectively, but P(Y (X)) are equal. The reason is A T 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) in M. The algorithm to find MCS and the related properties are Appendix B.
Definition 2 (Minimal conditional set regarding D- D-SEP(XX, Y, Mx) (MCS).. Let M be an MAG. X, Y, and denote the intervened variable, response variable, and the set D-SEP(X,, Y, Mx) in M, respectively. D subset of D. D minimal conditional set regarding D in M if
(1) ( 1 DÍD D (
(2) (Y DDDD''D U (XT)M, for any D C D.
We call it MCS regarding D-SEP(X, Y,M) MCS for short. Note that MCS is essentially a set of variables. For all MAGS M satisfying the conditions of Prop. with the same D. where D denotes the MCS regarding D-SEP(X, M, in respective M, they have the same causal effect as
P(Y]do(X = x)) = / X dD.
(2)
Since structure inference with interventional data is involved, we make an additional assumption as Assumption to match interventional data to causal graph, playing as the role of faithfulness given only observational data some intervention-rellted assumptions[17, 7, 6, 18]. The purpose is to avoid that different causal effects general (e.g. the causal effects ((Y)do(X] (X)) in Fig. 1(a) and Fig. 1(b)) happen to be equal given some specific observational distributions. Under the assumption,

---

there is bijection between MCS and P(Y]do( 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 PMAG by our proposed graphical characterization.
Assumption 1. For two Markov equivalent MAGs M and M² with the same observational distribution, if there are different minimal conditional sets regarding D-SEP(X, Y, M and D-SEP(X,Y, in the respective graphs, then P(Y]do(X= = x))
are different in the two MAGs.
3.3 Finding all MCSs in P by graphical characterization
At the beginning, we provide outline of finding possible MCSs regarding D-SEP(X, Y, M,) in all M consistent to P if GBC does not fail to identify P(Y]d((X) in M. The justification for the restriction M is that if M is the true MAG and GBC fails to identify P(Y (do())) in M, 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 such M. Hence, we consider the MAG M that satisfies D-SEP(X, Mx) n De(X, M) = 0, according to Prop. 1. There are three main parts to achieve it. 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 (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 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 at X, we introduce local MAG of X based on P in Def. 3. For local MAG M and an MAG M consistent to M, we then present sufficient and necessary condition for V E D-SEP(X,, Y, Myy in Thm. 2, which plays vital role for the following result involving MCS regarding D-SEP Mx).
Definition 3 (Local MAG of X based on P). Given a PMAG P and a variable X, a PMAG M is local MAG of X based on P if (1) M is with definite marks (arrowheads or tails) 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 ambiguity and denote it by M, which is different from calligraphic M that denotes MAG.
Theorem 2. Let M be a local MAG of X and M be an MAG consistent to M. Suppose V (V * X, Y) is a variable in M. If (X,, Y. Mx) n De MM) = 0, then V E D-SEP(XX, 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 an ancestor of X or Y in M.
The advantage of considering local MAG of X rather than P with circles at X is that based on local MAG we could obtain set of variables, PD-SEP X, Y, M), as Def, 4. This set implies some variables in D-SEP(X, Y, MMx and has good property that if PD-SEP(X, X, Y, .M) D-SEP (X, Y,Mx) A 0, there must be least one variable V E PD-SEP X, Y, M) which is not an ancestor of X Y in M, 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 local MAG of X and M be an MAG consistent to M. Variable V E PD-SEP(XX (X, Y. .M) if and only if V E PossAn(Y,, M) MD)Deee. M) 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 in M.
Remark. In the literature, there is well-defined notion Possible-D-SEE(XX Y) [8. 19], which is intro- duced with the similar intention that indicates some variables possibly belonging to D-SEP(X, M,. Since ours pretty different 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 Y, MM) in distinct MAG M
Note all the descendants of X in M consistent to M are knowable in M. which is detailed by Lemma 19 in Appendix C.I. Hence PD-SEP(XX, Y, A)) can be obtained based on A without the further knowledge about M.
5

---

Algorithm Find all possible MCSs in P
input: Intervention variable X, PAG P
1: L + 0
I/ It is to record each local MAG M and corresponding MCS/
2: for each local MAG M of X based P by merely marking the marks at X do
3: if there is critical variable set C for (X.Y) in M then
4:
CRITICAL(M C², S*) // S (S)x below) is the set S defined in Def. 5 in M (M²)
5: else
6: L- (MLUMM,MC MCS')
7: end if
8:
end for
9: function CRITICAL(M C
for each element C in the power set of C do
11:
Obtain new local MAG M by orienting F - S for E C/,, WS S and marking the critical marks of F E C*ACA C as arrowheads if there is critical variable set C2 for (X.Y) in Mis then CRITICAL(MER, Crk S
12:
14: else
15:
L L M
16:
end if
17: end for
18:
end function
output: L
consistent M. the MCSs regarding them are the same if there are no critical variables for (X, in M. We define critical variables for (X, Y) in Def. 5, and show example in Fig. 2, where F3 is critical variable and the circles colored by red are critical marks.
Definition 5 (Critical variable for (X, Y)). In local MAG M with a path X Fi
+ Fi-1 ++ F2 or X + F1 + ... ++ Fi-1 folF, t 2 1, where Fi.... F E FD-SEP(X,Y,,. F, called critical variable for (X, Y) if there is non-empty variable set S relative to F3 defined as follows: S S if and only if in M (1) S is a child of X, F1.
Fi-1, (2) there is F₁ o-+ S,
(3) S is at one minimal possible directed path from F, to Y, and no variable on the path belongs to PD-SEP(X, Y, M). Each circle at F; on the edge with Fi-1 or S E S is called critical mark of F,.
Theorem 3. Let M be local MAG of X based on PMAG P. Then condition (1) below is sufficient for condition (2):
(1) there is no critical variable for Y) in M.
(2) for any MAG M consistent M such that (a) D-SEP Y,Mx) n De(X,
(b) X E An(Y.M), it holds that AM = A'M- where AM denotes the MCS regarding D- SEP(((X, Y. Mx) in M and A'M denotes the MCS regarding PD-SEP(X, Y, M)) in M;
Remark. 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 is invariant for different M. If there is no critical variable as condition (1), then for any MAG M consistent to M, AM A'M holds according to Thm. 3. We thus conclude A.M is invariant for different M consistent to M, i.e. different D-SEP(X, Mx) in distinct M consistent to M share the same MCS regarding them.
Def. and Thm. form a graphical characterization that allows us to obtain all possible MCSs in all MAGs consistent to a local find all MCSs in P based on
F
MAG M. We propose Alg. 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 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 to the MCS regarding PD-SEP(X, Y, M) (Line 6). When there 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
Y-
S
Figure 2: An illustration for critical variable F, and critical marks (red).

---

be the ancestor of X or Y in some MAGs but the non non-ancestor in other MAGs, due to the unidentified critical marks. Conditioning on the non-and 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 Cg of the critical variable set C, there could possibly be some MAG M consistent to M where C& S D-SEP(X, Y, Mg and (C' (2)C n DDSEEP(X (X, Y, MMx
0. We
use 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. is shown in Lemma i.e. no matter what the true MAG M is, the MCS regarding D-SEP(X, X, Y, Mx) in M
could be returned as long as D-SEP(X, Y, Mx) n De(X,M) = 0.
Lemma 4. Let P be a PMAG of MAG M. X E An(Y, and D,SEP(X,Y,Mx)) n De(X,M) = 0, then the MCS regarding ESEP(X,Y,,M) in M and the corresponding local MAG are contained in the output of Algorithm 1.
3.4 Learning marks and purity matrix by interventional data
In this section we propose how 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 = P(Y).
(2) X has causal effect on Y and it can be identified by GBC, i.e., there exists generalized back-door set D such that P(Y (Y)))(()) = J P()|X,))
(3) has causal effect on Y but GBC fails to identify it.
For situation (1), is trivial to learn the marks by the interventional data according to Prop. 5.
Proposition 5. If P(Y (d) = 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 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. 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 (M3,MCS') MCS') by Alg. 1, where M is a local MAG and MCS' is the corresponding MCS. Let Par. (Y [Y|oo(X= = =)) and P(Y = x)) denote the estimated causal effect in each M by MCS' and that under real intervention respectively. Disc(P: Q) is the distribution discrepancy between and Q. If there are m intervention samples ((do(X- = 21), Y1). ......... (do(X- xx.), Y.), Y.)...,, "do))")'' = Im), Ym)). we take MCS* by
m Disc (PMCss (Y xx)), P(Y|do(X = s.)1)
MCS arg min
Σ
(3)
MCS/
Any distance metric can be used here. Since the attention is not calculation, we take the expectation difference as the metric for convenience, i.e., MCS arg min 2,T=||BBsss (Y]do(X rr))) Yzl- If the distance between the estimated causal effect by MCS* and interventional data 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. Otherwise, if there 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 X in the minimal possible directed paths from X to Y For T E T, ffr VV E T,, it holds either T & Adj(V, V,P P)) or there is a variable S of Adj(V, P) such that there a collider path Xo- T + t and every vertex except S on the path is parent 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
7

---

Algorithm 2 ACIC (ACtive target effect Identification with latent Confounding)
input: PAG P by FCI algorithm;
1: Initialize I [VIV E ((P), V PossAn(Y,P) and P(Ydo(VV) is unidentifiable by Prop. 1 // Record the variables whose causal effects on Y are unidentifiable by Prop.
in P]
2: Initialize 1 // Record the variables whose causal effects are failed to be identified by GBC
3: while Z1 [I2 * do
4: Select a variable X with the maximum number of circles from I (I2 to intervene
5: if P(Y ()) equals to P(Y) then
6:
Update P by Prop.
7:
else
8:
Find all possible MCSs in P by Alg. and select MCS* by Eq. 1
9:
m >>=I L (Y do(X = x²)) - Yg I r then if there only local MAG M with MCS' then
t is a pre-set threshold
11:
Update P to M and label all the edges out of X in the minimal directed paths from to Y Ppure
12:
else there is more than one local MAG Mī. M2. MM
13:
Update P with the common marks in MT, My :. ME. 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 // In this case GBC fails to identify P(Y|do(XT)
16:
else
17:
Update P by Prop. 6 Ia I2 U (X)
18:
19:
end if end if
20:
21: Update Iı by Prop. with the updated PMAG P and the updated purity matrix
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 cleven rules 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 go- b + b, Adj(d), a & Adj(c), and a, d, do not form an unshielded collider, then - c.
Proposition 7. Rule /l 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 Y (Line 1) among them and 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. 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 Y, then X cannot be ancestor of Y in any MAG consistent to P. And it holds that X & PPssAAnY,PP
4 Theoretical Results
In this section, we first prove the identifiability of causal effects Then we provide an analysis about the computation complexity of estimating all possible causal effects of each variable X on Y.
NNoe when we intervene, we have the information of P(Y]do(X x). However, we aim to identify P(Y|dok ({)) when say causal effect identification.
8

---

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 dd(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 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 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 necessary, we set Y as the descendant of all of XI.... .pp Due to space limit, we present a brief analysis here, while a detailed version is provided in Appendix E.2.
Proposition 10. Let M be a complete MAG with + 1 variables X1.... Xp, Y, where the causal order of the variables except Y is completely random and Y at the last. Denote the graph obtained by FCI with observational data by P and intervention variable by Xi. And let M be locul MAG of X; with p 1 k tails and arrowheuds at X,, The computational complexity of finding all possible causal effects P(Y ()) in all the MAGs consistent to M is O(2)). Further, the computational complexity of finding all causal effects P(Y (d))()))) in all the MAGs consistent to P is O(3).
Let S denote the set of variable that has an edge with an arrowhead at X,. Since the graph is complete, for any subset S of S, we could construct an MAG M based on M such that MCS in M is Sj, which detailed in Appendix E.2. Hence there are 2 causal effects of X, 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 X, 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.
local MAG M PAG
Possihle causal effects
20-1
Ours
O(2f) None
O(3P)
Malinsky and Spirtes (2016)
O(3r))
Table 1: Complexity of estimating all effects.
5 Experiments
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 data' 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 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.
*When 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 strate- gies, 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 change under intervention, which idea is ap- plied widely in many active causal discovery meth-
430
#corresty couzci effectt
030
ods [2, 3]. Since in these methods all the variables could be observed under intervention, we allow Do to select which variable X, to observe under interven- tion 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.
730
638
ACKCsimple ACK-gmadd
538
330
230
Intervention times
Figure The number of correctly identified causal effects by different methods.
6 Conclusion
In this paper, we tackle the problem of identifying the causal effect each variable on 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 charac- terization 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 verified theoretically and empirically.
There are two main aspects to improve the method. One is on how completely update 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.
Acknowledgment
This research 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-Ha Hao Tan for helpful discussions. We are also grateful to the reviewers for their valuable comments.
10

---

References
[1] Thomas Verma and Judea Pearl. Equivalence and synthesis of causal models. In Proceedings of the Sixth Annual Conference on Uncertainty in Artificial Intelligence, pages 255-270, 1990.
[2] Yang-Bo He and Zhi Geng. Active learning of causal networks with intervention experiments and optimal designs. Journal of Machine Learning Research, 022523-2542 2008.
[3] Alain Hauser and Peter Bühlmann. Two optimal strategies for active learning of causal models from interventional data. International Journal of Approximate Reasoning, 55(4):926 939, 2014.
[4] Juan Gamella and Christina Heinze-Denll Active invariant causal prediction: Experiment selection through stability. In Advances in Newral Information Processing Systems, 2020.
Alain Hauser and Peter Bühlmann. Characterization and greedy learning of interventional markov equivalence classes of directed acyelic graphs. Journal of Machine Learning Research, 13:2409 2464, 2012.
[6] Amin Jaber, Murat Kocaoglu, Karthikeyan Shanmugam, and Elias Bareinboim. Causal discovery from soft interventions with unknown targets: Characterization and learning. Advances Neural Information Processing Systems, 2020.
[7] Tian-Zuo Wang. Xi-Zhu Wu, Sheng-Jun Huang, and Zhi-Hua Zhou. Cost-effcctively identifying causal effects when only response variable observable. In Proceedings of the 37th International Conference on Machine Learning, pages 10060-10069, 2020.
[8] Peter Spirtes, Clark N Glymour, and Richard Scheines. Causation, prediction, and search. MIT Press, 2000.
[9] Marloes H Maathuis, Markus Kalisch, Peter Bühlmann, ct al. Estimating high- high-dimensional intervention effects from observational data. The Annals of Statistics, 37(6A)3313333 314,, 2009.
[10] Emilija Perkovic, Markus Kalisch, and Marloes H. Maathuis. Interpreting and using cpdags with back- ground knowledge. In Proceedings of the Thirty-Third Conference on Uncertainty in Artificial Intelligence, 2017.
[11] Jiji Zhang. Causal reasoning with ancestral graphs. Journal of Machine Learning Research, 9:1437-1474, 2008.
[12] Marloes H Maathuis, Diego Colombo, al. generalized back-door criterion. The Annals of Statistics, 1363):0060-100 2015.
[13] Jiji Zhang. On the completeness of orientation rules for causal discovery in the presence of latent confounders and selection bias. Artificial Intelligence, 172(16-17):1873 1896, 2008
[14] R Ayesha Ali, Thomas S Richardson, Peter Spirtes, et al. Markov equivalence for ancestral graphs. The Annals of Statistics, 37(5))288082288
2009.
[15] Zhongyi Hu and Robin Evans. Faster algorithms for markov equivalence. In Proceedings the Thirty- Sixth Conference on Uncertainty in Artificial Intelligence, pages 739-749 739-748,,7 2020.
[16] Daniel Malinsky and Peter Spirtes. Estimating causal effects with ancestral graph markov models, In Conference on Probabilistic Graphical Models, pages 299-309, 2016.
[17] Biwei Huang. Kun Zhang, Jiji Zhang, Joseph D. Ramsey, Ruben Sanchez- Romero, Clark Glymour, and Berhhard Schölkopf. Causal discovery from heterogencouu//oonstttiinann data. Journal of Machine Learning Research, 21:89:1 1-89:53, 2020.
[18] Sofia Triantafillou and Gregory Cooper. Learning adjustment sets from observational and limited experi- mental data. In Thirty-Fifih Fifth AAAI Conference on Artificial Intelligence, pages 9940-9948, 2021.
[19] Diego Colombo, Marloes H Maathuis, Markus Kalisch, and Thomas S Richardson. Learning high- dimensional directed acyclic graphs with latent and selection variables. The Annals of Statistics, pages 294-321, 2012.
[20] Christopher Meek. Causal inference and causal explanation with background knowledge. In Proceedings of the 1t Annual Conference on Uncertainty in Artificial Intelligence, pages 403 403-410, 1995.
[21] Markus Kalisch, Martin Mächler, Diego Colombo, Marloes H. Maathuis, and Peter Bühlmann. Causal inference using graphical models with the R package pcalg. Journal of Statistical Software, 47(11)11226, 2012.
[22] Thomas Richardson, Peter Spirtes, et al. Ancestral graph markov models. The Annals of Statistics, 30(4): 962-1030, 2002.
[23] Jiji Zhang. Causal inference and reasoning in causally insufficient systems. PhD thesis, Citeseer, 2006.
[24] Jiji Zhang and Peter Spirtes. A transformational characterization of markov equivalence for directed acyclic graphs with latent variables. CoRR, abs/1207.14199 2012.

---

[25] Murat Kocaoglu, Amin Jaber. Karthikeyan Shanmugam, and Elias Bareinboim. Characterization and learning of causal graphs with latent variables from soft interventions. In Advances in Neural Information Processing Systems, pages 14346-14356, 2019.
[26] Jin Tian and Judea Pearl. A general identification condition for causal effects. In Proceedings of the 18th National Conference Artificial Intelligence and 14th Conference Innovative Applications of Artificial Intelligence, pages 567-573, 2002.
[27] llya Shpitser and Judea Pearl. Identification of joint interventional distributions recursive semi-markovian causal models. In Proceedings of the 21 National Conference on Artificial Intelligence and the 18th 2006.
Innovative Applications of Artificial Intelligence Conference, pages
[28] Judea Pearl. Causality. Cambridge University Press, 2009.
[29] Yonghan Jung, Jin Tian, and Elias Bareinboim. Learning causal effects via weighted empirical risk minimization. In Advances in Neural Information Processing Systems, 2020.
[30] Ilya Shpitser, Tyler J. VanderWeele, and James M. Robins. On the validity of covariate adjustment for estimating causal effects. In Proceedings of the Twenty-Sixth Conference on Uncertainty in Artificial Intelligence, pages 527-536. 2010.
[31] Tyler VanderWeele and Ilya Shpitser. new criterion for confounder selection. Biometrics, 67()): 1406-1413, 2011.
[32] Antti Hyttinen, Frederick Eberhardt, and Matti Järvisalo. Do-calculus when the true graph is unknown. In Proceedings of the Thirty- firrt--First Conference Uncertainty in Artificial Intelligence, pages 195-404, 2015.
[33] Amin Jaher, Jiji Zhang, and Elias Bareinhoim. Causal identification under markov equivalence: Complete- ness results. In Proceedings of the 36th International Conference on Machine Learning, pages 2981-2989, 2019.
[34] Richard Guo and Emilija Perković. Efficient least squares for estimating total effects under lincarity and causal sufficiency, arXiv preprint 2r0i 03481, 2020.
[35] David Maxwell Chickering. Optimal structure identification with greedy search. c, 3:507-554, 2002.
[36] Rui-Che Cai, Jie Qiao, Kun Zhang, Zhen-Jie Zhang, and Zhi-Feng Hao. Causal discovery from discrete data using hidden compact representation. In Advances in Neural Information Processing Systems, pages 2666-26744 2018.
[37] Daniel Bernstein, Basil Saeed, Chandler Squires, and Caroline Uhler. Ordering- based causal structure learning the presence latent variables. In International Conference on Artificial Intelligence and Statistics, pages 6098-4105 PMLR, 2020.
[38] Patrik O. Hoyer, Dominik Janzing, Joris M. Mooij, Jonas Peters, and Bernhard Schölkopf. Nonlinear causal discovery with additive noise models. In Advances in Neural Information Processing Syxtems, pages 689-696, 2008
[39] Jonas Peters. Joris M. Mooij, Dominik Janzing, and Bernhard Schölkopf. Causal discovery with continuous additive noise models. Journal of Machine Learning Research, 15:2009-2053, 2014.
[40] Frederick Eberhardt. Causation and intervention. Unpublished doctoral dissertation, Carnegie Mellon University, page 93, 2007.
[41] Karthikeyan Shanmugam, Murat Kocaoglu, Alexandros G. Dimakis, and Sriram Vishwanath. Learning causal graphs with small interventions. In Advances Neural Information Processing System, pages 3195-3203, 2015.
[42] Yu-Hao Wang. Liam Solus, Karren Yang, and Caroline Uhler. Permutation--aase causal inference algorithms with interventions. In Advances in Neural Information Processing Systems, pages 5824-544444 5833, 2017.
[43] AmirEmad Ghassami, Saber Salehkaleybar, Negar Kiyavash, and Elias Bareinhoim. Budgeted experiment design for causal structure learning. In Proceedings of the 35th International Conference on Machine Learning, pages 1719-1728. 2018.
[44] Jin Tian and Judca Pearl. Causal discovery from changes. In Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, pages 512-521, 2001.
[45] Jonas Peters, Peter Bühlmann, and Nicolai Meinshausen. Causal inference by using invariant prediction: identification and confidence intervals. Journal of the Royal Statistical Society: Series (Statistical Methodology), 78(5):947-1012 2016.
[46] Kun Zhang, Wei Huang, Ji-Ji Zhang, Clark Glymour, and Bernhard Schölkopf. Causal discovery from nonstationaryhheeergeeeouuu data: Skeleton estimation and orientation determination. In Proceedings of the 26th International Joint Conference on Artificial Intelligence, pages 1347-1353, 2017.
[47] Hui Zhao, Zhongguo Zheng, and Baijun Liu. On the markov equivalence of maximal ancestral graphs. Science in China Series A: Mathematics, 48(4):548 (15455548-62,250 2005.
12


Reviews:
[{"review_id": "oFVEC4RlEf", "reviewer": "Reviewer_WArj", "summary": "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. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "As most of us know, the graphical model that best approximates a DAG with latent factors is an Acyclic Mixed Directed Graphs (ADMGs), which preserves not only conditional independence constraints but also dormant conditional independence constraints after one performs fixing operations on the original ADMG. But because the characterization of MEC of an ADMG is still an open problem, most of the current works consider a relaxation of ADMG -- MAG, as in the current submission. Unlike ADMGs, MAGs do not preserve dormant conditional independence constraints; also, the characterization of MEC of MAG has been solved by Richardson and Spirtes (2002).\n\nThis paper seems to be an extension of an earlier work by Wang et al. 2020 ICML, in which Wang et al. also consider only observing the outcome after active interventions, but under causal sufficiency assumptions. This paper, however, considered a more difficult problem, for which unmeasured factors/confounders are allowed. \n\nThe theoretical development is new but it is not easy to evaluate if the intervention scheme considered in this paper is very practically relevant. To me, the most (or in my opinion, the only) meaningful causal discovery setting is in genomics where large-scale intervention data is available to actually test the results, but in genomics, it is rarely the case that we only get to observe $Y$ after the intervention. As a result, I give a score of 7 to this paper.\n\nBesides the general comment, I have more specific comments or questions regarding the submission:\n\n(1) More recently, the research group of Elias Barenboim has also solved the problem of characterizing the so-called interventional MEC of MAGs when one has mixed observational and interventional data. Though the authors decide to take a different route (i.e. local search), it seems to me that it is entirely possible to characterize the MEC of MAGs when interventional data is available but we only get to observe $Y$ in each intervention. Have the authors considered such a problem? If not, is it by any means helpful for settings similar to what the authors are trying to solve?\n\n(2) In practice, decision variables might not be all observables except $Y$. In this setting, if I am only interested in $Y | do (X_{i})$ for $i$ from a subset of $[p]$, would there be a more efficient algorithm than simply applying ACIC but just focusing on this subset?\n\n(3) Intervening decisions variables one by one also seems restrictive. It is quite reasonable to consider cases where multiple variables are intervened on. If one can intervene in more than one variable, what are the technical challenges of developing theory?\n\n(4) A discussion on the potential generalization of this work to ADMG will be helpful to reach a more general audience of causal inference.\n\nMinor points:\n(1) Line 143: I would prefer to add its complete name when the authors first mention MCS.\n\n(2) Line 115: \"(identifying failing of GBC is counted).\" Does it mean that \"failing to identify $Y | do (X)$ by GBC\"?\n\n(3) After reading the paper, my understanding is that ACIC is sound but not necessarily complete. I would suggest the authors discuss this issue at the end of the paper and mention it in the introduction.\n\n(4) The paragraph below Prop 1 seems hard to understand. In the second unidentifiable case, do you mean that a generalized backdoor set may not exist?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This work is purely theoretical so no immediate potential negative societal impact.", "review_text": "", "extra_scores": {"ethical_concerns": "No.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5"}, "extra_text": {}}, {"review_id": "hVG27cZrjAc", "reviewer": "Reviewer_sQJg", "summary": "This paper extends a previous work where a method was presented for learning causal effects when some interverventions can be conducted, but such that only the distribution of the response variable is observable after the intervention. This paper extends the mentioned previous work by allowing for possible latent confounders, which requires listing possible alternative structures in an active manner.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "PROS: \n- Extending a previously published idea to a situation where there are latent confounders. \n- The derivations seem correct.\n\nCONS:\n- The motivation for the paper is not very well elaborated. The paper mentions an application in healthcare, where patients are not fully checked after treatment and only their illness is observable by doctors, but this seems overly simplistic, especially because there is no corresponding real data experiment.\n- The presentation is a bit hasty. First of all, the main text is not self-standing, but it's necessary to read at least ref [8] and the supplementary to grasp the main idea. Also, some abbreviations are used in the text without defining them first (at least ACI, MCS). Obviously the page limitation restricts what can be put to the main text, but I think it would improve the paper if the main text focused more on motivation, key points, and intuition.\n- Novelty compared to ref [8] seems a bit limited.\n- Based on experiments the difference of the presented active learning approach to a \"random\" approach seems small (Fig. 3). Also, the experiments are somewhat limited in general.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There is little on limitations and no discussion on negative impacts. I don't think there are serious ethical impacts, but more discussion could be provided on the limitations.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "ALBvC6unOal", "reviewer": "Reviewer_rzAn", "summary": "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 .  ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper tackles an interesting question and the proposed method has novel elements. However, details of the paper are not easy to follow. At the moment I am puzzled by the following aspects of the work:\n\n1. The paper proposes that if the effect of a variable X on the response variable cannot be identified by the generalized backdoor criterion (GBC) even given the true MAG with all the purity information, \"Fail\" will be returned for this effect. But why not intervene on X in such a situation to directly estimate the effect? In fact, in Section 3.4, the \"Fail\" situation is supposed to be \"detected\" by intervening on X. Then why not use the interventional data there to estimate the effect in question instead of returning \"Fail\"?  \n\n2. It is also unclear to me how those MAGs that do not license identification by GBC can ever be ruled out in the proposed method. For such a MAG, any effect estimated from the interventional data seems to be consistent with it, as the MAG does not entail what the effect is by GBC. \n\n3. The definition of local MAG is given on p. 5 relative to one variable, but Algorithm 1 seems to use local MAGs in a more general sense, which is not clearly defined (as far as I can see).\n\n4. The statement of Theorem 9 is a little curious on two counts. First, as I indicated in point 1 above, the locution \"the causal effect of X on Y is identifiable by GBC with the interventional data of Y under intervention on X\" sounds odd because the causal effect of X on Y is identifiable with the interventional data of Y under intervention on X, and it is unclear why \"identifiable by GBC\" is so important. Second, the theorem sounds like a simple tautology: the causal effect is identifiable by GBC if GBC does not fail to identify it.   \n\nMinor comments:\n\ni. In Proposition 1, since G is supposed to be an ancestral graph (as opposed to a partial ancestral graph), should \"PossDe\" be simply \"De\"?\n\nii. In Definition 3, the terminology \"deterministic marks\" is misleading. \"Definite marks\" or  \"determinate marks\" sounds better.\n\niii. Also in Definition 3, a local MAG is typically still a *partial graph*, so not an ancestral graph, right?\n\niv. In Definition 4, \"descendant\" or \"possible descendant\"?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Adequately addressed.", "review_text": "", "extra_scores": {"ethical_concerns": "  ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "0D1PEIEeNyP", "reviewer": "Reviewer_ot5a", "summary": "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)).", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The setting considered in the paper combines elements from structural learning and data-driven causal inference. As far as I know, the task of identifying all effects while learning the structure posed in the paper is novel. In particular, in the presence of latent confounding and having observational data plus interventional data where only the outcome is observed as input. Relevant related work seems to be properly cited.\n\nThe claims made in the paper seem well supported both by theoretical analysis and experimentation. While the method relies on the GBC, I wonder why the Generalized Adjustment Criterion (Perković et al. 2015) is not a better choice since it is known to be sufficient and complete for adjustment in the context of DAGs, MAGs, CPDAGs, and PAGs. The algorithms are described with enough detail and their complexity has been analyzed.\n\nI find the paper well-written and clear, with a few exceptions. In particular, I find the wording and subsequent explanation of Theorem 9 confusing. What does it mean for a causal effect to be \"identifiable by interventions\"? \nThe experimental section is clear and provides a compelling comparison with other methods.\n\nThe results presented in the paper address a causal inference setting that could arise in many practical scenarios. Allowing for only the response variable to be observed under intervention provides flexibility compared to other methods that require observation of all non-intervened variables. The method also seems to improve, compared to previous work, in terms of computation complexity and the number of required interventions.\n\nOther comments:\n- Consider adding a title to Definition 3.\n- Line 180: \"GBC dose not fail\"\n- Line 347: \"of first part\" (missing article)", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I am satisfied with the discussion of the limitations provided in the paper.\nI can't foresee any societal impact of the work that needs to be addressed at the moment.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper explores a causal setting where we are interested in understanding the impact of possible interventions on a single response variable, using observational data (which might suffer from latent confounding) and limited interventional data. The limit on the interventional data is that we only observe the response variable, and nothing else. This work extends several other papers that have dealt with similar setting, with the important distinction of allowing latent (i.e. hidden) confounding in the observational data. 
The paper is a theory paper, and the reviewers agreed that it contains a novel contribution and that it is technically correct. 

The main concern of the reviewers was about the applicability of the specific scenario the authors propose; however, the overall decision is that the real theoretical contribution is important enough. Furthermore, I believe it is often difficult to know in advance which learning scenarios or which techniques will end up useful. Since the work is both rigorous and novel, the recommendation is to accept the paper. 

The reviewers made some thoughtful suggestions in their reviews and the discussion period, and I encourage the authors to incorporate some of the conclusions in their revised version. 
Decision: Accept (Poster)