Recovery of Causal Graph Involving Latent Variables via Homologous Surrogates
Authors: Xiu-Chuan Li
Jun Wang
Tongliang Liu
Venue: ICLR 2025 Poster (2025)
Keywords: causal discovery
latent variables
Primary area: causal reasoning

Abstract: Causal discovery with latent variables is an important and challenging problem. To identify latent variables and infer their causal relations, most existing works rely on the assumption that latent variables have pure children. Considering that this assumption is potentially restrictive in practice and not strictly necessary in theory, in this paper, by introducing the concept of homologous surrogate, we eliminate the need for pure children in the context of causal discovery with latent variables. The homologous surrogate fundamentally differs from the pure child in the sense that the latter is characterized by having strictly restricted parents while the former allows for much more flexible parents. We formulate two assumptions involving homologous surrogates and develop theoretical results under each assumption. Under the weaker assumption, our theoretical results imply that we can determine each variable's ancestors, that is, partially recover the causal graph. The stronger assumption further enables us to determine each variable's parents exactly, that is, fully recover the causal graph. Building on these theoretical results, we derive an algorithm that fully leverages the properties of homologous surrogates for causal graph recovery. Also, we validate its efficacy through experiments. Our work broadens the applicability of causal discovery. Our code is available at: https://github.com/XiuchuanLi/ICLR2025-CDHS

Published as a conference paper at ICLR 2025
RECOVERY OF CAUSAL GRAPH INVOLVING LATENT VARIABLES VIA HOMOLOGOUS SURROGATES
Xiu-Chuan Li Jun Wang Tongliang Liu"
Sydney Al Centre, University of Sydney
ABSTRACT
Causal discovery with latent variables is an important and challenging problem. To identify latent variables and infer their causal relations, most existing works rely on the assumption that latent variables have pure children. Considering that this assumption potentially restrictive practice and not strictly necessary theory, in this paper, by introducing the concept of homologous surrogate, we eliminate the need for pure children in the context of causal discovery with latent variables. The homologous surrogate fundamentally differs from the pure child in the sense that the latter characterized by having strictly restricted parents while the former allows for much more flexible parents. We formulate two assumptions involving homologous surrogates and develop theoretical results under each as- sumption. Under the weaker assumption, our theoretical results imply that we can determine each variable's ancestors, that is, partially recover the causal graph. The stronger assumption further enables us to determine each variable's parents exactly, that is, fully recover the causal graph. Building on these theoretical re- sults, we derive an algorithm that fully leverages the properties of homologous surrogates for causal graph recovery. Also, we validate its efficacy through ex- periments. Our work broadens the applicability of causal discovery. Our code available at:
INTRODUCTION
Causality is a basic concept in natural and social sciences, playing a pivotal role in explanation, prediction, decision making and control (Zhang et al., 2018). In particular, causality has driven significant progress in machine learning (Yao et al., 2021; 2023; Huang et al., 2023; Hong et al., 2024; Lin al., 2024; Sun al., 2024). The gold standard for uncovering causality is conducting randomized experiments, but this is usually prohibitively expensive and time-consuming. Conse- quently, researchers have increasingly turned causal discovery, which aims to infer causal rela- tions from observational data alone. Traditional causal discovery methods typically assume that all task-relevant variables have been enumerated and measured (Spirtes & Glymour, 1991; Chickering, 2002; Shimizu et al., 2006; Hoyer et al., 2009; Zhang & Hyvärinen, 2009), but this assumption often fails in real-world scenarios, prompting the development of causal discovery with latent variables. These methods can be classified into three categories. The first category assumes that latent vari- ables are mutually independent (Hoyer et al., 2008; Maeda & Shimizu, 2020; Yang et al., 2022; Cai et al., 2023). The second category allows the presence of cousally-relatee latent variables but cannot identify latent variables, let alone their causal relations (Spirtes et al., 1995; Claassen et al., 2013; Claassen & Bucur, 2022). The third category not only allows the presence of causally-related latent variables but also can identify latent variables along with their causal relations (Silva et al., 2006; Xie et al., 2020; Huang al., 2022; Jin et al., 2024). Our work belongs the third category.
Recent works in the third category predominantly rely on the pure children assumption that latent variables have pure children. They not only identify latent variables by locating their pure children but also use their pure children as proxies to infer their causal relations. These works can be further categorized into two groups. Some works (Silva al., 2006; Shimizu al., 2009; Kummerfeld & Ramsey, 2016; Cai et al., 2019; Chen et al., 2022; Zeng et al., 2021; Xie et al., 2022; Chen et al., 2023) make the special pure children assumption that each latent variable has multiple pure children.
' "Correspondence Tongliang Liu (tongliang. Iiu hraeliiinnli@@yyyeeee @swddncycyc...uuuu

---

Published as a conference paper at ICLR 2025
Here, a variable is said a pure child of anther only if the latter is the only parent of the former. Other works (Xie et al., 2020; 2024; Huang et al., 2022; Dong et al., 2024: Jin et al., 2024) make the general pure children assumption that each latent variable belongs to a latent set (comprising more latent variables) which has sufficient pure children. Here, a variable is said a pure child of a latent set only if all parents of the former are within the latter. The general pure children assumption is often accompanied by local unidentifiability: for multiple latent variables within a latent set, even the existence (Iet alone directions) of the causal relations between them might be undeterminable. In summary, the concept of pure child is characterized by having strictly restricted parents.
or
Although the pure children assumption widely employed for the sake of tractability, Adams et al. (2021) argue that it is restrictive in practice and prove that it is not necessary for identifiability of linear non-Gaussian acyclic models with latent variables. In this paper; by introducing the concept of homologous surrogate, we eliminate the need for pure children. The homologous surrogate fun- damentally differs from the pure child in the sense that the former allows for much more flexible parents. Specifically, if an observed variable O is pure child of a latent variable L, O must have only one parent L: but if O is a homologous surrogate of L, O is allowed (not mandatory) to have other parents besides L, such as other latent parents provided that they are all L's ancestors. Taking O3 in Fig. 1 as an example, it has two parents L1, L2 where L1 an ancestor of L2. Correspondingly, it is a homologous surrogate but not pure child of L2. It is common that an observed variable is a homologous surrogate but not a pure child of a latent variable. For instance, a company's 's stock price is caused by both its intrinsic value and macroeconomic environment, and macroeconomic en- vironment also impacts its intrinsic value, so its stock price is a homologous surrogate but not a pure child of its intrinsic value. Besides, a boy's violent behavior is caused by both his violent tendency and the parental supervision, and the parental supervision also impacts his violent tendency, so his violent behavior is a homologous surrogate but not a pure child of his violent tendency.
We begin with the assumption that each latent variable has at least one (rather than multiple) homologous surrogate. Under this assumption, we develop theoretical results implying that the causal graph can be partially recovered, that is, we can de- termine whether any variable is an ancestor of any other vari- able. From these theoretical results, we derive an algorithm that sequentially identifies latent variables by locating their homologous surrogates, progressing from roots to leaves, dur- ing which process the causal graph is also partially recovered. We then develop further theoretical results with an extra as- sumption that if latent variable is an ancestor of another, the latter must have two generalized homologous surrogates that are not children of the former, where the generalized homologous sur- rogate is a variant of the homologous surrogate but is subject to fewer restrictions. These theoretical results imply that the causal graph can be fully recovered, that is, we can determine whether any vari- able a parent of any other variable, from which we also derive an algorithm. Building on the partial recovery result, this algorithm first locates latent variables' generalized homologous surrogates, then uses them to infer the causal relations between latent variables. Combining this information with the partial recovery result, the causal graph can be fully recovered. A causal graph that can be fully recovered by our algorithm is shown as Fig. 1, where no latent variable has multiple pure children.
O.
Figure 1:
causal graph that can be fully recovered by our algorithm. I. refers to latent variables while O; refers to observed variables.
The major innovations of our work are summarized as follows.
We introduce new concept called homologous surrogate to facilitate causal discovery with la- tent variables, which fundamentally differs from the pure child. While the latter characterized by having strictly restricted parents, the former allows for much more flexible parents.
We formulate two assumptions involving homologous surrogates and develop novel theoretical results under each assumption. These theoretical results imply that the causal graph can be partially/fully recovered under the weaker/stronger assumption.
Building on our theoretical results, we derive systematic and innovative algorithm which fully leverages the properties of homologous surrogates for causal graph recovery. We demonstrate the efficacy of our algorithm through experiments.
In summary, our work broadens the applicability of causal discovery. It may not only inspire further research in this direction but also benefit research in natural and social sciences. Due to space limit, we defer detailed discussion on related works to App. A.
2

---

Published as a conference paper at ICLR 2025
2 PRELIMINARY
In this paper, we focus on the linear non-Gaussian acyclic model (LiNGAM) with latent variables whose causal graph (V, E) is directed acyclic graph (DAG). V L U O where L and O respectively denote the set latent and observed variables. Each variable in and O follows
Li Σ T,5l.
7 Li Li El 0:
Σ 1.5
%o Li
Σ 0,50
00 0 E0
0, 000,
v, denotes the direct causal strength from V, to Vj, av of and only if Vi is a parent of Vj- Given V E V. we denote its parents, children, neighbors, ancestors, and descendants by Ch(V), Ne(V), An(V), and De(V). Partieularly, a variable's ancestors/descendants include itself. In the following. for any V S V, abbreviate Uvey:Pa(V) to Pa(V'). The latent parents and observed parents of V are denoted by (V) and Pao(V) respectively. ev refers to the exogenous noise of V, all exogenous noises have non-Gaus Gaussann distributions and are independent of each other. Without loss of generality, we assume that each exogenous noise has zero mean and the exogenous noise of each latent variable has unit variance.
not
We can rewrite Eq. (1) in a matrix form as
L
EL
+
(2)
0
E
where
AL
0
A
(3)
A
AO
the adjacency matrix. For VI, V2 V, Ay
v. refers the adjacent matrix from V1 to V2. Since
I A is invertible (Shimizu et al., 2006), we can further rewrite Eq. (3) as
L
M
(4)
0
60
where
(I- (I-
AD--1
M = (1-A)-1=
L
(5)
(I- (0- - A/.
(I (I-A0) -1
M
M
the mixing matrix whose elements are called mixing coefficients. By convention, assume the distribution over V is Markov and faithful to G, which implies that my, # 0 if and only if V; is an ancestor of Vj or V; Vj. In the latter case, m Vi 1.
V.
PARTIAL RECOVERY
Definition 1. (homologous surrogate) O O is called homologous surrogate of L E L, denoted by O HSu(L), i Ch(L), Ch(O) 0, (0) 0)= An(L) U (L) and (n) n Deo(L) 0.
Example. In Fig. 1, HSu(L,) = (02), HSu L2) {O3), HS,(HSuLLL L3) (06). HSu = (O,).
Remark. Given O e and L, we detail the the connections and differences between "O is L's pure child" and "O is L's homologous surrogate" in the following. There is consensus among previous works that if observed variable O is a pure child of latent variable L, then 0 must have no other parent except L. In this case, it is obvious that O E Ch(L), (O). and (O)(O) L.) = 0, that is, 3 out conditions in Def. are satisfied. On this basis, some studies (Silva et al., 2006: Kummerfeld & Ramsey, 2016; Xie al., 2023; Li al., 2024) explicitly require that has no child while others (Shimizu et al., 2009; Cai et al., 2019; Xie et al., 2020; 2022; Huang et al., 2022; Chen et al., 2023) directly assume that there exists observed variables. That is, the remaining condition Ch(O) 0 in Def. is satisfied. O is allowed to have children of its own only in very few works (Dong al., 2024; Jin et al., 2024). Therefore, if is pure child of L in most senses, then O is also homologous surrogate of L. The reverse necessarily true because L's homologous surrogate is allowed to have other parents.
An(L) (L)
edge between
3

---

Published as a conference paper at ICLR 2025
Intuition. Suppose O is L's homologous surrogate. If L is root variable, then O has child and only one latent parent L. Otherwise, with both L's ancestors and observed variables whose latent ancestors no child and only one latent parent I.. Because of this, homologous surrogates can be located from observed variables.
subset of L's ancestors removed, L becomes root variable and O still has
Assumption 1. VL L. HSu(L) * 0 and [Ch(L) 2 2.
Example. The causal graph shown as Fig. satisfies Asmp. 1.
Remark. In previous works making the pure children assumption, the number of latent variables must be strictly smaller than their pure children. Instead, we only require one homologous surro- gate per latent variable.
Intuition. Assuming that each latent variable has a homologous surrogate, latent variables can be sequentially identified by locating their homologous surrogates, progressing from roots to leaves, during which process the causal graph also partially recovered. Also, we assume each latent variable has multiple children, otherwise it can be modeled as noise (Silva et al., 2006).
High-level Overview. First, we identify observed root variables (Thm. I), estimate their effeets on others (Cor. 1), and then remove them (Cor. 2). Second, we identify latent root variables (Thm. 2, Props. and 2), estimate their effects on others (Cor. 3), and then remove them (Cor. 4). Repeating these procedures until all observed variables and partially recover the causal graph. During this process, all operations on latent variables are implemented through their homologous surrogates.
removed, we identify all latent variables
Initialization. We denoted the set of removed variables by J U K where J s L. O. In addition, for each O₁ O,K, there is an auxiliary variable O, which is linear combination of O and variables in K where the coefficient of O, is always while that of each variable in K is not = so O, O, for each O; O, is trivial that Cond. is valid.
fixed. Initially, we let
Condition 1. (1) For each V V K), De(V) (J K) 0. (2) For each J and O e K where Ch(O) # 0, m = m O = O.
$ Identifying Observed Root Variables. This can be accomplished based on Thm. 1. Definition 2. Residul-residull (Cai et al., 2019)) Given three variables V1, V2, V3 s.t. Cov(V2, V3) # the pseudo-residual of V1, V22 relative to V3 is defined
R(V. 1211) V1 Cov(Vi, V3) Cov V3) V22
(6)
Intuition. Pscudo-residual is simple variant of the conventional residual. The former reduces
to the latter when V22 V3. Before Cai et al. (2019), similar concepts have already been used by earlier works (Drton & Richardson, 2004; Chen et al., 2017).
Theorem 1. Suppose O, O,K, then An(O,) (JUK) if and only V0 e OO(KU (O1)), 0,10), Ö,
Intuition. The part before "if and only if" means that all ancestors of O; are in J J K, that is, O is root variable among (J K); the part after "if and only if" means that O, satisfies certain independence constraints. Therefore, this theorem provides a method for identifying observed root variables via statistical analysis.
Example. Suppose the underlying causal graph is shown as Fig. 1. Initially, K = 0. We can identify 0 an observed root because VO, E (02, ..., O R, O, 0, 1 Ō,
$ Estimating the Effects of Observed Root Variables. This can be accomplished based Cor. 1.
O, Corollary 1. Suppose O; satisfies Thm. 1, then v0, OY(K U (O,)), mo CO,(O,,O,)
Cov(O..O,)
4

---

Published as a conference paper at ICLR 2025
Remark, With the faithfulness assumption, O is a descendant of O, if and only if m * 0.
Removing Observed Root Variables. This can be accomplished based on Cor. 2.
O Corollary 2. Suppose O, satisfies Thm. 1, if we update K to K U (0i) and Ô, to , o, o, for each O2 e O,K, Cond. is still valid.
Remark. With observed root variables removed, some observed non-root variables before removal might become roots after removal, so we need to repeat the above three steps until there is no observed root variable, that is, no observed variable satisfies Thm.
$ Identifying Latent Root Variables. We identify latent root variables by locating their respective homologous surrogates from observed variables. However, this cannot be achieved in single step. Instead, we first locate observed variables that might be homologous surrogates (called candidate homologous surrogates) latent root variables (Thm. 2), then check whether any two them share common latent parent (Prop. 1), and finally find true homologous surrogates (Prop. 2).
Theorem 2. Suppose VO E O,K, An(O) & JUK. K. Given O; O,K, then Ch(O,) = 0, (a = 0, (O,))
1, and An(Pai, (O))J)) s if and only if v(O,, 0x} s OY(K U (Oi)) where Cov(Ó,,0)) (,),o,,)ovCC...o # O, R(O),00l0O O,
Intuition. The opening supposition requires that no observed variable O is a root variable among VJ U K), which can be ensured by iterating the aforementioned three steps involving observed root variables until there is no observed variable in OYK satisfying Thm. 1. In the subsequent statement, the part before "if and only if" means that O; has no child, no observed parent in O K, and only one latent parent in LAJ which is exactly a root variable among (JUK). This is necessary but not sufficient condition for O, being homologous surrogate of a latent root variable among (JUK) (further explained in Remark later); the part after "if and only if" means that O, satisfies certain independence constraints. Therefore, this theorem provides method for identifying candidate homologous surrogates of latent root variables via statistical analysis.
Example. Suppose the underlying causal graph shown as Fig. After removing the observed root variable O based on Thm. 1, 0. K = (01). At this point, VO (O2..., On1. An(O) g {01). Then we can identify O2 as a candidate homologous surrogate of latent root variable because V(Oj,
{03..., O11 R(O OxlŌ2) O2.
Li
Le
La
Remark. Based on Def. 1, is trivial that the part before "if and only if" is necessary condition for O; being homol- ogous surrogate of a latent root variable among VV U K), so we will not omit any homologous surrogate of any latent root variable. However, this is not a sufficient condition, an example is shown as Fig. 2, this theorem can only be used to locate candidate homologous surrogate.
O, 0 O
0:
0: 0.
Figure 2: When J (L1 L2, L3)
and K (0,, O2, 03). O4 satisfies
Thm. 2 but O4 & HSu(L.)
Proposition 1. Suppose O, and Oj satisfy Thm. 2, then Par (O,) Par (O if and only if Cov( 0,) # 0.
Proposition 2. Suppose O; satisfies Thm. 2, then O; (Os((aa andddnlyy i/ satisfying Thm. and ( (O,) [IM) llo s |IM|,,
Estimating the Effeets of Latent Root Variables. This can be accomplished based on Cor. Definition 3. (Cumulant) Given random variables Vi.... Vn. the k-th order cumulant is defined as a tensor of size n ... X (k times), whole element at position (i1...., ix) is
Cum(V, Vi = -1- 1)!
B
Vj
(7)
BEX
JEB
where is enumerated all partitions of (i1...,ik))

---

Published as a conference paper at ICLR 2025
Algorithm 1: Partial recovery of the causal graph under Asmp. 1.
Input: O
Output: An(V) for each V E V, My Mg
Initialize J= 0, and Ô == O.
while K # do
while there exists O E O satisfying Thm. do Identify all observed root variables O' based on Thm. 1.
Estimate O based on Cor. and find De(O') for each O' O'.
Remove based on Cor.
end
Identify all latent root variables L' based Thm. 2 plus Props. I and 2. Estimate ML. O based on Cor. and find An(!"), (I.(()) for each 1.' L/. Remove L' based on Cor. 4.
10
11 end
Remark. High-order cumulants have been widely used the community of signal processing since the last century, especially in the topic of independent component analysis (ICA) (Thi & Jutten, 1995; Hyvärinen Oja, 1997; Belkin et al., 2013; Voss et al., 2013; Ge Zou, 2016), which is closely related to causal discovery (Shimizu et al., 2006; Hoyer et al., 2008).
Corollary 3. Suppose O, satisfies Thm. and O, E HSu( then vO, e OK(K U (01)),
Li m mo
2
(,,nO,,,,,0,,000 Cum( Cum(0..0,,00,00)
L O o O,),
(8)
Remark. Let m > 0 without loss of generality, we can obtain m and m With the faithful- ness assumption, Oj is a descendant of L; if and only if m'; 0. Ln is an ancestor of L; if and only if mh 0 since An(L,) (O))
O.
S Removing Latent Root Variables. This can be accomplished based on Cor. 4. Corollary 4. Suppose O; satisfies Thm. 2 and O; E HSu(L)), if we update J to J U (L4), to KU (0,), and Õ, to Ō, (m')) 1 , each O, E O,,K, Cond. is still valid.
$ Summary. The algorithm is summarized in Alg. 1 with O(10)+) complexity, of which the process shown as Fig. and detailed below.
(1) Initially, K 0, Ô; 0;,
(2) First iteration shown as Fig. 3()) Alg. identifies 0₁ as an observed root among V) K), calculates m mo,' and updates K == K U (O1), := Ô, m Ô,. There is De(O1) (02)
(because mo: # O). Next, it identifies L1 as a latent root among V U K) with HS,) (02), calculates m L1 and updates J := Ju (L1), K Ku (02), Ô, Ô, - (m /m / )2)-- There is Deo(L,) (02, .... O11) (because m. * O,..., # #).
(3) Second iteration shown Fig. 3(c): Alg. identifies no observed root among VY K).
Next, it identifies L2 as a latent root among V\ U K) with HSu(L,) = {03), calculates
n and updates J = J (L2), K == K U (0s). Ô, = Ô, (m 0 /m o. (3) There is Deo(L2) (03, On) and An(L2) = (L1} (because O3 HSu(L2) and L1 An(O3)).
(4) The following iterations proceed similarly. Particularly, the last iteration shown Fig. 3(), Os. Og. O10. O₁ are added into K progressively: Alg. first identifies O as an observed root among VVJJ U K) and updates K K U (010), then it identifies Og, O1 as observed roots among VVJJ U K) and updates K == K (0s, On). Finally, it identifies O₂ as an observed root among (J(JU) K) and updates K K (0s).

---

Published as a conference paper at ICLR 2025
0 D
0n
0
0
De
0
0e 8.
0
6
0.
0
0e
O. 8.
(c)
00
Dn On
On On
0n
(c)
Figure 3: Illustration of Alg. I, where solid arrow refers to parental relationship while dashed arrow refer to ancestral relationship. (a) Ground truth. (b-c) Result of each iteration.
Theorem 3. Suppose the observed variables generated by a LiNGAM with latent variables satisfying Asmp. 1, in the limit of infinite data, Alg. identifies latent variables and ancestral rela- tionships correctly.
4 FULL IDENTIFICATION
Definition 4. (Generalized homologous surrogate) is called a generalized homologous
surrogate of I. L,, denoted by GHSu(L.,, if0 Ch(l.) and (O)(O) An(I.) (L.)
Example. In Fig. 1, (H) = (02). L2) = {03, O+. Os). GHSu(La) = {06. O7. Os), GHSu(L4) (Og, 110, O11).
Remark. Trivially, if O is L's homologous surrogate, it must be L's generalized homologous surrogate, but the reverse is not necessarily true. This is what "generalized" means.
Intuition. With causal relations between observed variables removed, for every latent variable, the ancestors of its each generalized homologous surrogate exactly its ancestors plus itself. Because of this, generalized homologous surrogates can be located from observed variables.
Assumption 2. Asmp. holds and V(L, Lj} where L, An(L,). 3(0,, O²² S GHHu(L,)) s.1 0 j & Ch(L,) and 0j & Ch(L.).
Example. The causal graph shown as Fig. satisfies Asmp. 2.
Remark. An extremely special case where this assumption holds is that each latent variable has multiple observed pure children.
Intuition. Since Asmp. holds, MY and MO can be estimated by Alg. 1. For every two latent variables L, Lj where L, is an ancestor of Lj. mLj can be estimated through Lj two generalized homologous surrogates that are not L;,s children, so we can also estimate ML; A can be readily recovered from M composed of MI; 0. My. MD that is, the causal graph be fully recovered.
High-level Overview. Building on the partial recovery result, we first remove causal relations between observed variables. Second, with these relations removed, locate generalized homolo- gous surrogates of each latent variable (Lem. 1). Third, through these surrogates, we estimate ML.
progressively (Thm. 4). Finally, given M composed of MI; 0. M.M Mo. recover A.
Removing Causal Relations Between Observed Variables. M is estimated by Alg. 1, from which A can be recovered by A = I- (Mg) following Eq (5). Given A we can remove causal relations between observed variables. Specifically, for each O; O, let
0, = 0,
Σ
a
01
(9)
7

---

Li Published as a conference paper at ICLR 2025
Algorithm 2: Full recovery of the causal graph under Asmp. 2.
Input: O, L, My MO returned by Alg. 1.
Output:
Remove causal relations between O based on Eq. (9).
Locate generalized homologous surrogates of each latent variable based on Lem.
i :=
while there exists I. E s.t. De' (1.) 9 do Estimate mL and a for each L L, L' e De (L), GHSu(L') based on Thm. 4.
i i
end
Recover A from M based on Eq. (5).
Note that My is also estimated by Alg. 1, then for each E L.
m = m
Σ
0, mb
o m
(10)
()EP)(O,)
Locating Generalized Homologous Surrogates. This can be accomplished based on Lem. 1.
Lemma 1. VL; L and O; O, O; e GHSu(La) if and only if m # O and yOj O where L no
# O, (o; Ilo s ( ll.. Besides, there a =m o
$ Estimating MI. For ease of exposition, we introduce the concept of n-hop descendants (Def. 5). M is estimated in progressive manner. Specifically. for each latent variable, first estimate the mixing coefficient from itself to its every I-hop descendant (Thm. 4(1)) and then the direct causal strength from itself to its every 1-hop descendant's each generalized homologous surrogate (Thm. 4(2)). On this basis, we investigate each latent variable's s 2-hop descendants. Repeating this process, M can be estimated finally.
Definition 5. (n-hop descendant) Given Li) L, we call Lj is an n-hop descendant of Li, denoted by Lj- E De" (L,), if L,j De(L,) and the longest directed path from L; to L.j has length n.
Remark. Given the partial identification result, we can derive n-hop descendants for each latent variable and each n. Specifically, suppose I.j De(L.),, we find the longest array that starts with L, and ends with Lj. in which any variable is an ancestor of the variable that follows it. If the array has length then L, De" DL).
Theorem 4. Suppose (L,, L,} C LL E (L),, vO, E GHSu(L,), let
nb; = =o;
Σ
m
m doj
(II)
LEDe(L))
(a) There exists (0 S GHSu(L,) wbr jaon =oo Jdon Lj
jaly Li by and m Li
m'; laon
Ia (b) a =oo m mi "0;
Remark. Given L, E De, and O, E GHSu(L,), if we have already investigated De (L), D (L) for each e L, then m
J. and L d0 in RHS of Eq. (11) are known. Moreover, 0
RHS of Eq. (11) can be derived from Eq. (10), so Poj La in LHS of Eq. (11) is known. In fact, di Ho; exactly d'o, + +m ao, (see Eq. (53) in App. C.3). With Hoj known, (a) provides a method to estimate m through Ly's some two generalized homologous surrogate O,, and O where O₁ and jj are exactly those variables that are not L,'s children (see proof in App. C.3), and (b) provides a method to estimate d for each 0, GHSu(L,) using the just estimated m
8

---

Published as a conference paper at ICLR 2025
L b 4
0' O. 0% d' O. O. d' O. 0¹ and
0. o. d. 0. 0: 0. 0 Or d: 0
0. d.
0.
8.
0.
0.
0
0:
0:
00
(a)
(b)
(c)
0. 0. 0
0. 0. 0. 0.000'
0. ds de Cr or D.
0:
0.
02
0.
8
0e
U0
(d)
(c)
n
Figure 4: Illustration of Alg. 2, where solid arrow refers to parental relationship while dashed
arrow refer to ancestral relationship. (a) Removing causal relations between observed vari- ables. (b) Identifying generalized homologous surrogates of each L L. (c-e) Investigation to
De (L), De (L.), De (I.) for each L. (f) Recovering A from M.
Example. In Fig. 1, L3 E (L,) and GH)u(L3) = (06, O7, Oz).
According to Eq. (11), Then we can calculate m Li 12 Os'
No; L. = of 12 a La oo; = o T1 or and 4 Ho; = m L1
oz
Li based on (a) and af o o based (b). m L3
Recovering A. M is composed M 0, My MO where ML is just estimated and My M are estimated by Alg. 1, so we can readily recover A from M by M = AI- following Eq (5).
Summary. The algorithm is summarized Alg. 2 with 0( complexity. With the result returned by Alg. as the input, its procedures are shown as Fig. 4 and detailed below.
(1) Fig. 4(a): Alg. 2 removes causal relations between observed variables.
(2) Fig. 4(b): Alg. 2 locates generalized homologous surrogates. Specifically, it determines
GHSu L1) = {02), G2Su(L2) = {03. O4, Os), GHSu L3) = (06, Oz). GHSu(L4)
{O,, O On). Also, it determines A (4) A (42)
[O:)' (0s,0..:3)" A (4a) (0..0r00,)' A (14) (O..0m.On1'
(3) Fig. 4(c): Alg. investigates (L) for each
L: De' {L2), De (L2) {L3), (Li)
De' (14) = (L4). It estimates mi "1""" 11
(La) Ls and then (0,.0.0,)) (r,.0%.0g) (0.00p000)
(La)
where only 0g 0x. "on
are non-zero.
(4) Fig. 4(d): Alg. 2 investigates De for each L E L: De (L3), De2(L) (L4)- It estimates ig m and then A (Li) (O,,0r.0,)* A (L2) (0..0m.0n) where only d/j Oio are non-zero. (5) Fig. 4(d): Alg. 2 investigates (L) for each L L: De² (L1). It estimates m and
then A (L,) (O0,.10.0.) where only d is non-zero.
(6) Fig. 4(f): Alg. 2 recovers A from M.
Theorem 5. Suppose the observed variables generated by LiNGAM with latent variables satisfying Asmp. in the limit of infinite data, Algs. I and 2 together identifies latent variables and parental relationships correctly.
EXPERIMENT
We first use four causal graphs shown Fig. to generate synthetic data. For each causal graph, we draw 10 sample sets of size 5k, 10k, 20k respectively. Each direct causal strength is sampled from a uniform distribution over [-2.0, -0.5] U [0.5, and each exogenous noise generated from exponential distribution. We compare our methods with GIN (Xie et al., 2020), LaHME (Xie et al., 2022), and PO-LiNGAM (Jin et al., 2024). We use 3 metrics to evaluate their performances: (1) Error in Latent Variables, the absolute difference between the estimated number of latent variables and the ground-truth one; (2) Correct-Ordering Rate, the number of correctly estimated causal or- derings divided by that of fround-truth causal orderings; (3) FI-Score of causal edges. Results summarized Tab. I, where we also report the running time. In particular, we set the size of the largest atomic unit in GIN and PO-LiNGAM 1 for a fair comparison.

---

Published as a conference paper at ICLR 2025
1
0
00
01
0
0
0.
0u
0
0.
6
0
0.
0.
00
0u
0u
On
02
G991
1
G
4
On
G
Figure 5: Causal graphs used to generate synthetic data.
Table 1: Comparison on synthetic data. 1 means higher is better while means lower is better.
Vanadee
FTS
Rumning
5%
51
CIN
0.3720007
1.002000
LUVEUII
Case
LaHME
0.8-0.6
1
0.5.0.5
1.30
0.140.3
1
0.8750.18 18
087.0.00
0.7
091+0.10
0.3400
0.96-0.5
15
0.7740.18
0.70
16
0
0.76
0.844011
0.7640007
0:9840.06
121 21162-27330 26
2,0120.14
16631127.64
2,32.0,25
19.5941661
2,9660.25
Ours
0.400.5
0.1
0.000.0
09440.07
0.9908.03
1.000.00
0.02
10
0.98
0.59
2.6460.27
3.05:0.22
4.1:0008
CIN
1.8504
3.
4.1.0.5
0:0700:04
0.0600003
0.0500.04
0.
0.15500
0.1380.05
3,3368.31
3447:0.33
4.1361144
Casz 2
PO PO-LINGAM
LaHME
3.9g1.3
1.fe.00
4.3e1.2
1.7.0.9
3.92
2.1e1.0
0.200.227
0.4500.00
0.12
04550004
0.12
0.35 12
0.15a0.15
0.4360.06
0.12x0.115
0.4120.66
0.1749.23
0.3929.07
2214.192779.92
36,60114.43
2073.976678.85 87535
86.45:7108
116, 158.1556..6 66
3482.57470488 83
Ous
1.25066
0.7
0.2g0.4
0.8220.00
0.91
10
0.97
0.77
0.5820.13
0.9428907
6.2760.54
7.72-0.33
9.6921.72
CIN
13100:0
01
0.11
0.31
1000
144456112
1.998.111
123:0.11
Coer 9
PI-LINGAM
LaHME
2.le1.0
1,5
2.51.0
0.8.0.9
0/669
2.76099
0.37
0.55pp 19
0.26
0.36g0
17 0.00t00 17
0.
0.1950009
0.5860.13
0-4850
15
13
0.48200
10
0.46640007
295
6,368
35544879 55
289 99590006
369, 12431 AM
10.26+ 19
Oues
1.4088
0.8c0.4
0.5e
0.71=0.15
0.34
0.91=0.08
0.336.117
0,7628.06
0.51=8807
2.5880.54
3.23.0.28
4.36g0 36
CUN
4.8-034
4.9.0
5.0000
00)-000
07000000
(0005000))
0.7916.77
1L87:8.88
Cucc
PO LINGAM
LaHME
4.0.000
4.9.0.3
4.8
4.220.4
4.12000
4.5603
0.
0.1120:00
00000000
0022000
0.0140102
0.10g0000
0.0280001
0.30g0000
0.00g:0004
0.26g0:12
0:0260.00
0.2740.05
03. 63.39216.79
11.88:1.48
6907-11731
13:011147
89.61226.55
17.5148995
Ours
21211
2.1.1
3.000
0.44-9.11
041
0.25
0.5366.16
0.53e6.09
0.50+8.02
1 1,080022 26
1.85-0.11
2.5088008
In case 1, each latent variable has at least two observed pure children, GIN and our algorithm demonstrate optimal performance. In other cases, the pure children assumption not valid, so previous methods cannot handle these cases properly. In case 2, Asmp. 2 is valid, so our algorithm invalid, Asmp. 1 holds, so our
significantly outperforms others. case 3, although Asmp. algorithm still reaches the best performance, especially high correct-ordeingg rate. In case 4, the violation of Asmp. leads to a remarkable degradation in the performance of our algorithm, although it still exhibits remarkable advantage over others since it can still identify L1 and L2- Moreover, in most cases, our algorithm is far more efficient than both LaHME and PO-LiNGAM. This is because LaHME has factorial complexity w.r.t. the number of variables in the worse case while PO-LiNGAM has exponential time complexity in the worst case.
Although our algorithm eliminates the need for pure children, acknowledge that it cannot yield satisfactory results when the sample size is small. For instance, in Case 2 where Asmp. 2 holds, our algorithm can achieve 0 error in latent variables, 1 correct-ordering rate, and F1-score theoretically, but it performs poorly in practice when the sample size is 5k. This can be attributed to two main factors. First, our algorithm estimates the mixing coefficients from latent to observed variables through high-order cumulants. Compared to covariances, high-order cumulants are more sensitive to extreme values and outliers, especially when the sample size is small. Second, our algorithm operates in progressive manner, of which each step builds upon the previous one, so errors are propagated and amplified during this process.
Besides synthetic data, we also evaluate algorithm on a real-world dataset Holzinger and Swine- ford 1939 (Rosseel, 2012). More details are provided in App. D.
6 CONCLUSION
In this paper, we introduce a new concept called homologous surrogate to facilitate causal discovery with latent variables, which fundamentally differ from the pure child. We formulate two assumptions involving homologous surrogates and develop a series of novel theoretical results under each as- sumption, implying that the causal graph can be partially/fully recovered under the weaker/stronger assumption. Also, building our theoretical results, derive algorithm that fully utilizes the properties homologous surrogates for causal graph recovery. Our work broadens the applicability of causal discovery and may benefit research in natural and social sciences.
Limitations. First, our algorithm cannot handle the latent hierarchical structure where some latent variables have observed children. Second, this work does not accommodate non-stationary (Liu & Kuang, 2023) and cyclic (Sethuraman et al., 2023) causal relations. We will endeavor to overcome these limitations in the future.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
Tongliang Liu is partially supported by the following Australian Research Council projects: FT220100318, DP220102121, LP220100527, LP220200949, ICI90100031. Xiu-Chuan Li is par- tially supported by ARC FT220100318. Jun Wang is partially supported by the JD Technology Scholarship for Postgraduate Research in Artificial Intelligence.
REFERENCES
Jeffrey Adams, Niels Hansen, and Kun Zhang. Identification of partially observed linear causal models: Graphical conditions for the non-gause con-gaussian and heterogeneous cases. In Conference 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. p 372-407, 2023.
Mikhail Belkin, Luis Rademacher, and James Voss. Blind signal separation in the presence of gaussian noise. In Conference on Learning Theory, pp. 270-287, 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-45462, 2023.
Ruichu Cai, Feng Xie, Clark Glymour, Zhifeng Hao, and Kun Zhang. Triad constraints for learning causal structure of latent variables. In Conference Neural Information Processing Systems, pp. 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. 3380-3407, 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 Artificial Intelli- gence, volume 36, pp. 6357,, 2022.
Zhengming Chen, Feng Xie, Jie Qiao, Zhifeng Hao, and Ruichu Cai. Some general identification re- sults for linear latent hierarchical causal structure. International Joint Conferences on Artificial Intelligence, 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 on Uncertainty Artificial Intelligence, pp. 172-181, 2013.
Diego Colombo, Marloes H Maathuis, et al. inder-inde constraint constraint-based causal structure learning. Journal of Machine Learning Research, 15:3741-3782, 2014.

---

Published as a conference paper at ICLR 2025
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 Learning Representations, 2024.
Mathias Drton and Thomas S Richardson. Iterative conditional fitting for gaussian ancestral graph models. In Conference Uncertainty in Artificial Intelligence, pp. 130-137, 2004.
Rong Ge and James Zou, Rich component analysis. In International Conference on Machine Learn- ing, pp. 1502-1510, 2016.
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. 1549,5561, 2022.
Zhuo Huang, Xiaobo Xia, Li Shen, Bo Han, Mingming Gong, Chen Gong, and Tongliang Liu. Harnessing cuttof-diistibbution examples via augmenting content and style. In International Con- ference on Learning Representations, 2023.
Aapo Hyvärinen and Erkki Oja. fast fxed-point algorithm for independent component analysis. Neural computation, pp. 1492, 1997.
Yibo Jiang and Bryon Aragam. Learning nonparametric latent causal graphs with unknown inter- ventions. In Conference on Neural Information P Processing Systems, pp. 14468-60513, 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: A 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. Conference on 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 Neural Information Processing Systems, 2023.
Erich Kummerfeld and Joseph Ramsey, Causal clustering for 1-factor measurement models. ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1655-1664, 2016.
Thue Duy Le, Tao Hoang, Jiuyong Li, Lin Liu, Huawen Liu, and Shu Hu. A fast pc algorithm for high dimensional causal discovery with multi-core pcs. IEEE/ACM Transactions Computa- tional Biology and Bioinformatics, 16: 16:1483-1495, 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.
12

---

Published as a conference paper at ICLR 2025
Yexiong Lin, Yu Yao, and Tongliang Liu. Learning the latent causal structure for modeling label noise. In Conference on Neural Information Processing Systems, 2024.
Chenxi Liu and Kun Kuang. Causal structure learning for latent intervened non-stationary data. In International Conference on Machine Learning, pp. 21756-111777 2023.
Takashi Nicholas Maeda and Shohei Shimizu. Red:
Repetitive causal discovery of linear non- gaussian acyelic models with latent confounders. In International Conference on Artificial Intel- ligence and Statisticx, 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: 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.
Yves Rosseel. lavaan: An package for structural equation modeling. Journal of statistical software, 48:1-36, 2012.
Muralikrishnna G Sethuraman, Romain Lopez, Rahul Mohan, Faramarz Fekri, Tommaso Bian- calani, and Jan-Christian Hütter. fodags-flow: Nonlinear cyclic causal structure learning. In International Conference on Artificial Intelligence and Statistics, pp. 6371-6387 2023.
Shohei Shimizu, Patrik O Hoyer, Aapo Hyvärinen, and Antti Kerminen. A linear non-gaussian acyclic model for causal discovery. Journal of Machine Learning Research, pp. 2003-2030, 2006.
Shohei Shimizu, Patrik O Hoyer, and Aapo Hyvärinen. Estimation of linear non-gaussian acyclic models for latent factors. Nearocomputing, pp.
2009.
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 in Artificial Intelligence, pp. 499-506, 1995.
Chandler Squires, Anna Seigal, Salil S Bhate, and Caroline Uhler. Linear causal disentanglement via interventions. In International Conference on 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 trane-transition processes for individual- ized reinforcement learning. Conference on Neural Information Processing Systems, 2024.
Hoang-Lan Nguyen Thi and Christian Jutten. Blind source separation for convolutive mixtures. Signal processing, 45:209-229, 1995.
James Voss, Luis Rademacher, and Mikhail Belkin. Fast algorithms for gaussian noise invariant independent component analysis. Conference on Neural Information Processing Systems, pp. 2552,, 2013.
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 -an--aussiin latent hierarchical structure. International Conference on Machine Learning, pp. 24370-24383 24387, 2022.
13

---

Published as a conference paper at ICLR 2025
Feng Xie, Yan Zeng, Zhengming Chen, Yangbo He, Zhi Geng, and Kun Zhang. Causal discovery of I-factor measurement models linear latent variable models with arbitrary noise distributions. Neurocomputing, 526:48--688 61, 2023.
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:1-61, 2024.
Yuqin Yang, AmirEmad Ghassami, Mohamed Nafea, Negar Kiyavash, Kun Zhang, and Ilya Sh- pitser. Causal discovery in linear latent variable models subject to measurement error. In Confer- ence on Neural Information Processing Systems, pp. 874-886, 2022.
Yu Yao, Tongliang Liu, Mingming Gong, Bo Han, Gang Niu, and Kun Zhang. Instance-dependen label-noise learning under a structural causal model. In Conference on Neural Information Pro- cessing Systems, pp. 4409-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-3966777 2023.
Yan Zeng, Shohei Shimizu, Ruichu Cai, Feng Xie, Michio Yamamoto, and Zhifeng Hao. Causal discovery with multi-domain lingam for latent factors. In International Joint Conferences on Artificial Intelligence, pp. 2097-2103, 2021.
Jiaqi 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 and Aapo Hyvärinen. On the identifiability of the post-nonlinear causal model. In Conference on Uncertainty in Artificial Intelligence, pp. 647-655, 2009.
Kun Zhang, Bernhard Schölkopf, Peter Spirtes, and Clark Glymour. Learning causality and causality-relate learning: some recent progress. National science review, pp. 26-29, 2018.
14

---

Published as a conference paper at ICLR 2025
A RELATED WORKS
Most traditional causal discovery methods (Spirtes & Glymour, 1991; Colombo et al., 2014; Le et al., 2016; Chickering, 2002; Shimizu et al., 2006; Hoyer et al., 2009; Zhang & Hyvärinen, 2009; Peters et al., 2014; Mooij et al., 2016) assume the absence of latent variables. Since latent variables ubiquitous in real-world scenarios, extensive research has been devoted causal discovery with latent variables. Our work is most related to those that not only allow causally-related latent variables but also can identify latent variables along with their causal relations, most of which make the pure children assumption. More specifically, some works (Silva et al., 2006; Shimizu et al., 2009; Kummerfeld & Ramsey, 2016; Cai et al., 2019; Chen al., 2022; Zeng al., 2021; Xie al., 2022; Chen et al., 2023) make the special pure children assumption that each latent variable has multiple pure children, where variable is said a pure child of anther only if the latter the only parent of the former. Others (Xie et al., 2020; 2024; Huang et al., 2022; Dong et al., 2024; Jin et al., 2024) make the general pure children assumption that each latent variable belongs to a latent set (comprising one or more latent variables) which has sufficient pure children, where variable is said pure child of a latent set only if all parents of the former are within the latter. Although the general pure children assumption is weaker than the special one, it comes at the cost of local unidentifiability. Specifically, a latent set contains multiple latent variables, none of which has its own pure children, even the existence of causal relations between these latent variables cannot be determined, let alone their directions. By introducing the concept of homologous surrogates, our work eliminates the need for pure children, in stark contrast to the above studies.
Although the pure children assumption has been widely adopted by previous works, Adams et al. (2021) argue that it is restrictive in practice and also not necessary for identifiability of linear latent non-Gaussian models in theory. They develop a causal discovery algorithm under the assumption which exactly sufficient and necessary for identifiability. Unfortunately, this algorithm is un- practical as acknowledged by themselves. First, it estimates Mý via overcomplete independent components analysis, which requires the number latent variables as prior knowledge and is com- putationally intractable. Second, to recover A from MY it needs to test which submatrices" singular values are exact zeros, which is quite sensitive to noises. Recently, Li et al. (2024) suggest that a pseudo-pure pair, composed of two adjacent observed variables that both become pure children of same latent variable if the edge between them is removed, can be transformed into two pure children under certain assumption. Based this finding, they propose a practical causal discovery algorithm free from the pure children assumption. Clearly, our work diverges significantly from existing works these two studies, offering a novel perspective on causal discovery with latent variables.
While the works discussed above all focus on the linear case, several studies have ventured into nonlinear problems, but most assume access counterfactual data (Brehmer al., 2022; Ahuja et al., 2022) or interventional data (Ahuja et al., 2023; Jiang & Aragam, 2023; Buchholz et al., 2023; Zhang et al., 2023). Notably, without structural restrictions such as our homologous surrogates assumption, even linear causal models are unidentifiable without comprehensive interventional data obtained by intervening on each latent variable individually (Squires et al., 2023). To the best of our knowledge, only Kivva et al. (2021) and Kong et al. (2023) can handle non-linear problems with latent variables using solely observational data, but they both make strong assumptions, e.g., all latent variables are discrete and the mapping from all exogenous noises to observed variables are invertible. We leave further research on nonlinear problems to our future work.
B NOTATIONS
We summarize notations in Tab. 2
15

---

Published as a conference paper at ICLR 2025
Table 2: Summary of notations.
Notation
Description
First appeared
G
Causal graph
Sec. 2
L
Set latent variables
Sec.
O
Set of observed variables
Sec.
V
L U O
Sec.
A latent variable
Sec.
O,
An observed variable
Sec.
Vi
A latent or observed variable
Sec,
ev;
Exogenous noise of V;
Sec.
Pa(V)
Parents of V
Sec. 2
Pa(V")
Uvev Pa(V)
Sec,
(V)
Latent parents of
Sec.
(V)
Observed parents V
Sec.
Ch(V)
Children of V
Sec.
Ne(V)
Neighhors
Sec.
An(V)
Ancestors of V
Sec. 2
Do(V)
Descendants of V
Sec,
a
direct causal strength from V/2 to V, mixing coefficient from to Vj adjacency matrix from to mixing matrix from Vj to V2 Homologous surrogates of HSu(V)
Sec.
my
Sec.
A
Sec.
M,
Sec.
Def. in Sec. 3
Set removed latent variables Set of removed observed variables
Sec,
K
Sec. 3
ó,
Auxiliary variable O; satisfying Cond. 1(2)
Sec.
R(V. V2(33)
Pseudo-residual of Vi, V2 relative
Def. Sec,
GHSu(V)
Generalized homologous surrogates of V
Def. 4 in Sec, 4
O
O, with its all observed parents removed n-hop descendants of
Eq (9) in Sec.
(L)
Def. in See,
K
{O E K/Ch(O) # 0)
Eq. (15) in App. C.2
K2
{0 E KJCh(O) = 0}
Eq. (16) in App. C.2
G'
G with all causal relations between observed variables removed
App.
O'
{0"10 O}
App. C.3
C PROOF
C.1 IMPORTANT LEMMAS
Darmois-Skitovice (D-S) Theorem. (Kagan et al., 1973) Suppose two random variables Vi and V. both linear combinations of independent random variables (m:h:
Vi Σ aam,
V = >Bmm
(12)
Then, V, TL Vz, each n; for which a, # 0 follows Gaussian distribution. That is, if there exists a non-Gaussian nj a;β; # 0, V1 ı Vz.
16

---

Published as a conference paper at ICLR 2025
Lemma 2. If three variables V1. V2, V3 can be expressed
V1 yie V2 = Y2c e2, V3 Y3e C3.
(13)
where e, (21, are mutually independent and y1Y2y3 O, then R(V,, V2(V3) 1 V3.
Proof.
R(V, V2[V3) (yie+ e1 e3) Cov(yze 02. y30 +3)
Y1
(y20+ =e1
e2 11 V3.
(14)
7/2
Lemma 3. Given three variables V1, V2. V3 where Cov Vo)Coo((2,, V2) # 0, if3V V s.l. only one of m and V is non-zero and V2 is non-zero, then R RV1, V2(V3) y V/3
V is non-zero, R(V, V2(V3) Proof. Since CVv V3) V3) # 0 and only of m and m # O, R(1, V2(V3) и. V3 based on D-S Theorem.
contains EV. Because m V V3
C.2 PROOF THEORETICAL RESULTS IN SEC.
Definition 1. (homologous surrogate) 0 O is called homologous surrogate of L L, denoted by O E HSu( L), if Ch(L), Ch(O) = 0, An, = An(L) u (L) and Ano(O) n Deo(L) = 0.
Assumption 1. Vı. L,, HSu(!.) 0 and [Ch(l.) 2.
Remark. We can easily derive from Asmp. 1 that VL E L, [Deo(L) 2.
Condition (1) For each V E V\ K), De(V) n (JU u K) 0. (2) For each L J and e K where Ch(O) # 0, m 6 m 0.
Remark. Let K₁ (0 e K)Ch(O) * 0) and K₂ (0 e K)Ch(O) 0}. Based on Cond. each O, E O,K and corresponding Ô (which, as mentioned in the main text, is linear combination of O; and variables in where the coefficient of O; is always while that of each variable in K is not fixed) can be expressed as
0,
Σ LEJ
mo
EL, +
Σ
mo
mi
+
Σ
mo co
Σ OKKO:K
Oc mo
co.
(15)
On EKi
6,
Σ
m EL, + Σ
1y
Ai
Σ
m
Oh EO
(16)
LyEL|J
On
Lemma 4. 1/3V, E K) and 0,) O,K
s.t.
Vi Vi # 0, then Cov(O, ,,) * 0. m
Proof. Based Eqs. (15) and (16),
Cov(O,,0))
Σ
mo Var(ev).
(17)
VEVi(uu)
According to the faithfulness assumption, Cov(O, θ,) # 0.
Theorem 1, Suppose 0; E OO,K, then An(O,) S (J U K) and only if Y0, e O,(K U (0:)),
R(O,, 0,0,) ι1 Ó,
Proof sketch. If An(O;) S KJ, we can prove independence for O₃ & De(O;) easily (in this case, R(O,. 0,(Ø,) O, θ,) and prove independence for O, E De(O;) based on Lem. 2 (EO, serves as in Eq. (13)). Otherwise, there exists an 0, E O\(K U (0,)) s.t. Cov(o,, # 0 and 0. dependence can be proven by Lem. 3.
O: ",
17

---

Published as a conference paper at ICLR 2025
Li
Li
O (a) Case
Oi
0
Oj
0
(b) Case 2(a)
(c) Case 2(b)
Figure 6: Illustration of "If" part in proof of Thm. A dotted arrow from V1 122 means that
1/2 De(Vi).
Proof. "Only if" Based on Eqs. (15) and (16),
Σ
Σ
L
Σ O2, EKi
Oui co.,
Σ
Oi
0
o, +
mo
EL, +
mo:
+
mo; cO
(18)
LJJ
1yElMM
O,E0KK
Σ
m Or EI4 + Σ
Ohi E0k
0,
mo
+ 60p
(19)
TTEl
OK EKI
6,
C0k, +
(20)
O2 Ka
m 0, 0. then Cov 0,) = 0, R(O, 0,10,) = , Ö, Otherwise, based on Lem. 2, there is also ((0,,0100) O, where co, serves as in Eq. (13).
O.
"If": We prove this part by contradiction. Suppose An(O,) & (JUK). There are two possible cases as follows.
1. Suppose Ano(Oi) & K. let Oj E {0(K) n Ano(O;). An illustrative example shown OJ Oj # O, Cov(O,, θ,) 0 based on Lem. 4. Also, trivial that as Fig. 6(a). As mo mo
Cov(O; θi) # O. Since m mo " o, Lem.
O, o, O, # 0 and mo; = 0, we can derive R(O,, 0,10, K Ô, based
2. Suppose Ano (O,) K, then (0,) $ J. Let L, (O, (LAJ), there two possible sub-cases as follows.
(a) Suppose De, 0, let O, Deoo())10,). An illustrative example is shown as La o # O, Cov(O,, Ō,) # 0 based on Lem. 4. Also, it is trivial that Fig. 6(b). As mo,
0: o: Cov(O;, Ō,) # O. Since mo m. o, based on Lem. 3.
O: # 0 and mo, 0, we can derive R(O,, 0;(0;) и Ö
(b) Suppose (O; 0. Oj HSu(L,;, it is trivial that O, & De(O,) (O,). An illustrative example is shown as Fig. 6(c). As m mo # O, Cov(O,, θ,) # 0 based on O, O, O. 0 and m o, Lem. 4. Also, it is trivial that Cov(O,, Ō,) # O. Since m m O,
0, we can
derive R(O,. O,) N Ô, based on Lem. 3.
This finishes the proof.
Cov(O,,0,)
Corollary 1. Suppose O, satisfies Thm. 1, then YO, E (K(KU(())))) mo Cov(O),o,)
18

---

Published as a conference paper at ICLR 2025
Proof. Based on Eqs. (15) and (16),
Ō =
Σ
E0
(21)
O cK2
0 Σ
m
0j
1a
EL + Σ
mo,er
L EL + Σ
Oh eoM moj
+
Σ
mo,
Oi c0
(22)
E
LiLLA
O2, EKi
OcEORK
0, = Σ
m O,
1a
EL4 + Σ
O
On EOKs
E02
(23)
L
Oh EK
Therefore,
0: Var(co,) 0: m,
Cov(O,,0))
o, Var(eo,)
(24)
Cov(O;, Oi)
Corollary 2. Suppose O; satisfies Thm. 1, if we update K to K U (0;) and Ö to Ō, -mo o; for each O, E K, Cond. is still valid.
Proof. Based Thm. it is trivial that Cond. 1(1) is valid.
Based on Eq. (16), before update
Ō, Σ
Aik
E0,-
(25)
O2cK:
Ô, Σ
mo
La EL,
Σ
djzEO +
Σ
Ot E0p mo
(26)
LELUJ
Ocek;
then
- 0. 0 = Σ
mo L EL, + Σ XyREO++ +
Σ
Ot 6O m
(27)
4ELW
OceK:
(,EO((KU(O,))
where
2'xx jík mo Lix so Cond. 1(2) is also valid.
Lemma 5. 1f O,K, An(O) JUK, then YO E An,
Proof. We prove it by contradiction. Suppose 30, O s.t. (0,) s J. then since An(O) g
JUK, (O) g K. Let (no( K s.t. Ano(O,) n (Ano ()) = 0, so An,)))) S
In addition, Ant (0,) C (O,) J. An(O,) C J K. which leads to contradiction.
Theorem 2. Suppose VO E O,K, An(O) & JUL K. Given O; E O,K, then Ch(O;) = 0.
(ao K 0, (O,)
I, and An(PaL(O))M) S J if and only viO,. O2} S O,(K u (O:)) where Cov(O, 0, Cov((, 02) # O, R(O, 1,, O,
Proof sketch. If O, satisfies the graphical condition, we can prove independence based on Lem.
(let ( J = (L), EL serves as e in Eq. (13)). Otherwise, there exists V E V) U K) and Ox) S OK (O,)) s.t. Cov(O, .,) Cov(O, Ox) # m 0, m), * O. and m 0, so dependence can be proven by Lem. 3.
Proof. "Only if": Let Par (O:)J {41), note that 0z) n De(O,) 0, based on Eqs. (15)
and (16),
Õ, m
1s EL,
Σ
Agi,o
+ EO.
(28)
Oi EK:
0
Σ LyEd
mo,
Li
EL,
Σ
m
Ia ELK
O EOn mo
Σ
m
On cOm
(29)
LELLJ
OnjEKi
02 Σ
O
LJ ELy
Σ
mor
Is EL ELK
Ohi EO m
Σ
m
On EOm
(30)
LyE
LELLJ
O4 EKi
(.UOO.
19

---

Published as a conference paper at ICLR 2025
Li
Ok
O
-
0,
Ok
O
>
0;
(a) Case 1
(b) Case 2
Li
Lj
Lj
Ok
0
Ok
O
O
(c) Case 3
(d) Case 4
Figure 7: Illustration of "If" part in proof of Thm. 2. A dotted arrow from V1 to 1/2 means that 1/2 De(V)).
Ia 1o Since Cov(O, O Cov( 0n) = 2m") mo (Var(er,))) * O, there is mo m # 0. Based
on Lem. 2, R(O 0x(O;) ι Õ, where e1, serves as in Eq. (13).
"If": We prove this part by contradiction.
1. Suppose Ch(O,) # 0, let O, E Ch(OO). Based on Lem. 5, An)(O) g J and let L, Ang. (J Besides, let O₂ E HS) it trivial that O₂ (O and O; An(O)). An I4 illustrative example is shown as Fig. 7(a). As m m0 o # O, Cov(O,, Cov( O,) # based on Lem. 4. Since m Ot Lem.
o, mo # 0 and mo = 0, we can derive R(O).0x10, Ô, based
2. Suppose Ch(O,) = 0 and Pao # 0, 1et (a,) Based on Lem. 5, (O,) g J and let L; E (O))J. Besides, let O E HSu(L,), it is trivial that Ox & (0;, 0j
and O2 & An(O An illustrative example shown Fig. 7(b). As m I4 0j Oz O,
Cov(O; O,, (Ox, Ō₁) O based on Lem. 4. Since o, mo, # 0 and mox derive R(O,,0,10, I Ō; based on Lem. 3. and (Par(())) (O,)J) 2 let (4, L,) S [O Without loss of generality, let Lj & An(L)) Let O, E MOO; and O₂ HSu(L,). It trivial that
O, O,
0₁
0, we can
3. Suppose Ch(O,) {o)
1 J,
Ok $ (0;,0,) and L, & An(O An illustrative example is shown as Fig. 7(c). As m 0, mo * and m m Cov(O), Co) Ō;) based on Lem. 4. Since m L L, mo. 0, we can derive Ox(0, x Ö; based on Lem. 3.
# 0 and o, mo
L,
4. Suppose Ch(O,) = Pao = 0. (Pa)()) = 1, and ( g J. Let (O)) (L,, L, E An O, (o and O₂ HSu(L,).
trivial
that O₂ $ {0;, 0,} and L; & An(OO). An illustrative example is shown as Fig. 7(d). As L. Lo
m 14 m 0, m # 0, O,,(O), θ,) # 0 based on Lem. 4. Since m L m, m oo = O, we can derive R(O,, Ox(0,) x Ô, based on Lem. 3.
# 0 and
0
This finishes the proof.
Proposition 1. Suppose O, and O, satisfy Thm. then (O,( Pay(O,) if and only if
Cov(ū;, 0,) # 0.
20

---

Published as a conference paper at ICLR 2025
Proof. Let Pal (O (L1) and Par (O,))[] {Lj). Based on Eqs. (15) and (16),
0; 0 EL, + Σ
A1 + E0
(31)
O EK:
Σ
14
EL, Σ 01 EK!
On E0
0
oj
ELK + m 0,
mo
+ E0,
(32)
Obviously, L, Lj if and only if (C, 07) m m 1, Cov(EL, EL,) that is. L Lj.
Proposition 2. Suppose 0, satisfies Thm. 2, then O, e (Su(Par(O)))J)) if and only if VO, satisfy- ing Thm. 2 and (O,) )) = (a) I| (0,; (o,; llo z |IM (0, llo
Proof. Let (Oi)( = (14))- "Only if". For each 0 satisfying Oj De(L:), there is An(O,) nJ 2 An(L,) n.J. Since O₁ HSu(L,, An(L,) O An(O,) Therefore, (o) Ilo < |[M (0,) llo.
"If". We prove this part by contradiction. Suppose 0; $ HSu L,). Let O e HSu(L;), then we have
[[M] (o.) llo [M o, lloo (A)(L)) n JJ. Since 0, De(L,), |M [o, llo |An(L,) 0 JJ. Therefore,
[|M] (0,) llo ||M (0,) llo. that is, An(O,) nJ An(O,) n An(Li), note that O, satisfies Thm. 2,
so 0; HSu(L,), this leads to contradiction.
Definition 3. (Cumulant) Given random variables VI...., Vn, the k-th order cumulant is defined as a tensor of size X ... x (k times), whole element at position (f....., ik)
Cum(Vi Vid)= (-1) ([x) 1)!
Vj
(33)
BEx
[EB
where is enumerated over all partitions of (i1.....
Corollary 3. Suppose O, satisfies Thm. and O E HSu(L,,, then Y0, E O)(KU (01)),
L 2
m
Cum(O,,0,00.00)
4 4 o m Cov(
(34)
14
Cum 0,)
m0,
Proof. Note that Oj De(O;), based on Eqs. (15) and (16),
o, = m m EL, +
Σ
An. +
(35)
0 K
0 = Σ
mo EL, + Σ
m ELE + Σ
Σ mo (mEOO
On Eo,
+
m mo; E0m
(36)
LJ
O eKi
Clearly,
Cov(o;, 0,) m m' Var(el,) m
(37)
The second equation holds because assume the exogenous noise of each latent variable has unit variance.
Because we assume each exogenous noise has zero mean, B[O,] E[O,1 = 0. There is
-mmo::;::....)-=E00000---BBBCBO- -
(38)
21

---

Published as a conference paper at ICLR 2025
Let é; = = m EL and ej O, m4 mo, eL. It follows that ee, , mutually independent. Therefore,
Cum(O; 0,000,000 =B[(m) cL, + ēi)² (m EL (3 + Emi) eL, + eeel eL =
=|0;0,]
l0,,0
BIO
= )) ( Li mo, Biei,]
3m Li L Blei,
mo,
ett -3 (m)))) m (B(e),
m o, Bl [B(
Li
E[ F4 +61) (m)) ex,t
B[ cu tm) e4 [ette)]B[(nn] <4 +8,
( (Blei,) 3(B(E2,
(39)
The second equation holds because for any three independent random variables V1, V2,, V/3 with [[v]]=0
= - O.
(40)
B[V = [[]]][[]]] B[ViV=] = [[v]][[[]] = O.
(41)
(42)
The third equation holds because
BiE B[G,, [B
(43)
Similarly,
Cum Cum(O,,0,00,,00) m (m
(BlEE,, ( 3(B(e,,
(44)
Therefore,
m 44 0: L m mo,
Cum
(45)
Cum
Remark. the above proof, we implicitly assume that B[E # 3(B D) that is, the excess
kurtosis of Er, not zero. An excess kurtosis of zero indicates that a distribution has identical tail behavior and peak characteristics extreme values occurring is precisely equivalent to that a Gaussian distribution. Considering that E,, is non-Gaussian variable, this is mild technical assumption.
Gaussian distribution, which means the probability of
Corollary 4. Suppose O; satisfies Thm. 2 and O, HSu(L,), if update J to J U (L:), K to Ku (0,), and Ō to Ô, (m'²,, / m for each 0, O,K, Cond. 1 is still valid.
Proof. Based on Thm. 2, it is trivial that Cond. 1(1) is valid.
Note that 0j De(O;), based Eq. (16), before removal
Ô m EL,
Li
Σ
MREE, +
(46)
Ocek:
Ô, Σ
m E2, Σ ARREO+ +
Li
Σ
m Ot cO
(47)
Oxek:
O,60)(KU(0,1)
then
Li
m Li
Σ (ELL(UU(L))
L mo,
EL,
Σ
X12500* +
Ot EO: m m
(48)
mo
ObeK:u(O,)
0,E0((K(1O.)
1 mo
44
mo
where
21, j,k
dit if O2 K2 and d' = =
if O = Oi, so Cond. 1(2) is also valid.
m
mo
22

---

Published as a conference paper at ICLR 2025
Theorem 3. Suppose the observed variables generated by LiNGAM with latent variables satisfying Asmp. 1, in the limit of infinite data, Alg. identifies latent variables and ancestral rela- tionships correctly.
Proof. Based on Thm. 1, Cors. and 2, Alg. 1 correctly estimates M Based on Thm. 2, Props. and Cors. 3 and 4, Alg. correctly identifies latent variables by locating their respective ho- mologous surrogates and estimates M Furthermore, given any two latent variable Li, Ljj. Alg. correctly determines whether L, is an ancestor of L, by checking whether L, is an ancestor of L homologous surrogates.
C.3 PROOF OF THEORETICAL RESULTS IN SEC. 4.
Definition 4. (Generalized homologous surrogate) O E O is called a generalized homologous surrogate of L L, denoted by GHSu(L), if O Ch(L) and (o) S An(L) (L).
Assumption 2. Asmp. holds and V[L, Lj} S L where L, An(L,),3(0) O₂2 S GHSu(L,) s.t J, Ch(L,) and J} Ch(L,).
As mentioned in the main text, we can remove causal relations between observed variables given Ao Specifically, for each O, O, let
a0 01
0 =0=1--
(49)
OjEPa(O,)
We denote by G the causal graph among LUO" where O [0,). Also, we use Pa" (V) to denote V's parents in G
Lemma 6. Given E L, and O E O, O e GHSu(L)) if and only if An" (0") = (L) (L).
Proof. This can be readily derived from the definition of generalized homologous surrogates.
Lemma 1, VL, E and O; E O. O; E GHSu(L,) if and only if m m # 0 and YO, E O where L mo # 0, [IML
L. to llM, llo. Besides, there is a =
O, there is An"(O') 2 An"(Li U (Li). Based on Proof. "Only if" For each 0j where m mo
Lem. 6, (O,) An' (L,) U (L4), so 1 s [IM] (o;,1lo.
"If". We prove this part by contradiction. Suppose O, & GHSu(L,). Let O2 e GHSu(L.), then Ia (itto s 1o) llo = [An' U (L1) based on Lem. 6. Since mo; # O, O De'(L), (L,) U (L))l. Therefore, |M llo IM llo. that is, An"
that is, [|ML top An" (L)) U (44), so O₂ GHSu(L)) based Lem. 6, this leads to contradiction.
Finally, based on Lem. 6, it is trivial that if O, GHSu(L,,, a' m because there is only one directed path from L, to O in G", which is exactly L, - 0
Theorem 4. Suppose (L, Ly) c I, Ly (L)) YO, E GHSu(L,)). let m
H L
Σ Ls to Idon and m N jaon
b. nti 00;
(50)
1n (EDe(()))An(t.)))
Li (a) There exists {0 (²) c GHSu(L;) s.t. noj jdoo Is La Lj (b) d =M0; m "
Li Ly
23

---

Published as a conference paper at ICLR 2025
1 Proof sketch. We can derive that Hoj = ao, + +m 14 ao, 11 on the faithfulness assumption, Ho; 1don Ho; ldon if and only if don do 0. that is,
(b) holds naturally. For (a), based
L L
La
L
O & Ch(L,) and O & Ch(L,). In this case, Ho; jaon mi trivially.
4
Proof. For any L, and 0j O", there is
44 + 1 of =o DD L. (L))PP((O))
Σ
1a 1t Ia Oj
(51)
Given O₂ GHSu(L,), based Lem. 6, Pa'(O)) S An"(O') An"(L) (De" (L))
Pa" Pa' ()))) s (L,) n An' = De(Li) O An(Lj). Because m m =0 if L. De (L,)
Pa' (03), we can rewrite Eq. (51) as
I = dos o
1a +
Σ
la + +m Li by m 0o
I, "os
(52)
LA (eDe(()))A((L))
Therefore,
H0 oo
14
Σ
m Lx 0,
L 1a Ia L2 + m aos
(53)
L.E))()))AnLL))
Let {0), 0n. S GHSu(Lj). On the one hand, if O₁, & Ch(Li) and O₁ & Ch(Li), then d0j ooj 00 so Hoj /ao), No 1000 = =m On the other hand, if O E Ch(Li) or Oj, E Ch(Li), 1s based on the faithfulness assumption, Hoj jdoj, # Ia #Mo; 1a0/. Therefore, (a) holds.
la
L,
Besides, based on Eq. (53), it is trivial that (b) holds.
Theorem 5. Suppose the observed variables are generated by a LiNGAM with latent variables satisfying Asmp. 2, the limit of infinite data, Algs. 1 and 2 together identifies latent variables and parental relationships correctly.
Proof. Based on Thm. 3, Alg. I correctly identifies latent variables and estimates M and MO Based on Thm. 4, Alg. 2 correctly estimates MI: Therefore, M is estimated correctly, from which can be derived based on Eq. (5).
D EXPERIMENT ON REAL- WORLD DATA
The Holzinger and Swineford 1939 dataset consists of mental ability scores of seventh- and eighth- grade children from two different schools (Pasteur and Grant White). There are 9 variables, which can be categorized into three dimensions: Visual (0,, O2, 03). Textual (O4. Os, O6), and Speeded (O,, O,, Ox). The result returned by our algorithm is shown as Fig. 8. Our algorithm correctly identifies the textual factor while merges the visual factor and the speed factor into single factor. This can be attributed to the fact that both the visual factor and speed factor depends on innate abilitics, while the textual factor highly depends on learning experience.
L
0.
0.
0
0.
0
0.
0
Ox
0+
Figure 8: The output of our algorithm on the Holzinger and Swineford dataset.
24


Reviews:
[{"review_id": "ffdgvGZnK9", "reviewer": "Reviewer_uc12", "summary": "This paper introduces the concept of homologous surrogates to address the challenges associated with causal discovery involving latent variables. It formulates two assumptions regarding homologous surrogates and develops theoretical results based on each assumption. Under the weaker assumption, the authors demonstrate the feasibility of partially recovering the causal graph by identifying the ancestors of each variable. The stronger assumption facilitates the exact identification of each variable's parents, enabling full recovery of the causal graph. Additionally, the paper proposes an algorithm that effectively leverages the properties of homologous surrogates for causal graph recovery and validates its effectiveness through experimental results.", "questions": "See the weaknesses above.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. This paper deals with a causal structure learning problem involving latent variables, which is significant for the field of causal discovery.\n\n2. The authors proposes a method for identify the causal structure via the homologous surrogates under mild assumptions.", "weaknesses": "1. The representation needs refinement, as the content of the paper lacks logical flow and coherence, which makes it difficult for readers to follow the main points.\n\n2. The technical contributions appear to be somewhat constrained. This paper draws upon two established methodologies, pseudo-residuals and causal effect estimation via cumulants. It introduces the concept of homologous children, which is fundamentally equivalent to the notion of pure children.\n\n3. The authors mentioned that their work expands the applicability of causal discovery methods, and that homologous surrogates aid in causal discovery with latent variables. However, in the experimental results involving real-world data, their proposed method performs poorly. The authors believe this is due to a limited sample size. So, are there more suitable real-world datasets available to validate the method proposed in this paper?", "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": "i8lTkIhJOY", "reviewer": "Reviewer_AU92", "summary": "This paper proposes a method for causal discovery with latent variables while relaxing the common assumption that requires the existence of pure children. Instead, the method relies on the condition of homologous surrogates, which can have multiple parents. The proposed algorithms are validated on synthetic data.", "questions": "Please refer to the comments above. Some statements in the current manuscript are not precise, and the overlooking of some closely related work in the introduction may introduce confusion about the unique contributions of this work.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The theoretical results are clearly stated with all definitions introduced clearly.\n\n2. The figures are helpful in understanding the method.\n\n3. Experiments in various settings validate the effectiveness of the algorithm.\n\n4. The limitations have been discussed explicitly.", "weaknesses": "1. Since \"homologous surrogate\" is a newly introduced term, it would be helpful to provide a concrete example immediately when it is first mentioned in the manuscript. This would aid readers in understanding the concept more intuitively.\n\n2. Some of the most closely related works have not been mentioned in the introduction. For example, [Dong et al., 2024] consider almost the same problem with a very similar motivation, i.e., relaxing the structural assumptions among latent and observed variables. That work also allows the existence of children for observed variables. Currently, the discussion was only in the remark and related work at the end of the manuscript, but not in the introduction.\n\n3. In line 82, it states that the considered setting is new in causal discovery. However, it might not be accurate since causally-related latent variables have been considered before, even in the presence of observed variables' children. I understand that omitting works such as [Dong et al. 2024] in the introduction would make the story clearer, but it might introduce confusion for readers less familiar with the field.\n\n4. In line 45, it seems to state that [Jin et al. 2024] make the pure children assumption, which might also not be true.", "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": "GDdO0lsee7", "reviewer": "Reviewer_BthH", "summary": "This paper proposes a causal discovery method with latent variables. Instead of assuming that each latent variable has multiple pure children, they assume that each latent variable has at least one homologous surrogate. They define homologous surrogates and develop identifiability analysis under the homologous-surrogate assumptions. Experiments show the efficacy of their proposed algorithm.", "questions": "1.\tIn Equation (7), how are the parents $O_j$ of $O_i$ identified? $O_j$ here might be observed ancestors of $O_i$? It is not clear which step aims to find the parents. Since $M_O^O$ is derived from Algorithm 1, which could contain some spurious edges.\n\n2.\tAs illustrated by the authors, their algorithms suffer from cases with small sample sizes but could achieve ideal performances when assumptions are met and the sample sizes are large enough. For example, in ideal Case 2 of the experiments, how many samples are needed to achieve the ideal results?\n\n3.\tIf the number of latent variables is not estimated correctly, what would happen? Did it greatly impact the final results?\n\n4)\tThe following paper [1] tackles the same problem and also allows non-pure children. Hence I suggest discussing the differences and connections with it.\n\n[1] Xie F, Huang B, Chen Z, et al. Generalized independent noise condition for estimating causal structure with latent variables[J]. Journal of Machine Learning Research, 2024, 25: 1-61.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1)\tThe authors tackle a significant but challenging causal discovery problem, that is, identifying latent variables and recovering causal relations between all latent and observed variables.\n\n2)\tThey introduce two assumptions about the defined homologous surrogates, based on which they develop partial and full identifiability theories. They also propose an algorithm to uncover the causal relationships between latent and observed variables.", "weaknesses": "1. The algorithm’s complexity is high, i.e., $O(|O|^4)$ and $O(|O|^2 |L|^2)$ for Algorithms 1 and 2, respectively, which could limit its real-world application. It might be better to give empirical complexity analysis in the experiments, compared with other baselines.\n\n2. Regarding the simulated causal graphs in Figure 5 for the experiments, I think the networks are all small. It could help to investigate the performances when there are more latent variables and when the causal relations between latent variables are sparse.\n\n3. It might be better to give simple descriptions and basic conclusions of the experiment on the real-world dataset Holzinger and Swineford, in the main paper. BTW, from Appendix C, the performances on such a real-world dataset look not satisfactory.\n\n4. It is good to give examples for the definitions. But I think giving examples for the theorems also matters since it is hard to catch the main idea or intuitions for the basic theorems.", "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": "E3a8ovMW9u", "reviewer": "Reviewer_B7bR", "summary": "The paper proposes the use of homologous surrogates to identify latent variables and recover the causal graph. The main contribution of this work is that, unlike pure child variables, homologous surrogates allow for the presence of other parents. Based on this concept, the paper develops corresponding theoretical support and applies it to an algorithm.", "questions": "1. In Algorithm 1, the font of \"Thm.1\" in line 3 is different from the \"Thm.1\" in other parts of the pseudocode, which needs attention.\n2. For Algorithm 1 and Algorithm 2, the authors use Figure 2 and Figure 3 for explanation, but the tracking example is placed in the figure captions, and the corresponding steps are not explained in detail. It is recommended to add more detailed explanations in the main text to guide readers in understanding the example presented in the figures.\n3. Please add your source code link to the paper.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The innovation of this paper is quite novel, as it uses homologous surrogates to identify latent variables and then recover the causal graph. The supporting theories are also rich, and the corresponding proofs are complete. The theories and propositions applied in the algorithm section are clearly explained, along with examples. These theories are crucial for the implementation of the algorithm. The method proposed in this paper offers a new perspective for discovering latent variables.", "weaknesses": "In the third chapter, PARTIAL RECOVERY, the explanation of the algorithm and theoretical part is not very clear in terms of formatting. The formulas and theoretical support needed for the preceding theories and hypotheses are instead explained afterward, which increases the difficulty of reading and affects the logical flow. For example, in \"Identifying Observed Root Variables.\", in the \"Intuition\" section, Theorems 1 and 2 are mentioned, so they should be placed before the \"Intuition\" section. The theories used in the proof should appear before the proof itself, rather than afterwards.", "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)