Latent Hierarchical Causal Structure Discovery with Rank Constraints
Authors: Biwei Huang
Charles Low
Feng Xie
Clark Glymour
Kun Zhang
Venue: NeurIPS 2022 Accept (2022)
Keywords: Latent hierarchical causal structure identification
Rank deficiency constraint

Abstract: Most causal discovery procedures assume that there are no latent confounders in the system, which is often violated in real-world problems. In this paper, we consider a challenging scenario for causal structure identification, where some variables are latent and they may form a hierarchical graph structure to generate the measured variables; the children of latent variables may still be latent and only leaf nodes are measured, and moreover, there can be multiple paths between every pair of variables (i.e., it is beyond tree structure). We propose an estimation procedure that can efficiently locate latent variables, determine their cardinalities, and identify the latent hierarchical structure, by leveraging rank deficiency constraints over the measured variables. We show that the proposed algorithm can find the correct Markov equivalence class of the whole graph asymptotically under proper restrictions on the graph structure and with linear causal relations.

Latent Hierarchical Causal Structure Discovery with Rank Constraints
Biwei Huang Charles Low +1 Feng Xie Clark Glymour', Kun Zhang
Carnegie Mellon University Mohamed bin Zayed University of Artificial Intelligence
Beijing Technology and Business University, China (bwei. huang, charleslow88, xiefeng009] com, cg09@andrew. cmu. edu, kunz10cmu. edu
Abstract
Most causal discovery procedures assume that there latent confounders in the system, which is often violated in real-world problems. In this paper, we consider a challenging scenario for causal structure identification, where some variables are latent and they form a hierarchical graph structure to generate the measured variables; the children of latent variables may still be latent and only leaf nodes are measured, and moreover, there can be multiple paths between every pair of variables (i.e., it beyond tree structure). We propose an estimation proce- dure that can efficiently locate latent variables, determine their cardinalities, and identify the latent hierarchical structure, by leveraging rank deficiency constraints over the measured variables. We show that the proposed algorithm can find the correct Markov equivalence class of the whole graph asymptotically under proper restrictions on the graph structure.
Introduction
In many cases, the common assumption in causal discovery algorithms-no latent manfounders-may not hold. For example, in complex systems, it is usually hard to enumerate and measure all task- related variables, so there may exist latent variables that influence multiple measured variables, the ignorance of which may introduce spurious correlations among measured variables. Much effort has been made handle the confounding problem in causal structure learning. One research line considers the causal structure over measured variables, including FCI and its variants (Spirtes) et al. 2000 Pearl 2000 Colombo et al., 2012 Akbari al. 202T], matrix decomposition-
approaches
Chandrasekaran et al. 2011 2012 Frot et al. 2019]. and over-complete ICA-based
ones (Hoyer et al. 2008
Salehkaleybar et al.) 2020
Another line focuses on identifying the causal structure among latent variables, including Tetrad condition-based approaches [Silva al. 2006 Kummerfeld and Ramsey 2016], high-order moments-
based ones [Shimizu et al.] 2009 Cai et al. 2019, Xie et al.] 2020 Adams et al., 2021 Chen
et al. 2022 matrix decomposition- based approach Anandkumar al. [2013]. copula model-based
approach Cui et al.) 2018), mixture oracles based approach [Kivaa et al. 202T]. and multiple
domains- based approach [Zng al. 202T]. Moreover, regarding the scenario of latent hierarchical
structures, previous work along this line assumes tree structure [Pearl] 1988, Zhang [004] Choi
Drton et al. 2017], where there one and only one undirected path between every pair of variables. This assumption is rather restrictive and the structure in real-world problems could be more complex-beyond tree.
al. 2011 I
In this paper, we consider more challenging scenario where latent causal variables form a hierarchical graph structure to generate measured variables the children of latent variables may still be latent
"These authors contributed equally to this work.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

X1
X10
Pa: Parents
X
X11
PCh: Pure children
X,
X
X12
PDe: Pure descendants
15
X5
X1
Gp:
Grandparents
X3
X9
Sib: Siblings
X2
X1
M: Measured
(h)
pure descendants
Example hierarchical graphs that our method can handle, where X; are measured variables and L, are latent variables.
Figure I:
Table 1: Graphical
notations.
and only the leaf nodes are measured, and moreover, there can be multiple paths between every pair of variables (see the example hierarchical graphs in Figure D]. We aim to find out identifiability conditions of the hierarchical structure that are as mild as possible, and meanwhile, develop an efficient algorithm with theoretical guarantees to answer the following questions. (1) How can we locate latent parents for both measured and latent variables, as well as determining the cardinality of the latent parents, by only providing the leaf nodes? (2) How
identify the causal relationships among latent variables and those from latent variables to measured variables?
Interestingly, we can answer these questions by properly making use of rank deficiency constraints; finding and leveraging rank properties in specific ways enable us to identify the Markov equivalence class of the whole graph, under appropriate conditions. Our contribution is mainly two-fold:
We propose structure identification algorithm that can efficiently locate latent variables (in- cluding their cardinalities) and identify the latent hierarchical structure, by leveraging the rank deficiency.
We show that the proposed algorithm can find the correct graph asymptotically under mild restrictions of the graph structure. Roughly speaking, show that it is sufficient to have k + 1 pure children (which can be latent), as well as another + neighbors, to identify the latent variable set with size k (see the detailed conditions in Definition 4 and Condition
is worth mentioning that rank constraints have been used in previous methods Silva et al. 2006
Kummerfeld and Ramsey 2016]. but they assume that each latent variable has three measured ones as children and each measured variable has only one latent parent. There are also other methods for latent structure learning; for instance, Annnddumar al. 2013]. which uses matrix decomposition, needs 3k measured children, and the GIN- method [ie et al. 2020]. which makes use of high-order statistics, needs 2k measured children. However, all those developments require that every latent variable should have measured variables as children. Very recently, Xie et al. [222] proposes approach for latent hierarchical structure by leveraging the GIN condition under linear non non-Gaussian models, but it assumes that each variable has only one parent, where both figures in Figure do not satisfy.
This paper is organized as follows. In Section 2 we give formal definitions of the latent hierarchical causal model under investigation and give conditions that are essential to the identifiability of the graph structure. In Section 3 we propose an efficient algorithm that makes use of rank-deficiency constraints to identify the latent hierarchical structure. Moreover, we show theoretically in Section f that the proposed algorithm outputs the correct Markov equivalence class of the whole graph we empirically validate the proposed approach on synthetic data.
asymptotically. In Section 5
Notations for graphical representations that are used in the paper are provided in Table
2 Latent Hierarchical Causal Model
In this paper, we focus on latent hierarchical causal model with graph structure G, where both measured variables Xg = [X,,... X.n) and latent variables Lg (L.,.... ......,,, Ln) are generated by their latent parents in directed acyclic graph (DAG) with linear relationships:
(1) where bij and Cą are the causal strength from L; to X; and from La to Lj. respectively, and Ex, and EL, are noise terms that are independent of each other. Without loss of generality, we assume that all variables in Xg and Lg have zero mean.
Xi- = Et,, bijL, + Ex,, L, EIIEPOLL) C,La + +1,
Below, we first give the general definition of a linear latent hierarchical graphical model in Definition U Then we give more detailed conditions on the graph structure (Definitions g1 that are essential to formalize the identifiability condition of the latent hierarchical structure.

---

Definition 1 (Linear Latent Hierarchical (L²H) Model), A graphical model, with its graph G (Vg. Eg), a linear latent hierarchical model if:
1. Vg =xgl U.g. where Xg is the set of measured variables and Lg is the set of latent variables,
2. there is at least undirected path between every pair of variables, and
3. each variable in Ng and Lg are generated by the structural equation models in Eq.
Generally, without further constraints, the causal structure of the L.HH model hard to be identified. It has been shown that if the underlying graph structure satisfies a tree [Pearl 1988). then the structure identifiable. However, this structural constraint may be too strong to hold in many real-world problems. In this paper, we give sufficient conditions that are much milder than previous ones, as well as an efficient search algorithm, for the identifiability of the causal structure.
We now give the corresponding definitions, including pure children, pure descendants, and effective cardinality, that will be used in the identifiability condition, together with illustrative examples.
Definition 2 (Pure Children). Variables V are pure children of set of latent variables L in graph G. if Pag(V) V) L and V n L = That is, have no other parents than L. We denote the pure children of L by PL).
Accordingly, Pure Descendants of a set of latent variables are defined as all recursive pure children of L (including PChg(L), PChg(PChg((I)) etc.). denoted by PDeg(L). Furthermore, measured variables that are pure descendent of L are called Measured Pure Descendants, denoted by Mg(L).
Example 1. In Figure I(a] the pure children of (Lz, Lz) are (Lo. Lio., its pure descendants are XI. ... .ii). and its measured pure descendants are (Xi,... Xui).
Lio. (L..,..
Definition 3 (Effective Cardinality). For a set of latent variables L, denote by C the largest subset of (L) such that there is no subset C' S C satisfying [C') > (Cag(C')) and (aag(C)) [L]. Then, the effective cardinality L''s pure children is (C).
In the case when L and its pure children are fully connected, the effective cardinality just the cardinality of the pure children of L. However, for Figure [[a]] the effective cardinality of the pure children of (L7, Ls) is 3, because here the largest subset that satisfies the condition is (Xs. Xs, X7).
We further define latent atomic cover that constrains the number of pure children and neighbours for latent variables, which are essential for structural identifiability.
Definition 4 (Latent Atomic Cover). Let I. (I.,.... .......... I&) be a set of latent variables in graph G. with IL| = k. We say that L is a latent atomic cover if the following conditions are met:
1. there exists subset of pure children C' C (C) with effective cardinality 2 k
2. there exists a neighbour set B s.f. B C' 0 and [B| k 1;
3. there does not exist a partition of = L, U L2, so that both L,, L2 satisfy conditions I and 2 and
(L)) U PChg(L2))) = PCh)
Example 2. In Figure [[a] L = (L2, is a latent atomic cover with k 2, because (1) there exists
a subset of pure children C' = (Lo, L7, Ls) with effective cardinality 3 = k 1, (2) there exists neighbor set B- LL, Lioh, B C 0 and B = 3 = k + 1, and (3) neither (Lz) or (Lg)
satisfies the above two conditions.
We now give the conditions for structural identifiability from measured variables Xg alone, including those on the structural constraints (Condition) D and rank faithfulness assumption (Condition 2b
Condition 1 (Irreducible Linear Latent Hierarchical (IL'H) Graph). An H graph G is an IL'H graph if
every latent variable L L in G belongs to at least one latent atomic cover,
for any pair of latent atomic covers (I,,, Lg), if PDeg(Ls) PDeg(La) # 0, then either (a)
LA c LL or (b) LA PDeg(Lg) or (c) Lg LA (d) Lg PDeg(Ls), and
for any three latent atomic covers LA, LR, Lc, if the causal structure satisfies LA - LB - Le or La < La Lc, and [L k, then Lp has 2k neighbors, except for La, Lc and the parents in
the v structare where Lg is a collider.
3

---

Next, we give the faithfulness assumption, which holds for generic covariance matrices consistent with G [Spirtes 2013].
Condition 2 (Rank Faithfulness). A probability distribution P is rank faithfil to a DAG G if every rank constraint on a sub-covariance matrix that holds in P is entailed by every linear structural model with respect to G.
We will show in Section 4 that if the underlying latent hicrarchical graph satisfies IL'H graph and the rank faithfulness holds, then the location and cardinality of latent variables, and the causal structure among latent atomic covers and that from latent atomic covers to measured variables, are identifiable with appropriate search procedures. Below, let us first present the identification procedure.
3 Structure Identification with Rank-Deficiency Constraints
We propose an identification algorithm (Algorithm) I to identify the structure of IL'H graphs, by leveraging rank-deficiency constraints of measured variables. In particular, the algorithm includes three phases: finding causal clusters and assigning latent atomic covers in greedy manner ('find- CausalClusters") ", refining incorrect clusters and covers due to the greedy search ("refine and refining edges and finding v structures ("refineEdges").
Algorithm 1: Latent Hierarchical Causal Structure Discovery
Input Date from set of measured variables Xg
Output Markov equivalence class G'
// find clusters and assign latent covers greedily 2 G" = refineClusters (G"): // refine incorrect clusters and covers from greedy search
g CinuSeusaCluutters (Xg):
G = refineEdges (g)):
// refine some edges and find v structures
Before describing the identification algorithm, we first give a theorem that relates the graphical structure of an IL-H graph to the rank constraints over the covariance matrix of measured variables. Theorem 1 (Graphical Implication of Rank Constraints in Il.'H Graphs). Suppose G satisfies an I1.- graph. Under the rank faithfulness assumption, the rros-covariiace matrix Σx,Xa over measured variables XA and Xg in G (with [XAl. > r) has rank r, if and only if there exists subset of latent variables with [L] = such that L d-separates XA from XB, and there is no L' with [L'] < [L] that d-separates XA from Xx. That is,
rank(Ex,,x))== = min[[L]: I. d-separates from Xa).
xxxx(.)) 1, because Ls d-separates X2) from (X3. X4) For instance, in Figure ((a) with |oo = 1.
Rank Test. We test rank deficiency by leveraging canonical correlations [Andrrson] 1984]. Specif- ically, the number of non-zero canonical correlations between two random vectors is equal to the rank. Denote by o, the i-th canonical correlation coefficient between X, and Xg. Then under the null hypothesis that rank(Ex..x.) S r, the statistics -p + q + 3)/2) Σ max(p4) log(1 - a²) is approximately x2 distributed with (p- - r) - r) degrees of freedom, where p = 1X q= = [x,,, and is the sample size.
We further show that for any subset of latent variables in an IL graph, we can use the measured variables as surrogates to estimate the rank, as indicated in the following theorem.
Theorem (Measurement as a surrogate). Suppose
an I1.-H graph. Denote by A, S g two subsets of variables in G. with A n B = 9. Furthermore, denote by XA the set of measured variables that are d-separated by A from all other measures, and by Xg the set of measured variables that are d-separated by B from all other measures. Then rank(EA,B) rank((xx.x.).
A special case when Theorem 2 holds is that XA and X are the measured pure descendants of A and B, respectively. Note that Theorem is special case of Theorem 2.8 in Sullivant et al. (010]] when applied to H graphs. Different from the setting in Sullivant et al. (2010) where access to the full covariance matrix Σvg.Vo is assumed, we only have access to the covariance matrix Σx,.Xp over the measured variables Xg. which we will use to infer the causal structure over the entire graph G. For this reason, although we can infer the number of latent variables that d-separate any two sets of measured variables Xx, Xg, we cannot directly know the exact location of these variables in the graph. Fortunately, the structure constraints of the IL' 'H graph and Theorem will allow us to reconstruct the graph with certain search procedures, shown below.

---

3.1 Phase I: Finding Causal Clusters
We start to discover clusters in a recursive and greedy manner, by performing rank-deficiency over measured variables. We denote by S a set of active variables that is under investigation; S is set to Xg initially and will be updated to include latent atomic covers when rank deficiency is discovered. Below, first give the definition about set size and the definition of atomic rank-deficiency set, which will be used in Rule and Algorithm
tests
Definition 5 (Set Size). Suppose S a set. We denote by [S] the cardinality S: the number of elements S in for S; S. We denote by [|S]] the number of variables in S, where ||S]| = U, for S.
S: that is, |S] is
For example, suppose S = (111) Ls), (L9, Lio)). Then [S] = 4 and ||S|| = 6.
Definition 6 (Atomic Rank Denncieefcieecy Set). Given a graph G'. Denote by S S Vg an active set of variables that is under investigation. Let A S and B = S'A. Denote by XA = MM (A) and XB 3==Me MM (B) the measured pure descendants of A and B, respectively. (f) ΣA. is rank deficient, L..., rank(>A.B) min][]A[|-|[BB -[BII),, and (2) no proper subset of A is rank deficient, then A is called an atomic rank-deficient set, and ΣA can be estimated by Xx,
For example, in Figure I(a] suppose now we have the measured variables Xg under investigation, so the active variable set Xg. A [X,, X2) c S forms an atomic rank-deficiency set because the cross-covariance matrix of XA against all other measures has rank (i.e., rank deficient). According to Theorem D the rank deficiency occurs because the latent parent Lo of (X,, X2) d-separates them from all other measures. This naturally leads to the following rule that assigns latent atomic cover over the rank- rank-deficiency set:
Rule 1:
If is a rank-deficiency set with rank(Ex,,x;) k, then assign a latent atomic cover I. of size k as the parent of every variable A; E A.
Later in Phase II, we will show that Rule I may not correctly identify the latent atomic cover in some cases, and, accordingly, we will further provide efficient revision procedure in Phase II. At the current phase, we use Rule 1, together with certain search procedures, to identify the clusters and latent atomic covers. The detailed search procedure of Phase I is given in Algorithm 2 (findCausalChusters)) which tests for rank deficiency recursively to discover clusters of variables and their latent atomic clusters. The set of active variables S is set Xg initially (line 1) and will be updated as the search goes on (line 14). We start to identify the latent atomic cover with size k = 1 (line 1). We consider any subset of the latent atomic covers in S and replace them with their pure children, resulting in S (line 4). Then we draw subset of variables A C Š with cardinality least k+ + and conduct a rank deficiency test of A against S by estimating the rank of rank(Ex, (lines 6-7). Note that here XA and Xς are the measured pure descendants of A and B, respectively, in the currently learned graph. This step is repeated until all subsets are tested (lines 5-9). If rank deficiency is found, we merge the overlapping groups into cluster and add latent covers over the cluster (lines 10-14). We further reset = and resume the search (line 15). Otherwise, no latent cover is found, we increment k = k+ (line 17). This procedure is repeated until more clusters found. Finally, we connect the elements in S into a chain structure (line 19). Figure 2 iillustrates an example procedure of finding new clusters by
findCasaalllsttteeett the measured variables
Xg generated from the structure in Figure ((a)
3.2 Phase II: Refining Clusters
As we have mentioned above, the naive assignment of causal clusters Algorithm 2 (findCausal- Clusters) may not be correct in some cases. In this section, we provide a precise characterization of the cases where findCausalClusters incorrectly clusters variables and, accordingly, propose an efficient algorithm to correct such cases.
Take Figure ((a) as an example to illustrate the issue. By applying, findCassalCuusters to the measured variables Xg. at k = 2, we discovered that (Xg, X10, Xn1) form a cluster and then set 2-letent atomic cover (4, L3) over it (Figure ((b).. This is not correct, because Xy, X10. X11 actually belong to three different l-latent atomic covers, L,, L2, Ls. respectively. The incorrect clustering and covering are because when discovering the rank -effcieiyy set (X9, X10. X11), the latent covers (I4, Ls), (Ls, Lr) have not been identified yet. If (/a, Ls) had already been discovered, we would correctly find that (Xg, 14, L.) form llteet atomic cover, and the algorithm would proceed correctly thereafter, More FineraallyfinCCCuaallco
may set incorrect cluster for the rank-deficiee set (X,, X1o, X J. in
5

---

Algorithm 2: Phase I: findCausalClusters
Input :ata from set of measured variables Xg
Output:Grape G'
Active S Xg: k c- 1;
2 repeat
repeat
draw set of latent atomic covers L let (S)L) ((
repeat
draw set of test variables A C with ||A]] 2 k I, and let SA,A; k' - rank([x,Xx.) estimated by rank deficiency test;
if < k then rank deficiency found and keep track of this set A until subsets A exhausted:
10
if any groups with runk deficiency are found then
merge overlapping clusters; identify lowest rank K found; foreach discovered cluster of variables A with rank K do create latent cover L with cardinality K as parents of
14
S = (SIA))L
A = I; break;
16
until all subsets L exhausted;
if group with ronk deficiency is found then k = + 1;
18 until no more clusters are found;
19 for all S; E S, connect them into chain structure;
return G'
L
X1 Xs
Xg Ry 1oX X12 11
la
La Lاb10 (d) k= 2, 114,), Lg). Ls). (L, Loo]/o)) ML. Loll--
(a) [X _16)
1,
(b) k= S= ((Lo), (Lrt No.... Xiol.
(c) 1=1,S=
(e) Connect
(1,,,
(L2, Lul and
(L,, Ls).
Figure 2: An illustration of Algorithm 2 that discovers new clusters sequence (marked with gray circle) by applying findCausalChusters to the measured variables Xg generated from the structure in Figure [(a] Specifically, we first set
S, and we can find clusters in (a), and no further cluster can be found with = 1. Then we increase to 2 with the active set S = (L. (LT), X6. Xist and = S, and then we can find the clusters in (b). Then, the active set is = [IL,, Ls), I. (L., La). (L., Liol) and we set back = 1, and when S (1L., Ls). X Xu1) we find the cluster in (c). Note that when testing the rank over (4,, Lg) against other variables, we use their measured pure descendants in the currently estimated graph instead. The above procedure is repeated to further find the cluster in (d). Finally, when there connecting (Lg Lx) (L,, Lg) in (c).
active set is S [X..... .(oo and
enough variables for testing, connect the elements the active variable set:
the case when their parents L1. L2. LA split the graph into two or more disconnected graphs. This result formally stated in the following definition and theorem.
Definition (Bond Set). Consider a set of measured variables X C Xg. and minimal set of latent variables L Lg that d-separate X from all other measures X' == X. We say that X is a bond set if L also d-separates some partition XA C X C X' from one another.
From the previous example, we have seen that with the existence of bond sets, finddCaaaalClusterss may end up with incorrect clusters and covers. The following theorem shows that the presence of bond sets is the only reason for incorrect clusters and covers with findCausal
Theorem 3 (Correct Cluster Condition). Suppose G is an IL H graph with measured variables Xg. Consider the output G' from applying findCasalClusters over Xg. If none of the clusters G' is the bond set in G. then all latent atomic covers have been correctly identified.
However, without access to the true graph G. we are not able to identify which clusters formed from FmddCassaClusters are bond sets. Fortunately, the following properties of the clusters formed over bond sets provide way to remove bond sets in our discovered graph even without such knowledge, so that the clusters and latent covers can be correctly identified.

---

Theorem 4 (Correcting Clusters). Denote by G' the output from findCausalClusterss and by G the true graph. For a latent atomic cover L' in G' if the measured pure descendants of is a bond set in the true graph G, then there exist a set of siblings S of in G' set of children C of and a set of grandparents P of such that My. (S U C) forms a cluster that is not a bond set in G.
The above theorem shows that whenever forming a bond set, the siblings and grandparents of the latent cover are the key to correcting the incorrect clusters and covers. Specifically, we will remove such a cover and use its children to form new clusters with the siblings and grandparents (see details in Algorithm B and Theorem guarantees that these new clusters will not contain bond sets, and thus, providing correct clusters.
Example 3. In Figure 3(b) the formed cluster (Xg, X1o Xnd is the bond set in the true graph in Figure 3(a) and the covers { L.), (11)), and (Lg)) are not correct. Illustration of the algorithm for this example, including refining the incorrect clusters and covers, is given in Appendix A5.7.
X8
X1
X
X5
X11
X
X5
X11
X
X
(a) Original graph
(b) Output from findCausalClusters
Figure 3: An example where findCausalClusters fails.
Furthermore, with Theorem give the following rule for correcting the clusters and covers.
Rule 2: For each discovered latent atomic cover I., let = (T.) ihg (L) Chg and apply findCausalClustee Clusters to V to refine the clusters.
Before introducing the detailed refining algorithm refineClusters based on Rule 2, we first introduce an operator RakeRoot that will be used in the algorithm, which will not change the rank deficiency constraints (Lemma 5).
Definition 8 (makeRoor). Give graph G' and latent atomic cover L in G'. A makeRoot operator of L,, denoted by makeRooi(L),, reorients all outgoing edges of L to L, such that L is a root variable.
Lemma 5 (Rank Invariance). Denote by G' the output from IndCausalClusters and by L a latent atomic cover in G'. Then all rank constraints, that are possible to be executed by findCassalllusters prescribed by G", before and after the operator makeRoor(L)) are identical.
Algorithm 3 introduces the procedure of refining clusters based on Rule 2. Starting with the output G' from FindCausalClusterss we proceed in breadth-fin first search from the root variable (lines 1-3, 5). Because the root is trivially not over a bond set, Theorem guarantees that for each child of the root, we will form new clusters that not over bond sets. For each cover L, if it has only one child, will recursively consider the children of its child instead, since if L is over a bond set then its single child will also be. We add the first set of children into the search set V (line 4). We construct the search set (line 6) and remove the covers we are refining (lines 7-8). Finally, we make I, the root (line 8) and conduct the search to form new clusters (line 9). The algorithm ends after refining every latent cover in G'. With this refining procedure, we will derive the correct latent covers for the graph in Figure
3.3 Phase III: Refining Edges
With findCausalClusteers and relineClusters, the output G' correctly identifies the latent variables. Moreover, G' correctly identifies the following d-separation: for every E L.g,, its parents Pag (L.) d-separates I. and its descendants from the ancestors of Pag:(L), and thus, there cannot be any edges from each L to any of its ancestors beyond its own parents. However, G' may still have incorrect edges locally. Specifically, each time we create atomic cover L in findCansalClasters, the implicit assumption is that each of its children is conditionally independent of the other children given the parents L. However, this assumption is not necessarily true, as (i) the children of L may be directly connected to one another, and (ii) L may only be directly connected to a subset of its children. In other words, previous steps did not consider condition independence relationships across clusters. Hence, we need a further step to correct edges over each L and its children.
For example, consider the true graph in Figure 4(a) which ends up with the graph in Figure 4(b) with the first two phases. However, note that the first two phases did not consider the d-separation between L2 and Lg. and thus the edges among Li Ly Lg L may not be correct, including the v structure. In
7

---

Algorithm 3: Phase II: refineClusters
Input :Ouiput graph G' from Phase I
Output:Refing graph G'
refineClusters (G"):
Let Q be an empty queue; Qoonuucut(Phgg..ooo ));
repeat
L Q.dequeueO;
while Chg (L) a single atomic cover do remove Cha (L. and add (Ch (L)) as children of L for each atomic cover C ε Che (I.) do Q.enqueue(C);
V - Gpo(L) i. (L) Chg((I); (L);
// variables for finding new clusters // atomic covers to be removed
R - LU Pag(L):
G m. (L): remove R and all adjoining edges from G':
G" findCausal Clusters((eeeeeee update G' with new clusters from G": // find new clusters
10 until Q is empty:
return
particular, in the true graph, L d-separates L2 from L3. while (L,, does not d-separate La from L3, but these d-separations are not reflected in the discovered G' in the first two phases. Thus, we need to refine the edges. To this end, we first set Li L,, L' and L L2 to be fully connected, and consider testing A = {L, X1) against B- = (L1z X2l. where we partition the children of L into two sets and put them in A and B, respectively. By doing so, we force L in G' to be in the separating set. Since rank((_n.s)) = 1, it implies that no other variable is in the separating set, and therefore we can conclude that L d-separates 12 from Lig. This principle is characterized in the following lemma.
Lemma (Cross-Cover Test). Given a set of variables S, consider two latent atomic covers LA L S, and a potential separating set C [Lc,] I S,,LA, For each Lc,, consider C2. C PCh(T.)) with CA, C. 0 and C₁2 C 0, and denote the cardinality kn == min([ IC k == mil IC respectively. Then there is no edge between LA and Lg if and only if there exists separating sel C such that rank(E < minn[[a]+ -A Σ, k(),
where A (LA, C2. C2 and B- (Lg, CT. Cg..... .... In this case, we say that C satisfies the cross-cover test of LA against Lg.
|La++
Note that in order to find rank deficiency when performing the cross-cover test, Lc; needs to satisfy the third condition in Condition [
Based on Lemma f we use the following rule to refine the edges.
Rule 3: For a pair of latent covers (La, LR), let A < [L., C₁, C2 Cs....) and < (L., C Cf. If there exists such A.B such that rankg (E)rs) is rank deficient, then remove all edges between LA, Lg in G'.
Furthermore, with Rule 3, Algorithm 4a (CrossCoverTest) in Appendix A gives the procedure of refining the edges over set of latent variables S to correct the causal skeleton.
Furthermore, we are going to identify the v structures among latent atomic covers. In the output G' from phase II, for any L' with child C; and parent P', it is not possible to have collider - L P' in the ground-truth graph, because in this case the cluster would not have been rank deficient. Therefore, the only structures in the graph are amongst the variables in L' U PChg (L'), and similar to crossCoverTess, we only need to test for v structures locally. Continue to consider the example in Figure 9 The edge between L3 and LA missing because the rank over (LS. and (2) is 1, implying that L; d-separates Lद from L,, as is done in crossCoverTest. Now, since L4 - LL, forms an unshielded triplet, we want to test if collider exists L'P We find that the rank over A (Z.5, Lg X1) and B- = (LG,, X2) is 2 > 1, and the rank over A = [L1 X1) ) and B = [L4 44, X2) 2>> > 1, so L3 - L4 t L. For general cases, the rule for finding structures are formulated in the following lemma and Algorithm 4b (finColliders) in Appendix A.
Lemma 7 (V-Structure Test). For any unshielded triangle L, Lc - L.g, let A,B be the set of variables in Lemma 6 such that Σn. was rank deficient. Let k rank(Exas). kn = ran and k2 = rank(Euu....)) Then, LA- - LB + Lc if and only if < min(k),k2)
As mentioned above, we only need to perform cross-cover test and v-structure test locally in the estimated graph G', Algorithm (Phase III: refineEdges) combines the search procedure of the two components together with the output G' from reffinelusste Clusters as the input. Specifically, for each latent cover L. in G', we only need to consider testing for edges amongst I.' and its children C Cho (I.'). Thus, we perform depth- first traversal of the output graph G' starting from Root(G") (lines 1-3), and
8

---

apply the cross-cover test at each L to refine the skeleton of G' (lines 4-7, 11) and the collider test to identify the structures (lines 10, 11). After determining v-structures, we can find more directions by applying Meek's s rule (line 12), analogous to that in the PC algorithm (Spirtes et al. 2000
Algorithm 4: Phase III: refineFdges
Input :Learned graph G' from phase II Output:Mann Markov equivalence class G"
refineEdges (G"):
foreach latent atomic cover in G' do
if L' does not have latent children then return G' foreach latent child C; of L' do G' - refinneEdess C):; if C == PChg:((:) (I:)) is single latent cover then S - I. UU (C): else - G" + makeRoot (I.' and remove all edges amongst in G" Edgeset & - crossCoverTestie G"): if no conditional independencies found then return G'; else
// temp graph
10
Collider set findColliders(S, &,g"); in G', remove all edges amongst and use & C to connect variables in S; apply Meek's rule to G":
11
12
13 convert g' Markov equivalence class;
14
return G'
X
X2
X5X4
X,X4
X5X
(a) An IL graph with v struc- ture.
(b) Possible Output from Phase
(c) Output from phase III.
II.
Figure 4: Illustrations refineLdgees.
4 Theoretical Results
In this section, we show the correctness of the algorithms proposed in Section 3 In particular, by making use of the rank constraints of only the measured variables, the proposed algorithms output the correct Markov equivalence class of the IL'H graph asymptotically, under the Sinimal-graph operator and skeleton operator, with their definitions given below.
Definition 9 (Markov Equivalence Class of IL'H graphs). Two IL' graphs GI and G2 are in the same Markov equivalence class, denoted by GI x G2. if and only (1) they have the same set of variables (both measured and latent variables), (2) have the same causal skeleton, and (3) have the same V-structures L; L1 c Lig. where L,, L Lg represent latent atomic covers.
Definition 10 (Minimal-Graan Graph Operator). Suppose G an IL'H graph. For every latent atomic cover I, in G. merge I. to its parents P if the following conditions hold: (1) L. is the pure children of P. (2) [L] = IPI, and (3) the pure children of form one latent atomic cover, or the siblings of I, form one latent atomic cover. We call such operator the minimal graph operator and denote it by O OminlG).
Definition 11 (Skeleton Operator). Suppose G is an HL'H graph. skeleton operator of denoted by O,GG) is defined as follows: for any latent atomic cover L., draw edge from to CR PC)g(L.), Il and c are not directly connected in G.
Note that the minimal-grape operator and the skeleton operator will not change the rank constraints, or in other words, graphs before and after applying the operators are indistinguishable with rank constraints. This result is shown in the following lemma.
Lemma 8. Suppose G is an 11.2 H graph. The rank constraints are invariant with the minimal-grape operator and the skeleton operator; that is, G and O OOenettonOmmmm are rank equivalent.
These two operators have already been achieved in Algorithm so the output of the algorithm is the rank-equivalent graph with the minimal number of latent atomic covers.
D
We next proceed to show that phases I-III will output a graph G' such that G' will be the same Markov equivalence class as O (G)),, denoted by G' x G. We have already shown earlier in

---

Theorem that findCausalClusterss gives correct latent covers when there is no bond set. Furthermore, Theorem shows that even in the presence of bond sets, Phase relsteClusters is able refine clusters into those without bond sets. Therefore, Phase I-1I can correctly identify the latent atomic covers of mG), which is given the following theorem.
Theorem 9 (Identifiability of Latent Variables). Suppose G is an H1.2H graph with measured variables Xg. Phases 1-11 in Algorithm 7 ovvr Xg can asymptotically identify the latent atomic covers of min (G), with only the first two conditions in Condition 1.
Moreover, Phase III refineEdges further guarantees correct skeletons and v structures. Therefore, the following theorem shows that Algorithm I which includes Phases I-III, can asymptotically identify the Markov equivalence class, up to the skeleton operator and the minimal-graph operator.
Theorem 10 (Identifiability of Causal Graph), Suppose G is IL'H graph with measured variables Xg. Algorithm D including Phases I-I1I, over Xg can asymptotically identify the Markov equivalence class of min (G))
5 Experimental Results
We applied the proposed algorithm to synthetic data to learn the latent hierarchical causal graph. Specifically, we considered different types of latent graphs and different sample sizes. The causal strength was generated uniformly from [-5, -0.5] [0.5, 5], and the noise term was randomly chosen from normal distribution with noise variance uniformly sampled from [1.5]. To the best of our knowledge, this is the first algorithm that can identify such general latent hierarchical structures, so to fairly compare with other methods, besides general I graphs, we also considered tree structures and measurement models. We compared the proposed method with tree-based method-C Sooold-Chowwaaa Recursive Grouping (CLRG) [Choi et al., 201T]. as well as measurement-mmone sotoreemmentmodll-baeeeeee methods, including FOFC [Kummerfeld and Ramsey 2016 and GIN (Xie et al. 2020
Table gives the estimation results evaluated on three types of latent graphs: IL--H graphs, tree structures, and measurement models. The performance is measured by the percentage of correctly identified causal clusters over only measured variables. Our method gives the best results on all types of graphs, indicating that it can handle not only the tree-based and measurement-basse but also the latent hierarchical structure. The CLRG algorithm does not perform well on tree-based structure because the metric is rather strict-even a single misclustered variable outputs an error. Complete experimental settings and more results, including performance measured by other metrics and the case when the noise terms are uniformly distributed, are given in Appendix B.
structures,
Table 1: Performance (mean (standard deviation)) on learning different types of latent graphs.
IL'H
Tree
Measurement model
'Smmle
Ours
CLRG
FOFC
GIN
Ours
CLRG
FORC
GIN
Ours
CLRG
FOFC
GIN
2k
0.70 (0.22)
0
0.12
0.35
0.89 (0.12)
0
0.38
0.13
0.92 (0.08)
0
0.38
0.3
0.83 (0,
0.17
0.40
(0.00.)0
0.75
0.23
(0.00.00))
0
0.65
0.7
10k
0,86 (0.13)
0.29
0.44
(0.00)
0.13
0.87
0.50
(0.00)
0
1.0
0.7
Conclusions and Future Work
In this paper, we formulated specific type of latent hierarchical causal model and proposed method to identify its graph by making use of rank deficiency constraints. Theoretically, we show that the proposed algorithm can find the correct Markov equivalence class of the whole graph asymptotically under mild restrictions of the graph structure. For more general graphs, only using the second-order statisties may result in rank equivalence class that contains multiple DAGs, how to further leverage high-order statistics to distinguish between causal graphs within the equivalence class will be our future work. Other future research directions include allowing nonlinear causal relationships and allowing measured variables to cause latent variables (existing techniques, e.g., Adams et al. (027 (qqiirss al. 2022]. may help to mitigate this issue).
Acknowledgement
BH would like to acknowledge the support of Apple Scholarship. Kun Zhang was partially supported by the National Institutes of Health (NIH) under Contract R01HL159805, by the CSveronvee Accelerator Track-D award #21 #2134901, by grant from Apple Inc., and by a grant from KDDI Research Inc. FX acknowledges the support by National Natural Science Foundation of China (NSFC 62006051).
10

---

References
Peter Spirtes, Clark N Glymour, and Richard Scheines. Causation, Prediction, and Search. MIT press, 2000.
Judea Pearl. Causality: Models, Reasoning, and Inference. Cambridge University Press, New York, NY, USA, 2000. ISBN 0-521-77362-8.
Diego Colombo, Marloes Maathuis, Markus Kalisch, and Thomas $ Richardson. Learning high- dimensional directed acyclic graphs with latent and selection variables. The Annals of Statistics, pages 294-321, 2012.
Sina Akbari, Ehsan Mokhtarian, AmirEmad Ghassami, and Negar Kiyavash. Recursive causal structure learning in the presence of latent variables and selection bias. In Advances in Neural Information Processing Systems, volume 34, pages 101 19-10130, 2021.
V. Chandrasekaran, S. Sanghavi, P. A. Parrilo, and A. S. Willsky. Rank-sparsity incoherence for matrix decomposition. SIAM Journal on Optimization, 2 21(2):572-596, 2011.
V. Chandrasckaran, P. A. Parrilo, and A. S. Willsky, Latent variable graphical model selection via convex optimization. Annals of Statistics, 40(4))1935-1188 2012.
Benjamin Frot, Preetam Nandy, and Marloes H Maathuis. Robust causal structure learning with some hidden variables. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 81 (3):459-487, 2019.
Patrik Hoyer, Shohei Shimizu, Antti J Kerminen, and Markus Palviainen. Estimation of causal effects using linear non-gaussian causal models with hidden variables. International Journal of Approximate Reasoning. 49(2):362-378 2008
Saber Salehkaleybar, AmirEmad Ghassami, Negar Kiyavash, and Kun Zhang. Learning linear non- gaussian causal models in the presence of latent variables. Journal of Machine Learning Research, 21(39):1-24, 2020.
Ricardo Silva, Richard Scheine, Clark Glymour, and Peter Spirtes. Learning the structure of linear latent variable models. Journal of Machine Learning Research, 191-2): 2006.
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, pages 1655-1664 ACM, 2016.
Shohei Shimizu, Patrik O Hoyer, and Aapo Hyvärinen. Estimation of linear non-gaussian acyclic models for latent factors. Neurocomputingg 72(7-9):2024-2027, 2009.
Ruichu Cai, Feng Xie, Clark Glymour, Zhifeng Hao, and Kun Zhang. Triad constraints for learning causal structure of latent variables. In Advances in Neural Information Processing Systems, pages 12863-12872, 2019.
Feng Xie, Ruichu Cai, Biwei Huang, Clark Glymour, Zhifeng Hao, and Kun Zhang. Generalized independent noise condition for estimating latent variable causal graphs. In Advances in Neural Information Processing Systems, pages 14891-14902, 2020.
Jeffrey Adams, Niels Hansen, and Kun Zhang. Identification of partially observed linear causal models: Graphical conditions for the non-gaussian and heterogeneous cases. Advances Neural Information Processing Systems, 34, 2021.
Zhengming Chen, Feng Xic, Jie Qiao. Zhifeng Hao, Kun Zhang, and Ruichu Cai. Identification of linear latent variable model with arbitrary distribution. In Proceedings 36th AAAI Conference Artificial Intelligence (AAAI), 2022.
Animashree Anandkumar, Daniel Hsu, Adel Javanmard, and Sham Kakade. Learning linear bayesian networks with latent variables. In International Conference on Machine Learning, pages 249-257, 2013.
11

---

Ruifei Cui, Perry Groot, Moritz Schauer, and Tom Heskes. Learning the causal structure of copula models with latent variables. In UAI. pages 188-197. AUAI Press, 2018
Bohdan Kivva, Goutham Rajendran, Pradeep Ravikumar, and Bryon Aragam. Learning latent causal graphs via mixture oracles. Advances in Neural Information Processing Systems, 34, 2021.
Yan Zeng, Shohei Shimizu, Ruichu Cai, Feng Xie, Michio Yamamoto, and Zhifeng Hao. Causal discovery with multi-domain lingam for latent factors. In LJCAL, pages 2097-2103, 2021.
Judea Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1988. ISBN 1558604790.
Nevin Zhang. Hierarchical latent class models for cluster analysis. The Journal of Machine Learning Research, 5:697-723, 2004.
Myung Jin Choi, Vincent Y.F. Tan, Animashree Anandkumar, and Alan S. Willsky. Learning latent tree graphical models. Journal of Machine Learning Research, 12(49):1771-1812, 2011. URL http://jmll
halllr.orgppaper//eee http//papers/l///hoollbbbbbb. http//hoollbbb.ttt.
Mathias Drton, Shaowei Lin, Luca Weihs, and Piotr Zwiernik. Marginal likelihood and model selection for gaussian latent tree and forest models. Bernoulli, 2202):100211233 2017.
F. Xie, B. Huang, Z. Chen, Y. He, Z. Geng, and K. Zhang. Identification of linear non-gaussian latent hierarchical structure. In JCML, 2022.
Peter Spirtes. Calculation of entailed rank constraints in partially non-linear and cyclic models. In Proceedings of the Twenty-Ninth Conference on Uncertainty in Artificial Intelligence, pages 606-615. AUAI Press, 2013.
T. W. Anderson. An Introduction to Multivariate Statistical Analysis. 2nd ed. John Wiley Sons, 1984.
Seth Sullivant, Kelli Talaska, and Jan Draisma. Trek separation for Gaussian graphical models. The Annals of Statistics, 38(3):1665 1685, 2010. doi: A0.126. URL https: //doi. 100 0
C. Squires, A. Yun, E. Nichani, R. Agrawal, and C. Uhler. Causal structure discovery between clusters of nodes induced by latent factors. In CLeaR, 2022.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] We proposed a method to identify latent hicrarchical causal graphs by making use of rank deficiency constraints. Theoretically, we show that the proposed algorithm can find the correct Markov equivalence class asymptotically for more general graph structures, compared to previous methods.
(b) Did you describe the limitations of your work? [Yes] See Section 6 on future work. One limitation is that here we only allowed linear models, and we will extend it to allow nonlinear causal relations as well. Another limitation is that here we did not consider direct causal edges among the measurement variables. This is because, for such cases, only using the second-ordes statistics may only identified to the rank equivalence class, which may contain multiple DAGs, so how to further leverage high-order statistics to distinguish between causal graphs within the equivalence class will be our future work.
(c) Did you discuss any potential negative societal impacts of your work? [No] We do not think there is any negative societal impact the current moment.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes] We have read the ethics review guidelines.
2. If you including theoretical results...
12

---

(a) Did you state the full set of assumptions of all theoretical results? [Yes] We clearly stated the assumptions Section 2.
(b) Did you include complete proofs of all theoretical results? [Yes] We gave complete proofs of all theoretical results in Appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material as a URL)? [Yes] We gave the detailed experimental setting in Appendix. Code will be made public.
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes] We specified all the details in Appendix.
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [Yes] See Section B in Appendix.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable
information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "xqHhA_ZFFt", "reviewer": "Reviewer_eq5G", "summary": "This paper proposes a new method to deal with causal discovery when latent confounds exist. The graph is assumed to be with hierarchical structure, and by incorporating the rank deficiency constraints, the method is able to learn the graph and some properties of the latent variables, which has been verified by experiments.\n", "questions": "1. How common do we meet the case that the causal structure is hierarchical？\n2. It seems that def 2 is not neccessary.\n3. I feel that even with phase 2, the rule 1 recovered graph may be incorrect since not all atomic covers are accessed. How to fix this problem?\n4. From lemma 6, how to guarantee that the colliders are all identified?", "limitations": "No obvious limitations.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1.\tThe paper is well formulated mathematically. Many definitions are clear and the theoretical analysis is sound.\n2.\tThere are many examples to ease the understanding of the readers on the main concept of the paper. \n\nWeaknesses:\n1.\tThe experimental results are slightly weak. It seems only very simple toy data are evaluated.\n2.\tThe efficiency of the method is not well studied. There are multiple phases of the method and the authors are better to show the computational aspects of the paper.\n", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "OXuqiaXzeAm", "reviewer": "Reviewer_548Y", "summary": "The authors present a method that under certain assumptions with respect to the graph structure, and an assumption of linear relationships between variables, guarantees identifiability of the Markov equivalent class of the hierarchical latent graph structure. The authors' method produce superior results to the nearest alternatives.", "questions": "Please see the section above for the questions presented to authors.", "limitations": "The authors briefly discuss the limitations of their work in the Conclusion section. Additional discussion might include the points raised above.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The authors present a method that under certain assumptions with respect to the graph structure and form of the relationships between variables, guarantees identifiability up to MEC for latent hierarchical models - the method presented is potentially of interest to conference audience as it constitutes an improvement over prior methods. \n\nWhat I was less clear on is in what scenarios would this method be useful for modeling observational data. When exactly would it be advantageous for a model selection to be conducted using this procedure? What would be the adventages compared to other methods for inferring latent structure. What is the extra adventage of having linear hierarchical latent variables? Or, do the authors consider this development as a potential foundation for other methods? Without these discussions, the method seems to be of interest to only a limited community of researchers.\n\nHow advantageous is the authors' method in terms of computational complexity compared to similar methods presented in the text? Are there any prohibitive trade-off's that come with the additional identifiability guarantees that the authors provide?\n\nLastly, I think the paper would benefit from improvements to its presentation. The authors present a lot of concepts (e.g. Defs 2,3,4) without any reference to their semantics with respect to the upcoming theoretical results. This leads the reader to do a lot of backtracking while examining the authors method. ", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "AxgPPdHtc-P", "reviewer": "Reviewer_ZSqv", "summary": "## Summary of paper:\n\nThis work deals with the task of causal discovery of linear additive models in the presense of latent (hidden) variables. Under various assumptions on the graph structure, this work proposes an algorithm to recover the Markov equivalence class of the underlying graph and they show that the recovered graph is asymptotically correct up to certain graph theoretic operators. Most prior works either assume the absence of latent variables (which almost always fails in real-life) or do not necessarily recover the causal structure among the latent variables. It's worth noting that few works have also attempted the latter difficult task of recovering the latent causal structure -- for the linear case, see [1], [2] and for the nonlinear case, see [3].\n\nThis work deals with the linear case. The basic strategy is to use rank constraints (which can be exploited because of the linearity assumption) to build the latent graph. Such approaches have been utilized before in other works, e.g. [4], [5]. The algorithm has 3 parts - (a) find \"atomic\" clusters of latent variables using a greedy approach; (b) fixing incorrect clusters that could be formed; and finally, (c) fix the local structure using the proposed cross-cover test and v-structure test. The overall algorithm proposed here seems similar in spirit to the work of [2] but is technically more involved. With this algorithm, they are able to recover a latent causal graph and show that in the infinite data limit, the graph they recover is in the same equivalence class as the true graph, up to the \"minimal graph\" and \"skeleton\" operators (definitions 9-10).\n\n### References:\n\n[1] Animashree Anandkumar, Daniel Hsu, Adel Javanmard, and Sham Kakade. Learning linear bayesian networks with latent variables. In International Conference on Machine Learning, pages 249–257, 2013\n\n[2] Feng Xie, Ruichu Cai, Biwei Huang, Clark Glymour, Zhifeng Hao, and Kun Zhang. Generalized independent noise condition for estimating latent variable causal graphs. In Advances in Neural Information Processing Systems, pages 14891–14902, 2020\n\n[3] Bohdan Kivva, Goutham Rajendran, Pradeep Ravikumar, and Bryon Aragam. Learning latent causal graphs via mixture oracles. Advances in Neural Information Processing Systems, 34, 2021\n\n[4] Ricardo Silva, Richard Scheine, Clark Glymour, and Peter Spirtes. Learning the structure of linear latent variable models. Journal of Machine Learning Research, 7(Feb):191–246, 2006\n\n[5] 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, pages 1655–1664. ACM, 2016.", "questions": "Main questions are raised in the strengths and weaknesses part above.\n\n## Other questions/comments:\n1. In L98, what is meant by L and pure children being fully connected? Every pair of vertices from within L, within its pure children and across L and its pure children are all connected by an edge?\n2. What is the objective of appendix G.1? It doesn't seem to explain Definition 3 as the algorithm in G.1 seems to modify the graph (esp. L287-288). But Definition 3 is for a static graph.\n3. In theorem 7, what is meant by a R-2H graph?\n4. Theorem 7 says that the correct Markov equivalence class is learned asymptotically. In the proof of theorem 7, it'd be good to clarify why the algorithm works in the limit. In other words, it's not clear where the asymptotic is coming from.\n5. How are the latent graphs constructed in the synthetic examples? Moreover, the code is not released so it's impossible to figure out how the synthetic examples were generated.\n6. What is the running time of the algorithm? It seems like Algorithm 2 for phase 1 seems to take exponential time in the input size but this should be clarified.\n7. The work [2] seems most closely related to this work. There is a comparison to it in Appendix E. The way it's stated, the main difference seems technical - reducting the number of observed variables needed for latent variables. Is there some other conceptual difference between the works?\n8. The caption for figure 12 is written over the page number in the appendix.", "limitations": "Limitations of the theory are addressed and the authors state there are no potential negative societal impacts. I tend to agree as this is predominantly a theoretical paper.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Summary of evaluation\n\nThe paper obtains nontrivial and potentially useful results. However, the paper is poorly written, with some misleading remarks and definitions. Moreover, the main condition is a bit hard to interpret without diving deep into the proofs and also, there is insufficient comparison to [3], which I think is doing a fairly more complicated setting than this one (although with different assumptions). See the weaknesses section for more details. Despite this, I appreciate the difficulty surpassed in this work, which I believe is inherent for this difficult task of latent causal discovery, that is slowly gaining traction in the community.\n\n## Strengths:\n1. Although the work builds on various known ideas such as exploiting rank deficiency and identifying v-structures, there is significant technical novelty in this work such as the 3-step algorithm that gradually builds the latent graph.\n2. The guarantees improve on some prior works such as [1], [2] on a technical level by weakening the required number of observed children for latent variables. That said, other assumptions are made especially regarding the graph structure.\n3. The algorithms are clear to follow and are illustrated with examples (see appendix G and H)\n\n## Weaknesses:\n1. It is claimed in the introduction that previous works do not handle hierarchical structures (also L66-67 in the appendix). Unfortunately, this doesn't seem right because both [2], [3] that are cited here do seem to handle such structures (see figure 1 in either paper). Moreover, these works handle far more complicated latent structures than the ones considered here (see the point below). Could the authors comment on this?\n2. Based on my understanding, the first and foremost assumption in this work is that the graph has a hierarchical structure. Note very importantly that this is a **strict subset** of directed acyclic graphs (DAGs). Therefore, this work does not handle general DAGs. This assumption should be explicitly stated and clarified.\n3. In the entire abstract and introduction, it is not mentioned that this paper is dealing with a **linear** model. It only shows up in the formal statement in Section 2. However, this is a highly crucial assumption that *significantly* simplifies the task of causal discovery. For instance, say we want to handle nonlinear models  using the same idea. A first stumbling block in this general setting is whether identifying rank-deficiencies, the engine of this paper, can be exploited again.\n4. The first definition Definition 2 is confusing. The phrase \"Variables V are pure children of variables L\" is defined. However, at this point, I don't see why V is uniquely defined, there could be multiple such Vs. Therefore the next sentence \"we denote the pure children of L by PCh_G(L)\" does not make sense. Could the authors clarify this?\n5. More concretely, it's not clear how the Pure Children definition works if L has connections within itself. For example, take figure 1(a) and assume that the edge L1->L3 is not present for now. Suppose L = {L_1, L_3}. Then PCh_G(L) = {L2, L7, L8, L9}. At this point, since L2 and L7 are connected, I don't understand what PCh_G(PCh_G(L)) is. Because of this, how do we define pure descendants of L?\n6. The assumptions of condition 1 (which builds on definition 4) seem hard to interpret. I may be missing something here, but based on my understanding, Appendix G.2, G.3 (in particular L297-298, L311-313) seems to explain how they are relevant *for the proposed algorithm to work*, but not as to why they are *reasonable* assumptions to make. It would be good if the authors could clarify this.\n7. Building on the above point, these graph theoretic assumptions are stated to be mild. Why are they mild assumptions?\n8. A proper comparison to [3] in appendix E should be added. As stated earlier, it seems like [3] handle general DAGs, not just hierarchical DAGs. Moreover, they handle general non-linear causal relationships instead of just linear and also report the more natural SHD metrics (see below). So its important to clarify which fiber of research this line of work develops on a conceptual level.\n9. The reported error metric is the percentage of correctly identified causal clusters over measured variables. Is there a reason a standard metric such as Structural Hamming Distance is not reported? Although I agree with L82-83 in that measuring accuracy is tricky for this problem, other works such as [3] have reported the SHD metric.", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept