Efficient and Trustworthy Causal Discovery with Latent Variables and Complex Relations
Authors: Xiu-Chuan Li
Tongliang Liu
Venue: ICLR 2025 Poster (2025)
Keywords: causal discovery
latent variables
complex causal relations
Primary area: causal reasoning

Abstract: Most traditional causal discovery methods assume that all task-relevant variables are observed, an assumption often violated in practice. Although some recent works allow the presence of latent variables, they typically assume the absence of certain special causal relations to ensure a degree of simplicity, which might also be invalid in real-world scenarios. This paper tackles a challenging and important setting where latent and observed variables are interconnected through complex causal relations. Under a pure children assumption ensuring that latent variables leave adequate footprints in observed variables, we develop novel theoretical results, leading to an efficient causal discovery algorithm which is the first one capable of handling the setting with both latent variables and complex relations within polynomial time. Our algorithm first sequentially identifies latent variables from leaves to roots and then sequentially infers causal relations from roots to leaves. Moreover, we prove trustworthiness of our algorithm, meaning that when the assumption is invalid, it can raise an error signal rather than draw an incorrect causal conclusion, thus preventing potential damage to downstream tasks. We demonstrate the efficacy of our algorithm through experiments. Our work significantly enhances efficiency and reliability of causal discovery in complex systems. Our code is available at: https://github.com/XiuchuanLi/ICLR2025-ETCD

Published as a conference paper at ICLR 2025
EFFICIENT AND TRUSTWORTHY CAUSAL DISCOVERY WITH LATENT VARIABLES AND COMPLEX RELATIONS
Xiu-Chuan Li
Tongliang Liu" Sydney Al Centre, University of Sydney
ABSTRACT
Most traditional causal discovery methods assume that all task-relevant variables are observed, an assumption often violated in practice. Although some recent works allow the presence of latent variables, they typically assume the absence of certain special causal relations to ensure a degree of simplicity, which might also be invalid in real-world scenarios. This paper tackles challenging and important setting where latent and observed variables are interconnected through complex causal relations. Under a pure children assumption ensuring that latent variables leave adequate footprints in observed variables, we develop novel theoretical re- sults, leading to an efficient causal discovery algorithm which is the first one capa- ble of handling the setting with both latent variables and complex relations within polynomial time. Our algorithm first sequentially identifies latent variables from leaves to roots and then sequentially infers causal relations from roots to leaves. Moreover, we prove trustworthiness of our algorithm, meaning that when the as- sumption is invalid, it can raise error signal rather than draw incorrect causal conclusion, thus preventing potential damage to downstream tasks. We demon- strate the efficacy of our algorithm through experiments. Our work significantly enhances efficiency and reliability of causal discovery in complex systems. Our code is available
INTRODUCTION
Causality is a fundamental notion in natural and social sciences, which plays crucial role in explanation, prediction, decision making and control (Zhang et al., 2018). Particularly, causality has driven signifi- cant progress machine learning (Yao et al., 2021; 2023; Huang et al., 2023; Hong et al., 2024; Lin et al., 2024; Sun et al., 2024). Uncover- ing causality through analysis of observational data, commonly known as causal discovery, has garnered significant attention. Most traditional causal discovery methods (Spirtes & Glymour, 1991; Chickering, 2002; Shimizu et al., 2006) assume that all task-relevant variables served, but in practice, we often fail to collect and measure all of them in practice. Some previous works can reveal causal relations between observed variables in the presence of latent variables, but their results are not informative of the number or the causal relations of latent variables. By utilizing linear models, some recent works can display latent variables and their causal relations explicitly in their results. However, they often assume the absence of certain special causal relations to ensure a degree of simplicity, including the measurement assumption (Silva et al., 2006; Xie et al., 2022) positing the absence of edges from observed variables to latent ones, the purity assumption (Cai al., 2019; Xie et al., 2020) positing the absence of edges between observed variables, and the no- triangle assumption (Huang et al., 2022; Dong et al., 2024) positing the absence of triangles formed by three mutually adjacent variables. Unfortunately, these assumptions fail in many real-world sce- narios. Consider the causal structure shown as Fig. 1 where L and O respectively denote latent and observed variables. Clearly, O2 - O3 violates the purity assumption, O - violates the measure- ment assumption, and I., O2 O3 violates the no-triangle assumption. This structure be found in business contexts, where 0,, I., O2, O3 refer to advertisement spending, consumer interest, product
0,
L
> O:
Figure 1: A causal struc- ture violating all of the purity, measurement, and no-triangle assumptions.
ob-
*Correspondence Tongliang Liu (tongliang. @

---

Published as a conference paper at ICLR 2025
views, and product sales respectively, In this paper, given observational data generated by linear non-Gaussian acyclic model (LiNGAM) with latent variables where latent and observed variables are interconnected through complex causal relations, that is, none of the above three assumptions is required, we aim to correctly identify the underlying complete causal structure, which is a directed acyellc graph (DAG) that explicitly represents both observed and latent variables along with their causal relations.
Adams al. (2021) first investigate the challenging setting with both latent variables and complex relations. They develop a causal discovery algorithm under the assumption which is exactly suffi- cient and necessary for identifiability of LiNGAM with latent variables, but requires the number of latent variables as prior knowledge and lacks robustness, hence is not advisable in practice. Sub- sequently, Jin et al. (2024) introduce a stronger assumption that latent variables have pure children, ensuring latent variables leave adequate footprints in observed variables. Under this assumption, they propose the first practical algorithm capable of handling this challenging setting, which recov- ers the causal graph in a bottom-up manner, progressing from leaves roots. Unfortunately, its has exponential time complexity with respect to the number of variables, substantially limiting its ap- plicability. In this paper, under a similar assumption also involving pure children, we propose far more efficient algorithm with only cubic time complexity. Our algorithm follows a bottom-up then top-down pattern. In stage it sequentially identifies latent variables through their pure children, progressing from leaves to roots. In stage 2, for variables not recognized as others' pure children in stage 1, it sequentially infers their causal relations, progressing from roots to leaves.
As mentioned above, we make a pure children assumption to enable a practical causal discovery algorithm. When this assumption holds, our algorithm can correctly identify the underlying com- plete causal structure. But when this assumption fails, the recovered causal graph may be incorrect, which is potentially harmful in practical applications. For instance. in financial markets, a plausible but incorrect causal conclusion might mislead investors to make poor investment choices and cause significant financial losses. To overcome this limitation, we additionally prove trustworthiness of our algorithm, meaning that it can raise an error signal rather than return an incorrect causal struc- ture when the pure children assumption is invalid. Specifically, if this assumption is violated, we prove at the end of stage 1, there exists unidentified latent variable an identified latent variable whose recognized pure children are not actually its pure children. In stage 2, this hidden risk will be triggered, prompting the error signal. To the best of our knowledge, there is a lack of similar results in the literature of causal discovery with latent variables!
The major innovations of our work are summarized as follows.
We investigate understudied and challenging setting in causal discovery where latent and observed variables are interconnected through complex causal relations.
Under a pure children assumption, we develop a series of novel theoretical results, leading to an efficient causal discovery algorithm, which can handle the setting with both latent variables and complex relations within polynomial time.
We prove trustworthiness of our algorithm, meaning that when the pure children assumption is invalid, it can raise an error signal rather than return an incorrect result.
In summary, our work significantly enhances efficiency and reliability of causal discovery in com- plex systems. It may both inspire further research in causal discovery and benefit research in natural and social sciences. Due to space limit, we defer detailed discussion on related works to App. A.
2 PRELIMINARY
We focus on the linear non-Gaussian acyelic model (LiNGAM) with latent variables whose graph structure Go is a DAG. Its vertex set is Vo L U Og where L and Og respectively denote the set of latent and observed variables. We augment Go to G by creating two children for every O E Og, each of which is O plus an independent -on-Gaassian noise. We denote the set of such created variables
Many works employ similar pure children assumptions. While the vast majority of them limit their scope to the scenario where the assumption holds, Silva et al. (2006) systematically analyze the case where the as- sumption fails, rigorously characterizing the potential mistakes. Although this is an insightful result. it does not directly enable us to determine whether the recovered causal graph is correct. Instead, we prove that emoo signal can be explicitly raised the assumption fails.
2

---

Published as a conference paper at ICLR 2025
L
6
0
6
6
0.
On
On
0n
Ou
On
O
(a)
Go: L [L) L4 Oo 10...... 016)
(b)
16 0 161.
Figure 2: An illustrative example of augmenting (a) 9o to (b) g.
by 01 and let 0 0. U I LUO. Trivially, identifying Go is equivalent to identifying g. An example is shown as Fig. 2. Because of the linearity, each variable V2 E V follows
V/ = Σ aijV; + EV,
(1)
VJEV
where Ev, refers to an exogenous noise. All exogenous noises have non- Gaussian distributions and are independent of each other. atj # 0 iff V is a parent of V,. Eq. (1) can also be written as
V = Σ mijev,-
(2)
VJEV
where M (1- with M and being matrices composed of my and ay respectively. By convention, we assume the distribution over V is both Markov and bottleneck-faibful (Adams et al., 2021) to G. Given V V. we denote its parents, children, neighbors, ancestors, and descen- dants by Pa(V), Ne()), An(V), and De(V). Particularly, a variable's ' ancestors/descendants do not include itself. We call a variable's ancestors/descendants plus itself its generalized ances- tors/descendants, denoted by GAn(V) and GDe(V). We abbreviate Uvev Pa(V) to PPa(V)
3 EFFICIENT CAUSAL DISCOVERY
In this section, we develop a series of novel theoretical results under Asmp. 1, leading to an efficient causal discovery algorithm with only cubic time complexity.
Definition 1. (Pure child) We say Vz is a pure child of V1, denoted by V2 e PCh(Vi), (f Pa(V2) (V1) and (ii) VV DP(V)),
Example. In Fig. 2(a), PC = 10,.0s.00 0o). On & PCh as (a (L2, 010) # (L2). O & &Ch as On E De (0 but (On))= 2.
Remark. This concept has been widely used in related works, there is no consensus its exact definition. For instance, a pure child in Silva et al. (2006); Kummerfeld & Ramsey (2016); Xie al. (2020); Li al. (2024) must an observed variable with no child, which is more restrictive than ours. In Jin et al. (2024), variable's 's pure child can have a descendant with multiple parents provided that these parents do not include the variable itself, which is less restrictive than ours.
Assumption 1. VL L, @PCh (L))))(() (L) 2 2 and @o (L) 3.
Example. The graph in Fig. 2(a) satisfies this assumption. For instance, PC) (L3, L4) and Ge (L1) L2, L3 L4. O2, O6).
Remark. This assumption allows each latent variable leave footprints observed variables ad- equate for identification. It naturally holds in the scenarios with many directly measured variables such as topic model (Arora et al., 2013). Similar assumptions involving pure children were also made in many previous works (Silva et al., 2006; Kummerfeld & Ramsey, 2016; Cai et al., 2019; Xie et al., 2020; Zeng et al., 2021; Chen et al., 2022; Xie et al., 2022; Huang et al., 2022; Chen et al., 2023; Dong et al., 2024; Jin et al., 2024; Xie et al., 2024).
Whiile the values of observed variables are directly accessible for causal discovery, causal relations of latent variables can only be inferred indirectly through their pure children (Def. 1). By introducing O₃ to create pure children for each observed variable, we can uniformly handle both latent and observed variables through analyzing their pure children, therehy eliminating the need to repeatedly distinguish between treatments of latent and observed variables, which keeps our care methodology clear.
3

---

Published as a conference paper at ICLR 2025
b
6
10
On
6
6.
a.
drot Bron Broh ouda duaa duot duot
Figure 3: Left: Initial H4, where Va and V& are marked in red and black respectively; Right: Initial H2, which is exactly Go. where Va and Ve are marked in red and black respectively.
3.1 STAGE 1: IDENTIFYING LATENT VARIABLES
High-level Overview, In stage 1, we identify latent variables through their pure children. Con- cretely, we initialize an active set Va as Og- First, we locate some variables that serve as pure children of others from the active set (Thms. 1 and 2). Second, we identify these pure children's parents (Thm. 3). Third, we update the active set by replacing these pure children with their parents. Repeating this process until the active set cannot be updated, all latent variables can be identified finally (Thm. 4). Clearly, we follow bottom-up pattern in stage 1. progressing from leaves to roots.
S Initialization. During stage I, we maintain two sets of variables Va. Vo and graph Hi over No V.. Initially, we let Va. Vo be Oo. Oj respectively and let V, E Pa" (V,) iff V E Og. O,, and V E Pa For G shown as Fig. 2(b). the initial H/ is displayed on the left of Fig. 3. Subse- quently, Va Vb. and H, will be updated following the rules described later in $ Update. Intuitively, Va consists of identified variables whose causal relations (i.e., both incoming and outgoing edges of the variable in the underlying causal graph) are not fully identified, V, consists of identified vari- ables whose causal relations are fully identified, and Hi consists of all identified causal relations. Clearly, Cond. holds initially, and we will show later Cond. always holds throughout stage
Condition 1. VV
H (V) = PCh $ (V): (2) VV E Va. Pa Hi (V) = 0, VV E Vb. |Pa* (V) = 1 and Ch²c ICh* (V)) 2 2, and Ch H (V) E PCh (V).
For ease of exposition, we denote VV(Va Vv) by Ve and the induced subgraph of G over V. U V by Hy. For G shown as Fig. 2(b), the initial Ve is exactly L and the initial H2 is displayed on the right of Fig. 3, which is exactly Go. Intuitively, while Va U V,, consists of all identified variables, Ve consists of all unidentified variables. While Hi consists of all identified causal relations, H2 consists of all unidentified causal relations.
Locating Pure Children. Ideally, we want to locate pure children in a single step, but this is infeasible because of the existence of complex causal relations. Instead, we first locate identifiable pairs (Def. 2) from V. (Thm. 1) and then locate pure children from these identifiable pairs (Thm. 2). Definition 2. (Identifiable pair, IP) We say (V1, V23 S Va is an IP, denoted by (V1, V23 e 8, if
(1) Pa Ho
PaH (V22= = (V1), 2h (V2) = 0, and Ne H: (V)) # 0. We denote this by { {V1, V23 E S1; or Ha (V2) (Vo), Ch²((v)) = Ch Ch2) 0, and Vo E Va or Ne HE (Vo) 122) # 0. We denote this by (V1, 122 E S2: or
(2) 3VD E Va U V V.V,V, V23 s.t. Paa)
(3) 3% E V. U V.VV, 1/2) s.t. (Vi) (Vo), Ch Ch+)(Vv) = (V2), Path (12) = (Vo. Vi), and
Ch ChHo(V) (V2)= 0. We denote this by (V1, V2) S3.
Example. In the right sub- figure of Fig. 3. S (10), (0,, 0g). ( 0₂) ) 10 013), (0 14). (0 014) (015.
(10g, (4, Osh. [10 0n1))
Intuition. Although H2 is unknown, we will show later that identifiable pairs can still be lo- cated from V. via statistical analysis (Thm. 1), this is what "identifiable" means. The connection between identifiable pairs and pure children are as follows:
(1) If (V, V22} E St, V22 is V 's pure child or V2 is Vz's pure child.
(2) If (V, V22} e S2, V1 and V22 are both pure children of Vn.
(3) If [V, V2} E S3, neither Vi nor V22 is a pure child of any other variable.
Definition 3. P'seudo-residual (Cai et al., 2019)) Given three variables V1, V2, V3 s.t. Cov(V2, V/) 0, the pseudo-residun of V1, V2 relative to V3 is defined as
Cov V3) R(V, 1211,) = V1- Cov(V2, VT))
V/2
(3)
4

---

Published as a conference paper at ICLR 2025
L
2
On
On
0x
0.
r dnos Daati Puat Durta Pudaa Dutbe Groth a%
Figure 4: Left: H1 after the first update, where Va and V are marked in red and black respectively;
Right: H2 after the first iteration, where Va and Ve marked in red and black respectively.
v Onda
6
6
On
ON
O..
6. r. 6i
Ou Crio Cy
Figure 5: Left: H1 the end of stage 1, where V and Vb marked in red and black respectively;
Right: H2 at the end of stage 1, where Va and Vo are marked in red and black respectively.
Intuition. Pseudo-residual is simple variant of the conventional residual. The former reduces to the latter when V/2 V/3 Before Cai et al. (2019), similar concepts have already been used by earlier works (Drton & Richardson, 2004; Chen et al., 2017).
Theorem 1. V(V, V S Va. (V, S iff there exists V& E VaMV, CVv(V, Cov)oo(V Vx) 0 and for each such VR, R(V,V,IVV, Va V)).
Vy) s.t. Cov(V, Vy)
Remark. This theorem provides a method for locating identifiable pairs from Va via statistical analysis. In principle, need to do independence test for each Vk. But in fact, it is sufficient to only consider any single V& (see Prop. in App. C.2.1), reducing the time complexity.
Definition 4. (Quintuple constraint) We say (V1, 1/2, V3, Va. Vs) satisfies the quintuple constraint if there exist a, B s.r. V1 + aV3 + BV4 IL V/2 and Cov( V1 aV3 + BV4, Vs) = 0.
Theorem 2. V(V. Vj} E S, let (Vi, Vú) Ch2 (V:).
(1) R(V,, VvlV,) Vi, iff (V, Vj} 31 and Vi Pa
(2) Suppose (V, Vi} & Sj. Vyr ESM(V, s. (Vr, Vy+ n (V. vy) * only if (but not
if) (V, Vj} S2.
(3) Suppose (V,, Vj) S, 3Vv, V1) UCh (VaVV, VJJ) s.t. (Vi, Vn, Vj. V&, Vi) satisfies the quintuple constraint iff (V. Vj) 33 and Vi E (V))
Remark. This theorem provides method to divide into S1. 33 via statistical analysis, from which we can easily locate pure children. Given (V, Vj) e 3, we first check whether (V, Vj) S based (1). If it is and V, Pa&(V)). then Vj is Vj's pure child. Otherwise, further check whether (Vi, Vi} $2 based on (2,3). is, then both V and Vj are pure children of another unknown variable; otherwise, they not.
& Identifying Pure Children's Parents. As mentioned in Rem. of Thm. 2, for any pair in &2, its parent is unknown. To avoid duplicate identification of latent variables, we need to check whether its parent is in Va or Va (Thm. 3(1)) and whether it shares the parent with other pairs in S2 (Thm. 3(2)..
Theorem 3. (I),(V, Vj} Sz, O Pa Vi)) V. (V,, Vy) E S s.t. (V. (VV Vy} # 0. (2) V(VV Vy}, (Vr, Vy)) c S2, Pa ((V. = PP ((V),Vy) iff (Vv,, Vyr) ) e 82 s.t.
(V, V2} (Vrr, V # 0 and (Vr. Vp (VPr, Vir} # 0.
Example. In Fig. 3, an example of (1) is that (V, Vi}= = {0,, 0t) and (V,, Vy) (0,, 03); example of (2) that (V, V,) = (0,, 0g) and (Vr, Vy) (Vr,, ) (07, 0g).
Update. For pairs in St, we move the children in them from V, to V, and add edges from parents to children into Hi. For pairs in S2 whose parents are in V. rather than V.. we merge those pairs that share a common parent into a set. In particular, if a pair does not share a common parent with any other, it is itself set. For each variable into V. as the its parent, and add edges from its parent to its all variables into H,. For initialization shown as Fig. 3, the updated result is shown Fig. 4.
move it from V. to Vp, create and add a latent
5

---

Published as a conference paper at ICLR 2025
Algorithm 1: Stage 1: Identifying latent variables (overview)
Input: Observed variables Og and Oj
Output: V. a- Vb. and HH1
Initializing Va. Vb, and H4 following $ Initialization in Sec. 3.1. while the current V, is not identical to the previous Va do
Locating identifiable pairs 8 from Va based on Thm. Locating pure children from identifiable pairs 3 based on Thm. 2.
Identifying pure children's 's parents based on Thm. 3. Updating Va. Vb. and H4 following $ Update in S.c.
end
Repeating This Process. After update, Cond. 1 is still valid (see Prop. 2 in App. C.2.1). By induction, we can repeat the above process until Va cannot be updated. Finally, all latent variables can be identified (Thm. 4). For & shown as Fig. 2(b), the final result of stage is shown as Fig. 5. An overview of our algorithm in stage is shown Alg. while a detailed version is deferred to Alg. 3 in App. E. It has 0 (R(Ool)) complexity where R is the number of iterations.
Theorem 4. 3 U2 = 0, V O.
Remark. If both 3 and 8 are empty, then V. cannot be updated, that is, stage comes to end. At this moment, Ve = 0, which means that all latent variables are identified.
3.2 STAGE 2: INFERRING CAUSAL RELATIONS
High-level Overview. For variables recognized as others' pure children in stage (i.e., Vo the end of stage 1), their causal relations are fully identified in H4. The aim of stage 2 is to infer those unidentified causal relations, i.e., to recover H2 among Va Ve at the end of stage 1, when V = based on Thm. 4. We initialize an active set U, as Va at the end of stage 1. First, we identify root variable in the active set (Thm. 5). Second, we estimate the root variable's effects on others (Thm. 6). Third, we remove the root variable from the active set and also remove its effects on others. Repeating this process until there no variable in the active set, we can estimate all causal effects and then recover H2. Finally, a top-down pattern in stage 2, progressing from roots to leaves.
obtain & by combining Hi with H2. Clearly, follow
S Initialization. We initialize Ua V at the end of stage 1. For the sake of uniform processing, we view observed variables in Ua as latent variables, and assign each V2 E Ua with two observed surrogates X2i-1 and X2i, which can be any variable in GDe Hi (V,, ) n O and GDe (V₁,) n where (V,, V22 S Ch H ( (V)). Taking H, shown on the left of Fig. 5 as an example, two observed surrogates of can be 012 and Ois while observed surrogates O can be O and 0" Clearly, Cond. holds initially (e'x, 0 for any j). We will show later Cond. always holds throughout stage 2.
Condition 2. VV) U., De (V)) E U.. (2) E U., X2i-1, Xzi can be written as
X2-1 = C2
Σ VyEU,
mijev, + exu-1 + e'xy_'i
X2i =
Σ
mijEv, + exx, + exxy
(4)
VyeU,
where EV,..... EV,, ex,...,,ee... (exx,''x ex..... é' ''Xmn (d'xs ex..... d'xen) are mutually independent. Without loss of generality, we assume each c is positive and each Ev, has variance 1.
S Identifying a Root Variable. This can be accomplished based Thm. 5.
Theorem 5. VV, E Ua, An (V-) n U 0 Vf E UA((V)), R(X2j-1, X2--1 (22) IL X2i-
S Estimating the Root Variable's Effects. This can be accomplished based Thm. 6.
RReaders may have such question: how to test independeencecorrllaiion involving latent variables. For any latent variable L E Va U Vb. let O be its any observed descendant H4. With the fact implied by Cond. that can be expressed as scaled L plus noise independent of all variables except for L's descendants in Hi (this can also be implied by Cond. 3 in Sec. 4.1), any independenceecorrllttioo in our theoretical results involving 1. holds iff it holds when I. is replaced with Ó. Therefore, when need to test independennee/comelation involving latent variable, we can directly replace it with its any observed descendant in Hj.

---

Published as a conference paper at ICLR 2025
Algorithm 2:
Stage 2: Inferring causal relations (overview)
Input: Va. Vb. and Hi output by Alg.
Output: complete causal structure G Initialize U, following $ Initialization in Sec. 3.2.
while U, 0 do
Identifying a root variable V; E Un based on Thm. 5. Estimating V; is effects other variables based on Thm. 6.
Removing Vi from U, and updating X2j-1. X2j for each Vj E U, following Eq. (6).
end
== Hi U12 where H2 is recovered from the estimated effeets.
Theorem 6. If satisfies Thm. then Cov(X2i-1, X2i) c2i-1C2 and e U.\.).
Cov( X21-1, X2)) ) Cov(X2-1, Cov X2j-1) = 02-102023-11021 (5)
sgn(mmji) =sgn( (ov(XXj-1.X3)
Besides, VV& E VaaUa. =0.
Remark. At the current iteration, mjj cannot be determined since c2j-1 C2j is still unknown. Later, when y becomes the root variable, c2j-1C2j is known and myj can be determined.
Removal. We remove the identified root variable V; from Ua and eliminate its effects on X21-1. X2, following Eq. (6) for each Vj E Ua.
X2)-1 := 1
X2j X2j-
(6)
Repeating This Process. After removal, Cond. 2 is still valid (see Prop. in App. C.2.2). By induction, we can repeat the above process until there is no variable in Ua. Finally, all causal effects can be estimated, from which H2 can be recovered following Eqs. (1) and (2). Combining Hi with H2, we can obtain G. An overview of our algorithm in stage 2 is shown Alg. 2 while detailed version is deferred Alg. App. E. has (((all time complexity.
3.3 SUMMARY
Theorem 7. Suppose the observed variables are generated by a LiNGAM with latent variables sat- isfying the bottlenekkfaithhfuree assumplion and Asmp. 1, in the limil of infinite data, our algorithm correctly identifies the underlying complete causal structure.
TRUSTWORTHY CAUSAL DISCOVERY
In this section, we prove that our algorithm is trustworthy in the sense that raise error signal rather than return an incorrect result if Asmp. is invalid. This is quite challenging since we need precisely characterize the behavior of our algorithm when Asmp. I is violated, that is, have to carefully examine, modify, and re-prove all theoretical results in Sec. 3 in the case without Asmp. 1.
Definition 5. (Paired pseudo-pure children) We say (V2, V3} is pair of pseudo-pur children of denoted by (V2, V3) P'Ch(VV), (i) Pa (V2, Vs)) {V1,, (ii) UP((Ps V3)) V2, V/) 0. (ii)) V22 E Ne(V;), V3), and (iv) VV UDe (VV2, V,). [Pa(V)] 1.
Example. In Fig. 2(a), P²Ch(L2) 100 Ont). In Fig. 6(a), {L, V23 & P'Ch(Vi) since V4 UDe(LL VLL V2J but [Pa(Va)] 2.
Intuition. With the edge between V/2 and V3 removed, they both become pure children of V1.
Definition (Pathological variable, PV) Given a latent variable we say a type-I PV
(I-PV) if Pa(L) (V1) and Ch(L) (V2, Vs. V4} where Pa(V,) = LV. [Pa(V)] 1 for each V e De(V2), and ChCh(() ((V,, V4]). We say L a type- PV (II-PV) if Pa(L) Ch(L)
(V1, V2, V1, V4), and P'Ch(L) [(V1, 12), (Vs, Va)). is PV if is either I-PV or II-PV.

---

Published as a conference paper at ICLR 2025
Remark. a I-PV shown as Fig. 6(a) exists in Go. running our algorithm, there might be V1 Va and Ch² (Vi) {L. V2} sometime; if II- PV shown as Fig. 6(b) exists in Go. there might be L E Va and (L) {Vi, 12} sometime. In both cases, neither Ch Hi (L) s PCh (L) nor {Ch (L)) = P'Ch (L).
Vs
V/
(a)
(b)
Figure 6: Illustration of (a) I-PV and (b) II-PV.
A pathological variable must satisfy many restrictive conditions, including but not limited to (1) it is latent variable; (2) it has just the right number of parents and children; (3) its each descendant has the just right number of parents.
Assumption 2. (1) E L, V E VoML), (L & Ch (V). (V) E Vo. Ch (V) is the unique minimal bottleneck (see Def. 7 in App. from Ch Oo. (L) VL L. L is not PV.
Remark. It is infeasible to achieve trustwor- thiness without any assumptions. For instance, suppose Go is shown as Fig. 7(a), then the ob- servational distribution (i.e. p(O), O2, 03)) can also be explained by the causal graph shown as Fig. 7(b) that satisfies Asmp. I, so Fig. 7(b) will be returned as the result and no error signal will be raised. To avoid such cases, we blend (1) and (2) from Adams al. (2021) which are necessary for identifiability of LiNGAM with latent variables. Besides, (3) is technical assumption that significantly eases the readability and accessibility of the proof as it ensures that for every V E Va either Ch Ch" (V) s PCh (V) or (Ch* (V))= paCh 9 (V). Considering that (3) is rather weak since a PV must satisfy many restrictive conditions, does not seriously damage the generalizability of our results.
L
Le
L
6
02
0,
0
O2
(a)
(b)
Figure 7: The observational distribution gen-
erated by (a) can also be explained by (b).
4.1 STAGE 1: IDENTIFYING LATENT VARIABLES
High-level Overview. We provide a variant of each theoretical result in Sec. 3.1. At the end of Sec. 3.1, all latent variables are identified and each variable's recognized children are all its actual pure children. But the end of this section, there is an unidentified latent variable or an identified latent variable whose recognized pure children are not actually its pure children. This potential risk will be triggered in stage 2 such that an error signal can be raised.
Condition 3. YV) YV E Vo, IPaHi (V) and Ch²c
M (V) = PCh (V); PCh
YV Va. Pa (V)
and |Ch (V)1 2 2. If Ch (V) & PCh&(V), then (Ch" other conditions (more details are deferred to App. C.3.1).
9 (V) and V satisfies some H (V)) = p²Ch
Remark. It variant of Cond. 1. Note that (Ch Hi (V)) p'th @ (V) implies that |Ch H4 (V)) 2.
Theorem 8. V(V, Vj} Va. Vii $ iff there exists V& VaV(V, Vj} s.t. Cov(V, Vy) Cov(V, Vov (V,. Vx) # O and for each such Vs, R(V, VylV)) a Va VV.
Remark. It is identical to Thm. 1, so the identifiable pairs can still be located from observed variables correctly and exhaustively.
Theorem 9. V(V. Vy} e, let (V,, Vv) S Ch*H (V)).
(1) RV,,, VylV,, V2, if' (V, V/) E 3 and PV)(V))
(2) Suppose (V, Vi} $ St, 3(Vr, Vy) SVLV, VJH s. (Vr, Vy- n (V. Vy} * only if (but not
if) (V, Vy} E S2.
(3) Suppose (V, Vi} & 31, (V,, Vi S UCh (V. VJJ) s.t. (V, V Vj. Vz, Vi) satisfies the quintuple constraint only if (but not if) (V. V2} e S, and V. E Pa (V,).
Remark. (1,2) here are identical to (1,2) in Thm. 2 while (3) here is different from (3) in Thm. 2. Denote the result of our algorithm at this step by 5, 32. St. this means that all pairs in Si will
8

---

Published as a conference paper at ICLR 2025
be incorporated into $1, all pairs in S2 will be incorporated into $2, but some pairs in 33 will be incorporated into S2 rather than $3. Formally, there is $ = St. &2 2 $2, and 33 S S3.
Theorem 10. (I) VIV, ViV, e &2 (VV. ViH) & Va iff ((V, Vy) E 8, s.t. (%, Vi O (Ve, * 0. (2) V([K, VyJ. (V,. Vyll s by P Vjt) N ((Vv if 3(Ve, Vyr) $2 s.t. VV O (Vr, Vyr) 9 and (Vr, Vy) (Vr, Vyr) # 0.
Remark. Similar to Thm. 3, it also guarantees no duplicate identification of latent variables.
Theorem 11. Asmp. 1 is invalid, when 8 U$2 0, Ve # 0 or there exists L E Va s.f. Ch²i g PCh (L).
Remark. It is variant of Thm. 4, which means that the end of this section, there is unidenti- fied latent variable (e.g., Fig. 8(b)) or an identified latent variable whose recognized pure children (i.e., children in H() are not actually its pure children (e.g.. Fig. 8(d)).
L.
O.
O₂
bn l e b 8 0. 0.
O. O. O. & d. d. 0.
(a)
(b)
(c)
(d)
Figure 8: Suppose Go is shown as (a), Hi at the end of stage 1 is shown as (b), where V. = { # #0.
Suppose Go is shown as (c), Hj at the end of stage 1 is shown as (d), where L1 E Va. Ch 71 (L1) (02, Os) & (L1).
4.2 STAGE 2: INFERRING CAUSAL RELATIONS
S High-level Overview. We provide variant of Thm. Thm. 12. In Sec. 3.2, there always exists a variable satisfying Thm. 5 at each iteration. But in this section, there exists no variable satisfying Thm. 12 some iteration, when error signal be raised.
((""(()) (V,) s &Ch (V)). (V) U De S U. U... Condition VV ValUa, Ch²
(3) VV, E Ua. X2i-1, X2i can be written as
X2-1= = C21-1
Σ
mijEv, + exx-1 + e
X21 =
Σ VyEU,UV.
mijEy, exx + e'xy>
(7)
VyeU,.N.
where Ey, EVA, (xx,,exs).... (exmo. ex,,, (e'x, "x,,.. exmn-)) ('x, 6xm are mutually independent and Vj s.t. Ch Ch"'(V) (V,) & PCh&(V)), ex-y11 11 EXay Without loss of generality, we assume each C2i-1 is positive and each Ev, has variance
Remark. a variant of Cond.
Theorem 12. VV, Ua. An (U))nU = and Ch*i PCh9 if Va\iV) 11 X21-
Remark. It is a variant of Thm. 5, which implies that if at some iteration, there exists no V; E U s.t. An #6 (V,) n (U, VV) = 0 and Ch²f S PCh PC))(V)), we cannot find a V2 E U, satisfying the independence condition, when an error signal can be raised. In fact, this must happen before Ua becomes an empty set, more details are provided in the proof Thm. 13.
4.3 SUMMARY
Theorem 13. Suppose the observed variables are generated by LiNGAM with latent variables satisfying the bottleneck faithfuunee assumption and Asmp. 2, if Asmp. 1 is invalid, in the limit of infinite data, our algorithm raises an error signal.
5 EXPERIMENT
We first use four causal graphs shown as Fig. 9 to generate synthetic data. For each graph, we draw 10 sample sets of size 2k, 5k, 10k respectively. Each causal strength is sampled from uniform

---

Published as a conference paper at ICLR 2025
Or + O.
0.
L.
O O2
6.
L.
0.
6.
Cn
0:
0.
Ok Cese
04
Oe
Oe
Oh
ch
a
Ch
2
C
Cre4
Figure 9: Causal graphs satisfying Assumption 1.
Table 1: Comparison on synthetic data. 1 means higher is better while means lower is better.
Bavor in
Latent Variebes L
Conees Cndkengg Kate
F1.Sext
Kunning 1im0l8)
2k
5x
10cc
24
10k
26
3K
T0V
SE
TOK
GIN
0,010.00
0.0:0.0
0.0:000
L00:0000
L00000000
1.000:0000
1/0050.00
L3030.00
121
1.39,013
LA3H0.16
Cise:
Po-LNNGAM
LaHME
0.260.4
0.3el1.5
0.150.3
1.1
0.000.0
0.2514
26
0.9240 16
00.44.0.117
0.98x0.07
01800e00225
1.00
0.523e0.11
0. 0,7000.1 10
0.93
1.5861.10
0.5960.04
1.3900.15 15
61.69211.9 19
65,
161st111
65.26420099 98
1.578l.1 14
Oars
0.000,0
0.1+0.3
0.000
0,9240
0.91+0.11 18
1.00
0..8
0.97+0.07
L00+0.00
1,800
2.18+0.33
2.49+6.1
GIN
01
0145
1.
17750100
1.99:8111
1.58
17150.18
LHHME
00150,0
0.0:0.0
(.RetUp
LUKt9.00
1.00
1.00 00
1.0000.00
1.0001.00
1.38,0115
1.5461134
1.
PO-LINGAM
0.440.5
0.1
0,73
1.94
0.7740.14
0.50=0.1
198:0.06
06
$8.9911087
17.5619.1
0.0x0.0
0.0e0u9
100+0.00
1.0000.00
1.00+0.00
1.00+0.00
10000.00
1.56+0
181+0.05
2.06+0.17
GIN
00:0.0
(1
100001.00
1700100
0.54540777
0.59H106
Cise
PO-LINGAM
LAHME
0.000.0
10:0.0
0.0
3.9
0.0
1
0.000=00000
0.25.0.22
00
0:00
27
0.91
0.00g00000
0.00050.00
0.5000.
06310.18 18
1100+00.00
0000+1.00
0.990.10
S6. 16.8
7.83e0.79 79
75,
75.78112007
K.1+0053
89 1048
10.30+).42
Ours
0,0:0,0
0.0:0.0
0,0:0.0
0.9%:9.04
1,00=0.00 000
1,0000000
0.92:9.10
0.99
0.9921.03
3.6420 1U
4.20+0.13
5.0280.14
GIN
0SHEL3
1
0.9+0
01155003
0020
0. F0HeCCI
1227112
0.01=
1.1188.11
Case 4
PO-LINGAM
LaEDMD
0.9.0.5
1880.
0.4
2,0
0.0
2,0
01
0.22
0.2260:02
0.71
0.2000.00
0. 0.20gz0 00
1.00:0.00
0,53.0.24 24
0.34 03
0.73+0.29
0.22+0.00
0.32+0.01
1.0000.00
36, 76.26.21. 13
2 2.27:4036
44.3119.78
26110.37
45.6514.3 3.39
3:2220.79
Ours
0.3
0.
0,020U
0.9120.15
1.0000000
1.00
0.5720011
1.0000.01
1.0010.00
4.30g0025
4.90291.33
5.9420.112
distribution over [-2.0, 0051 U 10.5, 2.0] and each noise is generated from the seventh power of uniform distribution. We compare our methods with GIN (Xie et al., 2020), LaHME (Xie et al., 2022), and PO-LiNGAM (Jin al., 2024). We use 3 metrics evaluate the performance, including (i) Error in Latent Variables, the absolute difference between the estimated number of latent vari- ables and the ground truth one; (ii) Correct- Correct-Ordering Rate, the number of correctly estimated causal ordering divided by the number of causal ordering in the ground-truth graph; (ii) FI-Score of causal edges. The results are summarized in Tab. 1, where we also report the running time. In particular, we set the size of the largest atomic unit in GIN and PO-LiNGAM to I for a fair comparison.
With sufficient samples, all methods can handle case properly. GIN does not perform well in case 2 where some latent variable has no observed pure child. Both GIN and LaHME are not suitable for case and case 4 where the purity or measurement assumption is invalid. While PO-LiNGAM and our algorithm can both handle all cases properly, ours is far more efficient. PO-LINGAM alternates between inferring causal relations and inferring causal relations from leaves to roots, whereas ours first identifying latent variables from leaves to roots and then infers causal relations from roots to leaves. The efficiency gap arises from distinct approaches for inferring causal relations. Take case 3 as an example, PO-LiNGAM first identifies 09 leaf node by finding subset P S (g){ s.t. a particular linear combination of P U {0g} is independent of On' (Og), where P is exactly Og's parents (O5, 07}. In contrast, our algorithm first identifies O as a root node because for any O, E ),, R(X2-1, X1) 11 X2. Clearly. PO-LiNGAM needs to traverse the power set of Oo\{Og} while the ours only needs to traverse (o\(O,) itself.
In addition, we also do experiments on data gener- ated by the graphs shown in Fig. 10, where Asmp. 1 is invalid. On 10 sample sets sized 10k for each case, while other algorithms all yield incorrect re- sults, ours raises an error signal 8 times in case 5 and 7 times in case 6.
L 0.
0
0
Y
4
4
0.
0,
0,
>
O.
0.
0,
0.
L
0 +
O+
+
O.
0.
O
Os
+ 0.
Case5
Case6
Figure 10: Causal graphs violating Asmp. 1.
We also apply our proposed algorithm to real-world data, more details are deferred to App. D.
6 CONCLUSION
In this paper, we focus on the setting where latent variables and observed variables are intercon- nected through complex causal relations. Under a pure children assumption, we propose an efficient algorithm, which is the first one capable of handling the setting with both latent variables and com- plex relations within polynomial time. Also, we prove trustworthiness of our algorithm. To the best of our knowledge, there is no similar result in the literature of causal discovery with latent variables.
Limitations. First, although Asmp. 1 allows the presence of complex causal relations, it is still somewhat restrictive, we will attempt to relax it without compromising efficiency significantly in our future work. Second, this work does not accommodate non-stationary (Liu & Kuang, 2023) and cyclic (Sethuraman et al., 2023) causal relations, on which we defer the research our future work.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
Tongliang Liu is partially supported by the following Australian Research Council projects: F1220100318, DP220102121, LP220100527, LP220200949, IC190100031, Xiu-Chuan Li is par- tially supported by ARC FT220100318.
REFERENCES
Jeffrey Adams, Niels Hansen, and Kun Zhang. Identification of partially observed linear causal models: Graphical conditions for the non-gaussian and heterogeneous cases. In Conference on Neural Information Processing Systems, pp. 22822-22833, 2021.
Kartik Ahuja, Jason S Hartford, and Yoshua Bengio. Weakly supervised representation learning with sparse perturbations. 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 on 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.
Sanjeev Arora, Rong Ge, Yonatan Halpern. David Mimno, Ankur Moitra, David Sontag, Yichen Wu, and Michael Zhu. A practical algorithm for topic modeling with provable guarantees. In International Conference on Machine Learning, pp. 280-288, 2013.
Johann Brehmer, Pim De Haan, Phillip Lippe, and Taco S Cohen. Weakly supervised causal repre- sentation learning. In Conference Neural Information Processing Systems, pp. 38319-38331, 2022.
Simon Buchholz, Goutham Rajendran, Elan Rosenfeld, Bryon Aragam, Bernhard Schölkopf, and Pradeep Ravikumar. Learning linear causal representations from interventions under general non- linear mixing. In Conference on Neural Information Processing Systems, pp. 45419-454444 2023.
Ruichu Cai, Feng Xie, Clark Glymour, Zhifeng Hao, and Kun Zhang. Triad constraints for learning causal structure of latent variables. 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 cumulants. In International Conference on Machine Learning, pp.
2023.
Bryant Chen, Daniel Kumor, and Elias Bareinboim. Identification and model testing in linear struc- tural equation models using auxiliary variables. In International Conference on Machine Learn- ing, pp. 757-766. 2017.
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, pp. 63550-655,.00 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 Conference Artificial Intelligence. pp. 3568-3576, 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 Conference on Uncertainty in Artificial Intelligence, pp. 443-452 2022.
Tom Claassen, Joris M Mooij, and Tom Heskes. Learning sparse causal models is not np-hard. In Conference Uncertainty in Artificial Intelligence, pp. 172-181, 2013.

---

Published as a conference paper at ICLR 2025
Diego Colombo and Marloes H Maathuis. Order-independent constraint-bused causal structure learning. Journal of Machine Learning Research, 15:3921-3960 2014.
Chenwei Ding, Mingming Gong, Kun Zhang, and Dacheng Tao. Likelihood- frree overcomplete ica and applications in causal discovery. In Conference on Neural Information Processing Systems, pp.
2019.
Xinshuai Dong. Biwei Huang, Ignavier Ng, Xiangchen Song, Yujia Zheng, Songyao Jin, Roberto Legaspi, Peter Spirtes, and Kun Zhang. A versatile causal discovery framework to allow causally- related hidden variables. In International Conference on Learning Representations, 2024.
Mathias Drton and Thomas S Richardson. Iterative conditional fitting for gaussian ancestral graph models. In Conference on Uncertainty in Artificial Intelligence, pp. 130-137, 2004.
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 on Learning Representations, 2024.
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, 2008.
Patrik O Hoyer, Dominik Janzing, Joris Mooij, Jonas Peters, and Bernhard Schölkopf. Nonlinear causal discovery with additive noise models. In Conference on Neural Information Processing Systems, pp. 689-696, 2009.
Biwei Huang, Charles Jia Han Low, Feng Xie, Clark Glymour, and Kun Zhang, Latent hicrarchical causal structure discovery with rank constraints. In Conference on Neural Information Processing Systems, pp. 5549-5595555 5561,55611222 2022.
Zhuo Huang, Xiaobo Xia, Li Shen, Bo Han, Mingming Gong, Chen Gong, and Tongliang Liu. Harnessing dittof-distribution examples via augmenting content and style. In International Con- ference on Learning Representations, 2023.
Yibo Jiang and Bryon Aragam. Learning nonparametric latent causal graphs with unknown inter- ventions. In Conference on Neural Information P Processing Systems, pp. 60468 60663,,653, 2023.
Songyao Jin, Feng Xie, Guangyi Chen, Biwei Huang, Zhengming Chen, Xinshuai Dong, and Kun Zhang. Structural estimation of partially observed linear non- gaussian acyclic model: practical approach with identifiability, In International Conference on Learning Representations, 2024.
Abram Meerovich Kagan, Yurij Vladimirovich Linnik, and Calyampudi Radhakrishna Rao. Char- acterization problems in mathematical statistics. 1973.
Bohdan Kivva, Goutham Rajendran, Pradeep Ravikumar, and Bryon Aragam. Learning latent causal graphs via mixture oracles. In Conference Neural Information Processing Systems, pp. 18087- 18101, 2021.
Lingjing Kong, Biwei Huang, Feng Xie, Eric Xing, Yuejie Chi, and Kun Zhang. Identification of nonlinear latent hierarchical models. In Conference on Neural Information Processing Systems, 2023.
Erich Kummerfeld and Joseph Ramsey, Causal clustering for 1-factor measurement models. AnM SIGKDD International Conference Knowledge Discovery and Data Mining, pp. 1655-1664, 2016.
Xiu-Chuan Li, Kun Zhang, and Tongliang Liu. Causal structure recovery with latent variables under milder distributional and graphical assumptions. In International Conference on Learning Representations, 2024.
Yexiong Lin, Yu Yao, and Tongliang Liu. Learning the latent causal structure for modeling label noise. In Conference on Neural Information Processing Systems, 2024.
12

---

Published as a conference paper at ICLR 2025
Chenxi Liu and Kun Kuang. Causal structure learning for latent intervened non-stationary data. In International Conference on Machine Learning, pp. 21756-1111111 21777, 2023.
Takashi Nicholas Maeda and Shohei Shimizu. Red: Repetitive causal discovery of linear non- gaussian acyclic models with latent confounders. International Conference on Artificial Intel- ligence and Statistics, pp. 735-745, 2020.
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:1 100--104,, 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.
Anastasia Podosinnikova, Amelia Perry, Alexander S Wein, Francis Bach, Alexandre d' A'premont, and David Sontag. Overcomplete independent component analysis via sdp. In International Conference Artificial Intelligence and Statistics, pp. 2583-2592, 2019.
Muralikrishnna G Sethuraman, Romain Lopez, Rahul Mohan, Faramarz Fekri, Tommaso Bian- calani, and Aan-Christian Hütter. Nodags-flow: Nonlinear cyclic causal structure learning. In International Conference on Artificial Intelligence and Statistics, pp. 637 2023.
Shohei Shimizu, Patrik Hoyer, Aapo Hyvärinen, and Antti Kerminen. linear non non-gaussian acyclic model for causal discovery. Journal of Machine Learning Research, pp. 2003-2030, 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- non-gaussian structural equation model. Journal of Machine Learn- ing Research, 1111225-1240 2011.
Ricardo Silva, Richard Scheines, Clark Glymour, and Peter Spirtes. Learning the structure of linear latent variable models. Journal of Machine Learning Research, 7:191-246, 2006.
Peter Spirtes and Clark Glymour. An algorithm for fast recovery of sparse causal graphs. Social Science Computer Review, 9:62-72, 1991.
Peter Spirtes, Christopher Meek, and Thomas Richardson. Causal inference in the presence of latent variables and selection bias. In Conference on Uncertainty Artificial Intelligence, pp. 499-506, 1995.
Chandler Squires, Anna Seigal, Salil Bhate, and Caroline Uhler. Linear causal disentanglement via interventions. In International Conference Machine Learning, pp. 32540-32560, 2023.
Yuewen Sun, Biwei Huang, Yu Yao, Donghuo Zeng, Xinshuai Dong, Roberto Legaspi, Kazushi Ikeda, Peter Spirtes, and Kun Zhang. Identifying latent state-transition processes for individual- ized reinforcement learning. Conference on Neural Information Processing Systems, 2024.
Tatsuya Tashiro, Shohei Shimizu, Aapo Hyvärinen, and Takashi Washio. Parcelingam: A causal ordering method robust against latent confounders. Neural Computation, 26:57-83, 2014.
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 non-gaussian latent hierarchical structure. In International Conference 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. Journal of Machine Learning Research, 25, 2024.
13

---

Published as a conference paper at ICLR 2025
Yuqin Yang, AmirEmad Ghassami, Mohamed Nafea, Negar Kiyavash, Kun Zhang, and llya Sh- pitser. Causal discovery in linear latent variable models subject to measurement error. In Confer- on Neural Information Processing Systems, pp. 874-886, 2022.
Yu Yao, Tongliang Liu, Mingming Gong, Bo Han, Gang Niu, and Kun Zhang. Instance-dependent label-noise learning under a structural causal model. In Conference on Neural Information Pro- cessing Systems, pp. 1409-4420. 2021.
Yu Yao, Mingming Gong, Yuxuan Du, Jun Yu, Bo Han, Kun Zhang, and Tongliang Liu. Which is better for learning with noisy labels: the semi-supervised method or modeling label noise? In International Conference on Machine Learning, pp. 39660-39673, 2023.
Yan Zeng, Shohei Shimizu, Ruichu Cai, Feng Xie, Michio Yamamoto, and Zhifeng Hao. Causal dis- covery with multi-domain lingam for latent factors. In International Joint Conference Artificial Intelligence, 2021.
Jiqqi Zhang, Kristjan Greenewald, Chandler Squires, Akash Srivastava, Karthikeyan Shanmugam, and Caroline Uhler. Identifiability guarantees for causal disentanglement from soft interventions. In Conference on Neural Information Processing Systems, pp. 50254-50292, 2023.
Kun Zhang, Bernhard Schölkopf, Peter Spirtes, and Clark Glymour. Learning causality and causality-related learning: some recent progress. National Science Review, 5:26-29, 2018.
14

---

Published as a conference paper at ICLR 2025
A RELATED WORKS
Traditional causal discovery methods mostly assume that all task-relevant variables are ob- served (Spirtes & Glymour, 1991; Colombo & Maathuis, 2014; Chickering, 2002; Shimizu et al., 2006; 2011; Hoyer et al., 2009; Peters et al., 2014; Mooij et al., 2016). Unfortunately, latent variables are pervasive in practice, in which case these methods usually introduce spurious causal relations. This limitation has inspired extensive works on causal discovery with latent variables. Some early works can reveal causal relations between observed variables in the presence of latent variables, but their results are not informative of the number or the causal relations of latent variables. Specifically, some works (Hoyer et al., 2008; Tashiro et al., 2014; Maeda & Shimizu, 2020; Yang et al., 2022: Cai et al., 2023) explicitly assume that latent variables are all root variables, which means that there exists no causal relation between any two latent variables. Others (Spirtes et al., 1995; Claassen et al., 2013; Claassen & Bucur, 2022) allow the presence of causally-related latent variables, but they cannot identify latent variables, which means that both the number and the causal relations of latent variables
unknown. By utilizing linear models, others can identify latent variables and infer their causal relations (Silva et al., 2006; Anandkumar et al., 2013; Kummerfeld & Ramsey, 2016; Cai et al., 2019; Xie al., 2020; Zeng et al., 2021; Adams al., 2021; Chen et al., 2022; Xie et al., 2022; Huang et al., 2022: Chen et al., 2023; Dong et al., 2024; Jin et al., 2024; Li et al., 2024; Xie et al., 2024). Among the latter line of works, the measurement assumption is employed by all except Adams et al. (2021): Dong et al. (2024); Jin et al. (2024) and the purity assumption is used by all except Silva et al. (2006); Kummerfeld & Ramsey (2016); Adams et al. (2021); Dong et al. (2024); Jin et al. (2024); Li et al. (2024); Xie et al. (2024). In addition, Huang et al. (2022) employ the non-triangle assumption that any three variables are not mutually adjacent while Dong et al. (2024) weaken this assumption slightly by allowing three mutually adjacent variables only if they are all observed variables. That is, only Adams et al. (2021) and Jin et al. (2024) can handle setting where latent variables and observed variables are interconnected through complex causal relations, which are of particular relevance to our work.
Adams et al. (2021) the first one investigating the important and challenging setting with both latent variables and complex relations, they present the sufficient and necessary condition for iden- tifiability of LiNGAMs with latent variables, which is a really profound theoretical contribution. Also, using this condition as the assumption, they develop a causal discovery method, which is un- fortunately inadvisable in practice as acknowledged by themselves. First, because overcomplete independent component analysis (OICA) which needs to know the number of source signals (Podosinnikova al., 2019; Ding et al., 2019), it requires the number of latent variables as prior knowledge and is computationally intractable. Given the mixing matrix returned by OICA, still needs to test which submatrices' singular values are exact zeros, which is rather sensitive to noise. Subsequently, Jin et al. (2024) strike delicate balance between theoretical identifiability and practical feasibility. Specifically, under a stronger assumption involving pure children similar to many previous works (Cai et al., 2019; Xie et al., 2020; 2022; Huang al., 2022; Dong et al., 2024), they propose the first practical algorithm capable of handling the setting with both latent variables and complex relations. But this algorithm has exponential time complexity with respect to the number of variables, seriously limiting its applicability. To overcome this limitation, under similar assumption also involving pure children that is moderately more restrictive than Jin et al. (2024)'s*, we propose an efficient algorithm which is the first one capable of handling the challeng- ing setting within only polynomial time. Our algorithm differs significantly from theirs. Specifically, their algorithm follows bottom-up pattern, which alternates between inferring causal relations and identifying latent variables, progressing from leaves to roots. Instead, ours follows a bottom-up then top-down pattern, which first sequentially identifies all latent variables, progressing from leaves to roots, and then sequentially infers causal relations, progressing from roots to leaves. Also, we prove trastworthiness of our algorithm, which means that it can raise an error signal rather than return an incorrect result when the pure children assumption is invalid. To the best of our knowledge, there is complete lack of similar results in the literature of causal discovery with latent variables.
based on
4On the one hand, our definition of pure child is more restrictive than Jin et (2024)'s as stated in Rem. of Def. 1, so our assumption is also more restrictive than theirs. On the other hand, the gap between these two assumptions is narrower than that between Adams et al. (2021)'s 's and Jin et al. (2024)'s because Adams et al. (2021) have absolutely need for pure children, so we say our assumption is "moderately" more restrictive than Jin al. (2024)'s.
15

---

Published as a conference paper at ICLR 2025
Besides work and that of Jin al. (2024), many previous studies that allow the presence of latent variables but not complex relations also make similar pure children assumptions (Silva et al., 2006; Kummerfeld & Ramsey, 2016; Cai et al., 2019; Xie et al., 2020; Zeng et al., 2021; Chen et al., 2022; Xie et al., 2022; Huang et al., 2022; Chen et al., 2023; Dong et al., 2024; Xie et al., 2024). While the vast majority of them limit their scope the scenario where the assumption is satisfied, Silva et al. (2006) systematically analyze the case where the assumption fails, rigorously characterizing the potential mistakes. For instance, their algorithm may fail identify some latent variables and may erroneously introduce an edge from a latent into an observed variable that does exist actually. Although this is an insightful result, it does not directly enable to determine whether the recovered causal graph is correct. Instead, we prove that an error signal can be explicitly raised if the assumption fails.
While the works discussed above all focus on the linear case, there are also some studies investigat- ing nonlinear problems, but most assume access to counterfactual data (Brehmer et al., 2022; Ahuja et al., 2022) interventional data (Ahuja et al., 2023; Jiang & Aragam, 2023; Buchholz al., 2023; Zhang et al., 2023). Notably, without structural restrictions such as the pure children assumption, linear causal models satisfying the measurement assumption prehensive interventional data obtained by intervening on each latent variable individually (Squires al., 2023). To the best of knowledge, in the presence of latent variables, only Kivva et al. (2021) and Kong et al. (2023) can handle non-linear problems through only observational data, but they both make rather strong assumptions. Specifically, Kivva et (2021) require that latent variables are discrete. Kong et al. (2023) require that the mapping from all exogenous noises to ob- served variables is invertible. We leave further research on nonlinear problems our future work.
unidentifiable without com-
B NOTATIONS
We summarize notations in Tab.
C PROOF
Definition 7. (Unique minimal bottleneck) We say B is a bottleneck from to K (J. K, B need not be mutually disjoint) VJ e and K K, each directed path from J to K includes some B E B. Given a bottleneck B, from J to K, if any other bottleneck B + B, satisfying [B] Z [Bi]. we say Bı is minimal bottleneck. Furthermore, if [ [Bt], say B₁ is the unique minimal bottleneck.
Assumption 3. For every S V,K S V, B is a minimal bottleneck from J to K, then the rank of M is exactly [B), where M a submatrix of M with columns indexed by J and rows indexed by K and M is a matrix composed of mij in Eq. (2).
Intuition. This assumption implies that
(I) mij # Off E GAn(V)).
(2) Suppose mam mammammma # O, ma//ma # ma/mat iff there exist two non-intersecting paths from (Vz. Vi} to (V, Vz).
Remark. In the following proof, rather than working directly with the bottleneck faithfulness assumption itself, we only utilize these two properties derived from it.
For ease of exposition, given V V and V V, we abbreviate Pa(V) O V as Pay. in the following.
C.1 IMPORTANT LEMMAS
In this section, summarize several important properties of the pseudo-residual (Lem. 1) and the quintuple constraint (Lem. 2), which serve as the cornrrsonns of the proofs of many following theoretical results.
16

---

Published as a conference paper at ICLR 2025
Table 2: Summary of notations.
Notation
Description
First appeared
Original ground-truch causal graph
Sec.
L
Latent variables
Sec. 2
Original observed variables
Sec. 2
L Oo
Sec. 2
G
Augmented ground-truch causal graph
Sec. 2
O
Created observed variables
Sec. 2
O
Og U O
Sec. 2
V
Vo U O
Sec. 2
Pa(V)
Parents of V
Sec. 2
Ch(V)
Children of
Sec. 2
Ne(V)
Neighbors of V
Sec. 2
An(V)
Ancestors of V
Sec. 2
De(V)
Descoddanss of V
Soc. 2
GAn(V)
Generalized ancostors of V, that is, An(V) U (V]
Sec. 2
GDe(V)
Generalized descendants of V, that is, De(P) (V)
Sec. 2
PCh(P)
Pure children of V
Def. in Sec.
PCC((V)
Paired pseudo pureeeepueeeee children of
Det, 5 in Sec.
PDe(V)
Pure descendants of
Def. 8 in App. C.2.1
PeDe(V)
Pseudo pure descendants of
Def. 9 in App. C.3.1
Y.. Va
Two sets variables maintained during stage with specific initialization and update rules
Sec. 3.1
VVVV. Vz)
Soc.
A graph over V. V, maintained during stage with speciffic initialization update rules Soc. Induced subgraph G V. V.
Sec.
Identifiable pairs
Def. in
St.
of'S
Def. in 3.1
3r
by our algorithm when Asmp. invalid
Thm. See. 4.1
V//55
Pscudo-residual of relative V;
Def. 3 in Soc. 3.1
Active stage
Sec. 3.2
Harmois-Skitovitel (D-S) Theorem. (Kagan al., 1973) Suppose two random variables and V2 are both linear combinations of independent random variables (n:h:
Vi = Σ ains
1/2
(8)
Then, if V1 V2, each n, for which a,B; 0 follows Gaussian distribution. That is, if there exists non-Gaussian n s.t. a;ß; # 0, V1 M V2.
Definition 3. (Pseudo-residual) Given three variables V1, V2, V3 s.t. Cov V3) 0, the pseudo- residual of Vi, 1/2 relative to V3 is defined as
R(V, V3(1)) = Vi Cov(V1. V3)
1/2
(9)
Cov(V2, V3)
Lemma 1. Given V,, V2, V3, V4, Vs (it is possible that V3 V4 Vs) where Cov Co) V3)
Cov(V2, V3) # O,
(1) VfVi die+e, e and V22 d2e es where (5) (c. Vs. Vo), Var(e) # 0, and d1 then R(V, V2(V;) 11 V4.
(2) If there exists Vi s.t. only one of mi and my is non-zero and m4 # O, then R(V, V3/V3) N V4.
(3) If there exists V. V2 s.t. mym H.M.MMMMMMMaaih * 0 and mu/mij # m2i/2aj then
R RV1, VzlV)) X Va R(V, V2(Vs) N Vs.
17

---

Published as a conference paper at ICLR 2025
Remark. (1) provides a sufficient condition for independence involving the pseudo-residual to hold while (2, 3) provides two sufficient conditions for independence involving the pseudo-residual to not hold.
Proof. The proofs of are as follows.
(1) R(V. V2lV3) = (11e+e)) Cov(die+ef Va)
Cov(dzese, Val (d2e+e)) = (d1e+e)) =
= e Va-
(2) As only one of mi; and m2i is non-zero, R(V,, V2(V)) contains ev, Since mai * 0, based on D-S Theorem, R(V, V2(V)) M V4.
(3) As i * and mu/miy # m2//m2j. R(V, V2(V3) contains ev, or ev, Since maimsj 0, based D-S Theorem, R(V,, V2(Vs) и V4 R(V, V2(V3) ı Vs.
Definition 4. (Quintuple constraint) We say (V,, 122 V3, V4, V2)) satisfies the quintuple constraint if there exist a, B s.t. V1 + aV3 BV4 a V/2 and Cov(V) æV3 + BV4, V/) = =.
Lemma 2. Given V1, 22, V3, V4, Vs.
(1) If there exists Vi s.t. mymy # and my = m4: = 0, then (V1, V2, V3, V4, Vs) does not satisfy the quintuple constraint.
(2) Suppose e,, e, e, ei
es.e's E2 are mutually independent and V1. V2, V3, V4 can be written as
Vi =1= ni=eeetteettee 1/2 Y2er+Y2e)+ez V3= = +
V4 = dee; (10)
where Varle)) # O, d1d2d3d4 # O, and y1y2y3 # (2.a) If a (ej,e,, ey e'g, e')) and Cov(Vs.e;) # O, then (V,, V2, V3. V4, V/) satisfies the quintuple constraint; (2.b) If Vs Il (e,,e',, ef),, Cov(Vs, Cov(s, e # O, and A1/ # ///y,, then (V1, V2, V2, V4, Vs) does not satisfy the quintuple constraint.
Remark. (2.a) provides a sufficient condition for the quintuple constraint hold while (1, 2.b) provides two sufficient conditions for the quintuple constraint to not hold.
Proof. The proofs as follows.
(1) As mi 0 and ma: = m4i = 0, Vi aVss + BV4 contains Ev, Since m2: # 0, based D-S Theorem, for any 8, V1 + aV3+ BV4 x V2.
(2) V' a (ej,e',ed e e' e and Cov e;) # 0, let Cov(V + aV3 + BV4, V22 = 0 and Cov(V1 + aV3 + BV4, V/)=
have
A B O. Y1 + ay3 = 0.
then
Vi a.33 + BVg (d1 + Bai)e; (11 +yy)ey ei aae's + Be, ei ae's + Be' V2. 0, and d1/ds 11/11, let Cov(V, aV3 BV4, 1/2) 0 and Cov(VI +aV, BV4, V/)) 0, we have
If V/S (ej,ei, e²), Cov(Vs,,)
A A1 Bd4 0, Y1 ay3 #0
then
+ Vi+aV BV, (d) + + + (4l + ayz)ee + é ac's Be's
(11)
contains e; and ej. so Vi aV3 BV4 1 V/2
18

---

Published as a conference paper at ICLR 2025
C.2 PROOF OF THEORETICAL RESULTS IN SEC. 3
Definition 1. (Pure child) We say 1/2 is a pure child of V1, denoted by V22 E PCh(Vi), (f Pa(V2) (V1) and (ii) VV De(V2), [Pa(V) 1. Remark. Based on this definition, if V22 PCh(Vi), then Ch(V2) = PCh(V2).
Assumption 1. VL E L, |PCh c (L) 2 2 and |Nc (L) 2
Trivially, if Asmp. holds, then VL e L. |PCh (L) 2 and |Ne (L) 3.
C.2.1 PROOF OF THEORETICAL RESULTS IN SEC. 3.1
Condition 1. (1) YV Vb, |Pa %h (V) (V)) ICh* (V) (C))(V)) 2 2, and Ch² (V) PCh
and Ch (V) PCh (V); (2) W Va. Pa =0,
Before proving theoretical results in the main text one by one, we first introduce two corollaries (Cors. I and 2) readily derived from Cond. 1.
Corollary 1. (1) VV Vb. Ch (V) Ch*1(V) and (V) PP) (2) E V. CV)
CV² and (V Pa th (V): (3) VV E V.. (V) Ch (V) CV* and Pa
Pa (V).
Remark. This corollary reveals the properties of variables in Vo. Ve, and Va. (1) means that for each variable in Vp. its parents and children in the underlying causal graph G are exactly its parents and children in Hi. (2) means that for each variable in Ve. its parents and children in the underlying causal graph are exactly its parents and children in H2. (3) means that for each variable in Va. its children in the underlying causal graph & are the union of its children in Hi and its children H2 while its parents in G are exactly its parents in Hy. This corollary widely used in the following proofs. To maintain fluency, we will use it without further citation.
Proof. First, if V/ E Vo. then Ch²)(V)) = PCh (Vi) and there exists V, E Va U Vo s.t.
Paz (V)) (V,) based Cond. 1(1). Moreover, since (i) Ch Ch²'(V) (V)) PCh (V) if V E Vo based on Cond. 1(1) and (ii) Ch² CV²)(V)) s PCh V, Va based on Cond. 1(2), there always V, (V,). Therefore, we can conclude that PV (V,) = Pa Hi (V)) and Ch&(V)) PCh& (V,) = Ch (V,), this completes the proof of (1).
Second, if V; E Ve. based on (1) that was just proven, Ch (V:) n V, = 0 and Pa (V:) (V)) n V, = 0. which is equivalent to Ch (V:) Ch Ho (V,) and (V)(()) Pa He (V₂) based on the definition of H2, this completes the proof of (2).
Third, if V, V then Ch (V1) Ch. (V/) UCh Y.uv, (V)) = Ch (V) (V) (V Besides, since
PaH (V) 0 based on Cond. 1(2), Pa (V) Pa (V). This completes the proof of (3).
Definition 8. (Pure descendant) We say Vz is pure descendant of V,, denoted by V22 E PDe(Vi), if 1/2 U (De(PCC((V))
Example. In Fig. 2(a), PDe(L,) = (4g, L4, 01 033, 144 015, 016)-
Remark. Based on this definition, if 1/2 PDe(V1), then Ch(Vz) PCh(V2) and De(V)) PDe(V2).
Corollary 2. VV Vo. I (V) 2 2. If De (V)) = then D (V) (V)
Remark. This corollary means that each variable in Ve has least two pure descendants in V and it has exactly two descendants in V these two descendants are exactly its all pure children. Intuitively, this enables to identify variables in V. through analyzing variables in V..
Proof. Note that V. c L, VV e Ve, have & 2 and PCh9(V) V. UV.. If JPCh (V)l 2 2, have g (V)l 2 2 naturally. Otherwise, PDe (V) PCh (V) 0. Let
19

---

Published as a conference paper at ICLR 2025
Vi E PDe (V) s.t. Ch (V,) Va we have |PCh. (Vi) 2, |PDe (V) PCh & (Vi) 2 2.
Therefore, VV Ve, there is always IPDe (V) 2 2.
Following the above analysis, given V E Ve, for any V' E PCh.. (V), we have pD & (V') 2 2, so
[De (V)) 2 2/PCh (V)I+ PCh. (V)..
(12)
Note that
|PCh (V)) PChh @ V. (V)) + PCh V. (V)) 2 2.
(13)
if [De (V) 2, then PCh Ve (V) 0 and De (V) PCh (V). that is, De (V) (V)
Proposition 1. v(V, v,, VR, Vi) Va where Cov(V, V Cov Vov VW) 0 and Cov(V, Co) (V,, VI) # O, R(V. VylVe) L VaViV Vj) if VjlV) a VoV, Vy).
Remark. Given (V, Vj} Va. denote (V E VaMV, Cov(V, Cov(V, CVv V2) # # by Vij. this proposition means that there exists no (Vx, V/) s Vij s.t. R(V, Vy(Ve) V VaV(V. and RVV, VylV)) и VaVV, Vj). Therefore, if we want to know whether for each V Vij. R(V, VaM,, Vj}, we only need to consider any single V2 E Vij.
Proof. If R(V, VjlVe) II VaV(V, ViJ. then R(V. V2lV2) I1 V.. which means that Cov(R(V,, VylV)), Vi) that is, Cov(V,.V.) Cov(V,.) VE) VD) so R(V, Vy(V)) R(V, ViIVe) VaVVV, Similarly, if,,,, VIMD IL VaVV,, Vj). there is also R(V, VylV2) 1 PAM,,V O
Theorem 1. V(V. Vy} S Va. V S iff there exists V& Va Vy) s.t. Cov(V, Vÿ) Cov(V, Vx) (V,. Vx)) # 0 and for each such VR, R(V. Vj[Vk) a Val (V, Vy).
Proof Sketch. If (V, Vi} E S, we can prove correlation and independence based on Lem. 1(1).
Otherwise, for each possible case, can prove either non-correlation or dependence based on Lem. 1(2,3).
Proof.
"Only if"
(1) Suppose (V, Vi)+ E Sj. Let V e (V) without loss of generality and V E Na (V)), Hi (Vx) Vy}. Clearly, V,, V,, Vi are
we have GD Ho (V)), Vy} # o and let Vi GDe, correlated to each other. Also, = VV+ Vj = ajvV +v, where VV VaY(V, Vj), (0, Ev,) æ (V,, V/, V), so RVV, VjlV) д V VaV, Vj} based on Lem. 1(1). Combined with Prop. 1, we reach the conclusion.
(2) Suppose (V, Vý} Sz. Let (Va)(V)) = PV = (V&). V Va. we let Vm = Vx- Otherwise, let Vi E (ex) Vý). Similarly to fn. 5, we have GDe He (V)) Vj) # 0 and let Vm E GDD Hh (Vi) Vz). Clearly, Vi, Vj. Vn are correlated to each other. Also, V; = Vi + EV, Vj = ajxVe V + Ev, where VV E VaV(V, Vy). (EV, (ev, 1l (V,, Vn. V), so RV, VylVm) IL Val(V, Vj} based on Lem. 1(1). Combined with Prop. 1, we reach the con- clusion.
(3) Suppose (V, Vi} 33. Let E (V,) without loss of generality and Pa Similarly to fn. 5, we also have GDe Ho (VW)VV Vy} # 0 and let Vi E GDe Clearly, V,, Vj. Vi are correlated to each other. Also, V; = aj VA + EV, V, = (ana + + + (ay + év,) where VV VVV VjJ. (Ev, ayiv; + ev,) aL (Ve, V), so R(V. VylV) II V Va\(V, Vj) based on Lem. 1(1). Combined with Prop. 1, we reach the conclusion.
(V2).
Ho (VW)
IF E Vo and (V, Vi) S (Vk). based on Cor. 2, we have GDe (VW) ViJ # U. (ii) IfV& Ve and (V, vy)
TThere are three possible cases. (i) V2. E Va. we have VA GD (V2 Hes
PDc (Vx), since Vj PCh& (Vx), hased on Cor. 2, have GDe
H: (Vx) Vj} #
20

---

Published as a conference paper at ICLR 2025
V
V
Vx
VI
Vi
(i) case (1.a)
i case (1.b)
(iii) case (2.a)
V&
Vi
V
V
V2
(iv) case (2.c)
(v) case (2.c)
Figure 1I: Illustration of "if" part in proof of Thm. 1. A dotted arrow from V1 to 122 means that
1/2 E GDe (Vi). V is marked in red if Va.
"If". We prove this part by contradiction. Suppose (V, Vÿ) & S.
(1) Suppose Vi E Ne (V,), (V)), all possible cases are follows.
Ch*((V)) (V,) # 0. we take the former example without loss (a) Suppose Ch Ch²o(V) (V) * 0 or Ch
of generality. Let V E Ch (V)). Similarly to fn. 5, we have GDe 26 (V2) Vj) # and let Vi E GDe th (VV) Vy}- An illustrative example is shown as Fig. 11()..
Vj $ (V)), mamy # 0 and m = 0, for any V E (VV.V. Vj) s.t. V, V, Vj are cor- related to each other, R(V, VjlV) X Vi based on Lem. 1(2), which leads to contradiction. Otherwise, if Vj E De He (V)), without loss of generality, we assume Vj De in which case mJRmii& # and mik = 0, so for any V E VV,,V V,} s.t. V. V,V. are corre- lated to each other, R(V, VJIV) Y Vi based on Lem. 1(2), which leads to contradiction.
(b) Suppose Ch 7/ (V/) = Ch 76 (V,) = 0, Pa (V:) # 0, and Po (V)) # 0. Since (V, Vj} S2, there exist (Ve, Vi) S Va U U VcMV, Vy} s.t. Ve E Pa PV))(V)) and Vi E Pa Ha (Vj). (V)). Similarly fn. 5, we have GDe The (V+) Vi] 0, GDe 26 (V))(V Vy)
and let Vn GD 26 (V.)VVV Vý). Vn, GDe Th (V) Vj) (It is possible that Vn V.). An illustrative example is shown as Fig. 11(i). If V; & De" or V, & (e we take the former as an example without loss of generality, then m mjmmal # O and ma = O. so for any V E V. V.V. V2} s.t. V, V.V.V, V, are correlated to each other, R(V, VylV) y Vn based on Lem. 1(2), which leads to contradiction. Otherwise, miM jKMAM # O. Since there exist two non-intersecting directed paths from (VE, Vi} to (V. Vj} (c.g., V2 V; and Vi - Vj). ma/m;, # m mjz/mmj jI- Also, mm # O. So for any V VaV.V, Vý) s.t. V, Vi, Vj are correlated each other, R(V, VylV) Vn, R(V, VylV) H V, based on Lem. 1(3), which leads to contradiction.
(c) Suppose Ne = or ?e (V,) = 0, we take the former as an example without loss of generality. Clearly, CV, Vy) = 0, which leads to contradiction.
Assume V, (V or Vj PaH take the former example without loss of generality, all possible cases are as follows.
(a) Suppose Ch Th (V)) # 0. Let V2 E Ch (V)). Similarly to fn. 5, we have He
GD He (V+) Vj} # 0 and let Vi GDe (V&)(V, An illustrative example is shown Fig. 1iii... Clearly, myjmy # 0 and myj 0, so for any V e Va Vy) s.t. V. V.. Vj are correlated to each other, R(V, VylV) N V, based on Lem. 1(2), which leads contradiction.
21

---

Published as a conference paper at ICLR 2025
(b) Suppose Pa Pa (V))\)) o and Ch* 0. Since (V, (V) & Si, we have Ne (e""((V)) (V)) = 0. Clearly, for any Val(Vi Vy}, Cov(V, V2) 0 which leads to contradiction.
(c) Suppose Ch (V)V() * O. (V) # 0, and (V)) = 0. Let V& Ch (V)AEV) and Vi (V) (It is possible that Vx Vt). Similarly to th
fn. 5, we have GDe (VW)VV * 0, GDe (VV) V2) * 0 and let Vn
V. (VW)V, Vj). Vn E GDe He (V).(V (It is possible that Vn = V2)) An il- GD He
lustrative example is shown as Fig. 11(iv). V; & DV) mymnt # 0 and ma 0, so for any V E VoV(V, Vÿ] s.t. V. V., V are correlated to each other, R(V, VjlV) N V,, based on Lem. 1(2), which leads to contradiction. Otherwise, M # O, since there exist two non-intersecting directed paths from (Vi Vi} to (V, V2} (e.g., Vi and Vi- Vj), m ma # mja/m, m. Also, mm # O, so for any V (VV. Vj} s.t. V. V. Vj are cor- related to each other, R(V, VjIV) и Vm or R(V, VJIV) X Vn based on Lem. 1(3), which leads to contradiction.
(d) Suppose Pa (V,) * O, Ch 26 (V)V(V) = O, Pa (V)) # O. and Ch (V) = 0. Since (V, Vj) 83. there exist (Vx, Vi} S V. U.M.V Vÿ) s.t. V2 Pa Pa (V:) and Vi
Pa (Vz). Similarly to fn. 5, we have GDe (V+)) V,) # 0, GD He (V))V, V2) #
and let Vm E GD (V,) Vj). Vn E GDe Ha (Vi) V,} (It possible that Vn Vn)) An illustrative example is shown as Fig. 11(v). Then the proof similar to case (1.b).
(e) Suppose Pa (V,) 0. Ch H: (V))VV 0, Pa (V)V() # 0, and (hh+&(V) 0.
Clearly, for any V E Va\e%, Vj), Cov(V, V/) = O, which leads to contradiction.
Theorem 2. VVV. E S, let (V,, VoJ S Ch (V/).
(1) V/lV,) Vú, iff (V, V2) e $ and V, Pa PVy())).
Suppose (V, Vj) 81, Vy) e (V(,, ViH s. (Ve, Vy) (V, Vj) 0 only if (but not
if) (V, Vi} E S2.
(3) Suppose (V, Vj} S1, 3(V,, v/) Uh (VaVV, VjD) s.t. (V,, Vz. Vj. V&, Vi) satisfies the quintuple constraint iff (Vi V2}= e 83 and Vú E (V).
Proof Sketch. For (1), if (V, Vy) S and V, E (V)),, can prove independence based on Lem. 1(1); otherwise, for each possible case, we can prove dependence based on Lem. 1(2.3). For (2), "onnly if" can be readily derived from the definitions of Si, S2, and S3 while "not if" can be proven by an example, which is {O,, Os) in Fig. 3. For (3), if (V, V₁} E S; and V; E (V letting V be the common parent of V, Vj and VR, Vi be respective generalized descendants of V's any two pure children, we can prove the quintuple constraint is satisfied based on Lem. 2(2.a); otherwise, for each possible case, we can prove it is not satisfied based on Lem. 2(1).
Proof. Cond. indicates that VV Va. Ch (V) PV)
"If" of (I): Clearly, Vn = Vi+ + EV. Vj ajiVi Ev, where (ev,, EV,) 11 (V, Vi,), so we can reach the conclusion based on Lem. 1(1).
"Only if" of (1): We prove this part by contradiction.
Suppose (i) (V, Vj}= E 31 and V2 Pa&(V)), or (ii) (V, VjJ E 82, or (iii) (V, Vj) e 33 and V, Pa (V)). Since mi, # O and mni 0, RVV, VylV)) N V1, based on Lem. 1(2), which leads to contradiction.
- -Suppose (Vi, Vy E S3 and V, E Pv Let Pa (v,) = (V)). Clearly, miamign &m amymjkk O. Since there exist two non-intersecting directed paths from (V,, Vi) to (V,, V (c.g., V, - Vú, and V₂ - Vj), m # m m Also, mig # 0, so R(V VylV,) & Vi based on Lem. 1(3), which leads to contradiction.
22

---

Published as a conference paper at ICLR 2025
"Only if" of (2): This follows the definitions of $ 32, and S3.
if" of (2): An example is {0,, Og) in Fig. 3.
"If" of (3): Let He (V;) = (V)). If V. E Va. let (V2, Vi S Ch* (Vi). Otherwise, Vn, E Ve S
L, let (Vn, Vn,) S PCh (V,). Similarly to fn. 5, we can obtain GDe 2a (V,,)) (V,,)),, V2] # 0 and
G 2
(V (V,, Vÿ) # 0, let V& E UCh (GDe (CDe" (Vn,)) and Vi E UCh" (GDe (Vr,))
In both cases, Vn, V42 V,, Vx can be expressed as
Vi athai Vn + dijiv, EV,,
(14)
Vi, =aihai Vh + aijEv, + +EV;
(15)
Vj (anaa ajn) Vn + ajivv, + EV,,
(16)
= A + eVa.
(17)
where Vn, Ev, eV,, EV2, ev, and Cov(V, Vn) # 0, so (V,, Vo, V,, V2, Vi) satisfies the quintuple constraint based on Lem. 2(2.a).
ev, are independent of each other, Vi 1l (cv,,vv, CV, ,v,,vv)
"Only if" of (3): We prove this part by contradiction. Suppose (i) (V, V2} e 33 and V, Pa Pa (V)) or (ii) (V, VýJ+ E $2. Clearly, mn # O, mij O, and for any Vx, mki = 0, so (V,, Viz. Vj, Vv, Vi) does not satisfy the quintuple constraint based Lem. 2(1), which leads to contradiction.
Remark. For the proof of (1) and (3), it be readily verified that if both Vi, and Viz identical to Vú (i.e., Oifi = aizi = 1 and Ev, = ÉV, = 0). Clearly, when V; refers to any Oj E Op. (Vi, V refers to (0',0") 0') S O₁, which are two created children of O,. This means that in the practical implementation, we can create O', and 0", by directly making two copies of Oj, without the need to add independent non- Gaussian noises into Oj.
Theorem 3. (I)v(V, Vý) e 82, Pa& V2)) s V, (V,, e O. (2) VIV., Vj), (V, Vr ç S2, Pa ((V. Vyh) = Pa ((Vr, iff (VVr, Vy E 82 s.t. (V, VDJ (Ver, Vyr} # 0 and (Ve, N (Vrr, Vpr) #
e s.t (V, Vy #
Proof. This can be readily derived from the definitions of 3) and Sz.
Proposition 2. Cond. is still valid after update.
Proof. We denote Db. Va. Vo. Hi, H2, 3 after update by V V. V. Hy Hy, S' respectively, While Cond. 1 is valid for V n Vo and Va Va trivially, we focus on V Vo and V..
If E VA then Vj E Va and there exists V; E V ii (V, Vy) and V; (V))(V)) or (ii) (V, v2} E $2. In both cases, [Pa H (Vy)1 = because Pa H (V,) = (Vi) in case (i) and (V,) Pa H6 (EV, V2H) in case (ii). Also, based on the definitions of 3 and S2, Vy has pure child in H2. Ch (V,) S PCh&(V)) reduces to Ch (V,) PCh PCh&(V)) then Ch*c (V,) Ch (V,) PCh (Vj).
Vf V.AV a. then VIV,, Vi) (V)), (Vr, Vi) E 32 and UPaaa Vi)) (V,). so Ch* (V,) c (V)) Besides, is trivial that Pa 0.
Theorem 4. S U 82 = 0, V. =0
Proof. We prove this by contradiction. Suppose V. # 0 and V, V. L.
23

---

Published as a conference paper at ICLR 2025
If Ch 0, then PCh Va. Conversely, if &Ch$ & Va. there exists V PCh., (Vi) and (V) Ch** 0, contradicting Asmp. For each (V,. V&) E PCh PCh)(V)) it is trivial that (V, V&J 32, that is, $ # 0, which leads to contradiction.
If "h U (PCh& (V)) * 0, let V = (VIV e PDe (V,), Ch* * 0. U Hc (Ch" 0) and V e V then (V)) s Va as proven by contradiction above. If Va. then for any V& Ch
Ch**(V)) (V)), it is trivial that (V, V&) S1, that is, $1 + 0. Otherwise, Vj E Ve S I, for each (Vx. Vi} s Ch (Vj), is trivial that (Ve, ViJ E 32, that is, S2 # 0. Both cases lead to contradiction.
C.2.2 PROOF OF THEORETICAL RESULTS IN SEC. 3.2
Condition 2. (1) VV U..
De & Ua. (2) Ua. X2i-1, X2r can be written as
X2--1 = C2--1
Σ
Mijev, ex + e'xx-1' X21 = c2i
Σ
Mijey, exx + ex
(18)
VJEU,
VJEU,
where EVi...., exp ex21 (e " e' Xam ) e'x ''..... &se are mutually independent.
Without loss of generality, we assume each Czi-1 is positive and each Ev, has variance 1.
Theorem 5. VV; Ua. An (V) U. 0 VV E UA(V))
X2- 12 X2--
Proof. When |Ua| = 1, the proof is trivial we focus on the case |U,l > 1.
"Only if" As An H: (V₂) n U, = 0, X2--1 and X2r can be written as
X2-1 c2i-1Ev + ex Ex X2i C21EV, exi + exxx'
(19)
If Cov X2;) = 0, then my = O, so R (2 X (2x) X2j-1 11 X2i.
If X2:) # O, then my # O. X2j-1 can be written as
Σ
X2j-1 = m + C2j-1
mjkEV, ex + +
(20)
where (exx-1 + é X c2j-1 Eveu,MM MyREV, + ex,=-1 + + 11 (EV, X21), so R(X2)-1, X (xx)) I1 X2i based on Lem. 1(1).
H6 "If": We prove this part by contradiction. Let V; E An (Vi). Clearly, X X2i, X2j-1 are cor- related to each other. Since X2i-1 and X2; both contain év, while X2j-1 does not contain Ev,, so Xx A X2 based on Lem. 1(2), which leads to contradiction.
Theorem 6. If V, satisfies Thm. 5, then Cov(X2i-1, X2i) c2i-1C2r and VV U.\(V)).
sgn(m)j) sgn( Cov(X2:11,X) ) 1ov(X2/-1,X)))
X2y-1) -2-102022-102)m
(21)
Besides, VV E Va!Ua. 0.
Proof. is trivial that WV, E ValUa.m. Ma. because V, & An An* based on Cond. 2(1). Since we assume each Ev, has variance I and each c2-1 is positive without loss of generality, VV, Ua V.V(V,)
Cov(X2-1,,2))
C2-1m
(22)
Cov(X2j-1, X2j) C2j-1 Var( Var( Evet, mixev,)
(ox(X))11.3)))
so ;a) = sgn(
). Besides, it is trivial that Covl Cov( (1
Cov(X2i-1, X2j) CotC)oo(Xxaa X2j-1) 121-10200)-1121mm Cov(Xoj-1,,22) -21-1021
(23)
Finally, VV2 Val Ve (VV), so mi: = 0.
24

---

Published as a conference paper at ICLR 2025
Proposition 3. Cond. is still valid after removal.
Proof. Based on Thm. 5, Cond. 2(1) holds trivially. Besides,
R(X X2)) C25-1
Σ
mV + ex---1 exy-11
m
(ex2.-1 +xxx-11+
C21-1
updated ex2s-1
(24)
X2j = c2j Vk
Σ
j + ex2, + + = c2j
MjkeV exxs + exay c2jmjiev,
(25)
VeV
updated e'xay
8o Cond. 2(2) is still valid.
C.2.3 PROOF THEORETICAL RESULTS IN SEC. 3.3
Theorem 7. Suppose the observed variables are generated by LiNGAM with latent variables satis- fying the bottlenec-ffaithuunee assumption and Asmp. 1, in the limit of infinite data, our algorithm correctly identifies the underlying complete causal structure.
Proof. In Stage 1, our algorithm sequentially identifies latent variables and their pure children. Dur- ing this process, Hi records all identified causal relations. According the theoretical results in Sec. 3.1, causal relations in Hi are correct. In Stage 2, with Hi fixed, our algorithm recovers H2. According to the theoretical results in Sec. 3.2, causal relations in H2 are correctly revealed. Com- bining Hi and H2, algorithm correctly identifies the underlying complete causal structure.
C.3 PROOF OF THEORETICAL RESULTS IN SEC. 4
Definition 5. (Paired pseudo-pure children) We say (V2, Va} is a pair of pseudo-pure children Vi,
denoted by [V2, V3} P'Ch Vi), if (i) n Pa((V, V/)) (V1), ). (ū) U Pa((V, (V,, V2, V/3 = 0. (iii) 1/2 E Ne(V: V3), and (iv) VV De (V2, V3), [Pa(V)]
Remark. Based on this definition, if (V2, V3} e P'Ch(V)) and 1/2 E Pa(V)), Ch(V2) = PCh(V2) U (V₂) and Ch(V)) PCs(
Assumption 2. (1) e L, Ve Vo,, Ch & (V WV) e Vo. Ch the unique minimal bottleneck from Ch (V) On. (L) L, is n PV.
Trivially, if Asmp. 2 holds, then (1) VL L,V VVL), CL & CV 22 Ch (V) is the unique minimal bottleneck from Ch to O. (3) L, Pv
C.3.1 PROOF OF THEORETICAL RESULTS SEC. 4.1
Definition 9, (Pseudo-pure descendant) We say V2 is a pseudo-pure descendant of V1, denoted by V/2 D'DeeVi), V/2 E De(Vi) and there exists common cause between V1 and V2.
Example. In Fig. 2(a), DeDe(O2) = [[,,,.., L4. O,, O3, .... 016).
24 (V) (V)) and |Ch H6 (V)l 2 If Ch "i (V) & P (V), then (Ch (Ch"((V) = P'Ch (V) and (V, Vy} S Val(V) s.t. V/ P V, V. and V, V,lV.
Condition 3. (1) VV Vb. IPa"
and Ch (V) (C) (V): (2) VV V.. Pva
Before proving theoretical results in the main text one by one, we first introduce two corollaries (Cors. 3 and 4) readily derived from Cond.
Corollary 3. (1) VV Vb. (i) &al (V) Pa?t (V) and Ch Ch Ch² or (ii) 3L E VD\(V)
S.I. Paś(V) = Pa (V) U (V') and Ch& (V), or (iii) Pa Pa (V) and 3V
VoV[V s.I. Ch (V) Ch 2h (V)U(V'); (V) (2) v., Ch (v) Ch²² and Pa
(3) VV V, W
and (V) = Pa Pa (V).
25

---

Published as a conference paper at ICLR 2025
Remark, This is a variant of Cor. in App. C.2.1. While (2,3) here are identical to (2,3) in Cor. 1,
(1) here is slightly different from (1) in Cor. in the sense that for each V Vb. Ch (V) or Pa (V) might contain one more variable in Vo than Ch in the following proofs. To maintain fluency, we will use it without further citation.
2i (V) or (V). This corollary is widely used
Proof. First, if V/ E Vb. then Ch² (V)) = PCh and there exists Vi E Va U Vo s.t. Pa th (V)) (Vy) based Cond. 3(1). Moreover, since (i) Ch (V,) PCh if E Vo
based on Cond. I(1) and (ii) (V)) s PCh or (Ch"
P'ch (V2) if V, E
Vo based Cond. 1(2), there is (i) Vi PCh or (ii) there exists V; E VoV[V) s.t. = Pch((V) -h" and Pa Pa (V2) (V,) if V; PCh or (ii) C (V)) PCh
P'Ch& (V2) ([V. v/)) Therefore, we can conclude that (i) Ch (V) Ch&(V)
Ch** (V:)
and (V) = (V (V)) U (V)) if P'ch' (V)) = (1V, V(D and V e Pa)(V));
or (iii) Ch&(V) (V) u (V/) (V) (V,) and (v) (V,) (V) if
Pºch
& (V1) ((V. v/)) and V. Ch (V)). This completes the proof of (1).
The proof' for (2,3) are similar to Cor. 1.
Corollary 4. VV E Vo. DD H6 (V) 2 2. If I (V) = 2, (v) = CV)
Remark. This is a variant of Cor. in App. C.2.1, where "pure descendants" and "pure children" in Cor. 2 degenerate to "descendants" and "children" here. Although this is not sufficient to identify
variables in Ve. we can still infer some of their properties through analyzing variables in Va.
Proof. It is trivial that Va is a bottleneck from Va U Ve to Va Vo. so for any V S Ve.. UGDe (V") is a bottleneck from V' to O given that O s Vau Vn. For any V E Ve, Ch&
Ca (nHa(V) (V) S Va U Ve. so De He (V) = U GDe (Ch& is a bottleneck from Ch& (V) to O. Based
on Asmp. 2(1,2), we have [De He (V)l z |Ch (V)I 2 2. Furthermore, the first "z" becomes "=" iff
CV) De (V) = Ch& (V) because of Asmp. 2(2).
Theorem 8. V(V, VJ) S Va. V e S iff there exists VR E VaV(V, Cov(V, Vx) Vx) and for each such Vg, R(V, V/VK)) I Va (V,, Vy).
Vy) s.t. Cov(V,Vy)
Proof. "Only if"
(1)
Suppose (Vi Vj) E St. The proof is similar to case (1) of "only if" part in proof of Thm. 1,
except that we obtain GDe
26 (V,) V2} # 0 in a different way
(2) Suppose (V, Vi} S2. The proof is similar to case (2) of "only if" part in proof of Thm. 1, He except that we obtain GDe (V)) Vj) # 0 similarly to fn. 6.
(3) Suppose (V. Vi} E S3. The proof is similar to case (3) of "only if" part in proof of Thm. 1, except that obtain GDe
He (Vx) (V. Vy) # 0 in different way?.
"If". We prove this part by contradiction. Suppose (Vi Vy) $ S.
There are three possible cases. (i) If V2 C Va. we have VA GD
Th (V2) VY) # 0. (i) C V
and (V, Vy) "o (Vx), based Cor. 4, we have GD H6 (V Vy) # 0. (ii) I Vo and (V, Vyl
De De since Vj Ch (Vx). based on Cor. 4, have GDe H: V. (Vx) Vj} # 0. Ch)(VV). IIf V Va. then V2 E GDe 76 (VW)VV V2J # 0. If E V. S L, suppose GD H6 (VV)VV =. base on Cor. Ch& (V²) = (V,, Vy). which leads Ch& (Vx) s Ch&(v,) (V:) u (Vi), contradicting Asmp. 2(1).
26

---

Published as a conference paper at ICLR 2025
Vi
V4
V
(ii)
Figure 12: Illustration of case (1.b.ii) of "if" part in proof of Thm. 8. A dotted arrow from V1 to 1/2 means that V22 GDe (Vt). A dot-dash arrow from V1 to V/2 means that V22 E De De (Vi). V is marked in red V Va.
(1) Suppose V & Ne Ho (Vj). . All possible cases are as follows.
(a) Suppose Ch 2h2 (V,) # 0 or Ch (V,) * 0. The proof is similar to case (L.a) of "if" part in proof of Thm. except that we obtain GDe He V. (V&) Vj) similarly fn. 6.
(b) Suppose Ch = (V²) = 0. Pa the (V,) # 0 and Pa (V,) # 0. Since (V.
$2, there two possible cases.
(i) Suppose Pa Pa (V,) = Pa Pata( = (Vi) where V22 E Ve and Ne (VW)VV, Vy} = Clearly, for any V E Va,,,, Vi}, Cov(V, V,) O, which leads to contradiction.
(ii) Suppose there exists (Vr, 1/) & Va U V5t s.t. Ve E Pa (V;) and GDe He (VV))VVVV)
and GDe H. (VD)VV V,} 0. the proof is similar to case (1.b) of "if" part in proof of Thm. 1. Otherwise, let GDe He (VR)VVV = without loss of generality, then we have V& E Ve S L and Ch (Vx) Vy) based Cor. 4. Also, based on Asmp. 2(1), (V& Ch (V)), so V; & Ch)), we have G. Vÿ) # and let Vn GDe (V) Vj}. An illustrative example is shown as Fig. 12(i).
Vi (V))
Suppose V; & (V)). As mimmml # O and mæ 0, for any V s.t. V, V.V.V are correlated to each other, R(V, VjIV) и Vm. which leads contradiction.
Suppose V; E De besides V; Ch (V))(VV) mentioned above, we can also derive Va & Ch (V)), so there exists Vp # V2 s.t. Vp E De (Ve) and V, De GD He (V,), Vj) * similarly to fn. 6. Let Vg GDe (It is possible that Vm = Vg). An illustrative example is shown as Fig. 12(i). If Vj & De (Vp). mip # 0 and mjp = 0, so for any V s.t. V. V.V.Vi are correlated each other. R(V, VylV) 1 Vg. which leads to contradiction. Otherwise, mmmip Mammppmmmmm...m jMM ip * O. Since there exist two non-intersecting directed paths from (V,, Vpb to (V. V2} (e.g., Vi Vj and V. - - Vi),, ma/ mip m jt/ m jp- Also, Ma # O, so for any V s.t. V. Vi, Vj are correlated to each other, R(V; VjlV) Vm R(V, VvlV) Vg. which leads to contradiction.
Based Asmp. 2(1), (Vr) & CV& p). Hb (V,).V..V))
have
(c) Suppose Ne (o,) 0 No (V,) He(H))
0. The proof similar case (1.c) of "if" part in
proof of Thm. 1.
(2) Suppose V, E Pa (V)) or Vj E PVH) we take the former as an example without loss of generality. All possible cases are follows.
(a) Suppose Ch Ch # O. The proof is similar to case (2.a) of "if" part in proof of Thm. 1, except that we obtain GDe
H6 (Vi) Vj) 0 similarly to fi. 6.
8 With Asmp. valid, this case is impossible as INe (V&)) 2 3, so we do not discuss this case in the proof of Thm. 1.
We can prove this by contradiction. Suppose V& E Ch 2e (V)). then Ch& from Che (V)) to O and |Ch& (V/)1 jCh (V)) u (V; H. contradicting Asmp. 2(2).
(Vi) U (VH)VV2) is bottleneck
27

---

Published as a conference paper at ICLR 2025
(b) Suppose Pa Pa*
(V)) 0 and Ch (V)) 0. The proof is similar (2.b) of "if"
part in proof of Thm. 1.
(c) Suppose Ch (V)) * O. (V)
and (V,) o. The proof is similar to case (2.c) of "if" part in proof of Thm. 1, except that we obtain He
H: GDe (V&))(VVV) Vj3 # similarly fn. 6 and GDe (VD) Vi} 0 similarly to fn. 7.
(d) Suppose Pa # O, Ch ** (V))\ = 0, Pa th (V,) * 0. and Ch ch**s10 (V,) = 0. The proof is similar to case (2.d) of "if" part in proof of Thm. except that we obtain both similarly fn. 7.
GDe Hh (V+) Vj} 0 and GDe
26 (V) V2}
(c) Suppose Pa (V) = 0, Ch proof is similar to case (2.e) of "if" part proof of Thm.
= 0. Pa Pa**(V,) (V)) * O, and (V3) = 0. The
Lemma 3. V(V. Vy) e 8, (V)) s PCh (V:) and Ch² (V₂) S PC))(V,).
Remark. This lemma means that if variable V is in an identifiable pair, then there is Ch (V) (V) S PCh (V), which is consistent with the case where Asmp. holds. This significantly simplifies the complexity of the proof of some following theoretical results. For instance, with this lemma, most proof strategies employed in the proof of Thm. can be directly adapted to prove Thm. 9.
Proof. The proofs are as follows.
Suppose (V, Vý} E Si and V; e (V))) First, we can easily derive that Ch**(V)) S PCh Second, we suppose Ch:H (V,) & PCh& (V/) and let V& (V) Sim- ilarly to fn. 6, we have GDe v. (V,, Vj) # 0 and let V/2 E GDe (V2) Vy). Clearly, there is Vy e DeDe (Vi), V M V. and ;j и Vi[V, contradicting Cond. 3(2).
Suppose (V, Vi} 82, similarly to fn. 10, we can easily derive that Ch Hi (V,) S PCh (V,) and (V)) PCh$
Suppose (V.. E 83 and V; PV First,
easily derive that Ch (Vj) S
PCh (V,) similarly to fn. 10. Second, suppose Ch (V;) & PCh (V;), based on Cond. 3(2), we have (Ch H (V/)) p'Ch G (V;), so & O, that is, V E L. Clearly, V; a I-PV. This leads to contradiction to Asmp. 2(3).
Theorem 9. VLV. Vý} e s, let (V,, V2) C CV.)
(1) R(V,, Vy(V)) V,, iff (V, v)) e S and V/ (V)).
(2) Suppose (V, Vy} & S,, 3Vr. E.V((V st Vy.Vy n (V. * 0 only (but not
if) (V, Vi}+ Sz.
(Va((V, (3) Suppose (V, Vj) Si, (VV. vi) Uhhh (V.AVV Vj)) s.t. (V, Vig Vj. Ve, Vi) satisfies the
quintuple constraint only if (but not if) (V, Vy} 83 and V; e Pa
Proof. Combined with Lem. 3, the proofs of (1), (2), and "only if' part of (3) are similar to Thm. 2. Here we focus on "not if" part of (3).
Suppose Ch*i (Vz) PCh (Vz), based on Cond. 3(2), have (Ch*H, H (Vz)) p²Ch (Vz). so VJ $ O. that is, Vj= E Let MhM (V2) = (V,, Vi) where V& Pa (V)), since Ch"H((V)) = 0, we have Ch& (VE. Vi). There is Ch& ( (Vx) u (Vz), contradicting Asmp. 2(1).
28

---

Published as a conference paper at ICLR 2025
Suppose Go is shown as Fig. 8(c), at the first iteration when Va (02, 06), (02, e S and O2 E Pa (Oz). Let 02,,0221 _ Ch (02), then O2,, 22 O3 can be expressed as
22, = 42102,241 02,260, 60
(26)
02 d2102,241 02,260, EO2²'
(27)
0x = (a21432 431 03260; EOs
(28)
Because a31 * 0, 42102/2/ + a31) # 22,2/22 For any (0,, they can expressed as
0z)),
O, = -,L1 (7iE0, ea). 0j - (yΙε0, + +e)),
(29)
where F0, Eos, <0,,; Y. + e are independent of each other, O, (Eos, F02, EO2, EO2)
and Cov(O, O, Li) Y,o. + e # Based on Lem. 2(2.b), (02, O2., 03, O, 0,) does not satisfy the quintuple constraint.
Corollary 5. Given (V, Vj) 33 and V, (V)(V let Pa (V)) (Vr) and (V, Vτ,} 3 Ch (V:).
(1) V E Va- then 3(V,. VI S Ch (VaMV, s.t. (Vi, Va, Vj. VR, Vi) satisfies the quintuple
constraint.
(2) (V Vi) S VaME, V2} s.t. Vn E DeDe (Vn), V, x Vho and Vn Vn then 3(K,, Vi3 S
Ch H6 (Va Vj)) s.t. (Vn, V/2, Vj. Vk, Vi) satisfies the quintuple constraint.
Remark. Given (V, V2) 93 and Vi E Pa PV)(V based on Rem. of Thm. 9 in the main text, both (V, Vj) E & and (V, Vý} E 33 are possible. This corollary provides two sufficient conditions that
3(Ve, ViJ c Ch (V. VVV, Vj}) s.t. (V,, Vn, V,, Vx. V/) satisfies the quintuple constraint, that is, (V,, Vy) $3. The proof of the following Thm. 10 highly relies this corollary.
Proof. The proofs are as follows.
(1) We first prove Ch Hi (Vn) & PCh (V₂) by contradiction. Suppose Ch Hi (Vn) & PCh (Vn), then based Cond. 3(2), (Ch% (V,)) = p²ch 9 (Vv). In addition, since (V, Vj) E $3, we have Ch*i (Vi) (V)) and Ch (V₂) (V)) s (V,) based on Lem. 3, so (V, Vj) p²Ch 9 (Vr) = (Ch* y Vo, which leads to contradiction, thus (V)) g PCh (V+). Let (V2, Vi C Hh (Vw), then the proof is similar to "if" of (3)" part in proof of Thm. 2.
(V%)
(2) Let V E Ch Hi (Vm) and Vi E Ch Hi (Vn), then the proof is similar to "'ff of (3)" part in proof of Thm. 2.
Theorem 10. (1) V(V. 82, (VV. & Va if HIV S st. V1 n (Ve, Vy) # (2) V((V, VjJ. VrH s S2 (PV V,)) (PVe, Vy)) iff 3(Ve, (Ve.VVre E. s.t. Vy N (Vr, Vyr) # 0 and
Vyr #0.
Proof. As mentioned in Rem. of Thm. 9 in the main text, 3 Si, 32 2 32, 3. Ss.
For any (V, Vy} S2 s 32 (1) can be derived from the definitions of 3 and Sz.
For (V, Vÿ} S2) the proof of (1) is follows. Clearly, (V,, Vy) E S3. First, based on the definition of S, v(V,, Vyr E 3 S,, (V. Vy) (Ve, Vy-) = 0. Second, we have O Pa (1V, V2)) & Va. otherwise (V, Vj}= E 33 based on Cor. 5(1), which leads to contradic- tion. This finishes the proof.
For any (VV, V2J, (Ve, Vy]) S $2 s $2, (2) can be derived from the definition of $2-
29

---

Published as a conference paper at ICLR 2025
For (V, VjJ E $2/52, the proof of (2) is follows. Clearly, (V.Vi) S3- First, based the definitions of S2 and S3, v(Ve.Vy) VVV(V E (82 U (HV,, Vi (V, V (Vr, Vr- 0. Second, we prove v(V,, Vr) E &
OP th (1V, D * N 2o ((Vr, Vy by contradiction. Let PPa ((V, = (Vn) and suppose n Pa 2 ([Vr, Vy)) = (V,). First, we have Vn E Ve S L, otherwise (V, Vj} E 8g based on Cor. 5(1), which leads to contradiction. Second, also have (Vr.Vy) E S3, other-
wise Vi E P'DDe $ (Vv). Vy X Vn. and Vp IL Vy.lV, so (V, Vj} S3 based on Cor. 5(2), which leads to contradiction. Third, because Vn is not a II-PV based on Asmp. 2(3), there exists V2= Ne (V.) Vj. Vr, Vy and we can derive GDe (VR)) GDe H: ((V; Vj. Ve. Vyr)) # 0 Let Vm E (Vr, Vy) and Vn E GDe He (WWAVWWUUUGSS Hi (1V, Vj, Vp, Vy)), since Vn De (Vx), Vn M Vk. and Vm 11 VnIVE, (V, Vj} E S3 based on Cor. 5(2), which leads to contradiction.
Proposition 4. Cond. is still valid after update.
Proof. We denote Vb. Va. Ve, H1, H2, S after update by Vn, V. V". Hi Hy, S' respectively. While Cond. 3 is valid for VA O Vo and Va n Va trivially, we focus on V Vv and V.Va..
IFV, E VA,, then Vy E Va and there exists Vi E Va s.t. (1) (V. Vj} e S and V, E (V,) or (2) Vi) E 32. Based on Lem. 3, Ch 2h (Vt) s PCh&(V)) then the proof similar to part 1 in proof of Prop. 2.
If V2 E V.Va.. then Vj E Ve and v(V. Vi) & (V)) V/.VV e 3 and (PV Vit) = (Vj). Also, VV (V)) (V) s PCh$(V) based on Lem. 3. Furthermore, based on Thm. 10(2), there are two possible cases.
- VV(V,, V/) Ch) (V., Vi) E S2. In this case, is trivial that (V²) & (V))
- (V,) S3. In this case, it is trivial that Ch* (Vy) E paCh $ (Vy). Now we prove (Cn"((VV))) = pach by contradiction. Let Ch2f = {Vn, V22) and suppose there exists (Vi, Vi) E pºch (V)) Vi2l. As (Vj. Viz) De
0. we have GD He (WW) VA # 0 and let Vm E GDe Ho (V2) Vig)- Because V2 is not a II-PV based on Asmp. 2(3), there exists V; E Ne (V)) Viz- Vv, Vi). Also, there H: exists V, E GDe Hi (VAA U V. (1V, VJ Ve, Vit) * 0 similarly to fn. 11. Clearly,
Vn E De (Vg), Vn Vj. and Vm IL V. (Vi, Vi+) 33 based on Cor. 5(2), which leads to contradiction. Therefore, (Ch H (V,)) = =P'Ch Φ (Vz). Likewise, we can conclude that BVV,, Vii+ S VV\(V,) s.t. V& E De G (V,). V1 M Vj. and V2 n VilV,, otherwise there is also (V,, Viz) E 83, which leads to contradiction.
Finally, is trivial that Pa7G = 0.
I1 There are three possible cases. (i) If V2 E Va. then V e GD (VAUU H.
# (IV, Vj, Vr, Vy3)
(i)) If Vs E Ve and Vk E Ch Ha (V)), then (o(e) UGDe Ha Va (1V, Vj. Vr. Vy)) 0.
so GD He (VANU Ha (VV. Vj. Vr.Vy.)) * @ based on Cor. 4. Ha (EV) Vy)) is bottleneck from Ch CV to O.
(ii) IF Vv Vo and V
He Pa (VVh) then (De (VW (VA))
so I(Do (V()) U (VDDAGGE M Vy, VyDI 2 |Ch& (V+) based on Asmp 2(1,2), so Ho (VW) U GDe
GDe
H6 ((V. Vj. Vy)) #0. 0.
30

---

Published as a conference paper at ICLR 2025
Theorem 11. If Asmp. is invalid, when $1 U. 0. Ve # or there exists L Va s.t. Ch Ch²i g (L).
Proof.
The proofs are as follows.
Suppose 3L, Lst. (PCh <. IfP'Ch & (L,) 0, there is L, Ve trivially. Otherwise,
It is possible that L, E Ve, e.g., if no pair in P'Ch (L,) It is possible that Li Va an example is shown Fig. 8(d). In this case, there must be (L,) & PCh because & (Li) < but "an" (L)I based Cond. 3(2). It is impossible that L, E Vb. Suppose L, Vb. it trivial that Ch")(L) & (L)) which leads to contradiction to Cond. 3(1).
(L,) is incorporated into $2.
Suppose VL. e L, [PCh& 2 2. Since Asmp. invalid, 31,; s.t. s.t. |Ne 3, that is, JPCh @ (L,) = 2 and Ne (L.) (P))(($$))) (L,) 0. According to the definition S, there always PCh (L,) S, there is always L Ve.
Corollary 6. If Asmp. is invalid, when 0, (V) e Va. DDe 2. (2) V S.I. Ch3i (V,) $ PCh (V:), [De2 (V.)) 2
Remark. This lemma means that at the end of stage 1, (1) for any Vi Va. V2 has least two descendants in Va and (2) for any VV, Va s.t. (V)) g PCh Vi has at least one descendant in Va. This corollary is important for the proofs the following Thms. and 13.
Proof. The proofs are as follows.
(1) This directly follows Cor. 4.
(2) Based Cond. 3(2), if Ch Chh"((,, (V)) & PCh&(V) (V,), then (Ch" (V)) p'chh (V)), V, & O. that is, V; L. Let Ch (V₂) (V,, Vi:) and Vi E Pa (Vi2), we can prove Ch²f # 0 by contradiction. Specifically, suppose (V²)(V,) 0 then Ch&(V;) (Vi, Vi,), that C s Ch
(Vi)) Ch&(V,) (Vi,), this leads contradiction Asmp. 2(1). Let V2 Ch (V)) is trivial that GDe (V,) # 0, De 2 (V:) # 0.
C.3.2 PROOF OF THEORETICAL RESULTS IN SEC. 4.2
Condition 4. (V) VA Ch (V)) S &Ch (V)). (2) U,U (c c UV.. (3) VV, E U2, X2i-1, X2i can be written as
X2-1 -15-1
C25-1
Σ
mijey, exa-1 + ex
X2i =
Σ VYEUaUVe
mijev, ex ex (30)
VjelluVe
where ey, EV, (ex, (ex exen) (e', (exx e'xan (ex
e'x are mutu-
ally independent and j. Ch (V,) PCh (Vj), ex exay. Without loss of generality, we assume each C2i-1 is positive and each Ev, has variance 1.
Theorem 12. VV, E Ua. An An" UV. 0 and Ch (V,) PCh in U,\(V)) R(X.j-1.X%, (22) I1 X2i.
Proof. When |U,l 1, there is V and the only V, E U, satisfies Ch (V,) s PCh((V)) otherwise we can derive contradiction to Cor. 6. We focus on the case where [U,| > 1.
"Only if": The proof is similar to "only if" part in Thm. 5.
31

---

Published as a conference paper at ICLR 2025
"If": We prove this part by contradiction. All possible cases follows.
Suppose Ch (V:) I (V)). Based on Cond. 3(2), (Ch* P''c (V)). Let Ch (V,) (V. Viz) where V,, E Pa&(V,,. Combining Cor. 6(2) with Cond. 4(2), De 2% (V:) # 9 and let Vj DeHHa (V:). Clearly, X X2i, X2j-1 are correlated to each other. Since both X and X21 contain Ev; and X25-1 does not contain ev;, (((2)-1111 1 - M X2 based on Lem. 1(2), which leads to contradiction.
Suppose Ch Hh (V)) & PCh$(V) (V₂) and An An # #0, let v, An (V)). The proof is similar to "if" part proof of Thm. 5.
Suppose Ch2* (V) s (V)) And, (V: = O. and An (V)) # 0. let V2 E Pay. (V:). 24 C, (VW) * 0. Besides, there exists Vj De T6 (VV) s.t. there exists directed path from Va to Vy which does not include V, Conversely, if for each V E De7 (Ve))(VV), every directed path from V2 to V includes V,, then [V:] is a bottleneck from CV&( to O, which leads to contradiction to Asmp. 2(1.2). Clearly, X2-1, X2;, X2j-1 are correlated to each other. If V & (e)* then X2-1 and X2 both contain Ev, while X2j-1 does not contain EV,, so R(X2j-1, X2--1(X2;) N X2; based on Lem. 1(2), which leads to contradiction. Otherwise, X2-1- 1- X2 and 22 all contain Ev; and EV2, and there exist VA - Vi ... + Xij-1 and V; - - X2-1)), so R(Xo--1, 11 M X2 based Lem. 13)), which leads to contradiction.
He
Combining Cor. 6(1) with Cond. 4(2),
non-intersecting paths from (Vx, 1/J} 1X2)-1.Xxt X2-13 (e.g..
Proposition 5. If we can find Ug satisfying Thm. 12, Cond. is still valid after removal.
Proof. Based Thm. 12, Cond. 4(1,2) holds trivially. The remaining proof is similar to the proof of Prop. 3.
C.4 PROOF OF THEORETICAL RESULTS IN SEC. 4.3
Theorem 13. Suppose the observed variables generated by a LiNGAM with latent variables satisfying the potteneck-faithfuumee assumption and Asmp. 2. if Asmp. is invalid, in the limit of infinite data, our algorithm raises an error signal.
Proof. Based on Thm. 11, at the end of stage 1, denote (L E ValCh Hi (1. & PCh by Va, Asmp. is invalid, VOUV, # 0. Based on Cor. 6, GDD
He (VoUVa) 2 2. Based on Cond. 4(1,2), 76 (V. V.) S U,. When U, UGDe 0 and (V,) s PV))(V)), that is, we cannot
throughout stage 2, there is always U UDe
V6 (V. U VV),
there exists no Vi E Ua s.t. An H6 (V) find a V, E Ua satisfying the independence condition in Thm. 12. Therefore, before U, becomes an empty set, our algorithm raises an error signal.
D REAL-WORLD DATA
The ground-truth causal graph of multitasking behavior model is shown as Fig. 13(a), it satisfies Asmp. 1, on which our algorithm yields a correct result. Moreover, we add some edges (marked in red Fig. 13(b) into the ground-truth graph by replacing some single variable with the sum of multiple variables, the modified graph violates Asmp. 1, on which our algorithm raises an error signal.
E ALGORITHM
The details of our proposed algorithm are provided in Alg. and 4.
32

---

Published as a conference paper at ICLR 2025
Sped
Spad
Ccnedly
Comdy makkll
Demede rebbel
Jrom Nember
Nember
Mastading Betaviar
Erar
Ensorraking Lakes
Ennr
Encorsaaiing dakes
Eoto nading Faurss
Emso nadiing Paurs
Avengs of coredily Djee The
Vwaeee sumeiiyyy are Quee (her
Crediee
Kvwnge of coreefl Slee The
Vveeee of sumeeiyy are (hee
Avergg st cutrace aa- Pa.
Avenge somis as QututPas
Figure 13: (a) ground-truth causal graph and (b) modified causal graph of multitasking behavior model. Rectangles represent observed variables while circles represent latent variables.
33

---

Published as a conference paper at ICLR 2025
Algorithm 3: Stage 1: Identifying latent variables (detailed)
Input: Observed variahles and O,
Output: V Vs. and Hi
Initialize Ob, V, O,,
(V))(VV) iff PaP Og, and V22 O identical previous V. do Assert Cond. holds if Asmp. holds.
while the current V.
S 0. for (V, v E Va do if 3r V VAV, V.V.V. &. s... Cov(V, Vÿ) Cov(V, Vo)Coo(V Ve) # and R(V, V2(Va a VoA V,) then S 3 V/H
end
end
Assert consists of all identifiable pairs satisfying Def. Asmp. holds. S1 == 0, = 0,33 == 0.
for V,) where (V,,, Vi.) S (V)) and (V,, Vi (V,) do RR (V,, Vi, then
((V, V2J} and V; (V)( then
else if Mi v.)
:= Si ((V, V2]) and V, E Pa (VG).
3r,, (V(V, VI st. Vy. (Vi Vý) * then
$2 (
else if (V. (V.0.. V,J) s.t. (V, V. V,, Vs. Vf) satisfies the quintuple constraint then
S = 53 V,}) and (V)).
if S U UCh" (V. (.I)),)))) st. (V V, Vi) satisfies quintuple constraint then Sy S3 ((V). VJ and VG e (V)...
21
33
else
24
82 = 82 ((V) V/3)-
15
end
26
end
27
Assert S consists type-1 identifiable pairs satisfying Def. 2(1) if Asmp. holds.
25
Assert 8 consists type-2 identifialle pairs satisfying Def. 2(2) Asmp. holds.
29
Assert 83 P
type-3 identifiable pairs satisfying Def. 2(3) Asmp. holds.
for (V.VV) do 38
IV Vy 3 (K. (V.. then P: (UV.
end end
36
EP, Assert Y(V, EP, Pa ((V. $ V. if Asmp. holds. 3= S,1P, while S2 do
17
Arbiurrrily choose (V.V,) V,) Sz. == 2n == V,)). for (V.. vy) v e (2, Vj]) do if 3V.. V S2 st (V, VV, n(V,, Vyt and and (V,, O Vyr) # then
2n = Qn (VV. V.
44
end
end
S. = 321Q..
end
Assert (l..., m) (VV, V,J. (V,, C. (V
V. Asmp. holds.
for (V, V2J e 3, where V/ (a do
19
V. = Vol(V,). V, = V, [V7) and Hi = Hi UV - -
51
end
41
for = do
53
Introduce new latent variable
V. ULNUUU Vo Vo Ut. Hi Hi (L V UO2).
15
end
56 end
Assert V if Asmp. holds.
34

---

Published as a conference paper at ICLR 2025
Algorithm 4: Stage 2: Inferring causal relations (detailed)
Input: Va. Vo. and Hi output by Alg. 3
Output: a complete causal structure G
Initialize Ua V and assign two observed surrogates X2--1, X2r for each V; Ua-
while [Ual > 0 do
Assert Cond. 2 holds if Asmp. holds.
There exists Vi E U, s.I. VV₃ E (VV), R(X2j-1, Xx 11 X2r then
Assert V; root variable among U, if Asmp. 1 holds.
VV, E Ua (VV),, calculate sgn(m,)), C2-112202--11
and c2-1122-
VV: E V U Mki == 0.
Ua = U. (V)) X R(2 X2 X2)), X2, X2,
else
10
raise error This happens iff Asmp. fails
end
end
13 for
(V,, Vj} S Va do mjj sgn(m)i)
1-11 cu-reuey-rey
if mfj 0
15 end
16 == I - -1 where M is composed of my-
H2: := (Va.0) 0).
18 for (V,, Vj} S Va do
if aj # 0 then
20
H6 = H2 U (V, - Vÿ}
21
end
end
23
G H1 U
35


Reviews:
[{"review_id": "tofr4H6u2v", "reviewer": "Reviewer_qEDV", "summary": "This paper is concerned with learning the structure of a graphical model that may contain latent variables. In contrast to some prior art which learns an equivalence class but does not explicitly represent latent variables, this procedure aims to both identify and model the relationships with latent variables. The author employ an additive noise assumption, and provide a simple and intuitive algorithm for discovering the latent variables via tree construction. Under assumptions on the generative structure and som restrictions on the purity of the children, theoretical results are provided which give nice recovery guarantees and are in general quite complete. A small experimental evaluation is provided as well.", "questions": "Please see weaknesses above.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "Overall, I think this paper approaches a challenging problem and provides a nice and elegant solution. The authors do a nice job of making the necessary assumption clear and carefully presenting their results. Though I have some reservations (see below), overall I consider the technical quality of this work to be quite good. Further, the problem it addresses in loosening the structural assumptions required for provable recovery. This is especially important, in my view, since these structural assumptions are unverifiable and can have an arbitrarily bad impact on the learnt structure under violations of those assumptionsl.", "weaknesses": "I found the writing in the introduction to be very hard to parse, in particular the task definition. The authors are focused on the problem of learning the structure of graph including latent variables under additive noise constraints. The description of the work in the introduction makes these points hard to follow, it also isn't immediately clear from the initial description the delineation between this and FCI and learning of other structures such as ADMGs, which allow for the presence of latent variables without explicitly representing them. It would be very useful to more clearly describe the problem. \n\nMost of the paper reads as a step by step walk through of the proof techniques. While this is interesting and useful, it limits the potential audience for the paper, and in many areas, obscures some of the underlying machinery. In my view, much of this should be moved to the supplement. For example, there's no central place in the text which walks through the algorithm as a whole, rather it is strewn out across the paper in analysis steps. \n\nMany of the proofs in the supplement lack the necessary text to provide sufficient context and intuition for the result. For example, it was not immediately clear to me why proposition 1 in App.C.2.1 implied the statement given in the remark of the main text until working it through. The results should be presented with sufficient detail such that they are reasonably easy to ingest and contextualize within the context of the paper. \n\nExperimental evidence is small and limited to very simple settings.", "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": "Cz4AxmqNZf", "reviewer": "Reviewer_BQvB", "summary": "The authors consider the problem of causal discovery in latent variable LiNGAM models under less restrictive graphical assumptions (described in Assumption 1). Specifically, they allow for some observed variables to be connected to each other and some latent variables to be children of observed variables. They propose a two-stage recovery algorithm that primarily relies on the properties of pseudo-residuals in linear non-Gaussian models. Finally, they consider the case where the graphical assumptions are violated and evaluate the performance of the algorithm through simulations.", "questions": "1. What is the exact definition of neighbor? The examples on line 179 rely on the fact that $\\text{Ne}^{\\mathcal{H}_2}(O_1)\\setminus{O_3}=\\emptyset$. This indicates that $\\text{Ne}^{\\mathcal{H}_2}(O_1)$ does not correspond to the sibling set (which is $L_1$) nor the neighbor set in the undirected graph (which is $(O_2, O_3, O_4, O_5)$).\n\n2. How are the augmented nodes ($O'$, $O''$) used in the identification results and algorithms?\nMy understanding is that they are only used in the algorithm, where the algorithm duplicates each observed variable with two extra copies and add non-Gaussian noises to them. \n\n3. Are there any identification guarantees for the recovery output? Specifically, does Theorems 1-6 imply that in linear non-Gaussian model, under Assumption 1 and rank-faithfulness, the underlying model can be uniquely identified? Similarly, doesn Theorems 7-11 imply that if Assumption 1 is not satisfied, then there will be no output?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "The authors provide a detailed theoretical analysis of the proposed algorithm, along with illustrative examples. They also include detailed comparisons of their assumptions and conditions with those of existing work.", "weaknesses": "The main weakness lies in the presentation of the results. Some definitions and concepts are not sufficiently motivated or explained (see Q1 and Q2 below), making certain technical details difficult to understand. Additionally, it would be helpful to include more detailed descriptions of the assumptions and theorems. For instance, in Algorithm 1, Theorem 2 appears to be used solely for partitioning $\\mathbb{S}$ into $\\mathbb{S}_1$, $\\mathbb{S}_2$ and $\\mathbb{S}_3$, rather than adding new IPs to $\\mathbb{S}$. It would be helpful if this kind of explanation (or a very sketched version of Alg 1 & 2) is provided.", "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": "7iI7I1CGO5", "reviewer": "Reviewer_d5Lc", "summary": "This paper proposes an efficient and trustworthy causal discovery method for discovering latent variable structure. The main difference compared with the previous work is that it will raise an error rather than draw an incorrect causal conclusion when the purity assumption is not met.", "questions": "See the weaknesses above.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Some theoretical results are proposed along with an efficient causal discovery algorithm.\n- The overall writing is clear and well-structured.", "weaknesses": "- Although this paper allows violating the purity assumption, the overall identification results and the algorithm mostly rely on the purity assumption, e.g., by locating the pure children like the previous work (e.g., Jin et al., 2024). Whether the purity for identifying the causal structure necessary? What is the complete identifiability under the impurity setting?\n- What is the intuition in obtaining the efficient causal discovery compared with the other works, e.g., which step is the key step in providing a faster discovering ability?", "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": "eRRNV7rwMX", "reviewer": "Reviewer_SqCS", "summary": "This paper considers the problem of causal discovery with latent variables, in a more general setting where the causal relations between observed variables are allowed, with some other structural assumptions (e.g., pure children). Moreover, those assumptions are claimed to be testable, i.e., when the assumptions are not satisfied, the algorithm can raise an error.", "questions": "See above.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The idea to testify the graphical assumptions and give an error signal instead of giving possibly incorrect result is very significant for causal discovery with latent variables.\n\n2. The generalization to allow edges in between observed variables is good.", "weaknesses": "Overall, the current draft's presentation **requires substantial improvement**. It's cluttered with theorem after theorem, while the core algorithm is scattered throughout and described with vague language. This makes it easy for readers (at least me) to lose track, unclear on the purpose of each theoretical statement, and difficult to assess the correctness of all the assertions. I totally understand that the work involves dense technical material and possibly complex algorithms, but this shouldn't excuse its current lack of clarity.\n\nHere are my specific comments/questions:\n\n1. In assumption 1., I guess what the authors meant is pure children or neighbors in the observed variables? Though the observed variables is not within the scope for definition 1.\n\n2. For definition 2 (Identifiable pair, IP),\n   - The definition heavily relies on H2, and the definition for H2 heavily relies on Vf. But so far (when definition 2 is presented) we only have \"Vf is unknown\", \"H2 is unknown\", which makes the understanding to definition 2 at that point very difficult, if not impossible.\n   - Please explain every definition/theorem/algorithmic step's purpose before directly delving into the technical sides (same applies elsewhere). E.g., here what is the general purpose of H2 (instead of the technical definition on \"induced subgraph of G over Vf and VC\")? What does Vf's \"launched in the future\" mean? It's until pg.6 did I notice that the authors want to use Vf for latent variables..\n   - Since VC and Vf can be updated, does the \"identifiable pairs\" changes in each epoch, based on different VC and Vf? Intuitively this shouldn't happen, as it seems describing something regarding the true structure. Then please show that there's no such dependence.\n   - Why is it named \"identifiable pairs\"? Theorem 1 shows a way to sufficiently identify them from data, but are they necessarily all the pure children information that can be identified (e.g., using Adam's formulation of equivalence class)?\n   - Instead of {V1, V2} ∈ S, please use e.g., (V1, V2) to indicate that they are ordered.\n\n3. In definition 4's \"Intuition\", what are those \"e1', e2', ...\"? Are they referring to the noise added to get Oi' in O1 variables?\n\n4. In theorem 2, what does \"let {Vi1, Vi2}⊂ChH1(Vi)\" mean? I understand that at the initialization epoch, ChH1(Vi) is just the corresponding two added O1 variables. But after that, does it mean \"for any two variables in ChH1(Vi), the followings hold\"?\n\n5. In theorem 3, what does \"∀Si ∈ S2\" mean? Before this all the notations for enumerating items in S is in the form of {Vi, Vj} ∈ S. If the authors intend to express a same thing, please be consistent throughout.\n\nOverall, for all the clarity/presentation issues that prevents me to further evaluate the work, I would appreciate it if the authors could provide:\n   - A clear overview of the algorithm: What is the input? What are all the assumptions (except for the structural ones, e.g., at least there should be some faithfulness)? What is the output (to which equivalence class does it identify -- e.g., does it achieve Adam's? which parts are assumed to be correct? when (if and only if) will the algorithm give an error signal)?\n   - A detailed pseudocode for the algorithm. For each step, instead of vague language (like those in the current \"Updating the Active Set\" paragraph), please use formal math/set language. For all the claims on the intermediate results (e.g., those reflected by condition 1, theorems 1, 2), please use \"assert\" lines.\n\n---\n\nSome other methodological questions:\n\n6. Why do the authors need to add new simulated variables O1 into the system? Intuitively they couldn't give any more information than those already encoded in O0. In other words, all information found by O1 should be able to be found by O0. Could the authors please give an example where such intuition is incorrect? Otherwise the O1 seems only adding more unnecessary complexities.\n\n7. What is the relationship between the two main constraints (Pseudo-residual and Quintuple constraint) used in this paper and the GIN condition? If they are special cases for GIN condition, why not directly use the GIN condition? Or can they identify something beyond GIN?\n\n8. Regarding the at-least-2-pure-children assumption, can this algorithm be applied to violation cases e.g., measurement error?\n\n9. Regarding the testability of the assumption, could the authors please give a brief review and compare to how other (linear non-Gaussian acyclic models with latents) work testify their assumptions?", "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)