Causal Structure Recovery with Latent Variables under Milder Distributional and Graphical Assumptions
Authors: Xiu-Chuan Li
Kun Zhang
Tongliang Liu
Venue: ICLR 2024 poster (2024)
Keywords: causal discovery
latent variables
Primary area: causal reasoning

Abstract: Traditional causal discovery approaches typically assume the absence of latent variables, a simplification that often does not align with real-world situations. Recently, there has been a surge of causal discovery methods that explicitly consider latent variables. While some works aim to reveal causal relations between observed variables in the presence of latent variables, others seek to identify latent variables and recover the causal structure over them. The latter typically entail strong distributional and graphical assumptions, such as the non-Gaussianity, purity, and two-pure-children assumption. In this paper, we endeavor to recover the whole causal structure involving both latent and observed variables under milder assumptions. We formulate two cases, one allows entirely arbitrary distribution and requires only one pure child per latent variable, and the other requires no pure child and imposes the non-Gaussianity requirement on only a subset of variables, and they both avoid the purity assumption. We prove the identifiability of linear latent variable models in both cases, and our constructive proof leads to theoretically sound and computationally efficient algorithms.

Published as a conference paper at ICLR 2024
CAUSAL STRUCTURE RECOVERY WITH LATENT VARIABLES UNDER MILDER DISTRIBUTIONAL AND GRAPHICAL ASSUMPTIONS
Xiu-Chuan Li!
Kun Zhang Tongliang Liu'
'Sydney AT Centre, University of Sydney
Cammeii Mellon University
"oohaeed bin Zayed University of Artificial Intelligence
ABSTRACT
Traditional causal discovery approaches typically assume the absence of latent variables, a simplification that often does not align with real-world situations. Re- cently, there has been a surge of causal discovery methods that explicitly consider latent variables. While some works aim to reveal causal relations between ob- served variables in the presence of latent variables, others seek to identify latent variables and recover the causal structure over them. The latter typically entail strong distributional and graphical assumptions, such as the non-Gaussianity, pu- rity, and two-pure-children assumption. In this paper, we endeavor to recover the whole causal structure involving both latent and observed variables under milder assumptions. We formulate two cases, one allows entirely arbitrary distribution and requires only one pure child per latent variable, and the other requires no pure child and imposes the non- aon-Gausiianty requirement on only subset of variables, and they both avoid the purity assumption. We prove the identifiability of linear latent variable models in both cases, and our constructive proof leads to theoreti- cally sound and computationally efficient algorithms.
INTRODUCTION
Understanding causal relations is a fundamental element of artificial intelligence (Schölkopf et al., 2021; Schott et al., 2018; Dominguez- Olmedo et al., 2022; Wang et al., 2021: Yao al., 2021; Lin et al., 2023; Huang et al., 2023; Hong et al., 2024). The gold standard is to use randomized experiments, but this is usually too expensive or even impractical. Therefore, there has been sig- nificant attention towards revealing causal relations through analysis of observational data, com- monly known as causal discovery. Most traditional approaches focus on the situation without latent variables. such as constraint- PC algorithm (Spirtes et al., 2000), score- based Greedy Equiv- alence Search (GES) (Chickering, 2002), and some Functional Causal rithms (Shimizu et al., 2006; 2011; Hoyer al., 2008a; Zhang & Hyvarinen, 2009; Peters et al., 2014; Mooij et al., 2016). However, in complex systems, we typically fail to collect and measure all task-relevant variables. Many algorithms have been proposed handle the situation with latent vari- ables, such as constraint-based Fast Causal Inference (FCI) (Spirtes et al., 1995), score-bases based Greedy PAG Search (GPS) (Claassen Bucur, 2022), and also some FCM-based algorithms (Hoyer al., 2008b; Tashiro et al., 2014; Salehkaleybar et al., 2020; Maeda & Shimizu, 2020; Cai et al., 2023).
(FCM-)basse) algo-
While the above approaches can reveal causal relations between observed variables with or without latent variables, they cannot identify latent variables. let alone infer their causal relations. However, researchers may care more about the causal structure over latent variables in many cases (Silva et al., 2006). Assuming linear causal relations and no observed variable being the parent of any latent one in the underlying causal graph, many existing works employed sparsity of causal edges to facilitate latent causal structure learning. For instance, some early works (Silva et al., 2006; Kummerfeld & Ramsey, 2016) have proven that latent causal structure can be recovered under the three-pure pure- children assumption that each latent variable has at least three pure children (an observed variable O is called a pure child of a latent variable L if O has no child and only one parent L, see Definition 2.). Others (Cai al., 2019; Xie al., 2020; 2022) have relaxed the three-pure-children assumption to

---

Published as a conference paper at ICLR 2024
0
O.
On
(a) G1: 1. has only one pure child and cach noise has arbitrary distribution.
(b) G2: 122 has no pure child and only noises of red variahles non- non-Gaussian.
Figure 1: The whole causal structure can be recovered in both the above cases where none of the purity, non-Gaussianity, and wwo-pure-children assumption holds.
the two-pure-children assumption that each latent variable has least two pure children. However, they entailed two additional assumptions: the purity assumption that there is no causal edge between observed variables and the non- Gaussianity assumption that noises of all variables are non-Gausiian. On this basis, Xie et al. (2023b) made a further step by eliminating the purity assumption.
In the real world, since some variables might have nearly Gaussian distributions (Lyon, 2014), the non-Gaussianity assumption might not hold. Besides, some observed variables may directly influ- ence others, violating the purity assumption, e-g.. in financial markets, while stock returns may be confounded by some economic or political factors, they may also be causally related (Adams al., 2021). Moreover, the occurrence of pure children will become less frequent without the purity as- sumption. Finally, when observed variables also causally related, we usually want the whole causal structure involving both latent and observed variables rather than only the latent causal struc- ture. Therefore, endeavor recover the whole causal structure in the case where none of the non-Gaussi,,,ty, purity, and two-pure-children assumption holds.
Recovery of the whole causal structure requires causal relations between any two variables. Existing works typically identify a latent variable by detecting its pure children from observed variables, which be achieved under strong graphical and distributional assumptions. We notice that previously used assumptions are sufficient but not necessary for detecting the pure children, and some special impure children can play a similar role as pure ones. Based on this, we formulate two sets of assumptions which are milder than previous ones. They both allow causal edges between observed variables, one allows entirely arbitrary distri- bution and requires only one pure child per latent variable, and the other requires pure child and imposes the non-Gaun -aussaassyyytty requirement on only subset of variables, two illustrative examples are shown in Figure 1. We prove identifiability of latent variables under either set of assumptions, and corresponding algorithms directly derive from our constructive proof. After this, we perform some pre-pro prepoeosssing procedures and then modify the PC-MIMBuild (Silva et al., 2006) which has already been proved asymptotically correct to infer causal relations between any two variables.
first identify latent variables and then infer
In summary, main contributions are three-fold. First, introduce two sets of milder assump- tions, both of which avoid the non-Gaussianity, purity, and two-pure-children assumption simulta- neously. Second, we prove that the whole causal structure of linear latent variable models can be recovered under either set of assumptions. Third, from our constructive proof, we derive algorithms recover the whole causal structure from purely observational data, which are both theoretically sound and computationally efficient.
2 PRELIMINARIES
In this paper, we focus on linear latent variable models with graph structure & = (V, which is directed acyclic graph (DAG), V = L U O where L {Li)i and 0 = {0,), respectively denote the set of latent and observed variables. In the causal graph G, each variable follows:
L;=
b būL; + EL, O () (14)
Σ
Σ
CjLi+
Σ
dj + t
(I)
(O,
O
where Paf. (V), Pag. respectively denote the set of latent parents and observed parents of V in G. (V) U & Pa (ag
UyevPa (V), and C (-), Nei (.) respectively denote children and neighbors. C Cj. d respectively denote the causal strength from L, to L,, from L, to O, from O to O, E,, and EO, refer to noises, which are continuous and independent of any other noise. Without loss of generality, suppose that each variable has mean.
Moreover, (v* = Pa (V)
2

---

Published as a conference paper at ICLR 2024
Definition 1. (linear latent variable model) A causal model with graph structure G (V, where G is DAG and V LUO is called a linear latent variable model if
1. each variable follows Equation (1):
2. the distribution over V is both Markov and faithful G;
Equation (1) implies that all causal relations are linear and no observed variable is parent of any latent one, both of which have almost become standard assumptions of latent causal structure learning since proposed by the seminal work (Silva et al., 2006), although very few works avoid them at the expense of other significant limitations. For instance, Kivva et al. (2021) allow non-linearity, but they assume that all latent variables are discrete. By the way, some of out theoretical results can still generalize to certain special nonlinear cases, please see Appendix C.I for more details.
Definition 2. (Pure child) An observed variable O E O is called pure child of latent variable L E L if Pa (O) = } and Ch (0) = O." Example 1. In Figure l(a). L1 has 3 pure children: O,.02, O3; L2 has 2 pure children: O4, Os: L3 has only pure child O10-
Definition 3. (Pure pair) An observed pair {01, O2] c 0 is called a pure pair if 3L E L s.t. both Or and O2 are pure children L.
Definition 4. (Pseudo-pure pair) An observed pair {0 02] O is called pseudo-pure pair if (02) (h2)
3/. E L (a) Pag(O:) Ch& (0:) (02), 9 (02) O1,, Ch9
or (b)
(O2) = (L., Ch& (h2) (01), (0:)))(00)))) (1. and Ch (01) = 0.
Definition 5. (Generalized pure pair) An observed pair 10 02) C O is called a generalized pure pair if it is either a pure pair or a pseudo-pure pair.
Example 2. In Figure I(a), there are 4 pure pairs: {01, 02), (0,, 02), (02, 03), (O4, Os), pseudo-pure pairs: (1), (Og, 09), {011, 012), and hence 7 generalized pure pairs.
Xie al. (2023b) suggest that with only the two-pure-childeee assumption, latent variables cannot be fully identified. The problem is that a pseudo-pure pure pair may be falsely identified as a pure pair, once this happens, a single latent variable will be split into multiple ones, ex- ample shown Figure 2. fact, pseudo- pure pairs are not uncommon in the real world, e.g., in psychometric questionnaires, "insom- nia" and "concentration" might be a pseudo- pure pair because the former directly influences the latter and they are also confounded by a latent variable "depression". To handle this problem, they further introduce the non- non-Gaussianity assump- tion which enables discrimination between pure and pseudo-pure pairs, while such ambiguity can also be avoided with the previously used phree-eure-childrenn assumption (Kummerfeld & Ramsey, 2016). However, both the non-Gaussianity and three-pure-ee qure-children assumption are only sufficient but necessary conditions. Besides, we find that pseudo-pure pairs may even benefit causal dis- covery because they can play similar role as pure pairs. This motivates us to investigate the case where none of the non-Gaussianity, purity, and woopuure-hhldrren assumption holds.
a
(b)
Figure 2: With only the two-pure-childre sumption, the structure in (a) cannot be discrim- inated against (b).
3 IDENTIFYING LATENT VARIABLES
To recover the whole causal structure, the first step is to identify latent variables. To this end, we formulate Assumption 1, 2, 3 at the outset of Section 3.1, 3.2, 3.3 respectively. Assumption 1 is preliminary assumption enabling partial identification of latent variables, which can be achieved by Algorithm 1. On this basis. if Assumption or Assumption 3 is also satisfied, latent variables can be fully identified. Taking the output of Algorithm as the input, Algorithm 2 and 3 can accomplish this goal under Assumption and respectively.
3.1 PARTIALLY IDENTIFYING LATENT VARIABLES
Assumption 1. (a) VL E L, L has at least one generalized pure pair as children, (b) VL E L, Neif. (L) # 0. and (c) YO e O, Pf = 0, then (Ch@ (0)) 2 3.
Some recent works such Xie et al. (2022) focused on the scenario where pure children may still be latent, which is out of scope. We discuss the relation between these works and ours in Section 5.
3

---

Published as a conference paper at ICLR 2024
Algorithm/ 1: Partially identifying latent variables.
Input: Observed variable O
Output: Candidate variables OC generalized pure pairs S, purity indicator function pure
Find all candidate variables based Definition 6.
Find all generalized pure pairs based on Theorem 1.
Identify many pure pairs possible based on Lemma
Assumption ((a) indicates that latent variable with a pseudo-pure -ure pair as children can have no pure child. Assumption 1(b) has already been used by previous works like Kummerfeld & Ramsey (2016), which can be replaced by much weaker assumption, please see Appendix C.2 for more details. Assumption (()) means that each root observed variable has a sufficient number of children.
Definition 6. (Candidate variable) Given an observed variable O₁ O, we call O1 is a candidate variable (O; O₁) с OV(O)) 302 E 01(01,0;.0) s.1. Or M Oz, O1 M. (z)(O;), O₁ M )2 and O y. Oz)(
We denote the set of candidate variables by OC
Definition 7. (Tetrad constraint) Given observed pair (0,, c O and set of observed variables O' c O8(01, s.t. |0'| 2 2, we call ((0,, O2), satisfies the tetrad constraint if V(O,, O,} c O', Cov(O,,, O,)oov(0,,, = (;)(O,,,)Cov(O0)))
Theorem 1. Suppose the underlying linear latent variable model satisfies Assumption 1 and (0,.02} O. Then (01.02) Oc and (101, O1(01,02)) satisfies the tetrad constraint if and only [(0,,00 is generalized pure pair.
Based on Theorem 1, we can detect all generalized pure pairs, the set of which is denoted by 3. Since each latent variable has at least generalized pure pair as children according to Assumption (a), every latent variable can be detected at least once. The soundness of Theorem 1 heavily relies on Assumption 1. Roughly speaking, Assumption (a) and ((b) guarantees that if O₃ and O2 both have latent parents, they are always candidate variables, and the tetrad constraint is satisfied if and only if [O,, 02) generalized pure pair. Assumption 1(c) guarantees that if O O₂ has latent parent, they are not both candidate variables or the tetrad constraint is not satisfied.
Lemma 1. Suppose
Then S a pure pair if (but not only if) ES' E s.l. S' #
To fully identify latent variables, still need to determine whether any two generalized pure pairs share a common latent parent, which requires us to first discriminate pure pairs against pseudo-pure pairs. Unfortunately, this issue can only be partially addressed based Lemma this point, so latent variables can only be partially identified. We define a purity indicator function p (-) on 3. If S is identified as pure pair, pure = 1; if S is identified as pseudo-pure pair, 1 p (S) 0; otherwise, if S E S is unidentifiable temporarily, (S) = -. The algorithm is summarized in Algorithm 1, which has O ((0)+) complexity. A detailed version can be found in Appendix D.
3.2 FULLY IDENTIFYING LATENT VARIABLES: CASE
Assumption 2. (a) E L, L has at least one pure child, (b) E L, |Nei (L) 2 4. Furthermore,
if (L)I = 4, Nei @ (L) = (L'), and Chy = (0,, 03) where (0,, O2) is a pure pair, then N (0s) L').
Assumption 2(a) requires only one pure child per latent variable. On the basis of Assumption and 2(a). given an L, there are only two cases where Assumption 2(b) is violated.
1. L has one latent neighbor L', two pure children (0), O2), and other neighbor;
2. L has one latent neighbor L', three observed children {0,, O2, Os}, and no other neighbor, where (0,, 02) is pure pair, O3 has two latent parents (L, L') and no other neighbor.
In other words, Assumption 2(b) can be satisfied in various forms, including but not limited to INeif (L) 2 2, |Neig (L) 2 4, or 30 E Ch. (L) s.t. Neig( (0) # O, etc. In particular, if the three-purechhildren assumption satisfied, Assumption holds, so we say our assumption milder.
Lemma 2. Suppose the underlying linear latent variable model satisfies Assumption I and 2, S (O,, 02) E S and 1 1 (S) = -1. Then is a pseudo-pure pair if and only if 303 e 00 0₂) s.t. (10), 0z), O%10,, O2, Os)) satisfies the tetrad constraint.
4

---

Published as a conference paper at ICLR 2024
Algorithm 2: Fully identifying latent variables in Case I.
Input:
Observed variables O, candidate variables O generalized pure pairs S, purity indicator function pure())
Output: Updated purity indicator function pure O,, sibling indicator function I sih (s
Discriminate pure pairs against pseudo-pure pairs based on Lemma 2.
Check whether two generalized pure pairs share a common latent parent based on Proposition 1.
Given a pseudo-pure pair S = (O1, O2), we denote by Ref(S) any (not all) auxiliary variable O₃ that satisfies the condition in Lemma 2.
Corollary 1. Suppose S is a pseudo-pure pair. Then Ref(S) is pure child of Pay. (S).
Based on Lemma 2, we can completely discriminate pure pairs against pseudo-pure pairs. Besides, Corollary 1 indicates that Ref(S) is not an ordinary variable but pure child of Pa), The soundness of Lemma heavily relies on Assumption 2. With Assumption 2(a), for any pseudo- pure pair, its latent parent has at least one pure child, which can serve as the auxiliary variable that makes the tetrad constraint in Lemma 2 hold; Without Assumption 2(b), given a pure pair, the tetrad constraint in Lemma 2 may still hold, an example is shown in Figure 2(b): for pure pair (O4, Os), ((04, 01). O) (O,, Os, Os}) satisfies the tetrad constraint, where O)(0,, Os, 0s} = (02. Os). Proposition 1. Let (2) C.
1. Suppose S and S2 are two pure pairs. Then (a)( = (a)( if only if) SinS2 0, or 3S3 E S s.t. Si nS # 0 and S2 n3 # 0.
2. Suppose Si is a pure pair and S2 is a pseudo-pure pair. Then Pa{(S)) Pa (S2) if and only (1) (2)) E S1, (2) 38g s.I. (ef(S2) E S3 and S SS # 0.
3. Suppose S₁ and S2 are two pseudo-pure pairs. Then Paf. (a)( paf(())) (S2) if only (1) Ref(S,) (2)( or (2) SS3 S Ref(Si) E S3 and Ref(S²) Sz.
Based on Proposition I, we can determine whether any two generalized pure pairs share common latent parent. We define a sibling indicator function (-, on S x 3. If (S) C S share a common latent parent, (ib(S(,))) = I; otherwise, (S)
= 0. The algorithm for fully identifying latent variables is summarized in Algorithm 2, which has O(OO)t) complexity. A detailed version can be found in Appendix D. With its output, we assign each S, E S with a latent variable Ii, and let I,, = L.j if (S, S,) 1, such that latent variables fully identified.
Theorem 2. Suppose the underlyyng linear latent variable model satisfies Assumption I and 2. Then latent variables can be fully identified.
3.3 FULLY IDENTIFYING LATENT VARIABLES: CASE II
Assumption 3. (a) VS;- = (0 0₂) E s.t. VSJ E SU(S)),S co., and co., are both non-Gaussian, (b) VS with Pa ( (L), i a pseudo-pure pair, then 3V, E Ch (L))S s.t. L 11 Pa (V))L)). Furthermore, Pa = 0. then 3V2 Ch& s.t. L Il Pa (V)LL) and V1 11 V22L.
Assumption 3(a) imposes the non-Gaussianity requirement on only some generalized pure pairs, which are exactly those on which pure (-) is Assumption 3(b) is a bit complicated. Specifically, for any pseudo-pure pair S with latent parent L.
1. if L is a non-root node, Assumption 3(b) requires that 3V e (L) s.t. there is no mediator or confounder between L and V. where V is not necessarily observed variable and may have other parent besides L:
2. if L is a root node, Assumption 3(b) requires that 3(V, 1/2) c Ch (L))S s.t. there is no mediator between L and Vj. no mediator between L and V2, and no confounder between V, and 1/2 besides L.
Clearly, if the Gan-Gaassyy assumption holds, Assumption 3(a) is satisfied; if the two-pure- children assumption holds, Assumption 3(b) is satisfied, so we say our assumption is milder. By the way, it is obvious that if Assumption 2 holds, Assumption 3(b) is satisfied.
Lemma 3. Suppose the underlying linear latent variable model satisfies Assumption and 3, S (O,, 02) and 11 pure (S) -1, Then S is a aseudo-pure pair if and only 3033, 04) O,(0,, 0z)
5

---

Published as a conference paper at ICLR 2024
Algorithm: 3: Fully identifying latent variables in Case II.
Input:
Observed variables O, generalized pure pairs S, purity indicator function pure
Output: Updated indicator function pure sibling indicator function s::b
Discriminate pure pairs against pseudo-pure pairs based on Lemma 3.
Check whether two generalized pure pairs share a common latent parent based on Proposition 2.
which is an ordered pair s.t. + +1+ B0, u1 O₁ where a satisfy
Var(O1) aCoo(O), 02) (Cov(O 03)
(2)
Cov(O), (a)
04) = O;
(3)
or O2 + a0, + B03 n O2 where B satisfy
Var aCov(O2,, 01) (00O)))O0OC 0,
(4)
Cov(O2, Oa)
=0.
(5)
Corollary 2. Suppose S [01,02] E S and 3(33, 04) C 0 O2) which is an ordered pair s.1. + +1+002 303 IL O1 where B satisfy Equation (2) and (3). Then S = (Ö,, O2) is a pure
pair with latent parent Pa.. (S) where Ô 0 and Õ 0 O0
Based on Lemma 3, we can completely discriminate pure pairs against useudo-pure pairs. Besides, each pseudo-purt purudd pair S can be converted into pure one S based on Corollary 2. The soundness of Lemma heavily relies on Assumption 3. Without Assumption 3(a), O₁ + ar2² + B03 1l O₁ in Lemma 3 may hold even if [01, 02) is pure pair since if O₁, O2. O3 are all Gaussian. Equation (2) entails 01 + a02 + 303 1L O Assumption 3(b) ensures that for any pseudo-pure pair S with latent parent L,, we
find two auxiliary variables {03, O4) which makes the condition in Lemma 3 hold. If L. is not a root node, O3 can be V1 (or its child) in Assumption 3(b), O4 can be an observed child of L's any parent; if L is root node, O3, O4 can be V,, V/2 (or their children) in Assumption (b)).
Proposition 2. Let S2) C S where S (01, O2) and S (03, 04). Then
1. Suppose Si and S2 are two pure pairs. Then Pa (Si) = (S)( if only (f(())(SS # s.I. Si S3 O and S2 S3 0.
0, or (2) 3S3
2. Suppose S₁ is a pure pair and S2 is a pseudo-pure pair. Then Pa{,(S,) (af((S)) if and only if (102,, Ö3), {0,, Õ4}) satisfies the tetrad constraint.
(S2) if and only if 3. Suppose S₁ and S2 are two pseudo-pure pairs. Then Pa{(S)) paf((a) ((0,, θz), (Ō,, Ō4}) satisfies the tetrad constraint.
Based on Proposition 2. we can determine whether two generalized pure pairs share a common latent parent, The algorithm for fully identifying latent variables is summarized in Algorithm which has O(1O))) complexity. A detailed version can be found in Appendix D. With its output, we assign each S, 3 with latent variable L,, and let L, L,j if (S, S;) 1, such that latent variables are fully identified.
Theorem 3. Suppose the underlying linear latent variable model satisfies Assumption and 3. Then latent variables can be fully identified.
3.4 DISCUSSION
In Section 3.2 and 3.3, we respectively formulate two cases where none of the non- Gon-Gaussi,,tty, purity, and two- two-pure-childee assumption holds but latent variable can still be fully identified. These two cases make different trade-offs between graphical and distributional assumption. In terms of the graphical assumption, Case requiring no pure child is more general than Case I entailing one pure child per latent variable; in terms of the distributional assumption, Case allowing entirely arbitrary distribution is more general than Case II requiring partial non- non-Gaussianity.
Algorithm 2 and 3 are proposed handle Case and Case II respectively. Without sufficient prior knowledge about the underlying causal model, it is non-trivial problem to choose between them. We design an expedient to handle this issue. We first run Algorithm After that, VS E S, Il (uree())
-1, latent variables can be fully identified; otherwise, v(O;, 0,) e $ s.t. pure (1O;, 0,) -1, we find an E O O,} s.t. (OvOO,O)Cov(O)) 0) 0, if one of O,, O,, O; O))
Cov(O,,0) O2 is Gaussian, then EO, EO, is Gaussian, violating Assumption 3(a), in

---

Published as a conference paper at ICLR 2024
Algorithm 4: PC-MIMBulld
Input: Variables V = U O U OU, and each variable in L LUOU has at least two indicators
Output: partially directed acyelic graph & over V
Find separation set for variables in I. U OU based on Theorem 19 in Silva et al. (2006) to
recover the skeleton over L U OU, which denoted by G.
Orient v-structures in & based on the separation sets.
Orient each undirected edge between a latent variable and an observed variable in G. Orient as many undirected edges in & as possible by Meek's rules (Meek, 1995).
Add variables in OD and corresponding causal edges to G.
which case we choose Algorithm 2, otherwise we choose Algorithm Although this is not per- fect method, it is much better than making a random choice. In fact, most previous works about latent causal structure learning just assumed some properties of the underlying causal models and circumvented the procedure of testing these assumptions.
4 INFERRING CAUSAL RELATIONS BETWEEN ANY TWO VARIABLES
After identifying latent variables, the next step is to infer causal relations between any two variables. In Section 1. describe some pre- processcssnng procedures. In Section 4.2, present the modified PC-MIMBuild for inferring causal relations. No extra assumption is introduced in this section.
4.1 PRE-PROCESSING
Given observed variable O, if 3S E S s.t. O E in Case or Case II, or 38 3 s.t. 0 Re)(SS in Case I, its causal relations with any other variable determined. Specifically, 0 E S and S pure pair in Case Case II, it has no other neighbor except a latent parent; if O E S and S is a pseudo-pure pair in Case or Case II, it has no other neighbor except latent parent and an observed neighbor; if 0 Ref(S) in Case it has no other neighbor except a latent parent based on Corollary 1. Such observed variables are called determined observed variables otherwise undetermined observed variables, the set of which are denoted by OD and O respectively. To recover the whole causal structure, we only need to focus on variables in LUO! O
Proposition 3. No variable in OD is parent of any variable in I. O
To recover the causal structure over latent variables, PC-MIMBuild requires that each latent variable has least two measured indicators that can be represented as its linear function plus an independent noise. Given latent variable L, if L has multiple pure children, these pure children can be detected and serve as the indicators of L, otherwise, according Assumption (aa). In Case I, O₁ and Ref (2)) Case II, 1Ō,, Õ2) derived by Corollary 2 can serve as indicators of L. Furthermore, our objective is to recover the whole causal structure involving both latent and observed variables. Since L U OU is causally sufficient based on Proposition 3, if we create two auxiliary indicators for each undetermined observed variable by adding independent noises it, causal relations between any two variables in L U OU can be revealed by PC-MIMBuild.
must has a pseudo-pure pair {0,,0) as children serve indicators of L; in
4.2 PC-MIMBUILD
An overview of PC-MIMBuild are summarized Algorithm Since no observed variable is parent of any latent one in linear latent variable models, when searching for the separation set of any two latent variables in line 1, we limit the search space to to reduce computational cost. For the same reason, we can orient each undirected edge between a latent variable and an observed one in line 3, which allows more undirected edges be oriented by Meek's rules (Meek, 1995) in line
Theorem 4. Suppose the underlying linear latent variable model satisfies Assumption and or Assumption and 3, in the limit of infinite data, & satisfies that (1) & has the same skeleton and v-structures as G: (2)V1O;; 0,} c 0 s.t. O, E (O)) and Paς (Oi) # Pa (0,), O, e Pa,(
is not surprising that without further assumptions, the causal structure can only be identified up to Markov equivalence. Fortunately, Chen et al. (2022) have proposed additional distributional

---

Published as a conference paper at ICLR 2024
conditions under which the causal structure can be identified completely and also corresponding algorithm, which could apply to & directly if their proposed conditions hold.
5 RELATION TO EXISTING WORK
Most traditional causal discovery approaches typically assume the absence of latent variables, but they usually yield unreliable results in situations involving latent variables which may cause spuri- ous correlations. This has inspired extensive researches into causal discovery with latent variables. While some works aim to reveal causal relations between observed variables the presence of latent variables, others attempt to identify latent variables and recover the latent causal structure. An im- portant line of works employs sparsity of causal edges to facilitate latent causal structure learning for linear latent variable models. The seminal work (Silva et al., 2006) suggested that the latent causal structure can be identified under the tiree-pure-childee assumption. On this basis, Kummerfeld & Ramsey (2016) proposed a more efficient algorithm which allows partial non-linearity based on the work of Spirtes (2013). Cai et al. (2019) first showed that two-pure-children assumption could also enable identification of latent causal structure. Subsequently, Xie al. (2020) and Zeng et al. (2021) attempted to generalize the results of Cai et al. (2019) to more challenging scenarios. The former could address the scenario where observed variables have multiple latent parents while the latter could recover the latent causal structure shared by multiple domains. Although the require- ment for pure children has been relaxed, they additionally entailed the non-Gaussianity and purity assumption. Xie et al. (2023b) made a further step by eliminating the purity assumption. Instead, we formulate two more general cases where none of the non-Gaussi, purity, and two-pure-children assumption holds. By the way, the purity assumption is also required by some other works which utilized matrix decomposition (Anandkumar et al., 2013) or mixture oracle (Kivva et al., 2021) for latent causal structure learning, so work is also more general than theirs in this regard.
Recently, latent hicrarchical causal structure learning has drawn significant attention, where "hi- erarchical" means that some latent variables may lack observed children. The seminal work (Xie et al., 2022) relied on the non-Gaussianity, purity, and generalized two-pure-children (pure children could be either latent or observed) assumption. Huang al. (2022) used more general assumptions that allow arbitrary distribution. Chen et al. (2023) highlighted that the assumptions in Huang el al. (2022) may not hold if there exist three mutually adjacent variables, they overcome this limitation by requiring more pure children. At a high level, each of these works decomposes the hierarchical structure into multiple layers, and then infers latent variables and their causal relations from lower to higher levels recursively. Since most algorithms used within single level originate from those designed for conventional linear latent variable models, our results can potentially generalized to this scenario. Some recent works leveraged counterfactual data (Brehmer et al., 2022; Ahuja et al., 2022) or interventional data (Ahuja et al., 2023; Seigal et al., 2023) rather than purely observa- tional data for latent causal structure learning. Although they have avoided many distributional and graphical assumptions, interventional or counterfactual data is not always available in practice.
Instead of the causal structure over only latent variables, attempt recover the whole causal structure involving both latent and observed variables. Previously, Adams et al. (2021) have in- troduced much weaker graphical assumptions for recovery of the whole causal structure, but they still required the Gaussiaayyy assumption and their proposed algorithms are computationally in- tractable. A contemporancous work (Xie al., 2023a) proposed efficient algorithms to recover the whole causal structure of n-factor causal models with latent hierarchical structure, which are beyond our ability. However, they still required the Gon-Gaussinnity and (generalized) two-pure-children assumption, and only allowed edges between particular observed variables.
In this paper, we decompose the recovery of the whole causal structure into two sub- uub-problems: identification of latent variables and inference of causal relations between any two variables. In Section 3, we provide main theoretical results about the first sub-problem, the proofs of which heavily rely on the Tetrad Representation Theorem (Spirtes et al., 2000) and Darmois-Skitovich Theorem (Kagan, 1989), which are presented in Appendix B.I and B.7. The former builds a con- nection between the structure of underlying causal model and the covariance of variables that can be calculated from samples. The latter means that as long as two variables share any non-Gause Gan-Gsssiin component, they cannot be statistically independent. Although many existing works (Silva et al., 2006; Xie et al., 2020; 2023b) also used them as cornerstones, their results cannot be directly in- volved in our framework where their required assumptions are mostly not satisfied. In Section
8

---

Published as a conference paper at ICLR 2024
Table I: Performance on synthetic data derived by causal models with structure G and G2-
N=500
N=1000
N=2000
Graph Algorithm
LO
LC
WI
Er
LO
LC
WI
Err
LO
LC
WI
Em
BPC
0.33+0..37
0.00&0.00
0.1910.16
1.0
0.3040.25
0.00g0.00
0.1640.13
1.0 0.2740.13
0.00g0.00
0.1640.08
1.0
FOFC
0:93+0.13
0.00=0.00
0.02+0.05
1.0 1.0000000
0.00+0.00
0.00+0.00
1.0 1.00+0.00
0.00+0.00
0.00=0.00
1.0
G
GIN
0.50#0.27
0.00=0.00
0.66#0. 17
1.0 0.60+0.20
0.00+0.00
0.75+0.09
1.0 0.57+0.21
0.00+0.00
0.71 16
1.0
Ours
0.07+0.13
0.03+0.10
0.0340.06
0.0340.10
0.00=0.00
0.01+0.04
0.2 0.00=0.00
0.00=0.00
0.00=0.00
BPC
0.30&0.23
0.00g0.00
0.29
1.0 0.27400.0
0.00s0.00
0.30g0.11
1.0 0.27+0.13
0.00=0.00
0.2840.11 11 1.0
FOFC
0.90+0.1 15
0.00+0.00
0.0340.04
1.0 0.9740. 10
0.00+0.00
0.01+0.022
1.0 1.00+0.00
0.00+0.00
0.00+0.00
1.0
6:
GIN
0.10&0.15
0.07
0.20s0.15
0.0740.13
0.07+0.13
0.23w0.13
1.0 0.00g0.00
0.07+0.13
0.30g0.07
Ours
0.13+0.22
0.00=0.00
1.1 17 0.5 0.10+0.21 0.00+0.00 0.07+0.15
0.3 0.03+0.10 0.00+0.00 0.03+0. 10 0.2
present algorithms for the second sub sub-problem, which are mostly based on the PC-MIMBuild (Silva et al., 2006). To make it more adaptable our framework, we design pre-processing procedures in Section 4. I and also make some modifications to itself in Section 4.2.
6 EXPERIMENTAL RESULTS
We apply our proposed algorithms to both synthetic and real-world data demonstrate their effee- tiveness. Due to the space limit, we only present experimental results on synthetic data derived by causal models with structure Gi and G2 as shown in Figure in the main text and provide more de- tails in Appendix A. For each graph, we draw 10 sample sets of size N=500, 1000, 2000 respectively. Each causal strength is sampled from a uniform distribution over [-2.0, -.000-0.5 2.0]. Noises of causal models with structure Gi are Gaussian variables with mean 0 and standard error drawn from uniform(0.5.1 1), those of causal models with structure G2 are the seventh power of uniform(-1.1) variables. which are then normalized to have standard error also drawn from uniform(0.5.1)..
We compare our proposed methods with BPC (Silva et al., 2006), FOFC (Kummerfeld & Ramsey, 2016), and GIN (Xie et al., 2020). We use Latent Omission (LO), Latent Commission (LC), Wrong Indicator (WI) as the evaluation metrics. LO and LC are respectively the number of omitted and redundant latent variables divided by the total number of latent variables in ground truth graph. WI is the number of wrong indicators divided by the total number of observed variables in the ground truth graph, where an indicator is called wrong if it measures least one wrong latent variable or it is still dependent of some other indicators given the latent variable it measures. Besides, we also report the Error Rate (Err) which is the number of sample sets on which LO, LCC, and WI are not all 0 divided by the total number of sample sets.
The experimental results are summarized in Table 1. No previous approach can yield correct re- sults since their required assumptions are not satisfied. For instance, FOFC requires the three-pure- children assumption, and its implementation in TETRAD (Ramsey et al., 2018) actually prefers at least four pure children per latent variable, so it cannot detect latent variables, leading to high LO. Using the expedient proposed in Section 3.4, we choose Algorithm 1 plus 2 to recover Gi and Algorithm 1 plus 3 to recover G2. Because causal models with structure Gi and G2 both satisfy Assumption and respectively satisfy Assumption and 3, our algorithms can return correct results.
7 CONCLUSION AND FUTURE WORK
In this paper, we endeavor to recover the whole causal structure of linear latent variable models under milder graphical and distributional assumptions. Firstly, we formulate two cases where none of the Gaussiaaii,,,,, purity, and two-pure-children assumption holds. Secondly, we prove that the whole causal structure involving both latent and observed variables is identifiable in either case. Thirdly, we also provide efficient algorithms for causal structure recovery.
Although we prove identifiability under milder assumptions, they may still not hold in practice. For instance, an observed variable might be the cause of some latent variables (Adams et al., 2021), some causal relations might be non-linear (Kaltenpoth & Vreeken, 2023) or non-stationary (Liu & Kuang, 2023), and the underlying causal graph may be cyclic because feedback loops are not uncom- mon (Sethuraman et al., 2023). Actually, some causal questions might be answered even without a fully identified causal graph, so is useful to investigate to which extent the causal structure can be recovered under less restrictive assumptions. Finally, to guarantee trustworthy result, need special algorithms to test whether the required assumptions are satisfied, for which we only propose an imperfect expedient in Section 3.4 while most existing works directly circumvent this procedure.
9

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENT
XL is partially supported by the JD Technology Scholarship for Postgraduate Research in Artificial Intelligence. KZ would like to acknowledge the support from NSF Grant 2229881, the National Institutes of Health (NIH) under Contract ROIHL159805, and grants from Apple Inc., KDDI Re- search Inc., Quris AI, and Infinite Brain Technology. TL is partially supported by the following Australian Research Council projects: FT220100318 DP220102121, LP20000077 IC190100031.
REFERENCES
Jeffrey Adams, Niels Hansen, and Kun Zhang. Identification of partially observed linear causal models: Graphical conditions for the non- ganssassii and heterogeneous cases. In Conference on Neural Information Processing Systems, pp. 22-22222222222 2021.
Kartik Ahuja, Jason S Hartford, and Yoshua Bengio. Weakly supervised representation learning with sparse perturbations. In Conference on Neural Information Processing Systems, pp. 15516 15528, 2022.
Kartik Ahuja, Divyat Mahajan, Yixin Wang, and Yoshua Bengio. Interventional causal representa- tion learning. In International Conference Machine Learning, pp. 372-407, 2023.
Animashree Anandkumar, Daniel Hsu, Adel Javanmard, and Sham Kakade. Learning linear bayesian networks with latent variables. In International Conference on Machine Learning, pp- 249-257, 2013.
Johann Brehmer, Pim De Haan, Phillip Lippe, and Taco S Cohen. Weakly supervised causal repre- sentation learning. In Conference on Neural Information Processing Systems, pp. 38319-38331, 2022.
Barbara M Byrne. Structural equation modeling with Mplus: Basic concepts, applications, and programming. routledge, 2013.
Ruichu Cai, Feng Xie, Clark Glymour, Zhifeng Hao, and Kun Zhang. Triad constraints for learning causal structure of latent variables. In Conference on Neural Information Processing Systems, pp- 12883-12892, 2019.
Ruichu Cai, Zhiyi Huang, Wei Chen, Zhifeng Hao, and Kun Zhang. Causal discovery with latent confounders based on higher-order eumulants. In International Conference Machine Learning, pp. 3380-3407, 2023.
Zhengming Chen, Feng Xie, Jie Qiao, Zhifeng Hao, Kun Zhang, and Ruichu Cai. Identification of linear latent variable model with arbitrary distribution. In AAAI Conference on Artificial Intelli- gence, volume 36, pp. 6350-6357, 2022.
Zhengming Chen, Feng Xie, Jie Qiao, Zhifeng Hao, and Ruichu Cai. Some general identification re- sults for linear latent hierarchical causal structure. In International Joint Conferences Artificial Intellignnee 2023.
David Maxwell Chickering. Optimal structure identification with greedy search. Journal of Machine Learning Research, 3:507-554, 2002.
Tom Claassen and Ioan G Bucur. Greedy equivalence search in the presence of latent confounders. In Uncertainty Artificial Intelligence, pp. 443-452, 2022.
Ricardo Dominguez-Olmedo, Amir H Karimi, and Bernhard Schölkopf. On the adversarial ro- bustness of causal algorithmic recourse. In International Conference on Machine Learning, pp- 5324-5342, 2022.
Ziming Hong, Zhenyi Wang. Li Shen, Yu Yao, Zhuo Huang, Shiming Chen, Chuanwu Yang, Ming- ming Gong, and Tongliang Liu. Improving non- transferable representation learning by harnessing content and style. In International Conference Learning Representations, 2024.
10

---

Published as a conference paper at ICLR 2024
Patrik Hoyer, Dominik Janzing, Joris M Mooij, Jonas Peters, and Bernhard Schölkopf. Nonlinear causal discovery with additive noise models. Conference on Neural Information Processing Systems, pp. 689-696, 2008a.
Patrik O Hoyer, Shohei Shimizu, Antti J Kerminen, and Markus Palviainen. Estimation of causal effects using linear non-gaussian causal models with hidden variables. International Journal of Approximate Reasoning, 49:362-378, 2008b.
Biwei Huang, Charles Jia Han Low, Feng Xie, Clark Glymour, and Kun Zhang, Latent hierarchical causal structure discovery with rank constraints, In Conference on Neural Information Processing Systems, pp. 5549-5549500 5561, 2022.
Zhuo Huang, Xiaobo Xia, Li Shen, Bo Han, Mingming Gong, Chen Gong, and Tongliang Liu. Harnessing citto--distributiion examples via augmenting content and style. In International Con- ference Learning Reprexentations, 2023.
AM Kagan. New classes of dependent random variables and a generalization of the darmois- skitovich theorem to several forms. Theory of Probability & Its Applications, 33:286-290 295, 1989.
David Kaltenpoth and Jilles Vreeken. Nonlinear causal discovery with latent confounders. In Inter- national Conference Machine Learning, pp. 15639-15654, 2023.
Bohdan Kivva, Goutham Rajendran, Pradeep Ravikumar, and Bryon Aragam. Learning latent causal graphs via mixture oracles. In Conference on Neural Information Processing Systems, pp. 18087- 18101, 2021.
Erich Kummerfeld and Joseph Ramsey. Causal clustering for 1-factor measurement models. InACM SIGKDD International Conference Knowledge Discovery and Data Mining, pp. 1655-1664 2016.
Yexiong Lin, Yu Yao, Xiaolong Shi, Mingming Gong, Xu Shen, Dong Xu, and Tongliang Liu. Cs-isolate: Extracting hard confident examples by content and style isolation. In Conference on Neural Information Processing Systems, pp. 58556-585777 2023.
Chenxi Liu and Kun Kuang. Causal structure learning for latent intervened non-stationary data. In International Conference on Machine Learning, pp. 11756-21777, 2023.
Aidan Lyon. Why normal distributions normal? The British Journal for the Philosophy of Science, 65:621-649, 2014.
Takashi Nicholas Maeda and Shohei Shimizu. Red: Repetitive causal discovery of linear non- gaussian acyelic models with latent confounders. International Conference on Artificial Intel- ligence and Statistics, pp. 735-745, 2020.
Christopher Meek. Causal inference and causal explanation with background knowledge. In Uncer- tainty in Artificial Intelligence, pp. 403-410, 1995.
Joris M Mooij, Jonas Peters, Dominik Janzing, Jakob Zscheischler, and Bernhard Schölkopf. Dis- tinguishing cause from effect using observational data: methods and benchmarks. Journal of Machine Learning Research, 17:1103-1204 2016.
Jonas Peters, Joris M Mooij, Dominik Janzing, and Bernhard Schölkopf. Causal discovery with continuous additive noise models. Journal of Machine Learning Research, 15:2009-2053 2014.
Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Elements of causal inference: foundations and learning algorithms. The MIT Press, 2017.
Joseph D Ramsey, Kun Zhang, Madelyn Glymour, Ruben Sanchez Romero, Biwei Huang, Imme Ebert- Ubert-Uphoff, Savini Samarasinghe, Elizabeth A Barnes, and Clark Glymour. Tetrad-a toolbox for causal discovery. International Workshop on Climate Informatics, pp. 29, 2018.
Yves Rosseel. lavaan: An package for structural equation modeling. Journal of Statistical Soft-
ware, 48:1-36, 2012.
11

---

Published as a conference paper at ICLR 2024
Saber Salehkaleybar, AmirEmad Ghassami, Negar Kiyavash, and Kun Zhang. Learning linear non- gaussian causal models in the presence of latent variables. Journal of Machine Learning Research, 21:1436-1459, 2020.
Joumnal
Bernhard Schölkopf, Francesco Locatello, Stefan Bauer, Nan Rosemary Ke, Nal Kalchbrenner, Anirudh Goyal, and Yoshua Bengio. Toward causal representation learning. Proceedings of the IEEE, 109:612 634. 2021.
Lukas Schott, Jonas Rauber, Matthias Bethge, and Wieland Brendel. Towards the first adversarially robust neural network model on mnist. In International Conference on Learning Representations, 2018.
Anna Seigal, Chandler Squires, and Caroline Uhler. Linear causal disentanglement via interventions. In International Conference on Machine Learning, pp. 12540-32561 2023.
Muralikrishnna G Sethuraman, Romain Lopez, Rahul Mohan, Faramarz Fekri, Tommaso Bian- calani, and Can-Chiistian Hütter. Nodags-flow flow: Nonlinear cyclic causal structure learning. In International Conference on Artificial Intelligence and Statisticx, pp. 6371-6387, 2023.
Shohei Shimizu, Patrik O Hoyer, Aapo Hyvärinen, Antti Kerminen, and Michael Jordan. A linear non-gaussian acyclic model for causal discovery. Journal of Machine Learning Research, 7: 2006.
Shohei Shimizu, Takanori Inazumi, Yasuhiro Sogawa, Aapo Hyvarinen, Yoshinobu Kawahara, Takashi Washio, Patrik O Hoyer, Kenneth Bollen, and Patrik Hoyer. Directlingam: A direct method for learning a linear non-gan con-gaussian structural equation model. Journal of Machine Learn- ing Research, 22:1225-1248, 2011.
Ricardo Silva, Richard Scheines, Clark Glymour, Peter Spirtes, and David Maxwell Chickering. Learning the structure of linear latent variable models. Journal of Machine Learning Research, 7:191-246, 2006.
Peter Spirtes. Calculation of entailed rank constraints in partially non-linear and cyclic models. In Uncertainty in Artificial Intelligence, pp. 606-615, 2013.
Peter Spirtes, Christopher Meek, and Thomas Richardson. Causal inference in the presence of latent variables and selection bias. In Uncertainty in Artificial Intelligence, pp. 499-506, 1995.
Peter Spirtes, Clark Glymour, and Richard Scheines. Causation, prediction, and search. 2000.
Sullivant, Talaska, and J Draisma. Trek separation for gaussian graphical models. The Annals of Statistics, 38: 1665-1685, 2010.
Tatsuya Tashiro, Shohei Shimizu, Aapo Hyvärinen, and Takashi Washio. Parcelingam: A causal ordering method robust against latent confounders. Neural computation, 26:57-83, 83, 2014.
Lingxiao Wang, Zhuoran Yang, and Zhaoran Wang. Provably efficient causal reinforcement learning with confounded observational data. In Conference on Neural Information Processing Systems, pp. 21111-1111277 175, 2021.
Feng Xie, Ruichu Cai, Biwei Huang, Clark Glymour, Zeng Hao, and Kun Zhang. Generalized independent noise condition for estimating latent variable causal graphs. In Conference on Neural Information Processing Systems, pp. 14891-14902, 2020.
Feng Xie, Biwei Huang, Zhengming Chen, Yangbo He, Zhi Geng, and Kun Zhang. Identifica- tion of linear non-gaussian latent hierarchical structure. In International Conference on Machine Learning, pp. 24370-24387, 2022.
Feng Xie, Biwei Huang, Zhengming Chen, Ruichu Cai, Clark Glymour, Zhi Geng, and Kun Zhang. Generalized independent noise condition for estimating causal structure with latent variables. arXiv preprint arXiv:2308.067 2308.0671888888 2023a.
Feng Xie, Yan Zeng, Zhengming Chen, Yangbo He, Zhi Geng, and Kun Zhang. Causal discovery of I-factor measurement models linear latent variable models with arbitrary noise distributions. Neurocomputing, 526:48-61 2023b.
12

---

Published as a conference paper at ICLR 2024
Yu Yao, Tongliang Liu, Mingming Gong, Bo Han, Gang Niu, and Kun Zhang. instance-dependee label-noise learning under a structural causal model. Conference on Neural Information Pro- cessing Systems, pp. 4409-4420, 2021.
Yan Zeng, Shohei Shimizu, Ruichu Cai, Feng Xie, Michio Yamamoto, and Zhifeng Hao. Causal discovery with multi-domain lingam for latent factors. In International Joint Conferences on Artificial Intelligence, pp. 2097-2103, 2021.
Kun Zhang and Aapo Hyvarinen. On the identifiability of the post-nonlinear causal model. In Uncertainty in Artificial Intelligence, pp. 647-655, 2009.
13

---

Published as a conference paper at ICLR 2024
Organization of Appendix:
Section A: More experimental results.
Section B: Proof.
Section C: More theoretical results.
Section D: Details of algorithms.
A MORE EXPERIMENTAL RESULTS
First, we compare Algorithm plus to existing algorithms on more causal models with structure G3. G4. Gs shown in Figure 3(a.b.c). For each graph, draw 10 sample sets of size N=1000. Each causal strength is sampled from a uniform distribution over [-2.0, -0.5] U (0.5,2.0]. All noises Gaussian variables generated following Section 6. Experimental results are summarized in Table 2.
Table Comparison of Algorithm I plus with others.
G4
G.
Algorithm
1.0
1.C
WI
Fir
1.0
1.C
WI
Firr
1,0
1.C.
WI
Fi
BPC
0.00=0.00
0.00+0.00
0.05#0.09 0.2 0.67+0.30
0.00.0.00
0.30#0.26
1.0 0,40=0.13
0.0020.00
0.39=0.12
1.0
FOFC
0.0740.13
0.0040.00
0.0140.02
0.2 1.00+0.00
0.00+0.00
0.00+0.00
1.0 0.9740.10 0.00:0.00
0.0240.07
1.0
GIN
0,53+0.16
0.00+0.00
0.58+0.14
1.0 0.5010.22
0.00+0.00
0.78+0.00
1.0 0.67#0.00
0.00=0.00
0.78=0.00
Ours
0.0540.10
0.00+0.00 0.00+0.00 0.1 0.00+0.00 0.23+0.15 0.4010.13
1.0 0,00=0.00
0.00:0.00 0.13+0.07 1.0
Since G3 satisfies the three-pure-children assumption, BPC and FOFC can yield correct results. Because Assumption and 2 are also satisfied in this case, our algorithm can also return correct results. As all noises are Gaussian and there exist edges between observed variables in G3. GIN always produce wrong results.
2. Since L1 in G4 has no pure child, Assumption 2(a) is not satisfied. In this case, our algo- rithm will falsely identify both {O1, O2) and (O3, O4) as pure pairs which do not share common latent parent. Therefore, f-1 will be split into two latent variables, whose indica- tors are respectively {0 O2) and (O3, O4). leading to high LC and WI. Therefore, our algorithms cannot yield correct results. Any other algorithm also fails.
3. Since L3 in G5 has exactly one latent parent L and three observed children O7, Og. O9 where O7, Og are both pure child of L3 and Pa (0₂) (22, L3), Assumption 2(b) is not satisfied. In this case our algorithm will falsely identify (0s, Og} as pseudo-pure -ure pair and Ref(( 09)) = O7, so O7, Og will serve as the indicators of L3, leading to high WI. Therefore, our algorithms cannot yield correct results. Any other algorithm also fails.
Second, we compare Algorithm plus 3 to existing algorithms on more causal models with structure G6. G. as shown in Figure 3(d,e.f). For each graph, we draw 10 sample sets of size -11000. Each causal strength is sampled from a uniform distribution over [-2.0, -0.5] U [0.5, 2.0J. All noises of causal models with structure Go and Gx are non-Gaussian variables generated following Section 6. For causal models with structure G7, noises of (02, O4, O6. Os} are non-Gaussian while other noises are Gaussian. Experimental results summarized in Table 3.
Table Comparison of Algorithm plus with others.
Go
G.
Gx
Algorithm
1.0
L.C
WI
Fir
1.0
L.C
W1
Firr
1.0
LCC.
W1
Fir
BPC
0.6340.31
0.00+0.00
0.1440.13
1.0 0.5310.16
0.0010.00
0.3510.12
1.0 0.77a0.15
0.0010.00 0.2810.21
1.0
FOFC
1.00=0.00
0.00+0.00
0.00g0.00
10 0.9740.10
0.00g0.00
0.03+0.08
1.0 1.0000.00
0.00=0.00
0.00=0.00
1.0
GIN
0.4740.43
0.0040.00
0.0040.00
0.6 0.50+0.27
0.0340.10
0.68+0.11
1.0 0.53+0.22
0.03e0. 10 0.75e0.00
1.0
Ours
0.0010.00
0.0040.00
0.00+0.00
0.0 0.43+0.21
0.0010.00
0.6510.12
1.0 0.07+0.20
0.00:0.00
0.30=0.10
1.0
14

---

Published as a conference paper at ICLR 2024
(a) G3: Three-pure-chhee pureeeccrr-ehheennn assumption is satisfied
(b) 94 Assumption 2(a) is violated
(c) Gs: Assumption 2(b) is violated
(d) G6: Non-Gaussianity, purity, and two-pure-
children assumption are all satisfied
(e) Gh: Assumption 3()) is violated
(f) Gy: Assumption 3(b) is violated
(g) Go
(h) G10
(i) G11 Assumption I(c) is violated
Figure 3: Causal graphs used to synthesize data, noises of red variables are non-Gaussian.
1. Since causal models with structure satisfy the non-Gaussianity, purity, and two-pure- children assumption, GIN can yield correct results. In this case, Assumption and are also satisfied, so our algorithms can also return correct results. Furthermore, because al- gorithms use both second-order and high-order statistics while GIN purely relies on high- order statistics, our Err is remarkably lower than GIN. Since the three-pure-chie cureecedddenn as- sumption is not satisfied, both BPC and FOFC always produce wrong results.
2. Since S = [{O1, O2). (03. O4), (Os, 0s), {0,, Os)} in G7 and noises of (O2, O4, Os. Og) in causal models with structure G7 are all Gaussian, Assumption 3(a) is not satisfied. In this case, our algorithm may falsely identify pure pairs as pseudo-pure ones and pseudo- pure pairs cannot be converted into pure ones correctly. variable is split into multiple ones multiple latent variables are merged into a signle one. Therefore, our algorithms cannot yield correct results. Any other algorithm also fails.
possible that single latent
3. Since the L3 in G3 has pseudo-pure pair (0,, O&) as children but has other child, Assumption 3(b) is not satisfied. this case, our algorithm will falsely identify {07, Og) pure one, and both of them will serve the indicators of L3. leading to high WI. Therefore, our algorithms cannot yield correct results. Any other algorithm also fails.
Moreover, we investigate the behavior of different algorithms on causal models with structure G9. G1o. and Gı1 as shown in Figure 3(g.h,i), where there is no latent variable. For each graph, we draw 10 sample sets of size N=1000. Each causal strength is sampled from uniform distribution over [-2.0, -0.5] 2.0]. All noises are non-Gaussian variables generated following Section 6. Overall, our algorithms return no generalized pure pair in Go. G10- and G11. indicating that there exists latent variable. This is because only one candidate variable 0 and O₂ in G10 and Gn respectively. However, all other algorithms introduce latent variable being the parent of all observed ones in G10 and G11. Note that in G10. the
tetrad constraint is satisfied in Go and there exists
15

---

Published as a conference paper at ICLR 2024
root variable O₁ has only one child O2, violating Assumption I(c), but our algorithms still yield correct results. In the case without latent variable, PC-MIMBuild can be replaced by the vanilla PC.
Finally, compare algorithms with others two real-world datasets: HolzingerSwine ford1939 (HS1939) (Rosscel, 2012) and Teacher Burnout (TB) (Byme, 2013). The experimental results summarized in Table 4.
Table Experimental results on real-world datasets.
Algorithm
HS1939
Teacher Burnout
LO
LC
WI
L.
LC
WI
BPC
0.00
0.00
0.00
0.42
0.00
0.13
FOFC
1.00
0.00
0.00
1.00
0.00
0.00
GIN
0.33
0.00
0.22
0.75
0.00
0.34
Ours
0.00
0.00
0.00
0.25
0.00
0.06
HolzingerSwinefrr11933 (HS1939) dataset consists of mental ability test scores of seventh- and highth-grade children. observed variables influenced by 3 latent variables (visual, textual and speed). Please refer to Section 4 in Rosseel (2012) for more details of the dataset and the ground-truth causal graph.
2. Teacher Burnout (TB) dataset is used to investigate the influence of organization and per- sonality on burnout in full-time elementary teachers. 32 observed variables are influenced by 12 latent variables (role ambiguity. role conflict, work overload, classroom climate, de- cision making. superior support, peer support, self-esteem, external locus of control, emo- tional exhaustion, depersonalization and personal accomplishment). Please refer Chapter 6 in Byrne (2013) for more details of the dataset and the ground-truth causal graph.
B PROOFS
B. PROOF THEOREM
We begin with the Tetrad Representation Theorem (Spirtes et al., 2000) which is essential for our proof.
Theorem 5. (Tetrad Representation Theorem) In linear latent variable model with graph structure G. let I,, Jı,J2 be four variables in G. Then ((h,)) (J1, satisfies the tetrad constraint if and only there a choke point between (I,, 12) and (2}.
Theorem 5 entails some graphical definitions. Specifically, in a directed acyclic (DAG) graph,
a path is sequence of distinct variables Vi...., Vms such that V2 is adjacent to Vk+1 for all k I...., - In particular, single variable is also path.
2. a collider on a path Vj,... Vm is variable V,, i < n, such that Vi1 and V41 are both
parents of V;:
3. trek is path that does not contain any collider;
4. the source of a trek is the unique node in the trek to which no arrows are directed.
5. the side of a trek between and with source the subpath directed from to I. In particular, it is possible that S = I;
6. a choke point between two set of variables and J is variable V that lies on every trek between any element and any element of and V is either on the side of every such trek or on the J side of every such trek.
Then we further define pseudo-pus pure child and generalized pure child for ease of exposition. Definition 8. (Pseudo-pure child) An observed variable 01 O is called pseudo-pure child of latent variable if 0, E Pa& (O2), O, is called a type-l pseudo-pure child of L; otherwise, O is called a rype- pseudo-pure child of l..
0 E Chg (L) and 30, s.t. {O,, 02) pseudo-pure pair. Furthermore,
16

---

Published as a conference paper at ICLR 2024
Definition 9. (Generalized pure child) An observed variable O E O is called generalized pure child of a latent variable L E L if is a pure child or a pseudo-pus child of L.
Assumption (a) VI. E L, has at least one generulized pure pair as children, (b) VL E L, Neif. (L) # 0, and (O)
VO E O, Pf (0) = 0, then (O)) 3.
Assumption (a) indicates that each latent variable has at least two generalized pure children.
Before proving Theorem 1, we present three lemmas about candidate variables under Assumption Lemma 4. Suppose 01 E O and (01) * 0. Then 0 E OC
Proof. Let L1 Pa
According to Assumption (a). L1 has generalized pure child O2 * O Besides, 11 has latent neighbor L2 according to Assumption ((b) and L2 has two generalized
(O1). (O,).
pure children {03, 04) c Oi(O,, O2) according to Assumption (a)) Therefore, there are treks
O1 < L1 O2, 01 t L1 L2 O3, O1 + L1 L2 04. That is, V[O,00] O)(O)) let O2 E (02, 03, 04) O)). we have 0 и Ox. 01 y Oxl(Oi).00 x Oxl(O;}, and 0 M
Oxl(O;, 01 E O
Lemma 5. Suppose O E O and Pa 0. 1f0, E OC, (Neig (01) 2.
Proof. This lemma proved by contradiction. Suppose |Neig (01) 2. combined with Assump- tion 1(c), O, is a leaf node which has no other neighbor besides an observed parent Oz. Based on the local Markov property (Peters et al., 2017), O₁ a O110,, (22), so O₁ & OC, which leads to contradiction.
Lemma Suppose (01, |Neig( (0)) U Neig (0-)) 0z)1 2.
and Pa Pa. = If (01, OC, then
Proof. This lemma is proved by contradiction. Suppose |Neig (O₂) Nei (0)MMO,00) 1. There are two possible cases.
1. Suppose O2 E (O1), then INeig (0t) U (02)0000 02)1 $ implies that |Neig (0)) s 1, based on Lemma 5, O & OC, which leads to contradiction.
2. Suppose O2 E Neig
[Neig(0,) Neig 02)1 O, then Neig(0)) (02)
{01), based Lemma 5, O₁ OC. which leads to contradiction. If |Neig (01) U Nei Neig (O))MO0000 = I, since INeig (Ncig(0,) 2 2 and INeig (02) 2 2, there exists 03 0810,, 02) s.t. (0) = (02.0g) and (eig((,) (0). According Assumption I(c), neither 0, nor O₂ is a root node, either O or O₂ is leaf node. Without loss of generality, let O₁ be leaf node, then O₃ has no other neighbor besides two observed parents O2, O3. Based on the local Markov property, O₁ Il 0)(02, O3), that is, 0 & O which leads to contradiction.
Theorem 1. Suppose the underlying linear latent variable model satisfies Assumption 1 and (0,.02 O. Then (0,,02) O and O1(,,00) satisfies the tetrad constraint if and only (0,,02) is generalized pure pair.
Proof. (i) "If". Suppose (O,, 02} is generalized pure pair, then (aς # 0 and Paς # 0. based on Lemma 4, (0,, 02) c O Let Paς. ((O,, = (L), then VO E Oy(0,, 02). L lies in each trek between O and O and is the 0 side of every such trek. This also holds for each trek between O₂ and O. Therefore, Theorem 5, we reach the conclusion that ((01, 01(01, O2)) satisfies the tetrad constraint.
a choke point between (0,, 02) and O,10,, O2). Based on
17

---

Published as a conference paper at ICLR 2024
01
03
O2
0
01
0
O2
0+
(a) Case
(b) Case 2
L1
L2
L
L2
01
0
O2
0+
01
02
O
0+
(c) Case 3
(d) Case 4
Figure 4: Illustration proof (ii) of Theorem
(ii) "Only if" This part is proved by contradiction. Suppose (01, is not generalized pure pair, there are 4 possible cases w.r.t. Pay (O1) and Paf (02).
Suppose ones of Paf. (01) and Pay. (02) is an emply set. Without loss of generality, and Paf(O2)) 0. Based Lemma 5, O, has an ob- served neighbor O3 e 0V(02). Let L. E (0)) then I. has a generalized pure child O4 0)(0,,0,, 03) according Assumption ((a). Clearly, there two intersecting treks 0 -0 and O2 - L O4. Therefore, there is no choke point between (2) and [03. 04). An illustrative example is shown in Figure 4(a).
we suppose Pay. (O,) (O,)
2. Suppose Pa (0,)
and Pa)(O,) 0. Based on Lemma 5 and 6, 3(03, 04) 0Y(0,, 02) s.t. O3 (O))(0,) and O4 Neig (02). Clearly, there are two non- intersecting treks O 0 and -24 Therefore, there is no choke point between (0,, O2) and (03, 04). An illustrative example is shown in Figure 4(b).
3. Suppose Paς((o)
O. Paf # O and [Paf 02))1
That is, there exist
L1 E Paf (0), L2 E Paf((O, s.t. L1 # L2. According to Assumption 1(a), Lı has generalized pure child O₃ OV(0,, Similarly, L2 has generalized pure child O4 O,(0,, 02) and O3 # O4. Clearly, there are two non- non-intersecting treks 0 - L1 - O3 and O₂ - L2 O4. Therefore, there is no choke point between (0,, 02) and {03, 04). An illustrative example is shown in Figure 4(c).
4. Suppose (o)) * 0, Pa (02) * 0 and IPa (10) 02)) 1. Since (0,, 02) is not generalized pure pair, there is Neig (0))((0)) * or Neig (02) # 0. Without loss of generality, we suppose Pa oa (10,, 02)) (L1). E (z2) latent neighbor L2 according to Assumption 1(b) and L2 has a generalized pure child O4 Assumption ((a). Clearly, there are two non-intersecting treks O2 O3 and 0 <- I,, l22 - O4. Therefore, there is no choke point between {O,.0,) 02) and (Os, 04). An illustrative example is shown in Figure 4(d).
Then L₁ has
O)(O,, Oz. 03} according
Based on Theorem 5, we reach the conclusion that (20, 01000, 02)) does not satisfy the tetrad constraint, which leads to contradiction.
18

---

Published as a conference paper at ICLR 2024
L/
4
4
L2
05
0
02
03
0+
01
02
0
O5
(a) Case
(b) Case
Lg
4
L2
4
L2
05
0₂
02
O
O
0
02
Os
0
0+
(c) Case 3
Case 4(a)
Case 5(a)
(d) Case 4(b)
Case 5(b)
4
L2
0
O
05
Os
Case 5(c)
Figure 5: Illustration of proof (ii) of Lemma 2, where dotted lines mean that the edges may may not exist.
B.2 PROOF LEMMA
Lemma 1. Suppose S S. Then S is a pure pair if (but not only if) 3S' e e s.t. S S' # 0.
Proof. (i) "If". This can be easily derived from the Definition 3, 4, and 5.
(ii) "Not only if". If latent variable L has no pure child except 0 and O2, then (0,, a pure pair but it does overlap with any other generalized pure pair.
B.3 PROOF LEMMA
Assumption (a) VL E L, has least one pure child, (b) E L. |Nei (L) 4. Furthermore, Nei (I.) = 4, Nei L (I.) (1'), and Chg (0,, O2, 03) where (01, O2) a pure pair, then
N (0s) # L'.
Lemma 2. Suppose the underlying linear latent variable model satisfies Assumption and 2, S (01, 02) E $ and I (S) -1 Then S is pseudo-pure pair if and only if 303 e 0C 0z) p
s.1. (f0,, 03), 0 (Y10,, O2, O3}) satisfies the tetrad constraint.
Proof. (i) "Only if". Suppose S = (0,, is ascudo-pure pair and let ( = (L). According to Assumption 2(a), L has a pure child O₂ E 0)(0,, O2). Based on Lemma 4, O3 OC. Besides, Vo (),0,, O2. O2). L lies in each trek between O and and on the 0 side of every such trek. This also holds for each trek between O₃ and O. Therefore, L is choke point between (0), 03) and OV10, O2, Oz). Based on Theorem 5, we reach the conclusion that ((O,, Oz). 0, O2. 0z}) satisfies the tetrad constraint.
19

---

Published as a conference paper at ICLR 2024
(ii) "If". This part proved by contradiction. Suppose S {01, O2) is a pure pair and let Paf
{L1}. Because (S) = -1, L1 has no pure child except O and O2, otherwise we can derive pure based Lemma 1. There are 5 possible cases w.r.t. Paf(
1. Suppose (0) 0. Based on Lemma 5, O3 has an observed children O4 OM(O,, Besides, L, has a latent neighbor L2 according to Assumption 1(b) and L2 has generalized pure child Os E 0%(0,, O2, O3. O4) according to Assumption (()). Clearly, there are two non-intersecting treks O3 O4 and O₁ < L1 L2 - Os. Therefore, there is no choke point between {01,0) and {04, Os}. An illustrative example is shown in Figure 5(a).
2. Suppose (a²) = (L1). Since O3 is not a pure child of L1, O3 has an observed neighbor O4 E OV(0,,0), Besides, L1 has a latent neighbor L2 according to Assumption 1(b) and L2 has a generalized pure child Os E O O2. O3, O+} according to Assumption 1(a). Clearly, there are two non-intersecting treks
and O t L1 L2 O5. Therefore, there is no choke point between {01, O3) and (0,, Os). An illustrative example is shown in Figure 5(b).
3. Suppose (Os) # {Li} and 32, E (Os)((L)) s.t. L2 & Neif(L1). (L1). Then L2 has a (Os) generalized pure child O4 E 0V10,, 02, Os) according to Assumption (()). Besides, Li has a latent neighbor L3 # L2 according to Assumption ((b) and L3 has generalized pure child O5 E 01 O2, O3, 04) according to Assumption ((a). Clearly, there are two intersecting treks 03 < L-2 - O4 and O₁ < L1 L3 - Os. Therefore, there is no choke point between (O,, 0z) and (04, Os). An illustrative example is shown in Figure 5(c).
4. Suppose (O3) * (41) VL e Paf M4))),))),
Neig. (41) and L Paf(O)). Let L2 E Paf. (LL), then L2 has a generalized pure child O4 E O110,, 12, O3) according Assumption (a)). Furthermore, there are two possible sub-case sub-cases w.r.t. Neig(L)). (L1).
(a) Suppose INeif [1)] (L)) 2 2. Then L1 has latent neighbor L3 # L2. The remaining proof is the same as Case 3.
(b) Suppose |Nei (1)) = 1, According to Assumption 2(b) that INeiS (Li) 2 4, 4,30s
Chg (L)))OO, 02). Since L1 & Paf (03) and O4 is generalized pure child of L2, we have Os # 03 and O5 # 04. Clearly, there are two non-intersecting treks 03 + L2 O4 and 0₁ L1 Os. Therefore, there is choke point between (0,, 0z) and [04, Os}. An illustrative example is shown in Figure 5(d).
According to Assumption 1(b), Neig. (L1) # O, so there is no other possible sub-case.
5. Suppose (Os) (41), VL Paf (4)))
Neif (L1) and L₁ Paς Let L2 E Paf. (Os)\( then L2 has a generalized pure child O4 E OV10,, O2, 03) according to Assumption ((a). Furthermore, there are three possible sub-cases w.r.t. Neif (L,).
(a) Suppose [Neif, (L,) 2 2. The remaining proof is the same as Case 4(a).
(b) Suppose |Neig (L1) 1 and INei (L1) let Oş e (L)(L)) Oz, O3). Since Os is a generalized pure child of L2, Os # O4. The remaining proof is the same as Case 4(b).
(c) Suppose |Nei (L1) = I and @ (L)) = 4, considering the supposition at the be- ginning of Case 5, we have Neif. (L1) (L2). CLg(L))) (O,, (2, 0z), (O,) Assumption 2(b) that Nei (0z) # (L,, L2). there is Neig (O₂) ) # 0. Let Oş E Neig( Since O4 is a generalized pure child of L2, Os $ O4. Clearly, there two non- -in--reeeecttnggg treks O₂- - Os and O L1 L2
(L1, L2). According
O4. Therefore, there is no choke point between (O,, Oz) and (O4, Os). An illustra-
tive example is shown in Figure 5(e).
20

---

Published as a conference paper at ICLR 2024
L
00
O2
O3
0
Og
8₁
52
S
Ref((22)
S2
S1 Ref(s,) Ref(52) 52
(a) Condition ((1)
(b) Condition 2(1)
(c) Condition 3(1)
S
82
S3 Ref(S.)
S2
Re((S,) S3 Ref(S²)
52
(d) Condition 1(2)
(e) Condition 2(2)
(l) Condition 3(2)
Figure 6: Illustrative examples for Proposition 1.
According to Assumption 1(b) and Assumption 2(b), Nei (L1) # and |Nei (L1) 2 4. there is other possible sub-case.
Based on Theorem we reach the conclusion that YO; 0 02). ((O),03), 0V),, O2, 0z)) does not satisfy the tetrad constraint, which leads to contradiction.
B.4 PROOF OF COROLLARY
Corollary 1. Suppose S is a pseudo-pure pair. Then Ref(S) is pure child of Pa (S).
Proof. This corollary is proved by contradiction. Suppose Ref(S) is not pure child of Paf (S), let = [O,, 02), Ref(S) O3 and Pa)( (L1). According to Assumption 2(a), L1 has a pure child O4 01101, O2, 03). Then there three possible cases w.r.t. Paf (0g).
1. Suppose Pa (O3) = 0. Based on Lemma 2 and Lemma 5, O3 has an observed neighbor O, E OY10,, O2, O4}. Clearly, there are two non-intersecting treks 0₁ L1 O4 and 0; O5. Therefore, there is no choke point between (01, Oz) and (0+, Os).
2. Suppose (a,)) # 0 and Pa Pa (03) * {L1). Let Le E Paf (O:) Then L2 has generalized pure child Os E 0f10,, O2, O3, O4). Clearly, there are two non-intersecting treks 0₁ - 1, - O4 and O3 < L2 Os. Therefore, there is no choke point between (3),03) and (04. 0s).
3. Suppose pa (03) (L1). Since O3 not a pure child of I,,, it has an observed neighbor Os E O)10), O2, O3, O4). Clearly, there are two non-intersecting treks O < L - O4 and O3 - O3. Therefore, there is choke point between (0,,0z) and (0,, 0s).
Based Theorem reach the conclusion that ((O,,0;), 01 Oz, 0z)) does not satisfy the tetrad constraint, which leads to contradiction.
B.5 PROOF PROPOSITION
Proposition 1. Let S2) S.
21

---

Published as a conference paper at ICLR 2024
1. Suppose S1 and S2 are two pure pairs. Then Pa (S)) Paf if and only (f S 0, or (2) 3S3 E s.t. S1 nS # 0 and S2 n # O.
2. Suppose S₁ is pure pair and Sn is pseudo-puu pair. Then Pay, (Si) ) Paf. (S2) if and only (1) Ref(S2) E St, or (2) 3S3 3 s.t. Ref(S2) S3 and S S # 0.
3. Suppose S1 and S2 are two pseudo-pure pairs. Then Paf((s) (Si) = f (S2) if and only (f) Ref(S,) Re)( (2) 3S3 e s.t. Ref(Si) E S3 and Ref(S2) S3.
P
Proof. (i) "If"
1. Suppose S₁ and Se are two pure pairs. (1) Suppose Si n S2 # 0. Then Paf (S)) Pa (S) n S2) Pa{(Sa) (S2). (2) Suppose 3S3 & s.t. Si n 0 and S² 0 S3 # 0. Then = Paf (S2). Pat (Si) Paf (Sx) (S3)
2. Suppose S₁ is a pure pair and S2 is pseudo-pure pair. (1) Suppose Ref(S2) E St. Then based on Corollary Paf. (Si) Paf (R))(S2)) Pay (S2). (2) Suppose 3S} s.t.
Ref(S2) E S3 and S C S3 # 0. Then based on Corollary 1, (a)) Paf. (Re)(S:)) Paf. (S2).
(Si) = Pa (St)
3. Suppose S₁ and S2 are two pseudo-pure pairs. (1) Suppose Ref(S)) = Ref( Then
based on Corollary 1, Pa (Si Pa (Ref(Si)) Paf. (Ref(S:)) = Pa (S2). (2) Suppose
3S₁ s.t. Re)(S E S3 and Ref(S2) S3. Then based Corollary 1, Paf. (St) Paf (Ref(S))) Paf (Sa) Paf (Ref(S))) = Paf (S2).
(ii) "Only if"
1. Suppose S and S2 are two pure pairs and Paf = Pa (S²) = (L). Then 0A E Si U2
O a pure child of L. It is obviously possible that S S 2 # 0; otherwise, V0, E S₁ and vO2 S2, S3 {01. 02) is also pure pair, that is, S3 E S.
2. Suppose S₁ is pure pair, S2 is a pseudo-pure pair, and Paf (S)) Paf (L). Then based on Corollary NO S U (Re((S2)). O is a pure child of It obviously possible that (ef(S)) E Si; otherwise, VO E St. S3 = (ef(s) is also a pure pair, that is, S3 S.
3. Suppose S and Sn are two pure pairs and Paf (S,) = Pa (S²) = (L). Then based on Corollary 1, both Ref(S,) and Ref(S)) are pure children of I.. It obviously possible that Ref(S,) Re)( otherwise S3- (Ref(S)), Ref(Sz)) is also pure pair, that is, S3 E S.
B.6 PROOF OF THEOREM 2
Theorem 2. Suppose the underlying linear latent variable model satisfies Assumption 1 and 2. Then latent variables can be fully identified.
Proof. Theorem ensures latent omission under Assumption while Proposition ensures latent commission under Assumption 1 and 2. Therefore, latent variables can be fully identified. O
B.7 PROOF OF LEMMA 3
We begin with Darmois- Skitoiichh Theorem (Kagan, 1989) which essential for our proof.
Theorem 6. (Darmois Skitovitch DDarmois-Skitoiitch Theorem) Suppose random variables V1 and V2 be repre- sented as linear combinations of independent random variables (ei)i
Vi Σ aien
V/= Σ Biei.
(6)
22

---

Published as a conference paper at ICLR 2024
L3
L3
L2
04
1
02
0
0g
(a) L1 is non-root node, Vi c cO
(b) L1 is non-root node, V1
L3
4
Oz
0+
0
(c) L1 is rool node, V O, 1/2 L
(d) L1 is root node, (Vi, 1/2]
L2
L3
L2
O2
0
0g
(e) L1 is root node, V1 L. 1/2
L1 is root node, (Vi, 1/2)
Figure 7: Illustrative of proof of Lemma 3.
Then, if V1 and V2 are independent, all variables ej for which a aB,; # O Gaussian. In other words, if there exists a non-Gaussian e for which ar B # 0, V1 and V22 are dependent.
Assumption 3. (a) VS; = =0,,, E $ s.t. VS, E SMSS) n S = 0, EO., and EO,, are both non-Gaussian. (b) VS S with Pa.(S) (L), S a pseudo-pune pair, then 3V1 E Ch (L)\S s.1. и1 Pa& (V)) Furthermore, Pa (L) = 0, then 3V2 (L) s.i. L 11 Pa (1)) and V1 V2
B.8 PROOF OF LEMMA 3
Lemma 3. Suppose the underlying linear latent variable model satisfies Assumption I and 3, S (01,0s and (S) = -1, Then is a pseudo-pure pair if and only if 3(33, O4) c. OY(0,, 02) which is ordered pair O + a02 803 O₁ where a, satisfy
Var(O,) + (((O)))=aov(O,,000 02) BCov O3) =0,
(7)
04) =0,
(8)
or 02+00 303 IL O2 where a satisfy
Var(O2) (COO) 03) =0
(9)
(00(0),00)+++Co0000000000000 (Cov( 04) 0.
(10)
Proof. (i) "If". This part is proved by contradiction. Suppose S = (0,, 02) is a pure pair. Then 0, contains 6o, while VO (), O does not contain ED, Therefore, Va, 0 a02 + 80, contains 60,- Because Eo, is non non-Gaussian based on Assumption 3(a), 0, a0, + 80, A O,. Similarly, Va. B. O2 a0, 303 y O2, which leads to contradiction.
23

---

Published as a conference paper at ICLR 2024
( "Only if". Suppose S is pseudo-pure pure pair and 0₁ (a2 without loss of generality. Let (aO 02)) (I-1), then 01, O2 be represented
0 =c14++ 60
(11)
0₂ = c1241 + d1201 E0, (cnd12 c12)411 d1250, + +0.-
(12)
There are two possible cases w.r.t L1.
1. Suppose L1 is not a root node. According Assumption 3(b). 3V e (L))OO,,
s.t. L1 ыl Pa (Vi) V E O. we let O₃ Vı; otherwise we let L2 Vi and O3 be pure child or a type-l pseudo-pure child L2. Therefore, O3 can represented as
0 = -13 Co,
03 223 co; b1202s 023 + 60g
(13)
where fEo,, } 11 LT. Let L3 e Paf. (L1) and O4 a pure child or type-I pseudo-pure child L3 which can represented as
O4 = C3443 + E0.
(14)
Since L1 11 Pa (v)MVL) and L3 that (5 (i)) L3.
we have L3 Pa (Vi) indicating
2. Suppose Li root node. According Assumption 3(b), 3(V, 12] (L) L 1L Pa (V)) L 1. Pa (V2) and V1 1 V2 If Vi E O, we let 02 Vi; otherwise let L2 V1 and O3 pure child or a type-I pseudo-pure child of L2-
V/2 E O, we let V/2 = O4; otherwise we let 1/2 L3 and O4 be a pure child or a type-I pseudo-pure child of L3. Therefore, O3, O4 can be represented as
0 = C13LI + E' or 0, = 0232 + Eo; 212023L1 + C23 + +
(15)
04 = cial1 éo.
O₂ c3al3 EO, b13czal1 c34E2 E02
(16)
where (e' l. For 4,)) 11 L1 and ( 11 (E {,.)
Clearly, L1 is non-root node, there are two possible cases w.r.t {0s, O4): otherwise, there are four possible cases w.r.t. (03, O4}. We show all six possible cases in Figure 7. In each case, can rewrite 0₁, O2, O3, 04
0 A1L EO,
(17)
O = A2L + W2E0 + +02
(18)
03 dzl. + E03'
(19)
04 A4 6
(20)
where EO,, 60,, 50, 5, are independent of each other, each of them is independent of L and L,, and Cov(L,L') # O. We substitute Equation (17)~(20) into Equation (7) and (8),
d (1 + ad2 + Var) (1+ aw>) Var(E,,)
(21)
(22)
which yield that
A ad2 BA and
I + +aw> = 0.
(23)
Therefore, we can reach the conclusion that
01+a02+p00 = (21 + +dd2 + + (1 +aw)eo, + +aEo, BEO, = + +BE 11 0). (24)
24

---

Published as a conference paper at ICLR 2024
B.9 PROOF OF COROLLARY 2
Corollary 2. Suppose S = {01, O2) E 3 and 3(03. O4) C (0 02) which is an ordered pair
s.f. O1 + a02 + 303 u 0 where a. satisfy Equation (2) and (3). Then S = (01, 02) is a pure pair with latent parent fa (S) where Ô 0₁ and O₂ = 0 00,
Proof. Based on Lemma 3, S (0,, 02) is pseudo-pure pair. Suppose O2 Pa Pa (01), then O, contains EO, while 4A & O (11)), O does not contain 60,, so Va, B. 01 + aQ2 + B03 contains 60,- As ED, is non- -au-Gaas based Assumption 3(a), 01 a02 + f03 ı O₁, which leads to contradiction. Therefore, we can conclude O₁ E Pa (O2). Let Paf, (S) = (4.) then O,, O2 can be represented as
0, = =111+++00
(25)
= = 1 to. (c11d12 c12) d12 + 602 We can easily obtain = because if a - both 0 and 01 + a02 B03 contain non- Gaussian t i.e., 01 + +002 + 803 N. O1. Therefore, we can represent Ō,, Ô₂ as
(26)
o, = Cn1 EO, E0
Ô2 = =c202 60.
(27)
Clearly, (ő,,02) is pure pair with latent parent L. B.10 PROOF OF PROPOSITION
Proposition 2. Let S1) c where S (01,02) and S² = [03, 04). Then
Suppose S₁ and S2 are two pure pairs. Pa (S (S)) = Pa (S2) (S2) if and only if) (1 S * 0, or 3S3 $ s.t. SinS; # 0 and S n S3 * 0.
2. Suppose Si is pure pair and S2 is pseudo-pure pair. Then Paf, (Si) Pa (S2) if and only if ((02, 03), {0 Õ4)) satisfies the tetrad constraint.
3. Suppose S₁ and S2 are two pseudo-pure pairs. Then Paf,(S) Paf, (S2) if and only if ((02,03), θ4}) satisfies the tetrad constraint.
Proof. "If"
1. Suppose Si and S2 are two pure pairs. The proof is the same as that of the first sub- proposition of Proposition 1.
2. Suppose S₁ a pure pair and S2 pseudo-pure pair. Clearly, St S2 0. Based on Corollary {Ō3, 04) is pure pair with latent parent Pa (S2). This part can be proved Paf((5 by contradiction. Suppose Pa((S) Paf. (S2), let Paf (S, {L1} and Paς(S2) Then there are two non-intersecting treks 0 - L1 -2 and Ô L2 - Ô4, there is no choke point between (02, 03) and {0,, Ô4). Therefore, (102, 03), (0,, O4 does not satisfy the tetrad constraint, which leads to contradiction.
(S2) (L2).
3. Suppose Sj and S2 are two pseudo-pure pairs. The remaining proof similar that of the second sub pooppoopoiiionn above.
(ii) "Only if"
1. Suppose S₁ and S2 two pure pairs. The proof is the same as that of the first sub- proposition of Proposition I.
2. Suppose S₁ is a pure pair and S2 is a pseudo-pure pair. Clearly, S n S2 = 0. Based
on Corollary 2, {Ō,, Ô4) is a pure pair with latent parent Paf( (Sa). Suppose Pa (Si) Pa (S2), let fa (Si) = (4). Since O₁, Oz, Ôs, Ôa are all pure children of L, a choke point between (02, σ₃) and (O,, Ō.). Therefore, ((Oz. θz}. (0,, σ.)) satisfies the tetrad constraint.
25

---

Published as a conference paper at ICLR 2024
X
Z
Z
Figure Illustration of Meek's rule 1
3. Suppose S1 and S2 are two pseudo-pure pairs. The remaining proof is similar to that of the second uub-proposition above.
B.11 PROOF OF THEOREM 3
Suppose the underlying linear latent variable model satisfies Assumption 1 and 3. Then latent variables can be fully identified.
Theorem 3.
Proof. Theorem ensures no latent omission under Assumption while Proposition ensures no latent commission under Assumption and 3. Therefore, latent variables can be fully identified. O
B.12 PROOF OF PROPOSITION
Proposition 3. No variable in OP is parent of any variable in L LUU0 O..
Proof. We prove this proposition in Case (where Assumption and 2 hold) and Case II (where Assumption and hold) respectively.
1. In Case I, O₁ E OD and only if (1) 302 E s.t. s.t. 0 (S) Based Corollary 1, the latter means that O₃ is a pure child of some latent variable. Therefore, we can easily reach the conclusion that no variable in O is parent of any variable in LUOU
(0).02) E S, or (2) SS e s.t.
2. In Case II, O₂ OD if and only if 302 O s.t. {0,, 02) 8, so no variable in OD is parent of any variable in L LO0d
B.13 PROOF THEOREM 4
Theorem 4. Suppose the underlying linear latent variable model satisfies Assumption and 2 or Assumption and 3, in the limit of infinite data, G satisfies that (1) & has the same skeleton and v-structures G; (2) 0j) s.t. O; E (a)(O.) and Paf. (O.) # (a)) O, Pa (O,)
Proof. Based Theorem 2 and Theorem 3, latent variables can be fully identified. After pre- processing, each latent variable has multiple indicators of which each can be represented as its linear function plus independent noise.
(1) This derived by the soundness of PC algorithm.
(2) Without loss of generality, suppose 0, E Pa (O,), there are two possible cases w.r.t. (0,)
Suppose AL E Pa (0,) s.t. L E Paf (O,). Then there exists a v-structure - in G. which can be discovered by line 2 of Algorithm 4.
- -
26

---

Published as a conference paper at ICLR 2024
2. Suppose VL E (O), (O). Since Pa, # Paf. EL' (0,) s.t.
$ (O)) After line 3 of Algorithm 4, there L'' 0,-0, and L' is not adjacent to
O in G. Based on Meek's s rule shown as Figure 8, 0, 0 can be oriented as 0, - Oj.
C MORE THEORETICAL RESULTS
C.I NON-LINEARITY
All theoretical results in Section 3.1 and 3.2 are derived by the Tetrad Representation Theo- rem (Spirtes et al., 2000), which is a special form of the Trek Separation Theorem (Sullivant et al., 2010). Furthermore, Spirtes (2013) has extended the Trek Separation Theorem to partially nonlinear cases. An exact formulation of the Extended Trek Separation Theorem entails many concepts not previously introduced, here we only need to know
1.
If there is a choke point C between {41 123 and (2], C is on the {4, 12) side, and for each directed path æ from C to {/, 12,, any vertex V on æ is linear function of its parents along π plus an arbitrary function of the parents not along æ, then (f/1. /2), (2) satisfies the tetrad constraint.
2. If there is no choke point between {4, /2) and (2), under faithfulness assumption, ((), (2) does not satisfy the tetrad constraint.
Based on these two propositions, we conclude that all theoretical results in Section 3.1 and 3.2 are still valid as long as all causal relations involving generalized pure children (see Definition 9) are linear. More specifically, any causal relation between and V2 can be nonlinear as long neither V1 nor V/2 is a generalized pure child of some latent variable. Any tetrad constraint in this case holds if and only if it holds in the linear case. Furthermore, if only causal relations between observed variables that are not pseudo-pure children (see Definition 8) of some latent variable are nonlinear while others are all linear, all theoretical results in Section 3.3 also hold, because our proofs do not rely on linearity of these causal relations.
C.2 WEAKENING ASSUMPTION I(B)
Assumption 1(b) requires that VL L, Nei (L) 0. It used only in the proof of Theorem 1 and Lemma In fact, even if 3L s.t. Nei (L) = 0, Theorem still holds for every such L,, (L))(L)) z 4; and Lemma still holds if for every such L. ICh. (L) 2 Taking Lemma 2 as an example, we prove that it still holds if VZ. s.t. Neig 0. |Ch (
Proof. In the proof of Lemma 2 given in Appendix B.3, Assumption 1(b) is only used to prove that YO E 0c (((0,, ({O,,0),00 0,00 10,00.00, 0}) does not satisfy the tetrad constraint if S (01,0) 02) is a pure pair and 1l pure (S) = -1 We only need to prove this part. Let Pag (S) = (L1), L has no pure child except O, and O2 since 1 pure = -. Given an O3 E 001(0,, 02), there are three possible cases w.r.t. Paf.(Og).
1. Suppose Pa5(Os) 0. Based on Lemma 5, O3 has an observed children 04 Oy{0,, O2}. If Neig( (L1) # 0, the proof the same as the original one; otherwise, there is |Chg (L1)) 5 according
assumption, 30s E Ch (L.)))O) O2, Oz, Oa)- Clearly, there are two non-intersecting treks O₂ O4 and O < 11 - O5. Therefore, there is no choke point between (0,, 03} and (04, O5).
2. Suppose Paf)(Os) = (L1). Since O3 is not pure child of L,. 304 e Neig(O:) where Os & (0,, 02). 3. If Neig, (L1) # 0, the proof is the same as the original one; otherwise, there is (Ch((1.)) (1+1) 5 according our assumption, 30s (1.())))10, Oz, Oz, O4).
27

---

Published as a conference paper at ICLR 2024
Clearly, there are two non-intersecting treks O₃ O4 and 01 < L1 Os. Therefore, there is no choke point between {01. 03) and {04, Os).
3. Suppose Paf. (03) 0 and Paf. (03) # {Li}, that is, 3L2 E Paf (O3) Then L2 has generalized pure child O4 E O 1, O2, 03) according to Assumption (()). If Nei (L1) * 0, the proof the same as the original one; otherwise, there is |Chg (L)) 2 5 according assumption, 305 Chg((, (1g))((01 O2. O3, O4). Clearly, there are non- intersecting treks O3 < L2 - O4 and O₁ - L1 - O5. Therefore, there no choke point between {0,, 0z) and [04, Os).
Based on Theorem 5, we reach the conclusion that Vo 02), 01100,00),,,,000,0000,000,,, 0H) does not satisfy the tetrad constraint.
D DETAILS OF ALGORITHMS
The detailed versions of Algorithm 1, 2, and 3 are shown Algorithm 5, 6, and 7. Besides, we also provide two illustrative examples to show how each step proceeds.
1
(a) G1
(b) G
Taking the causal model with structure Gi an example of Case show the procedures of recovering the whole causal graph as follows.
1. Line of Algorithm I: find all candidate variables. Here O = =.
2. Line of Algorithm 1: find all generalized pure pairs. ((01, O2). O3), (0z, (04, Os). (06, O7), (0g, 0s), (0n, 012)).
Here
3. Line 3 of Algorithm I: identify many pure pairs possible. Since (0,, 02) 0 {0,,0, # and {O,, [2) n (02,0s 03} # 0, ((0,, (102. 0z}) 1, for any other generalized pure pair 11 pure -1.
= p100 03))
4. Line of Algorithm 2: discriminate pure pairs against pseudo-pure ones. Since
(106. 04), 0,, O6. 07}) satisfies the tetrad constraint, p 07}) = 0 and Ref( 07)) O4. Similarly, we have pare ((0g, 0g)) 0. pure (0 012))
and Ref( (0s, 0g)) = O10. Re.((On. 012)) = O Besides, pure 0s)) =
5. Line 2 of Algorithm 2: check whether any two generalized pure pairs share a common
latent parent. Clearly, (af,( = Paf,((O,. 0zt) = Paf. (10,, 0z)) = (L1), Paς (104, 05)) (af,(O4) Paf, (106, 0T)) (L2), and (10g 0,)) Paf. (01o) Paf. (10 112)) = (Ls).
6. Pre-processing in Section 4.1: The measured indicators of L1, L2 and L3 can be respectively (0 02), (0., Os) and (Og, 11)). Furthermore, we also create two auxiliary measured indicators for each vari- able in O
L2,, 0D = [0 1-1 O" (0 0.4.
7. Run Algorithm 4 to reveal causal relations between any two variables.
Taking the causal model with structure G2 as an example of Case II, we show the procedures of recovering the whole causal graph follows.
1. Line of Algorithm 1: find all candidate variables 0C, Here 0f O.
28

---

Published as a conference paper at ICLR 2024
2. Line 2 of Algorithm 1: find all generalized pure pairs S.
Here
$
{[01, O2). (0),04), (0s, 0s), (0,, Os). {O,, (9), (0g. Os)).
3. Line 3 of Algorithm I: identify as many pure pairs as possible. Since (0,, Os) 0
(O,, 09) * 0 and {0,,0s) n (Os.09) * 0, pare 0x)) pure ((07, 0g))
I pure (10g. Oa)) = 1, for any other generalized pure pair 1l pure is
4. Line of Algorithm discriminate pure pairs against pseudo-pun ones and convert each pseudo-pury ones into pure one. Since (01, O2) can make O3 + a02 + 80, I O₃ hold and (0,, 01) can make O5 + a06 + ,80 11 Os hold, we have pure (103. 04)) and pure ([Os. 0st) O. Besides, we also have 1l pure (101, 02)) = 1. Then we convert {O3, O4) into {Ō3, Õ4) and (Os, O6} into {Ō5, 0g)
5. Line 2 of Algorithm 3: check whether two generalized pure pairs share com- mon latent parent. We have Paf. (=0,..0))2) = (103, 04)) = (41 since
((0,, θ3), (02. (4)) satisfies the tetrad constraint, Paf (105, 06)) = (L2). and
Paf (107, 0s)) Paf (107, 09}) Pag (10s, 0o)) {L3).
6. Pre-processing in Section 4.1: L = (L1, L2, Lx), O = (Oi) Ou = (0 O 012)- The measured indicators of L1 L2 and L3 can be respectively (0,, O2). (05, θ,) and {O,, Os). Furthermore, we also create two auxiliary measured indicators for each variable in O
7. Run Algorithm 4 to reveal causal relations between any two variables.
29

---

Published as a conference paper at ICLR 2024
Algorithm 5: Partially identifying latent variables under Assumption (a detailed version).
Input: Observed variable O.
Output: Candidate variables OC, generalized pure pairs $, purity indicator function pure
// Find all candidate variables.
0 : 0;
for 01 E do
flag 1. for (02. 03) c (1(0)) do vf 0,(0,, 0z} s.t. O, O4 given some subset of (02, O3) then
flag O; break
end end
11
flag = then
O = 0 (01):
12
13
end
14 end
15
Find all generalized pure pairs.
3 = 0:
for (0,, 02) c o do
ifv 04) 001101000...00000,,0000000000000 = (,000)))00))00..000000000000000, then su ((01,02))
18
29
end
21 end
// Identify many pure pairs possible;
23 for S
(S) = 11;
25 end
for S E $ do
27
Ir'SS' SMS) s.t. S'S' # 0 then
28
(S)
29
end
30
end
30

---

Published as a conference paper at ICLR 2024
Algorithm 6: Fully identifying latent variables in Case (a detailed version).
Input: Observed variables O, candidate variables 0 generalized pure pairs 8 purity indicator
function pure (-)
Output: Updated purity indicator function pure (.), sibling indicator function s.)b( // Discriminate pure pairs against pseudo-pure pairs.
for == (0, C S s.t. (ure =1 do
for O3 E 0 10, 02) do
if Y004, Os) (O), O2, 03), Cov(O1, Cow.:n.-cpCc000000000--000000000 then
Il pure (S) := 0: Ref( S) = O3i
else
pure (S)
end
end 10
I1 end
// Check whether two generalized pure pairs share common latent parent.
13 for S2) c do
sib S2) 0:
15 end
for (S,,S2) $ do
17
pure (S) = and Il pure (S²) = then
18
if S S2
ES; (() Si n and S2 n 0 then Lb (2) =
20
end
else if
pure (Si) 0 and pure (S²) then
22
SS) E S2 or SS₃ (S,, S2) s.t. Ref(S)) E S3 and S2 n S3 # then
23
sb (2)
I;
24
end
25
else if 1 pure ( (S₁) = and 1l pare (S₂) = then
if Ref( S₁ or 3S₁ (S, S2) s.t. Ref(S:) S3 and S n S. # then sbb S2) == end
27
28
else
30
(S)) E (e) or ES; e ((S),S}) s.t. Ref(S)) e S3 and Ref(S,) E S3 then 1 S2) 1;
32
end
33
end
34 end
31

---

Published as a conference paper at ICLR 2024
Algorithm 7: Fully identifying latent variables in Case II (a detailed version).
Input: Observed variables O, generalized pure pairs $, purity indicator function Il pure (-)
Output: Updated purity indicator function p (:), sibling indicator function (., // Discriminate pure pairs against pseudo-pure pairs.
for S = {O,, 02) C $ s.t. (S)
do
for (O3, 04) c O,(0,, (2) do
if 0 + a02 880 IL O₁ where B satisfy Equation (2) and (3) then
(pare()) =: 0, Ô O1, 02 == O2 + 01;
else if 0₂ +2 80; 3 и O2 where a. B satisfy Equation (4) and (5) then pure (S) = 0, 0 == 0 + 0r, 02 = Oz;
else
pure (S)
10
end
end 11
12 end
// Check whether two generalized pure pairs share common latent parent.
14 for S2) do
sbb S2) 0;
16 end
for (S,, S2) do
18
pure (S)) = and ll pure (S2) = then
19
S n
ES; (V( Si n and S n 0 then sbb ()) ==
29
21
end
22
else if
pure ( 0 and ll pure (S:) then if CCCvv θ Cov 03) (ov( then
24
sub Sz) = 1;
end
else if 1 pure (Si) 1 and 1l pure (St) = 0 then
27
if Cov( ,, (ov 03) (ov(0)),0)Cov(0))0 then
28
Lb (S, 1;
end
30
else
(oCov( O,) θ3) Cov(0,,,3)Cov(02.00 Ō4) then
31
a (S,,
33
end
34
end
35 end
32


Reviews:
[{"review_id": "sq8DuBfBS8", "reviewer": "Reviewer_nXRg", "summary": "The authors address the problem of causal discovery in the presence of latent variables.  As opposed to most approaches that aim to handle latent variables, which focus on estimating the causal dependence among the observed variables in the presence of latent variables, the authors focus on identifying the latent variables and the dependence structure between them and the observed variables.  Other similar methods in the literature have stricter assumptions, generally requiring either at least two pure children of each latent variables or non-Gaussianity.  The authors' proposed method has milder assumptions, requiring at a minimum only a generalized pure child pair and a latent neighbor for each latent variable.  The authors go on to describe increasing sets of assumptions that allow for stronger identifiability and present the algorithm PC-MIMBUILD.", "questions": "Section 2, in the second sentence, says that no observed variable can be a parent of a latent one.  This seems like a non-trivial assumption, yet it is not treated as an assumption, or justified, anywhere that I can see.  Is this a standard assumption in this sort of latent-variable identification literature?  Is there a reason to believe that, in practice, that this assumption is reasonable?\n\nIn Section 3.1, what is \"latent commission\"?  I don't see it anywhere in the paper apart from this mention.\n\nIs there any guidance for how to choose which algorithm/set of assumptions to go with?  For example, in the experimental results in the Appendix, Algorithm 1+2 or Algorithm 1+3 are chosen depending on the underlying graph.  In practice, however, we won't have access to the underlying graph.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper addresses an interesting problem and the initial motivation is strong.  Rather than presenting a single set of relaxing assumptions, I appreciate the authors' presentation of multiple sets that can be used depending on the situation.  The writing is generally good, and the notation is consistent and clear.  In addition, as someone largely new to this specific sub-field of research, the authors do a good job at summarizing the state of the art and positioning their work within it.", "weaknesses": "I have two primary concerns about this paper: the awkward presentation order of the narrative and the lack of any empirical results.\n\nThroughout, this paper has an issue with referencing terms and concepts extensively before actually defining them.  While some level of this is often inevitable (e.g., you're not going to have defined everything by the introduction, yet you still need to give a high level overview), this is rampant enough in this paper that it often hinders understanding.  For example, in the introduction, the mentions of a \"pure child\" in the second paragraph, while a bit unclear, were largely fie (despite not knowing what a \"pure child\" was on a first read, I could at some level get that a \"two-pure-children assumption\" was lighter than a \"three-pure-children assumption\".  However, the fourth paragraph of the introduction continues to talk about \"the purity assumption\" and \"pure children\", without even trying to provide a high-level intuition of these terms.  Similarly, the fifth paragraph of the introduction has the line \"the two structures in Figure 2 cannot be discriminated against each other, where {O3, O4) in Figure 2(a) is called a pseudo-pure pair.\" - this is essentially meaningless with any basic terminology or intuition.  I'd recommend keeping the introduction at a higher level and providing some of this discussion after Section 2.\n\nThis pattern persists, on a much smaller scale, throughout Section 3.  For example, in Section 3.1, the paragraph before Theorem 1 reads as though it assumes some familiarity with Theorem 1.  Presenting them the theorem and then presenting a description of the intuition afterwards would lead to a much clearer flow.\n\nIn general, Section 3 is high on technical detail and low on intuition.  Some of the assumptions (e.g., |Nei(L)| >= 4 in Assumption 2) feel very specific and arbitrary.  While I'm sure there's a strong motivation behind it, no discussion is provided to help the reader along in understanding where it comes from.  I'm sure that fitting everything into the page limit was a challenge, but as it stands, I think the lack of discussion and intuition makes the paper challenging to follow.\n\nI see that empirical results are present in the appendix.  However, I wish at least some experiments were included in the main paper.  For those experiments, it also appears (though I may be mistaken) that all of the synthetic data graphs conform to the assumptions made by the authors.  I'd be interested to see how the author's approach performs under mild assumption violations, and how it compare to other algorithms when all of them have their assumptions violated in different ways.\n\nThis is a minor point and doesn't contribute to my score, but the authors use the phrase \"relatively milder\" a lot in this paper, and it feels awkward.  Sometimes, as in the first paragraph of Section 3, an assumption is referred to as \"relatively milder\" when no alternative is being discussed, leaving the comparative \"milder\" feeling strange.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "m4LXatAgpD", "reviewer": "Reviewer_YYCe", "summary": "Expanding on previous work on causal discovery for linear latent models, this work allows for causal relationships between observed children of latent variables. Specifically, they give 2 conditions under which such models are identifiable. One under which the latent has to have at least one pure child and sufficient number of neighbours. Another under which children of latents with a causal edge are allowed given that they are non-Gaussian distributed. With these weaker assumptions when compared to previous works, the authors devise an algorithm that can identify latent linear models.", "questions": "- Given that the assumptions required are mostly on latent variables, is it possible at all to get an indication of when these assumptions might hold given a dataset?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- Really well written and structured\n- Claims are well justified and theory is very neat.", "weaknesses": "- The main weakness would be the empirical evaluation. Currently, the results are only for 10 models, and the standard deviation of the accuracy is not reported. A lot of the methods discussed are not compared against. For example: Huang et al. (2022), Xie et al. (2023b) just to name a few. \n- The fact that the experiments had to be deferred to the Appendix is an indication that this paper is too long already.\n\nMinor points: \n- It would be useful to readers to have graphical depictions for what causal graphs your algorithm does and does not allow. To further delineate from previous works, it may be useful to have depictions of graphs that previous works allow as well.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "m0U2oDV452", "reviewer": "Reviewer_y7UL", "summary": "The paper studies new identifiability criteria for linear SCMs with latent variables. They generalize several prior works on identifiability of latent variable SCMs.", "questions": "- First, part of Section 3 was not very helpful for me because the results are not established at this point.\n\n- The definition of the set $\\mathbb{S}$ seems to be missing. (only in Algorithm it becomes clear what it is).\n\n- I could not follow Assumption 2. Maybe this can be clarified. Does it mean $Nei(L)\\geq 4$ and, moreover, in the case where $Nei(L)=4$ such that there is one latent and three observed neighbours then there is a pure pair....?\n\n- Why does each variable need a latent parent? It would be nice to generalize the case without latent variables.\n\n- 'All assumptions allow\\textbf{s}'\n\n-'It is rather milder'\n\n- Did you normalize the data? I think it should be (I should not make a huge difference but potentially for threshold choices in your algorithm)", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper seems to generalize previous results in several directions.\n- As latent confounding is ubiquitous, an important problem is adressed.\n- The presentation appears to be sound and clear. I did not check proofs after C.7 but until then, I found no issues.", "weaknesses": "- Careful proofreading would improve the paper further\n- While there are several different results in the paper, it would be great if a common theme could be established, e.g., a more systematic understanding of the right identifiability conditions.\n- This might be a bit much to ask, but can the conditions be tested? \n- The graphical conditions are still quite restrictive (but probably unavoidable). An interesting direction might be to consider when can we answer some 'causal queries' without full identifiability under milder assumptions.\n\n\nOverall, I don't have major complaints, but I am a bit hesitant because I am not too familiar with the field.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kAhNez710J", "reviewer": "Reviewer_7d8K", "summary": "Most of the causal discovery approaches assume sufficiency constraint of the causal factors; this work aims to go beyond that, identifying the latent causal factors and the relation between them and observed features. Resulting in learning a full causal graph with observed and unobserved latent structures.", "questions": "Please refer to weakness section", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The authors do a great job of setting up the motivation and providing an exhaustive list of related works\n- The paper attempts to address the important problem in causal discovery", "weaknesses": "- Linear relations: authors make a linearity assumption between latent-latent, latent-observed, and observed-observed features. The linearity assumption between observed-observed features seems very strong \n- Generalised pure pair seems to be a very strong requirement; how do you ensure this is followed in practice? For that matter, how do you test for this?\n- Algorithmic description is missing; please provide a detailed description of the algorithm along with the intuition for the steps\n- I understand the limited space constraint, but it would be nice to have some details on the experimental setup and the results in the main paper and discuss their implications \n- The proposed method for finding all the generalised pairs is strongly dependent on relations between latent and observational factors being linear, which is not that convincing. It would be nice to see some discussion on relaxing this behaviour or ways to test this behaviour of real datasets\n- It would be useful to consider synthetic datasets with known latent nodes and their interactions and compute the standard metrics in causal discovery like SHD, SID \n\n- Presentation concerns: please introduce all the assumptions before referencing them for easier readability \n- The paper is not self-contained; please consider including a background section briefly describing previous methods which are directly involved in your framework", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)