Learning Nonparametric Latent Causal Graphs with Unknown Interventions
Authors: Yibo Jiang
Bryon Aragam
Venue: NeurIPS 2023 poster (2023)
Keywords: graphical models
directed acyclic graphs
causality
identifiability
causal representation learning
unknown interventions
TL;DR: Identifiability theory for general latent causal graphs without making linear, gaussian, or other parametric assumptions

Abstract: We establish conditions under which latent causal graphs are nonparametrically identifiable and can be reconstructed from unknown interventions in the latent space. Our primary focus is the identification of the latent structure in measurement models without parametric assumptions such as linearity or Gaussianity. Moreover, we do not assume the number of hidden variables is known, and we show that at most one unknown intervention per hidden variable is needed. This extends a recent line of work on learning causal representations from observations and interventions. The proofs are constructive and introduce two new graphical concepts---_imaginary subsets_ and _isolated edges_---that may be useful in their own right. As a matter of independent interest, the proofs also involve a novel characterization of the limits of edge orientations within the equivalence class of DAGs induced by _unknown_ interventions. These are the first results to characterize the conditions under which causal representations are identifiable without making any parametric assumptions in a general setting with unknown interventions and without faithfulness.

Learning nonparametric latent causal graphs with unknown interventions
Yibo Jiang University of Chicago yi riboj@uchicago.o edu
Bryon Aragam University of Chicago bryon@chicagoboooth. edu
Abstract
We establish conditions under which latent causal graphs are nonparametrically identifiable and can be reconstructed from unknown interventions in the latent space. Our primary focus is the identification of the latent structure in measurement models without parametric assumptions such as linearity Gaussianity. Moreover, we do not assume the number of hidden variables is known, and we show that at most one unknown intervention per hidden variable is needed. This extends recent line of work on learning causal representations from observations and interventions. The proof' are constructive and introduce two new graphical concepts concepts-imaginnay imaginary subsets and isolated edges that may be useful in their own right. As matter of independent interest, the proofs also involve novel characterization of edge orientations within the equivalence class of DAGs induced by unknown interventions. These are the first results to characterize the conditions under which causal representations identifiable without making any parametric assumptions in a general setting with unknown interventions and without faithfulness.
the limits
Introduction
Among the many challenges in modern machine learning and artificial intelligence, learning and reasoning about causes and effects from data remains a key challenge. practice, one of the hurdles that must be overcome that we often do have direct access measurements on causally meaningful variables, and instead can only measure primitive, indirect measurements such as pixel intensities in vision, gene expression values in biology, letters and words in language, or frequency signals in audio. In these applications, it is necessary to first learn representations with meaningful causal signals, problem known as causal representation learning [52]. Besides learning representations or features of data, we are also interested in understanding what happens when we intervene on these learned features, which is essential for causal reasoning. As such, broadly speaking, causal representation learning can be broken down into two steps: (1) learning high-level features from raw data and (2) learning causal relations between these features.
Given the proliferation of recent work of identifying latent representations in the observational setting [2, 13, 23, 26, 29, 30, 32, 38, 40, 43-45, 51, 55, 63, 66, 70, 71, 73], in this paper we consider the case of interventions. Data arising from interventions opens the door for a causal interpretation of the learned representations, which often described by directed acyclic graph (DAG). This setting raises new challenges, namely that the interventions are both latent and unknown. Moreover, in practical applications, flexible deep neural networks are used learn nonlinear representations of the data, which necessitates the consideration of nonparametrie assumptions. Motivated by these challenges, we seek to answer the following important question:
Given a list of latent, unknown interventions, when is it possible to identify the underlying (latent) causal relationships without making parametric assumptions?
37th Conference on Neural Information Processing Systems (NeurIPS 2023).

---

H1
H2
H4
H3
GB
X2
X1
X5
X6
X4
X3
Figure I: Illustration of the main concepts used in this paper. G = Gn U GF is measurement model with bipartite DAG Gy (blue edges) and latent DAG Gy (red edges), (Xs; X6) } is an imaginary subset, (X1,Xe) } is replaceable subset while {X1, X2, Xs) is non-replaceable subset, and H₂ H, is an isolated edge. In fact, {Xs. X6) is non-replaceable imaginary subset. This also not a maximal measurement model although it still illustrates the main concepts. For completeness, the undirected dependency graphs under different interventional targets are provided in Figure
In particular, we focus on the problem of learning structure 56], and leave the problem of learning the representations themselves to existing work, since one can then use deep latent variable models to infer the latent distributions from the latent structure, which is well-studied [e.g. 20, 28, 35, 46, 64, 65]. We adopt the measurement model [36, 43, 54] where there are no direct causal edges between observed covariates. This model has been used extensively to model causal representations [e.g. 1, 25, 32, 57, 61, 66-68]. Surprisingly, we show that it is possible to learn latent causal structure without learning the distributions latent representations, unlike [1, 32, 57, 61]. Furthermore, unlike [1, 57, 61]. we do not impose any parametric assumptions: We allow for general noisy, nonlinear transformations between latents and observed as well as arbitrary nonlinear relationships between the latents, which makes the problem significantly harder. Part of our motivation is to better understand the minimal assumptions for learning causal structure from unknown interventions.
1.1 Contributions
Our main contribution is set of nonparametric assumptions under which the entire latent causal graph is identifiable given unknown interventions in the latent space, up to edges that show cannot be oriented without additional assumptions (in a similar sense to reversible edges in a Markov equivalence class). To the best of our knowledge, structure identification in nonparametric setting given unknown and latent interventions has not been considered in-depth in the literature.
More specifically, we make the following contributions:
We introduce two new graphical concepts concepts-imaginnrry imaginary subsets (Definition 3.2) and isolated edges (Definition 3.3)-that key to identifiability and orientability of edges in the true causal graph. These are illustrated in Figure and discussed in detail in Sections 4-5.
2. We combine these concepts with nonparametric, graphical assumptions show that the causal graph is identifiable up isolated edges (Theorem 3.4).
3. We show the limitation of edge orientations using CI relations alone under unknown inter- ventions even when there are no latent variables (Theorem 5.3).
The implications of these results are twofold: 1) It is possible to learn the entire DAG without making parametric assumptions, albeit at the cost of nontrivial graphical assumptions, and 2) we wish to relax these graphical conditions, alternative assumptions are needed. That is, in Appendix C (Examples 3-6), we prove that our assumptions are nearly necessary in the sense that if any individual assumption is relaxed, then identifiability fails. Figure illustrates graphical conditions in simple example that will be referred back to throughout the paper. Finally, we verify our theoretical results in simulation study.
1.2 Related work
Learning the Markov equivalence class of causal graphs from observational distributions is well- researched area [56]. Although our focus is on learning measurement models with interventions, we note that the observational case has been extensively studied [25, 32, 36, 43, 54, 66-68].

---

Intervention design. In the classical setting of known interventions on observables, Eberhardt et al. [16] show that for causal graphs with more than n >> variables, sufficient, and in the worst case, they are also necessary. Kocaoglu et al. [34] consider intervention design in the presence of latents, and propose efficient algorithms. Hauser and Bühlmann [24] derive a notion of interventional equivalence for hard/structural interventions, while Tian and Pearl [60] and
single node interventions are
Yang et al. [69] do the same for soft/parametric interventions.
Unknown interventions. There has been growing literature on learning under unknown inter- ventions recently as well. A recent line of work studies soft interventions where the unknown interventional targets are observed [7, 15, 19, 21, 27, 33, 49, 58). In particular, Jaber et al. [27] consider the case where the causal graph consists of measured and unmeasured latent variables, but
the intervention targets, though unknown, are from measured variables. Squires et al. [58] assume no hidden variables and use direct I-faithfulness to identify the unknown intervention targets. Perry et al. [49] utilize independent causal mechanisms as a key assumption and measure the number of mechanism changes to identify the true DAG, Castelletti and Peluso [7], Eaton and Murphy [15], and Faria et al. [19] propose Bayesian methods to learn DAGs under unknown interventions.
Latent interventions. A very different setting arises when the interventions are both unknown and latent. Perhaps the earliest approach to this general setting is causal feature learning, introduced in [8, 9J. More closely related to our paper are Liu et [42], Squires al. [57], and Varici et al. [61], which consider unknown interventions on latent variables under parametric assumptions. Squires et al. [57] assume hard interventions on latent variables under a linear model. Varici al. [61] allow nonlinearities in the latent space with linear map between hidden and observed, using the score function for identification. Liu et al. [42] assume the existence of an auxiliary observed variable u that modulates the variant weights among latent causal variables where the setup is similar to that of iVAE [31]. Ahuja et al. [1] assume a polynomial decoder and the intervention target on the latent is known. Brehmer et al. [4] consider the weakly supervised setting with paired pre- and post-intervention samples, where the interventions are random and unknown. Lippe et al. [41], J. on the other hand, work with latent interventions on temporal sequences.
While our work was under review, we were made aware of several concurrent works that study the same problem under different assumptions [5, 37, 72].
2 Preliminaries
Our basic setup a standard graphical model with both observed and latent variables. Appendix contains comprehensive overview of all the necessary formal graphical concepts; we briefly outline the basics here. Let G = (V, E)) be a directed acyclic graph (DAG) with V (X, H)) where X denotes the observed part and H/ denotes the hidden or latent part. Define n := |X] and m := = For a given node v, we use standard notation such as pa(v), ch(v), (t). an(v) and de(v) for parents, children, ancestors, and descendants respectively. Given subset V C V. VV(
Usev pa(c), given two subsets A, B C V, p (A) = pa(A) n B and given a subgraph G' C G. pag- (V") = pa ("')nn nG'. Similar notation can be defined for children, ancestors, and descendants. For disjoint subsets (ABB
A, B. C S V, define d-sepo (AB | C) to mean that A, B are d-separated by C in the graph G. A DAG encodes set of d-separation relations, defined by
(G. = (A, B, C² d-sepa (C) for disjoint subsets A, B,C CCCVV
where V' C V. For simplicity, we write T(G)- = (G') Recall that two DAGs G1 and G2 are Markov equivalent if T(1) = TG22). The Markov equivalence relations define set of equivalence classes of DAGS called the Markov equivalence class (MEC).
Every distribution P on V defines a collection of conditional independence (CI) relations:
Tv.(P) = (A,, A 1L B C in P for disjoint subsets A, B, B.C
where V S V, and as before T(P) = (P). We denote the marginal V by Pv:. Remark 2.1. Throughout the paper, unconditional (i.e. marginal) independence and d-separation will play a prominent role. Thus, unless otherwise stated, when we say A and B are dependent or d'connected, or that there an active path between A and B, without explicit mention of the separating set C, we consider it implies that C' 0.
3

---

X1
X2
X1
X2
X3
X4
X3
X4
X6
X
X6
X
(a) When the intervention target is 0, {H1 or [22), the UDG contains maximal cliques: (1,2, 3, 5, 6), (1,2,4).
(b) When the intervention target is (Ha). the UDG contains maximal cliques:
21,2,5, (1, (1, (3,
X1
X2
X3
X4
X5
X6
(c) When the intervention target is {Ha}- the UDG contains maximal cliques: (1,2,5) (1, 4), (3,,,,6 (3,5,6).
Figure 2: UDG under different intervention targets for Figure 1.
Interventions. For background, Eberhardt and Scheines [17] provides a detailed account of the different types of interventions causal systems. In this paper, we consider hard (or structural) interventions on a single node. Let / C V be set of intervention targets. The intervention graph of G is the DAG G (V, E where E == {(a, (a) b) E E, b & I}. Similarly, let p()) be the interventional distribution. We further restrict intervention targets be latent variables in this paper (I C H), which necessitates considering unknown intervention targets. Thus, we have access to family of intervention targets (fo...., [x} with [4] s 1. By convention, we let 0 so that GTo) G and ((a)
the observational distribution.
subtle but important point that different interventional distributions may be the same, i.e. p( p((") but 1 /f I'. This implies, particular, that the number of latent variables unknown (see Remark C.I).
Example 1. Known and unknown interventions have different implications in terms of edge orien- tations. To see this, consider the unoriented edge between the intervention target is {X1} and we observe that X and X₂ become independent under this intervention, then know X1 X2. However, we do not know the intervention target is X₃ and we observe the same independence between X1 and X2, then it is possible the true DAG is X1 + X2 with intervention target X2 the true DAG X1 X2 and the intervention target X2.
variables Xi and X2. If know
Measurement models. Our main results apply so-called measurement models [36, 54] in which every observed variable only has incoming edges and no outgoing edges (i.e. ch(X) 0). This assumption cleanly encapsulates the problem of reconstructing latent causal structure and captures relevant applications where the relationships between raw observations are less relevant than causal features and is standard model adopted in prior work [e.g. 25, 43, 66-68].
For any measurement model, G decomposes as the union of two subgraphs G GB U Ge where GB is directed, bipartite graph pointing from / to X, and Gy is DAG over the latent variables H. See Figure
Following Markham and Grosse-Wentrup Wentrup [43], for any distribution P over V. define the undirected dependency graph (UDG), denoted D(P), to be the undirected graph over X in which there an edge between X; and X; if and only if they are marginally dependent (i.e. given the empty set, ef. Remark 2)... Clearly, D(P) easily constructed from Tx (P) by checking if each pair of observed variables is marginally independent not.

---

3
Main result
We can now state our goal formally as follows:
Given a set of interventional distributions ( P
Hie, can we recover G3 and Gy ?
Here, Mezz is a set and not a tuple: If two different interventions lead to the same interventional distributions, then we only observe one copy of p(!) in this set. As result, do not know the number of latent variables (see Remark C.I); we show how this is learned in the proof. Of course, in practice, only have sample access to p()) In this paper, focus identifiability and leave estimation from finite samples to future work.
Remark 3.1. Learning from the tuple (P&)) )rez
(rex) is easier than learning from the set ( rez, since problem by removing duplicates. Thus, there is no can trivially reduce the tuple problem loss of generality in our setting.
3.1 Assumptions
To solve this problem, we make the following assumptions: Assumption 1 (Graphical conditions). The DAG G satisfies the following conditions for every I I and pair of hidden variables H; * Hy:
(a) p()) is Markov with respect to G()), i.c T(G CT(PD))
(b) X, T Xy = d-sepaco( ((, 1)), i.c. marginal independence in X implies d deppprrtio
(c) d-sepaon (HH, } 0) there exists X; E (14) and X, E chx(l1,) such that d-sepaon (XX,)X,) 0).
Assumption 2 (Complete family of targets). I = {0, (HI)...... {mm}}.
Intuitively, the graphical conditions in Assumption ensure that hidden variables and their depen- dencies have detectable signatures in observed distributions. Of course, Assumption ((a) is just the usual Markov assumption that relates the graph to the distribution P. Assumption 1(b) requires that marginal dependencies of observed variables reflected in the underlying graph, and is much weaker than similar conditions in the graphical modeling literature. Assumption ensures that the effect of each hidden variable is measured. Furthermore, with the exception of Assumption Icc), which arises from our fully nonparametric setup, each of these assumptions has appeared previously in the literature [1, 14, 18, 32, 43, 48, 53, 59, 61]. See also Remark 4.3. A detailed discussion of these assumptions is deferred to Appendix C. In particular, with the exception of the Markov property Assumption (a)), we give counterexamples to show that when any one of these assumptions is violated (but the rest continue to hold), there are two graphs that have the same set of observed distributions under different interventions.
worth noting that the well-known subset condition [18, 32, 48] is implied by Assumption and Assumption 2 (Lemma C.1 in Appendix C.4). However, this arises from the fact that Assumption 2 is needed for exact recovery. If the main objective is instead partial recovery and Assumption 2 is relaxed, then needs to additionally assume the subset condition. See Appendix C.4 for details.
Remark 3.2.
Remark 3.3. Assumption 1 and Assumption 2 also generalize the well-known pure child condition, which is widely used and has applications in NI.P and topic modeling [e.g. 3, 6, 45, 66]; see also Section 4.3. It is easy to see that the existence of pure children for each latent implies Assumption 1(c).
3.2 Maximal measurement model
Under Assumptions 1-2, two different measurement models can still induce exactly the same inter- ventional distributions of observed variables. Even without interventions, there may be ambiguities, an observation that dates back to [50] the definition of a maximal ancestral graph and was more recently used in [32]. Example 6 in Appendix C.5 gives concrete example where two measurement
5

---

models share the same set of observed distributions under interventions. Fortunately, the ambiguity limited: There is always a maximal measurement model that encodes many non-redundant dependencies as possible, as defined below:!
Definition 3.1 (Maximal measurement model). measurement model is called maximal if satisfies Assumption and the following two conditions:
(a) pa(X;) * 0 for all E [n]]
(b) There is no DAG G' = (V, E') also satisfying Assumption such that, {Tx (T (Tx (Tx(G"))))EE and E Ç F".
Our definition of maximality here mirrors the concept maximality introduced [50], extended to include interventions. Throughout the paper, if not mentioned explicitly, the measurement model is considered be maximal. More discussion on maximality is provided in Appendix C.5.
3.3 Imaginary subsets and isolated edges
To identify G, we will break the problem into two phases: First, we learn the bipartite graph GB. and then this to learn the latent DAG Gy. Each of these phases introduces new graphical concept, which are defined here.
3.3.1 Imaginary subsets
Latent variables induce cliques in the UDG D(P())) which provide way to identify the existence of a latent [43]. Unfortunately, the identification of GB is complicated by imaginary subsets: Intuitively, imaginary subsets ambiguous subsets of observed variables that may not be the children of single latent. Given D ( let ! be the set of maximal cliques in D D(Pl)). We also let Ω Urer? Definition 3.2 (Imaginary subsets). A subset X' C X is valid subset if for all T I, there exists maximal clique C' s such that X' C C. A valid subset maximal if there is no other valid subset X" such that X Ç X" S C for every maximal clique C Ω containing X'. A maximal valid subset X' S X is imaginary if there is no hidden variable H, such that X' C chx (H.).
Imaginary subsets (more precisely, the lack thereof) crucial to the identification of Gg, although at first glance they may seem a bit abstract. Indeed, handling imaginary subsets turns out to a nontrivial issue, defer further discussion of this concept to Section 4, where several examples and intuitions are given.
3.3.2 Isolated edges
Once we identify Gg, we'd like to identify Gy. Unfortunately, Example gave example where unknown interventions are incapable of orienting an edge using CI information only. This type of edge be identified more broadly follows:
Definition 3.3 (Isolated edge). We say an edge + is isolated if æ does not have any parent (pa(z) 0) and y only has as its parent (pa(y) {z)))
The importance of isolated edges is that these are precisely the edges that cannot be oriented using CI information only (see Section 5.2).
3.4 Identifiability of causal graph
We can now state the main result of this paper:
Theorem 3.4. Let G be maximal measurement model satisfying Assumption 1. Then, given complete family of interventions (Assumption 2). the following statements are true:
(a) If there are no imaginary subsets (Definition 3.2), then G is identifiable from (p(I) up to isolated edges (Definition 3.3) in GHi
Here, non non-redunde redurdann means that the edge encodes genuine dependence. In other words, adding any more edges would change the underlying model.

---

(b) Isolated edges in Gμ cannot be oriented using CI information only.
In particular, the unknown number of latents m also identified.
In other words, G can be maximally identified in the sense that any edge in the latent space that isn't oriented cannot be oriented from the given list of interventions using CI information only: Additional assumptions are needed (e.g, conditional invariances and direct I-faithfulness as in [58].
We devote significant effort in the sequel to interpreting and understanding the assumption of no imaginary subsets, which turns out to be subtle and complicated. Thus, in Section 4, we provide several additional sufficient conditions well examples of imaginary subsets help build intuition for this condition.
The proof of this result is broken down into two main steps:
Identifying the bipartite graph Gg (See Section 4);
2. Identifying the skeleton of the latent DAG Gμ and orienting the edges Gy (See Section 5);
Sections 4-5 outline the basic ideas behind these constructions. As the ideas are independently interesting and may be more broadly useful beyond just proving Theorem 3.4, we treat these independently.
4 Imaginary subsets and the bipartite graph
Theorem 3.4 indicates that as long as there are no imaginary subsets, GB can be identified. In this section, we show how identifiability of GB is related to the absence of imaginary subsets (Definition 3.2), and provide several different conditions for this to hold. Throughout this section, we assume as in Theorem 3.4 that G = GB U Gи is maximal measurement model satisfying Assumption I, and that Assumption 2 also holds.
4.1 Identifying GB with no imaginary subsets
The following proposition explains why maximal valid subsets (Definition 3.2) are useful: Proposition 4.1. For any hidden variable HG, ch a maximal valid subset.
Proposition 4.1 suggests that we assign a latent variable to each maximal valid subset. However, not every maximal valid subset corresponds to single latent variable: For example, Figure 1, (Xs, X6) is maximal valid subset that does not correspond to any hidden variable, and hence is an imaginary subset. Unfortunately, these examples are not pathological; this turns out to be endemic and must be resolved carefully.
The first issue that maximal valid subset can be contained in another maximal valid subset. An example is {X1,X,) C {X,, X2, Xs} in Figure 1 (see also Example 7 in Appendix D). This typically happens when two such subsets appear in different cliques, which does not violate our definition of maximal valid subsets:
Definition 4.2 (Replaceable subset), A maximal valid subset X' C X is replaceable if there exists another maximal valid subset X such that X' X"
An example of a replaceable subset is in Figure 1. The advantage of replaceable subsets that they can be identified and ignored. In particular, any replaceable imaginary subset is non-issue. Thus, we have the following important result, which is proved in Appendix D.I:
Theorem 4.3. If there are no non-replaee imaginary subsets, then subset X a non- replaceable maximal valid subset if and only if there exists hidden variable H; such that (H,) X'. particular, it follows that Gn is identifiabl..
Since one can check if X' is replaceable, one might hope that simply eliminating replaceable subsets fixes the problem. Unfortunately, this is not enough: The devil non-replaceuble imaginury subsets: i.e. imaginary subsets that cannot be identified from the data. Moreover, non-replaceable imaginary subsets are genuine phenomenon (( (xs, Xa3 in Figure 1). Thus, as stated, Theorem 4.3 has two drawbacks:
7

---

1. Checking if non renlaceeee imaginary subsets exist and getting rid of them is not easy; and
2. Even when there are imaginary subsets, GB may still identifiable.
Given the difficulties with non-replaceable imaginary subsets, we will provide two sufficient condi- tions to guarantee there are no imaginary subsets (Section 4.2) and also show how one can identify GB even when there are imaginary subsets (Section 4.3).
4.2 Sufficient conditions for no imaginary subsets
In this section, we provide two additional sufficient conditions to guarantee there are no imaginary subsets: The frst--singl source node-is intuitive and interpretable, but cannot always be checked. The second-aa no fractured subsets- is less intuitive but can be explicitly checked.
Single latent source. A latent source is any latent variable such that pa(H.) H.)) V. We can show that imaginary subsets do not exist if there is only one latent source. This still allows for arbitrarily many hidden variables m |H| > (i.e. the descendants of the latent source GT)).
Theorem 4.4. Under Assumptions 1-2, if Gи has one latent source, there are imaginary subsets.
Therefore, with only one latent source node, we can recover the bipartite graph by Theorem 4.3.
Fractured subset condition. necessary condition for an imaginary subset is that the subset is fractured. The definition is somewhat complicated, but worth it since fractured subsets can be identified and checked practice:
Definition 4.5 (Fractured subset). Given a collection of maximal valid subsets S, clique C is called shattered by S if there exists a subset S' S S such that US' = C. A collection of maximal valid subsets {Si J is complete if for every intervention target / E I, all shattered cliques in ((P()) form an edge cover of D ((P).. ). A maximal valid subset X' C X is fractured if there exists a complete collection {S.} such that S; g X' for all S:.
Intuitively, fractured subset provides redundant information every connection between nodes in the fractured subset can be explained by other maximal valid subsets. The aforementioned necessity is shown by the following lemma:
Lemma 4.6. If a subset X' C X is imaginary, then X' is also fractured.
Therefore, we have the following identifiability corollary:
Corollary 4.7. Under Assumptions 1-2 and if there are no fractured subsets, then GB is identifiable. Furthermore, the absence of fractured subsets can be checked and verified, and if fails, a certificate provided.
Remark 4.1. Technically, we only need the condition that there are no non-replaceable fractured subsets.
Remark 4.2. One might suggest getting rid of all fractured subsets, however, even a non non- -oaainagiy subset can be a fractured subset (Example 9 in Appendix D). The no fractured subset condition naviely captures such ambiguities of imaginary subsets, but overkill. In fact, it is still possible to have identifiability with fractured subsets under different assumptions (Theorem 4.4, Theorem 4.8),
4.3 Identifying Gg when there are imaginary subsets
Finally, we show that under the well-known pure child assumption, G3 can be identified when there are imaginary subsets. The pure child assumption has been made in many existing works [e.g. 3, 6, 45, 66], typically along with additional parametric assumptions.
Assumption 3 (Pure child). For every H, E H, there exists at least one X; E X with pa(X,) (H,). f.e X, only has parent and that parent is H;-
Remark 4.3. Assumption I(c) is a much weaker assumption than Assumption 3. In particular, if measurement model satisfies Assumption 3, it also satisfies Assumption 1(c).
Theorem 4.8. Under Assumptions 1-3, the complete collection (cf. Definition 4.5) with the smallest cardinality is exactly (1 and thus GB can be identified.
Remark 4.4. Under Assumption 3, there still could be imaginary subsets (Example 11 in Appendix D).

---

5 Identifying the latent DAG
Once we have learned the bipartite graph Gg, the next step is to learn the DAG GH over the latent variables H. Learning the skeleton of Gy turns out to be straightforward: Assumption 1(b-c) suggest that two hidden variables H; and Hj are d-separated if and only c (H,) and chx (H₂) are in different cliques (Lemma E.2). Therefore, the idea is use unconditional d-separations of latent variables under interventions for identification which is harder than having access to all conditional d-separations in the fully observational case (see Appendix E for details).
Remark 5.1. In fact, we do not have access to full conditional d-separation statements of latents because observed variables are descendants of latent nodes.
The more interesting question how to orient the edges with unknown interventions. Unlike known interventions, edge orientation might not always be possible even when there are latent variables as shown in Example I. At the same time, it is sometimes possible as demonstrated by Example 13 in Appendix F. This raises the question of which edges provably cannot be oriented under our assumptions: It turns out these are precisely the isolated edges (Definition 3.3).
Theorem 5.1. Let G be a maximal measurement model satisfying Assumption and assume we are given complete family of interventions (Assumption 2) as well as the bipartite DAG Gg. Then the true latent DAG Gy is identifiable up to isolated edges. Moreover, isolated edges cannot be oriented without making additional assumptions.
Thus, as long as we identify GB (cf. Section 4), we can identify Gи up to isolated edges.
Remark 5.2. The proof of Theorem 5.1 in Appendix G provides a constructive algorithm. Pseudocode for the overall approach can be found in Algorithm 2 in Appendix G.
In fact, the non-orientability of isolated edges is not restricted to latent edges even the measurement model; this fact applies to general, fully (or partially) observed DAGs.
5.1 Isolated equivalence
We now introduce an equivalence relation on DAGs that refines the notion of Markov equivalence to account for the extra information conveyed by unknown interventions. Unlike known interventions, which suffice to identify the entire DAG, Example shows that unknown interventions carry strictly less information vs. known interventions. These definitions are purely graphical and can be studied in their own right.
For this result, do not need the measurement model assumptions nor Assumption 1-2. So, for now, consider the case of an arbitrary, fully observed DAG (i.e. = 0). By the transformational properties of MEC [12], we know that two Markov equivalent DAGs can be transformed into one another by sequence of covered edge reversals (Definition B.3). Similarly, let's define the following:
Definition 5.2. (Isolated equivalence class) Two DAGs G1 and G2 are isolated equivalent, denoted G g G2 if there exists sequence of isolated edge reversals to transform one into another.
An example of two isolated-equivaleett DAGs can be obtained from Figure I: Since the latent edge H2 + H4 is isolated, reversing it yields DAG that is isolated equivalent to G.
Remark 5.3. Despite what the name might suggest, an isolated edge X + Y does not mean that X and Y are disconnected from all other nodes. In fact, X and Y can still have outgoing edges (Definition 3.3) and X + Y is not just an isolated connected component. Therefore, the IEC is not just union of disjoint edges.
Remark 5.4. Since an isolated edge is covered by definition, Gi and G2 are Markov equivalent they are isolated equivalent. It easy to check that isolated equivalence is an equivalence relation. Therefore, the isolated equivalence class (IEC) is a finer partition of the Markov equivalence class (MEC). An IEC can and often will be a singleton (i.e. DAG that is not isolated equivalent to any other DAG in the MEC).
Remark 5.5. This also different from the interventional Markov equivalence class where the intervention target is known [69].

---

5.2 (Non-JOrientability of isolated edges
The value of isolated equivalence is that it identifies which DAGs cannot be distinguished (from CI information alone) using unknown interventions. This is formalized in the following theorem:
Theorem 5.3. Suppose G1 and G2 are in the same IEC. If the tuple (G1, I1) induces {T(G) IEEI, then there exists family of interventional targets I2 (possibly the same as I1) such that the tuple I2) also induces {T (T(G("))ee )iezI
Theorem 5.3 shows that it is impossible to distinguish DAGs in the same IEC by looking at d- separations only. While impossible to distinguish within an IEC, it possible to so between different IECs (see Theorem F.7 in the appendix). Together. Theorems 5.3 and F.7 establish that isolated edges are precisely those edges that cannot be oriented by unknown interventions under our assumptions. This does not imply, of course, that this is impossible in practice: We simply need to impose additional assumptions. For example, one could use conditional invariances to improve the identifiability of edge orientations under additional assumptions like direct I Z-faithfulness [58], which we have not assumed in this paper.
Experiments
We test the theoretical results on simulated datasets under two settings: pure child and single latent source. Because this paper is primarily theoretical, the purpose of experiments is simply to verify the theory. particular, for single latent source experiments, we still adopt the pure child structure but we explicitly test our identification strategy no imaginary subset (Theorem 4.4). We generate random causal graphs under different settings of m. n. We do not enforce Assumption (b) nor maximality (Definition 3. /. For each variable Vi in the causal graph, the structural equation is simply V; 4 Σv, Epa()( J(V,) + 6, where is Gaussian noise, and a nonlinear function. We set f to be a quadratic function. To test independence, we adopt Chatterjee's s coefficient [10]. The metric we use is the Structural Hamming Distance (SHD) between the estimated DAG and the true DAG. The results show that even without the graphical assumptions, our method can be effective in recovering the DAG for nonlinear models.
Table I: Experiments on simulated data show the effectiveness of our identification theory. The table shows SHD and standard errors are over 100 runs.
(M.N)
(2, 5)
(3, 8)
(4, 7)
(4, 8)
PURE CHILD
0.01+0.01
0.54+0.13 0.92+0.18
1.35
2.35+:0.30 1.52+0.21
SINGLE SOURCE
0.02+0.02
2.81+0.30
7 Conclusion
Using unknown, latent interventions, we have provided nonparametric identifiability results for a class of graphical measurement models that are commonly used to learn causal representations. For this, we introduced two important graphical concepts: Imaginary subsets and isolated edges. Our proofs constructive and can be implemented on finite samples. Obvious relaxations of interest include finding better sufficient conditions for identifying bipartite graphs and extensions to multi-node and/or soft interventions.
8 Acknowledgments
The authors would like to acknowledge the support of the NSF via IIS- 1956330, the NIH via R01GM140467. and the Robert H. Topel Faculty Research Fund at the University of Chicago Booth School of Business. This work was done in part while B.A. was visiting the Simons Institute for the Theory of Computing.
10

---

References
[1] K. Ahuja, Y. Wang. D. Mahajan, and Y. Bengio. "Interventional causal representation learning". In: arXiv preprint vrXii:2209.11922 (2022).
[2] A. Anandkumar, D. Hsu, A. Javanmard, and S. Kakade. "Learning linear Bayesian networks with latent variables". In: Proceedings of The 30th International Conference on Machine
Learning. 2013.
[3] S. Arora, R. Ge, and A. Moitra. "Learning topic models-going beyond svd". In: 2012 IEEE 53rd annual symposium on foundations of computer science. IEEE. 2012.
[4] J. Brehmer, P. De Haan, P. Lippe, and T. Cohen. "Weakly supervised causal representation learning". In: arXiv preprint arXiv:2203. 16437 (2022).
[5] S. Buchholz, G. Rajendran, E. Rosenfeld, B. Aragam, B. Schölkopf, and P. Ravikumar. Learning Linear Causal Representations from Interventions under General Nonlinear Mixing. 2023.
[6] R. Cai, F. Xie, C. Glymour, Z. Hao, and K. Zhang. "Triad constraints for learning causal structure latent variables". In: Advances in Neural Information Processing Systems. 2019.
[7] F. Castelletti and S. Peluso. "Network structure learning under uncertain interventions". In: Journal of the American Statistical Association (2022).
[8] K. Chalupka, F. Eberhardt, and P. Perona. "Causal feature learning: an overview". In: Behav-
iormetrika 1 (2017).
[9] K. Chalupka, P. Perona, and F. Eberhardt. "Visual causal feature learning". In: arXiv preprint (2014).
arXiv:
[10] S. Chatterjee. A new coefficient of correlation. 2020.
[11] M. Chickering. "Optimal structure identification with greedy search". In: Journal of machine learning research Nov (2002).
[12] D. M. Chickering. "A transformational characterization of equivalent bayesian network struc- tures". In: arXiv preprint arXiv: 302.4938 (2013).
[13] M. Choi, V. Y. Tan, A. Anandkumar, and Willsky. "Learning latent tree graphical models". In: Journal of Machine Learning Research (2011).
[14] D. Deligeorgaki, A. Markham, P. Misra, and L. Solus. "Combinatorial and algebraic per- spectives on the marginal independence structure of bayesian networks". In: arXiv preprins 0rXiv:2210.0082 (2022).
[15] Eaton and K. Murphy. "Exact bayesian structure learning from uncertain interventions". In: Artificial intelligence and statistics. PMLR. 2007,
[16] F. Eberhardt, C. Glymour, and R. Scheines. "N-1 experiments suffice to determine the causal relations among n variables". In: Innovations in machine learning. 2006.
[17] F. Eberhardt and R. Scheines. "Interventions and causal inference". In: Philosophy of science
5 (2007).
[18] R. Evans. "Graphs for margins of bayesian networks". In: Scandinavian Journal of Statisties
3 (2016).
[19] G. R. A. Faria, A. Martins, and M. A. Figueiredo. "Differentiable causal discovery under latent interventions".. In: Conference on Causal Learning and Reasoning. PMLR. 2022.
[20] M. Germain, K. Gregor, I. Murray, and H. Larochelle. "Made: masked autoencoder for distribution estimation". In: International conference on machine learning. PMLR. 2015.
[21] A. Hägele, Rothfuss, L. Lorch, R. Somnath, B. Schölkopf, and A. Krause, "Bacadi: bayesian causal discovery with unknown interventions". In: arXiv preprint arXiv:2206.0166 01666 (2022).
[22] Y. Halpern, S. Horng, and D. Sontag. "Anchored discrete factor analysis".. In: arXiv preprint arXiv:/511.00 1.03299 (2015).
[23] H. Halvä, S. Corff, L. Lehéricy, So, Y. Zhu, E. Gassiat, and A. Hyvarinen. "Disentan- gling identifiable features from noisy data with structured nonlinear ica".. In: arXiv preprint arXiv:2 006.09620 (2021).
[24] A. Hauser and Bühlmann. "Characterization and greedy learning of interventional markov equivalence classes of directed acyclic graphs". In: The Journal of Machine Learning Research (2012).

---

[25] B. Huang, J. H. Low, F. Xie, C. Glymour, and K. Zhang. "Latent hierarchical causal structure discovery with rank constraints". In: arXiv preprint arXiv:2210.01798 (2022). Hyvarinen and H. Morioka. "Unsupervised feature extraction by time-contrastive learning and nonlinear ica". In: Advances in Neural Information Processing Systems (2016).
[26]
[27] A. Jaber, M. Kocaoglu, K. Shanmugam, and E. Bareinboim. "Causal discovery from soft interventions with unknown targets: characterization and learning". In: Advances in Neural Information Processing Systems. 2020.
[28] M. J. Johnson, D. K. Duvenaud, A. Wiltschko, R. P. Adams, and S. R. Datta. "Composing graphical models with neural networks for structured representations and fast inference". In: Advances in neural information processing systems (2016).
[29] I. Khemakhem, D. Kingma, R. Monti, and A. Hyvarinen. "Variational autoencoders and nonlinear ica: a unifying framework". In: International Conference on Artificial Intelligence and Statistics. PMLR. 2020.
[30] I. Khemakhem, D. P. Kingma, R. P. Monti, and A. Hyvärinen. "Ice-beem: identifiable condi- tional energy-based deep models". In: NeurlPS2020 (2020).
[31] I. Khemakhem, D. P. Kingma, R. P. Monti, and A. Hyvärinen. "Variational autoencoders and nonlinear ica: a unifying framework". In: (2019). [32] Kivva, G. Rajendran, P. Ravikumar, and B. Aragam. "Learning latent causal graphs via mixture oracles". In: Advances in Neural Information Processing Systems (2021).
[33] M. Kocaoglu, A. Jaber, K. Shanmugam, and E. Bareinboim. "Characterization and learning of causal graphs with latent variables from soft interventions". In: Advances in Neural Information Processing Systems (2019).
[34] M. Kocaoglu, K. Shanmugam, and E. Bareinboim. "Fxperimental design for learning causal graphs with latent variables". In: Advances in Neural Information Processing Systems (2017).
[35] M. Kocaoglu, C. Snyder, A. G. Dimakis, and S. Vishwanath. "Causalgan: learning causal implicit generative models with adversarial training". In: arXiv preprint arXiv: 1709.02023 (2017).
[36] E. Kummerfeld and J. Ramsey. "Causal clustering for 1-factor measurement models". In: Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining. 2016.
[37] J. von Kügelgen, M. Besserve, W. Liang, L. Gresele, A. Kekić, E. Bareinboim, D. M. Blei, and B. Schölkopf. Nonparametric Identifiability of Causal Representations from Unknown Interventions. 2023.
[38] S. Lachapelle, P. Rodriguez, Y. Sharma, K. E. Everett, R. Le Priol, A. Lacoste, and S. Lacoste- Julien. "Disentanglemenn via mechanism sparsity regularization: a new principle for nonlinear ica". In: First Conference on Causal Learning and Reasoning. 2021.
[39]
S. L.. Lauritzen. Graphical models. 1996.
[40]
S. Li, B. Hooi, and G. H. Lee. "Identifying through flows for recovering latent representations".
In: arXiv preprint arXiv: 1909. 12555 (2019).
[41] P. Lippe. S. Magliacane, S. Löwe, Y. M. Asano, T. Cohen, and S. Gavves. "Citris: causal identifiability from temporal intervened sequences". In: International Conference on Machine Learning. PMLR. 2022.
[42] Y. Liu, Z. Zhang, D. Gong, M. Gong, B. Huang, A. v. d. Hengel, K. Zhang, and J. Q. Shi. Identifying Bright-Variant Latent Causal Models. 2022.
[43] A. Markham and M. Grosse-Wentne
"Measurement dependence inducing latent causal models". In: Conference on Uncertainty in Artificial Intelligence. PMLR. 2020.
[44] G. Mita, M. Filippone, and P. Michiardi. "An identifiable double vae for disentangled rep- resentations" In: Proceedings of the 38th International Conference on Machine Learning.
2021.
[45] G. E. Moran, D. Sridhar, Y. Wang, and D. M. Blei. "Identifiable variational autoencoders via sparse decoding". . In: arXiv preprint a 10. 10804 (2021).
[46] J. Mouton and R. S. Kroon. "Integrating bayesian network structure into residual flows and variational autoencoders". In: Transactions on Machine Learning Research ().
[47]
J. Pearl. Causality. 2009.
[48]
J. Pearl and T. S. Verma. "A statistical semantics for causation". In: Statistics and Computing
2 (1992).
12

---

[49] R. Perry, J. von Kügelgen, and B. Schölkopf. Causal Discovery in Heterogeneous Environments Under the Sparse Mechanism Shift Hypothesis. 2022.
[50] T. Richardson and P. Spirtes. "Ancestral graph markov models". In: The Annals of Statistics 4 (2002).
[51] G. Roeder, L. Metz, and D. Kingma. "On linear identifiability of learned representations". In: Proceedings of the 38th International Conference on Machine Learning. 2021.
[52] B. Schölkopf, F. Locatello, S. Bauer, N. R. Ke, N. Kalchbrenner, A. Goyal, and Y. Bengio. "Toward causal representation learning.. In: Proceedings of the IEEE 5 (2021).
[53] A. Seigal, C. Squires, and C. Uhler. "Linear causal disentanglement via interventions". In: arXiv preprint arXiv:2211. 16467 (2022).
[54] R. Silva, R. Scheine, C. Glymour, and P. Spirtes. "Learning the structure of linear latent variable models". In: Journal of Machine Learning Research Feb (2006).
[55] P. Sorrenson, C. Rother, and U. Köthe. "Disentanglement by nonlinear ica with general incompressible-flow networks (GINY". In: International Conference on Learning Representa- tions. 2019.
[56] P. Spirtes, C. N. Glymour, R. Scheines, and D. Heckerman. Causation, prediction, and search. 2000.
[57] C. Squires, A. Seigal, S. Bhate, and C. Uhler. Linear Causal Disentanglement via Interventions. 2023,
[58] C. Squires, Y. Wang, and C. Uhler. "Permutation- based causal structure learning with unknown intervention targets". In: Conference on Uncertainly in Artificial Intelligence. PMLR. 2020.
[59] J. Textor, A. Idelberger, and M. Liskiewicz. "Learning from pairwise marginal independencies". In: arXiv preprint arXiv: 150, 508,00280 (2015).
[60] J. Tian and J. Pearl. "Causal discovery from changes". : In: arXiv preprint arXiv: (2013).
[61] B. Varici, E. Acarturk, K. Shanmugam, A. Kumar, and Tajer. "Score- based causal represen- tation learning with interventions". In: arXiv preprint arXiv:2301.0888 2000000000000 (2023).
[62] T. Verma and J. Pearl. "Equivalence and synthesis of causal models". In: UAI '90: Proceedings of the Sixth Annual Conference on Uncertainty Artificial Intelligence, MIT, Cambridge, MA, USA, July 27-29, 1990. 1990.
[63] Y. Wang, D. Blei, and J. P. Cunningham. "Posterior collapse and latent variable non- identifiability". In: Advances in Neural Information Processing Systems (2021).
[64] S. Webb, A. Golinski, R. Zinkov, T. Rainforth, Y. W. Teh, F. Wood, et al. "Faithful inversion of generative models for effective amortized inference". In: Advances in Neural Information Processing Systems (2018).
[65] C. Weilbach, B. Beronov, F. Wood, and W. Harvey. "Structured conditional continuous normalizing flows for efficient amortized inference in graphical models". In: International Conference on Artificial Intelligence and Statistics. PMLR. 2020.
[66] F. Xie, R. Cai, B. Huang, C. Glymour, Z. Hao, and K. Zhang. "Generalized independent noise condition for estimating latent variable causal graphs". In: Advances in Neural Information Processing Systems (2020).
[67] F. Xie, B. Huang, 7. Chen, Y. He, 7. Geng, and K. Zhang. "Identification of linear non-gaussian latent hicrarchical structure". In: International Conference on Machine Learning. PMLR. 2022.
[68] F. Xie, Y. Zeng, Z. Chen, Y. He, Z. Geng, and K. Zhang. "Causal discovery of 1-factor measurement models in linear latent variable models with arbitrary noise distributions". In: Neurocomputing (2023).
[69] K. Yang, A. Katcoff, and C. Uhler. "Characterizing and learning equivalence classes of causal dags under interventions". In: International Conference on Machine Learning. PMLR. 2018.
[70] M. Yang, F. Liu, Z. Chen, X. Shen, J. Hao, and J. Wang. "Causalvae: disentangled repre- sentation learning via neural structural causal models". In: arXiv preprint trXiv:2004.0869 (2020).
[71] Yang, Y. Wang. J. Sun, X. Zhang, S. Zhang, Z. Li, and J. Yan. "Nonlinear ica using volume- preserving transformations". In: International Conference on Learning Representations. 2021.
[72] J. Zhang, C. Squires, K. Greenewald, A. Srivastava, K. Shanmugam, and C. Uhler. "Identi- fiability guarantees for causal disentanglement from soft interventions". In: arXiv preprint rxXiv:2307.06250 (2023).
13

---

[73] R. S. Zimmermann, Y. Sharma, S. Schneider, M. Bethge, and W. Brendel. "Contrastive learning inverts the data generating process", In: International Conference on Machine Learning. PMLR. 2021.
14

---

A Definitions
Let G (V, E") be DAG with V (X, where X denotes the observed part and H denotes the hidden or latent part. In the measurement model, G decomposes as the union of two subgraphs G Gg Gμ where Gg a directed, bipartite graph of edges pointing from H X, and Gμ is DAG over the latent variables H. We let E be the set of edges in G3 and let E be the set of edges in Gy. See Figure 1.
For a given node v, we use standard notation such as pa(c), ch(v), an(e), de(v) for parents, children, ancestors, descendants respectively. A node w is a parent of if there exists edge
A node w is a child of if there exists an edge V + w. A node w an ancestor of v if there exists directed path from w v. A node w is descendent of if there exists a directed path from We also define pa(e) pa(v) {u), ch(v) ch(u) U {e), an(u) an(v) U {v) and de(e) (e(v)U(u), Given subset V V.V VV') Usev pa(v). given two subsets A, B S V. pag
= pa( A) n B and given a subgraph G' G. pac. (V') == pa(V") n Similar notation can be defined for children, ancestors, and descendants. We use so()")
A) (
denote the source nodes of G' which are the nodes in G' that do not have incoming edges. We also adopt the convention that H identified with the indices [m] = .I,, m. and similarly X is identified with [n] {L, nt.. In particular, we use pa(i) and pa (H) interchangeably when the context is clear.
Recall that node V/2 is called collider if it is in the form
1/2 + V1 + V3.
For disjoint subsets, A, B, C V, define d-sepa (AB (B|0) C') to mean that A, B are d-separated by C in the graph G which means that active path between and B given by C.
path between and active given C if the following hold:
(a) For every collider in the path, either the collider or one of its descendants is in C.
(b) C does not include any non-colliders in the path
Recall the definitions of (G) and Ty. follows:
Tv.(G) = [AA, C) d-sepa(AB CC) for disjoint subsets B, C CV}
Tv.(P) (AA B|C in for disjoint subsets A,B,CCV))
where V' V.
B
Preliminaries
Markoy equivalence class. Usually, there is more than one DAG that encodes the same set of d-separations. To formalize this, Markov equivalence can be defined as follows [39]:
Definition B.1. Two DAGs G2 and G2 are called Markov equivalent if T(G,) = T(G2).
In particular, Fortunately, MEC has a convenient graphical characterization. Recall that the skeleton of a DAG is the undirected graph of the DAG by ignoring its edge orientations. And e-structure in DAG G is ordered triple of variables (V1, V2, Vi) such that (1) G contains edges V + V/2 and V + V/2 and (2) Vi and V3 are not adjacent in G.
E(G) denote the Markov equivalence class (MEC) that G' belongs to.
Theorem B.2 (Verma and Pearl [62]). Two DAGs are Markov equivalent if and only if they have the same skeletons and the same u structures.
There is also another transformational characterization of Markov equivalent DAGs [12]. Definition B.3 (Covered Edge). We say an edge x >> y covered if x and y share the same parent excluding x (i.e. pa(x)) U [ar} = pa(y)).
Theorem B.4 (Chickering [12]). G1 and G2 are Markov equivalent, then G1 and G2 can be transformed inlo one another by sequence of covered edge reversals.
15

---

H1
H2
H1
X2
XI
X1
X2
(a)
(b)
Figure 3: Distinguishable measurement models under latent interventions.
PDAGs and CPDAGs. PDAG is a partially directed acyclic graph that contains both directed and undirected edges [11]. If DAG G and PDAG P have the same skeleton and u-structures and if every directed edge in has the same orientations G, then G' is called consistent extension of P.
We use completed PDAGs (CPDAG) to represent Markov equivalence classes of DAGs [11]. We define edge to be compelled if, for every DAG of the Markov equivalence class, this edge has the same orientation. A reversible edge is an edge that is not compelled. Therefore, the completed PDAG of MEC is a PDAG that has directed edge for every compelled edge and an undirected edge for every reversible edge. A CPDAG uniquely represents an equivalence class of DAGs and every DAG in the equivalence class consistent extension of this CPDAG.
Measurement models and UDG. Recall that throughout the paper, we consider a specific type of latent causal graph called the measurement model [36, 54] in which there are no direct edges connecting the observed variables.
For any distribution P over V, recall the definition of the undirected dependency graph (UDG), denoted (PP), to be the undirected graph over X in which there is an edge between X; and X, and only if they are marginally dependent (i.e. given the empty set, ef. Remark 2.1). Similarly, we can also define UDG for a measurement model G, denoted DGG), to the undirected graph over X in which there is an edge between two X; and X, if and only if they are d'connected (i.e. by
the empty set, cf. Remark 2.1) in G. Parallel to the definiton of 52(2) which is the set of maximal cliques in D(P()), we can also define o4 to the set of maximal cliques in D(G())). We also let Ω = U
Although it is always possible (i.e. by ignoring independencies and allowing for degenerate edges) to represent any latent variable model with densely connected, independent latents, this ignores precisely the latent (causal) structure that we seek capture. We aim to uncover latent structures that can best capture the observed (in dependdencies. Markham and Grosse- Grosse-Wentrup [43] show that, with only access the observational distribution, we only need minimal measurement model, where every latent variable corresponds to clique of a minimum clique cover set of D(G) and there is no edge between latent variables, to represent all the dependencies of the observed variables X. With interventions, however, such a minimal measurement model may not capture all of the observable dependencies, as illustrated by Example 2.
Example 2. Without interventions, the graphs Figure 3(a) and Figure 3(b) share the same CI statements over X, and the first graph would be the one returned the minimal measurement model. But they do not share the same CI statements under interventions. Specifically, we can intervene on H2 in Figure 3(b) which makes X, and X₂ independent, and this is not possible to achieve in Figure 3(a).
C Discussion of assumptions
In this section, we discuss the main assumptions made in this paper (Assumption I and Assumption 2). With the exception of the Markov property (Assumption 1(a)), which is standard, we will also show why each assumption is needed by providing a counterexample showing that if each of the other assumptions hold but the assumption of interest fails, there exist two sets of measurement models and interventional targets (G1,I, and (G2, I2), which can generate identical sets of observational distributions under unknown interventions. This implies, in particular, that none of our assumptions
16

---

can be removed without imposing additional assumptions. It is an interesting direction for future work to explore possible alternative assumptions more carefully.
We use the following notation in the examples:
(p) is Bernoulli random variable such that
[1
with probability
opp)
otherwise
(p) is random variable such that
1
with probability p
T(p)
-1
otherwise
means XOR;
means AND.
For ease of reference, we recall our two main assumptions here: Assumption 1 (Graphical conditions). The DAG G satisfies the following conditions for every and pair of hidden variables H; # Hy:
p() is Markov with respect G(), i.e. T(G()) C
(b) X; I. P d-separation.
d-sepacn (x,) 0), i.e. marginal independence in X implies
(c) d-sepaun H } 9) = there exists X, E chx and X, E chx(H,) such that d-sepain ((X, (X)) 0).
Assumption 2 (Complete family of targets). I = (Hmm
Remark C.I. Although we know the set of intervention targets, we do not know the mapping from targets to distribution. In fact, it is possible that for two intervention targets I1 and I2, have p(() = p( For instance, if the measurement model has multiple source nodes, then intervening on these source nodes would not change the structures of the DAG. And it is not hard to have parametric examples where the distributions are also kept the same (for instance, see Example 4), So the number of elements in the set { (P&) ( Jrez could be less than m 1. Therefore, we do not even know the number of hidden variables.
In particular, by Assumption (a) and (b), ((P(!) the same D(G and thus of equals 20 We use these concepts interchangeably in this paper.
It is important to highlight that distributions P1 and P2 G2 share the same UDG (i.e. D(P;)= = D(P))) if and only Tx = Tx (G2) (Lemma D.12). Therefore, for Assumption 1(b), (c), and Assumption
measurement models G1 and
in addition show that the measurement models in counterexamples are also structurally equivalent in terms of observed variables, which means that (Tx (G(") ()((")))ee Iez, is the same (Gx( IEIg.
C.1 Assumption 1(b)
Assumption 1(b) requires that the UDG D(P()) correctly encodes the marginal independence structure of P()), It is type of "marginal faithfulness" assumption, however, this a significantly weaker assumption than faithfulness and should not be confused with ordinary faithfulness, which requires that all conditional independence statements in P(T) are encoded in the DAG G(T) To appreciate the sizable. difference. note that Assumption ((b) imposes ((n²) constraints whereas faithfulness imposes ((4") constraints. Similar "marginal"-tyrr -type assumptions have been invoked previously; see [43, 59] and the references therein. Example shows why Assumption 1 is needed. Specifically, because we allow nonlinear functions between observed and latent, without any restrictions, the observed distributions (i.e. over X, both observational and interventional) can be arbitrary.
17

---

H1
H2
H1
X2
X1
X1
X2
(a)
(b)
Figure 4: Counterexample for Assumption 1(b)
Example 3 (Counterexamples for Assumption 1(b)). Consider the two measurement models ((o) and G(b) Figure We will construct structural causal models for G( and Ggb such that they both satisfy Assumption (a), and (c). With the complete family of interventional targets (Assumption 2). the interventional distributions of observed variables for both DAGs are the same. Thus, without Assumption 1(b), there are ambiguities.
Specifically, for G(a). we have the following structural equations:
H1 + (0.5) X1 H1 o
G (0.5)
X₂ - H e 5
G + (0.5)
For G(b). we have the following structural equations:
H1 + (00.5)
H₂ + H1 @6
e (0.5)
6 t (0.5) Xi 11 @ b
X2 - H2 + eg
6g + (0.5)
Assumption 1(b) is violated because X1 and X2 are independent in both cases.
Let P3,(X,,X, be the joint distribution over X1, X2 where X₃ and X₂ are independent bernoulli variables with parameter 0.5.
For G(a), if the intervention target / is 0. then ptf P If the intervention target is {H1 but the interventional marginal distribution of H₁ is still Bernoulli distribution, then p Px-
For G(o), if the intervention target / then (()) P If the intervention target is ( {H₂} but the interventional marginal distribution of H, is still Bernoulli distribution, then p(! Px. If the intervention target / is {H2) and we have H2 <- (0.5), then pX Px
Therefore, both G(a) and (()) can induce ( her = {Px}.
C.2 Assumption 1(c)
Assumption I(C) ensures the relationships between the hidden variables leave observable signatures in the observed data. Of all the assumptions. this one is new to the best of our knowledge and arises due to the fact that (a) We allow for dependencies between the latents, and (b) We make no parametric assumptions. The latter is what crucially distinguishes our approach from previous work that inevitably leverages parametric assumptions to either implicitly guarantee Assumption I(c) or sidestep it altogether. In the fully nonparametric setting, this cannot be avoided, as shown by Example 4.
Example (Counterexample for Assumption 1(c)). Consider the two measurement models G(a) and G(b) in Figure 5. We will construct structural causal models for both G(a) and G()) such that they satisfy Assumption (a)), (b), and (c). With the complete family of interventional targets (Assumption 2), the interventional distributions of observed variables for both DAGs are the same. In
18

---

H
H2
H3
H1
X3
X1
XI
X
X3
X2
(a)
(b)
Figure 5: Counterexample for Assumption I(c)
particular, these two DAGs have the same set of d-separation statements of observed variables under interventions. Therefore, Assumption I(c) needed to avoid ambiguities.
First of all, let us examine the structure of these two measurement models. For (()) if the intervention target is either 0, {Hi}, {H2] or Ha). X1, X2 and X3 always stays d-connected. For G if the intervention target 7 0 or (H1). X,, X2 and X3 also stays d-connected. Therefore, by Lemma D.10, for the complete family of interventional targets [(a) of ((a) and [(b) of (m)) {Tx (G
(a) Hezz is
the same (Tx (G TET
Now let's consider this parametric example. Specifically, for G(a), have the following structural equations:
H1 + (0.5)
H₂ - H1 0
9 + (0.5)
H3 + H2 +6
6 + (0.5))
X1 H1 + H2
X₂ - H2 + H3
X3 + H1 + Ha
And for G(t,, we have the following structural equations:
d - (0.5) & - (0.5) (0.55
H1 + (2,))
X1 (11,1,0), Hi)
X₂ + (10,1,
X3 (11,0,1)
For G(a), if the intervention target is 0. denote P Pk. If the intervention target / is {H1} and H₃ + (0.6), denote / P If the intervention target I is {H2} and H2 + (0.5) or the intervention target }H3} and H3 + (0.5), we have that p(D) P}.
For G(a), if the intervention target / is 0. let p Pk. And if if the intervention target T is (H,) and we set the distribution of et to be (0.6), we also have that p = P
Therefore, both G(a) and G(o) induce { hiz== (P) P And one check that all the other assumptions still hold.
C.3 Assumption
Assumption 2 ensures that the effect of each hidden variable is measured. Example 5 shows why Assumption 2 is needed. This assumption is also made in recent work on causal representation learning [1, 53].
Example 5 (Counterexample for Assumption 2). Consider the two measurement models G(a)) and G(yy in Figure 6. Consider the family of incomplete interventional targets {0, {H2)], and assume
19

---

H1
H2
H3
H1
H2
X1
X2
X3
X1
X2
X3
(a)
(b)
Figure 6: Counterexample for Assumption 2
{0, (H2)). We will construct structural causal models for both G(a) and (()) such that they satisfy Assumption and the interventional distributions of observed variables for both DAGs are the same. In particular, these two DAGs have the same set of d-separation statements of observed variables under interventions. Therefore, Assumption 2 is needed to avoid ambiguities.
that
Let us examine the structure of these measurement models. For G(a), if the intervention target I is 0, X1, X2 and X3 d-comnected. If the intervention target I is (H2), then only X₂ and X3 are d-connected. Similarly, for (b)- the intervention target I is 0, X1. X2 and X3 also stays connected. And if the intervention target 7 (H2), then only X2 and X3 are d-connected. Therefore, by Lemma D.10, {Tx (a) rETT,) is the same as {Tx (G)))
Now let's consider this parametric example. Specifically, for G(a), we have the following structural equations:
H1 + (0
H2 H1 + cî
el + NO0 1) 6 + 10,,1)
H3 + H₂ + 6
X1 H1
X, + H2
X3 H3
And for G(g), we have the following structural equations:
H1 1))
H₂ H1 + ci
& N(0,1
X1 + Hh
X2 H2
X3 + H2 + c
e N(0,1
1
For G(a). if the intervention target / is 0, pb N/ 2n) and E1
2
2
If the interven-
3
0
tion target / is {H2),, and H2 <- NN(0, then p( NO0 222) where Ei
0
a
a
a
On the other hand, for G(yy- if the intervention target / 0, p()) -O E,). And If the intervention target is {H2). and H2 <- (O a), then pt/ = -N0,
Therefore, both G(a) and G can induce (p() (N(0, E1), Ez)). And one can check that all the other assumptions still hold.
C.4 Discussion of subset condition
Subset condition a common assumption used for latent graph identification that dates back to Pearl and Verma [48] (see also [18, 32]. It is defined follows:
20

---

H1
H3
H1
H3
H2
H4
H
H
X1
X3
X1
X3
X2
X
X2
X
(a)
(b)
Figure 7: An Example of maximal measurement model
Assumption (Subset condition). For any H, * Hy. chy (H,) is not subset of chx (H2) and vice versa.
The subset condition ensures that latent variables have observable signatures (i.e. in the observed marginal P)X)) and dates back to the 1990s [48], where was used to study graphical latent variable models, and has more recently been applied on similar problems [18, 32].
turns out that the subset condition implied by Assumption and Assumption 2.
Lemma C.1. Under Assumption I and Assumption 2, the subset condition always holds.
Proof. Suppose the subset condition is violated, then without loss of generality, there exist two hidden variables H; and Hj such that chx (H₂)= chx (H2). Then by Lemma E.4, there exists interventional target such that H, and Hj are d-seperated. But this would violate Assumption (c).
is, however, worth noting that the subset section is implied because of Assumption 2. If the complete family of intervention targets is not assumed be given, one might need assume the subset condition. This is because Assumption (cc) relies on the international targets provided. For example, if the latent graph is complete and the one and only interventional target is the empty set, then Assumption I(c) is not violated for any graph.
C.5 Maximal measurement models
Recall the definition of the maximal measurement model:
Definition 3.1 (Maximal measurement model). A measurement model G is called maximal if it satisfies Assumption and the following two conditions:
(a) pa().) * 0 for all E [n).
(b) There is no DAG G' (V, E') also satisfying Assumption such that, {Tx (Tx(G())) (Gx()"))) and E E..
Example shows why the maximality condition needed.
Example (Maximal measurement model). Consider the two measurement models G(a) and G in Figure 7. We will construct structural causal models for both G(a) and G(a) such that they satisfy Assumption and with complete family of interventional targets (Assumption 2), the interventional distributions of observed variables for both DAGs are the same. In particular, the CI relations of observed variables are the same under different interventions. Furthermore, G(D) encodes strictly more dependencies than G(a) and is maximal measurement model. Since these two graphs cannot
be distinguished from the set interventional distributions (P()) Jiez alone, and one encodes more information than the other, this motivates why consider maximal measurement models.
Let's first examine the structure these two measurement models and show that G(y) is maximal.
For G(o),, if the intervention target I is 0. X1, X2, X3 and X, are d-connected. If the intervention target is }.1}. then only X2, X3. X4 are d-connected. If the intervention target / is {H2), then
21

---

X1, X2, X3 and X1 are d-connected. If the intervention target I is {H3}. then X1, X3, Xa are d-connected and X2 is only d-connceted to X1. If the intervention target I {H4}, then X1, X2. X3 are d-connected and X4 is only d-connceted to X1.
Similarly, for (()). if the intervention target 7 is 0, if the intervention target 7 is 0, X1, X2, X3 and X4 are d-connected. If the intervention target 7 is {H₂ ), then only X2, X3. X, are d-connected. If the intervention target I is { {H2), then X1, X1. X3 and X₃ are d-connected. If the intervention target I is { then X1, X3, X4 are d-connected and X₂ is only connceted to X1. If the intervention target is { (Ha), then X1, X2, X3 are d-connected and Xs is only connceted to X1.
Therefore, by Lemma D.10, for the complete family of interventional targets ((a) of ((a) and I of G(D). (Tx (G (1)I, is the same as {Tx (G(( HEEO
One can also check Giy is maximal because adding additional edges to G(b) would lead to different d-separation statements of observed variables under interventions.
Now we construct structural causal models for each DAG. Specifically, for G(a), we have the following structural equations:
H2 - o
a + (0.5)
H3 - H2e
6 - (0.5) G + (00.5) E + (00.))
H1 - H3C
H1 + H2H
X1 + H1
X2 + H₂
X3 H3
X4 + H44
And for G(b), we have the following structural equations:
H2 + e e + (0.5)
H3 H2e
e + r(0.))
H4 - Hae's
E3 + o
H1 < H2H2 Hae & + o0.5)
X, <- HI
X₂ t H2
X3 H3
X1 t HA
For G(o), if the intervention target / is 0, then X2 = Eq. X3 =992. Xa EfEgeg and Xi efegegel.
For G(b). if the intervention target is 0. then X₂ =t, = e X1 cic and X1 c
For G(a), if the intervention target is { and H2 + éi where é is another Bernoulli random variable, then X₂ = éj. X3- = c X, = Gic and X, = C.g....
For Goo). if the intervention target is {22) and H₂ + é where of is another Bernoulli random variable, then X₂ ci, X3 c X, c/ and X1 G
For G(a), if the intervention target is { and Ha + La where eá is another Bernoulli random variable, then X₃ = ef. X3 = é X, < and X1 E6EEEC..
For Gay, if the intervention target is HHy and H3 + e where e is another Bernoulli random variable, then X₂ = c.. X3 = - X, 6 and X, diGese
For G(a), if the intervention target is (H,} and H. ea where es is another Bernoulli random variable, then X2 ef, X3- Efe, X é and X1 effGg..
22

---

For G(b), if the intervention target is } and H₃ + cg where eg is another Bernoulli random variable, then X₂ = oî. X3 = c X4 Eg and X1 ej
For G(a), if the intervention target is { and H1 t- c4 then X2 = X, x
and Xi =
For (b) if the intervention target 7 is [H1} and H1 < c4 then X2 = X3 = 9 X4 x
and X = 4
Note that the four pairs of (ct. t). (c2 <2), (c) eg) and (4), <t) have the same distributions.
Therefore, both ((a) and ((B) can induce the same { ( P1ez.
frez. And one can check that Assumption 1
still hold.
In general, there are multiple DAGs that are Markov to given distribution, and the question is how do we decide on the correct "minimal" representation. Without latents, there no ambiguity: We can always test all possible CI relations and obtain complete picture to obtain minimal I-map. With latents, we must careful:
If we can check CI relations over all of (X, H)), then the usual notion of a minimal I-map prevails. But in practice, we cannot access P(X, H) since H is unobserved.
Thus, in practice, we should restrict attention to information about P(X) only. In this case, we argue that we should only remove an edge if its removal can be justified on the basis of information about P(X) only. This is the essence of maximality: We only remove an edge if follows from the observed data X. Otherwise, we remain agnostic: We do not want to remove edge that may in fact reflect "real" dependence over H.
This encapsulates the concept of maximality, and the underlying intuition is akin to that of maximal ancestral graphs. As result, our characterization of the maximal measurement model aligns with the core principles of the maximal ancestral graph. Measurement models have latent variables and we only have access to partial information (ie.. observed variables). Since two measurement models can encode the same of conditional independencies over X and the absence of edges encodes nontrivial information, the removal of an edge should be justified carefully on the data we have available.
D Proofs for Section
In this section, we provide all proofs that were left out in Section 4. Recall that we assume that G is maximal measurement model (Definition 3.1) satisfying Assumption 1, and that Assumption 2 also holds.
This first proposition shows that maximal valid subsets can be used to identify bipartite graphs Proposition 4.1. For any hidden variable H3, chx (Hz) is a maximal valid subset.
Proof. By Assumption (aa) and Assumption 1(b), two observed variables X; and X, are dependent if and only if X; and Xj are d-connected. Therefore, D(G!)) D(P(D) under any intervention target I.
Any two variables in chx (H;) would stay d-connected under any unknown intervention on latent variables via the common parent H; So chx (H;) are always in the same clique for any D(G()) and thus chx (H,) must be a valid subset.
Suppose c (H₂) is not maximal. Then there exists a valid subset X' C X such that chx (H,) & X', and by definition, for any intervention target and any maximal clique C 2 such that chx (H+) S C, we have chx (H,) Ç. X' C C. Let e be an element in X' \\ chx (H,). Consider the following new graph G' with added edge H; e. We know that for any maximal clique C' such that chx (H+) C C, we have chx (H+) C chx chx(H.) [e} X' C.
To get contradiction, we need to show that ((G D(G for any intervention target T. Because are adding additional edge to G², existing active paths between any observed variables
23

---

H
H2
X1
X2
X3
Figure 8: In this example, {X2} is a maximal valid subset and is contained in another maximal valid subset X2]
in G still exist in G'. Therefore, ((G can only have more edges, and any potential additional edges in ((Gr()) must be between and some observed node X,, There are two cases. (a) Suppose X; E chx (H;), then because e is always in the same clique as chx (H₂), )), the edge X; - must already exist in D(G()). (b) Suppose X, E chx (H)) where H; * Hy. Then X, and are d-connected because there is an active path between H; and H, under intervention target 1. By Lemma D.13, 26 where chx((H)) c S C. However, we also know that chx(HH) S (H;) U {e) S X S Therefore, the edge X; - e must already exist in D(G!)). Then, (26 Jiez is the same as ( Frez. And by Lemma D.10, (Tx(G())) is the same as {Tx (Gx()) By Lemma D.17, this is not possible because G' is maximal.
there exists maximal clique C E
D.1 Replaceable and imaginary subsets
Somewhat unintuitively, it is possible that a maximal valid subset can be contained in another maximal valid subset. The reason that X" in Definition 3.2 not allowed depend on the clique C. Example 7. Consider G defined in Figure 8. When I {H1) T 0, there is maximal clique C = {X1, Xa} E o When I = {H2), then there are two maximal cliques in 2 {X1, X2) and {X2, Xa). Thus,
Ω ((X1, X2), (X2, Xa). X2,
X2,, Xa)3:
and the valid subsets are {X1). (X2). (X3), (X1,X)) and { (X2, X3). It clear that {X1, X2) is maximal valid subset by the definition. But it turns out that (X2) is also maximal: Even though there are valid between {X2] and each clique in Ω there is not single valid subset with this property.
Theorem 4.3. there replaceable maximal valid subset if and only if there exists a hidden variable H; such that chx( = In particular, it follows that GB is identifiabl.
non-replaceable imaginary subsets, then subset X is non-
Suppose there exists a non-replaceable maximal valid subset X' such that there is no hidden variable H, with chx (H;) X'. Then X' is imaginary, which is a contradiction. Note that X' cannot be a proper set any chx (H,) either, because is non-replaceable and all chx (H;) are maximal valid subsets by Proposition 4.1.
Proof. (+)
(=) On the other hand, there exists hidden variable H; such that chx X'. Then must be non-replaceable. Suppose it is replaceable, then, by definition, there exists another maximal valid subset X" such that X' Ç X" Then by the subset condition (Lemma C.1), X" must be imaginary. Suppose X" is replaceable, then there must exist another non-replaceable imaginary subset that contains both X' and X", which also a contradiction.
On
There might exist a hidden variable H, such that ch x (H,) is replaceable (Example 8).
Example 8 Non-imaginarr set can be replaceable). Consider Figure below. When the inter- vention target is 0. )Ha) (H1). then there are maximal cliques: {X1, X2, X3, X;) and (X2, Xg. X3) When the intervention target / is (.2). then there are three maximal cliques: (X1, {X4} and {X2, X3, Xs). When the intervention target is {Ha). then there are three maximal cliques: [X2, X4h. {X3,Xx Xa) and X2, Xs). Both [X2} and {X2, Xs} J are maximal valid subsets. But (X2, Xs} } is imaginary. One might be tempted to add another edge Hz Xs which would create a clique of (Xe, X4. Xs} when intervening on H3.
24

---

H4
X1
H1
H2
H3
X1
X2
X3
X6
Figure 9: In this example, {X2} is a maximal valid subset and is contained in another maximal valid subset {X2, Xs} even though (X2) the child set H2.
D.2 Single source node
It can be shown that imaginary subsets do not exist if there is only single hidden source node, ic. a hidden variable such that pa(H,) = Note that this still allows for arbitrarily many hidden variables H 1.
For any two observed variables X, and X,. Let p(a.h) be the set of all active paths between X, and X6 in (
Definition D.1 (Dominated path). An active path P between Xa and Xa is called (Xay Xt)- dominated path if either of the followings is true:
(1) P common parent path (i.e., X. + H2 + X, for some hidden variable H₃)) and every directed path to so(P) has at least one node H; + H2 such that such that { (Xa: X,) S chx (H.).
(2) P a common parent path and (a) every directed path so(P) has least one node Н; such that {Xa, X&} S chx (H)) or (b) there exists hidden node H, in P such that Xa < H, - Xy is non-(Xa, X1)-ddmmnnttdd path (see (I)).
Remark D.1. We consider the empty path from H; to H₃ directed path.
Remark D.2. To slightly abuse notation, when so( P) only has element, also use so to mean that element.
Appendix D.2.1 gives some lemmas to characterize dominated paths. Theorem 4.4. Under Assumptions 1-2, if GH has one latent source, there are no imaginary subsets.
Proof. Suppose there is an imaginary subset X'. Then it must have least three elements in it. If |X' = 1, then it must be subset of chx (H:) for some H, If |X'| = 2, then these two nodes do not share the same parent. Thus, there must exist at least two active paths between them ( because of Lemma E.4. By definition, these two active paths non-dominated. But because there is only one single source node in the latent DAG, by Proposition D.5, this not possible.
For every pair of nodes in X', there could only be one non-dominated path between them because the necessary conditions in Proposition D.5 cannot be satisfied when there only one single source node and Lemma D.I shows that there is at least one non-dominated path.
By Proposition D.6, X' cannot imaginary.
D.2.1 Key lemmas and propositions for proving Theorem 4.4
The following two lemmas characterize dominated paths.
Lemma D.1. If X, and X, are d-connected in G(O), then p(a,b) has at least one non-(X,, Xb)- dominated path.
Proof. Because X, and X,, are d-connected in ())) by definition, p(a.b) is not empty.
Now let's consider two cases:
25

---

(a) There exists at least one hidden node that is common parent of Xa and X₁. Without loss of generality, let H1 be common parent of X, and X'. Because there is no circle and there is only finite number of hidden variables, there exists a hidden variable H2 that could be H1 or an ancestor of H1 such that {Xa: ancestor such that both X and X3 are its children. By definition, Xa +- H2 + X, is non-(X,. X;) (i).xxX))ootattt -dominated.
chx (H2) and H2 does not have
(b) There is no hidden node that common parent of Xa and X Then every path in p(ab) is non-(Xa. Xx)) -dominaddte Because p(a.6) is not empty, p(a.6) has least one non-(Xa: domiintte path.
Lemma D.2. If (Xay Xb) is valid subset and po,b has only one non-(Xa, dominnttd path, then the non- non-(Xa: X₂) X.).:x-omminttee Jdddmmminteed path must be a common parent path.
Proof. Let's consider two cases:
(a) There is no hidden node that is common parent of X. and X6. Because {Xa: Xi} is valid subset, there must exist at least two active paths between X, and X, in G Otherwise, by Lemma E.4, Xa and X₁ must be d d-separated for an intervention target. By definition, any active paths between Xa and Xo. are non-(Xa. (x)) -ommintte paths. So, this case is not possible.
(b) There exists least one hidden node that is a common parent of Xa and Xs. Without loss of generality, let H1 be common parent of X, and Xg. If the active path Xa <- H1 + X is (Xa,. . X2) -dominated, we can find an ancestor of H1 called H2 such that {Xa+ X,} S chx (H2). Because there is only finite number of hidden variables and there is no circle. we can eventually find common parent H' of X, and X, such that X₂ f- H' X, is non-(Xa, Xo)--dmmnated path. Therefore at least one of the non-(X.. a; Xy)-dominated paths is common parent path. And if there is only one non-(Xa, X₂) Xo)-nnmidtted path, it must be common parent path.
Lemma D.3. For any two nodes Xa and X5, where pa.b has only one non-(Xas Xo)-dominated path P., then there does not exist a directed path from H2 to H2 with either H₃ + Xas H2 + Xb or
H2 + Xa, H1 - Xb such that so(P) de(H2).
Proof. By Lemma D.2, P. is common parent path. Let H. be the common parent. Now here two cases:
A. Hi H2. In this case, P. would not be non-dominated path by definition. So this is not possible.
B. H1 + H2. Because this path is dominated, then either (a) H. must be on this path or (b) there exists common parent of X.. X5: H' such that H' E an(Hi) Case (a) is not possible because de( H2). Case (b) is also not possible by Lemma D.4.
Lemma D.4. For any two nodes X, and X,, where pa.b has only one non-(Xa, Xx))-dominate path P.. for any hidden node H' that is common parent of Xa, Xy and not the same as so(P.), so(P.) is an ancestor of H'.
Proof. Suppose so(P. (P) is not an ancestor of H'. Then because X, + H' < XG is (Xa, Xt)- dominated path, and there is only finite number of hidden variables, common parent H of X, and X, such that X, +- H" > X, is a non-(Xa, Xx) X,)-dominated path. But so P.) ) not an ancestor of H'. it cannot be H" This a contradiction the fact that pa.b has only non- (Xa, a. (.)...))ooomnnn -ominnted path.
eventually find
26

---

Proposition D.5. (6), S X' where X' is an imaginary subset and Pla.b) has at least two nXn-(Xa, Xx) dominated paths, then the following two conditions hold:
(a) There exists a pair of non-(Xas a Xb) ( -oo-dmninte paths (P1, P2) such that given any interven- tion target I E I, at least one of P1 and P2 is active in G
(b) For any pair of non-(Xay (5))dominated paths (P1, P2) that satisfies (a), there does not exist a single hidden node H that shared by all directed path (P) and so(P2) in G(D)
Proof. First, let's prove the first condition. We consider two conditions:
(a) There is no hidden node that is a common parent of X, and Xb. Because {Xa, X1} is a valid subset, there must exist at least two active paths between Xa and X in G(0), Otherwise, by Lemma E.4, Xa and X,, must be d-separated for an intervention target. By definition, any active paths between Xa and Xs, are non-(Xa. Xs) X -dominated paths.
(b) There exists at least one hidden node that is a common parent of Xa and Xs. Without loss of generality, let H₁ be a common parent of X₂ and X3- If the active path Xa <- H1 - Xτ is (X.. X3, ddmmineiet we can find an ancestor of H1 called H2 such that {X.. X₂} S chx (H2). Because there is only a finite number of hidden variables and there is no circle, we can eventually find common parent /f' of X, and X5 such that X. f- H1' + X, is non-(Xa, doominatee path. Therefore at least one of the non-(Xa, Xr)--dminated paths is a common parent path. Because p(a.6) has at least two non-(Xa. Xx) -dyommnitt paths, and given any intervention target, the common parent path will not be destroyed, the first condition is true.
Let's denote Pi to be a non-(X,, Xx))-ominated active path with hidden variables Ha, and Ha, such that X, + Ha, and X,, Hs.1 in Pt. Let P2 to be an mon-(Xa,,)) Xom--nnind active path with hidden variables Ha,2 and H,.2 such that X, + Ha, and X, + Ha,2 are in Pa.
Now let's prove the second condition. Suppose, the contrary, there exists such hidden node Hy. Because P1 and P2 are Xx).xxX
there must exist one directed path to P1 and one directed path to P2 such that these two directed paths do not have any hidden node H; with Xx} S chx (2),, common node H.. Let H. be the common nodes with the lowest ranking in topological ordering. Then H, has the property that, under any intervention target I, one of the two directed paths Pi,. and P2... where Pt.- the directed path from H. so(P)) and P2,, is the directed path from H. to so P2), still exists. If this is not true, then there is one intervention target T. such that intervening on this node would break Pt.. and P2... Then I, would be common node on Pi.- and P2,, other than H.. This violates the assumption H, has the lowest ranking in the topological ordering. Note that so(P)) or (o2))) only has one element in it by Lemma E.3.
paths share at least except for maybe so and so(P2). P2). On the other hand, these two directed
We now have four paths Pt. P2 PI,+ and P2... Under any intervention target I, one of P1, P2 is active and one of Pı,. and P2,, is still active. Let's consider the following three cases:
A. Pt,. has no shared hidden node with P2 and P2,. has no shared hidden node with P..
First of all, H, cannot be a common parent of X, and X Suppose H, is a common parent of X, and X'. Then by our construction, it is only possible if H, so(Pi) and 11, = so2))). Because Pi and Pg are both non-domin non-dominated paths, they must both be common parent paths in this case. This would imply they are the same path, which is a contradiction.
Note that by Lemma E.3, an active path between hidden nodes H₃ and H2 can only be a common ancestor path or directed path. Either way, there is only one source node of the path and every other node in the path is a descendant of that source node. Therefore, Pi.. cannot have a shared hidden node with P1 except for (PP). otherwise there will be directed circle. Similarly, P2.. cannot have a shared hidden node with P2 except for so For any intervention target 1, there are three cases:
27

---

(a) None of P1. P2 Pi,* and P2.* are affected by I. Then all of Ha.1, Ha,,, Hb,1, Ho.2 are descendents of H..
(b) One of PT.. and P2,, destroyed. Without loss of generality, suppose P2.. no longer exists. The intervention target 7 must be part of the path P2.. and it cannot be H.. Because P2.. has no shared hidden node with Pi intervening on means that P1 is still intact. Therefore, Ha, 1 are descendents of H.. (c) One of Pi and P2 is destroyed. Without loss of generality, suppose P2 no longer exists. The intervention target must be a part of the path P/ and it cannot be so(P)). Therefore, PI, is still intact. 1a, Hb,1 are descendents of H..
Finally, in all three cases, at least one pair of 1 Ho.1) and (Ha.2. Ha,2) is a set of descendants of H.. Now consider graph G' = (V. E') with E' EUUH. + Xa HHH - X.). Note that E' is not the same as E because at least one of {H. + Xa) and (H. + Xs) is missing. Otherwise, H, would be a common parent of X, and X,, By Lemma D.15, G' violates the maximality.
B. Without loss of generality, Pi,. has shared hidden nodes with P2 and P1 is not common parent path.
Note that in this case, P2.. cannot have a shared hidden node with P1 except for one special case. Suppose the opposite is true. Let the shared node between Pt.. and Pz be H4. Let the shared node between P2,+ and P1 be H2. There must be a circle between H1 and H2 if Hi # H2 which is a contradiction. If H1 = H2, then H1 H₂ so(P)) = so In this case, there is always at least one pair of (Ha.1, Hb.1) and (Ha Ho,2) that is a set of descendants of so({;) and so(P)) under any intervention target. In this case, adding {.a. X to chx (s)(P))) would not change 2 by the proof of Lemma D.15. By Lemma 1.17, this is not possible. So we will ignore this special case.
Now let's 'ss consider the following cases under any intervention target I for when P2., does not have shared hidden node with P1:
(a) None of P1. P2 P1,+ and P2,+ are affected by L. Then Ha,1, Ho, are descendents of so(P)).
(b) Pi.. is destroyed. Then P1 must be intact because the intervention target is in Pi
Ha, Ho,1 are descendents of so(P1).
(c) P2.. is destroyed. Because P2,. does not have shared hidden node with Pl, Ha, Ho.1 are descendents of (P)).
(d) P2 is destroyed. Then P1 must be intact. Then Ha, Ho, are descendents of (P).. (e) P1 is destroyed. Then P2 must be intact. Pt.. must also be intact because the inter- vention target is in P1 and it is not so(P)). Because P2.. cannot have a shared hidden node with P1, P2., is also active. Therefore, Ha,2, H5.2 are connected to so P1) via the common ancestor 11,.
= (u (soo)ss(PP)) + Xo}.No Note Let's consider graph G' (V, with E'= that E' is not the same as E because at least one of {so P1) - Xa) and (so(P.) + Xx} is missing because Pj is not common parent path and P1 is also non-(Xa; X.)-dominated.
For any intervention target I that induces (a), (b), (c), (d), adding (Xa, Xx} to ( P1)) would not change 2 ()) by the proof of I Lemma D.15.
For any intervention target / that induces (c), ( does not have more edges than D(G)). If the opposite is true, then the new edge in D(G must involve the added node X, or X₁. Without loss of generality, suppose the new edge is between Xa and Xx. it must be that parent of X is d-connected to so(P)) ). Suppose that the parent of X is He. By Lemma E.3, there are 2 cases. If so Pt) has a directed path to HE. then H₃ is connected to Xa and Xo via the common ancestor H. If H₂ has a directed path to so )) or Hş and P1)P share a common ancestor, by our assumption, Hę and (Xa. Xa) are connected by common ancestor Hg. Therefore, X and X, are d-connected in D
So adding (Xa, Xx) to chx (so Pi)) would not change (
Finally, by Lemma 1717, this is not possible.
28

---

C. Without loss of generality, Pi,+ has shared hidden nodes with P2 and P1 is common parent path.
Let Hi be the shared node between PI.. and P3 that has the lowest topological ranking. Therefore, for any intervention target I, least one of P2 and the directed path from Hi to so(P1) is intact. Otherwise, Hi is not the shared node between PI,+ and P2 that has the lowest topological ranking.
First, let's consider two scenarios.
(1) Both P1 and P2 are common parent paths. First of all, so( so(P)) is not the same as so (P2). Otherwise, P1 and P22 would be the same path. On the other hand, if so P2) appears in Pi.. because there is the only possible node that can be shared and is not so Pi ), it would violate how Pt.. chosen. So this scenario not possible.
(2) Pi is common parent path and P2 is not. First, Hi is not the same as so P1) because Hi is also on P22 which non-(X X₂) -dominattdd path. By definition, this is not possible. On the other hand, Hi is not a common parent of X. and X5 because it would violate how Pt.- is chosen. Wl'll study this scenario next.
Similar to the previous case, P2.. cannot have a shared hidden node with Pj. Now let's consider the following cases under any intervention target I:
(a) None of PI, P2 P1,+ and P2,+ are affected by Then Ha,1, Ho,1 are descendents of Hi.
(b) P2.. is destroyed. Because P2,. does not have shared hidden node with P1, Ha,,, Ha,1 are descendents of Hi.
(c) P2 is destroyed. Then the directed path from Hi to so(P1) is still intact. Then Ha,1 Hb,1 are descendents Hi.
(d) Pi.- is destroyed but the directed path from H, to so(Pi) is still intact. Then P1 must be intact because the intervention target in Pi, Ha,,, Ho.1 are descendents of Hi.
(e) Pi is destroyed or the the directed path from H1 to so(P) (P)) is destroyed. In either case, P2 must be intact. The directed path from H, to H1 must also be intact. Because Pe.x cannot have a shared hidden node with P1 or Pt.,, P2., is also active. Therefore, Ha,2, Ho, are connected to Hi via the common ancestor H,.
Now consider graph G' = (V, with E' (H, E' is not the same as E because at least one of (Hi X,) and (H: - Xx) is missing. By the same argument as fore, G' also violates the maximality assumption by Lemma D.17.
+ X²). Note that
Finally, we have a contradiction. So the second condition is also necessary.
Proposition D.6. Suppose X' C X a valid subset with |X| 2 and every pair of nodes X' has only one non-dominated path. And the latent DAG only has one source node. Then the followings are true
(1) there exists a hidden node H' with X' C cH)
(2) for any node X₃ E X', one can find at least another node X3 X' such that X, t- H'
Xj is non-(X;, Xy)-dominated path.
Proof. We'll show this by induction.
Base step: This is because of Lemma D.2.
Inductive Hypothesis: Suppose the statement is true for all X' with XX| = k.
Inductive Step: We will show the statement is true for |X'| = + Without loss of generality,
let's suppose X' = [X1,.., ). Consider the subset X" = (Xi,.., X2). By the inductive hypothesis, there exists a hidden node H' with X C chx (H') and again without loss of generality, mon-oonnnnnnoo two nodes X1 and X2, such that X, +- H' + X2 is non- (X1, X2) X2) dominated path.
29

---

Now consider another subset X1,4+1 = Xx+1). By our assumption and Lemma D.2, there exists a hidden node H1, +1 such that X1 t- Hi, H1, X is a (., Xx+1) ddominated path. We can define 12, in similar way.
If H1 H', then we done.
Let's now consider the cases when H1,8+1 # Ht' Because there only one single source node, there must exist at least one common ancestor of 11,41 and H': H., Now let's consider three cases:
(I) H1,++1 is an ancestor of H'. Then there is a directed path P from H1.++1 to H'. Now we have an active path between X2 and Xx+1 via Because this path is (X2, Xx+1)- dominated, we have few cases.
(a) There exists common parent of X2, X that is in an 1+11), which means that H2,841 1 is an ancestor of H1,841 by Lemma D.4 (case (c) covers when H2 = H1,4+1). By Lemma D.3, this is not possible because have path between X1 and X2 via the directed path from H2,841 to H1, but H' is a descendent of H1,441-
(b) H2 is on P but it is not the same as HI nor H'. By the same argument as the case (a), this also not possible because of Lemma D.3.
(c) H2 = 11.++ This means that H1,4+1 is common parent of X2. So it cannot be an ancestor of H'. This is contradiction.
(d) When H2 = H', then H' is the hidden node we are looking for because X' S chx dH') and for any node X, E X', there exists another node Xj X' such that X; < H' + X, is a non-(X, ; X₃) Xy)-dominated path (for X one can choose X₂ such that X2 H' Xk+1 is non-dominated path).
(2) H' is an ancestor of H1 H1,++1 1. Then there is directed path P from H' to H1,++1 Let X,, be an arbitrary node in X" that not X1. Then we can define hidden node H Hy such that Xg f Hg, + Xk-1 is non-(X,, Xx+1) d-domnntted X path. Now we have an active path between Xg and Xx+1 via P. Because this path is (Xg. X241)-dominater we have a few cases.
(a) There exists common parent of Xg. X8+1 that is in an(H', which means that Hq is an ancestor of H' by Lemma D.4 (case (c) covers when Hg.0+1 = H'). By Lemma D.3. This is not possible because we have a path between X, and X via the directed path from Hg to H' but H1,441 is a descendent of H'.
(b) Hg is P but it is not the case (a), this is also not possible because of Lemma D.3.
as H1
H'. By the same argument the
(c) Hq H'. This means H' is common parent of Xx+1- So it cannot be an ancestor of H1,8+1. This a contradiction.
(d) Hq H1,441. This is possible. But because X, is chosen arbitrarily. We have Hg H1,4+1 for q = ..., Therefore X' C chx (H1,&+1). And for any node X: + Xx+1, we have that X; <- H1,4+1 + X is non-dominated path.
(3) There exist a common ancestor H. that is neither H1,+11 nor H', H' is not ancestor of H1,441 and HI,4+1 is not an ancestor of H'. H. is a common ancester of X2 and Xx+1- Therefore, there is common ancestor path between X2 and X But this path is (X2, (x+1)-dominatee path.
There are two cases: (a) Ha E an(H1,44 when H2 is on the directed path from H. H1 or there another common parent of X2, Xx41 that an an(H.) (Lemma D.4), (b) H2,4+1 E (H'H)) when H2,k+1 is on the directed path from H, to H' or there is another common parent X2, X that is an. (Lemma D.4). For case (a), we have a (X1, -2)xxnadomitteed path cased by the path from 22 to H1,+11 In this case, because X1 < H' - X₂ a non-(X (X1, ddmminnnd path. H' must
ancestor for H1,41,
which is contradiction. By similar argument, case (b) is also not possible.
30

---

X
H2
H5
H3
X
X1
H
H4
X4
X
X
X7
Figure 10: In this example, the non non-imaginary subset {Xs,, Xo, X7} is fractured
X4
X5
X6
X1
X5
X6
H1
H₂
H3
H1
H₂
H3
H4
X1
X₂
X3
X1
X2
X3
(a)
(b)
Figure 11: An example where two maximal measurement models share the same UDG
D.3 Fractured subset condition
A necessary condition for a non non-replaceable imaginary subset is that the subset is fractured. The definition is restated below. Intuitively, fractured subset provides redundant information as every connection between nodes in the fractured subset can be explained by other maximal valid subsets.
Definition 4.5 (Fractured subset). Given a collection of maximal valid subsets S, clique C is called shattered by S if there exists a subset S' S such that US C. collection of maximal valid subsets {S: [S is complete if for every intervention target / E I, all shattered cliques in D(P(T) form an edge cover of D(P'). ). A maximal valid subset X' C X is fractured if there exists a complete collection {5.) such that S; g X' for all S..
The aforementioned necessity is shown by the following: Lemma 4.6. If a subset X' S X is imaginary, then X' is also fractured.
Proof. By Lemma 1.16, we know that {chx (H:)) a complete cover. And because X' is an imaginary subset, X' g ch (H,) for any H₃-
One might suggest getting rid all fractured subsets. However, even a non-imaginary subset can be fractured subset (Example 9).
Example 9 (Non-ime Non-iimginnary set can be fractured). Consider Figure 10. If the intervention target I is {H1}. {H2). 0. then we have two maximal cliques: {X1, X3, X4, X6, X7}. (X2, X3. Xs, N6,X7,, If the intervention target I is {Hg }. then there three maximal cliques:
X5, X7). {X2,X4, X4, X6,X,) [X,, Xs, No. X7). If the intervention target / is (Ha), H then there three maximal cliques: (Xa. X X7). (X2, X3. Xs, X6. X7). (X1, X3, Xs. X Xy When the intervention target is (Hz). there are three maximal cliques: (X,,X,, Xel. {X2, Xah. (X3, X4, Xs, X6, X7). By Proposition 4.1, all these five valid subsets are maximal: (Xi, Xs. Xe). (X2, Xs, Xo). (Xa, Xs, X7). (Xa, Xo, X7) and (X5, Xo, XT). But (Xs, Xa, X7) is fractured. In fact, (X1, X5. Xa). (X2, Xs. Xe). (Xa, Xs, X7). (X4, Xe, X7) constitutes complete collection of maximal valid subsets.
Even under the maximality condition, is still possible that two DAGs can share the same UDG (Example 10). The no fractured subset condition captures such ambiguities but is overkill.
31

---

Example 10. Consider Figure 11. For both (()) and ((), under any intervention target. there are four maximal cliques: { X1. {X2, Xot. X4, (X1, Xs, And one can check that both ((a) and (()) satisfy the maximality condition.
D.4 Pure child assumption
We can also use the pure child assumption (Assumption 3) to get identifiability. The pure child assumption has been made in many existing works [6, 22, 66] with additional parametric assumptions to get identifiability.
Assumption 3 (Pure child). For every H, E H, there exists at least one X; E X with pa(X,) = (Hi), i.e X, only has parent and that parent H;.
Note that under Assumption 3, there still could be imaginary subsets.
Example 11. Figure 12 satisfies Assumption but there is an imaginary subset (X5, Xo)-
Theorem 4.8. Under Assumptions 1-3, the complete collection (cf. Definition 4.5) with the smallest and thus G3 can be identified.
cardinality is exactly
Proof. By Assumption (aa) and Assumption 1(b), two observed variables X, and X, are dependent if and only if X, and Xj are d-connected. Therefore, ((G()) is the same as D(P(1) under any intervention target L.
By Assumption 3, let's associate each hidden node H; with one pure child X,-
First of all, there does exist imaginary subset with two pure children X; and Xy of different hid- den parents. If the opposite is true, then X,) must be valid which is impossible by Lemma D.14. Therefore, every complete collection must have least maximal subsets.
By Lemma D.16, {chx != complete collection with m maximal subsets.
In fact, {chx (H is the only complete collection with m maximal subsets. Suppose there exists a complete collection with imaginary subsets. There two cases:
A. None of the imaginary subsets contains a pure child. Then we still need at least m non- imaginary subsets to cover pure children.
B. At least one of the imaginary subsets contains a pure child. Suppose one such imaginary subset is S; and it contains X,. Then there must exist another maximal subset from the collection that contains X,.
Suppose the opposite is true. Because S; is an imaginary subset, there exists X₃ E S, such that X and X, do not share the same parent. And for any intervention target 7, if there is any edge between X; and Xj in D(G()), by definition, there exists a shattered clique C' D(G()) such that {X,, X,) C C and S; C. Therefore, there is an edge between Xj and X₂ as well. Now consider graph G' = (V,E') where E' = E U (H, + Xx)- Under any intervention target 1, D(G"()) can only have more edges than D(G and there exists new edge, these edges must involve X₁. Suppose one of these newly added edges is between X₁ and Xj. Then it must be that a parent of X, is d-connecetd to H; This would mean that X; is d-connedted to X, in ((G))). By the previous argument, X is also d-connedted to X, in D(G()). Thus, G" would violate the maximality condition by Lemma D.10 and Lemma D.17 which is a contradiction. Therefore, there one
H1
H
H
H
X;
X1
X₂
X
X
X
Figure 12: In this example, the graph satisfies pure child but (X,, Xe) ) is an imaginary subset.
32

---

imaginary subset in the complete collection that contains pure child, there must be at least two imaginary subsets that contain such pure child. This means that to cover m pure children, we need more than m maximal subsets.
On the other hand, suppose there exists a complete collection with at least one maximal subset X' such
that X' S chx (H,). Then X' must not include the pure child of H;: X,, This is because, if X; E X then for any maximal clique because any node in C' C (X²) } is d-connected by X; via H2 since X; is pure child. Therefore, X' is not maximal which is a contradiction. Because X' does not contain a pure child of H;, we still need
E Ω such that X' C C, we have that {X;} S X' C chx(H,) S C
cover all m pure children. We need more than m maximal subsets.
For algorithmic purposes, under the pure child assumption, one only needs check if shattered maximal cliques form an edge cover.
Lemma D.7. Under Assumptions 1-3, for any intervention target I, all maximal cliques E 52 that is shattered by {chx (H,)) )m is an edge cover of D(P(n).
Proof. By Assumption (a) and Assumption 1(b), two observed variables X, and X, are dependent and only if X, and X, are d-connected. Therefore, ((G()) is the same as D(P(1)) under any intervention target /. By Assumption 3, let's associate each hidden node H, with one pure child X; I. there exists one
Suppose the statement is not true. Then for some intervention target clique C' in o that is not shattered and that clique contains one edge that is not covered by other shattered cliques in 2 Suppose that edge between X1 and X2, then there exist H1 and H₂ with X₁ chx (H1) and X2 chx (H2) and H₃ is d-connected to H2. Let one such active path between H1 and H2 be P1.2. By Lemma E.3, there exists one source node s0(2222 (If H1 = H2. then so (1.2) is just H1). Note that we can always find one node H, in an(so that has no incoming edge. Let's denote that the pure child H, is X..
Then C, = ) chx(H, must be a shattered maximal clique in 26 Suppose C. is not maximal clique. Then the maximal clique that contains C. must contain another element X3 not in C.. There must exist another hidden variable H3 with X3 (H3) that H, is d-connected to because X3 is connected to the pure child of H.. But this is not possible by Lemma E.3 and the fact that H. is a source node while X3 not a descendant of H..
D.5 Examples of measurement model with no non-replaceable fractured subsets
Lemma 4.6 shows that an imaginary subset is fractured subset. Because a replaceable imaginary subset can be found, our concern should focus solely on the non-replaceable ones (Theorem 4.3). In fact, Corollary 4.7 can be strengthed to say that as long as there are no non-replaceeble fractured subsets, then the bipartite graph can be identified. In this section, we will show a class of measurement models with no non-repleeeable fractured subsets (see Remark 4.1).
Let's first present a simple example where there are multiple source nodes and the pure child assumption is violated, and there still no non-replaceable fractured subset.
Example 12. Consider Figure 13. If the intervention target is 0, H1 Hs. then maximal cliques are {X1, X2, X3} and {X2, Xz, X1). 3. If the intervention target is H2, then there are three maximal clique: (X,, X2). (X2, X3) and {X3, X4). One easily check that there is non-
replaceable fractured subset.
H1
H₂
H3
X1
X₂
X
X4
Figure 13: In this example, there is no fractured set.
33

---

In fact, we can extend Figure 13 to a family of measurement models as follows: Definition D.2 (Sparse Measurement Model), For a given measurement model G = (V, E) and V X U H, if X2 X2 X is d-connected, then it must be that
1. There exists at most one hidden node H, such that {X1, X2] S chx (Type-1 path).
2. There exists at most one active path between X, and X2 such that pap(X) (X1) * pap(pp) (Type-2 path).
And for any tuple (X1, 1; X2, X3) S X such that (X1; X2) S (H2) and (X1; X3) S chx (H3) with H2 * H3, X2 and X3 can only be d-connected via type-2 path P with the property that pap(X2) H2 and pXp((x)= H3-
Theorem D.8. Under Assumptions 1-2 and with maximal sparse measurement model. there is no imaginary subset.
Proof. Suppose there is an imaginary subset X'. Then |X| 2 3. If X' has only element, then it must be subset of c (H') for some hidden node H'. If X' has two nodes, by the definition of sparse measurement, there could only be one active path between them and there exists an intervention target that can break this path. So X' would not be valid.
Next, we'll 'Il use induction show that for any valid subset X' with [X'| 2 3, there exists a hidden node H' such that X' C chx (H'). In other words, X' cannot be imaginary.
Base Step: If X 3. then let X" = 121,X2, X2, Xa). Suppose X' is imaginary. Then every pair of nodes in X' must have a type-1 path and ttyp-22 path because there exists an intervention target that can destroy the type-2 path but every pair of nodes is valid. Therefore, we have Hi.2 as the common parent of X2, H2.3 as the common parent of X2, X3 and H1.3 as the common parent of X1, X3. Note that these three hidden nodes are distinct, otherwise, X' would not be imaginary. This is also not possible by the definition of the sparse measurement model.
Inductive Hypothesis: For any valid subset X' with [X|| = k 2 3, there exists hidden node H' such that X' C chx (H²).
Inductive Step: We'll show this is true for X = + 1. Without loss of generality, suppose X" [X1,... X By the inductive hypothesis, x"= (X,,,, X2) are both non-imaginary. In other words, there exist H" and H such that X" C chx(H") (H") and X" C chx (. Because XX| 2 4. both H" and H" are common parent of X2 and X3. By the definition of the sparse measurement model, H" = H"
and X" = {X2, ..., X
O
Theorem D.9. Under Assumptions 1-2 and with maximal sparse measurement model, there is no non-replaceable fractured subset.
Proof. By Theorem D.8, there is no imaginary subset. Therefore, if X' is maximal valid subset, then X' C chy (H,) for some hidden variable Hç. By definition, if X' non-replaceable, there must exist a hidden variable H; such that X' = chx (H,).
In addition, if X' is fractured, there exists a complete collection S [5 such that S, g X' for all Sj. Note for any Sj. there exists a hidden node H, such that S; C ch (H2) because there is no imaginary subset.
First of all, X' must have at least two elements in it. If XX 1, then by the subset condition (Lemma C.I). no other hidden variable can be a parent of the single node in X' and the aforementioned complete collection does not exist.
Let X1, X2 be two elements in X'. Because the measurement model is sparse, by Lemma E.4, there exists an intervention target I (could be the empty set) such that, the type-2 path between X1, X₂ is destroyed. Under this intervention target, there must exist C' E D(G()) that is shattered by S and contains (X1, X2). Therefore, there exists a subset of S: (8) with (X1, X2) C C US
Because S% & X', there exist two maximal subsets S and Sy such that X, E S and X₂ E Sy. This also means that there exist Hi and H2 with X1 E S C chx (II, and X2 E S S chx Hi
34

---

and Hy must be two different nodes other than H; by the defition of the sparse measurement model. In addition, because Si & X', there exists X3 Si where X3 & X'.
and (X1, Xa} C chx (H1) and X2, X3 are d-connected under the intervention target T, by the definition of the sparse measurement model, X2 and X3 are d-connected via the path between H; and H1. This is not possible because this path creates another type-2 path between 1 and X2.
Because (X1, X2) S chx
D.6 Useful lemmas
The first two lemmas show that we only need to care about maximal cliques of undirected dependency graphs.
Lemma D.10. For two measurement model 11 and G2 and two intervention targets 11 and Iz, we have that &
(12) ifand only Tx (x(
Proof. If (x Tx (G then (( is the same ((G! by construction of undirected dependency graphs. The obviously 26 = ( On the other hand, if 2 = 52
(1a)
then ((G(")) is the same as () by Lemma D.11. By Proposition [43], Tx (1) (22))
Tx (G2
L
Lemma D.11. IfG1 Ez) and G2 = (V, E2) share the same maximal cliques, then E Eg.
Proof. Let's first show Ei E2. Suppose (A- + B) E2 and (A + B) & Ej. Then there exists maximal clique that contains A, B for G2. But there is no clique that contains A, B at the same time for G1. Therefore E₁ S Ez. Similarly, E2 E1.
Lemma D.12. Under Assumption I(a) and (b), two distributions P1 and P2 over two measurement models G1 and G2 share the same UDG if and only if (G1) = Tx (G2).
Proof. Because of Assumption 1(a) and (b), D(P) D(G,) and D(P2) D(G2). By Lemma D.10 and Lemma D.11, the statement is true.
O
Lemma D.13. If two hidden nodes H; and Hj are d-connected G under intervention target then there exists a maximal clique C Eo such that ( U (H,) C
Proof. Because H; and H are d-connected, chx (H.) and chx (H₂) form a clique. Therefore, there exists maximal clique that is superset of chx (H:) U chx (Hz).
Lemma D.14. If a set of two observed elements (Xa, X&} is valid and Xa, Xy do not share the same parent, then one of X, and Xs, must have at least two parents.
Proof. Xa and N,, do not share the same parent. Therefore, there must exist at least two hidden nodes Ha,1 and Ha such that X, Ha,1 and X, Hr,1- However, if there are only two such hidden nodes, Lemma E,4 suggests there exists an intervention target / that makes X, and X, d-separated and thus X, and X,, d-separated. This violation of the fact that Xb} is valid subset. O
Lemma D.15. For hidden variable H, there does not exist observed node X; such that X; & chx (H.) but under any intervention target I E I, X is descendant of H..
Proof. This violates maximality.
Consider G' = E') with E' = = EUHH, - X1). For any intervention target I, D(G does not have more edges than D(G'). ). If the opposite is true, then the new edge in ((G must involve X,. Suppose the new edge is between X; and X,, it must be that a parent of X2 is d-connected to H,. However, because X; is a descendant of H,, by Lemma E.3, X; must be d-connected to X, in is the same as {Tx (G())
D(G)). Therefore, by Lemma 10 (Tx (Tx(G)))
By Lemma 1717, the existence of G' violates the maximality condition.
35

---

Lemma D.16. {chx (H:) is complete cover.
Proof. By Assumption (a) and Assumption 1(b), two observed variables X, and X, are dependent if and only if X; and X, are d-connected. Suppose {chx (H;) is not a complete cover. Then for some intervention target / E I, there exists one clique C' in D(G() that is not shattered and that clique contains one edge that is not covered by other shattered cliques in D(G(D). Suppose that edge between X1 and X2. then there exist H1 and H2 with X₁ chx(H1) and X2 chx (H2)) and H1 is d-connected to H2. By Lemma D.13, this is not possible.
Lemma D.17. IʃG = (X U H, E) is a maximal measurement model, then there does not exist measurement model G' (X U H, E') with E' E u (H, + X.3 for some hidden variable H;
and observed variable X; such that for any intervention target I E I, where I is the complete family of intervention targets,
Tx Tx = (G
Proof. By the definition of the maximal measurement model, we just need to show that G' also satisfies Assumption 1. G'' satisfies Assumption 1, then the existence of G' would mean that G is not a maximal measurement model. Before delving into the graphical assumptions, one first notices that because for any intervention target I E I, Tx (G(I)) = Tx (G"(1),, then X; must always be d-connected to chx (H;) in both G(I) and G*()) under any intervention target.
For Assumption ((a), if distribution P is Markov to G. then it must be Markov to G". This is because G" has one more edge than G, any active path in G would remain active in G' as well. Thus T(G") T(G) S T(P). A similar argument can be made for the interventional case.
For Assumption 1(b), we know that for any intervention target I, X; TL pi) (=se)pcu((x){((X) (0). Because Tx(U)) = (G"()), Assumption 1(b) is true for G' as well.
For Assumption (c)), because Tx (G Tx (G)LD) for any intervention target and G', G only differs in biparite graph. If Assumption ((c) is satisfied by G. it must be satisfied by G' as well.
Therefore, G' satisfies Assumption 1 and G is not maximal, which is contradiction.
E Learning the skeleton of latent structures
Once we have learned the bipartite graph GB, the next step is to learn the DAG GH over the latent variables H. This turns out to be straightforward: Assumption I(c) suggests that two hidden variables H, and H, are d-separated if and only if chx (H;) and chx (H₃) are in different cliques (Lemma E.2). Therefore, the idea is to learn causal graphs using unconditional d-separations of latent variables under interventions.
Define Mn as follows:
(H = (H(A, d-Bepo for disjoint subsets A, C H)).
Note that My MG) C. (G) because M (G) only stores unconditional d-separations. Therefore, to learn the latent DAG, we would like to answer the following question:
Given (M IEI, can recover Gn?
Remark E. This is harder than the fully observational case where we have access to all conditional d-separations.
The answer to the previous question is affirmative shown by the next theorem (see Appendix E.2). Theorem E.1. Under Assumptions 1-2 and suppose the bipartite graph GB is correct, the skeleton of GH is identifiable.
E.1 Identifying unconditional d-separations of the latents
Given the bipartite graph Gn and (Tx(P(U)) we can easily construct (Mn(G())) by the following lemma.
36

---

Lemma E.2. Given intervention target I, two hidden variables H; and H are d-separated in G and only if there does not exist a clique E Stp such that chx (h,(H,) chx (Hz) C.
Proof. By Assumption ((a) and Assumption 1(b), two observed variables X, and X, are dependent if and only if X, and Xj are d-connected.
If H2 and H2 are d-separated in G then, by Assumption I(c), there exists X,, X; E X where X; E c ( E ch)(H,), such that X; and X, are independent. Therefore, chx (H,) Uhhx (Hj)
not a clique.
On the other hand, if there exist clique C' 2 such that chx (H.) U c S C. This means that (H,) U chx (lx) is a clique. Then H2 and H must be d-connected, which contradiction.
E.2 Algorithm
Now have Algorithm 1 to find the skeleton.
Algorithm Learning Skeleton of Gæ
Input: (Mu(G"))))eez
E - 0;
// Set of unoriented edges
/* Step
2 {M (M (G(N)) only has one distinct element then
L Output: E
/* Step 1: Remove any pair of hidden variables that appears twice for Mn(G()) (Mn(G do for (H1, H2) (M(() do
*/
If (H1, H2) appears twice with at least two different intervention targets, delete (H1, H2) from (M
/* Step 2: Add unoriented edges for Mn(D(() (MM(G())) do
for (H1, H2) (x(G(() do
E + E (H2 H2)}
Output: E
Theorem E.1. Under Assumptions 1-2 and suppose the bipartite graph GB is correct, the skeleton of Gy is identifiable.
Proof. The proof relies on the correctness of Algorithm 1 which show here.
First, suppose HM (G( only has one distinct element. Then there is no edge between latent variables in Gи. Suppose, on the contrary, there is an edge H1 - H2 between two hidden variables H1 and H2 in GØ. then by Lemma E.2, chx(HI) chx (H2) must be clique in ((G())). But by Lemma E.3, when the intervention target / is H2, H1 and H2 would be d-separated, and by Lemma F.2, ch (Hi) U chx (H2) must not be clique in D(GU)). Therefore, there must be at least two distinct elements in (M
Now, let's consider the case after step O. Let's denote the unoriented edge set returned by Algorithm I as E, and the true unoriented edge set of Gμ as E2.
A. E2 C Ej. By Lemma E.3, [MH(CC) (G())) has all pairs of hidden variables. And we removed all the pair that does not have an edge Eg by Lemma E.S.
B. F1 C F2. Suppose 3(H, H2) Fn such that (H1, H2) & Eg. Note that (H1, H2) only appears with one intervention target and by Lemma E.5, this is not possible.
D
37

---

E.3 Useful Lemmas
Lemma E.3. Given DAG G = (V, E). If twwo nodes A, B E V are d-connected by the empty set, then at least one of the following must be true
A. They share common ancestor (common ancestor path)
B. There are directed paths between the two nodes and all the directed paths must have the same direction (directed path)
Proof. Because A, B are d-comnected, there must exist active paths between the two nodes. There are four possibilities of active path
A. A ... B. This could be direct path if every edge points the same direction. If one of the intermediate edges points in the opposite direction. Then we would have a collider which makes the path inactive.
B. 4- B. The same as the first case.
C. ... + B. This is not possible because there must exist a collider on the path.
D. A --... + B. A and B must share common ancestor in this path unless there is a collider which not possible.
Obviously, we cannot have two directed paths pointing in opposite directions because that would create circle.
Lemma E.4. For any two hidden variables H1 and Hg, there exists at least one intervention target I I, such that (H1, H2) E (G()))).
Proof. If H1 and H2 d d-separaeed in G(O), then we can just choose I 0.
If H1 and H2 are d-connected in ( and assume, without loss of generality, the directed paths between H1 and H2, if exist, point H2. then based on Lemma E.3, we intervene on Hg. all the active paths between H1 and H2 would disappear.
Lemma E.5. (M has least two distinct elements, then for any two hidden variables H1 and H2, there is no direct edge between H₃ and H2 if and only if there exists at least two intervention targets I,, I. such that (H1, H2) E MM(G()) and (H1, H2) E &M (GU1)).
Proof. If there is direct edge between H1 and H₂ and there exists only one intervention target I I, such that (H1, H2) MMH(G(F)) then Iı * 0. There is because if I 0 and (H1, H2) (H Then there would not create active paths. Because (G(()))))) has at least two distinct clements, there must exist another intervention target such that (H1, H2) appears. By the proof of Lemma E.6, one of H1 and H2 is the intervention target IT. Without loss of generality, suppose I {H₂}, }. we can add H1 < H2 to the graph and it would violate the maximality condition. Thus, if there is no direct edge between H, and H2, then there exists at least two intervention targets I, In I, such that (41HH) Mи (G(h) and H2) (G((aa))
active paths between H1 and H2 and deleting edges via interventions
If there exists at least two intervention targets 41, 1, E I, such that (HI, H2) E (H(U(()) and (H1, H2) E M (G(l)),, then suppose there is a direct edge between H1 and H2. Without loss of generality, let's assume H1 - H2. Then two variables would only be d-separated when intervening on H2 which is contradiction.
Lemma E.6. In Algorithm I, after step 1, for any intervention target I such that Mz()(D) # ())),) then there exist hidden variable H1 such that H₃ (H, H2) for all (H,, Hy) e
MH (HU))) and H2 is the intervention target 1.
38

---

Proof. We just need to show that if Hz) E (M and HH,, & Mz(G(()) for I' + I, then one of H; or Hj must be the intervention target I. This because, after step every pair of hidden variables only appear once.
Suppose the opposite is true, then neither H; H2 is heing intervened on. So there is direct edge between H; and H2 since otherwise H; and H, would be d-connected. On the other hand, (H, Hz} & MH(G()) for I' + I, implies that H; and H, are d'connected in the observational distribution because My (GU) # M Then by Lemma E.3, or H2 such that (H;, H5) would appear again which would be a contradiction.
find another intervention target H;
F Limitations of edge orientations
Unlike known interventions, with only access to CI information, edge orientation might not always be possible even when there are no latent variables as shown in Example But it also possible as demonstrated by Example 13. This raises the question of which edges provably cannot be oriented.
In this section, we attempt answer this question by studying equivalence relations between DAGs under unknown interventions. Such equivalence relations are finer partitions of the Markov equivalence class. The results are purely graphical and can be studied in their own right. If assuming Markov and faithfulness, it also shows the limitations of edge orientations with access to CI information only. In addition, one could use conditional invariances to improve the identifiability of edge orientations. But it might require additional assumptions like direct I-faithfulness(58 which we do not make in this paper.
Example 13. Consider the CPDAG G shown in Figure 14. Let G be consistent extension of G such that X₁ X2 and I X2. Then ((X1, X2, 0), (X3, X2, 0)} T(G(")) G2 is another consistent extension of G where X₂ + X2 but there does not exist an intervention target that can induce T(c(41)). Therefore, if we observe T(G(()), then know that X1 - X2.
X3
X1
X₂
Figure 14: CPDAG of three variables with no latent variables.
In this section, we consider the general case of an arbitrary, fully observed DAG (i.e. H = 0) instead of the measurement model. Given the skeleton of the DAG, all the compelled edges in the MEC can already be identified without access to interventional distributions. Therefore, without loss of generality, assume the CPDAG given and study if unknown hard interventions on single nodes can help orient reversible edges. Furthermore, because isolated edges are covered, they must be reversible the MEC as well (cf. Lemma G. there is no loss of generality focusing on reversible edges.
To state the problem formally:
Given a CPDAG G, we want orient its reversible edges given list (TGG!))ee for a family of intervention targets and G.. which is the true consistent extension of G. In other words, is the tuple IG,,I) the unique one that can induce (T(G!)))ee) Iiez?
Let's start with some definitions, Recall the definition of covered edges[12]: Definition B.3 (Covered Edge). We say edge y is covered if x and y share the same parent excluding x (i.e. pa(x) U {a] = pa(y)).
In particular, an isolated edge is a special covered edge. Definition 3.3 (Isolated edge). We say edge - y is isolated if does not have any parent (pa(z) = $) and y only has x as its parent (pa(y) = {x)).
Remark F.I. Isolated edges trivially covered.
39

---

F.1 Isolated equivalence class
Chickering [12] show that two Markov equivalent DAGs can be transformed into one another by sequence of covered edge reversals. The isolated equivalence class is also defined in a transformational fashion. We restate the definition below.
Definition F.1. (Isolated equivalence class) Two DAGS 11 and G2 are isolated equivalent, denoted G1 ~E G2 there exists a sequence of isolated edge reversals.
The next two theorems show that it is impossible to distinguish DAGs in IEC by looking at d-separations only.
Theorem F.2. Let 1₁ and G2 be two consistent extensions of CPDAG G E). Suppose
1. G₁ and G2 only differs in one isolated edge
2. All the interventional targets are single nodes and the intervention is hard.
Suppose the tuple II) induces (T(G)"))EE)
Then there exists a family of interventional targets I2 such that the tuple (G2, I2) also induces (T(GP)))
Theorem 5.3. Suppose G1 and G2 are the same IEC. the tuple (G1,Iı) induces (T(G)) MLeL. then there exists family of interventional targets Ig (possibly the same as IT) such that the tuple I2) also induces (T(G()) (
Proof. Because G₁ and G2 are in the same IEC, then, by definition, there exists sequence of isolated edge reversals. Then we can prove by applying Theorem F.2 repeatedly.
F111 Proof of Theorem F22
Definition F.3. (Augmented Active Subgraph) Let G = EV, be DAG and let path P V1 + V& be an active path given C' where C C V. Suppose H4 is a collider, then there must exist at least node Va in de( (V)) where E C. We define an active descendent path of V; to be directed path from VÚ2 to Va. An augmented active subgraph of P is subgraph including the active path P and all the active descendent paths of colliders the original active path.
Remark F.2. Our definition also considers the special case where V, Va and the directed path is just Vi V4,
Lemma F.4. Let G EV, be DAG. Let be single node hard intervention target, then,
T(G) S T(G))
Proof. Doing a hard intervention on any node V, E V removes all incoming edges to H;.
Suppose the statement is not true, then there exists (A, B)C) E T(G) such that (A, B, C) & T(G'). This means that intervening on Vi2 creates an active path between A, B given C. But deleting edges would not create new path. The only way active path can emerge is if previously blocked path becomes unblocked after an intervention.
A path is blocked if either:
1. any non-collider is being conditioned on.
2. no descendants of collider (including itself) is being conditioned
For the first condition, know that deleting edges would make non-colliders colliders. On the other hand, deleting edges would also not make non-descendants descendants (intervening on the collider itself would destroy the path). Therefore, hard intervening single node would not create new active paths.
Lemma F.5. Let G be a DAG. Suppose there is an active path G, and the hard intervention target I is not the augmented active subgraph of the active path. Then this path stays active.
40

---

Proof. Because the intervened node is not on the path nor on the directed path going out from one of the colliders on the active path. Deleting its incoming edges would not change these paths.
Lemma F.6. Let G1 and G2 be two DAGs that share the same augmented active subgraph of active path P given conditioning set C. If there is single node hard intervention one of the nodes of that augmented active subgraph in both G1 and Gz. then either the path is active in both G1 and G2 or it is not active in either G1 or G2.
Proof. Intervening on any node on the active path would destroy (if the intervened node has incoming edges) or sustain (if the intervened node has no incoming edges) the path both G₁ and G2.
Suppose we intervene on a descendant of a collider on the active path that is not the collider itself. Any active descendant path that has the intervened node on would get destroyed. The path would stay active if there cxists an alternative active descendant path that does not involve the intervened node, which is shared between G1 and G2 because they share the same augmented active subgraph. Note that intervening on node would not create a new descendant path.
Proof of Theorem E2. For notation, let's suppose the isolated edge is V; - Vj in G1. To prove this, we just need to show that for any 1; I1, there exists 17 such that
(1) ) TTG
In particular, we will show that we can choose 1 = {Ti) when I; * (Vi and I = [V3} when
7, = (V:).
By the definition of Markov equivalence, we know that
T(G1) = T(22)
First of all, note that augmented active subgraph given conditioning set C' in G1 must exist and be active given conditioning set in G2 and vice versa. We know that two DAGs in the same Markov equivalence class share the same skeleton and v-structures. Therefore, for any augmented active subgraph given conditioning set C' in G1. there is a subgraph with the same skeleton in G2. If the edges of the augmented active subgraph in G1 have the same orientations in G2, then it is active in G2. If some edges of the augmented active subgraph in G1 have different orientations than that of G2. Then the subgraph can only differ in one isolated edge. Because the endpoints of isolated edge cannot have other parents, the isolated edge cannot be in the descendant paths. The isolated edge can be in the active path itself, with edges going out from endpoints of isolated edge. When that edge is reversed, the path is still active.
To show that T(G(L)) -TGGL") B, C) E T(G!f))). By Lemma F.4, T(G,) C T(G and T(G2) C CTGG()) We can only B, consider tuple (A, C) where C,C T(Gi).
we first need to show that for any (A, B.C E T(C
If BA C) E T(G1), but (A, E T()( then all the active paths between and B given C' must be blocked or deleted after intervention on I, Let's consider the following two cases:
1. Suppose an active path has the same augmented subgraph in both G1 and G2, then it will get blocked in G2 when intervened on 4; 1;. Note that I; is neither Vi nor Vj- Because Vi + V3 is isolated, they do not have other parents. Intervening on them will not block/delete that path.
2. Suppose an augmented subgraphs in G2 and an augmented subgraphs in G2 differ in one isolated edge. If the intervention target I; is V., then we can choose I, to be Vj (intervening on V, in G will not delete that path). If the intervention target is neither V, nor Vj, then we can keep I5 to be the same as I,. Because V; + V, is an isolated edge, this edge must be on the active path itself and not on the active descendant paths. Suppose the active path P is V1 - ... - Va, then the subpath P1 Vi + + V, and P3 : V2 ... - V/ have the same augmented subgraphs in both G2 and G2. By Lemma F.6, the intervention would have the same effect on them.
41

---

Therefore, if 1 {4} when 4 * [V} and I (V2} when 4; (Vi). By similar argument, ) [T((
E.1.2 Orienting Non-isolated Edges
While it impossible distinguish within an IEC, is possible to do so between IECs.
Theorem F.7. Let 11 and G2 be two DAGs. Suppose
A. G1 and G2 are Markov equivalent.
B. G1 and G2 are not isolated equivalent.
Then there exists a single-node hard intervention target I such that
T(G # T(GG)))) V12
where I2 is also single-node hard intervention larget.
Proof. Let AG1,, G2) denote the of edges in G1 that have opposite orientations in G2-
By theorem of [12], we know that there exists a sequence of [ G2)l distinct covered edge reversals that can transform G1 to G2. And each covered edge reversal creates DAG in the same Markov equivalence class.
Because G1 and G2 are not isolated equivalent, there exist DAGs Gm and G, in the sequence such that Gm and G,, differ by covered edge where endpoints the edge share at least one additional parent node. Without loss of generality, let G, and G, be the first pair in the sequence to have covered but isolated edge reversal. In particular, the sequence G1
Gm Gn + ... G2-
For simplicity, suppose the covered edge in Gm is A + and the common parent C. Obviously, in Gn, the covered edge is reversed (A B). Suppose there is intervention target is { {B), then edges C + B and + B get removed. Therefore, there exist subsets of vertices Si and S2 such that C and B are d separated by S1, and and B are d separated by S1.
Gm that
However, for all DAGS the subsequence after Gm, including G, and G2- The edge is reversed be A B (Note that the sequence has A G2)l distinct covered edge reversals that can transform G to G2. A reversed edge cannot be reversed again). There does not exist single node intervention target that can remove both edges between A, B, and B, C.
Therefore,
T(G + (a)
VIz
By our construction, Gm and G1 are in the same IEC. By Theorem F.2, there exists an intervention target 1, such that,
T(G(")) # (() vl2.
F.1.3 Useful Lemmas
The first lemma characterizes the uncovered reversible edges.
Lemma F88. Let G1 be consistent extension of a CPDAG G. Suppose there is an uncovered edge e: A + B in Gj and the edge is unoriented in the CPDAG, then there must exist a node C G such that C + B and C' +- A.
Proof. Because is uncovered, there are two cases.
A. There node in G that is a parent of but not parent of Suppose there is no edge between C' and A. Then because is unoriented, changing its direction would destroy a r-structure. Therefore there must be an edge between and and because is not parent A, we have C < A.
42

---

B. There is a node C' in 11 that is parent of A but not a parent of B. By similar argument, Therefore there must be an edge between C' and B. Because C' is not parent of B, we have
C <- B. In this case, we have a circle. Therefore, this is not a valid case.
The next lemma characterizes reversible edges in an IEC. Lemma F... Let G1 and G2 be two DAGs in the same IEC. Let be a reversible edge in G1 that has the opposite orientation in G2. Then, e1 must be isolated.
Proof. Let's denote ei in G1 as A +- B. We can consider two cases.
A. 61 is covered edge in G1-
Suppose, on the contrary, éi is non-isolated. By definition, there exists common parent C. Because é1 has the opposite orientation in G2, we have A B in G2. G1 and G2 are isolated equivalent and thus Markov equivalent. They must share the same skeleton. So there must be edges connecting C, A, and C, B in Gg. By definition, there exists sequence isolated edge reversals from G2 to G1. There are only three valid possibilities (the fourth one is ignored because it creates circle) in G2:
(a) C' + A, +- B. Out of all the three edges among A, B, C. the first edge that might be reversed the sequence
< B. But regardless of the orientation of the edge between B and C, one cannot reverse A <- B in the sequence as it cannot be an isolated edge.
(b) C - A, + B. Out of all the three edges among A, B, C, the first edge that might be reversed in the sequence is C + A. But regardless of the orientation of the edge between B and C, one cannot reverse A < in the sequence as cannot be an isolated edge.
(c) C A, C <- B. Because G₁ and G2 are in the same IEC. The first edge to be reversed must be B + A. But then, we cannot reverse B + C' because it is not covered and we cannot reverse + C because it is covered but not isolated. So this case is also not possible.
B. e) is not covered edge in G1.
By Lemma F88, there must exist node C' in G1 such that C - B and C A. Note that in G2. we have A +- B. By definition, there exists scquence isolated edge reversals from G2 to G1. There are only three valid possibilities (the fourth one is ignored because it creates circles) in G2:
(a) C A,C + B. Both C + A and A +- have to be reversed. Out of all the three edges among A, B, B, C, the first edge that might be reversed in the sequence is C <- B. But regardless of the orientation of the edge between B and C, one cannot reverse
A 4 B the sequence as cannot be an isolated edge.
(b) C < A, C < B. Because G1 and G2 are the same IEC. The first edge to be reversed must be B + A. But then, we cannot reverse B + C' because it is not covered.
(c) C + A. B. All the edges must be reversed. Because G1 and G2 are in the same IEC. The first edge to be reversed must be B + C. But then, we cannot reverse B + because it covered but not isolated and we cannot reverse - A because is not covered. So this case is also not possible.
G Edge orientations for measurement model
Up this point, we have used unknown interventions learn the skeleton of the underlying DAG G (Appendix D, Appendix E). For causal interpretation, we must go one step further and orient these edges. Now, orienting the edges in the bipartite graph is easy: In measurement model, the observed X cannot have any children, so the only possibility is to orient the edges from hidden to observed. Orienting edges the latent space different matter: Since the intervention targets are additionally unknown, this raises additional complications.
43

---

We extend Algorithm I to Algorithm 2 to orient edges in Gμ up to isolated edges which cannot be oriented using CI information only in general (Appendix F).
Theorem 5.1. Ler G be a maximal measurement model satisfying Assumption and assume we are given a complete family of interventions (Assumption 2) as well as the bipartite DAG Gp. Then the true latent DAG Gy is identifiable up to isolated edges. Moreover, isolated edges cannot oriented without making additional assumptions.
Proof. The identification is given by Algorithm 2.
Suppose the returned PDAG is G# First, by Theorem E.I, G# and Gи share the same skeleton. By Lemma G.2, all the unoriented edges are the reversible edges the Markov equivalence class E(GH). ). If reversible edge H1 + H2 is not covered covered but non-isolated in Gı then H2 has at least two incoming edges by definition and Lemma F.8. Then H1 + H2 will be correctly oriented because M (G(H))) has least two members. Therefore, the only reversible edge that cannot be oriented is the isolated one.
By Lemma E9, the only reversible edges in the IEC of Gh are isolated in Gи. And by Theorem 5.3, we cannot distinguish DAGs in IEC with unknown single-node hard interventions.
G.1 Useful Lemmas
Lemma G.1. Let G be a DAG and suppose X - Y is a covered edge in G. then X + Y is not compelled in E()).
Proof. By Lemma of [12], we can reverse this edge to get G' and G' is Markov equivalent G. By definition of compelled edge, is not a compelled edge.
Lemma G.2. Every unoriented edge returned by Algorithm is a reversible edge of the Markov equivalence class (GH).
Proof. Recall that an edge is reversible if there exist two members of the equivalence class that have two different orientations of this edge.
Without loss of generality, suppose one of the unoriented edges returned by Algorithm 2 is H₁ +- H₂ in GH. Let's consider the following cases:
A. In GR. Hi has incoming edges other than Hi +- H2.
this case, when the unknown intervention target / is {H1). there are at least two elements in (H((()) after step of the algorithm. By Lemma E.6, we can thus orient the edge H1 + Hg in step 2.
B. In GH, H1 has incoming edge other than H1 <- H2 and H2 has at least two incoming edges.
In this case, when the unknown intervention target 7 is H2, there are at least two elements in M ()(D)) after step I of the algorithm. By Lemma E.6, we can thus orient the incoming edge of H2 step and orient 1I H2 in step 3.
C. In Gg. H₁ has no incoming edge other than H₁ +- H2 and H2 has only one incoming edge. Suppose the other edge is H2 +- Hş in Gμ- Then this edge must also be unoriented the Algorithm 2. Because if this edge is oriented, then H2 must be in Ż by step 3 which implies that H₁ + H2 must also be oriented as well. Therefore, we can reverse H; < H₂ and H2 + H3. Because H2 + H3 is unoriented, H3 must have at most one incoming edge since the other cases have been ruled out by the previous argument. If it has one incoming edge, we can reserve that edge as well. The process continues until we reach one node that does not have any incoming edge. The whole process does not create any new u-structures. So we have two Markov equivalent graphs with different orientations of Hi +- H2.
D. In GH, Hi has incoming edge other than Hi +- H2 and H2 has incoming edge.
44

---

Consider Gy where Gy has the same edges as Gy except that Gy has H1 + H2. Because v-structure is created or destroyed with this edge reversal, G3 and Gn are Markov equivalent.
If an edge is unoriented, it must fall in the last two cases and be reversible.
45

---

Algorithm 2 Learning Skeleton and Orienting Edges
Input: H, (T)
E E-0 0;
// Set of directed and undirected edges // Set of intervention targets
10 I+0: 0: /* Step
*/
(M (G(1)) rez only has one distinct elemen! then L Output: E
/* Step 1: Remove any pair of hidden variables that appears twice for MH(G(() (M)(G())))eE do for (I1,, H12) MM(((() do If (H1,, H22 appears twice with at least two different intervention targets, delete (II1, H22 from (M
*/
14
Remove Mr((G from (Mr(GGU)) if Mn(G(D) has element.
/* Step 2: Add edges for colliders
for MH(G(1) E (M) do if M (M()) 1 then
16
17
Find the common hidden variables H, shared by all tuples in Ma (G(I)
18
7 -+ (H.) for (H1, H22 E MMH(G()) do if H1 H. then
19
20
22
+ EU EU + H1}
23
else
24
E EUIHi + H2}
Remove MH(G(() from (G
25
/* Step 3: Add compelled edges
NewIne True: // Flag check if new intervention targets are added to Σ while NewInu True do NewInv t False
27
for Mu(G))) e (MH(G do
29
Let the only element in My (GD)) be (H1 H2)
30
if Hi E ī then
31
32
E (U H22
T-UufH NewInu + True
33
34
Remove MH(G()) from (Mu
35
36
else if H1 E I then
37
E + E U H2 - H1}
Žu (H1} NewInw + True
39
Remove Mz from {My (G
40
/* Step Add unoriented edges Mn(G()) (M do Let the only element in My (GL)) be (H1 H2)
41
43
E c F. U ( (H,
H2}
Output: G (H, E)
46


Reviews:
[{"review_id": "kwTfXMZJR0", "reviewer": "Reviewer_ZNv1", "summary": "This paper studies the problem of nonparametrically constructing latent causal graphs given unknown _interventions_ in a measurement model. In particular the paper given a constructive proof of establishing sufficient conditions under which one can find the latent causal structure between observed and hidden variables. \n\nAuthors achieve this by first defining a notion of *imaginary subsets,* which is a subset of observed variable that are not children of a single latent variable. Authors show that if a graph does not have any imaginary subsets then up to some assumptions on the graph, one can identify a causal structure. Author further give sufficient conditions that guarantee there don't exist imaginary subsets in the graph. \n\n**Update**: After reading other reviews and rebuttals. I have updated the score from 5 to 6. ", "questions": "In theorem 3.5, one needs to know $\\{ P^{(I)}}_{I\\in \\mathcal{I}}$. Isn’t this a very strong assumption as one needs to exactly know the intervention distributions for all hidden variables since $\\mathcal{I} = \\{0, \\{H_1\\}, …, \\{H_m\\}\\}$.", "limitations": "Authors have addressed limitations of the work. ", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "\n- Authors identify sufficient conditions for when causal structure is possible and construct a causal graph under this setting.\n- Paper is thorough and identify limitations with respect to  limitations of the proposed construction.", "weaknesses": "- Overall though the paper is difficult to follow for non-experts. It heavily relies on jargon that is used commonly in causal inference and thus proves to be a difficult read. For instance from the abstract authors use unknown *intervention* starting in the abstract which is not defined much later in the paper.\n- The paper can really benefit from a running example that could guide the reader through all the definitions because in the current state one it is difficult to follow.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your review!\n\n**“Overall though the paper is difficult to follow for non-experts. The paper can really benefit from a running example that could guide the reader through all the definitions because in the current state one it is difficult to follow.”**\n\nThanks for the suggestion! “Intervention” is a standard term in the causal inference community. We actually use Figure 1 as our running example which covers most of our key graphical concepts. We will be happy to add some more detail about this example in the camera ready.\n\n**“Theorem 3.5”**\n\nThis is a common assumption and in fact, it is an open question whether or not this can be relaxed [a-b]. [a] also shows that this assumption is necessary (Section 3.3 of [a]).\n\nSince our focus is on the nonparametric side, we have not yet looked into optimizing the number of interventions. The complete family of intervention targets is needed to guarantee exact latent graph recovery (appendix C.4), but one might be able to relax these assumptions to get partial recovery. On the other hand, knowing all the interventional distributions does not mean we know the interventional target. In fact, we argue in the paper that two interventional distributions could be the same and thus we might not even know the number of latents. \n\nMoreover, compared to classical work on interventions in graphical models, the current literature on causal representation learning (including our submission as well as [a,b]) considers a strictly harder setting since the interventions are both latent and unknown. Since the intervention target is latent, we only have access to partial information (observed variables) regarding the effect of interventions. And since the intervention target is unknown, compared to the known intervention target, we additionally have the unorientability problem of isolated edges which is discussed in section 5.2 (L357).\n\n[a] Seigal, Squires, Uhler. \"Linear causal disentanglement via interventions.\" arXiv preprint arXiv:2211.16467 (2022).\n\n[b] Varici, Burak, et al. \"Score-based causal representation learning with interventions.\" arXiv preprint arXiv:2301.08230 (2023).\n"}, {"review_id": "KerJXjLjD6", "reviewer": "Reviewer_3v5g", "summary": "The paper discusses the identification and reconstruction of latent causal graphs from unknown interventions in the latent space. The main focus is on uncovering the latent structure in a measurement model, where the dependence between observed variables is less significant than the dependence between latent representations without parametric assumptions.\nThe paper presents a characterization of the limits of edge orientations within the class of Directed Acyclic Graphs (DAGs) induced by unknown interventions. The paper concludes with an experimental evaluation that shows the recovery of the causal graph using structural Hamming distance as the error metric of the true vs. learned causal structure.\n\n********** POST REBUTTAL *******\n\nThank you to the authors for their responses. I’m satisfied with the clarifications and increased my score", "questions": "Could you elaborate on why is needed to rely on the concept of imaginary subsets?\n\nWhat was the main technical challenge to define the additional concepts of imaginary subsets and isolated edges?", "limitations": "The paper does not describe potential societal impacts.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "Creating models that identify the causal structure in scenarios where parametric assumptions are not applicable is an important problem in causal inference.\n\nThe proposed approach uses interesting and clever concepts to provide a novel perspective of latent causal graphs. \n\nThe proposed approach provides an intriguing perspective about the DAGs’ equivalence class associated to unknown interventions.", "weaknesses": "Some details of the paper could be further clarified such as why not used stablished concepts of Markov equivalence classes, etc. Or why not consider non-parametric learning of causal structure such as the one in Gao, et al. (2020) or Azadkia et al. (2021)\n\nAnother aspect to consider is the fact that the evaluation is done with two settings and 100 runs for only 4 combinations of M,N. \n\nIn general the paper main contributions seem interesting from a theoretical perspective and because of that a more thorough discussion could have improved the paper to compensate for the limited evaluation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your questions! We also agree that this problem is important!\n\n**“Some details of the paper could be further clarified such as why not used stablished concepts of Markov equivalence classes, etc. Or why not consider non-parametric learning of causal structure such as the one in Gao, et al. (2020) or Azadkia et al. (2021)”**\n\nThanks for the question! These papers do not consider latent variables or the measurement model and hence are not applicable to our setting. Markov equivalence applies to observational data without interventions, thus with interventions, standard graphical concepts such as Markov equivalence are not as useful. (Note that the MEC is of course still valid, it just does not account for interventions.)\n\n**“Another aspect to consider is the fact that the evaluation is done with two settings and 100 runs for only 4 combinations of M,N. In general the paper main contributions seem interesting from a theoretical perspective and because of that a more thorough discussion could have improved the paper to compensate for the limited evaluation.”**\n\nThanks for acknowledging our theoretical contributions! We have detailed and thorough discussion of the assumptions and limitations of our theory in the appendix. For instance, we discuss why our assumptions are necessary in appendixes C and D. We also discuss in detail the difficulty with identifying bipartite graphs and why dealing with imaginary subsets is nontrivial with many examples in appendix E. Currently, because our paper is primarily theoretical, the experiments are shown as a proof of concept. It would be an exciting future direction to extend our results to real-world datsets. Other methods that rely on functional assumptions could potentially surpass our approach when supplemented with extra functional information (such as linearity). Nonetheless, our theory holds greater generality as it pertains to a wide range of nonlinearities.\n\n\n\n**“Could you elaborate on why is needed to rely on the concept of imaginary subsets?”**\n\nImaginary subsets arise because we allow arbitrary connections between the latent variables. This is explained very briefly at L196-200, and we are happy to include more detail on this as follows: It is possible that two observed nodes can stay d-connected under any interventions even when they do not share the same parent. The densely connected latent graph makes them appear as if they share the same parent. The existence of imaginary subsets complicates the identification of the bipartite graph (example 8 and example 9). In this paper, we show additional assumptions one can have to get rid of imaginary subsets (section 4.2) including one testable assumption (no fractured subset, corollary 4.7). We also show how to identify the bipartite graph even with the presence of imaginary subsets under pure child assumptions (section 4.3). These are explained in detail in both Section 4 and Appendix E.\n\n\n**“What was the main technical challenge to define the additional concepts of imaginary subsets and isolated edges?”.**\n\nThe main technical challenge with defining imaginary subsets is finding a concise way to encapsulate the difficulties with learning bipartite graphs and define them in a way that’s useful for guaranteeing identifiability. For instance, in section 4.2, we define fractured subsets which is a testable necessary condition of imaginary subsets. This is made possible by our precise notion of imaginary subsets. The main technical challenge with isolated edges is to identify whether they are the only non-orientable edges under unknown interventions, which we show by introducing isolated equivalence classes (section 5).\n"}, {"review_id": "h9wIPXmppq", "reviewer": "Reviewer_bZuh", "summary": "this paper aims the learn the causal structure in the latent space, by using interventional data, where the intervention targets are unknown, but with certain restrictions. This paper's focus is to provide some theoretical analysis, to show that, under what assumptions, we can recover (up to what level) the causal structure (include the bipartite DAG between observable variables and latent variables, and the DAG within the latent variables).", "questions": "1) can we give a definition of clique in main body?\n\n2) in line 224~226, the paper said \"In other words, G can be maximally identified in the sense that any edge in the latent space that isn’t oriented cannot be oriented from the given list of interventions using CI information only: Additional assumptions are needed (e.g. conditional invariances and direct I-faithfulness).\"\nI want to know, if the additional assumptions are included, how much further we can achieve? from my perspective, conditional invariance and direct I-faithfulness are fair assumptions, they basically say that \"when you do intervention, the data distribution should be changed in a rational way; otherwise, intervention cannot introduce detective changes thus you can exploit nothing from interventional data\"", "limitations": "N/A", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1 - the paper deals with a very challenging, or even ill-posed problem, about recovering the causal structure in latent space.\n2 - the theoretical part seems to be sound.\nI have checked the illustration and the proofs in appendix C, the idea of the necessity of the assumptions in (1) is well presented\n3 - recovering latent causal structure has great potential for AI or AGI area.", "weaknesses": "The most concern from my side is that, what this paper is telling lacks real-world relevance. this makes me doubt if this work can be helpful for practical usage. It seems to be more like a analytical deduction in that, given what assumptions, what I can achieve. but whether these assumptions are relevant in real-world is unclear. Some details\n1) Can this work be evaluated from \"causal representation learning\" perspective?\nfor example, image pixels are generated from some latent concepts/entities, which seems to be quite aligned with the motivation of this work, can this work be experimented on any such case to justify its real usefulness?\n2) justification of the required assumptions\nmany assumptions used in this work are untestable, although the authors discussed some of them, and pointed out that they are not be ignored, which is fine. But without real-world relevance, how can I know in what situation should I apply the proposed algorithm? for example, a complete family of targets seems to be too strong, from the perspective of \"causal discovery from interventional data\".\n3) Better re-structure the paper writing\nOverall, the paper is very dense and lacks intuitions. Regarding identifying the latent variables (or at least, detecting the number of latent variables), one sentence in line 245 is very interesting: \"Proposition 4.1 suggests that we assign a latent variable to each maximal valid subset\", I think this has a potentially nice intuition about identifying latent variables by using dependencies among the observational variables. I suggest the authors to provide an overview, with intuitions about the key idea, rather than defer then to Section 4 and 5.\n4) claim of Example 1 is improper.\neven with unknown interventional target, and by intervening once, we can still recover the orientation between X1 and X2. you can further checking if there is marginal independence between X1 and \"whether the intervention is performed\", and X1 and \"whether the intervention is performed\", this information can further help you to identify the causal direction. you can check more details from [1].\n\n[1] Mooij, J. M., Magliacane, S., & Claassen, T. (2020). Joint causal inference from multiple contexts. The Journal of Machine Learning Research, 21(1), 3919-4026.\n\nThe second concern is the weakness of experiment.\nas the author pointed, \"Compared to these existing works, our focus is on nonparametric models with unknown, hard, single-node interventions on the latent variables\", I think this is a clear configuration, and we can certainly conducts comparison with other SOTAs (such as using parametric approach)\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thorough review and suggestions!\n\n**“The most concern from my side is that what this paper is telling lacks real-world relevance. this makes me doubt if this work can be helpful for practical usage.”**\n\nFor example, one practical application is topic models. In topic models, the pure child assumption is fairly common [a], which is strictly stronger than assumptions 1(c) and 1(d) (Remark 4.2). And we show in the paper (Section 4.3) how to identify causal graphs under the pure child assumption. Applying our results to image data is a very interesting future direction. \n\n[a] Arora, Sanjeev, et al. \"A practical algorithm for topic modeling with provable guarantees.\" International conference on machine learning. PMLR, 2013.\n\n**“justification of the required assumptions many assumptions used in this work are untestable.”**\n\nThis paper studies the theoretical limit of nonparametric identifiability of latent causal graphs, and in Appendix C we show that our assumptions are tight. We feel like understanding the capabilities and limits of these assumptions can build the foundation for future work on CRL. On the other hand, our empirical results (section 6) show that even when our assumptions are not enforced, we can still get approximate recovery with low error rate as long as graphs are generated with sparsity. \n\nFinally, the complete family of targets is needed to get exact graph recovery (section C.4). One can easily relax this assumption to get partial identification (i.e., lumping some latent variables together). \n\n**Better re-structure the paper writing**\n\nThanks for the suggestion. You’re right that the intuition behind our proof to identify latent variables is to use dependencies among the observational variables. By examining what’s invariant and what’s changing, one can recover the latent graph.\n\n**Claim of Example 1 is improper. even with unknown interventional target, and by intervening once, we can still recover the orientation between X1 and X2. you can further checking if there is marginal independence between X1 and \"whether the intervention is performed\", and X1 and \"whether the intervention is performed\", this information can further help you to identify the causal direction. you can check more details from [1].**\n\nTypically, one needs additional information to identify the interventional target. For instance, [b] uses direct I-faithfulness. Once the interventional target is known, then one can solve the isolated edge orientation problem. For JCI, could you clarify what you do mean by “whether the invention is performed”? If you meant the observed context variables, then one still needs to have observed context variables that satisfy assumptions on how system variables and context variables interact. \n\n[b] Squires, Chandler, Yuhao Wang, and Caroline Uhler. \"Permutation-based causal structure learning with unknown intervention targets.\" Conference on Uncertainty in Artificial Intelligence. PMLR, 2020.\n\n\n**“Comparison with other SOTAs”**\n\nOur paper studies the general setting that allows arbitrary nonlinear transformation between latents and observed and among latents. It is likely that other methods utilizing functional assumptions like linearity can perform better if the functional form is known. Since our paper is primarily theoretical, our experiments are just a proof of concept to demonstrate that even for nonlinear transformations one can still recover the measurement model with low error. \n\n\n**“Can we give a definition of clique in main body?”**\n\nThanks for the suggestion. We’ll add the definition to the main body. A clique is a subgraph where every pair of distinct vertices are adjacent. \n\n**“I want to know, if the additional assumptions are included, how much further we can achieve?”**\n\nWith additional assumption like direct I-faithfulness [b], one can identify isolated edges. In this paper, we want to study nonparametric identifiability with minimal assumptions. Even without assumptions like direct I-faithfulness, intervention **can** still introduce detective changes. This is why all the non-isolated edges can be oriented (Theorem G.7). Our results demonstrate how to orient non-isolated edges without making additional assumptions. Thus, additional assumptions are not totally necessary. \n\n"}, {"review_id": "RjKCcOaBX0", "reviewer": "Reviewer_tfcU", "summary": "- The paper studies causal representation learning, or more precisely the identification of the causal graph between observed and latent variables, from interventional data with unknown intervention targets.\n- Its main contribution is an identifiability result for the causal graph. This theorem makes no assumptions on the functional form of the causal model or the mixing function, but is based on several graphical requirements. In various ways, the paper requires that different latents affect different sets of observed variables.\n- The authors spend a large part of the paper discussing these assumptions and providing sufficient conditions for them.\n- In the end, they also briefly demonstrate their algorithm on toy data.\n- Unlike most of the CRL literature, the paper does not study the identification of the latent *variables*. The authors delegate this task to \"existing work, since one can [...] use deep latent-variable-models to infer the latent distributions from the latent structure\".\n\nI have read the author's rebuttal. They have addressed my questions clearly.", "questions": "- In line 150, the authors stress that they consider the *set*, not the tuple, of interventional distributions. What motivates this choice?\n- Is Assumption 1(b) the same as the common assumption of faithfulness?\n- In Theorem 3.4, what does \"using CI information only\" mean exactly? Could we get stronger results when using the full distribution(s), not just the conditional independence patterns?\n- In Theorem 3.4, what does \"G is identifiable\" mean exactly? Identification up to a graph isomorphism (so for instance allowing for a permutation of the latent variable)?\n- In line 227, what is meant by \"sequel\"?\n- If we had a dataset with multi-target interventions in addition to the single-target interventions, would that allow for stronger statements? Perhaps we could relax the requirement of not having imaginary subsets?\n- I'm a bit confused why we can have identifiability of the latent graph except for the direction of isolated edges $a \\to b$ . It seems that any other isolated chain, like $a \\to b \\to c$ disconnected from all other latents, would be similar. Could the authors provide some intuition for why this latter graph can be identified, while the isolated edge cannot?\n- Is the interventional MEC a subset of the IEC?\n- In line 372, what are m and n?", "limitations": "- The authors are very clear about the assumptions of their theoretical results.\n- Nevertheless, I believe it deserves more discussion whether these assumptions fit realistic problems (see above).", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "- It is great that the authors can prove identifiability from observational, unlabelled data, and without functional assumptions. This makes the results potentially quite practical, barring limitations from the graphical assumptions (see below).\n- While I have not been able to check the proof in detail and I do have some questions (see below), I overall believe that the key results are correct.\n- The paper is very thorough, with precise statements, extensive discussion, useful examples, and thorough appendices. There is a lot in here that may be useful beyond the concrete identifiability result.\n- It is also extremely well-written, really a joy to read. I appreciate the frequent signposting. Great job!", "weaknesses": "- Different from virtually all other CRL works, the authors choose to focus *only* on the identifiability of the causal structure and entirely disregard the identification of the causal variables.\n\t- Arguably, in most applications of CRL, the latent variables are at least as important as a result.\n\t- The strategy of solving the structure learning problem first and delegating the variable identification to a latent-variable model makes sense, but deserves a discussion that goes beyond the two lines that the authors have reserved for it.\n\t- Could you perhaps quote or sketch what kind of guarantees on the identification of the latent variables one can expect when following such a two-step procedure?\n- As with most of the CRL literature, a key question is whether the assumptions are too unrealistic or too difficult to verify to make the results useful beyond pure academic curiosity. I am particularly worried that assumptions 1(c), 1(d), and the lack of imaginary subsets do not apply to typical CRL settings.\n\t- For instance, I find it difficult to imagine these assumptions applying to any of the systems sketched in lines 18-20 in the introduction. Could the authors discuss this and provide perhaps some semi-realistic examples of systems that satisfy them?\n\t- Negative results are equally valuable though, and I appreciate the counter-examples that show the lack of identifiability when these assumptions are violated.\n- I am also concerned about the restriction to maximal measurement models.\n\t- This seems to be a bit at odds with Okham's razor: if multiple models explain the data, why should we focus on the most complex model that explains the data? Should we not identify the family of all models, or the simplest model?\n\t- It would be great if the authors could comment on how strong this assumption is and in what kind of systems they expect it to be satisfied.\n- The experiments are very limited and really just a minimal proof of concept.\n\t- It would make the paper stronger if the authors would design experiment that test whether the approach scales to interesting problems and that test how robust the approach is to violations of the assumptions.\n\t- In addition, a comparison to other methods (for instance on problems that satisfy  functional assumptions made by other papers) would be interesting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the detailed comments! We're glad you find the paper a joy to read.\n\n**“Focus only on the causal structure”**\n\nWe completely agree that learning latent distributions is important! At the same time, without causal structure, latent distributions may not be interpreted causally, and therefore we suggest that gaining an understanding of latent causal structures is of equal importance. In some sense, learning the structure is necessary: To understand causal relations, one needs to know what happens when we intervene on these learned features. Therefore, this paper studies the equivalently important problem of structure learning and we believe that it lays the foundation for future research on CRL.\n\nIn this sense, since most related work focuses on the latent distribution, we are studying a complementary but equally important aspect: What are the minimal conditions needed to recover the latent causal structure? We believe that understanding these two problems (structure vs representations) separately is crucial to understanding what assumptions matter, why they matter, and for which aspects of the problem they are needed.\n\n**“The assumptions are too unrealistic or too difficult to verify”**\n\nPlease see the global response.\n\n**“maximal measurement models”**\n\nMaximality helps uniquely identify latent causal graphs as in many cases, there could be multiple measurement models that can explain the observed interventional distributions but only one maximal measurement model (Appendix D). Such construction is similar to the definition of maximal ancestral graphs (MAGs, see L180-181). See [c] for more details on MAGs, which are standard graphical models for incorporating latent variables. Intuitively, a conditional independence statement could be explained by multiple combinations of missing edges. We choose the simplest explanation with the least amount of missing edges. \n\n[c] Richardson and Spirtes. \"Ancestral graph Markov models.\" The Annals of Statistics (2002).\n\n**“The experiments are very limited”**\n\nPlease see the global response.\n\n**“set vs tuple”**\n\nThis is a good observation! Because we allow interventional distributions to be the same under different interventions and the interventional targets are unknown, sampling from the same interventional distributions could be viewed as the same. Thus, we consider sets instead of tuples since this allows for a more realistic setting where different interventions are indistinguishable. Moreover, learning from a tuple is easier than learning from a set, since one can reduce the tuple problem to set problem because one can create a set from a tuple by removing duplicates. Thus, there is no loss of generality in our setting.\n\n**“Assumption 1(b) and faithfulness?”**\n\nAssumption 1(b) is substantially weaker than the usual faithfulness assumption (L166-168 and detailed discussion in appendix C.1). Here, we only consider pairwise, marginal independencies between observed variables. Ordinary faithfulness includes full conditional independencies of arbitrary order including latent variables.\n\n**“In Theorem 3.4, what does \"using CI information only\" mean exactly?”**\n\nYes, one could use more information about the distributions to potentially orient more isolated edges, and this is a natural direction for future work. Our results imply that this will require additional assumptions. One example is direct I-faithfulness [c], which uses distributional info (L368). \n\n[c] Squires, Chandler, Yuhao Wang, and Caroline Uhler. \"Permutation-based causal structure learning with unknown intervention targets.\" Conference on Uncertainty in Artificial Intelligence. PMLR, 2020.\n\n**Confusion about isolated edges a->b**\n\nYour intuition is right. a->b->c cannot be oriented either. Note that a->b is an isolated edge. This is because the only parent of b is a and c is a child of b (Definition 3.3). Thus one can reverse it such that we have a<-b->c. Now, b->c is an isolated edge, one can reverse it again to get a<-b<-c. Thus a->b->c and a<-b<-c are in the same IEC because there exists a sequence of isolated edge reversals between them. Theorem 5.3 shows that these two graphs are indistinguishable using CI information only. \n\nWe apologize for the confusion and feel like there is a potential misunderstanding due to the naming of “isolated edges”. An isolated edge X->Y does not mean that X, Y are disconnected from all other nodes. In fact, X and Y can still have outcoming edges and X->Y is not just an isolated connected component. For instance, in your example, a->b is an isolated edge but is connected to other edges as well.\n\n\n**“In Theorem 3.4, what does \"G is identifiable\" mean exactly? Identification up to a graph isomorphism (so for instance allowing for a permutation of the latent variable)?”**\n\nThis is correct. Up to different labeling of the latent variables (graph isomorphism). But such reordering is trivial because of assumption 1(c). Different latent variables will have different sets of observed children. Thus one can use the children set to uniquely identify different latent variables.\n\n\n**“If we had a dataset with multi-target interventions in addition to the single-target interventions, would that allow for stronger statements? Perhaps we could relax the requirement of not having imaginary subsets?”**\n\nThis is a good question! Extending our theory to multi-target interventions is an exciting direction. Having access to multi-target interventions would definitely help relax assumption 2 and maybe allow for stronger results. \n\n**“Is the interventional MEC a subset of the IEC?”**\n\nInterventional MEC is a bit different from IEC. IEC is for unknown interventions and interventional MEC is for known interventions.\n\n\n**“In line 372, what are m and n?”**\n\nSorry for the confusion. We define m and n as the number of latents and observed respectively on line 103. We will clarify it again in the experiment section. \n"}, {"review_id": "21mLQteBLy", "reviewer": "Reviewer_Yp1n", "summary": "The paper studies the problem of recovering causal relationships under the measurement model where there are latents but no direct causal edges between observed covariates. The authors introduced two graphical concepts -- imaginary subsets and isolated edges -- and show how they relate to sufficient conditions for recovery (under some additional assumptions). The assumptions are discussed at length in the appendix and a two phased recovery algorithm is proposed.", "questions": "Caption for Figure 1:\nFrom my understanding of Definition 3.2, imaginary subsets have to be maximally valid. Why is $\\{X_5, X_6\\}$ maximal?\n\nSuggestion for Figure 1:\nIn the additional page that comes with paper acceptance (if this gets accepted), it would be nice to include a picture of D(P), mention that $\\Omega_P = \\\\{ \\\\{1,2,5,6\\\\}, \\\\{3,4,5,6\\\\} \\\\}$, and then refer to Fig 1 on Lines 146 and 200.\n\nMissing assumption:\nThis work implicitly assumes infinite samples / population regime / access to a d-separation oracle, right? Please state this explicitly.\n\nAssumption 2:\nThis assumption feels very strong... For example, such an assumption trivially solves the causal graph discovery problem in the causal sufficient setting (w/o latents but observed covariates have edges amongst themslves) if we have access to all $n$ interventional essential graphs. I understand that the model studied here has latents, but then the measurement model seems to also simplify things a lot. Why does Assumption 2 not immediately trivialize the entire (or part of the) recovery objective? For example, if there is no repeated interventional distributions (i.e. $|\\mathcal{I}| = m+1$), then isn't Line 223 trivial? I understand the discussion of this assumption in the appendix (Line 651 should be emphasized in the main text), but it seems that, in the worst case, we just \"lump\" all downstream latents together. What am I missing? What is the subtlety that I am not getting?\n\nLine 184, footnote 1:\nDo you mean \"In other words, removing any more...\" instead of \"In other words, adding any more...\"? We can always add redundant edges while maintaining the underlying model, right? e.g. a clique can encode any arbitrary distribution, including the product distribution.\n\nTheorem 3.4:\nIs there a \"necessary\" counterpart to this result? For instance, I was under the impression that existence of imaginary subsets makes G unidentifiable. If that is the case, you should perhaps write something like \"G is identifiable if and only if no imaginary subsets\" for (a). Characterizations like these would greatly strengthen the paper's contribution.\n\nLine 250, and also appendix E; Misconception about maximality:\nI think I have a misconception about maximality, which is affecting my understanding of the paper's correctness. Why is $\\{X_1, X_2\\}$ a maximal valid subset if $\\{X_1, X_2, X_5\\}$ is one? Doesn't the fact that the former subset being a proper subset of the latter make it *not* maximal? Could you kindly resolve my misconception? Thanks! (I will revise the soundness score and overall rating accordingly.)\n\nLine 377:\nI am unsure what the last sentence is trying to imply. Could you clarify? I have the following guesses (all of which could be wrong):\n- Are the theoretical assumptions unnecessary?\n- Did you just \"get lucky\" with the experiments?\n- Are you suggesting that the assumptions are not required for the class of models which you have ran experiments on?\n\nTable 1:\nHow are the errors split across $G_B$ and $G_H$? From my understanding, the algorithm to recover $G_H$ crucially depends on $G_B$ being correctly recovered, right? It is unclear to me what we can conclude if $G_B$ was recovered with errors and then subsequently used to recover $G_H$ --- how do the errors propagate? Can you say something about it in theory?\n\nFigure 2 and 3:\nIsn't Figure 3 just Figure 2?\n\nExample 12:\nWhy does Figure 1 satisfy assumption 3? $H_1$ and $H_2$ have no pure child.", "limitations": "Nil.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written and easy to follow in general. I also appreciate the in-depth discussion of the assumptions.", "weaknesses": "Assumption 1(d) seems redundant and I think it is implied by assumption 1(c); rewriting it in terms of a lemma or consequence of assumption 1(c) would strengthen the paper and reduce the number of assumptions required. Consider the following argument: Fix any two latents $H_i$ and $H_j$. By assumption 1(c), $H_i$ has a child $X_i$ that is not a child of $H_j$, and $H_j$ has a child $X_j$ which is not a child of $H_i$. We now consider the contrapositive of 1(d). Suppose $X_i$ and $X_j$ are d-connected. In the measurement model, this means that there is a path $X_i \\gets H_i - \\ldots - H_j \\to X_j$ which has no colliders. Then, this same path is a witness to $H_i$ and $H_j$ being d-connected.\n\nI am unsure how interesting Definition 5.2 on Isolated equivalence class (IEC) is. I do not think it is fair to compare its significance to Chickering's \"covered edge reversal\" characterization, which I believe is significantly more subtle and interesting. For instance, while there exists a sequence of covered edge reversals (say edge $e_1$, then $e_2$, then $e_3$, ..., then $e_r$) between any two DAGs in the same Markov equivalence class (MEC), the edges may actually NOT be covered edges midway through the transformation and one cannot arbitrarily reverse the set of edges $\\{e_1, \\ldots, e_r\\}$ in any ordering whilst ensuring that we always get a DAG from the same MEC. Chickering further gives a constructive algorithm which tells us how to find this sequence $(e_1, \\ldots, e_r)$. In contrast, IEC seems trivial since it involves a union of disjoint edges, where the size of IEC is always 2^(number of isolated edges) and every edge can be reversed at any point in time.\n\nExperimental details are lacking: Section 6 is short and there is nothing in the appendix about the experiments. It is hard to judge or appreciate any empirical contribution. I feel that the authors should have just focused on presenting this work as a theoretical contribution (which I think is already sufficient on its own, modulo the questions below).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the questions and suggestions!\n\n**Assumption 1(d)**\n\n1(d) is not implied by 1(c). In your example, $X_i$ and $X_j$ could be connected via other hidden variables. Even when $H_i$ and $H_j$ are disconnected,  $X_i$ and $X_j$ might still be connected. We give such an example in Appendix C.3. In particular, consider Fig 5, $X_1$ is not a child of $H_2$ and $X_3$ is not a child of $H_1$. However, under the intervention target $H_2$, $X_1$ and $X_3$ are still d-connected via parent $H_3$.\n\n**IEC**\n\nApologies for any confusion. There seems to be a potential misunderstanding regarding the concept of isolated edges. Despite what the name might suggest, an isolated edge X->Y does not mean that X, Y are disconnected from all other nodes. In fact, X and Y can still have outcoming edges (definition 3.3) and X->Y is not just an isolated connected component. So IEC doesn't just involve a union of disjoint edges. For example, consider a graph of three variables: A, B, C with two edges A->B, A->C. These two edges are both isolated edges but not disjoint. In fact, one can reverse edge A->B to be B->A. In that case, A->C is no longer an isolated edge. Therefore, similar to MEC where the edges may actually NOT be covered edges midway through the transformation, isolated edges can have the same problem. \n\nWe agree that the characterization of isolated edges is simpler than covered edges because isolated edges are special cases of covered edges. On the other hand, the introduction of IEC is used merely as a tool to characterize the unorientability of isolated edges (theorem 5.3 and G.7) and is not intended to suggest that this is deeper or more fundamental than the MEC.\n\n**“Experimental details”**\n\nWe will provide more details on experiments in the updated version. Some additional details include that the weights are generated by uniformly sampling from $[-2, -0.5] \\cup [0.5, 2]$ and the variances are set to 1. More details can also be found in the codebase we included in the supplementary files. \n\n**“Misconception about maximality”**\n\nAgain, we apologize for any confusion: The definition of a maximal valid subset clearly states that X’ and X’’ must be contained in the *same* clique in the UDG. A maximal valid subset X’ is maximal in the sense that for any clique containing X’ there does not exist X’’ that’s also in the same clique and is a superset of X’. In other words, X’ is maximal if its existence cannot be completely explained by another subset. We apologize for the confusion, however, upon inspecting our definitions, everything is correct as stated. We will add a clarification of this point in the camera ready. See below as well for a correction to Figure 1.\n\n**Why is X_5, X_6 maximal?**\n\nThanks for pointing this out! In fact, as reported in Figure 1, {$X_5, X_6$} is not maximal. Thanks to your careful attention, we realized there is a mistake in Figure 1 that needs to be corrected. The original Figure 1 was simplified for the purpose of providing a clear and easily understandable demonstration, but in the process of simplifying the DAG, the maximal valid subsets became slightly different than what the caption states. \n\nIn the attached pdf file, we present a modification to Fig 1 that corrects the issue and preserves all the statements about maximal valid subsets and imaginary subsets. We have also taken your advice to include UDGs under each intervention. \n\nTo demonstrate why both {$X_1, X_2$} and {$X_1, X_2, X_5$} can be maximal valid subsets, let’s refer to the updated figures in the pdf file. Figure 2(c) in the pdf file shows that under intervention target $H_4$, there are three maximal cliques: {$X_1, X_2, X_4$}, {$X_1, X_2, X_5$}, {$X_3, X_5, X_6$}. Because {$X_1, X_2, X_4$} contains {$X_1, X_2$} but not {$X_1, X_2, X_5$}, these two sets can both be maximal without contradicting the definition. \n\n\n**Missing assumption**\n\nThis is stated at L49: “Given a set of interventional distributions”, as opposed to samples. Of course, the population regime is equivalent to assuming distributions as input, which is standard in the literature when discussing identifiability. Since the goal of this paper revolves around identifiability, we leave estimation as an intriguing future direction. We’ll make these points clear in the updated version.\n\n**Assumption 2**\n\nThis is a common assumption and in fact, it is an open question whether or not this can be relaxed [a-b]. [a] also shows that this assumption is necessary (Section 3.3 of [a]).\n\nMoreover, compared to classical work on interventions in graphical models, the current literature on causal representation learning (including our submission as well as [a,b]) considers a strictly harder setting since the interventions are both latent and unknown. Since the intervention target is latent, we only have access to partial information (observed variables) regarding the effect of interventions. And since the intervention target is unknown, compared to the known intervention target, we additionally have the unorientability problem of isolated edges which is discussed in section 5.2 (L357).\n\n[a] Seigal, Squires, Uhler. \"Linear causal disentanglement via interventions.\" arXiv preprint arXiv:2211.16467 (2022).\n\n[b] Varici, Burak, et al. \"Score-based causal representation learning with interventions.\" arXiv preprint arXiv:2301.08230 (2023).\n\n**Line 377** \n\nPlease see the global review. \n\n**Line 184, footnote 1**\n\nSorry for the confusion. What we meant is that adding edges until we cannot add more without changing (i.e. adding _or_ removing) the conditional independence statements. This notion of maximality is the same as in maximal ancestral graphs (MAGs), as mentioned on L180. See [c] for more details on MAGs, which are standard graphical models for incorporating latent variables. We have double-checked our definition and can confirm it is correct as stated.\n\n[c] Richardson and Spirtes. \"Ancestral graph Markov models.\" The Annals of Statistics (2002).\n"}]

Author rebuttal:
We want to thank all the reviewers for their thoughtful comments and suggestions! We also want to address some common questions. 

**Assumptions**

Two reviewers have questions about the real-world relevance of our assumptions (bZuh, tfcU). First of all, we completely agree with Reviewer tfcU that negative results are equally valuable. One of the main objectives of this paper is to study the theoretical limits of nonparametric identifiability of latent causal graphs. The fact that our assumptions are tight (L164-176 and Appendix C) is crucial: Any hope of relaxing these assumptions will require making alternative assumptions. We show what is possible and impossible under this setting and why additional assumptions are needed. 

In particular, we show in the paper why assumptions 1(c) and 1(d) are necessary for our problem (appendix c.2 and c.3). A practical example where such assumptions might be satisfied is topic modeling. In topic modeling, one often assumes the existence of pure children (or anchor words) [a]. But our 1(c) and 1(d) assumptions are strictly weaker assumptions than the pure child assumption (Remark 4.2) and we show how to identify under the pure child assumption even with imaginary subsets (section 4.3, theorem 4.8).

[a] Arora, Sanjeev, et al. "A practical algorithm for topic modeling with provable guarantees." International conference on machine learning. PMLR, 2013.

**Experiments**

Three reviewers have questions about limitations of experiments (3v5g, bZuh, tfcU), although Reviewer 3v5g does agree that the paper is “interesting from a theoretical perspective”. We also appreciate Reviewer Yp1n for acknowledging that the theoretical contribution of this paper is “already sufficient on its own”.

Since our paper is primarily theoretical, the purpose of our experiments is simply to verify the theory, illustrate that it is easy to implement, and serve as a proof of concept, as Reviewer tfcU has suggested. It is likely that other methods which use functional assumptions might outperform our method if the additional functional information (i,e., linearity) is available. Nevertheless, our theory is more general and applies to arbitrary nonlinearities. 

We also want to apologize to Reviewer Yp1n for the confusion at L377. To clarify, we simply mean that we did not enforce Assumptions 1 and maximality strictly in the experiments, and in spite of this, the method still performs well. We will modify this sentence to say: “The empirical results show that our method is robust at recovering DAGs with low errors when the graphs are generated with sparsity.” We suspect this is a combination of two factors: 1) The simulated DAGs are sparse, which intuitively suggests they are likely (but not guaranteed) to satisfy Assumption 1, and 2) There is some mild robustness to misspecification. Since we know the assumptions cannot be relaxed, we know that violations of the assumptions must lead to nonidentifiability, however, the _severity_ of nonidentifiability could be mild (we stress that we do not have any justification of this beyond the encouraging results of the simulations). This is an interesting observation we look forward to investigating more deeply in future work.


Meta-review: This work addresses the rapidly blossoming theory of identifying latent causal models, considering the setting with nonparametric assumptions. In the rebuttal, the concerns of the reviewers were addressed, so I recommend acceptance. Please incorporate the changes requested by the reviewers in the camera ready revision.
Decision: Accept (poster)