Learning Discrete Latent Variable Structures with Tensor Rank Conditions

Authors: zhengming  chen
ruichu  cai
feng  xie
jie  qiao
anpeng  wu
zijian  li
zhifeng  hao
kun  zhang
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 09:02:28

Abstract: Unobserved discrete data are ubiquitous in many scientific disciplines, and how to learn the causal structure of these latent variables is crucial for uncovering data patterns. Most studies focus on the linear latent variable model or impose strict constraints on latent structures, which fail to address cases in discrete data involving non-linear relationships or complex latent structures. To achieve this, we explore a tensor rank condition on contingency tables for an observed variable set $\mathbf{X}_p$, showing that the rank is determined by the minimum support of a specific conditional set (not necessary in $\mathbf{X}_p$) that d-separates all variables in $\mathbf{X}_p$. By this, one can locate the latent variable through probing the rank on different observed variables set, and further identify the latent causal structure under some structure assumptions. We present the corresponding identification algorithm and conduct simulated experiments to verify the effectiveness of our method. In general, our results elegantly extend the identification boundary for causal discovery with discrete latent variables and expand the application scope of causal discovery with latent variables.

Main paper: 
 introduction: 
 Social scientists, psychologists, and researchers from various disciplines are often interested in understanding causal relationships between the latent variables that cannot be measured directly, such as depression, coping, and stress (Silva et al., 2006) . A common approach to grasp these latent concepts is to construct a measurement model. For instance, experts design a set of measurable items or survey questions that serve as indicators of the latent variable and then use them to infer causal relationships among latent variables (Bollen, 2002; Bartholomew et al., 2011; Cui et al., 2018) .Numerous approaches exist for addressing structure learning among latent variables. In particular, if the data generation process is assumed to be a linear relationship, known as linear latent variable models, several approaches have been developed. These include the second-order statistic-based approaches (Silva et al., 2006; Kummerfeld and Ramsey, 2016; Chen et al., 2024; Sullivant et al., 2010) , high-order moments-based ones (Xie et al., 2020; Chen et al., 2022; Cai et al., 2019; Adams et al., 2021) , matrix decomposition-based methods (Anandkumar et al., 2013 (Anandkumar et al., , 2014 (Anandkumar et al., , 2015)) , and copula model-based approaches (Cui et al., 2018) . Moreover, the hierarchical latent variable structure has been well-studied within the linear setting (Huang et al., 2022; Xie et al., 2022; Chen et al., 2023; Jin et al., 2023) . However, the linear assumption is rather restrictive and the discrete data in the real world could be more frequently encountered (e.g., responses from psychological and educationalℙ(𝑋1|𝐿 = 0) ℙ(𝑋1|𝐿 = 1) 0 Ƹ 𝑝 0|0 Ƹ 𝑝 0|1 1 Ƹ 𝑝 1|0 Ƹ 𝑝 1|1 2 Ƹ 𝑝 2|0 Ƹ 𝑝 2|1 ℙ(𝑋2|𝐿 = 0) ℙ(𝑋2|𝐿 = 1) 0 𝑝 0|0 𝑝 0|1 1 𝑝 1|0 𝑝 1|1 2 𝑝 2|0 𝑝 2|0 𝐿 𝑋 1 𝑋 2 0 1 ℙ(𝐿)𝑝 0 𝑝 1 (a) A latent structure with conditional probability tables. Figure 1 : Illustrating the graphical criteria of the tensor rank condition, the rank of the joint distribution is determined by the support of a specific conditional set that d-separates all observed variables, i.e., Rank(P(X 1 , X 2 )) = |supp(L)| = 2. See Example 3.4 for details.assessments or social science surveys (Eysenck et al., 2021; Skinner, 2019) ), which does not satisfy the linear assumption.When the data generation process is discrete, however, due to the challenging nonlinear transition relationship in discrete data, few identifiability results exist and are mostly only applicable in strict cases. In particular, under some prespecified structure, the identifiability of parameters is established, such as in the hidden Markov model(HMM) (Anandkumar et al., 2012) model, topic models (Anandkumar et al., 2014) , and multiview mixtures model (Anandkumar et al., 2015) . By further specifying the latent variable structure as a tree, Wang et al. (2017) ; Song et al. (2013) show that the structural model is identifiable. Recently, Gu (2022) ; Gu and Dunson (2023) further considered the identifiability of pyramid structure under the condition that each latent variable has at least three observed children. However, challenges persist in extending identifiability to more general structures among discrete latent variables. Existing approaches, unfortunately, cannot identify the causal structure of latent variables as shown in Fig. 2(a) . measurement model is fully identifiable and the structure model can be identified up to a Markov equivalence class.L 1 L 2 L 3 L 4 X 4 X 5 X 6 X 1 X 2 X 3 X 7 X 8 X 9 X 10 X 11 X 12L 2 L 3 L 4 X 4 X 5 X 6 X 1 X 2 X 3 X 7 X 8 X 9 X 10 X 11 X 12 (c) Identification resultThe contributions of this work are three-fold. (1) We first establish a connection between the tensor rank condition and the graphical patterns in a general discrete causal model, including specific dseparation relations. (2) We then exploit the tensor rank condition to learn the discrete latent variable model, allowing flexible relations between latent variables. (3) We present a structure learning algorithm using tensor rank conditions and demonstrate the effectiveness of the proposed algorithm through simulation studies. 
discrete latent structure model: 
 For an integer m, denote [m] = {1, 2, ⋯, m}. Consider a discrete statistic model with k latent variable set L = {L 1 , ⋯, L k }, L i ∈ [r i ] and m discrete observed variable set X = {X 1 , ⋯, X m } with X i ∈ [d i ] (r i , d i ≥ 2), in which any marginal probabilities are non-zero. We say a discrete statistic model is a discrete causal model if and only if V = L ∪ X can be represented by a directed acyclic graph (DAG), denoted by G. We use supp(V i ) = {v ∈ Z + ∶ P(V i = v) > 0} to denote the set of possible values of the random variable V i . Our work is in the framework of causal graphical models. Concepts used here without explicit definition, such as d-separation, which can refer to standard literature (Spirtes et al., 2000) .In this paper, we focus on learning causal structure among latent variables in one class of discrete causal models. The model is defined as follows. Definition 2.1 (Discrete Latent Structure Model with Three-Pure Children). A discrete causal model is the Discrete Latent Structure Model with Three-Pure Children (Discrete 3PLSM) if it further satisfies the following three assumptions:1) [Purity Assumption] there is no direct edges between the observed variables; 2) [Three-Pure Child Variable Assumption] each latent variable has at least three pure variables as children; 3) [Sufficient Observation Assumption] The dimension of observed variables support is larger than the dimension of any latent variables support.These structural constraints inherent in the discrete 3PLSM are also widely used in linear latent variable models, e.g., Silva et al. (2006) ; Kummerfeld and Ramsey (2016) ; Cai et al. (2019) ; Xie et al. (2020) . In the binary latent variable case, recently, a similar definition is also employed in Gu and Dunson (2023) ; Gu (2022) . The key difference is that there are no constraints on the latent structure in our work. An example of a discrete 3PLSM model is shown in Fig. 2 (a), where L 1 , ⋯, L 4 represent discrete latent variables, and X 1 , ⋯, X 12 are discrete observed (measured) variables.Generally speaking, the discrete 3PLSM model can be divided into two sub-models (Spirtes et al., 2000) , i.e., the measurement model and the structure model, e.g., red edge and blue edge in Fig. 2 (a) . By this, one can first identify the measurement model to determine the latent variables and then use the measured variable to infer the causal structure of latent variables. As shown in Fig. 2 (b), we will separately discuss the identification of the two sub-models and show that the measurement model is fully identifiable and the structure model is identified up to a Markov equivalence class. The symbols used in our work is summarised in Table 1 .To ensure the identification of causal structure and the asymptotic correctness of identification algorithms, some common causal assumptions are required. Assumption 2.2 (Causal Markov Assumption). Let G be a causal graph with vertex set V and P V be probability distribution over the vertices in V generated by G. We say G and P V satisfy the Causal Markov Assumption if and only if for everyV i ∈ V, P(V i , V \ Des V i |Pa V i = i) = P(W |Pa V i = i)P(V \ Des V i |Pa V i = i).Assumption 2.3 (Faithfulness Assumption). Let G be a causal graph with vertex set V and P V be probability distribution over the vertices in V generated by G. We say < G, P V > satisfies the Faithfulness Assumption if and only if (i). every conditional independence relation true in P V is entailed by the Causal Markov Assumption applied to G, and (ii). for any joint distribution P(L p ), there does not existP(L q ) with |supp(L q )| < |supp(L p )| such that P(L p ) = P(L q ).Assumption 2.4 (Full Rank Assumption). For any conditional probability P(X|Pa X ), the corresponding contingency table is full rank, i.e., each column of P(X|Pa X ) is linearly independent with the other column vectors in the parameter space.In general, Assumptions 2.2 ∼ 2.3 are widely used in the constraint-based causal discovery methods, e.g., PC algorithm and FCI algorithm (Spirtes et al., 2000; Spirtes and Glymour, 1991) . One can see that we further constraint the parameter space of joint distribution cannot be reduced to a lowdimension space, for maintaining the diversity of parameter space. This is also the reason for Assumption 2.4, which aligns with the non-degeneracy condition used in (Kivva et al., 2021) .Our goal: The goal of our work is to develop a robust approach for identifying discrete latent structure models, including both the measurement and structural models.V: The set of variables V = X ∪ L X: The set of observed variables L: The set of latent variablesV i ⫫ V j |V p : Conditional independence |X p | : Dimension of X pT (X p ) : the tensor form of P(X p ) P(X p ): the joint distribution of X p Rank(T (X p ) ) : The rank of tensor T (X p ) Pa X : The parent set of X Des X : The descendant set of X Diag(M): The diagonal matrix of M u i ⊗ u j : The outer product of two vectors  
tensor rank condition with graphical criteria: 
 To address the identification problem in the discrete 3PLSM, this section introduces the building block-the tensor rank condition of the discrete causal model. Then, we establish the connection between tensor rank and d-separation relations under a general discrete causal model.Before formalizing the tensor rank condition, we first give the explicit definition of tensor rank.Definition 3.1 (Rank-one Tensor). An n-way tensor T ∈ R I 1 ×⋯×I n is a rank-one tensor if it can be written as the outer product of n vectors, i.e.,T = u 1 ⊗ u 2 ⊗ ⋯ ⊗ u n ,where u i are vectors that each represent a dimension of the tensor, ⊗ represents the outer product. Definition 3.2 (Tensor Rank Kolda and Bader (2009) ). For an n-way tensor T ∈ R I 1 ×⋯×I n , the rank of a tensor T is defined as the smallest number of rank-one tensors that sum to exactly represent T . Formally, the rank of tensor T , denoted rank(T ), is the smallest integer r such that:T = r ∑ i=1 u (i) 1 ⊗ u (i) 2 ⊗ ⋯ ⊗ u (i) n ,where each u (i) k is a vector in the corresponding vector space associated with the k-th mode of T .In other words, the tensor rank denotes the minimal number of rank-one decompositions. In the discrete causal model, the joint distribution can be represented as a tensor, e.g., the joint distribution of two random variables is a two-way contingency tensor. Interestingly, by carefully analyzing the (non-negative) rank-one decomposition of the joint distribution, we find that the tensor rank essentially reveals structural information within the causal graph. The result is presented below. Theorem 3.3 (Graphical implication of tensor rank condition). In the discrete causal model, suppose Assumptions 2.2 ∼ Assumption 2.4 hold. Consider an observed variable set X p = {X 1 , ⋯, X n } (X p ⊆ X and n ≥ 2) and the corresponding n-way probability tensor T (X p ) that is the tabular representation of the joint probability mass function P(X 1 , ⋯, X n ). Then, Rank(T (X p ) ) = r (r > 1) if and only if (i) there exist a conditional set S ⊂ V with |supp(S)| = r that d-separates any pair of variables in {X 1 , ⋯, X n }, and (ii) does not exist conditional set S that satisfies |supp( S)| < r. We further provide an example to illustrate Theorem 3.3. Example 3.4 (Illustrating the graphical criteria). Consider a single latent variable structure as shown in Fig. 1 (a) where L is a latent variable with supp(L) = {0, 1} and X 1 , X 2 are observed variables with supp(X i ) = {0, 1, 2}, i ∈ {1, 2}. For convenience, we denote p i = P(L = i), pi|j = P(X 1 = i|L = j), and pi|j = P(X 2 = i|L 1 = j). The joint distribution P(X 1 , X 2 ) can be expressed as the product of conditional probabilities, as shown in Fig. 1(b) . By applying the tensor decomposition, we observe that P(X 1 , X 2 ) can be decomposed as the sum of two rank-one tensors: P(X 1 , X 2 |L = 0) and P(X 1 , X 2 |L = 1). Thus, the rank of the tensor P(X 1 , X 2 ) is two, corresponding to the cardinality of the latent variable's support. The reason P(X 1 , X 2 |L = i) is a rank-one tensor is that L d-separates X 1 and X 2 , i.e., P(X 1 , X 2 |L = i) = P(X 1 |L = i) ⊗ P(X 2 |L = i). This illustrates the connection between tensor rank and d-separation relations.Intuitively, the graphical criteria theorem suggests that, in the discrete causal model, the tensor rank condition implies the minimal conditional probability decomposition within the probability parameter space, which hopefully induces the structural identifiability of the discrete 3PLSM model. 
structure learning of discrete latent structure model: 
 In this section, we address the identification problem of the discrete 3PLSM model using a carefully designed algorithm that leverages the tensor rank condition. Specifically, we first show that latent variables can be identified by finding causal clusters among observed variables (Sec. 4.1). Then, we use these causal clusters to conduct conditional independence tests among latent variables based on the tensor rank condition, identifying the structure model (Sec. 4.2). Finally, we discuss the practical implementation of testing tensor rank (Sec. 4.3). For simplicity, we focus on the case where all latent variables have the same number of categories. The result can be directly extended to cases with different numbers of categories (see details in Appendix E).To answer the identification of the measurement model, one common strategy is to find the causal cluster that shares the common latent parent, which has been well-studied within the linear model, such as Silva et al. (2006) ; Cai et al. (2019) ; Xie et al. (2020) . We follow this strategy and show that, in the discrete 3PLSM, the causal cluster can be found by testing the tensor rank conditions iteratively. The definition of a causal cluster is as follows. Definition 4.1 (Causal cluster). In the discrete 3PLSM, the variable set {X 1 , ⋯, X n } is a causal cluster, termed C i , if and only if all variables in {X 1 , ⋯, X n } share the common latent parent.It is not hard to see that, the measurement model can be identified if all causal cluster is found. In order to find these causal clusters by making use of the tensor rank condition, the key issue is to determine the support of latent variables in advance. This issue can be addressed by identifying the rank of the two-way tensor formed by the joint distribution of two observed variables. Proposition 4.2 (Identification of support of latent variables). In the discrete 3PLSM model suppose Assumptions 2.2 ∼ Assumption 2.4 hold. The support of the latent variable corresponds to the rank of the two-way probability contingency table for any pair of observed variables X i and X j , i.e., |supp(L)| = Rank(T (X i ,X j ) ), ∀X i , X j ∈ X.This result holds because any pair of variables in the discrete 3PLSM model is d-separated by any one of their latent parent variables, and all latent variables have the same support. Next, we formalize the property of clusters and give the criterion for finding clusters. Proposition 4.3 (Identification of causal cluster). In the discrete 3PLSM mode, suppose Assumption 2.2 ∼ Assumption 2.4 hold. Let r = |supp(L i )| denote the cardinality of the latent support. Given three disjoint observed variables X i , X j , X k ∈ X,• Rule1: if the rank of tensor T (X i ,X j ,X k ) is not equal to r, i.e., Rank(T (X i ,X j ,X k ) ) ≠ r, then X i , X j and X k belong to the different latent parents. • Rule2: for any X s , X s ∈ X \ {X i , X j , X k }, if the rank of tensor T (X i ,X j ,X k ,X s ) is r, i.e., Rank(T (X i ,X j ,X k ,X s ) ) = r, then {X i , X j , X k } share the same latent parent. Example 4.4 (Finding causal clusters). Let's take Fig. 2 (a) as an example. One can find that for{X 1 , X 2 , X 3 , X k }, where X k ∈ X \ {X 1 , X 2 , X 3 }, the rank of tensor T (X 1 ,X 2 ,X 3 ,X k ) is r. Thus, {X 1 , X 2 , X 3 } is identified as a causal cluster.Next, we consider the practical issues involved in determining the number of latent variables by causal clusters. That is, there are some causal clusters that should be merged because they share one latent parent. We find that the overlapping clusters can be directly merged into one cluster. This is because the overlapping clusters have the same latent variable as the parent under the discrete 3PLSM model. The validity of the merge step is guaranteed by Proposition 4.5. Proposition 4.5 (Merging Rule). In the discrete 3PLSM model, for two causal clusters C 1 and C 2 , if C 1 ∩ C 2 ≠ ∅, then C 1 and C 2 share the same latent parent.Based on the above results, one can iteratively identify causal clusters and apply the merger rule to detect all latent variables. The identification procedure is summarized in Algorithm 1.Algorithm 1 Finding the causal cluster Input: Data from a set of measured variables X G , and the dimension of latent support r Output: Causal cluster C 1: Initialize the causal cluster set C ≔ ∅, and G ′ = ∅; 2: // Identify Causal Skeleton 3: Begin the recursive procedure 4: repeat 5:for each X i , X j and X k ∈ X do 6: if Rank(T {X i ,X j ,X k } ) ≠ r then 7: Continue; // Rule1 of Prop. 4.3 8: end if 9: if Rank(T {X i ,X j ,X k ,X s } ) = r, for all X s ∈ X \ {X i , X j , X k } then 10: C = C ∪ {{X i , X j ,G = G ∪ {L i → X j |X j ∈ C i }.19: end for 20: return Graph G and causal cluster C. Theorem 4.6 (Identification of the measurement model). In the discrete 3PLSM, suppose Assumption 2.2 ∼ Assumption 2.4 hold. The measurement model is fully identifiable by Algorithm 1.Once the measurement model is identified, the observed children can serve as proxies for the latent variables, enabling the identification of the causal structure among them. Here, we employ constraintbased framework to learn the causal structure of latent variables.Constraint-based structure learning algorithms find the Markov equivalence class over a set of variables by making decisions about independence and conditional independence among them. Given a pure and accurate measurement model with at least two measures per latent variable, we can test for independence and conditional independence (CI) among the latent variables. Specifically, to test statistical independence between discrete variables, one can examine whether the rank of their joint distribution contingency table is one (Sullivant, 2018) . For testing conditional independence (CI) relations among latent variables, further leveraging the algebraic properties of the tensor rank condition is required (see Theorem 4.7). Theorem 4.7 (d-separation among latent variable). In the discrete 3PLSM, suppose Assumption 2.2 ∼ Assumption 2.4 hold. Let r denote the cardinality of the latent support. Then,L i ⫫ L j |L p if and only if Rank(T (X i ,X j ,X p1 ,X p2 ) ) = r |L p |, where X i and X j are the pure children of L i and L j , X p1 and X p2 are two disjoint child sets of L p that satisfy∀L i ∈ L p , Ch L i ∩ X p1 ≠ ∅, Ch L i ∩ X p2 ≠ ∅.Intuitively, based on the graphical criteria of tensor rank condition, L p is a minimal conditional set in the causal graph that d-separates X p1 and X p2 and hence the rank of tensor T (X i ,X j ,X p1 ,X p2 ) is the dimension of support of L p , if X i and X j also be d-separated by L p .Example 4.8 (CI test among latent variables). Consider the structure in Fig. 2 (a) and suppose r = 2. By selectingX p1 = {X 4 , X 7 } and X p2 = {X 5 , X 8 } as two disjoint child sets of {L 2 , L 3 } respectively, let X p = {X 1 , X 10 , X 4 , X 5 , X 7 , X 8 } and L p = {L 2 , L 3 }. One can see that the rank of tensor T (X p ) is four since L p (i.e., {L 2 , L 3 }) is minimal conditional set that d-separates any pair variable in X p , which imply that L 1 ⫫ L 4 |{L 2 , L 3 }.Based on Theorem 4.7, we introduce the PC-TENSOR-RANK algorithm. This method accepts a measurement model learned by the previous procedure, and outputs the Markov equivalence class of the structural model associated with the latent variables within the measurement model, in accordance with the PC algorithm. The implementation is summarised as Algorithm 2. Consequently, we establish the identification of the structure model as shown in Theorem 4.9.Algorithm 2 PC-TENSOR-RANK Input: Data set X = {X 1 , . . . , X m } and causal cluster C Output: A partial DAG G.1: Initialize the maximal conditions set dimension k; 2: Let L i denote as C i , C i ∈ C; 3: Form the complete undirected graph G on the latent variable set L; 4: for ∀L i , L j ∈ L and adjacent in G do 5://Test the CI relations among latent variables by Theorem 4.76: if ∃L p ⊆ L \ {L i , L j } and (|L p | < k) such that L i ⫫ L j |L p hold then 7: delete edge L i -L j from G; 8:end if 9: end for 10: Search V structures and apply meek rules Meek (1995) . 11: return a partial DAG G of latent variables.Theorem 4.9 (Identification of structure model). In the discrete 3PLSM, suppose Assumption 2.2 ∼ Assumption 2.4 hold. Given the measurement model, the causal structure over the latent variable is identified up to a Markov equivalent class by the PC-TENSOR-RANK algorithm.In our theoretical results, the key issue is to test the rank of a tensor, which involves estimating the dimension of latent support and the rank of a tensor. Here, we aim to explore methods to (i) estimate the rank of the contingency matrix for determining the dimension of latent support, and (ii) apply the goodness-of-fit test to assess the tensor rank.Estimate the rank of contingency matrix. We start with the estimation of the dimension of latent variables support based on Prop. 4.2. There are many practical approaches used to estimate the rank of a general matrix M, such as Camba-Méndez and Kapetanios (2009) . In our implementation, we 10) 0.00(0) 0.10(2) 0.00(0) 0.00(0) 0.05(1) 0.00(0) 0.00(0) 0.00(0) SM 1 + M M 1 10k 0.05(1) 0.05(1) 0.10(2) 0.90(10) 0.00(0) 0.05(1) 0.00(0) 0.00(0) 0.00(0) 0.00(0) 0.00(0) 0.00(0) 50k 0.00(0) 0.00(0) 0.00(0) 0.90(10) 0.00(0) 0.00(0) 0.00(0) 0.00(0) 0.00(0) 0.00(0) 0.00(0) 0.00(0) 5k 0. 23(5) 0.19(6)  0.26(6)  0.90(10) 0.00(0) 0.19(6) 0.03(1) 0.00(0) 0.05(2) 0.19(6)  0.23(6)  0.00(0)  SM 2 + M M 1 10k 0.13(4) 0.13(4)  0.13(4)  0.86(10) 0.00(0) 0.03(4) 0.00(0) 0.00(0) 0.00(0) 0.13(4)  0.13(4)  0.00(0)  50k 0.06(2) 0.10(3)  0.10(3)  0.86(10) 0.00(0) 0.13(4) 0.00(0) 0.00(0) 0.00(0) 0.13(4)  0.10(3)  0.00(0)  5k  0.12(2) 0.19(6)  0.21(5)  0.90(10) 0.00(0) 0.19(6) 0.00(0) 0.00(0) 0.03(1) 0.16(6)  0.21(5)  0.00(0)  SM 2 + M M 2 10k 0.03(1) 0.13(4)  0.10(3)  0.86(10) 0.00(0) 0.13(4) 0.00(0) 0.00(0) 0.00(0) 0.11(4)  0.10(3)  0.00(0)  50k 0.00(0) 0.07(2)  0.07(2)  0.83(10) 0.00(0) 0.07(2) 0.00(0) 0.00(0) 0.00(0) 0.07(2)  0.06(2)  0.00(0)  5k  0.25(6) 0.30(6) 0.55(10) 0.86(10) 0.00(0) 0.30(6) 0.00(0) 0.00(0) 0.12(5) 0.20(6) 0.55(10) 0.00(0)  SM 3 + M M 1 10k 0.17(5) 0.25(5) 0.50(10) 0.83(10) 0.00(0) 0.25(5) 0.00(0) 0.00(0) 0.05(3) 0.16(5) 0.50(10) 0.00(0)  50k 0.08(3) 0.20(4) 0.50(10) 0.83(10) 0.00(0) 0.20(4) 0.00(0) 0.00(0) 0.03(2) 0.13(4) 0.50(10) 0.00(0) use the characteristic root statistic, abbreviated as CR statistic Robin and Smith (2000) , to test the rank of the probability contingency matrix of two observed variables. Specifically, Let M be an asymptotically normal estimator of M, then the CR statistic is the sum of dr smallest singular values of M, multiplied by the sample size. Under the null hypothesis, the above statistic converges in distribution to a weighted (given by the eigenvalues) sum of independent X 2 1 random variables.Goodness-of-fit test for tensor rank. Once the dimension of the support of latent variables is identified, in the structure learning procedure, we perform the following hypotheses test:H 0 : Rank(T ) = r v.s. H 1 : Rank(T ) ≠ r.To achieve this, we first apply the canonical polyadic (CP) decomposition technology to the target tensor T as a sum of r rank-one tensors given specified r, then we evaluate how well the reconstructed tensor from this decomposition approximates the original tensor to conduct the hypotheses test.To perform the rank-decomposition with specified r on the probability contingency tensor, one can use the non-negative CP decomposition to decompose the tensor into the sum of r rank-one tensor Shashua and Hazan (2005) . Given the decomposition, one can obtain a reconstructed tensor, denoted by T , from the outer product of decomposed vectors.With the reconstructed tensor, we constructed square-chi goodness of fit test Cochran (1952) for testing Rank(T ) = r. Such a test is frequently used to summarize the discrepancy between observed values and the expected values, which measure the sum of differences between observed and expected outcome frequencies. Let vec(T ) be the vectorization of tensor T , suppose vec( T ) be the asymptotic normality estimator of vec(T ), we have the chi-square statistic asX 2 = ∑ i∈vec( T ) (vec(T ) i -vec( T ) i ) 2 vec( T ) i , which follows the X 2 distribution with freedom degrees ∏ i∈[n] d i -(∑ i,j∈[n] d i d j ). 
simulation studies: 
 In this section, we conducted simulation studies to assess the correctness of the proposed methods.The baseline approaches include Building Pure Cluster (BPC) Silva et al. (2006) , Latent Tree Model (LTM) Choi et al. (2011) , and Bayesian Pyramid Model (BayPy) Gu and Dunson (2023) .In the following simulation studies, we consider the different combinations of various types of structure models(SM) and measurement models(MM). Specifically, for the structure model, we consider the following five typical cases: [SM1]:L 1 → L 2 ; [SM2]: L 1 → L 2 → L 3 ; [SM3]: the structure of latent variables is shown in Fig. 2(a); [Collider]: L 1 → L 2 ← L 3 ; [Star]: L 1 → L 2 , L 1 → L 3 , L 1 → L 4 .For the measurement model, we consider the following two cases: [MM1]: each latent variable has three pure observed variables, i.e., L i → {X 1 , X 2 , X 3 }; [MM2]: each latent variable has four pure observed variables, i.e.,L i → {X 1 , X 2 , X 3 , X 4 }.In all cases, the data generation process follows the discrete 3PLSM model: (i) we generate the probability contingency table of latent variables in advance, according to different latent structures (e.g., SM1), then (ii) we generate the conditional contingency table of observed variables (condition on their latent parent), and finally (iii) we sample the observed data according to the probability contingency table, where the dimension of latent support r is set to 3 and the dimension of all observed variables support is set to 4, sample size ranged from {5k, 10k, 50k}. 0.00(0) 1.00(10) 0.26(8) 1.00(10) 0.10(1) 0.00(0) 0.00(0) 0.00(0) 0.10(1) 1.00(10) -1.00(0) Collider+M M 1 10k 0.00(0) 1.00(10) 0.23(6) 1.00(10) 0.00(0) 0.02(1) 0.0(0) 0.00(0) 0.00(0) 1.00(10) -1.00(0) 50k 0.00(0) 1.00(10) 0.10(3) 1.00(10) 0.00(0) 0.00(0) 0.00(0) 0.00(0) 0.00(0) 1.00(10) -1.00(0) 5k 0.15(3) 1.00(10) 0.16(6) 1.00(10) 0.10(1) 0.00(0) 0.00(0) 0.00(0) 0.00(0) 0.00(0) -0.00(0) SM 2 + M M 1 10k 0.05(1) 1.00(10) 0.13(4) 1.00(10) 0.01(1) 0.00(0) 0.00(0) 0.00(0) 0.00(0) 0.00(0) -0.00(0) 50k 0.00(0) 1.00(10) 0.10(3) 1.00(10) 0.00(0) 0.00(0) 0.00(0) 0.00(0) 0.00(0) 0.00(0) -0.00(0) 5k 0.10(3) 1.00(10) 0.25(5) 1.00(10) 0.20(5) 0.00(0) 0.00(0) 0.00(0) 0.00(0) 0.00(0) -0.00(0) Star + M M 1 10k 0.06(2) 1.00(10) 0.15(3) 1.00(10) 0.08(3) 0.00(0) 0.00(0) 0.00(0) 0.00(0) 0.00(0) -0.00(0) 50k 0.03(1) 1.00(10) 0.15(3) 1.00(10) 0.05(2) 0.00(0) 0.00(0) 0.00(0) 0.00(0) 0.00(0) -0.00(0) 5k 0.22(7) 1.00(10) 0.50(10) 1.00(10) 0.40(6) 0.00(0) 0.02(1) 0.00(0) 0.20(2) 1.00(10) -1.00(10) SM 3 + M M 1 10k 0.15(5) 1.00(10) 0.50(10) 1.00(10) 0.10(2) 0.00(0) 0.00(0) 0.00(0) 0.10(1) 1.00(10) -1.00(10) 50k 0.05(2) 1.00(10) 0.50(10) 1.00(10) 0.05(1) 0.00(0) 0.00(0) 0.00(0) 0.00(0) 1.00(10) -1.00(10)For each simulation study, we randomly generate the dataset and apply the proposed algorithm and baselines to these data. We use the following scores for evaluating the performance of causal clusters from each algorithm: latent omission, latent commission, and mismeasurement. Moreover, to assess the ability of these algorithms to correctly discover the causal structure among latent variables, we use the metric like edge omission (EO), edge commission (EC), and orientation omission (OO). These metrics can be referred to Silva et al. (2006) , in which the tasks are aligned with our work. Each experiment was repeated ten times with randomly generated data, and the results were averaged.The results are reported in Table 2 and Table 3 . Our method consistently delivers the best outcomes across most scenarios, demonstrating its capability to identify both the causal clusters and the causal structures of latent variables. In contrast, the BPC approach performs poorly, as it is specifically designed for linear models. Additionally, the LTM and BayPy algorithms show suboptimal performance in structure learning of latent variables due to their limitations to specific structural models, such as tree structures, or assumptions that latent variables are binary.6 Discussion and Further Work The preceding sections presented the identification of discrete 3PLSM. In this section, we examine whether the impure structure (e.g., an edge between observed variables) can be detected through tensor rank conditions. For instance, consider the structure shown in Fig. 3 and suppose all observed variable has the same support. One can observe that for any subsetL X 1 X 2 X 3 X 4 X 5{X i , X j , X k } ⊂ {X 1 , X 2 , X 3 , X 4 , X 5 } where {X 4 , X 5 } / ⊂ {X i , X j , X k }, one has Rank(T (X i ,X j ,X k ) ) = |supp(L)|. This implies {X 1 , X 2 , X 3 }and X 4 (or X 5 ) share the common latent parent. Moreover, we have Rank(T (X 4 ,X 5 ) ) = |supp(X 5 )|, assuming the cardinality of the observed variables is larger than that of the latent variables. By the graphical criteria of the tensor rank condition, one can infer that there is an edge between X 4 and X 5 , indicating the impure structure can be identified by the tensor rank condition. Developing an efficient algorithm to learn a more general discrete 3PLSM structure that allows impure structure in a principled way is part of our future work. 
conclusion: 
 We derive a nontrivial algebraic property of a particular type of discrete causal model under proper causal assumptions. We build the connection between tensor rank and the d-separation relations in the causal graph and propose the graphical criteria of tensor rank. By this, the identifiability of causal structure in discrete latent structure models is achieved based on which we proposed an identification to locate latent causal variables and identify their causal structure. We provide a practical test approach for testing the tensor rank and verifying the efficientness of the proposed algorithm via the simulated studies. The proposed theorems and the algorithms take a meaningful step in understanding the causal mechanism of discrete data. However, the proposed method can hardly be applied to high-dimensional discrete data and only applies to pure-children structures. Therefore, relaxing these restrictions and making them scalable to high-dimensional real-world datasets and more general structural constraints would be a meaningful future direction. T (X 1 X 2 ) = ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢EQUATIONwhere T (X 1 |L 1 ) is the tensor representation of P(X 1 |L 1 ), T (X 2 |L 1 ) is the tensor representation of P(X 2 |L 1 ) and Diag(T (L 1 ) ) is the diagonalization of P(L 1 ).Under the Full Rank assumption, we have T (X 1 |L 1 ) and T (X 2 |L 1 ) are column full rank. Thus, the rank of T X 1 X 2 is two, i.e., Rank(T X 1 X 2 ) = |supp(L 1 )| = 2. This illustrate the Prop. 1.Next, we consider the three-way tensor T (X 1 X 2 X 3 ) of the joint distribution P(X 1 X 2 X 3 ). We will represent the three-way tensor as its frontal slices Kolda and Bader (2009) , i.e., three matrices for P(X 1 X 2 X 3 = 0), P(X 1 X 2 X 3 = 1) and P(X 1 X 2 X 3 = 2). ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ p 000 p 010 p 020 p 100 p 110 p 120 p 200 p 210 p 220 ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ T (X 1 X 2 X 3 =0) , ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ T (X 1 X 2 X 3 =1) , ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ p 002 p 012 p 022 p 102 p 112 p 122 p 202 p 212 p 222 ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ T (X 1 X 2 X 3 =2).(2)In the contingency tensor above, the element of T (X 1 X 2 X 3 ) isEQUATIONOne can represent the tensor T X 1 X 2 X 3 |L 1 =r asEQUATIONwhere ⊗ represent the outer product, e.g., for two vector u and v, (u⊗ v) ij = u i v j with u = {u 1 , ⋯, u n } and v = {v 1 , ⋯, v n }.According to the definition of tensor rank, one can see thatT (X 1 X 2 X 3 |L 1 =r) is a rank-one tensor. Furthermore, since T (X 1 X 2 X 3 ) = ∑ 2 r=1 T (X 1 X 2 X 3 |L 1 =r) T (L 1 =r) , the rank of T (X 1 X 2 X 3 ) is two under Assumption 2.2 ∼ Assumption 2.4. This is because L 1 d-separates X i and X j with ∀i, j ∈ [1, 2, 3],which illistrate the graphical criteria of tensor rank condition. 
 
 Appendix: To study the discrete statistical model, certain commonly-used parameter assumptions are necessary. For instance, the Full Rank assumption (Assumption 2.4), as utilized in our study, ensures diversity within the parameter space. This is crucial to prevent the contingency table of the joint distribution from collapsing into a lower-dimensional space. There are related works that also use such an assumption Leonard and Novick (1986) ; Bartolucci et al. (2007) ; Gu (2022) . Essentially, in our work, such an assumption ensures the effectiveness of rank decomposition (e.g., minimal decomposition or unique decomposition Kruskal (1977) ), which induces the structural identifiability of a discrete causal model. Moreover, the sufficient observation assumption that the dimension of latent support is larger than the dimension of observed support is reasonable, as it ensures sufficient measurement of the latent variable. We also discuss this assumption in the remark E.4 that demonstrates the CI relation is testable if this assumption holds.It is worth noting that, although Kivva et al. (2021) shows that the causal structure among latent variables can be identifiable under weaker assumptions, by leveraging the identifiability of the mixture model, we emphasize that our algorithm, based on the tensor rank condition, is simpler and more efficient. It can also produce more robust results when performing causal discovery on the observational data. Moreover, in Kivva et al. (2021) , the parameters of the mixture oracle, such as the number of components, are estimated using approximate methods like the K-means algorithm, which may not be applied directly to discrete data.D.1 Proof of Theorem 3.3We prove this by contradiction, i.e., suppose (i). there exists a variable set S in the causal graph G with |supp(S)| = r that d-separates any pair of variables in {X 1 , ⋯, X n }, and (ii).does no exist conditional set S that satisfies |supp( S)| < r, then Rank(T {X 1 ...X n } ) ≠ r. There are two cases we need to consider: Case 1: Rank(T {X 1 ...X n } ) > r, and Case 2:EQUATIONwhich violates the definition of tensor rank (i.e., k is not a minimal rank-one decomposition, it can be reduced to the smaller decomposition with r). Meanwhile, if there exists other conditional sets S such that P(X1 ⋯X n ) = ∑ k i=1 (∏ n j=1 T (X j | S=i) )T ( S=i) is minimal rank decomposition, it violates the condition (ii) that |supp(S)| is minimal. , Case 2: When Rank(T {X 1 ...X n } ) < r, let Rank(T {X 1 ...X n } ) = t < r,due to S is conditional set with smallest support r in the causal graph, one haveEQUATIONwhich means that there at least exist T (X 1 ...X n |S=i) and T (X 1 ...X n |S=j) such that T (X j |S=i) = αT (X k |S=i) for any i, k ∈ [n] where α is a constant, i.e, the columns of the conditional contingency table are linearly dependent. This violates the assumption 2.4 (the Full Rank assumption).Therefore, Rank(T {X 1 ...X n } ) = r if the condition (i) and condition (ii) holds.We will show if one of the conditions is violated, the tensor rank is not r, i.e., if (i). there does not exist a variable set S in the causal graph with |supp(L)| = r that d-separates any pair of variables in {X 1 , ⋯, X n }, or (ii). exist S that satisfies |supp( S)| < r, then Rank(T {X 1 ...X n } ) ≠ r.We first show the case that condition (i) is violated. There are two cases we need to consider, i.e., Case 1: S is not a conditional set in the causal graph, and Case 2: S is a variable constructed from parameter space.Case 1: if S is not a conditional set and S ∩ Des X 1 ∩ ⋯ ∩ Des X n = ∅, by the Markov assumption, P(X 1 , ⋯, X n |S = i) ≠ ∏ n j=1 P(X j |S = i). By Lemma. D.3, P(X 1 , ⋯, X n |S = i) is not a rank-one tensor, which violates the definition of tensor rank.If S is not a conditional set and S∩Des X 1 ∩⋯∩Des X n ≠ ∅, we will show that P(X 1 , ⋯, X n |S = i) is not a rank-one tensor, to prove such a rank-decomposition does not exist. Under the faithfulness assumption and Markov assumption, let S be the a minimal conditional set with |supp( S)| = k for any pair variable in {X 1 , ⋯, X n }, we haveEQUATIONNote that if there exists X p , X q ∈ {X 1 , ⋯, X n } such that S is the common descendant variable of X p and X q , it will lead to a collider structure in which P(X i |S) and P(X j |S) is relevant (i.e., the v-structure is activated). Thus, letX t = {X 1 , ⋯, X n } \ {X i , X j }, T (X 1 ⋯X n |S=i)is not a rank-one tensor due to the sub-tensor T (X i X j ,X t =c|S=i) (a slice of tensor T (X 1 ⋯X n |S=i) ) is not a rank-one tensor 2 Hackbusch (2012); Kruskal (1977) , under the faithfulness assumption. If so, one haveT (X i X j ,X t =c|S=i) = u 1 ⊗ u 2 . Let u 1 = P(X i , X t = c|S = i) and u 2 = P(X j , X t = c|S = i), itviolates the faithfulness assumption. Thus, S can not be the common descendant of any pair variables in {X 1 , ⋯, X n }. So, for any X p , X q ∈ {X 1 , ⋯, X n }, there are T (X p X q |S=j S=i) = T (X p | S=i,Des Xp )=c ⊗ T (X q | S=i,Des Xq )=c according to Markov assumption ( S is a d-separation set for X p and X q ). Now, for the Eq. 8, we haveT (X 1 ⋯X n |L=i) = k ∑ j=1 ⊗ n t=1 T (X t | S=j,Des Xt =c) T ( S=j,Des Xt =c| S=j) = u 1 ⊗ ⋯ ⊗ u n . (9)This equality holds if the k sum of the rank-one tensor can be reduced to a rank-one tensor, i.e., for any Xp , T (X p | S=1,Des Xp =c) = α 2 T (X p | S=2,Des Xp =c) = ⋯ = α r T (X p | S=r,Des Xp =c), where α i and c are constant. However, this equality can not hold due to the following reasons.If Pa X p ≠ ∅, let L p be the parent of X p , we haveEQUATION2 The lower bound of tensor rank is not less than the rank of any slice of tensor. in which the inequality holds because of the Full Rank assumption and all marginal distribution probabilities are not zero (see Lemma. D.4). Therefore, T (X p | S=1,Des Xp =c) ≠ ⋯ ≠ α r T (X p | S=r,Des Xp =c) . Thus, T (X 1 ⋯X n |S=i) is not a rank-one tensor. By the definition of tensor rank, Rank(T (X 1 ⋯X n ) ) ≠ r.If Pa X p = ∅, i.e., X p is the root variable, (e.g., X p → S, Des X p ∈S ), we will show that the probability contingency table T (X p |S) is full rank, and then the equality in Eq. 8 can not hold. According to the Full Rank assumption and X p is the parent variable of S, we have the probability contingency table T (S|X p ) is full rank.Due to P(X p , S) = P(S|X p )P(X p ) = P(X p |S)P(S) and the probability in the marginal distribution is not zero, we have T (X p |S) = T (S|X p ) Diag(T (X p ) )Diag(T (S) )† , where Diag(T (X p ) ) is a diagonalization of marginal distribution probability vector of X p . One can see that T (X p |S) is full rank due to the diagonal matrices are all of full rank. Thus, T (X p | S=1) ≠ ⋯ ≠ α r T (X p | S=r) and T (X 1 ⋯X n |S=i) is not a rank-one tensor. By the definition of tensor rank, Rank(T (X 1 ⋯X n ) ) ≠ r.Case 2: we further show that for the parameter space, the tensorT (X 1 ,⋯,X n ) = ∑ r i=1 u 1 ⊗ ⋯ ⊗ u ndoes not hold with r, where u i represents any vector. Let u i ⊗ ⋯ ⊗ u n be a rank-one tensor of P(X 1 , ⋯, X n | S = i)P( S = i) due to P( S = i) is a constant. In other words, one can construct a variable set S with |supp( S)| = r. For any S constructed from parameter space (i.e., S is not a true node set in the causal graph), ifT (X 1 ,⋯,X n | S=i) = u 1 ⊗⋯⊗u n , one can let u 1 = T (X 1 | S=i) , ⋯, u n = T (X n | S=i), which violates the faithfulness assumption. Based on the above analysis, there does not exist S by any constructed such that T (X 1 ⋯X n ) have the summation r rank-one decomposition, i.e., Rank(T (X 1 ⋯X n ) ) ≠ r. Now, we analyze the condition (ii), i.e., there exists a conditional set S with supp( S) < r. Letsupp( S) = k, k < r, we have T (X 1 ⋯X n ) = ∑ k i=i T (X 1 | S=i) ⋯⊗T (X n | S=i) T ( S=i) is a smaller rank-one decomposition than T (X 1 ⋯X n ) = ∑ r j=1 u j 1 ⊗ ⋯ ⊗ u j n .According to the definition of tensor rank, we haveRank(T {X 1 ...X n } ) = k ≠ r.In summary, the theorem is proven.Lemma D.1. Let L p be the parent of X p . Consider P(X p |S = i) and P(X p |S = r), where S can be any variable set. Under the Assumption 2.4, for a constant c, the following inequality holds:|supp(L p )| ∑ j=1 T (X p |L p =j) T (L p =j|S=i) ≠ c |supp(L p )| ∑ j=1 T (X p |L p =j) T (L p =j|S=r) .Proof. We prove it by contradiction. For convenience of symbols, let v j = T (X p |L p =j) , and α j|i = P(L p = j|L = i) and β j|r = P(L p = j|L = r) (α j|i ≠ β j|r ), if the equality hold, we haveEQUATIONwhich means thatEQUATION)That is, v t is a linear combination of other vectors v k with t ≠ k, i.e., the linear combination of other column vectors in the conditional probability contingency table, which is contrary to the Assumption 2.4.Lemma D.2. Let L p be the parent of X p . Suppose Assumption 2.2 ∼ Assumption 2.4 hold. T (X p |S=i) cannot be expressed as a linear combination of other q vectors T (X p |S=r) , i.e., T (X p |S=i) ≠ ∑ q r=1 γ r T (X p |S=r) .Proof. We prove it by contradiction. For convenience of symbols, let v j = T (X p |L p =j) , and α j|i = P(L p = j|S = i) and β j|r = P(L p = j|S = r), if the equality hold, one haveEQUATIONthere exist a vector v t with α t|i -∑ q r=1 γ r β t|r ≠ 0, such that EQUATION⋯X n } = ∅, then T (X 1 ⋯X n | S=j)is not a rank-one tensor.Proof. Let S be the minimal conditional set, (e.g., S = {X 1 , ⋯, X n-1 }), denote |supp(S)| = r, under the faithfulness assumption and the Markov assumption, P(S) ≠ P( S), if T (X 1 ⋯X n | S=j) is a rank-one tensor, we haveEQUATIONwhich means that for anyX p ∈ {X 1 , ⋯X n }, T (X p |S=1) = α 2 T (X p |S=2) = ⋯T (X p |S=r) .If X p has a parent variable L p in the causal graph, by Lemma .D.1, the equality does not hold. Thus,T (X 1 ⋯X n | L=j) is not a rank-one tensor.If X p is root node in the causal graph, and S is conditional set that d-separates X p and {X 1 , ⋯X n } \ {X p }, we have T (X p |S) is full rank. The reason is the following.Since P(X p |S)P(S) = P(S|X p )P(X p ) by Bayes' theorem Koch and Koch (1990) , and due to all marginal probabilities are not zero, then we haveT (X p |S) = T (S|X p ) Diag(T (X p ) )Diag(T (S) )† , where † is inverse of matrix, and X p is ancestor of S. By Lemma .D.2, S has a parent variables and hence T (S|X p ) is full rank (one can vectorize the variable set S as a variable). Now, we have T (X p |S) is full rank due to the three matrices on the right are all full rank. Thus, T (X p |S=1) = α 2 T (X p |S=2) = ⋯T (X p |S=r) does not hold, i.e., T (X 1 ⋯X n | S=j) is not a rank-one tensor.Lemma D.4. In a discrete causal graph, for the variable X p , let L p represent the vectorized parent set of X p , and let Des X p denote the set of descendant variables of X p . Under this setup, T (X p |L p ,Des Xp =j) is full rank.Proof. By Bayes' theorem Koch and Koch (1990) , we haveT (X p ,L p |Des Xp =j) = T (X p |L p ,Des Xp =j) Diag(T (L p |Des Xp =j) ) = T (L p |X p ,Des Xp =j) Diag(T (X p |Des Xp =j) ).(16) Since X p and Des X p both are the descendant set of L p , we haveEQUATIONdue to the fact that all marginal distribution probabilities are not zero. Then T (L p |Des Lp ) is full rank, i.e., T (L p |X p ,Des Xp =j) also full rank.Moreover, for any T (L p =i|Des=j) , we haveEQUATIONbecause all marginal distribution probabilities are not zero. Thus, we haveEQUATION)One can see that T (X p ,L p |Des Xp =j) is full rank due to three matrices on the right side being full rank.Proof. The proof is straightforward. In the discrete 3PLSM model, suppose all latent variable has the same state space. Any two observed are d-separated by any one of their latent parents. According to the graphical criteria, the rank of tensor T (X i X j ) is the dimension of latent support.Proof. Proof of Rule 1: In the discrete 3PLSM and suppose the assumption 2.2 ∼ assumption 2.4 holds, if there does not exist a latent variable L 1 that d-separates any pair variables in {X i , X j , X k }, i.e., the rank of tensor T (X i X j X k ) is not r (by Theorem 1), it must be the full-connection structure among latent variables, as shown in Fig. 4 (d ). Otherwise, one can find one latent variable L 1 that can d-separates {X i , X j , X k }, as shwon in Fig. 4 (a) ∼ (c). We will show that, if only consider one of the latent variables of {L 1 , L 2 , L 3 } in Fig. 4 (d) , the tensor of T (X i X j X k ) can not have rank-one decomposition. According to the graphical criteria of tensor rank and r < d i in the definition of discrete LSM, and suppose all latent variables have the same state space, for X i , X j and X k , there is not only one latent variable is conditional set, i.e., but there also is not one latent variable L that d-separates any pair variables in {X i , X j , X k }. Thus, Rank(T (X i X j X k ) ) ≠ r.We aim to show if Rank(T (X i X j X k X s ) ) = r for any X s ∈ X \ {X i , X j , X k } then there exists a latent variable L p that d-separates {X i , ..., X s } and L p is the parent variable of {X i , X j , X k } in the discrete 3PLSM. We first prove it by the contradiction. If {X i , X j , X k } does not share one common latent parent, e.g., L 1 → {X i , X j } and L 2 → {X k }, due to the structure assumption in discrete 3PLSM, there exist X s ∈ Ch L 2 , as shown in Fig. 5 . By the graphical criteria of tensor rank condition and r < d i , one has Rank(T (X i X j X k X s ) ) ≠ r since L 1 or L 2 is not the conditional set that d-separates any pair variable of {X i , X j , X k , X s } (e.g., X k , X s can not be d-separates given L 1 ), which is contrary to the condition Rank(T (X i X j X k X s ) ) = r.Proof. Since C 1 and C 2 are two causal clusters, then the elements in C 1 have only one common latent variable. Without loss of generality, we let L 1 denote the parental latent variable of C 1 . Similarly, L 2 denotes the parental latent variable of C 2 . Since C 1 and C 2 are overlapping, then they have at least one shared element. Let X i denote the shared element of C 1 . then X i has two latent parents L 1 and L 2 , which contradicts with the pure child assumption in the discrete 3PLSM model. This finishes the proof.Proof. Based on Prop. 4.3, one can identify the causal cluster by testing the tensor rank condition (Line 5 ∼ 12). Moreover, the Prop. 4.5 ensures no redundant latent variables are introduced (Line 15). Thus, the causal cluster can be identified by Algorithm 1, under the discrete 3PLSM, with assumption 2.2 ∼ assumption 2.4.Proof. We first prove this result by a specific case and then extend it to a general case result.Proof by Specific case 'If' part: as shown in Fig. 6 , suppose all support of latent space is r and r < d i , d i is the dimension of any support of observed variables. We will show that, for {X 1 , ..., X 6 }, the rank of T {X 1 ,...,X 6 } are r 2 . Let L be the vectorization of joint distributionP(L 3 , L 4 ) with |supp(L)| = r 2 .Since L 2 , L 3 is a conditional set that d-separates all variables in {X 1 , ⋯, X 6 } and there is no other conditional set with smaller support, according to the graphical criteria of tensor rank,Rank(T (X 1 ⋯X 6 ) ) = |supp(L)| = r 2 .'Only if' part: now, we consider the case that if L 1 and L 2 are d-connection (Fig. 6 ). In this case, given P(L 3 L 4 ) (represented by P(L)), T (X 1 X 2 |L=i) cannot be decomposition as outer product of two vectors since the contingency table of T (X 1 X 2 |L=i) is not a rank-one tensor by Markov assumption. That is, L is not a conditional set that d-separates X 1 and X 2 .According to the graphical criteria of tensor rank condition, one can infer that Rank(T(X 1 ⋯X 6 ) ) ≠ |supp(L)| = r 2 .Based on the above analysis, one can see that the conditional independent relations hold if and only if the rank of the tensor equals the cardinality of support of the conditional set.Proof by general case 'if' part: in the discrete 3PLSM model, assume that all latent variables have the same support. For any pair of variables X i and X j that are pure children of L k , it is evident that L k is the only minimal conditional set that d-separates X i from X j . Consider a set of latent variables L p and their corresponding child sets X p1 and X p2 , where each latent variable has at least two child variables included in X p1 and X p2 . The minimal conditional set that d-separates all variables in X p1 from those in X p2 is their common latent parent set L p . Moreover, for two variables X i and X j that do not share a common latent parent, if L p d-separates X i and X j , then L p also d-separates all variables in X p1 ∪ X p2 ∪ {X i , X j }. Since all latent variables have the same support, the minimal conditional set in the graph corresponds to the set with the minimal support. Therefore, by the graphical criteria of tensor rank, Rank(T (X i , X j , X p1 , X p2 )) = |supp(L p )|. As all latent variables share the same state space, we deduce that |supp(Lp )| = r |L p | .'Only if' part: if X i and X j cannot be d-separated by L p , then L p does not constitute a conditional set for X p1 ∪ X p2 ∪ {X i , X j }, under Assumptions 2.2 ∼ 2.4. According to the graphical criteria of tensor rank, Rank(P(X i , X j , X p1 , X p2 )) ≠ |supp(L p )|.D.7 Proof of Theorem 4.9Proof. Such an identification is derived from the original PC algorithm. By Theorem 4.7, given the measurement model, one can test the CI relations among latent variables, when r < d i (remark 1). Thus, the causal structure among latent variables can be identified up to a Markov equivalent class by Algorithm 2 Spirtes et al. (2000) .To extend our theoretical result to the case in which the state space of the latent variable may be different (i.e., r i ≠ r j ). We present the minimal state space criteria by which the state space of the latent variable in the conditional set is identifiable. Theorem E.1 (Minimal state space criteria). In the discrete 3PLSM, suppose Assumption 2.2 ∼ 2.4 holds. For any two observed variables X i and X j , let L i and L j be their latent parent respectively, and let r 1 be the cardinality of supp(L i ) and r 2 be the cardinality of supp(L j ), there is Rank(T (X 1 ,X 2 ) ) = min(r 1 , r 2 ).Proof. In the discrete 3PLSM model, for two observed variables, we have r < x i and any one of the latent parents can d-separate X i from X i . Based on the graphical criteria of the tensor rank condition, one can see that the rank is the latent parent with minimal cardinality of support.Based on the minimal state space criteria, one can directly extend the identification of the discrete 3PLSM to the case where the cardinality of latent support may be different.Proposition E.2 (Identification of causal cluster in different state space). In the discrete 3PLSM, suppose Assumption 2.2 ∼ Assumption 2.4 holds. For three disjoint observed variablesX i , X j , X k ∈ X, then {X i , X j , X k } share the same latent parent if Rank(T (X i ,X j ,X k ,X s ) ) = r for any X s ∈ X \ {X i , X j , X k }, where r = Rank(T (X i ,X j ) ) = Rank(T (X i ,X k ) ) = Rank(T (X k ,X j ) ).Proof. If Rank(T (X i ,X j ,X k ,X s ) ) = r, there exist a variable set S with |supp(S)| = r that d-separates any pair variables in {X i , X j , X k , X s }, according to the graphical criteria of tensor rank condition.In the discret LSM model and r < d i (any support dimension of latent variable is less than the support dimension of observed variable), r = Rank(T (X i ,X j ) ) = Rank(T (X i ,X k ) ) = Rank(T (X k ,X j ) ), we have for any X i , X j ∈ {X i , X j , X k , X s }, the conditional set is one of the latent parent of X i and X j . If X i , X j and X k do not share the common latent parent, without loss of generality, let L 1 be the parent of X i X j and L 2 be the parent of X k , there exist the X s ∈ Ch L 2 such that X k and X s cannot be d-separated given L 1 or X i and X j cannot be d-separated given L 2 . By the graphical criteria of tensor rank condition, Rank(T(X i ,X j ,X k ,X s ) ) ≠ |supp(L 1 )|, or Rank(T (X i ,X j ,X k ,X s ) ) ≠ |supp(L 2 )|. Let r = min(|supp(L 1 )|, |supp(L 2 )|), we have Rank(T (X i ,X j ,X k ,X s ) ) ≠ r if X i , X jand X j are not a causal cluster.One can properly adjust the search algorithm such that the causal cluster can be identified, by the minimal state space criteria. The algorithm is presented as follows (Algorithm 3).Algorithm 3 Identifying the causal cluster (different latent space) Input: Data from a set of measured variables X G Output: Causal cluster C1: Initialize the causal cluster set C ≔ ∅, and G ′ = ∅; 2: Begin the recursive procedure 3: repeat 4:for each X i , X j and X k ∈ X do 5:// Apply the minimal state space criteria 6: r = min(Rank(T {X i ,X j } ),Rank(T {X i ,X k } ),Rank(T {X k ,X j } ) ); 7: if Rank(T {X i ,X j ,X k ,X s } ) = r, for all X s ∈ X \ {X i , X j , X k } then 8: C = C ∪ {{X i , X j ,G = G ∪ {L i → X j |X j ∈ C i }.17: end for 18: return Graph G and causal cluster C.Proposition E.3 (conditional independence among latent variables in different state space). In the discrete 3PLSM, suppose Assumption 2.2 ∼ Assumption 2.4 holds. Let X i and X j be the pure child of L i and L j respectively, X p1 and X p2 be two disjoint child set of the latent setL p with |X p1 | = |X p2 | = |L p |, then L i ⊥L j |L p if and only if Rank(T (X i ,X j ,X p1 ,X p2 ) ) = r, where r = ∏ L i ∈L p |supp(L i )|.Proof. 'If' part: in the discrete 3PLSM, we have r i < d j for any i ∈[k], j ∈ [p],where k is the number of latent variables while p is the number of observed variables. In the causal graph, for X q1 ∈ X p1 and X q2 ∈ X p2 , X q1 , X q2 ∈ Ch(L t ) for ∀L t ∈ L p , we have L t is the only conditional set that d-separates X q1 and X q2 with minimal support dimension. Thus, L p also be the minimal conditional set that d-separates any pair variables in X p1 ∪ X p2 . Now, if X i and X j are d-separated by L p , according to the graphical criteria of tensor rank condition, one have Rank(T (X i ,X j ,X p1 ,X p2 ) ) = |supp(L p )|. Since L p is the joint distribution of latent variable set, we have r = ∏ L i ∈L p |supp(L i )|.'Only if' part: on the other hand, if X i and X j are not d-separated by L p , for example, L i → L j in the causal graph, then L p is not a conditional set that d-separates all pair variables in {X i , X j , X p1 , X p2 }. According to the graphical criteria of tensor rank condition, we have Rank(T (X i ,X j ,X p1 ,X p2 ) ≠ |supp(L p )|, i.e., Rank(T (X i ,X j ,X p1 ,X p2 ) ) ≠ ∏ L i ∈L p |supp(L i )|. This completes the proof.In particular, |supp(L i )| can be identified by their pure child variable, according to minimal state space criteria. An intuition illustration is by mapping the conditional set variable L p to one new latent variable L (i.e., vectorization), the graphical criteria of causal cluster still hold, e.g., {X p1 , X p2 , X i } is a causal cluster that shares a common parent L. However, such a map will exponentially increase the dimension of the latent variable support. One issue will be raised: the observed variable may have a smaller support dimension than the latent variables such that the d-separation relations among latent variables cannot be examined. Thus, it is necessary to study when and how the testability of d-separation holds. The result is provided in Remark. E.4. Remark E.4 (Testability of d-separation). For an n-way tensor T {X 1 ,...,X n } that is used to test the d-separation relations among latent variables, such a CI relation is testable if∏ |L p | j=1 r |L p | j < ∏ n i=1 d i -max(d 1 , ..., d n ).Proof. We prove it by contradiction. If ∏EQUATIONwhich is a smaller rank-one decomposition than L p with support r |L p | . According to the definition of tensor rank and the graphical criteria of tensor rank, we have Rank(T (X1 ⋯X n ) ) = ∏ n i=1 d i - max(d 1 , ..., d n ).That is, no matter whether the conditional independent relations hold given L p , the rank of tensor still be the dimension of the support of P(X 1 ⋯X n-1 ). It means that the CI relations can not be detected.In other words, if the support of the conditional set is more than the dimension of observed variables, then the minimal rank-one decomposition of the joint distribution will lead to P(X 1 , ⋯,X n ) = ∑ {X 1 ,⋯,X n-1 } P(X 1 , ⋯, X n |X 1 , ..., X n-1 )P (X 1 , ⋯, X n-1). Thus, if the increasing of latent state space is less than the sum of tensor dimensions, the CI relations among latent variable are testable. Due to assuming that d > r, the CI relations among latent variables are generally testable when the causal structure is sparse.Actually, our result can be extended to a specific hierarchical structure, by constraining the structure of hidden variables. For instance, consider a hierarchical structure in which each latent variable is required to have at least three pure children (whether latent or observed) and one additional neighboring variable. An illustration of this type of structure is provided in Fig. 7 . Assume that all latent variables have the same dimension of support, and that this dimension is smaller than that of the observed variables. Under these conditions, causal clusters at the bottom level can still be identified, as demonstrated by Proposition 2. For instance, the sets {X 1 , X 2 , X 3 }, {X 4 , X 5 , X 6 }, {X 7 , X 8 , X 9 }, and {X 10 , X 11 , X 12 } are recognized as four distinct causal clusters. The pure measured variables from each cluster can act as surrogates for their corresponding latent parents, allowing the causal cluster learning procedure to be repeated. For example, if X 1 serves as the surrogate for L 2 , and X 4 , X 7 , X 10 as surrogates for L 3 , L 4 , L 5 , then {L 2 , L 3 , L 4 , L 5 } can be identified as a cluster according to the graphical criteria of tensor rank. Thus, the specific hierarchical structure is identifiable by designing the proper search algorithm making use of the tensor rank condition. We will explore these results in future works. L 1 L 2 L 3 L 4 L 5 X 1 X 2 X 3 X 4 X 5 X 6 X 7 X 8 X 9 X 10 X 11 X 12Here, we describe the practical implementation of tensor rank estimation. To alleviate the problem of local optima during tensor decomposition, we initiate the process from multiple random starting points. We then perform the tensor decomposition from each of these points and subsequently select the decomposition that yields the smallest reconstruction error as our final result. The procedure is summarised in the Algorithm 4.Algorithm 4 Practial tensor rank estimation Input: X p = {X i , X j , ..., X n }, iteration number n, threshold ε r and tested rank r Output: Boolean of rank test 1: Initialize the minimal reconstructed error E min = +∞; 2: for i < n or E min ≤ ε do 3:i ← i + 1;T ← non-negative-parafac(T (X p ) , r);5:E ← ∥T (X p ) -T ∥; return True; 13: end if 14: return False.Besides, in the PC-TENSOR-RANK algorithm, to further identify the V-structure among latent variables, the statistic-independent test among latent variables is required, which can be tested by following. Remark G.1 (Statistic independent between latent variables). Give the measured variable X i and X j of latent variable L i and L j , then L i ⫫ L j if Rank(P(X i , X j )) = 1.Proof. Since L i ⫫ L j , we have X i ⫫ X j also hold in the causal graph. We have P(X i X j ) = P(X i )P(X j ) = T (X i ) ⊗ T (X j ) . According to the definition of tensor rank, Rank(T (X i ,X j ) ) = 1.Although the proposed tool is theoretically testable, it still is an approximate estimation of tensor rank by heuristic-based CP decomposition in practice. How to consider a more robust approach to examine the tensor rank still be an open problem in the related literature. It significantly restricts the application scope and performance of our structure learning algorithm. However, we want to emphasize that the main contribution of our work is building the graphical criteria of tensor rank and using it to answer the identification of causal structure in a discrete 3PLSM model.Next, we will show how the CI relations among latent variables can be distinguished by testing the goodness of fit test. Consider a four latent variables structure as shown in Fig. 8 , a chain structure among four latent variables in which each latent variable has two pure observed variables. The data generation process follows the discrete 3PLSM model (see the description in the simulation studies section) and the sample size is 50k. We check the CI relations between any L i , Lj ∈ {L 1 , L 2 , L 3 , L 4 } given L p ∈ {L 1 , L 2 , L 3 , L 4 } \ {L i , L j }.The results are reported on the right side of Fig. 8 , in which each red point represents a CI test result, e.g., the second point in the graph represents to test L 2 ⫫ L 4 |L 1 by examining Rank(T (X 3 ,X 7 ,X 1 ,X 2 ) ) = 2. One can see that the p-value returned by the goodness of fit test is lower than 0.05, which means that we will tend to reject the null hypothesis, i.e., Rank(T (X 3 ,X 7 ,X 1 ,X 2 ) ) ≠ 2. By sorting all CI test results, one can see that the true CI relations can be identified by setting the significant level to be 0.05. In this section, we provide the information required to reproduce our results reported in the main text. We further conduct additional simulation experiments to validate the efficiency of the proposed algorithm (Appendix E).We first give a details definition of evaluation metrics. Specifically, the performance of causal cluster is evaluated by following scores for the output model G out from each algorithm, where the true graph is labelled G:• latent omission, the number of latents in G that do not appear in G out divided by the total number of true latents in G;• latent commission, the number of latents in G out that could not be mapped to a latent in G divided by the total number of true latents in G;• mismeasurement, the number of observed variables in G out that are measuring at least one wrong latent divided by the number of observed variables in G;Moreover, we use the following metric to evaluate the performance of causal structure among latent variables:• edge omission (EO), the number of edges in the structural model of G that do not appear in G out divided by the possible number of edge omissions;• edge commission (EC), the number of edges in the structural model of G out that do not exist in G divided by the possible number of edge commissions;• orientation omission (OO), the number of arrows in the structural model of G that do not appear in G out divided by the possible number of orientation omissions in G;These evaluation indicators are derived from Silva et al. (2006) .Next, we give a concrete implementation of baseline methods.BayPy: The Bayesian Pyramid Mode (BayPy) is a discrete latent variable structure learning method that assumes the latent structure is a pyramid structure and the latent variable is binary. We use the implementation of Gu and Dunson (2023) . We set the iteration parameter to 1500 and set the search upper bound of the number of latent variables to 5.The latent tree model, is a classic method for learning gaussian or binary latent tree structure. We use the implementation from Choi et al. (2011) . Specifically, we use the Recursive Grouping (RG) Algorithm in Choi et al. (2011) (since it has better performance), and use the discrete information distance to learn the structure of the discrete 3PLSM model.The Building Pure Cluster (BPC) algorithm Silva et al. (2006) is a classic causal discovery method for the linear latent variable model. We use the implementation from the Tetrad Project package3 .Non-negative CP decomposition: To perform non-negative CP decomposition in our algorithm, we use the implementation from the python package, tensorly4 , and set the maximum iteration parameter to 1000, the cvg criterion parameter to "rec_error".Data Generation: To generate the probability contingency table or conditional probability contingency table for latent variables and observed variables in our simulation studies, we use the implementation from the python package, pgmpy5 . The package provides the function to generate observed data according to the probability contingency table.Finally, we aim to demonstrate the correctness of our methods in handling cases involving latent variables with varying state spaces. Specifically, we consider the structure model with star structure and the SM 3 structure, and the measurement model with M M 1 . The data generation process follows the description in the main context and we let the support of latent variable L 1 , L 2 to be {0, 1} and the support of latent variable L 3 , L 4 to be {0, 1, 2}, for simulating the case that latent variable has different latent support. Besides, the support of the observed variable is {0, 1, 2, 3}. In our implementation, the significant levels for testing the rank of the matrix and tensor are set to 0.005 and 0.05, respectively. The coefficient of probability contingency tables is generated randomly, ranging from [0.1, 0.8], constraining the sum of them to be one.The results are presented in Table 4 and Table 5 . The performance of our method appears superior in scenarios where latent variables have differing state spaces. This improvement is attributed to the reduction in the frequency of higher-order tensor rank testing, facilitated by evaluating the consistency of ranks such as Rank(T (X i , X j )) = Rank(T (X i , X k )) = Rank(T (X k ,X j ) ). In contrast, the BayPy approach underperforms in latent structure learning, likely due to its assumption of a pyramid structure with a top-down directionality and no peer-level connections among latent variables. Additionally, the Latent Tree Model (LTM) shows weaker performance in cluster learning, possibly because it was originally designed to handle only binary discrete variables. 0.09(3) 0.20(4) 0.23(5) 0.96(10) 0.00(0) 0.20(4) 0.00(0) 0.00(0) 0.03(1) 0.18(4) 0.23(5) 0.00(0) Star + M M 1 10k 0.06(2) 0.17(3) 0.13(4) 0.96(10) 0.00(0) 0.15(3) 0.00(0) 0.00(0) 0.00(0) 0.15(3) 0.13(4) 0.00(0) 50k 0.00(0) 0.13(3) 0.10(3) 0.93(10) 0.00(0) 0.15(3) 0.00(0) 0.00(0) 0.00(0) 0.13(3) 0.10(3) 0.00(0) 5k 0.12(3) 0.33(7) 0.55(10) 0.96(10) 0.00(0) 0.30(6) 0.00(0) 0.00(0) 0.06(2) 0.30(7) 0.55(10) 0.00(0) SM 3 + M M 1 10k 0.06(2) 0.26(5) 0.50(10) 0.93(10) 0.00(0) 0.20(5) 0.00(0) 0.00(0) 0.00(0) 0.19(5) 0.50(10) 0.00(0) 50k 0.03(1) 0.20(4) 0.50(10) 0.93(10) 0.00(0) 0.15(4) 0.00(0) 0.00(0) 0.00(0) 0.11(4) 0.50(10) 0.00(0) 0.00(0) 1.00(10) 0.26(8) 1.00(10) 0.10(1) 0.00(0) 0.00(0) 0.00(0) 0.10(1) 1.00(10) -1.00(0) Star+M M 1 10k 0.00(0) 1.00(10) 0.23(6) 1.00(10) 0.00(0) 0.02(1) 0.0(0) 0.00(0) 0.00(0) 1.00(10) -1.00(0) 50k 0.00(0) 1.00(10) 0.10(3) 1.00(10) 0.00(0) 0.00(0) 0.00(0) 0.00(0) 0.00(0) 1.00(10) -1.00(0) 5k 0.15(3) 1.00(10) 0.16(6) 1.00(10) 0.10(1) 0.00(0) 0.00(0) 0.00(0) 0.00(0) 0.00(0) -0.00(0) SM 3 + M M 1 10k 0.05(1) 1.00(10) 0.13(4) 1.00(10) 0.01(1) 0.00(0) 0.00(0) 0.00(0) 0.00(0) 0.00(0) -0.00(0) 50k 0.00(0) 1.00(10) 0.10(3) 1.00(10) 0.00(0) 0.00(0) 0.00(0) 0.00(0) 0.00(0) 0.00(0) -0.00(0)We first briefly present the results from two real datasets. The first is the political efficacy dataset, collected by Aish and Jöreskog (1990) through a cross-national survey designed to capture information on both conventional and unconventional forms of political participation in industrial societies. This dataset includes 1719 cases obtained in a USA sample. The second dataset, referred to as the depress dataset, is detailed by Jöreskog and Sörbom (1996) and comprises twelve observed variables grouped into three latent factors: self-esteem, depression, and impulsiveness, with a total of 204 samples. Our algorithm learns the correct causal structure (including the measurement model and the structure model) for both datasets by first identifying the dimension of latent support as two in the political efficacy dataset and four in the depress dataset.For the political efficacy data Aish and Jöreskog (1990) , by identifying the support of latent variable to be two, one can identify the causal cluster {'NOCARE', 'TOUCH', 'INTEREST'}, {'NOSAY', 'VOTING', 'COMPLEX'}. These clusters correspond to the latent variables 'EFFI-CACY' and 'RESPONSE', respectively. In our implementation, we set the significance level to 0.0015. The result is aligned with the ground truth provided in Jöreskog and Sörbom (1996) .For the depress dataset, the ground truth structure Jöreskog and Sörbom (1996) includes three latent factors: Self-esteem, Depression, and Impulsiveness, with the corresponding observed clusters:• {'SELF1', 'SELF2', 'SELF3', 'SELF4', 'SELF5'};• {'DEPRES1', 'DEPRES2', 'DEPRES3', 'DEPRES4'};• {'IMPULS1', 'IMPULS2', 'IMPULS3'}.In our implementation, we utilize a bootstrapping resampling approach to enhance the statistical properties of the data. Following the extended results outlined in Appendix E, we first identify the dimension of support for the factors Self-esteem and Depression as four, and set the dimension of support for Impulsiveness at three. The significance level is set to 0.025. The results of our algorithm are presented as follows.• {'SELF1', 'SELF2', 'SELF3', 'SELF5'};• {'DEPRES1', 'DEPRES3', 'DEPRES4'};• {'IMPULS1', 'IMPULS2', 'IMPULS3'}.One can see that our algorithm can learn three causal clusters corresponding to three latent factors. Such a result shows that our method finds all latent variables from the depress data. In the latent structure learning process, the PC-TENSOR-RANK algorithm outputs the fully connected graph of the three latent factors, indicating the absence of conditional independence (CI) relations between them. One possible reason is there may be more potential factor interaction structure Salles et al. (2024) .The proposed Tensor Rank Condition identifies the causal structure of latent variables in the discrete LSM model. Our theoretical results extend the identification bounds of causal discovery with latent variables and expand the application scope of latent variable models. For instance, in psychology and social sciences, our algorithm can learn the causal structure of the latent factors of interest from observed data (e.g., survey data), enabling researchers to better understand the causal mechanisms behind them. Additionally, based on the discovered causal relationships, one can design more effective intervention strategies to improve mental health or stimulate the market economy.The proposed method can hardly be applied to the high-dimensional discrete data. Therefore, how to relax this restriction and make it scalable to high-dimensional real-world datasets would be a meaningful future direction.https://github.com/cmu-phil/tetradhttps://github.com/tensorly/tensorlyhttps://github.com/pgmpy/pgmpy 


Decision: This paper studies learning latent variable structures under discrete data. This problem is well-studied in the literature, with numerous identifiability result. During the discussion, it was pointed out by Reviewer tR91 that many results in the submission follow from previous work by Kivva et al that is not cited and which is less restrictive. This negates some claim by the authors, for example, that "few identifiability results exist and are mostly only applicable in strict case".

There was an extensive back and forth. In the end, reviewers agreed that in spite of the misleading presentation of prior work, this paper indeed introduces some new ideas, namely, a statistically testable tool that connect rank constraints and d-separation. To quote the discussion:

"It is possible that the proposed method is more statistically robust under the stronger assumptions of this paper, but this is not how this paper describes its contribution."

I agree with this point, and the paper could be rejected on this. **I am willing to recommend accept if the authors (significantly) revise the paper to properly situate their contributions in light of this (and other, see [1-3] below) prior work and also clarify their contributions according to the discussion with Reviewer tR91.** 

[1] Causal Discovery under Latent Class Confounding https://arxiv.org/abs/2311.07454 

[2] Identifiability of Product of Experts Models https://arxiv.org/abs/2310.09397 

[3] Causal Inference Despite Limited Global Confounding via Mixture Models https://arxiv.org/abs/2112.11602

Reviews: review: paper_summary: paper_summary: This paper studies the problem of learning latent variable structure in the discrete LSM measurement model. My understanding is that the paper operates under the following assumptions:
1) All latent variables are discrete 
2) There are no connections between observed variables (i.e. observed variables are independent when conditioned on latent variables
3) In the unknown causal structure graph, each observed variable has exactly one latent variable parent.
4) The joint probability distribution of observed variables is fully known, and there is no noise in the measurement.
5) Each latent variable has at least three pure variables as children.
6) Other technical assumptions.

The authors show that under such assumptions the unknown causal structure can be recovered from an algorithm that studies tensor rank conditions on contingency tables for an observed variable set.
strength_weakness: strength_weakness: I am a bit concerned about the novelty of the proposed results and methodology. In particular, [1] seems to obtain a stronger result under similar, if not weaker, assumptions, and this paper does not cite [1].

[1] proposes a structure learning algorithm for measurement model with discrete latent variables, under what seems to be a weaker set of assumptions. In particular [1] does not require each latent variable to have at least three pure children and does not require that each observed variable has only one latent parent. Those assumptions seem quite strong. 

The technique used in [1] to identify causal structure is also similar in flavor, and also relies on studying the rank of joint probability tensor (through numbers k(S)).

Considering that [1] operates under a significantly more general setup while relying on similar techniques and ideas, could the authors please clarify what is the main novelty of this paper compared to [1]? 

[1] Learning latent causal graphs via mixture oracles
B Kivva, G Rajendran, P Ravikumar, B Aragam - Advances in Neural Information Processing Systems, 2021
questions: questions: see above

-----
During rebuttal score was increased 3 --> 4
limitations: limitations: na
paper_summary: paper_summary: This paper studies the problem of learning causal structures among latent variables from discrete observational data. The author presents a tool, termed the tensor rank condition, to establish the connection between rank constraints of the probability tensor and d-separation relations in the causal graph. The proposed tool appears simple and effective. Based on the tensor rank condition, the author proposes a two-stage algorithm that first learns the causal clusters to identify latent variables and then tests the conditional relations among latent variables using their measured variables. The proposed algorithm extends the identification bound of discrete latent variable models, and the experimental results demonstrate the efficiency of the proposed methods.
strength_weakness: strength_weakness: 1. For the sufficient observation assumption, it seems that the cardinality of the observed variable support can be equal to the cardinality of the latent support, as discussed in Remark F.4. Could you clarify this?

2. Why is the Three-Pure Child Variable Assumption required? In my opinion, the tensor rank condition can test the d-separation relations between only two observed variables, as shown in Figure 1. Thus, one can learn the causal cluster from a two-pure child variable assumption. Please correct me if I am wrong. If this assumption does not hold, what happens to the output of your algorithm?

3. In Proposition F.3, $r$ is easily confused with the concept of the cardinality of the support of a single latent variable. It is recommended to change the expression like $\tilde{r}$.
questions: questions: typo: In Figure 2(b), LVM should be LSM.
limitations: limitations: see weakness
paper_summary: paper_summary: This paper aims to learn latent causal models with discrete random variables. To this end, a tensor rank condition on contingency tables of observed variables is used. Specifically, the paper establishes connections between the d-separation of the observed variables and the “tensor rank” of the said random variables. Subsequently, this property is leveraged to construct an algorithm that learns (i) the measurement model, that is the connections from the latent variables to observed variables, and (ii) the structure model (the edges between the latent variables) up to Markov equivalence class. The main structural assumptions for the results are purity (no edges between the observed variables) and three observed children per latent node, and other standard causal assumptions, e.g., faithfulness, are adopted in the paper.
strength_weakness: strength_weakness: - *Structural limitations are quite restrictive*. Specifically, the purity assumption that there are no edges between the observed variables is a serious limitation. On one hand, this is understandable as the existing works usually have similar or stronger restrictions. On the other hand, having partial results for the cases where this assumption is violated would have made the paper significantly stronger. I see that the paper touches on this via an example and leaves it as future work, nevertheless, it’s a big limitation of the current paper.
- On a related note, the assumptions are not convincingly justified. For instance, three-pure children assumption is just taken for granted without proper discussion (I acknowledge the reference to similar work, please see the questions section). 
- This is relatively a minor concern: I enjoyed the flow of the paper, but the writing could be improved for sure. I elaborate on this in questions.
questions: questions: **Critical points on assumptions**
- *Allowing edges between observed variables*: It seems like extending the results to impure structures would require a different approach. Because the propositions -- the backbone of finding the measurement model -- are very specific to the purity assumption. In the discussion section, an example is provided and the extension is left for future work. I think you can be more open about it, e.g., what are the challenges, what are the missing pieces? For instance, in the example in Section 7, are you also able to determine the lack of edges between any $(X_i,X_j)$ pair except $(X_4,X_5)$?
- *Structural constraints in the literature*: I think you need to be more direct and provide exact requirements/structural constraints and results. For instance, if I recall correctly, Cai et al. and Xie et al. require 2 pure children per latent whereas this paper requires 3 pure children (I am aware that those papers are for linear latent models). Can you elaborate on the similarities and differences between the roles of these assumptions? On key difference from related work, L89 says that the are no constraints on the latent structure. Is this difference w.r.t. binary latent variable case (Gu and Dunson (2023) and Gu (2022)) or all the previous work including the linear latent variable models?
- In Appendix D, the full rank assumption (Assumption 2.4) discussion is informative and reasonable. However, a similar discussion for the other assumptions is missing. For instance, in the example in Section 7, the possibility of working on an impure structure is explained but failure cases (and why they happen) are not explained. I think it’s equally important to explain those cases. On a related note, the role of 3 pure children assumption is not discussed in the paper (please point out if I missed it). 
- *Support of latent variables*: The paper says that *”For simplicity, we focus on the case where all latent variables have the same number of categories, with extensions provided in Appendix F”*. Some clarification can be helpful. I skimmed through Appendix F, and it seems like the extension to “latent variables with different numbers of categories” is immediate without extra assumptions. If this is indeed the case, then I suggest the authors explicitly state it in the main paper. If the extensions require more assumptions and/or more sophisticated techniques, again, be more clear about it so the reader can understand if it’s a limitation or not.


**Experiments related**:

- I see that the definitions of metrics are in Appendix I (which should be referred to in L288 to help the reader). It would have been nicer to squeeze them into the main paper.  
- Adding a small section for real data applications (Section 6) without sufficient details does not add much value. I think it can be safely moved to the appendix, where the details are given, which would also open space for a more self-contained simulation section.
-  I think your method should be able to handle an arbitrary number of children as long as there are at least 3. So, you could have tested different sizes for different latent variables instead of a fixed number of 3 or 4. For instance, each latent variable can have at least 3, at most 6 observed variables, which could have allowed you to evaluate whether there is a difference between the performance in learning measurement and structure models.
- For such sparse and small graphs, 50k samples are a bit too aggressive. Perhaps starting from 1k would show the limits of the approach and help us to understand the performance better. For instance, at “mismeasurements” metrics, even 5k sample seem to work well, it would have been interesting to see what is the limit.

**Relatively minor notes**:
- *Definition 2.1 (Discrete LSM)*: Is this a proper name? I don’t like calling the specified model “discrete LSM” simply because it is too general. Assumptions are clearly stated in the definition, but calling the model just discrete LSM, especially under the purity and three-pure child assumptions is not great,  especially when we think about the potential future work and positioning of this paper in the literature.
- *Theorem 4.7*: Please be careful when using $p$ in notations, $\mathbf{X}_p$ and $\mathbf{L}_p$ notations are a bit confusing. At first reading, $p$ reads as a set, e.g., in Example 4.8, $\mathbf{X}_p$ implies $p=\\{1,10,4,5,7,8\\}$, but $\mathbf{L}_p=\\{L_2,L_3\\}$, so it is not a set notation.
- *Conclusion Section 8*: Overall, I liked this conclusion. That being said, being more direct and recalling the main structural assumptions would have been good. For instance, the limitations paragraph in Appendix K is very clean — I appreciate it. Since it’s just 2.5 lines, I’d suggest to include in the main paper

**Typos etc.**:
- Prop 4.3: I think Rule 2 statement is missing “if”. Also, why $L_i$ instead of $L$?
- Theorem 4.7: varaible
- Theorem 4.9: TESNOR
- L177: missing period
- L800: TENSKR
- CP decomposition: please spell out at the first appearance
- Figure 8: make the markers larger, please.
limitations: limitations: Limitations are mostly addressed. I suggest the authors to see my comments on questions to further clarify them.
paper_summary: paper_summary: This study develops new methods for identifying causal structures in discrete latent variable models using rank constrain. By leveraging this nontrivial algebraic property, the authors propose criteria and algorithms for discovering hidden causal relationships. They validate their approach through simulations.
strength_weakness: strength_weakness: I wonder if some assumptions are a bit strong such as the faithfulness assumption and the three pure child assumption and I wonder how they play into practical scenarios.
questions: questions: 1. How does this paper compare to works like [1] where rank constraint is also used in a non-linear setting?

[1] Kong, Lingjing, et al. "Learning Discrete Concepts in Latent Hierarchical Models." *arXiv preprint arXiv:2406.00519* (2024).
limitations: limitations: See weakness.

Comments: title: Many thanks for your question
Thanks for the clarification in helping us algining this issues
Thank you very much for your positive comment
Thank you very much for your response
Thank you for your response
Thanks for you kind response
comment: We are very grateful for your thoughtful comments, which we basically agree with.  Below please let us share some thoughts.

In contribution [1], the authors show that to learn the measurement model, only the $k(S)$ in the mixture oracle is required.

In our previous response, we mentioned that recovering the complete information about the mixture oracle generally requires strict assumptions--we hope you also agree with it, since it involves identifying more parameters of the mixture oracle.

Regarding your point about the identification of the measurement model under a weaker assumption, we acknowledge that it is indeed possible since only $k(S)$ is needed. We appreciate this insight. At the same time, we would like to highlight that our method offers a more statistically robust approach for achieving this under the three pure children assumption, which you also pointed out. This assumption often holds in practice, especially when data is gathered through questionnaires, which is common in fields including social science, psychology, and healthcare.

That being said, we feel that our work goes beyond just this aspect. As you mentioned, we provide a testable tool that offers a stronger ability to discover causal structures. Additionally, it's nice to note that, given the measurement model, the causal structure among latent variables is identifiable with only two pure children needed for each latent variable. We believe this is another major contribution of our work.

We are very grateful for your patient response. Please let us know if you have any further questions--we greatly appreciate the opportunity to discuss with you.
>  We would like to argue that by fixing X_i and looking at triples with different X_j, X_k, we may not be able to figure out that the triple is incorrect.

I explained above how this can be done by taking convex hull of vectors in the first mode of the decomposition. I think the authors in the subsequent paragraph refute something I did not claim. 

>However, the identification approach in this work relies on the existence of a mixture oracle, and estimating the mixture oracle is a non-trivial task.

Performing the steps I described above provides the desired mixture oracle and gives identifiability results out of the box.

> We introduce a statistically testable tool, termed the tensor rank condition , which establishes a connection between rank constraints and d-separation relations within a discrete model.

*I agree that this is a novel and an interesting contribution of this paper!* 

It is nice to see how this can be used for the identification of the structure. However, as I outlined above, the identifiability results for the measurement model essentially follow from weaker assumptions from prior work. It is possible that the proposed method is more statistically robust under the stronger assumptions of this paper, but this is not how this paper describes its contribution.
**Dear Reviewer tR91,**

Thank you for your effort and your time. We would like to argue that by fixing $X_i$ and looking at triples with different $X_j, X_k$, we may not be able to figure out that the triple is incorrect.

For example, consider a simple structure $L_1 \to L_2 \to L_3$, where each latent varaible has three pure children, corresponding to $X_{123}$, $X_{456}$, and $X_{789}$, respectively. When we fix $X_1$ and look at any $X_j, X_k \in \overline{X_1}$, one can see that there is still a minimum rank decomposition with d components (where d represents the cardinality of latent support). This is because any three observed variables can be d-separated by only one latent variable in this structure (see the proof of Prop. 4.3).  For instance, let $X_j=X_4$ and $X_k = X_7$, which is the example in the previous response. Thus, we cannot check if the basic $P(X_j|L) $ is actually $P(X_j|Pa(X_j))$ from the decomposition.


Please let us take this opportunity to highlight our contributions, in order to situate this work in the rich literature:

1. We introduce a statistically testable tool, termed the  *tensor rank condition* , which establishes a connection between rank constraints and d-separation relations within a discrete model.
2. Utilizing the tensor rank condition, we achieve the identification of the measurement model under the three pure children assumption.
3. Furthermore, based on the tensor rank condition, we complete the identification of the structural model, requiring only two pure children for each latent variable.

In [1], the authors leverage information from a mixture oracle and perform tensor decomposition to identify the measurement model, recovering the distribution to learn the latent variable structure. However, the identification approach in this work relies on the existence of a mixture oracle, and estimating the mixture oracle is a non-trivial task.

Most importantly, we want to emphasize that the tensor rank condition is not restricted to any specific mixture model and does not rely on information from such models. The discrete causal structure can be discovered using the tensor rank condition, which allows for identifying edges between observed variables and even permits causal directions from observed to latent variables. We believe that the tensor rank condition opens up new research directions and offers promising avenues for developing search algorithms for latent variable researchers.


Moreover, as we discussed in the general response, the three pure children assumption is merely a sufficient condition for identifying the measurement model by tensor rank. We also explored potential extensions to more general conditions, such as impure structures or hierarchical structures, for identifiability. We discussed that the tensor rank condition has the capacity to handle these cases, which we outline as directions for future work.


If you have further feedback, we hope to read it and hope for the opportunity to respond to it.  We highly appreciate your engagement in the discussion.
I am grateful for your response.

> However, we want to argue that without knowing the structure information we will have different basis when we probe at different triples and we do not know which one is the "correct".

It is actually easy to identify the "correct" one. Let's fix $X_i$ and look at triples with different $X_j, X_k$. If minimum rank decomposition has more than d components we can immediately refute triple as incorrect, which handles your concern about uniqueness of the decomposition. By Kruskal's theorem, those triples that admit decomposition of rank at most d will have a unique decomposition. Decompose all such tensors and compile a list of first-mode components for each of them.
Note that $P(X_i|L = \ell) = \sum_{t} P(X_i|L = \ell, Pa(X_i) = t) P(Pa(X_i) = t| L = \ell) =  \sum_{t} P(X_i| Pa(X_i) = t) P(Pa(X_i) = t| L = \ell)$ and all $P(Pa(X_i) = t| L = \ell)$ are non-negative. This means that each vector of the form $P(X_i|L = \ell)$ belongs to the convex hull of the "correct" set of vectors $P(X_i| Pa(X_i) = t)$. Since all P(X_i| Pa(X_i) = t) are linearly independent by assumption 2.4, they are the unique "defining directions" of the convex cone formed by all first mode components of tensor decompositions of $P(X_i, X_j, X_k)$ with a fixed $i$. Note also that there is no ambiguity about the direction (sign) of the vectors in the decomposition, as we expect every vector participating in the decomposition to have positive entries. 
Note that no structure information is used, and one do not need to assume that all latent variables have the same support, etc.  

> Moreover, we want to show that, without the structure information, $Pa(X_i|Pa(X_i))$ may not be identifiable due to violation of the unique decomposition condition.

By assumptions of this paper, the triples of variables $X_i, X_j, X_k$ which are of interest to construct "mixture oracle" have unique decomposition of rank at most $d$ ($d$ here can be replaced with the size of the support of observed variables, so knowledge of $d$ is not needed). All other triples can be ignored.    

Please let me know if you have any questions.
Thanks for the clarification in helping us algining this issues.
It seems that you treat the $Pa(X_i|Pa(X_i))$ as the basis, thereby the tensor $P(S|Pa(S))$ can be recovered.

However, we want to argue that without knowing the structure information we will have different basis when we probe at different triples and we do not know which one is the "correct" basis (here $Pa(X_i|Pa(X_i))$) we are looking for. 

For example, when there exists a minimum rank decomposition for $X_i, X_j, X_k$, the basic can be equal to $Pa(X_j|L_i) \neq Pa(X_j|Pa(X_j))$ (see the example in the previous response). In this case, we do not know if $Pa(X_j|L_i)$ is $Pa(X_j|Pa(X_j))$.


Moreover, we want to show that, without the structure information, $Pa(X_i|Pa(X_i))$ may not be identifiable due to violation of the unique decomposition condition.

For example, consider a structure with three observed variables $X_i, X_j, X_k$ and $L_1, L_2, L_3$ are their latent parent, respectively. To obtain the minimum rank decompositions of $X_i, X_j, X_k$ for estimating $Pa(X_i|Pa(X_i))$, it must satisfy the Kruskal's condition, that is, $Rk(P(X_i|L))+Rk(P(X_j|L))+Rk(P(X_k|L)) >= 2r+2$, where $r$ is the cardinality of latent support L, where $L = \[{Pa(X_i), Pa(X_j), Pa(X_k)\}]$. However, when the cardinality of the latent and observed support both are $d$, one can see that $Rk(P(X_i|L))+Rk(P(X_j|L))+Rk(P(X_k|L)) = 3d < 2d^{3}+2$. Therefore,  $Pa(X_i|Pa(X_i))$ cannot be recovered due to a violation of the Kruskal condition. And it also violate the condition of 2K-1 strongly separate variables in [2], a sufficient and necessary condition for identifying the parameters of a discrete mixture model.


We are very grateful for your patient response. Please feel free to reach out if you have any further questions.
I believe authors misunderstood points 3 and 4 in my comment above. I do not claim that (*) is obtained via minimal rank decomposition, as authors aim to refute in their response. 3 and 4 above use that any vector has a unique decomposition in a basis in a linear space.

To give a simplified example: Let $a_1, a_2 \in R^n$ be linearly independent and $b_1, b_2 \in R^m$ be linearly independent, then vectors $a_1\otimes b_1, a_2\otimes b_1, a_1\otimes b_2, a_2\otimes b_2$ are all linearly independent (as vectors in $R^{nm}$) and for a vector $T = \alpha_1 a_1\otimes b_1 +\alpha_2 a_2\otimes b_2 +\alpha_3 a_3\otimes b_3$ one can uniquely recover this decomposition if $a_i$ and $b_i$ are known, even if it tensor has smaller rank (say, 2).  

One can recover vectors $P(X_i|pa(X_i))$ by looking at minimum rank decompositions of triples of variables and use it to recover necessary decompositions of $P(S|Pa(S))$ (and hence get mixture oracle), as I outlined above.

Please feel free to reach out if something is still not clear.
Dear Reviewer hs7U,

Thank you very much for your positive comment! We believe our paper is improved as a direct result of your comments.

Sincerely,

Authors
Thanks for the detailed response. My questions have been well addressed. As far as I know, the tensor rank condition is the first to establish the connection between algebraic constraints and d-separation in discrete causal models. Based on this, the identification algorithm for discrete LSM is both simple and effective. I believe these results are meaningful to the NeurIPS community. I raise my score accordingly.
Thank you very much for your response. Please allow us to take a little time to clarify further.

We want to argue that $supp(Pa(S))$ cannot be directly estimated even under Assumption 2.4 and the three-pure children assumption when the latent structure is unknown and the subset $S$ has different latent variables. 

We agree that in your example, when we *known* the three observed $X_i$, $X_j$ and $X_k$ is the pure children of $L$, the $supp(Pa(S))$ can be recovered through the tensor decomposition. However, when $S$ has different latent variables and the *unknown* causal structure, the minimum rank tensor decomposition does not necessary correspond to the $supp(Pa(S))$ and it will produce multiple equivalence class as we discussed in the proof of Prop. 4.3 in our paper, such that $supp(Pa(S))$ can not be identified.  



Consider the structure in Fig. 4(c) in our paper, without loss generality, let $L_2 \to L_1, L_2 \to L_3$, $L_1 \to X_j, L_2 \to X_i$ and $L_3 \to X_k$. Let $S = \{X_i, X_j, X_k\}$. As such, we will have the following decomposition:


$$\begin{align}P(S) =& \sum_{i = 1} ^{|supp(L_1)|} \left( \sum_{L_2} P(X_j, L_2|L_1=i) \right) \otimes P(X_i|L_1=i) \otimes \left( \sum_{L_3} P(X_k, L_3|L_1=i) \right) \cdot P(L_1=i)\\\\
=& \sum_{i = 1} ^{|supp(L_1)|} \left( \sum_{L_2} P(X_j, L_2|L_1=i) \right) \otimes P(X_i|Pa(X_i)=i) \otimes \left( \sum_{L_3} P(X_k, L_3|L_1=i) \right) \cdot P(L_1=i)
\end{align}$$
where the vectors $\sum_{L_2} P(X_j, L_2|L_1=i)$ and $\sum_{L_3} P(X_k, L_3|L_1=i)$ also are linear independent. In this case, we can find a unique decomposition (based on Kruskal's theorem), but not follow the form of (*), i.e., $P(S) \ne \sum_{\ell \in supp(Pa(S))} P(S|Pa(S) = \ell) P(Pa(S) = \ell)$.


Moreover, in our work, the conditional independence between latent variables can be tested by the tensor rank condition (Theorem 4.7), without assuming the existence of the mixture model and recovering the distribution of latent variables.

We are very grateful for your patient response. Please feel free to reach out if you have any further questions.
I am grateful to the authors for their detailed and constructive rebuttal. I am still concerned about the novelty of the results of this paper as compared to [1]. Let me try to provide some more details regarding my concern.

The Mixture Oracle in [1] is essentially only used to count the number of components $k(S)$ in the "mixture decomposition" in 

(*) $P(S) = \sum_{\ell\in supp(pa(S))}P(S|pa(S) = \ell)P(pa(S) = \ell)$, 

or in other words to estimate the size of the $supp(Pa(S))$ if assumption 2.4.a from [1] is added, where S is a subset of observed variables. See eq. (2-3) in [1] and Remark 2.6.

> We would like to argue that the requirement of the Mixture Oracle may lead to a weaker identifiability result than ours due to the strict conditions in obtaining the Mixture Oracle

The Mixture Oracle in the setup of this paper can be easily obtained from Assumption 2.4 (in this paper) and the assumption about three pure children made in this paper. To see this, 
1) observe that $P(S|L = \ell)$ is a rank-1 tensor of the form $\sum_{\ell \in supp(pa(S))}\bigotimes_{X_i \in S}P(X_i|pa(X_i) = \ell_j)$
2) Let $X_i, X_j, X_k$ be pure children of vertex $L_t$, then by assumption 2.4 columns $P(X_i|pa(X_i))$ can be recovered as first modes of minimum rank tensor decomposition of $P(X_i, X_j, X_k)$.
3) Observe that if vectors in each of sets A and B are linearly independent, then all vectors $a\otimes b$ for $a\in A, b\in B$ are linearly independent. Applying this recursively, we get that all vectors $\bigotimes_{X_i \in S}P(X_i|pa(X_i) = \ell_j)$ are linearly independent, and we know the full set of those vectors from 2). Therefore, we can find unique decomposition (*) and count the number of components with non-zero coefficients (in practice, coefficients less than some threshold).     
4) note that the decomposition in 3) is not a minimum rank decomposition, as was also pointed out by the authors in the rebuttal, so Theorem 3.3 cannot be used to estimate the number of components.

I also suspect that the desired mixture oracle should exist under significantly weaker assumptions than what I outlined above; in particular, using three pure children seems to be an overkill, but I have not spent time trying to simplify these assumptions.

----

Based on the above, Theorem 3.3 appears to be the key novel result of this paper. The algorithm in the sections that follow operates under significantly stronger assumptions than [1]. Theorem 3.3 is an exciting result and, indeed, may provide a more robust approach than what [1] offers. That said, I still think that the assumptions used in this paper are somewhat strong compared to other results in the literature, as also pointed out by other reviewers.

 After the author's rebuttal, I will increase my current score to 4.
Dear Reviewer Upr4,

Thank you for your positive comment. We believe our paper is improved as a direct result of your comments.

Sincerely,

Authors
Thanks for your rebuttal. I will keep my score leaning towards acceptance.
Dear Reviewer Snze,

We are glad that most of your concerns have been addressed, and we are really grateful that you raised your score to “weak accept”.

Sincerely,

Authors
I thank the authors for the well-written rebuttal, it addressed my questions and confusions clearly. I increased my score accordingly to “weak accept”.
This rebuttal deserves an explanation for why I am not giving a higher score: It's mainly because I think the considered setting is still somewhat limited — even if the assumptions are justified within the context of the paper’s results.