Structural Estimation of Partially Observed Linear Non-Gaussian Acyclic Model: A Practical Approach with Identifiability
Authors: Songyao Jin
Feng Xie
Guangyi Chen
Biwei Huang
Zhengming Chen
Xinshuai Dong
Kun Zhang
Venue: ICLR 2024 poster (2024)
Keywords: causal discovery
latent variable model
structure learning
Primary area: causal reasoning
TL;DR: Identification of partially observed linear non-Gaussian acyclic model where latent variables may be anywhere in the causal structure.

Abstract: Conventional causal discovery approaches, which seek to uncover causal relationships among measured variables, are typically fragile to the presence of latent variables. While various methods have been developed to address this confounding issue, they often rely on strong assumptions about the underlying causal structure. In this paper, we consider a general scenario where measured and latent variables collectively form a partially observed causally sufficient linear system and latent variables may be anywhere in the causal structure. We theoretically show that with the aid of high-order statistics, the causal graph is (almost) fully identifiable if, roughly speaking, each latent set has a sufficient number of pure children, which can be either latent or measured. Naturally, LiNGAM, a model without latent variables, is encompassed as a special case. Based on the identification theorem, we develop a principled algorithm to identify the causal graph by testing for statistical independence involving only measured variables in specific manners. Experimental results show that our method effectively recovers the causal structure, even when latent variables are influenced by measured variables.

Published as a conference paper at ICLR 2024
STRUCTURAL ESTIMATION OF PARTIALLY OBSERVED LINEAR NON-GAUSSIAN ACYCLIC MODEL: A PRAC- TICAL A APPROACH WITH IDENTIHIBBILITY
Songyao Jin", Feng Xie Guangyi Chen"*, Biwei Huang", Zhengming Chen'*, Xinshuai Dong', Kun Zhangi*
Mohamed bin Zayed University of Artificial Intelligence, Abu Dhabi, UAE BBeijin Technology and Business University, Beijing, China
*University of California San Diego, La Jolla CA, USA
!Guangdong University of Technology, Guangzhou, China
CCanegie Mellon University, Pittsburgh PA, USA
ABSTRACT
Conventional causal discovery approaches, which seek uncover causal relation- ships among measured variables, are typically sensitive to the presence of latent variables. While various methods have been developed address this confound- ing issue, they often rely on strong assumptions about the underlying causal struc- ture. In this paper, we consider general scenario where measured and latent variables collectively form a partially observed causally sufficient linear system and latent variables may be anywhere the causal structure. We theoretically show that with the aid of high-order statistics, the causal graph is (almost) fully identifiable if, roughly speaking, each latent set has a sufficient number of pure children, which can be either latent measured. Naturally, LiNGAM, model without latent variables, is encompassed as a special case. Based on the identi- fication theorem, we develop principled algorithm to identify the causal graph by testing for statistical independence involving only measured variables in spe- cific manners. Experimental results show that method effectively recovers the causal structure, even when latent variables are influenced by measured variables.
INTRODUCTION
Inferring causal relationships from observed data is popular field within statistics and artificial intelligence. Conventional causal discovery methods, such as the PC algorithm (Spirtes & Glymour [991]. Greedy Equivalence Search (Chickering, 2002). LiNGAM (Shimizu al.) 2006),, are de- signed to identify causal structures among measured (observed) variables, assuming that no latent variables exist in the causal graph. However, in practice, usually can measure all task-related variables, leading to a violation of the no-latent-variable assumption (Spirtes & Zhang 2016).
To estimate causal relationships among measured variables involving latent variables, line of approaches assumes independent latent confounders and utilizes conditional independence con- straints (Spirtes al. 1995) Colombo
al., 2012 Claassen al., 2013), functional causal models and non-Gaussianity (Hoyer et al. 2008 CCen & Chan 2013 TTshiro et al. 2014 Maeda & Shimizu, 2020p. Going beyond this assumption, some approaches allow for causally related la- tent confounders. These include methods based on measurement models and hierarchical models, distinguished by whether the latent variable's children are measured or not. particular, measure- ment mrodel-based methods typically rely on the Tetrad condition (Silva et al., 2006)] Kummerfeld & Ramsey] 2016), Gou-Gaussyy (Shimizu et al. 2009 Cai et al. 2019 Xie et al. 2020), mixture oracles (Kivva et al. (021). On the other hand, hierarchical model-based methods have evolved from tree-like structures (Pearl, 1988; Zhang 2004| Choi et al. [001]] Drton et al. (007)) to more general hierarchical structures (Xie al. 2022 Huang | [2222] Kong et al. 2023). Of particular relevance to us are methods based on the Generalized Independent Noise (GIN) condition (Xie et al.)
2020 2022), which leverage higher-order statisties (beyond the second-order moments in statistics,

---

Published as a conference paper at ICLR 2024
X1
A variable
V: A set of variables
LE: An atomic unit
U: A set of atomic units
Xa X2 X6
Xs
X X11
X12 X13 XIa X15
| Number of variables
PCh: Pure children
X1c - X17 X1s X19
X22
MS: Measured surrogates
Figure/ 1: An example latent causal graph G that our algorithm can handle. L; Table I: Graph notations, are latent variables, and X; are measured variables.
More Details in Appdix. I.
e.g., skewness, kurtosis, etc. of the data) to improve identifiability in the presence of latent con- founders. However, all those methods typically rest on the measarement axsumption-thal there no measured variables acting as parents of any latent variables in the underlying causal graph.
The aforementioned methods are tailored to specific configurations among measured or latent vari- ables, which limits their practical applicability. In fields like human health, latent genetic factors, for instance, might be influenced by observed environmental factors, subsequently affecting observed host phenotypes. While AAdms et al. (2021) established necessary and sufficient conditions for structure identifiability based on overcomplete ICA, does not have a practical estimation approach and requires knowing the number of latent variables at the beginning. Recently, (Squires et al. (2022) presented method that allows latent variables to be influenced by measured variables, but it still relies on strong assumptions, such as the absence of edges between pairs of observed or latent nodes.
In this paper, we target an inclusive scenario involving latent variables, without imposing constraints on their presence and positions. Meanwhile, we seek to strike delicate balance between theoretical identifiability and practical feasibility. To identify the causal structure within this general scenario, we leverage the linear causal model and non-Gaussianity giving rise to the proposed Partially Ob- served Linear Non-Gaussian Acyelic Model (PO-LiNGAM), We demonstrate that, even without prior knowledge of the latent variables, the causal graph is virtually identifiable when each variable conforms to the PO-LiNGAM and each latent set has a sufficient number of pure children. Building upon the identification theorem, we introduce feasible search algorithm that utilizes the Gener- alized Independent Noise (GIN) condition in specific manners. The proposed algorithm comprises three iteratively executed phases that sequentially identify latent variables and infer causal relation- ships among (both latent and measured) variables, progressing from leaf to root variables. The algorithm halts its inference of the higher-level causal structure when the latent set lacks a sufficient number of pure children. This helps to maintain precision and applicability in real-world situations. Furthermore, in cases where there are no latent confounders, our algorithm's 's results will reduce to those obtained using LiNGAM-based methods (Shimizu et al., 2006; 2011). Additionally, our al- gorithm possesses the capability to handle overlapping variables between discovered latent sets, an aspect often overlooked by other methods. Our contributions summarised as:
a.) We consider a broad spectrum of causal structures, regardless of the presence and positions of latent variables, and establish their theoretical identifiability under milder graphical conditions. Figure [ depicts an illustrated latent graph with several notable characteristics, For instance, the latent variable set {L2 La} serves not only as hidden confounder for measured variables but also for latent variables, forming a latent hicrarchical structure. Additionally, {L3, L has its own unique set of pure children, distinct from those of (Lz, Ls). though both are influenced by the measured variable {X, }. Latent triangles, such as {X, L,,LI,X,, ), are accommodated as well.
b.) We propose an efficient algorithm to estimate the causal structure through precise application of GIN tests, without prior knowledge of latent variables. Our algorithm infers the causal graph by precisely identifying the pure and impure children.
2 PARTIALLY OBSERVED LINEAR NON-GAUSSIAN ACYCLIC MODEL
2.1 MODEL DEFINITION
Precisely, we focus partially observed linear non-Gaussian acyclic model where X (X,....,X,, denotes the set of measured variables, L = (L,,...,L, denotes the set of la- tent variables, and V X U L denotes the total set of variables. Each variable V, V is generated
2

---

Published as a conference paper at ICLR 2024
within directed acyclic graph (DAG) by the following linear structural equation model:
V₁ Σ big V EV,
(1)
V,EPa(V.)
where Vz and V can be either measured or latent variables, ;) is the set of parent variables of V.. by represents the causal strength from V, to V,, and EV, represents the noise term of V,. The noise terms are assumed to be continuous random variables with non-Gaussian distribution, and they independent of each other. Additionally, without loss of generality, we assume that all variables have zero mean (Otherwise, they can be centered).
Definition 1 (Partially Observed Linear Non-Gaussian Acyelic Model (PO-LINGAMI). A linear graphical model, with its directed acyclic graph G, is called partially observed linear non- Gaussian acyclic model, iff:
Each variable in variable set V is generated by the structural equation model 7 The distribution over V is Markov and faithful to the DAG g.
Unlike the LiNGAM in Shimizu et al. (2006), we allow for the presence of latent variables. As shown in Definition T we disregard the specific positions of the measured and latent variables. This means that both measured and latent variables, individually or jointly, can act parents to other measured or latent variables. It distinguishes our work from previous studies on linear latent models
(Silva et al., 2006 Hoyer al.) 2008 Cai et al., 2019 Xie et al. 2020: 2022: Sqqiies et al.) 2022 Huang et al., 2022). In this paper, our goal is to establish the identifiability of the PO-LiNGAM causal structure and show how can be discovered solely from the set of measured variable X.
2.2 GRAPHICAL CONDITION FOR IDENTIFIABILIT FORMULATION
We now formulate the graphical condition that will be utilized to establish the structural identifia- bility in Section 3.4 Below, we first give some definitions corresponding graphical structures.
Definition 2 (Pure Child), Let V be the set of all variables that have the common parent variable ser P and V P O. For any V V. V a pure child of P iff V is d-separated V given the parents P. Similarly, for any subset V of V, V is a pure child of P iff V is d-separated from V.V given the parents P.
Example 1. In Figure 7 (Xs), (X6). (X7), [Xs} are pure children of (I1, X2), respectively or combination. (I1, X2) in combination is a pure child of (X1).
A complex causal graph can be identified by decomposing it into simpler, independent components. This simplifies the analysis by focusing on individual components and their relationships. We now give the definition of the atomic unit which represents the basic building block of causal structures.
Definition 3 (Atomic Unit). An atomic unit is either a single measured variable, or a set of variables V with size || = t 2 that the following conditions hold:
contains at least one latent variable.
V has at least t t+1 1 atomic units its pure children, in which in total at least t child variables are contained in the atomic units other than t atomic units, and each of all these pure atomic unit childrer covers all atomic units that share common variables with it. Additionally, when t 2 2, V has another atomic unit that either neighbors it or overlaps with it.
V is the minimal set that cannot be decomposed into several smaller atomic units.
Example 2. In Figure [ each measured variable is atomic unit. LL LT} is atomic unit with size t = 2, where in addition to the 2 (note that 2 2 t) pure atomic unit children {X²1) and {X22). the remaining pure atomic unit children {X2s} and {X2a} in total contain 2 child variables. Furthermore, {L2, La} is an atomic unit with size = 2, where in addition to the 2 pure atomic unit children {X10} and (X1)), }, the remaining pure atomic unit child { (Le, Ia} contain
child variables. However, ( [L,, X2) is not strictly an atomic unit because it can be decomposed into two smaller atomic units {L1} } and {X2).
For measured variables, it is reasonable to examine each variable individually. As for latent vari- ables, linear transitivity allows to extract their information provided they have sufficient number
It indicates that the pure children themselves are atomic units. The same goes for the following.
3

---

Published as a conference paper at ICLR 2024
of pure children. Below, for the sake of convenience, we default considering children at the atomic unit level. It means that when we refer to C as pure child of P. the premise that C and P are atomic units. Below is the graphical condition to guarantee identifiability of PO-LINGAM.
PO-LINGAM Identifiability Condition a.) Any latent variable in at least one atomic unit. b.) For any two atomic units with overlapping variables, their non-overlapping parts do not influence each other.
The first term is the basic condition for identification of latent variables (Xie et al., 2020: Huang et al. 2022). It implies that every latent variable must have measured variables as its descendants. The second term arises because the discovered atomic units may have overlapping variables. In cases where two atomic units share variables, we cannot determine whether the non-overlapping part of one unit causally affects the non-overlapping part of another unit due insufficient information. Theorem 4 will show the entire causal graph is identifiable at the atomic unit level when the above graphical (identiffabiliity) condition satisfied.
3 STRUCTURE IDENTIFICATION THROUGH A THREE-PHASE ALGORITHM
In this section, we present our algorithm for structural identification and corresponding theoretical guarantees. Our algorithm is iterative, with each iteration consisting of three phases, progressively uncovering the entire causal graph from leaf to root nodes. Let A. be the active atomic unit set consisting of atomic units under investigation, which is initially set to X and updated progressively. Phase identifies the causal relationships among atomic units in A. Phase discovers new atomic units from A. Phase III refines the discovered atomic units. After that, A is fed back to phase I, and a new iteration starts until A is not updated. Finally, we simply verify multiple root atomic units by checking the discovered second-highest causal order atomic units (see Appendix C.5
Algorithm 1:
The identification procedure of PO-LiNGAM
Input: Measured variable set
Output: Causal graph G
Initialize partial causal graph G:= 0, active atomic unit set A:= X:
while ||| > and A is updated do
(G, A.) <
A); Phase 1 (G, A, New AtomieUnttt)))) <- DiscoverNewAAtomiclme A): // Phase 2
(G,A) < RefineAtomic A, NewAtomicUniiSSel; // Phase 3
end
Check for multiple root atomic units (see Appendix C.5
return G
3.1 PHASE IDENTIFYING LEAF NODES AND THEIR PARENTS
Each iteration starts with phase I. In phase I, we deal with the identification of causal structure among atomic units A by recursively identifying the leaf nodes in the causal graph composed of atomic units in A and their latent confounders. Below, we briefly review the Generalized Independent Noise (GIN) condition (Xie et al., 2020), which the workhorse for our algorithm.
Definition 4 (GIN condition) (Xie et al., 2020). Let Z and Y be sets of variables with zero mean in a linear non-Gun Gau-siassinn acyelic causal model. We say that (Z, Y) follows GIN condition if and only if w Y is independent of Z. where w satisfies w E
0 and +
Roughly speaking, if the GIN condition satisfied, then there set of variable (which can contain variables in Y) of size |[P|| < ||| which are ascendants of Y and d-separate P from Z Z.P. See Xie et al. (2020) and Appendix for more details.
In a causal graph, for any leaf node variable, it is d-separated from the other variables given its parents. By utilizing the GIN condition and non-Gaussianity, this graphical condition can be sta- tistically linked to the data. To derive the theorem for the general case, start by considering scenario in which all variables are measured, meaning there are no latent variables in the causal ghaph-this corresponds to the case of LiNGAM (Shimizu al. 2006 2011).
4

---

Published as a conference paper at ICLR 2024
Proposition 1 (Identifying leaf variables without latent confounders). Let V be set of variables satisfying PO-LiNGAM with no latent variables, and V be a variable in V. For a set of variable P E VVV V is one of the current leaf variable nodes and P contains all parent variables of V, iff (V\V, U) follows the GIN condition and there is no P P such that V) the GIN condition.
Example 3. Consider the causal graph in Figure 7 composed of V (X9,, X16, X17, X18}. Let follows the GIN condition, which implies that X17 is the current leaf node, and X16 and X18 are its parents. Remov- ing X17 V, we can find that X16 is the current leaf node and Xg is its parent.
V == X17 and the minimal P (X11:X18) ([Xg, X16: X18), X16,
If there are no latent variables, Proposition T allone suffices to identify the entire causal graph. We achieve this by recursively identifying the leaf variables and then reconsidering the remaining vari- ables. In practice, however, it is difficult to exhaustively measure and collect all task-related vari- ables (Spirtes et al., 2000). Thanks to the transitivity of linear causal relations, although we cannot directly access to the latent variables, we can use their measured descendants to test GIN conditions.
Definition 5 (Surrogate variable & Measured Surrogate Variable set MS.,)). Let P be an atomic unit involving latent variables and atomic unit C E PCh(P). Surrogate variables of P are the variables each C or up to ||C|| surrogate variables of C. Measured Surrogate variables of P are its surrogate variables that are measured. Measured Surrogate Variable set MS, & MS, of P are two sets of measured surrogate variables, where the minimal set d-separating MS, and MS, is P, and [PMI [|MS = [[P|]-
Example 4. In Figure D for the atomic unit (T., MS, can be (X21, X22} and MS, can be X21). For the atomic unit {L2, La), MS, can be (X21, X22) and MS₁ can be {X1o.
To harmonize the view, in the following sections, for each measured variable that also serves as an atomic unit, we designate both MS. and MS, to refer to the measured variable itself. We will explain in Phase II how to discover latent atomic units and their measured descendants. Let us now show how the leaf atomic units and their parent atomic units in the causal graph can be identified by utilizing measured surrogate variable sets of each known (measured or latent) atomic unit.
Theorem 1 (Identifying leaf atomic units). Let U be set of non-overlapping atomic units satisfying PO-LiNGAM with known MSa.b for each atomic unit in U, and l be an atomic unit in U. For a set of atomic units F S U.M, U is one of the current leaf atomic unit nodes and P contains all parent atomic units of iff (US MS JP) follows the GIN condition and there is no P c such that (MS.
MS&(U U P)) follows the the GIN condition.
Example 5. Consider the causal graph in Figure 1 composed of ([X2), [Xa], [Ls}]. Suppose we know that {Lo} } is the latent confounder of (Xis) and {X19]. meaning that MSo,s can be } ) and {X19}, respectively. (!X2, X9), {X2, X193) follows the GIN condition, which implies that (Tss) is the current leaf node and {X2} is its parent that d-separates it from the other atomic units. Removing (T.5) from U. we can find that {Xg} is another leaf node and (X2) is its parent.
Theorem I extends Proposition D allowing for the atomic units involving latent variables. In The- orem [ we make the assumption that each atomic unit does not overlap with other atomic units. However, as shown in Figure D {L2, La} and {L3, L4) are two atomic units with the overlapping variable Lg. In our algorithm, during each iteration, Phase III checks for overlap among atomic units after the new atomic units are discovered in Phase II. Below, we propose the complement to Theorem T that ensures the theorem's 's correctness even in the presence of overlapping atomic units starting from the second iteration onwards.
Remark (Complement to Theorem 1). In Theorem 1, before testing GIN condition, a.) if any atomic units in U have overlapping variables with U, then we remove them from U and remove them from P if they exist in P. b.) if the atomic units in IP overlap with each other, instead of using entire set of MS, (P)) for testing, we use its maximal subset S that makes (MS,(UU S) does not follow GIN condition. Similarly, for P. instead of using entire MS;(P) for testing, we use its maximal subset S that makes (MS, (US,U (U,U), S) does not follow GIN condition.
MMS. denotes the union of MS, of each atomic unit in U.4 The same goes for the following.
5

---

Published as a conference paper at ICLR 2024
We now infer the causal structure among atomic units in A. Specifically, the atomic units in A and their latent confounders form a causal graph. For any leaf atomic unit of the graph in A, if all its parent atomic units are also in A, it and its parents can be identified by using Theorem Jand Remark [ Then, we archive it and remove it from A. The remaining atomic units in A and their latent confounders form smaller causal graph in which we can continue identifying leaf atomic units, Below, we present the main search procedure of Phase I. The algorithm details can be found in Algorithm 2 (Appendix C.I). which also includes an additional checking and refinement process (lines 8 and 14, Alg. 2 that will be explained in the next subsection.
Phase I: Identifying Leaf Nodes And Their Parents
1. Start with partial causal graph G and active atomic unit set A.
2. For each atomic unit in A, test if there is a subset of atomic units P in the A that satisfies Theorem with Remark 1.
3. If found, add direct edges from each atomic unit in P to U, and remove U from A.
4. Repeat steps 2 and 3 until no more atomic units can be removed from A.
5. Return G and A.
Example 6 [An illustration of Phase IJ. Consider the causal structure in Figure 7 Suppose that at the beginning. the active variable set is & {[X]]..... {X26 H. With Phase I, one can know that Pa((X17)) = {(X16), {X1s}}. Pa((X16]) = (Xe). and Pa Pa((Xg))= {X2}.
3.2 PIISE II: DISCOVERING NEW ATOMIC UNITS
After there no leaf atomic units with their full parents in current A. which can be identified by Phase I, we discover new atomic units by clustering their pure children from A in Phase II. This procedure is achieved by first clustering the child atomic units that have common parents, and then identifying pure children to discover new atomic units.
Theorem 2 (Clustering atomic units). Let U be a set of non-overlapping alomic units satisfying PO-LiNGAM with known MSa.b for each atomic unit in U, and there is no such leaf atomic unit in U that its full parents are also in U. Let Y S (Y) be a part of measured surrogate variables of Y, where is subset of and no Y C Y satisfies Y C MS,(Y). The atomic unit set have a total of Y|| parent variables (including latent variables), denoted as P, which can d-separate Y from UN (Y)P), ifa.) (MSa (U)Y), Y) follows the GIN condition, b.) there is no subset Y Y such that (MS. (U)) W), Y) follows the GIN condition, and c.) there no any alomic unit P E Y such that (MS (P OUW Y), Y) follows the GIN condition.
Example 7. Consider the causal graph in Figure 7 composed U ([X2), (Xa)...... ..., (8&)). We can fand five Y clusters that satisfy Theorem i.e. ,,= ([Xa), [X+]], J. Y2 [[xs). (Xe), (87)), Y3 = (Xo): (Xe). {X Y4
{[Xo), (X7), (X+}), and Yr [[Xo), (Xa))
Similar to Theorem Theorem 2 focus on the non-overlapping atomic units. Furthermore, for two overlapping atomic units. if one atomic unit is entirely covered by another, the parents of the covered atomic unit must be a subset of or identical to the parents of the covering atomic unit. To leverage the covering atomic unit, we introduce a complement Theorem which extends its applicability to overlapping atomic units.
In Theorem 2, before testing GIN conditions, if any atomic units in U is completely covered by any one atomic unit in Y, then we remove these covered atomic units from U.
Remark 2 (Complement to Theorem 2).
Next, we propose Corollary I It helps identify individual pure children of set V's common parents from W, thus providing information for the new atomic units.
Corollary 1 (Identifying individual pure child). Let U be a set of atomic units satisfying PO- LINGAM with known MS..b for each atomic unit in U, and there is no such leaf atomic unit in U that its full parents are also in UU. Let Y be subset of U that satisfies Theorem 2 with Remark 2, and Vi be an atomic unit in Y. For any one atomic unit )12 in Y. iff the new subset (D)z U U.Y. } also satisfies Theorem 2 with Remark 2, then (3% U U 2/ has the same total parent set as those of Y, and )i and Y/ are two individual pure children, each of which is not partially or fully covered by other atomic units.

---

Published as a conference paper at ICLR 2024
Example 8. Continuing from Example 7, Y2 {[Xs], (X)), ((x)
{X&}}
are two clusters that fulfill the requirements. We can know Y2 and L3 share the same parent set because they both have {XxHHo)), }, and {X7} and {Xs} are two individual pure children of their common parent set because either of them can form a cluster with the base set (Xxx)(Xa))
Based on the theorems above, we can discover new atomic units by identifying individual pure atomic unit children that have common parents. There is a special situation where only one com- mon latent parent variable is behind only two atomic units, called bi-unit cluster. For example, ((Xa), [X+}] in Figurel L In such situation, Corollary does not help to identify whether { {Xa) and {X1} have direct causal relationship between them. Fortunately, Lemma 1 in Xie et al. (2022) provides a solution and is integrated into our algorithm.
Below, we present the search procedure of Phase II, where step 4 is aligned with the requirement of the second term in Definition 3 The detailed algorithm can be found in Algorithm (3 (Appendix c.2). During Phase II, we exclusively focus on pure children in current A. Causal relationships for impure children and uncovered pure children are inferred in Phase I of subsequent iterations.
Phase II: Discovering New Atomic Units
1. Start with partial causal graph G. active atomic unit set A. and size n
2. n = n+11 1. For each variable subset Y from MS, (A) with ||||| = n, test if Y satisfies Theorem with Remark 2, until all subset are tested. Collect the satisfactory Y where Y C MY).
3. Gather the satisfactory Y sets that contain some same atomic units together as set of sets, and add it into a collection C, repeatedly and exhaustively. C is thus a collection of sets of sets.
4. For each element (set of sets) in C, first identify individual pure atomic unit children for the bi- unit cluster by Lemma in Xie et al. (022). Then, identify individual pure atomic unit children by choosing a base set and testing Corollary 1. Additionally, with the help of identified pure children, identify whether atomic units in the base set are also pure children.
5. If sufficient number of pure children that share the same parents are identified, we create new and remove their pure children from A. 6. Repeat steps 2-5 until no more subsets that satisfy Theorem 2 with Remark are found.
atomic units, add them into A and
7. Return G, A. and NewAtomicUniis
Example 9 [An illustration of Phase II]. Continuing from Example 6 and consider the structure in
Figure ! The current & = [[X1]...... {[&], {Xio)...... {X1s), {X1s) bas............. ... {X2s }) With Phase
II, we can discover and introduce new atomic unit {LA} to be parent of { (Xa), (X4),, D. [L2 Lg} to be parent of ([Xs), {Xe), {X7),
, {Xs]), {L,, [g } to be parent of (X12), ) (X1a) [X14) (Xis),.
{L1) to be purent of ((81s), {X19]), and [I,, to be purent of ((X1)) J. (X22)
(X23). (X24))
We add the new discovered atomic units into A and remove their individual pure children fhildrenfrrm A.
Due to the mechanism of Theorem 2 and the searching procedure of Phase II, clustering issue may arise when the parent atomic unit is fully covered by others. For example, in Figure [ if (Xa} was a latent atomic unit and not in current A, then during Phase II, (X4) would be clustered with {[Xs), (Xs), {X7}, {X+}- Consequently, it would be treated as sharing the same parent atomic unit L' that contains two variables, other variables in the cluster. Fortunately, after {Xa} is discovered, we can identify the sub atomic unit from L' by re-clustering {{Xa), {Xa)). We introduce Proposition 2 to check sub-atomic units in the general case and incorporate an additional procedure into Phase (lines 8 and 14, Alg. 2). Further details can be found in Appendix C.4
Proposition 2 (Checking sub-atomic units) Let P be a collection of a.) an atomic unit, b.) the atomic units that have common children with it, and c.) the atomic units that overlap with it. Let U be the set of all children of each atomic unit P,, and Y be a subset of MS. (Y) where Y is subset of U. If there is no such Y with || S [[Pa(Y)] satisfying Theorem 2 and Remark 2 with corresponding parameters (U, Y, Y), then no undiscovered sub-atomic units in I can be further identified.
3.3 PHASE III: REFINING ATOMIC UNITS
In this phase, we check whether the newly discovered atomic units in Phase II have variable overlap with other atomic units in A, which is relatively under-explored in other methods (Xie et al. 2020 Huang et al. 2022). Following that, we further verify each atomic unit in & by checking whether can be fully decomposed into other smaller atomic units in A.
7

---

Published as a conference paper at ICLR 2024
Theorem 3 (Checking the overlap of atomic units). Let U1 and U2 be two atomic units. Let U1 be part of variables in MS, Iff (MSa(14 (U UU2), U1 U (S) follows the GIN condition and there is no subset U1 C U1 such that (MS, (14 UU2), U2 U MSa((42) follows the GIN condition, then the two atomic units have | ||U1 + 11 overlapping variables in total.
Example 10. Consider two atomic unit } and {LI, P X the GIN condition. This implies that {Lı] and (Lı, X2)
in Figure 7 Let =1= {Xx) and we
find ([X3, Xs, Xe);
have / = 1-|+/ overlapping variable. The same comes for {X2] and (T,,X2)
By Theorem +] identify the overlapping atomic units in A. facilitating structure identification in the subsequent iterations. Furthermore, in the A after Phase II, there may exist decomposable "atomic units' that can be decomposed and replaced by other smaller atomic units in A. We have the following corollary to identify such situations.
Corollary (Identifying decomposable 'atomic unit'). Let U be an atomic unit and S be set of small atomic units that can be completely covered by U and do not overlap with each other. U can be completely decomposed as and replaced by the atomic units S. iff [itd = =|||||-
Continuing from Example 10, we find that both { and {X2} have one overlapping variable with {I1,X, but not with each other. {L,, X2} is a decomposable 'atomic unit', which can be replaced by two small atomic wnits {Li} and {X2).
Example 11.
In our algorithm, for each identified decomposable 'atomic unit' in A. we replace it with the small atomic units that make it up and move the children of that decomposable 'atomic unit' to them. The searching procedure for Phase III presented below, and a detailed algorithm can be found in Algorithm (Appendix C.3
Phase III: Refining Atomic Units
1. Start with partial causal graph G. active atomic unit set A. and NewAttomiCUnitSet.
2. For each pair of atomic units in A (at least one of which is also in NewAtomicUnitSet), test whether Theorem 3 applies and, so, record the number of overlapping variables.
3. For each atomic unit in A. which overlaps with other atomic units in A, test whether it is decom- posable by Corollary 2. Move the children of the decomposable 'atomic unit' to the atomic units that decompose it, and remove it from A.
5. Return G and A.
Example 12 [An illustration of Phase III] Continuing from Example 9 and consider the structure in Figure With Phase III, we can can find the new discovered atomic unit (I/z, L1}] can be fully replaced by {LA J and {X2}. We move the children of (I.2, Lg} to (I4) and {Xa}, and remove (L/2 L/ from A. After that, we start the next iteration and feed the current A into Phase
3.4 IDENTIFABILITY FOR CAUSAL STRUCTURES
In this section, we discuss the identifiability of our algorithm for the causal structure. Our algorithm runs three phases in a loop, discovering the causal graph from leaf to root nodes. The computational complexity depends on the number of variables (including latent variables) and density of underlying causal graph, which determine the number of iterations needed to discover the entire graph. A complete illustrative example and the algorithm complexity are provided in Appendix D and along with some experiments of running time in Appendix G.4
Theorem 4 (Identifiability of causal graph). Suppose that the input data X follows PO-LiNGAM with the PO-LiNGAM identifiability condition. Then the atomic units, their size, and the causal structure among them can be fully identified with our algorithm. If there are no direct causal rela- tionships between variables within atomic units, the entire causal graph & is virtually identifiable.
Moreover, it is natural that under more stringent conditions, the identification of the causal graph can be accomplished using only a subset of the theorems and procedures outined earlier.
Corollary 3 (Identifiability of causal graph with stricter conditions). Suppose that the input data X. follows PO-LiNGAM. If each latent variable has at least two pure variable children, the entire causal graph can be identified with aid of Theorem 1, Theorem 2, and Corollary I from Phases and
Sttictly speaking, {T., X₂} is not atomic unit because it is decomposable. However, we did not know this when we discovered by clustering its pure children in Phase II.
8

---

Published as a conference paper at ICLR 2024
Table Comparison on synthetic data with four typical causal structures. Results are averaged over ten experiments. "_" indicates that the method is not suitable for the corresponding graph.
Eme XIE
Pl-aae PORCUN
Aspmmi
Caps LINGAM
PaaLIN
LaRME
Ebur
LINCAM
FANGEN
LaiME
LNGAAM
18533
1/0
0.6
10%
8.96
1.0
0.6
0.0
0.99
10
0.56
0.25
0.2
0.20
0.67
0.55
08
0.50
0.55
0.30
0.35
0.71
0.00
0.70
0.63
C
BC97
175
1738
070
0.00
100
11:00
033
0270
1220
070
0197
0.5
622
0.4
0:25
Case 3
116
1099
0225
025
0.57
1007
1008
1825
1225
0225
1223
0.54
1230
0.31
007
0.25
100
1
13.5
1.30
0.58
1005
100
1.75
1715
0.30
0.23
1.0
1030
0723
1087
0.75
8.93
10:0
0.21
000
0.25
0.29
0.34
0.30
133
0.2
0.63
000
0.3
070
0.33
0.26
1097
0.54
II. Alternatively, if there are no latent confounders, the entire causal graph can be identified with aid of only Proposition I, a simplified version of Theorem I from Phase I.
4
EXPERIMENTS
4.1
SYNTHETIC DATA
In the simulation studies, we compared our method with competitive baselines, including typical LiNGAM (Shimizu et al. 2006: 2011). measurement-bart based methods such as BPC (Silva et al. 2006)
and FastGIN (Xie et al. 2020), hierarchical methods such as LaHME (Xie et al. 2022) and IL (Huang et al. 2022). We considered four typical causal structures: i) all measured variables, ii) latent mediators between measured variables, iii) latent hierarchies, and iv) a general causal structure synthesized from first three cases, shown in Figure 2 To evaluate the results,
employed three metries adapted from Xie et al. (2022) and Huang et al. (2022), including i) Correct Ordering Rate, ii) Error Rate in Latent Variables, and fii) F1-score. For more information, please refer to Appendix The experimental results are reported in Table Our algorithm performs well with all structures, which proves that can deal with general causal structures, whereas other methods focus only on particular settings. For complex causal structures such as Case 4, a substantial sample size is often required. One possible reason is that the reliable estimation of higher-order statistics requires much more samples than that of second-order statistics (Hyvärinen et al. 2009).
X4
(a) Case
(b) Case 2
(c) Case 3
(d) Case
Figure 2: Causal structures used in our simulation studies. Case 4 is the same in Figure 1.
4.2 REAL-WORLD DATA
We evaluate our method on two real-world datasets, including H&:S-1939 dataset (Holzinger &
Swineford 1939) and SOFA dataset (Muthén & Muthén] 2017). More details is in Appendix H
Result H& 19339 dataset: We focus nine of the original 26 tests, as in Cui et al. (019))
The result graph is shown in Figure I0 Consistent with the path diagram in Cui et al. (2019), 9), the variables belonging to the textual aspect (T) T2, T3)) and visual aspect (V V2. V3) are clustered and influenced by their respective latent factors. Furthermore, the variables in the speeded aspect (S1. S2, S3) are influenced by those of textual aspect and visual aspect. This relationship can be attributed to the fact that speed is, in essence, a reflection of both textual and visual comprehension. Result on SOFA dataset: The result graph of our output forms a hierarchical structure, consistent with the hypothesized model given in Chapter 5 of Muthén & Muthén (2017).
CONCLUSIONS AND FUTURE WORK
In this paper, we have theoretically demonstrated the identifiability of causal structures under the linear causal model and non-Gaussiynity assumptions, without prior knowledge regarding the pres- ence or positions of latent variables. Furthermore, we proposed feasible iterative algorithm to identify the causal graph. To strike a good balance between theoretical identifiability and practical feasibility we currently require sufficient number of pure children for each atomic unit. One future research is directed towards reducing the number of pure children required. Another direction for future research is to estimate the causal structure under nonlinear causal models.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
This material is based upon work supported by the AI Research Institutes Program funded by the National Science Foundation under Al Institute for Societal Decision Making (AI-SDM), Award No. 2229881. The project is also partially supported by the National Institutes of Health (NIH) under Contract R01HL159805, and grants from Apple Inc., KDDI Research Inc., Quris AI, and Infinite Brain Technology. FX would like to acknowledge the support by the Natural Science Foundation of China (62306019).
REFERENCES
Jeffrey Adams, Niels Hansen, and Kun Zhang. Identification of partially observed linear causal models: Graphical conditions for the non- gan-saasiian and heterogeneous cases. Advances Neural 2021.
Information Processing Systems, 34:22822
Animashree Anandkumar, Daniel Hsu, Adel Javanmard, and Sham Kakade. Learning linear bayesian networks with latent variables. In International Conference on Machine Learning, pp. 249-22 257. PMLR, 2013.
Ruichu Cai, Feng Xie, Clark Glymour, Zhifeng Hao, and Kun Zhang. Triad constraints for learning causal structure of latent variables. Advances in neural information processing systems, 32, 2019.
Venkat Chandrasekaran, Pablo A Parrilo, and Alan S Willsky. Latent variable graphical model selection via convex optimization. In 2010 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 1610-1613. IEEE, 2010.
Venkat Chandrasekaran, Sujay Sanghavi, Pablo Parrilo, and Alan Willsky. Rank-sparsity inco- herence for matrix decomposition. SIAM Journal Optimization, 21(2):572-596, 2011.
Zhitang Chen and Laiwan Chan. Causality in linear nongaussian acyclic models in the presence of latent gaussian confounders. Neural Computation, 25(6):1005-164) 2013.
David Maxwell Chickering. Optimal structure identification with greedy search. Journal of machine learning research, 50075455 2002.
Myung Jin Choi, Vincent YF Tan, Animashree Anandkumar, and Alan S Willsky. Learning latent tree graphical models. Journal of Machine Learning Research, 12:1771-1812, 2011.
Tom Claassen, Joris Mooij, and Tom Heskes. Learning sparse causal models is not np-hard. arXiv preprint arXiv: 30990.30.0000 6824, 2013.
Diego Colombo, Marloes H Maathuis, Markus Kalisch, and Thomas S Richardson. Learning high- dimensional directed acyelic graphs with latent and selection variables. The Annals of Statistics, pp. 294-321, 2012.
Ruifei Cui, Ioan Gabriel Bucur, Perry Groot, and Tom Heskes. novel bayesian approach for latent variable modeling from mixed data with missing values. Statisties and Computing, 29:977-993, 2019.
Mathias Drton, Shaowei Lin, Luca Weihs, and Piotr Zwiernik. Marginal likelihood and model selection for gaussian latent tree and forest models. 2017.
Karl John Holzinger and Frances Swineford. A study in factor analysis: The stability of a bi-factor solution. Supplementary educational monographs, 1939.
Patrik O Hoyer, Shohei Shimizu, Antti J Kerminen, and Markus Palviainen. Estimation of causal effects using linear non-gaussin non-gaussian causal models with hidden variables. International Journal of Approximate Reasoning, 49(2):362-378, 2008
Biwei Huang, Charles Jia Han Low, Feng Xie, Clark Glymour, and Kun Zhang. Latent hierarchical causal structure discovery with rank constraints. arXiv preprint arXiv:2210.017900 2022.
10

---

Published as a conference paper at ICLR 2024
Aapo Hyvärinen, Janmo Hurri, Patrik O Hoyer, Aapo Hyvärinen, Jarmo Hurri, and Patrik O Hoyer. Independent component analysis. Springer, 2009.
Karl G Jöreskog. A general approach to confirmatory maximum likelihood factor analysis. Psy- chometrika, 34(2):183-25) 202, 1969.
Bohdan Kivva, Goutham Rajendran, Pradeep Ravikumar, and Bryon Aragam. Learning latent causal graphs via mixture oracles. Advances in Neural Information Processing Systems, 34:18087- 18101, 2021.
Lingjing Kong, Biwei Huang, Feng Xie, Eric Xing, Yuejie Chi, and Kun Zhang. Identification of nonlinear latent hierarchical models. arXiv preprint arXiv:2306.0799 07916,, 2023.
Erich Kummerfeld and Joseph Ramsey. Causal clustering for 1-factor measurement models. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pp. 1655-1664, 2016.
Takashi Nicholas Maeda and Shohei Shimizu. Red:
Repetitive causal discovery of linear non- gaussian acyclic models with latent confounders. In International Conference on Artificial Intel- ligence and Statistics, pp. 735-745. PMLR, 2020.
Linda K Muthén and Bengt Muthén. Mplus user's guide: Statistical analysis with latent variables,
user's guide. Muthén Muthén, 2017.
Judea Pearl. Probabilistic reasoning in intelligent systems: networks of plausible inference. Morgan kaufmann, 1988.
Yves Rosseel. lavaan: An package for structural equation modeling, Journal of statistical software, 48:1-36, 2012.
Shohei Shimizu, Patrik O Hoyer, Aapo Hyvärinen, Antti Kerminen, and Michael Jordan. A linear non-gaussian acyclic model for causal discovery. Journal of Machine Learning Research, 7(10), 2006.
Shohei Shimizu, Patrik O Hoyer, and Aapo Hyvärinen. Estimation of linear non-gaussian acyclic models for latent factors. Nearocomputingg 72(7-9):2024-2000 2027, 2009.
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-gaussian structural equation model. Journal of Machine Learn- ing Research-JMLR, 12(Apr):1225-1248 2011.
Ricardo Silva, Richard Scheines, Clark Glymour, Peter Spirtes, and David Maxwell Chickering. Learning the structure of linear latent variable models. Journal of Machine Learning Research, (2), 2006.
Charles Spearman. Pearson's contribution to the theory of two factors. British Journal of Psychol- ogy, 19(1):95, 1928.
Peter Spirtes and Clark Glymour. An algorithm fast recovery sparse causal graphs. Social science computer review, 91)):22-7, 1991.
Peter Spirtes and Kun Zhang. Causal discovery and inference: concepts and recent methodological advances. In Applied informatics, volume 3, pp. 3. SpringerOpen, 2016.
Peter Spirtes, Christopher Meek, and Thomas Richardson. Causal inference the presence of latent variables and selection bias. In Proceedings of the Eleventh Conference Uncertainty in Artificial Intelligence, UAI'95, pp. 499-506, San Francisco, CA, USA, 1995. Morgan Kaufmann Publishers Inc. ISBN 1558603859.
Peter Spirtes, Clark N Glymour, and Richard Scheines. Causation, prediction, and search. MIT press, 2000.
11

---

Published as a conference paper at ICLR 2024
Chandler Squires, Annie Yun, Eshaan Nichani, Raj Agrawal, and Caroline Uhler. Causal structure discovery between clusters of nodes induced by latent factors. In Conference on Causal Learning and Reasoning, pp. 669-687. PMLR, 2022.
Seth Sullivant, Kelli Talaska, and Jan Draisma. Trek separation for gaussian graphical models. 2010.
Tatsuya Tashiro, Shohei Shimizu, Aapo Hyvärinen, and Takashi Washio. Parcelingam: A causal ordering method robust against latent confounders. Neural computation, 26(1):57-883 2014.
Feng Xie, Ruichu Cai, Biwei Huang, Clark Glymour, Zhifeng Hao, and Kun Zhang. Generalized independent noise condition for estimating latent variable causal graphs. Advances neural information processing systems, 33:1 18911-9224, 2020.
Feng Xie, Biwei Huang, Zhengming Chen, Yangbo He, Zhi Geng, and Kun Zhang. Identifica- tion of linear non- gaussian latent hierarchical structure. In International Conference on Machine Learning. pp. 24370-2438 PMLR, 2022.
Feng Xie, Biwei Huang, Zhengming Chen, Ruichu Cai, Clark Glymour, Zhi Geng, and Kun Zhang. Generalized independent noise condition for estimating causal structure with latent variables. arXiv preprint 3rXiv:2388.067// 2023.
Nevin Zhang. Hierarchical latent class models for cluster analysis. The Journal of Machine Learning Research, 5:697-723, 2004.
Qinyi Zhang, Sarah Filippi, Arthur Gretton, and Dino Sejdinovic. Large-scale kernel methods for independence testing. Statistics and Computing, 28: 13-130, 2018.
12

---

Published as a conference paper at ICLR 2024
A RELATED WORK
Inferring causal relationships from observed data is popular field of statistics and artificial intelli- gence. As described in the introduction, from the scope of application, most methods can be divided into three areas: a) Infer the causal relations among measured variables with the assumption that there are no latent variables, for example, PC algorithm (Spirtes & Glymour 1991), LiNGAM- based method (Shimizu et al.] 2006). Greedy search (Chickering) (002). b) Infer the causal relations among measured variables in the presence of latent variable interference, for example, FCI and its variants (Spirtes et al. 1995 Colombo et al. 2012 Claassen et al. 2013). c) Infer the causal rela- tions among latent variables, for example, measurement models (Silva al. 2006 [Kummereeld &
Ramsey 2016 Cai et al. [2019] Xie et al. 2020) and hierarchical models (Pearl [988| Zhang 2004
Choi et al. 201 Drton et al. 2017] Xie al., 2022; Huang et al.
2022] Kong et al. 2023).
Depending on the different constraints and criteria used, most previous causal discovery methods can be divided into the following main categories:
1.) NNo--arammtrie setting) Conditional independence constraint: The PC algorithm (Spirtes & Glymour 199T), as well as the FCI algorithm (Spirtes et al., 1995) and their variants (Colombo et al. 2012, Claassen et al.) 2013), are prominent examples of non-parametric methods that infer causal relationships among measured variables by testing conditional independence. They do not care about whether the causal relationships are linear or not. However, these methods struggle with the latent variables and their causal relationships. Another limitation is that they yield multiple Markov equivalent structures, introducing ambiguity regarding the presence of confounders in the resulting graph.
2.) (Linear Gaussian setting) Tetrad condition and rank deficiency constraint: By investigating the sub-covariance matrix of measured variables, Tetrad condition (Spearman 1928) allows to locate latent variables and infer the causal relationships among them in Ginear-Gaussian settings (Pearl 1988 [Silaa et al.] [2006] Kummerfeld & Ramsey (2016). These methods generally assume that each latent variable possesses at least three pure measured variables as pure children, and each measured variable is exclusively a pure child of a single latent variable. [Squires et al. (2022) presented a Tetrad-basse method that allows latent variables to be influenced by measured variables. It relies on strong assumptions, such as the absence of edges between pairs of observed nodes or between pairs of latent nodes. The rank deficiency constraint is a general version of the Tetrad condition. [Huang ett al. (2022) use it to infer a latent hierarchical structure, which assumes k+1 pure children and k+1 neighbors for a set of latent variables with size k, and implicitly assumes all clustered children pure children. Similar to the conditional independence constraint based methods, they return result that is asymptotic to the ground truth graph.
3.) (Linear non-Gaussian setting) Independent component analysis (ICA): Shimizu et al. (006) leveraged non- -aussiaust of data and showed that a linear non-Gaussian acyclic model (LiN GAMM is identifiable based on ICA algorithm. By over-complete ICA, for example, [Hoyer al. (0008;; Shimizu et al. (2009); Tashiro et al.) (2014) learn the causal structure with latent variables. The limitation of over-complete ICA is that there are equivalence structures and the estimation is easy to fall into local optima. Recently, based on overcomplete ICA, AAdms et al. (022I) established necessary and sufficient conditions for structure identifiability in both the linear non-Gaussian and the linear heterogeneous setting. However, it does not have a practical estimation approach and requires knowing the number of latent variables at the beginning.
4.) (Linear non-Gaussian setting) Independent noise, Triad constraint, and GIN condition: al. (20IT) proposed DirectLiNGAM in 2011, which learns LiNGAM by replacing the ICA al- gorithm with regression and independence tests of noises. Triad constraint (Cai et al. 2019) is an extension of the independent noise condition for latent variables with the same assumption that the noise terms are non -au-Saas,,n, and is used to discover the structure of latent variables. GIN condi- tion Xie et al. (2020) is a more general version that allows multiple parents behind multiple children. Xie et al. (2022) identify a latent hierarchical structure by using the GIN condition, which assumes one-factor clusters and measured variables to be descendants of latent variables.
Shimizu
5.) (Linear setting) Matrix decomposition and Optimization: Matrix decomposition techniques have been applied to model causal structures. Under specific conditions, the precision matrix can be decomposed into two components: low-rank matrix that characterizes the causal relationships from
13

---

Published as a conference paper at ICLR 2024
latent variables to measured variables, and sparse matrix that represents the relationships among measured variables (Chandrasekaran et al. 2010; 2011). By requiring triple measured variables than latent variables, Anandkumar et al. (2013) decompose the covariance matrix, and is capable of handling DAGs with effective depth one and multi-level Directed Acyelic Graphs (DAGss (similar to latent hierarchical structures), with the help of low-order observable moments.
With the help of discrete latent variables, Kivva et al. (2021) proposed a mixture oracles- based method to identify the potentially nonlinear latent variable graph. Recently, Kong et al. (2023) learns a nonlinear latent hierarchical causal model by self-supervised representation learning. This innovative method accommodates general nonlinearity and multi- dunti--dimnsionall continuous variables. However, this approach still relies on strong assumptions regarding the data generation process and the estimation easy to fall into local optima.
6.) Others:
B WHEN THE PO-LINGAM IDENTIFIABILITY CONDITION IS VIOLATED
B. THEORETICCA ANALYSIS
PO-LINGAM Identifiability Condition: a.) Any latent variable is at least one atomic unit. b.) For any two atomic units with overlapping variables, their non-overlapping parts do not influence each other.
ii Violation of identifiability condition(a): Our algorithm discovers atomic units by clustering their individual pure children, and whether the number of pure children for latent variables satisfies the condition is tested during the discovery process, which is mainly achieved by Theorem 2, Remark 2, and Corollary 1. Meanwhile, please notice that our algorithm sequentially identifies the whole causal graph from leaves to roots. The higher-order causal structure be inferred only after the lower-order causal structure are fully identified. As a consequence, the algorithm halts its inference of the higher-order causal structure when the latent set lacks a sufficient number of individual pure children to be located, so that it does not output spurious latent variables. In other word, since this condition violated, can detect all latent variables, but we can still trust the discovered ones. The atomic units, whose causal orders are lower or equal to the unidentified latent set, and the causal relations among them are still identifiable.
(ii) Violation of identifiability condition(b): Let's consider the example in Figure B(a), where two atomic units [L, L2] and (L,, are both caused by {- Meanwhile, L, causes Lg. which violates identifiability condition(b). In our algorithm, for any two atomic units with overlapping variables, ignores the influence of non-overlapping part of one atomic unit to that of another and infer their causal relationships separately, illustrated in Remark [ and Remark 2 Therefore, the discovered causal graph will ignore the causal relationships between non -on-olellapinng parts any two overlapping atomic units, as shown in Figure (b).
X2 X1
X
X2 X
X
(a) Ground-truth graph
(b) Discovered graph
Figure 3: An example of causal graphs where identifiability condition(b) is violated.
B.2 EXPERIMENTS
(i) To evaluate the performance of our algorithm under the violation of condition(a). we adjusted the causal graphs in Cases 2 and 3 of the simulation experiment, resulting in Case A and Case B of Figure 4 In Case A, L1 lacks sufficient pure atomic unit children for discovery due to the causal chain X2 + + X,. Nevertheless, the algorithm can still identify the causal structure L, and its descendants, shown in Figure 4b)). Moreover, in Case B, where Lg cannot be discovered due to having only one pure atomic unit child, namely X,, the algorithm still identifies the causal structure of I.g and I4, shown in Figure d). The corresponding average numerical result from
14

---

Published as a conference paper at ICLR 2024
ten executions is presented in Table The high Correct Ordering Rate indicates that the discovered partial causal graph highly accurate.
L1
X2 23 X4 Xs X6 X7
Xs
X8 X2 Xs
X4 X5
Xa
(a) Case A: ground truth
(b) Case A: discovered graph
L
L2
X1 X2 X3
X X7
X1 X2 X3
X=
(c) Case B: ground truth
(d) Case B: discovered graph
Figure 4: Causal graphs that violate identifiability condition(a), and the corresponding discovered results acquired by our method.
Table The performance of our method three causal graphs that violate the PO-LiNGAM iden-
tifiability condition. Case A and Case B violate the condition(a), as shown in Figure 4 Case C
violates the condition(b), as shown Figure
Case A
Case B
Case C
5k
10k
50k
10k
50k
5k
10k
50k
Correct Ordering Rate
0.98
1.0
1.0
1.0
1.0
1.0
0.94
0.94
1.0
Error Rate in Latent Variables
0.45
0.5
0.5
0.53
0.5
0.5
0.66
0.52
0.33
Fl-score f
0.55
0.56
0.56
0.60
0.62
0.62
0.54
0.66
0.85
(ii) To evaluate the performance of our algorithm under the violation of condition(b), we tested the algorithm with the ground-truth graph in Figure aa.. The result discovered by our method is in Figure b). The corresponding average numerical result from ten executions is presented in Case of Table 3 The high Correct Ordering Rate indicates that the discovered partial causal graph is highly accurate.
C DETAILS OF IDENTIFICATION ALGORITHM
Our algorithm is iterative, with each iteration comprising three main phases, progressively uncover- ing the entire causal graph from leaf to root nodes. For each iteration, first recursively identifies the leaf nodes and their parent nodes from the active atomic unit set A in the causal graph composed of atomic units of A and their latent confounders, and update A. (Phase I). Then, we discover new atomic units by clustering their pure children in A, and update A (Phase II). After that, we refine newly discovered atomic units by checking overlapping atomic units and decomposable 'atomic units', and update A (Phase III), At the end of an iteration, A is sent back to the Phase I and new iteration starts until no more atomic units & are updated.
C.I PHASE
The detailed algorithm for Phase I is in Algorithm
C.2 PHASE II
The detailed algorithm for Phase Algorithm
C.3 PHASE III
The detailed algorithm for Phase III is in Algorithm
15

---

Published as a conference paper at ICLR 2024
C.4 SUPPLEMENTARY ALGORITHMS FOR PHASE
To handle the situation explained at the end of section 3.2 we proposed two additional steps for (line 14, Alg. 2
Phase including Algorithm (line 8, Alg. 2 and Algorithm 6
Small atomic units that can be completely covered by larger atomic units are sometimes indistin- guishable from those larger atomic units due to the different causal order counting from the Icaf nodes of the graph as well as the characterization of the GIN condition. The purpose of Algorithm 5 check this case by rechecking the number parent variables of the related atomic unit children. If such a case happens, most children are re-added into A and treated the same as others in A. For the special children that have partial parents not in A, Algorithm used to relocate parents for them after the normal children are settled.
C.5 CHECK FOR MULTIPLE ROOT ATOMIC UNITS
Most causal discovery methods for handling latent variables Silva et al. (2006); Cai et al. (2019); Xie et al. (2020 2022); Huang al. (2022) implicitly assume that there no unconditional inde- pendence between any two variables in the measured variable set X. In other words, they assume that there is at most one root node in the causal graph, which may be a latent variable or latent
variable set with common children.
In practical situations, there may be more than one root node in causal graph, not to mention that the input measured variables may form multiple disconnected subgraphs. In Figure ata), X1 X4 form subgraph, while X5 not connected to any other variables. Furthermore, in the sub causal graph consisting of X1 X4, X2 is unconditionally independent of both X3 and X4. In such case, there are three root nodes: X1, L1, and X5.
Our methods can handle the situation regardless of the number of root atomic units in the causal graph. At the end of the inference process, the algorithm tends to cluster all the true root atomic units (three or more) together and assigns them common latent parent variable, as depicted in Figure This occurs because when the active atomic unit set contains only root atomic units, those root atomic units naturally satisfy the GIN condition and are unconditionally independent of each other without requiring any additional operations. is considered that those root atomic units share common latent parent variable with value of O. To verify the presence of multiple root atomic units in the causal graph, we can perform the independence tests. If the discovered root atomic unit comprises only latent variable and lacks impure children, we should examine the unconditional independence of the pure atomic unit children of that discovered root atomic unit (For latent atomic units, their measured surrogate sets are used). If these pure children are found to be unconditionally independent of each other, then we can conclude that they are the true root atomic units of the causal graph. One the other hand, if the initially discovered causal graph has only two root atomic units, we can do the same unconditional independence test to check whether there is common latent variable parent behind them.
X1
Xs
X
X₂
(a) Ground-truth graph
(b) Discovered graph
Figure 5: An example of causal structures where there are multiple root atomic units.
16

---

Published as a conference paper at ICLR 2024
Algorithm 2: Phase I: J.dettihLLaloooosssschhhrrrPrrrr
Partial causal graph G, Active atomic unit A Output: Partial causal graph 9 Active atomic unit set A repeat
Input:
Select atomic unit L/ E A: for GrLen < to | [ do
repeat
Select atomic unit subset from A'U such that [IP] Gen
U with IP satisfies Theorem I and Remark I then + A A,M, and update G;
A) +- CheckSubAtoomicnnits. PPF::
Return to line 2:
10
end
11
until all subsets with size GrLen in A u selected;
end
until more atomic units can be removed from A;; (G, A) < wtw.:aCciiideeooSSSuutttttttiiie
14
A.);
return G,
Algorithm 3: Phase II: DissoverNewAAtomiiCuts
Input:
Partial causal graph G, Active atomic unit set A
Output: Partial causal graph G. Active atomic unit set
GrLen:= 2, A == A, and NewAtomieUniiSett: := 0;
repeat
ClusterList:= 0;
repeat
Select subset Y from MS,(A') such that ||Y|| GrLen, Y C MS.(T) and V 2: if Y satisfy the Theorem and Remark then Add Y into ClusterList;
end
until all subset with size GrLen in MS,(A') (A') selected;
10
Gather the sets having overlapping atomic units with each other from the ClusterList as set of sets and add into another set C, repeatedly and exhaustively;
11
for each C, C do
12
when GrLen= 2, if C, contains only one set (bi-unit cluster) then identify pure children by Lemma in Xie et al. (2022);
13
Select one set E C,, remove one atomic unit from it, get a base I with |B 2 Grlen- PureChildSet 02 for each set S E C; if [S B do add B into PureChildSet;
15
for each atomic unit
do
Select Grlen-1 atomic units from PureChildSet and patch B with them to form set T,
17
end
if bi-unit cluster is pure cluster, or PureChild 2 Grlen-I and all Ts C; then
The atomic units in PureChildSet and I are all pure children; A AXT PureChildSet, and update G; Create new atomic unit 24 and save it in New.AtomieUnitSet;
20
22
end
23
end
A' < A Cluster and GrLen <- GrLen+1;
24
25
until no more clusters are found:
26
return G, A, and NewAtomicUnitSee
17

---

Published as a conference paper at ICLR 2024
Algorithm 4: Phase III: RefineAtomicUnits
Input:
Partial causal graph G, Active atomic unit A, NewAAtomiUnnittet Partial causal graph 9, Active atomic unit set
Output:
repeat
Select two atomic unit U, 24, E A, where at least one in New AtwmttomiUnniiSet for < to ||24]] do
Select measured surrogates from (24), denoted as Uı if (24 U222). U1 U (22) follows GIN condition then
Ui and L/ have || - ||U,|| + overlapping variables; Update 9, and merge Un with L/2
Return to line 2;
end end
10
11
until all binary atomic unit set selected;
for each atomic unit U A do
13
for each S; E EA and S; S U do add S; into set C; repeat
14
15
Select a subset S C C;
if atomic units in 8 do not overlap and [[ ||||| then Move the children of lI to below the atomic units in S; A is not updated, then & A\;: Update 9;
20
end
21
until all subset in C selected;
22 end
return G
Algorithm 5: CheckSubAtomicUniss
Input: Partial causal graph G, Active atomic unit set A, atomic unit set TP C A Output: Partial causal graph G, Active atomic unit set A.
Let be the union of and the atomic units in that overlap with atomic units in P;
Let U contains the atomic units whose parents is subset of P:
GrLen:= U':= U;
repeat
ClusterList:=
repeat
Sclect subset Y from (U)) such that || GrLen, Y C MS,(Y) and Y 2 2; satisfy the Theorem and Remark then
Add Y into ClusterList;
|| < known [Pl(Y)] then
10
if there are atomic units & A. which has partial atomic unit parents in P and the
rest atomic unit parents & A. then mark them and the atomic units U with matching symbols;
+ (A (P) U, update G, and go to line 18:
12
13
end end
until all subset with size GrLen in MU, selected;
15
U' - Clusturte,,, and GrLen +- GrLen+1;
17 until more clusters are found;
IN return G, A.
18

---

Published as a conference paper at ICLR 2024
Algorithm 6: ReffinChhiddcaoooSSitAtooiiiiii
Input: Partial causal graph G. Active atomic unit
Output: Partial causal graph 9, Active atomic unit set A for each marked set of atomic units in G do if the atomic units in U are all relocated to be children of the smaller atomic wnits then Relocate the parents for the atomic units that used to have partial atomic unit parents in P and the rest of atomic unit parents A, by Theorem and Remark 1; Update G;
end end
return G, A
D ILLUSTRATION OF OUR ALGORITHM
(a)
(b)
Xie Xir
(d)
(c)
Xua
X
X50
Xu
Nir
Xi Na
(
(g)
8 Xia
(h)
Figure 6: Illustration of the entire procedure of our algorithm. For each subgraph, the nodes in blue circles are active variables that are under investigation, and other measured variables for which causal relationships have not been identified
shown for clarity. (a) Ground-truth structure. (b) Output after phase of the first iteration of our algorithm.
(c) Output after phase Il of the first iteration. (d) Output after phase III of the first iteration. (e) Output after phase I of the second
iteration. (f) Output after phase II of the second iteration.
(g) Output after phase III of the second
iteration. (h) Output after phase of the third iteration, which has recovered the causal structure.
In this section, illustrate algorithm with the ground-truth graph in Figure 6 a(). We assume Oracle tests for GIN conditions. In this structure, Ly.... L, are latent variables and ,,...., measured variables. We from the graph that measured variables are interspersed with
19

---

Published as a conference paper at ICLR 2024
latent variables. The causal relationships among them are also complex. The estimation process is as follows:
i Initially, the active atomic unit set A = {(x))..... (X26 } and graph G = 0.
i During phase I of the first iteration, it first identifies (a((X17)) ((X16), (X1s) }. and remove } from the active set A. After that, we sequentially identify Pa( (8(1)1)) = {X9} and } {X2), and update A. The result after phase of the first iteration is shown in Figure b), and the current A = [(X1)......... (X&): (X1o). (X1s), (X1s).... (X2)))
Pa( Pa((Xo]
ii
During phase Il of the first iteration, we cluster the individual pure children in A to form new atomic units. is worth noting that we do not know the true serial numbers of the latent variables. In the following, for the sake of clarity, we use the true serial numbers of latent variables to
denote them. As shown in Figure G(c). we introduce the new atomic unit {L1} to be parent
of individual pure children set {(x3), {X+)). J. the new atomic unit {Lイ, Lxx, } to be parent of
individual pure children set {[Xs) (Xe) J. (X7), (Xa)), the atomic unit [L3, L4 to be parent of
individual pure children set ((X12) ) [X1s), (X13)x(X1))- (X14),(X1s)) (X1s},, the atomic unit {Ls} to be parent of
individual pure children set {{11)) ). {X19] }.. the atomic unit {Ls, L7} to be parent of individual
pure children set {{X21) }. [X22) J. (X2s). (X2+}. We add the newly discovered atomic units into A and remove their individual pure children from A.
iv During phase III of the first iteration, we find that the newly discovered atomic unit {Li Lx,, } can be fully replaced by } and {X2), as shown Figure d).. We move the children of [x,) to } and (X2), and remove {L1, xx2) from A.
v Now, we start the second iteration. During phase I of the second iteration, we find Pa Pa((Ta]) = {[X2), (Lo, L7}}, Pa({X2))
[X2). Pa Pa((X20)) Pa( (X2)) = ((225). LJ.,, and Pa((X25)) = {Lo, L77, as shown in Figure (()..
{[LI): (X1}). Pa( Pa([Li} }) {81}.
vi In phase II of the second iteration, introduce the new atomic unit {L2, L4) to be parent of individual pure children set {[X1o), (X1), }, {Lo, L7 as shown in Figure
vii In phase III of the second iteration, we find that the newly discovered atomic unit (L2 L3} have one variable overlapping with atomic unit {L3, L1}. and merge them. The result is shown in Figure ggg)
viii Now, we start the third iteration. During phase of the third iteration, we find Pa( Pa,, Ls)) {X1} and Pa((L3, La}) = {X1). as shown in Figure Gh). After that, the current active atomic unit set contains only the measured variable[X and the whole underlying causal graph is identified.
E COMPUTATIONAL COMPLEXITY OF OUR ALGORITHM
In this section, we analyze the complexity of our algorithm. Denote by the number of active atomic units at the beginning of each phase. The complexity of phase is upper bounded by On >> x-
k=1 ("r The phase has the worst case complexity O (i)). Denote by / the size of the largest atomic unit in the active atomic unit set. The complexity of phase III is upper bounded by ())))) The total complexity of the algorithm to discover the whole causal graph de- pends the number of (both measured and latent) variables and the structural density of the causal graph, which determine how many iterations the algorithm needs to run.
F PROOFS
Before presenting the proofs of our results, we need a few more theorems and definitions derived from Xie et al. 2222 2023).
Definition 6 (GIN condition (Xe et al., 2020 Let Z. Y be sets of variables in a linear non- Gaussian acyclic causal model. We say that (Z, Y) follows GIN condition if and only if w Y are statistically independent of Z. where w satisfies (ETE|YY) = 0 and w + O.
In other words, (Z,Y: Y) violates the GIN condition if and only if Fxxzz is dependent on Z.
20

---

Published as a conference paper at ICLR 2024
Recently, Xie et al. (2023) extended the original graphical criteria of the GIN condition with the help of trek and trek-separation (t-separationn) (Sullivant et al.) 2010). We next describe the notion of the trek and trek-separation criterion, which more general than d-separation in linear causal models. After that, we show the graphical implication of the GIN condition in PO-LiNGAM, which helps to exploit the GIN condition to discover the causal graph.
Definition (trek (Sullivant et al. 2010)). A trek in 9 from i to j is an ordered pair of directed paths (P1, P2) where P1 has sink i, P2 has sink and both P1 and P2 have the same source k. The common source k is called the top of the trek, denoted top(P1, Pz). Note that one or both of P1 and P2 may consist of a single vertex. that is, a path with no edges.
Definition 8 (t-separation (Sullivant et al., 2010). Let A, B, CA. and CB be four subsets of V. We say the ordered pair (CA. CB) 1-separates A from B for every trek (Tii T2) from a vertex in A to vertex in B, either Ti contains a vertex in CA or T2 contains a vertex in CB.
Theorem (GIN Graphical Criteria PO-LiNGAM)), Let Y and Z be two sets of measured vari- ables of a partially observed linear non non-Gaus Gaussian acyelic causal model (PO-LiNGAM), Assume the faik-aiitfullness holds. (Z, Y) satisfies the GIN condition if and only if there exists variable set S with 0 < Dim(() S min( Dim - 1, (iim(Z)),, such that 1) the order pair (0, S) I-sepurates and Y, and that 2) the covariance matrix of S and Z has rank Dim(S), and so does that of S and Y.
Note: In this paper, (S) = -||S]] represents the number of variables in S, regardless of whether S is a set of variables or set of atomic units.
Roughly speaking, the conditions in this theorem can be interpreted in the following way: i.) a causally earlier subset (according the causal order) of Y t-separates Y from Z, and ii.) the linear transformation from that subset of the common causes to has full column rank. Based on the definition of d-separation, the first interpretation that the causally earlier subset S (according to the causal order) of Y d-separates Y from S,S.
Proof. Recently, it has been shown in Xie et al. (2023) that the graphical criteria hold in linear non-Gaussian acyclic causal model. In (Xie et al. 2020 2022 2023), they allowed part variables to be latent. In our paper, the latent variable can be the descendent ancestor of measured variables, which does not affect the graphical criteria of GIN because linear causal models are transitive.
F.1 PROOF OF PROPOSITION 1
Proof. Let V be set of variables satisfying PO-LiNGAM with latent variables, and V be variable in V.
() Assume that V is leaf variable of the causal graph, and P are its all parents. We know that 0) < |P|| < min( [V U PlI - 1, V(VI),, and b) P is the minimal set so that (0. P) t-separates V\V and VUP. Furthermore, the set of common components between the covariance matrix of P and V V has rank ||S]], and so does that of P and V U P. Therefore, (V)V, VUP) follows the GIN condition and there is no P C P such that VV)V, V,VVV VUP) follows the GIN condition.
V\V P and V V is P. so
(ii) Assume that (V\V,VUP) follows the GIN condition and there is no P C P such that (V)V, VUP) follows the GIN condition. We know that P is the minimal set that (0, P) t-separates VAV and V U.P, and therefore, P is causal earlier than V. In a causal graph, the minimal causal variable from the other variables is the parent set of that variable.
earlier set that t-separates
Therefore, from (i) and (ii), the proposition is proved.
F.2 PROOF OF THEOREM
Proof. The proof of theorem 1 is similar to the proof of Proposition 1. Let U be set of non- overlapping atomic units satisfying PO-LiNGAM with known MS for each atomic unit in U, and LI be an atomic unit in U.
21

---

their measured surrogate variable set Published as a conference paper at ICLR 2024
(i) Assume that 2/ is a leaf atomic unit in the current causal graph, and P is the set of parent atomic units of 24. We know that a) 0 S ||P|| I min [I J - 1, [UVU])) and b) P is the minimal set so that (0, IP) t-separates UM and U JP. Furthermore, the set of common components between U U and U7,44 is P, so the covariance matrix of and 4 UTP has rank ||P]] and so does that of PP and U.4. And because some of the atomic units may be latent, to represent them. Therefore, (MS, (UVZ), (2 P)) follows the GIN condition and there is no P IP such that (MS.(UU44) MS, (24 u P)) follows the the GIN condition. The same is true if represent them using another set of measured surrogate variables.
(ii) Assume that (US4( (S U)) follows the GIN condition and there is no P C such that (M),( (U),), (2 P)) follows the the GIN condition. MS, (U'(4) contains set of measured surrogate set of U U, MS,(UUP contains another set of measured surrogate set U.P. The common component of UV4 and 24 UP P. And, without MS, the GIN condition cannot the Y set. Thus, P is the minimal set that (0, IP) t-separates MS, (U))) and MS, (L4 U P), and therefore, P is causal earlier than U. the causal graph, the minimal causal earlier atomic unit set that t-separates one atomic unit from the other atomic units is the parent set of that atomic unit.
be satisfied singly using (4)
Therefore, from (i) and (ii), the theorem is proved.
F.3 PROOF OF REMARK
Proof. (i) The first term is to eliminate the effect of overlapping atomic unit sets when searching for parents, since for any two atomic units with overlapping variables, we don't have enough informa- tion to know whether the non-overlapping part of one atomic unit is the parent of the non-overlapping part of another atomic unit. As illustrated case I of Figure 7 we want to know the parent of the atomic unit (I2, La), we need remove the atomic unit (Lg, La} from U and P. Otherwise, both
{Lg, L and } will be considered as the parents of {L2, L3} rather than the true parent {L1}-
(i) For the second term, let consider the case 2 of Figure 7 where we want to find the parent of (Xo). P = {(L1, L2), (L2, }a}} and U = {Xg}. There is no point in testing the GIN condition for (U,2)) MS, (14 U P)). since even without MS, in Y set, the graph criteria of GIN condition is still satisfied, so GIN condition. That is because those two atomic units {L,, L2) and (Lg, L3} have overlapping Lg, and therefore the unrepeated variable set behind their measured surrogate variable has size 3 instead of 4. Thus, we need to find subset of (IP) so that the number of variables is equal to the true size |P||| That is the maximal subset S of MS,(P) that makes (UVUU) S) does not follow GIN condition.
No
X10
X2 X X X1
X8
X1
X2
X3
X2
X9
X,
X8
(a) Case 1
(b)
Case
Figure 7: The illustrative examples for remark 1.
F.4 PROOF OF THEOREM? 2
The aim behind Theorem 2, Remark 2, and Corollary is to find sufficiently large number of pure children to support the discovery of new atomic units.
Proof. Let be a set of non-overlapping atomic units satisfying PO-LINGAM with known MS,, for each atomic unit in U, and there is such leaf atomic unit in U that its full parents are also in U. Assume that (MS, (U\Y), Y) follows the GIN condition, and there is no subset Y C Y such that (UVV), Y) follows the GIN condition. It means that there is variable set S with size
22

---

Published as a conference paper at ICLR 2024
|Y||| - 1, which is causal earlier than Y, and the order pair S) t-separates ( and Y. Since we know in IJ' there is no leaf atomic unit that its full parents are also in U, S contains at least one latent variable which is the parent of Y. However, S may also contain variables that are also in Y. The third statement is to check out this situation by explicitly adding the variables in P into S and testing the GIN condition. Therefore, with these three statements, there is parent variable set P involving at least one latent variable, which has size || - and can d-separates Y from the atomic units of UY UP.
ensure that behind Y
F.5 PROOF OF REMARK 2
Proof. It is obvious that Remark 2 does not affect the correctness of Theorem 2 whether not there are overlapping atomic units in U. However, it is reasonable that the parents of the covered atomic unit must be subset of the same as the parents of the covering atomic unit. As illustrated in Figure 8 the atomic unit {L2} is fully covered by [Ln,Is}, and both {L2} and {L2, Ls} have
parent {L1 J- After removing {L2} from the active set, the atomic unit {Lg, L3} can be considered
as an individual pure child for discovering the new atomic unit { according to Corollary 1. D
X7
X8
X9
X10
X
N6
Figure 8: The illustrative examples for remark 2.
F.6 PROOF OF COROLLARY
Proof. If one atomic unit V is replaceable in the Y that satisfies Theorem 2 with Remark 2, then know that in the current causal graph composed of atomic units in U and their latent confounders, Y is not directly causally connected the other atomic units in Y.,, except for their common total parent set. The reverse is also true.
F.7 PROOF OF PROPOSITION 2
Proof. We demonstrate the utility of Proposition 2 and prove it with the example in Figure 9 With algorithm, at the beginning, the active set contains only measured variables. After Phase of the first iteration, nothing is identified. During Phase 2 of the first iteration, we cluster the pure children to discover new atomic units. It is obvious that we can cluster {X&) and {Xg} form the atomic unit (L1}. However, when clustering for discovering the atomic unit L2), the atomic unit
{X2) will also be clustered together with any two of {[Xa), (X1). (Xs), (Xa}), and considered as a individual pure children of the atomic unit {L, L. though (X2} is actually the individual pure child of {I,}. That because that atomic unit [I.. L2 covers atomic unit {I,} and when clustering for [2) {L1} LL,,L)) In the following iterations, {La} will be discovered and identified as a child of {L,, L2)- After that, {L1) } can be separated from (L1, L2) } by re-clustering the children of [L1, L2). ). We know that { and [Ls} can be clustered, which shows the number of parent variables behind them is instead of 2. and therefore, there is small atomic unit covered by (L1, L2).
does not have enough individual pure children to separate it from
F.8 PROOF OF THEOREM 3
Proof. Let and Ll2 be two atomic units. Let U, be part of variables in (S,)
(i Assume that U1 and Uz are two discovered atomic units. (M4 U12)), MS, U242)) can satisfy GIN condition only U4 and U2 have overlapping variables. According to Theorem 5, S = Ui Ulb. DSm(S) should be smaller equal to Dim(Uh) Dim((1) 1 so that the graph
23

---

Published as a conference paper at ICLR 2024
3 X
Xs Ng
X7
Figure 9: The illustrative examples for proposition 2.
criteria of the GIN condition is satisfied. means Ui and U2 have overlapping variables. When Uj the minimal set that (MS, (24 U22)), U1 U MSx(242) follows the GIN condition, we know the true number [u U22 is [1 ll + | 1. Therefore, we know that the two atomic units have |R4 - || ll overlapping variables total.
(ii) Assume that 24 and U2 have |[24 101--100 1-1l +1 overlapping variables. According to the graphical criteria of PO-LiNGAM (Theorem 5 we can know that U₁ is the minimal set that (MS, (24 U2), U1 U (S2( follows the GIN condition.
F.9 PROOF OF COROLLARY 2
Proof. The proof of Corollary 2 is obvious. For a set of atomic units that do not overlap with each other and can be covered by atomic unit 24 |[4]]| ||||| is equivalent to the fact that each atomic unit in is part of U, and together they can form U.
F.10 PROOF OF THEOREM 4
Proof. In section 3.1, we show that the causal structure among atomic units is identifiable by The- orem 1 and Remark 1. In section 3.2, we show that the new atomic units can be discovered by clustering their pure children with the help of Theorem Remark and Corollary 1. section 3.3, we refine the discovered atomic units by Theorem 3 and Corollary 2.
The three sections are integrated into our iterative algorithm to discover the causal graph from the leaf to root nodes. For the possible problem with covered small atomic units during the iterative dis- covery process, we check and identify it through Proposition 2. Furthermore, at the end of discovery process, we check for multiple root atomic units by testing unconditional independence relation- ships. Therefore, the atomic units, their size, and the causal structure among them can be fully identified with our algorithm. It is obvious that if there variables within atomic units, the entire causal graph G is virtually identifiable.
direct causal relationships between
F.11 PROOF OF COROLLARY
Proof. Corollary 3 is similar to Theorem 4, but with stronger assumptions. If each latent variable has at least two pure variable children, each atomic unit we discovered will only contain one variable. Thus, we do not need to consider the problem that the discovered atomic units have overlapping variables. Similarly, we need to check whether there are multiple root atomic units at the end. Roughly speaking, with Theorem 1, Theorem 2, and Corollary 1, the entire causal graph G is fully identifiable. Furthermore, if there is no latent confounder, we need not consider the discovery of latent variables. The entire causal graph & is identifiable with only Proposition 1, and the result is the same as the typical LiNGAM discovery algorithm (Shimizu et al. 2006 2011
G MORE DETAILS ON SIMULATION EXPERIMENTS
G.1 DATA GENERATION PROCESS AND IMPLEMENTATION
According to Eq. we generated the causal strength b,, uniformly from [-2, -0.5] U [0.5, 2] and the non-Gaussian noise terms were generated from exponential distributions the second power.
24

---

Published as a conference paper at ICLR 2024
For BPC and HL Gaussian noise is used. HSIC-based independence tests Zhang et al. 2018 were used to test the GIN condition.
G.2 EVALUATION METRICS
We adapted the evaluation metrics from Xie et al. (2022) and Huang et al. (002 evaluate the results. They are:
a.) Correct ordering rate: the number of correctly inferred causal orderings divided by the total number inferred causal orderings.
b.) Error rate in latent variables: the absolute difference between the inferred number of latent variables and the number of latent variables the true structure divided by number of latent variables in the true structure.
c.) Fl-score:
precision recaal to measure the similarity between the inferred adjacency matrix and the true adjacency matrix.
precisionerecall
G.3 MORE DETAILS ON FI-SCORE
In this paper, adjacency matrix is square matrix whose each element represents whether or not the variables in the graph are connected by edges with direction. For example, Adjo(i,j) represents there is direct edge from ith point to Juh point, and Adjg(i.j) represents there is no direct edge from dsh point to jen point.
We used the Fl-score to calculate the percentage of similarity between estimated and ground-truth
true positive adjacency matrices. To calculate the Fl-score, we first calculate the precision total best positive that represents the number of correct inferred edges
number of total inferred edges, and the recall
true positive true positive that represents the number of correct inferred edges over number of total ground- truth edges. F1-score = precislon+recal)
precisiou-recall which combines the precision and recall of the adjacency matrices by taking their harmonic mean, and can better represent the structural recovery rate.
In practice, the latent variable indices in the estimated graphs may not match those in the real graphs. To remove this ambiguity, similar to Huang et al. (2022), permuted the latent variable indices in the estimated graphs and used the one that has the minimal difference from the true graph. In addition, if the estimated number of latent variables is smaller than the true number of latent vari- ables, we add extra latent variables that do not have edges with others to G. If the estimated number of latent variables is larger than the true number of latent variables, we find subset of the latent variables in G that best matches the true one.
G.4 MORE RESULTS OF SIMULATIOON EXPERIMENTS
Here, evaluate the running time for four simulation cases. Each case is executed ten times, and the results are averaged. The summarized results are reported the Table
Table 4: The averaged running times for various cases with different sample sizes.
Case
Case 2
Case
Case 4
5k
10k
50k
5k
10k
50k
5k
10k
50k
5k
10k
50k
Time (s)
8
10
18
25
26
47
18
20
42
2026
2164
3132
To evaluate the performance of our algorithm when some noise is Gaussian-distributed, we modified the first two cases the simulation experiment. In Case 1, we generate standard Gaussian noise for X₂ and X₃. In Case 2, generate standard Gaussian noise for X₂ and XG. Each case is executed ten times, and the results are averaged. The summarized results are reported in the Table Although some of the noise is Gaussian-distributed, our method still recovers the true structures.
25

---

Published as a conference paper at ICLR 2024
Table 5: The performance of our method on causal structure graphs in the presence of Gaussian- distributed noise.
Case
Case 10k
5k
10k
50k
5k
50k
Correct Ordering Rate f
0.93
1.0
0.94
0.91
0.95
0.95
Error Rate in Latent Variables
0.0
0.0
0.0
0.20
0.15
0.10
Fl-score f
0.95
0.97
0.95
0.91
0.93
0.96
H MORE DETAILS ON THE REAL-WORLD DATA EXPERIMENT
The Holzinger and Swineford (1939) dataset consists of mental ability test scores of seventh- and eighth- -iaade children from two different schools (Pasteur and Grant-Whiter In the original dataset, there are scores for 26 tests. However, a smaller subset with 9 variables is more widely used in the literature, for example, in Jöreskog (1969). This dataset can be retrieved from R package lavaan (Rosseel 2012). The variables used our paper are given in Table which can be broadly catego- rized into three dimensions: Visual, Textual, and Speeded.
Table 6: The details of 9 variables in 'Holzinger & Swineford 1939' dataset.
Visual perception test from Spearman VPT Part I
Visual
Cubes, Simplification of Brighams Spatial Relations Test
Lozenges from Thorniie--Shape flipped over then identify target
Word Meaning Test
Textual
Sentence Completion Test
Paragraph Comprehension Test
Speeded discrimation of straight and curved caps
Speeded
Speeded counting of dots in shapes
Speeded addition test
The second-order factor analysis model dataset a built-in dataset of the Mplus software (Muthén & Muthén 2017). The ground truth is the same as in Figure IO).). Each set of three measured variables has a corresponding first-order latent indicator, all of which are influenced by second- order latent indicator. A detailed explanation of the dataset and model can be found in http: 7/ www. stwtmodel com/ HTML___MGGG http/chapttrtt r08 htm
Anstedl
Visc
compltese
Vi borage
To: crmpetetee
(a)
(b)
Figure 10: The outputs on (a) 'Holzinger & Swineford 1939' dataset and (b) Second-order factor analysis dataset. The nodes in circles are the latent indicators discovered from measured variables.
NOTATIONS AND TERMS
26

---

Published as a conference paper at ICLR 2024
Table 7: More explanations Notions and Terms.
Natation
Description
Initially
X
measured variable. varisble.
First paragraph of Section 2.1
First paragraph Scetion
A variable, which either measured or lntent.
First paragraph Section 2.1
Boldfaced letter; set of variables, each of which is either measured latent.
First paragraph of Section 2.1 Definition
Script letter, stomic unit, whose definition Definition 3. Blackhrard bold letter; A set of atomic units.
U. Y
Theorem
(eg. U.
number variables set The
U).
Delinition
(e.g. U)
The number of stomic units set (J).
Algorithm 2
Pa(a) V.1()
(V.
First paragraph Section 2.1
Pure atomic unit child
Each pare child itself an atomic unit.
Delinition
Surrogate variable of (l1)
Each descendant surregatc variable 14.
DefinitionS
measured surrogate variable set a/
DefinitionS
The discovered 'atomic unit' during phase I1, which can be fully decomposed units daring III.
Decomposable 'atomic unit'
several small
First paragraph Section 3.3
27


Reviews:
[{"review_id": "tzvQXcejXx", "reviewer": "Reviewer_BTCR", "summary": "This paper addresses the challenging issue of causal discovery in the presence of latent variables. It considers a general scenario in which both measured and latent variables collectively form a partially observed causally sufficient linear system, allowing latent variables to be situated anywhere within the causal structure. The paper establishes a theoretical foundation, demonstrating that with the application of high-order statistics, the causal graph can be (almost) fully identified. This identification is achieved under the condition that each latent set contains a sufficient number of pure children, whether they are latent or measured variables. Importantly, this extends beyond LiNGAM, a model without latent variables.\n\nExpanding on the identification theorem, the paper introduces a systematic algorithm for identifying the causal graph. This algorithm involves three iteratively executed phases that sequentially identify latent variables and infer causal relationships among both latent and measured variables. Experimental results validate the effectiveness of the proposed method in accurately recovering the causal structure, even when latent variables are influenced by measured variables.", "questions": "1. The decomposition of atomic units among latent variables is not unique, correct? If so, how can this be proven? If not, could this potentially impact the final results?\n\n2. What is the computational time required for this algorithm?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "They have introduced an algorithm that extends the LiNGAM algorithm to accommodate latent confounder conditions. Moreover, they do not impose any constraints on the presence or positioning of latent variables. Additionally, their algorithm has the capability to handle overlapping variables within the discovered latent sets.\n\nClarity: The paper is well-organized, with examples that effectively demonstrate how the algorithm functions.", "weaknesses": "The paper  appears to have no discernible weaknesses. It seems to be well-structured and comprehensive, with ample supporting materials in the appendix. The methodology and presentation seem robust.\n\nGiven that I am not an expert in this domain, I might leave the 'weaknesses' section blank for the time being and await feedback from other reviewers during the rebuttal phase.", "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": "chtcuk3gGk", "reviewer": "Reviewer_e967", "summary": "In the paper, the authors suggest a general version of LiNGAM, called PO-LiNGAM, where the existence of latent variables is permitted. While previous Linear non-Gaussian variants assume either no-latent variable, specific position or the number of latent variables , the proposed method relaxes such assumptions. When reconstructing a causal graph, the authors use a set of variables called the atomic unit, which represents the basic building block of casual structures. The PO-LiNGAM identification procedure consists of three step: (Phase 1) : Identify a leaf node and its parents; (Phase 2): Discover atomic units; and (Phase 3) : Refine the atomic units. Discovering relationships between atomic units is based on theorems under GIN (Generalized Independent Noise) condition which is an existing graphical condition for identifying a latent hierarchical structure.", "questions": "there is a minor typo: In Remark 1, 2nd sentence, we remove them form → we remove them from", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "In order to alleviate the strong assumptions of existing linear non-gaussian models, the authors cluster the variables into atomic units and obtain the information of latent variables from their measured descendants, called the measurement surrogate variable set. In other words, the authors establish the theorems, which view the existing GIN condition from the perspective of the atomic unit. This approach actively utilizes linear transitivity to infer latent variables. The author clearly describes the entire process of the method, and helps the reader's understanding by showing various examples. A sufficient amount of experiments demonstrates the validity of the paper.", "weaknesses": "The contribution of the model PO-LiNGAM is that it is free from assumptions about latent variables compared to existing models. However, for the algorithm to work properly, each atomic unit must have a sufficient number of pure atomic unit children. It is difficult to say that this is not a strong condition. The authors are aware of this issue and presented relaxing this as future work. One thing to add is that the only explanation of notations in the paper is provided through table 1 in figure 1. It is difficult to clearly understand the notations just from the table. For example, in definition 3, the term 'pure atomic unit child' is used for the first time. However, no clear explanation for this term is provided. It would be better if more specific notation explanations are added.", "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": "bK0pVfombS", "reviewer": "Reviewer_53sg", "summary": "The problem of causal structure learning with latent confounders is considered, with linearity and non-Gaussianity assumptions, and an additional assumption relating to notions of atomic units and their pure children in the graph. A completeness theorem is given showing structures can be learned up to atomic units and experiments on both generated and real data are done.", "questions": "Can the authors give real examples of when the assumptions relating to atomic units (PO-LiNGAM identifiability condition, including part b) would be reasonable to assume, and when they wouldn't? This would help me get a better grasp of the significance. As it stands we have these assumptions that are clearly stated but I don't know when they can really be made.\n\nMinor comments:\n- Abstract: \"fragile\" -> \"sensitive\"", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The work is well-situated within the causal structure learning literature, where various classes of assumptions are studied. In this context the additional graphical assumptions that they consider are novel and interesting. As far as I can tell, the results are sound and the experimental results are demonstrative.", "weaknesses": "The presentation is somewhat dense. See questions below.", "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": "i1tWod0loP", "reviewer": "Reviewer_XS6k", "summary": "The paper proposed a new causal discovery method for partially observed linear non-Gaussian acyclic model where the structure of observed and latent variables can be quite general. Their algorithm is an iterative one with each iteration consisting of three phases: identifying leafs, identifying atomic units, and refining atomic units. They establish the identifiability of their method under two conditions: (a) any latent variable is in at least one atomic unit and (b) the non-overlapping parts of two overlapping atomic units do not influence each other.", "questions": "Q1: How to understand the second bullet point of Definition 3? Does \"not partially or fully covered\" simply mean intersection is empty? \nQ2: Can the authors summarize how their identifiability conditions in relation to existing identifiable conditions for similar models?\nQ3: How does condition (a) imply every latent variable must have measured variables as its descendants? \nQ4: Definition 5 is a little hard to understand. What is the definition of surrogate variable? How to understand the terms \"can be\" and \"can have\" in the definitions? And is the last sentence an assumption? What do you mean by non-redundant set? \nQ5: In the last sentence of the first paragraph in Section 3.3, \"decomposable atomic units\" are not atomic units by definition, right? How \"decomposable atomic units\" arise from Phases I and II?  \nQ6: Section 3.4 assume oracle independence test I assume?\nQ7: Corollary 3: what \"parts\" of Phase I&II need to be specified. Additionally, do the authors mean \"no latent variables\" instead of \"no latent confounders\" in the last sentence of the corollary?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1. The causal structure among latent and measured variables are quite general\n2. Despite the generality, the causal graph can be identifiable when the two identifiable conditions are met.", "weaknesses": "The main weakness I find is the clarity of the writing, which hinders my ability to fully understand the method (hence the current rating). There are a number of places that need to be clarified. Please see my questions below. \n\nOne minor weaknesses: the authors used V, boldfaced V, and script V, which can be somewhat hard to read especially the latter two both denote sets. Use a different letter may help. It is particularly confusing in the first line of Definition 3 where script V and boldfaced V are used.", "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)