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 2024 poster (2024)
Keywords: Causal Discovery
Identification
Latent variables
Primary area: causal_inference

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.

Learning Discrete Latent Variable Structures with Tensor Rank Conditions
Zhengming Chen 1.2 Ruichu Cai Feng Xie Jie Qiao',
Anpeng Wu 2.4 Zijian Li", Zhifeng Hao Kun Zhang 2.6.+
1. School of Computer Science, Guangdong University of Technology
2. Machine Learning Department, Mohamed bin Zayed University Artificial Intelligence
3. Department of Applied Statistics, Beijing Technology and Business University
4. Department of Computer Science and Technology. Zhejiang University
5. College of Science, Shantou University, Shantou, Guangdong, China
6. Department of Philosophy, Carnegie Mellon University
Abstract
Unobserved discrete data are ubiquitous in many scientific disciplines, and how 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 striet constraints on latent structures, which fail address cases in discrete data involving non-linear relationships or complex latent structures. To achieve this, we explore tensor rank condition on contingency tables for an observed variable set X,, showing that the rank is determined by the minimum support of specific conditional set (not necessary in X,) that d-separates all variables in Xp. By this, one can locate the latent variable through probing the rank 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. Our results elegantly expand the application scope of causal discovery with latent variables.
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 depression, coping, and stress (Silva et al. 2006). common approach to grasp these latent concepts is to construct measurement model. For instance, experts design a set of measurable items or survey questions that serve 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:CChen Chen et al. [2224] (Sulivvant et al.
20101, high-order moments- based ones (Xie al.] [2020] Chen et al.] 2022 Cai al. | [2019]] Adams et al, 2021), matrix decomposition boboo methods (Anandkumar et al. 2013 2014 2015), and copula model-bas approaches (Cui et al.) (2018). Moreover, the hierarchical latent variable structure has been well-studied within the linear setting (Huang et al. [022]] Xie et al.) 2022 Chen et al. 2023 Jin et al. 2023). However, the linear assumption rather restrictive and the discrete data the real world could be more frequently encountered (e.g., responses from psychological and educational
"Corresponding author
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

#0G.A1
P(K, -0
Σ
Σ
P
P4
103
100
PUG.
Bsx Ari
Σ
Put Auch
17
101
AriA
Mip Fivhi
Arp Pai
X1
X2
16 0)
POX, 10 -
P0 01
PCRaIC -
Pecile 14 gpikklle-e 1300
1
Decorppoation
Pqu.
Pan
Avydi
Auo
Pin
Pip
Pii
PusPas
+ Pr
PuaFes
PasPas
PurPes
Pau.
Pqi
Parfan
Pa
Pai
0. (R. (1)
P(I. - xyl
-1)
(Rank: ane tonsort
(Rank: one temsort
(a) A latent structure with conditional probability tables.
(b) The decomposition the joint distribution.
Figure I: Illustrating the graphical criteria of the tensor rank condition, the rank of the joint distribution determined by the support of a specific conditional set that sesparatts all observed variables, i.e., Rank(P(XX, X2)) = |supp( [L) = 2. See Example 3,4 for details.
assessments or social science surveys (Eysenck et al. 202 Skinner 2019)), which does not satisfy the linear assumption.
When the data generation process discrete, however, due to the challenging nonlinear transition relationship in discrete data, few identifiability results exist and mostly only applicable in strict cases. In particular, under some prespecified structure, the identifiability of parameters is established, such as the hidden Markov mode((HMM) (Anandkumar al., 2012) model, topic models (Anandkumar et al.) 2014), and multiview mixtures model (Anandkumar et al. 2015). By further specifying the latent variable structure show that the structural model is identifiable. Recently, Gu (222)) Gu and Dunson (023) 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
tree, Wang al. (2017); 7): [Son et al. (2013)
causal structure of latent variables shown in Fig. a
Recently, some studies have shown that causal structures involving discrete latent confounders can be effectively identified, building on the identifiability results of mixture models, as discussed in (Kant et al., 2024 Gordon al. 2023 Mazaheri et al. 2023 Annadkkuar al. 2012). Most of these works focus on the causal structure among observed variables, usually assuming single latent confounder. For the identification of latent structure, (Kivva al.) (021) shows that causal structures of discrete latent variables can be identified by recovering the latent distribution from mixture oracle. However, while a general discrete latent variable model can be identified theoretically, estimating the parameters of the mixture model is challenging, Approximating methods are often applied, but these may be unrealistic and impractical in real-world situations.
In this paper, we aim to establish a general identification criterion for discrete latent structures in cases where latent structures exhibit flexible dependencies, while also developing a simple but robust structure learning algorithm. To achieve this, we explore a tensor rank condition on the contingency tables for observed variable set Xp. to probe the latent causal structure from observed data. Interestingly, as shown in Fig. D. we found that the rank of the contingency tables the joint distribution (P(X,,,x)) X2) is deeply connected
the support of a variable (not necessary among X2) that d-separate X, and X2. By this observation, we first develop a general tensor rank condition for the discrete causal model and show that such rank is determined by the minimal support of a specific conditional set (not necessary in X,)) that d-separates all variables in X,, Such findings intrigue the possibility to identify the discrete latent variables structure. We further propose a discrete latent structure model that accommodates more general latent structures and shows that the discrete latent variable structure can identified locally and iteratively through tensor rank conditions. Subsequently, we present an identification algorithm to complete the identifiability of discrete latent structure models, including the measurement model and the structure model. We theoretically show that under proper causal assumptions, such faithfulness and the Markoy assumption, the

---

X3
X
X2
Identifiability of discrete 3PLSM
X3
X
X2
Identifiability of measurement model
Identifiability of structure model
L2
Lg
X,
X5
La
X, XgXo
X
X
Completely identifiable
Markov equivalence
X10 X11
X10 X11-X12
(a) ground truth
(b) Identification of discrete 3PLSM
(c) Identification result
Figure 2: An example of discrete latent structure model involving 4 latent variables and 12 observed variables (sub-fig (a)). Here, the red edges form measurement model, while the blue edges form structural model. The theoretical result of this paper is shown sub-fig (c).
measurement model is fully identifiable and the structure model can be identified up Markov equivalence class.
The contributions of this work are three-fold. (1) We first establish connection between the tensor rank condition and the graphical patterns general discrete causal model, including specific separation 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 is latent variable set I [L,,.". ".,, In3, L, E [[r;] and m discrete observed variable with X, E [d,] (r,, 2), in which any marginal probabilities
= (.,,"., X,. non-zero. We say discrete
statistic model is discrete causal model and only acyelic graph (DAG), denoted by G. We use supp(V,) {u E z P(V, =) > 0} to denote the set of possible values of the random variable V/. 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 al. 2000).
= X can be represented by directed
In this paper, we focus 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) ['hrre-Pure Child Variable Assumption] each latent variable has 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, c.g., Silva et al. (2006); Kummerfeld and Ramsey (2016); Cai et al. (2019); 9): Xic et al. (000)). In the binary latent variable case, recently, similar definition also employed in Gu and Dunson 2023): Gu 2022). The key difference is that there are no constraints on the latent structure in work. An example of discrete 3PLSM model is shown in Fig. a where L,,., La represent discrete latent variables, and X1, '.,, X12 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. (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. shown in Fig. (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 Markov equivalence class. The symbols used in our work is summarised Table
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 9 be causal graph with vertex set V and Ip be probability distribution over the vertices in V generated by G. We say 9 and Pv satisfy the Causal Markov Assumption if and only if for every V, EV, P(V, V Desy, (Pay, = P(WIPav, ()P(V Desv,/Pay, =)..
Assumption 2.3 (Faithfulness Assumption). Let G be a causal graph with vertex set V and Pv be probability distribution over the verfices in V generated by G. We say < G.Pv > satisfies the Faithfulness Assumption if and only if (i). every conditional independence relation true in Pv is entailed by the Causal Markov Assumption applied G, and (ū). for any joint distribution P(L.). there does not exist P(L.)) with (supp(L.g) < [supp(L,p] such that PPLpp) = P(L.))
Assumption 2.4 (Full Rank Assumption). For any conditional probability P(X the corre- sponding contingency table is fill rank, i.e., each column of P(X(Pax is linearly independent with the other column vectors in the parameter space.
2.3 are widely used in the constraint- causal discovery methods, e.g., PC algorithm and FCT 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 dimension 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).
In general, Assumptions 2.2
low-
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 = XUL
X: The set of observed variables p Conditional independence
The set latent variables
Vi Vj [V
|Xpl Dimension of X,
T(Xp) the tensor form of [P (XXp))
P P(Xp) p): : the joint distribution of Xp
Rank( T(xp) p)) The rank tensor T(x
Pax: The parent set X
Des The descendant sct of X
Diag(M) The diagonal matrix M
uz Uj The outer product of two vectors Table 1: Mathematical notations used in this paper.
3
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, first give the explicit definition of tensor rank.
Definition 3.1 (Rank-one Tensor), An n-way tensor T E R (1xxxln is a rank-one tensor if it can be written as the outer product of vectors, i.e.,
T U U2
Un:
where u, are vectors that each represent a dimension of the tensor, @ represents the outer product.
Definition 3.2 (Tensor Rank Kolda and Bader (2009)). For n-way tensor T E g the rank of a tensor T 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:
(5)
where each ug is 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 tensor, e.g., the joint distribution of two random variables is 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, (X1, X (X, S X and n 2 2) and the corresponding n-way probability tensor T(x;) -that is the tabular representation of the joint probability mass function "', Xn). Then, Rank(T(x,)) = (r > 1) if and only if (i) there exist conditional set S C V with |supp(S)] that d- d-separates any pair of variables in {X1,'., "",, Xu.. and (ii) does not exist conditional set S that satisfies [supp(S)] < <..
We further provide an example to illustrate Theorem 3.3
Example 3.4 (lllustratnng the graphical criteria). Consider a single latent variable structure as shown in Fig. D (a) where L is a latent variable with supp(L) = {0, 1} and X1, X2 are observed variables with supp( x) = {0, 1, 23, i 21. For convenience, we denote p: = P(L i), Pa15 = IP(X; = = j). and Pul; (X2, = j). The joint distribution xX) can be expressed as the product of conditional probabiliries, as shown in Fig. [īb). By applying the tensor decomposition, we observe that 1 1, X2) can be decomposed as the sum of two rank-one tensors: X2|
and P(X,, I = 1). Thus, the rank of the tensor P(X,, X2) is two, corresponding to the cardinality of the latent variable's 's support. The reason P(X,, X2 =i) a rank-one tensor that L d-separates X1 and X2, i.e., IP(X,, X21L i) P(X, i) @ P(X21L = 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.
4 Structure Learning of Discrete Latent Structure Model
In this section, we address the identification problem of the discrete 3PLSM model using 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... 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 [
4.1 Identification of the measurement model
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,,...,X, is a causal cluster, termed C,, if and only if all variables
",,,""",)) 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 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 probabilit contingency table for any pair of observed variables X₂ and X ie. |supp(L)] Rank(T(x,,x)) v X,, X.
5

---

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 Iddenificcatinn of causal cluster). In the discrete 3PLSM mode, suppose Assumption 2.2 Assumption 2.4 hold. Let |supp( L,)) denote the cardinality of the latent support. Given three disjoint observed variables X,, X3, X5 E X,
Rulel: if the rank of tensor x(,,.Xx,,,) is not equal to i.e., Rann Rann(((x;.xxxxx))) # then X latend
Xj and X5 belong the different latent parents.
Rule2: for any X X. E X (X,, X,, Xk), if the rank of tensor XX, is v, i.e.
Rank(T(xx (axkk(T(x.X,..x)x xxxxx) r, then [X, Xx) share the same latent parent.
Example 4.4 (Finding causal clusters). Let's take Fig. a as an example. One can find that for (X,,X2, XR), where X X
the rank of tensor xxx is r. Thus,
{X,,X, X3} 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₁ and Cz. if C₁ n C2 # Ø, then C1 and C2 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 Xg. and the dimension 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;, X3 and X E X do
6: if RRRkk (T,,,,,,, Xxi) # then
7: Continue; Rulel of Prop.
8: end if
9: if RaRk (aa,
rr for all X, E (X,, X,, X,,X,) then
Xx)
C= Cu Cu X,.
11: end if
end for
13: until no causal cluster is found.
// Merging cluster and introducing latent variables
15: Merge all the overlapping sets in C by Prop. 4.5 for each C, E C do
17: Introduce a latent variable for C;;
18: G U - XylX, E C.).
19: end for
20: return Graph 9 and causal cluster C.
Theorem 4.6 (Identification of the measurement model). In the discrete 3PLSM, suppose Assumption Assumption 2.riiioon2.4... hold. The measurement model is fully identifiable by Algorithm 1.
2.2
4.2
Identification the structure model
Once the measurement model is identified, the observed children can serve proxies for the latent variables, enabling the identification of the causal structure among them. Here, we employ constraint- based 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 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 required (see Theorem 4.7p.
Theorem 4.7 (d- separation among latent variable). the discrete 3PLSM, suppose Assumption 2.2 Assumption 2.4 hold. Let denote the cardinality of the latent support. Then, L; IL L,|L, if and only if Rank (aann((Tx..,,,.. XX xp. (2a)) ,lاbl where X; and Xj are the pure children of L, and L.g. Xp and Xp2 are two disjoint child sets of L, that satisfy L; E Lp, Chr, OXpl * Ø, Chr,, nX22 # Ø.
Intuitively, based the graphical criteria of tensor rank condition, Lp is minimal conditional set in the causal graph that d-separates X and Xp2 and hence the rank of tensor 55 (i X,aa) is the dimension of support of ,, X; and X, also be d-separated by Lp
Example 4.8 (CI test among latent variables). Consider the structure in Fig. a and suppose r = 2. By selecting X = (XA, X7) and Xp2 = (X5,. Xs} as two disjoint child sets of {In Laa) respectively, let X, = (X1, X X10; X X3. X7;Xs) and L, (In, lzz)- One can that the rank of tensor T(x,) is four since Lp (Lee {Io, La]) is minimal conditional set that d-separates any pair variable in Xp. which imply that L IL Lal(L,, Ls).
Based on Theorem 4.7, we introduce the PC-TENSOR -E-NORR--RANK RANN algorithm. This method accepts measurement model learned by the previous procedure, and outputs the Markov equivalence class of 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 the structure model as shown in Theorem
Algorithm 2 PC-TENSOR-RAAK
Input: Data set X [X I...... X and causal cluster C Output:
partial DAG g.
I: Initialize the maximal conditions set dimension k;
2: Let L, denote as C₁2 C, E: C:
3: Form the complete undirected graph G on the latent variable set L; and adjacent in G do
4: for VT,, I.,
5: //Test the CI relations among latent variables by Theorem 4.7
6: if LL L {Li, L,} and (LLp k) such that Le 11 Lý Lp hold then
7: delete edge L; - Ly from G;
8: end if
9: end for
10: Search structures and apply meek rules Meek (1995).
11:
return 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 Markov equivalent class by the PC-TENSOR-RAND algorithm.
4.3 Practical Test for Tensor Rank
In our theoretical results, the key issue is to test the rank of tensor, which involves estimating the dimension of latent support and the rank of tensor. Here, we aim to explore methods to estimate the rank of the contingency matrix for determining the dimension of latent support, and (ii) apply the goodness-off fft 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 estimate the rank of general matrix M, such Camba-Méndez and Kapetanios (2009). In implementation,
7

---

Table 2: Results on learning pure measurement models, where the data is generated by the discrete 3PLSM. Lower value means higher accuracy.
omission
Lalent commiision
Mismoaurreennts
Algovishm
Our
HayPy
1:M
RPC
HayPy
LTM
BPC
Our
BayPy
1.MM
RPC
Sk
0.15(3)
0,1022)
0.131.3
0.95(10)
0.0000
0.10k2)
0.030:
000001
0.05(])
00030)
0.000)
0.00R0)
SM, MMM,
10k
0.05(1)
0,05(1)
0.10(2)
0.90(10)
0.0000)
0.05(1)
0.001)
0.0000
0.00:0)
0.00:0)
0.0000
0.00(0)
0.0010)
0.90(10)
0.000)
0.00K0)
0.0000
0.90:0)
0.0000
0.000)
0.90/0)
5k
0.25(5
0,19661
0.2616)
0.300110)
0.000)
0.1916)
0.03()
000001
0.0512)
0.19
0.2366
0.0000)
SM₂ M,M,
10k
0.13(4)
0.1344)
0.1364)
0.6((10)
(.0K0))
0.83(4)
0.000)
D.000)
0.9K0)
0.13(4)
0.13(4)
0.9K0)
0.1033
0.1013)
0.8(10)
0.13(4)
0.0000
0.00001
0.00/0)
0.134)
0.103)
0.00/0)
Sk
0.1212)
0.19K6)
0.2115)
(.)00(00
0.0000)
0.19(6)
0.0000
0.0000)
0.03(1)
0.1060)
0:21(5)
0.90(0)
SM, + MMM,
10k
0.03(1)
0.13(4)
0.1013)
0.86(10)
0.0000
0.1364)
0.00/0
0.0000
0.00:0)
0.11(4)
0.10(3)
0.90:0)
0.000)
0.07(2)
0.07(2)
(.8((1))
0.0000
0.07(2)
0.0000
0.000)
0.07(2)
0.062)
0.90/0)
0.2566
0.3036)
0.55(10)
036
0.000)
0.30X6)
0.000
(1000)
0.12(5)
0.2066
0.55(10)
03900)
SMG + M.M,
10k
0.17(5)
0.25(5)
0.50(10)
0.83(10)
0.00D)
0.25(5))
0.000)
0.000)
0,0533)
0.16(5
0.50010)
0.000))
0.08(3)
0,2044
0.50(10)
0.83(1)
0,000)
0.2044)
0.000)
0.0000
0.03(2)
0.13(4)
0,50X10)
0.90/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 d - r 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²" random variables.
Goodness-of-ft 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: Ho: 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.
Rank(T) v.s. H4 Rank(T) #
To perform the sunk-dccompostiion with specified r on the probability contingency tensor, one can use the non-negen 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 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)
Such 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 as x² Eiever(T) which follows the x²2 distribution with freedom degrees [sEEn) d; - -(E d,d)).
(Nec(T),- ve
5 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) et al.] (011)) 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]: I, L.g [SM2]: In + I2 + Tag; [SM3]: the structure of latent variables is shown in Fig. 2 a): [Collider]: L1 - L2 + Lg; [Star]: L1 - L2, L1- L3, L1 - L1. For the measurement model, we consider the following two cases: [MMI]: each latent variable has three pure observed variables, i.c., L, {Xx, X2, Xy): [MM2]: each latent variable has four pure observed variables, i.c., L: - (X,,X2, X3. X.).
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.. SMI), 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 and the dimension of all observed variables support is set to 4, sample size ranged from (5k, 10k, 50k).
8

---

Table 3: Results on learning the structure model. The symbol '-' indicates that the current method does not output this information. Lower value means higher accuracy.
Edge omistion
Edge commiscionn
Orientation omiissoo
Algarithm
Our
RayPy
RPC
Our
BayPy
1.TM
RPC
Our
RayPy
BPC
5k
0,00(0)
[00
0.2668]
1000,10)
0.0000)
0.000)
0.000
0.10(1]
1,00(10)
LXXX0:
M
10k
0,000)
100000>
0.2366)
1,00(10)
0.050)
0.02(1)
0.00)
0.000)
0.900)
1,00(10)
1.000)
0.0000)
10X109
0.103)
1.0010)
0.00K))
0.000)
0.00)
0.900
1,000)
5k
0.13(3)
0.1666)
1.00100)
0.10(1)
0.000)
00000)
0.000)
0.0001
(.00R0)
SM2+ MM
10k
0,U5(1)
100010>
0.13(4)
1.00(10)
0.01(1)
0.000)
0.000)
0.0001
0.000)
0.0000)
D.000)
50k
0.0010)
100010>
0.10.3)
100010)
0.00/0)
0.000)
0.000)
0.000)
0.0001
0.00/0)
0.00/))
0.10(3)
L0X
0.2565)
1,000 10)
0.2015)
0.000)
(1000)
0.000
0.0000
0,30(0)
(.000)
Star + MM
10k
0.06(2)
100010)
0.13)
1,00(10)
0.08(3)
0.00,0)
0.0000)
0.0000)
0.00/0)
0.00/0)
0.00.0)
50k
0.03(()
100010)
0.15(3)
1,00(10)
0.05/2)
0.000)
0.0000
0.0000
0
0.00:0)
0.0000)
0.22(7)
1000
0,50Ç10)
1.00
0.4016)
0.000)
0.021))
0.0000
0.2021
1,00
1,0K
SM, MM,
10k
0.1515)
100(10)
0.50(10)
1.00(10)
0.10(2)
0.000)
0.000)
0.000)
0.10/1)
1.00110)
1.0010)
50k
0.0512)
1.0010)
0.50C10)
1,00(10)
0.05(1)
0.000)
0.00.0)
0.0000)
0.00/01
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 (0O). These metrics can be referred to Silva et al. (200)) 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 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 specifically designed for linear models. Additionally, the LTM and BayPy algorithms show suboptimal perfor- mance in structure learning of latent variables due their limitations 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 struc- ture (e.g., an edge between observed variables) can be detected through tensor rank conditions. For instance, consider the struc- ture shown in Fig. 3 and suppose all observed variable has the same support. One can observe that for any subset (X,, X3,, X&} c {X1,X2, X4, Xs} where (Xa, X3} & (X,, X,, Xx). one has Rank(T (Tx,,(X(x.,,,xx..)) [supp(L)]. This implies {X1, X23 and X, (or Xs) share the common |supp(Xxs]] assuming the cardinality of the
X2
Xa
Figure 3: Example of identify- ing the impure structure.
latent parent. Moreover, we have Lank(T(x,,xx observed variables larger than that of the latent variables. By the graphical criteria of the tensor rank condition, one infer that there is an edge between X, and X5, 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 principled way is part of our future work.
7 Conclusion
We derive a nontrivial algebraic property of 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 meaningful future direction.

---

Acknowledgments
This research was supported in part by National Key R&D Program of China (202IZD01 11501), National Science Fund for Excellent Young Scholars (62122022), Natural Science Foundation of China (61876043, 61976052, 62476163), the major key project of PCL (PCL2021A12). ZM would like to acknowledge the support of the China Scholarship Council (CSC). .. FX would like to acknowledge the support by the Natural Science Foundation of China (62306019). JQ would like to acknowledge weegge the support by the Natural Science Foundation of China (62406080). KZ would like to acknowledge the support from NSF Award No. 2229881, Al Institute for Societal Decision Making (AI-SDM), the National Institutes of Health (NIH) under Contract R01HL.1990S and grants from Salesforce, Apple Inc., Quris AI, and Florin Court Capital. We appreciate the comments from anonymous reviewers and Area Chairs, which greatly helped to improve the paper.
References
Silva, R.; Scheine, R.; Glymour, C.; Spirtes, P. Learning the structure of linear latent variable models. JMLR 2006, 7, 191-246.
Bollen, K. A. Latent variables in psychology and the social sciences. Annual review of psychology 2002, 53, 605-634.
Bartholomew, D. J.; Knott, M.; Moustaki, I. Latent variable models and factor analysis: unified approach; John Wiley & Sons, 2011.
Cui, R.; Groot, P:; Schauer, M.; Heskes, T. Learning the Causal Structure of Copula Models with Latent Variables. Proceedings of the Thirty-Fourth Conference on Uncertainty in Artificial Intelli- gence, UAI 2018. 2018; pp 188-197.
Kummerfeld, E.; Ramsey, J. Causal clustering for 1-factor measurement models. KDD. 2016; pp 1655-1664.
Chen, Z.; Qiao, J.; Xie, F: Cai, R.; Hao, Z., Zhang, K. Testing Conditional Independence Between Latent Variables by Independence Residuals. IEEE Transactions on Neural Networks and Learning Systems 2024,
Sullivant, S.; Talaska, K.; Draisma, J.; others Trek separation for Gaussian graphical models. The Annals of Statistics 2010, 38, 1665-1685.
Xie, F.; Cai, R.; Huang, B.; Glymour, C.; Hao, Z.; Zhang, K. Generalized Independent Noise
Conditionfor Estimating Latent Variable Causal Graphs. NeurIPS. 2020; pp 14891-14902.
Chen, Z.; Xie, F:; Qiao, J.; Hao, Z.; Zhang, K.; Cai, R. Identification of Linear Latent Variable Model with Arbitrary Distribution. Proceedings 36th AAAI Conference on Artificial Intelligence (AAAI). 2022.
Cai, R.; Xie, F.; Glymour, C.; Hao, Z.; Zhang. K. Triad Constraints for Learning Causal Structure of Latent Variables. NeurIPS. 2019; pp 12863-12872.
Adams, J.; Hansen, N.; Zhang, K. Identification of partially observed linear causal models: Graph-
ical conditions for the non-gaussian and heterogencous cases. Advances in Neural Information Processing Systems. 2021.
Anandkumar, A.; Hsu, D.; Javanmard, A.; Kakade, S. Learning linear bayesian networks with latent
variables. International Conference on Machine Learning. 2013; pp 249-257.
Anandkumar, A.; Ge, R.; Hsu, D. J.; Kakade, S. M.; Telgarsky, M.; others Tensor decompositions for learning latent variable models. J. Mach. Learn. Res. 2014, 15, 2773-2832.
Anandkumar, A.; Ge, R.; Janzamin, M. Learning overcomplete latent variable models through tensor methods. Conference on Learning Theory. 2015; pp 36-112.
Huang, B.; Low, C. J. H.; Xie, E: Glymour, C.: Zhang, K. Latent hierarchical causal structure discovery with rank constraints. Advances in Neural Information Processing Systems. 2022.
10

---

Xie. F.; Huang, B.; Chen, Z.; He, Y:; Geng, Z.; Zhang, K. Identification of linear non non- Gaussian latent hierarchical structure. International Conference on Machine Learning.. 2022: pp 43770-24377.
Chen, Z.; Xie, F:; Qiao, J.; Hao, Z.; Cai, R. Some general identification results for linear latent hierarchical causal structure. Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence. 2023; pp 3568-3576.
Jin, S.; Xie, F.; Chen, G.; Huang, B.; Chen, Z.; Dong, X.; Zhang, K. Structural Estimation of Partially
Observed Linear Non-Gaussian Acyclic Model: A Practical Approach with Identifiability. The Twelfth International Conference on Learning Representations, 2023.
Eysenck, S. B.; Barrett, P. T. Saklofske, D. H. The junior eysenck personality questionnaire. Person- ality and Individual Differences 2021, 169, 109974.
Skinner, C. Analysis of categorical data for complex surveys. International Statistical Review 2019, 87, S64-S78.
Anandkumar, A.; Hsu, D.; Kakade, M. A method of moments for mixture models and hidden Markov models. Conference on learning theory. 2012; pp 33-1.
Wang, X.; Guo, J.; Hao, L.; Zhang, N. L. Spectral methods for learning discrete latent tree models. Statistics and Its Interface 2017, 10, 677-698.
Song, L.; Ishteva, M.; Parikh, A.; Xing. E.; Park, H. Hierarchical tensor decomposition of latent tree graphical models. International Conference on Machine Learning. 2013; pp 334-342.
Gu, Y. Blessing of Dependence: Identifiability and Geometry of Discrete Models with Multiple Binary Latent Variables. arXiv preprint arXiv:2203.0444 044403 2022,
Gu, Y.; Dunson, D. B. Bayesian pyramids: Identifiable multilayer discrete latent structure models for discrete data, Journal of the Royal Statistical Society Series B: Statistical Methodology 2023, 85, 399-426.
Kant, M.; Ma, E. Y.; Staicu, A.; Schulman, L. J.; Gordon, S. Identifiability of Product of Experts Models. International Conference on Artificial Intelligence and Statistics. 2024; pp 4492-4500.
Gordon, S. L.: Mazaheri, B.; Rabani, Y.; Schulman, L. Causal Inference Despite Limited Global Confounding via Mixture Models. Conference Causal Learning and Reasoning. 2023; pp 574-601.
Mazaheri, B.; Gordon, S.; Rabani, Y.; Schulman, L. Causal Discovery under Latent Class Confound- ing, arXiv preprint arXiv:2371.0745 2023,
Anandkumar, A.; Hsu, D.; Huang, F:; Kakade, M. Learning high-dimensional mixtures of graphical models. arXiv preprint arXiv: 1203.00203.069 2012,
Kivva, B.; Rajendran, G.; Ravikumar, P.; Aragam, B. Learning latent causal graphs via mixture
oracles. Advances in Neural Information Processing Systems 2021, 34.
Spirtes, P.; Glymour, C.: Scheines, R. Causation, Prediction, and Search; MIT press, 2000.
Spirtes, P.; Glymour, C. An algorithm for fast recovery of sparse causal graphs. Social science computer review 1991, 9, 62-72.
Kolda, T. G.; Bader, B. W. Tensor decompositions and applications. SIAM review 2009, 51, 455-500.
Sullivant, S. Algebraic statistics; American Mathematical Soc., 2018; Vol. 194.
Meek, C. Causal inference and causal explanation with background knowledge. UAL 1995; pp 403-410.
Camba-Méndez, G.; Kapetanios, G. Statistical tests and estimators of the rank of matrix and their applications in econometric modelling. Econometric Reviews 2009, 28, 581-611.
Robin, J.-M.; Smith, R. J. Tests of rank. Econometric Theory 2000, 16, 151-175.

---

Shashua, A.; Hazan, T. Non-negatin tensor factorization with applications to statistics and computer vision. Proceedings of the 22nd international conference on Machine learning. 2005; pp 792-799.
Cochran, W. The x2 test of goodness of fit. The Annals of mathematical statistics 1952, 315-345.
Choi, M. J.; Tan, V. Y.; Anandkumar, A.; Willsky, A. S. Learning Latent Tree Graphical Models. Journal of Machine Learning Research 2011, /2, 1771-1812.
Pearl, J. Causality: Models, Reasoning, and Inference, 2nd ed.; Cambridge University Press: New York, 2009.
Leonard, T.; Novick, M. R. Bayesian full rank marginalization for two-way contingency tables. Journal of Educational Statistics 1986, 11, 33-56.
Bartolucci, F:; Colombi, R.; Forcina, A. An extended class of marginal link functions for modelling contingency tables by equality and inequality constraints. Statistica Sinica 2007, 691-711.
Kruskal, J. B. Three-way way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics. Linear algebra and its applications 1977, 18, 95-138.
Hackbusch, W. Tensor spaces and numerical tensor calculus; Springer, 2012; Vol. 42.
Koch, K.-R.; Koch, K.-R. Bayes' theorem. Bayesian Inference with Geodetic Applications 1990, 4 8.
Aish, A.-M.; Jöreskog, K. G. A panel model for political efficacy and responsiveness: An application of LISREL with weighted least squares. Quality and Quantity 1990, 24, 405-426
Jöreskog, K. G.; Sörbom, D. LISREL 8: User's reference guide; Scientific Software International, 1996.
Salles, J.; Stephan, F.; Molière, F.; Bennabi, D.; Haffen, E.; Bouvard, A.; Walter, M.; Allauze, E.; Llorca, P. M.: Genty, J. B.; others Indirect effect of impulsivity on suicide risk through self-esteem and depressive symptoms in population with treatment-resistaat depression: A FACE-DR study. Journal of affective disorders 2024, 347, 306-313.
12

---

Supplementary Material
The supplementary material contains
Graphical Notations;
Example of Tensor Representations of Joint Distribution;
Discussion of Our Assumptions;
Proofs of Main Results;
Proof of Theorem 3.3;
Proof of Proposition 4.2;
Proof of Proposition 4.3;
Proof of Proposition 4.5;
Proof of Theorem 4.6;
Proof of Theorem 4.7;
Proof of Theorem 4.9.
Extension of Different Latent State Space;
Discussion with the Hierarchical Structures;
Practical Estimation of Tensor Rank;
More Experimental Results;
Experimental Results on Dataset;
A Graphical Notations
Below, we provide some graphical notation used in our work, which is mainly derived from the Pearl (2099) Spirtes et al. (2000).
Definition A.1 (Path and Directed Path). In DAG, a path P is a sequence of nodes (V,,... V2) such that V; and V++1 are adjacent in G, where s < Further, say path P (Vi, V ........ V.,) in G is a directed path if it is sequence of nodes of where there is a directed edge from V., to Vag.n, for any S s k
Definition A.2 (Collider). A collider on a path (V)....pp is node V, 1<ii such that V
and Vi+1 are parents of V,
Graphically, also say collider is 'V-structure'.
Definition A.3 (d-separation). A path p is said to be d-separated (or blocked) by a set of nodes Z if and only if the following two conditions hold:
p contains chain V: + Vv + Vj or a fork V; Vv V3 such that the middle node Vy is in Z:
p contains a collider V; Vx c- V₁ such that the middle node Vg is not in Z and such that descendant of Vv is in Z.
A set Z is said to d-separate A and B if and only if Z blocks every path from a node in A to node B. We also denote as 1L Z in the causal graph model.
B Example of Tensor Representations of Joint Distribution
Consider single latent variable structure that has three pure observed variables, i.e., Li X2, Xz). We aim to illustrate the tensor representation of the probability contingency ta- ble and the tensor rank condition for the joint distribution
For convenience, let {0, 1, We further denote Pij = P(X, i,X, = j), Pil P(X, L j), Pij = P(x2 L j). p. P(L, = i). and Pijk = P(X, X, X. k). For the joint distribution of X2), have the tensor representation follows:
supp(L,) = (0. 13 and supp(X,)
13

---

Poo
Poi
Po2
Pójo
Póji
Po 0
Pojo Pojz
Pijo
Pajo
x,x,
P1o
P11
P12
Pilo
PiJI
(1)
P122
Pal1
P20
P21
P22
P2j0
P211
Dingel T(x.)))
Tiaato
where T(x.)r.) is the tensor representation of ( L1), T(x2(1,) is the tensor representation of P( P(X21T.) and Diag(T(L,)) the diagonalization of P(T.).
Under the Full Rank assumption, we have 14,, and T(xa!1,) are column full rank. Thus, the rank This illustrate the Prop.
of Tx,x, X2 is two, i.e., Rank(Tx, = |supp(L,)
Next, we consider the three-way way tensor T(x, x,) of the joint distribution (x.s)) We will way tensor as its frontal slices Kolda and Bader (2009). i.e., three matrices for X2X3 = 0), P(X,X,X, 1) and P( = 2).
represent the three-wer three-way
Poo0
Po10
Pu20
Poo1
Pol1
P021
Po02
P012
Po22
P100
P110
P120
Piot
P111
P121
P102
P112
P122
(2)
P200
P210
P220
P201
P211
P221
P202
P212
P222
X2
T(x1X2X=-1)
In the contingency tensor above, the element of T(x,XxX)) is
P(X1 = =, A)
Σ P(X, = i, X₂ = X, = K|4 = r) r)
(3)
Σ P(X = i = = =r)(L = r).
One can represent the tensor Tx, Xx as
IP = 01
P(X, = 0
P(X3 0 =
P(X; 11, =
@
P(G, 1 =
P(X; 1 =
(4)
P((:; = 2
P((2 L
[(Xs 2 =
where @ represent the outer product, e.g., for two vector u and v, (u @ v)ij u,úy with u ("1, J,, and (",,""; un).
is a rank-one tensor. According the definition of tensor rank, one can see that T(x the rank of T(x, Xg) is two under
Furthermore, since Xxx)) - xnn Assumption 2.2 Assumption 2.4. This because L, d-separates X, and X, with Vi,j E [1,2,3]. which illistrate the graphical criteria of tensor rank condition.
C Discussion of Our Assumptions
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 lower-dimensional space. There are related works that also use such an assumption Leonard and Novick (986);: 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 discrete causal model. Moreover, sufficient observation assumption that the dimension of latent support 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.
14

---

It is worth noting that, although Kivva et al. (202T) 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. (202T) the parameters of the mixture oracle, such the number of components, are estimated using approximate methods like the K-means algorithm, which may not be applied directly to discrete data.
D Proofs of Main Results
D.1 Proof of Theorem 3.3
Proof. "If" part:
We prove this by contradiction, i.e., suppose (i). there exists variable set S in the causal graph G with [supp(S)) = r that d-separates any pair of variables in (X1, 1..,,,,,
and (ii).does no exist Xn.. .",),,
conditional set $ that satisfies [supp(S)] < then Rank(T[x, (x.),.....)) xx)) # There are two cases we and Case 2: Rank Ran,.(T(.......)) <T.
need to consider: Case I: Rankkaaaaaaa (T(x,.....))
Case 1: Due S is conditional that d-separates all variables in (", then we have ((X,--.,,)) = Σ (TT==1 P(X,IS P)) = i). When Rank(Tr Tlank(Tx,....a = k there are
let
Txx
T(x]S==)) @ ... T(x,, [S=) T(s=i)
(5)
(i)
@
u @un,
which violates the definition of tensor rank (i.e., is a minimal rank-one decomposition, it can be reduced to the smaller decomposition with r). Meanwhile, if there exists other conditional sets such that ..(X.....X,) = Σ ([T)= ((s)s) is minimal rank decomposition, it violates the condition (ii) that |supp(S)] is minimal.
Case 2: When Rank(T(s) (T(x, ) < r, let Rank(T[xx...xx = r, due to S is conditional set with smallest support r in the causal graph, one have
Tix...xan)
Σ [-1
T(xi[S=i) @ ... ([x.
(6)
Σ
(1)
Ø ... @ u
1=1
which means that there at least exist T(x......I=s.)) and T(x,..... such that T(x,1s=:) aTT(x,Is=E) for any i, k [n]] where is constant. i.c the columns of the conditional contin- gency table are linearly dependent. This violates the assumption 2.4 (the Full Rank assumption).
Therefore, Rank Ran..(T........) r if the condition (i) and condition (ii) holds.
"Only if" part:
will show if one of the conditions is violated, the tensor rank not r. i.e., (i). there does not exist a variable set S in the causal graph with [supp(L.] that d-separates any pair of variables in (X ",, Xn), or (ii. exist S that satisfies |supp(S)] < r, then Rank (((nk(((.....)))))) $ r.
15

---

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 conditional set the causal graph, and Case variable constructed from parameter space.
Case 1: if is not conditional and S n Desx, ... n Desx. 2, by the Markov assumption, P(X1, IS i) *
i). By Lemma. D.3 PP X,IS i) is not rank-one tensor, which violates the definition of tensor rank.
I is not a conditional set and SnDesx, n...nDexx * Ø we will show that 1. x,, = i) is not a rank-one tensor, to prove such 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 (Xi.... Xn). we have
T(xi--X.1(81))
k
Σ
J-1
XXISs)))) is a rank-one tensor, i.e. T(X, U1 @ ... @ Un we further have
Σ X. T(8-1($-)) u, un
(8)
Note that there exists Xp, X, E (X1, "., X,) such that S is the common descendant variable of X, and X, it will lead to collider structure in which P(X,(S) and (P(X,|S) is relevant (i.e., the v-structure activated). Thus, let X, = (X1, X,) (X;,X)) (xxss"X.Iss.)) not a rank-one tensor due to the sub-tensor , x(=)(S=)) (a slice of tensor T(xI--).1s=i)) is not rank-one
tensor Hackbusch 2012); Kruskal 1977). under the faithfulness assumption. If so, one have XX,,X,X u, @ u2. Let u X, clS = i) and u, PX,, X, = c|S i). violates the faithfulness assumption.
Thus, S not be the common descendant of any pair variables in (X1, ".,, So, for any accord- Xp, Xg E (X,,".., there are x[x,,x,|S=5$$=) = T(x,1S== Desxx)) @ (xxx1$=i,Dess ing to Markov assumption ($ is d-separation set for X, and Xg). Now, for the Eq. we have
T(x-xxX,ILE1))
Σ
i=1 T(x, 2n) Dex =c|==))
(9)
j-1
U1
Un
This equality holds if the A sum of the rank-one tensor can be reduced to rank-one tensor, i.c., for any Xp. ISx,,SS-1,Dexx -c) = a2 (S= 2,Desxx -e) a, Ier.Dxxp -c)- where a; and are constant. However, this equality can not hold due to the following reasons.
If Pax, Ø. let Lp be the parent of Xp, have
TSx,,S=i,Dex,, =e)
[
Σ
T,x,,,, T(, (-i,
F=1
(10)
[supp(T,p)]
Σ
T(x,14,=,
T Ser, 1Sx, mc)
J=1
"The lower bound of tensor rank is not less than the rank of any slice of tensor.
16

---

in which the inequality holds because of the Full Rank assumption and all marginal distribution prob- abilities are not zero (see Lemma. D.4). Therefore, Tix, (xx_IS-1.Dexx,- =c)
a, ( Dex. =e)- Thus, (X,1=xx,((s=;)) is not rank-one tensor. By the definition of tensor rank, Rank
If Pax, Ø. i.e., Xp the root variable, (e.g., X, S. Desx, Es ). will show that the probability contingency table T(x, is) is full rank, and then the equality in Eq. caa not hold. According to the Full Rank assumption and Xp is the parent variable of S, have the probability contingency table T(SIX,) is full rank.
Due to p( S) P(SIXX) = F(X, and the probability in the marginal distri- bution is not zero, have T(x_ S)) T(SIx, Diag( T(x,,) Diag(T(s)) where Diag( T(xx)) is diagonalization of marginal distribution probability vector of X,- One can see that T(x, is full rank due the diagonal matrices are all of full rank. Thus, T(x,1S=1) ... a, a,,T(x,18=r) and (x, not a rank-one tensor. By the definition of tensor rank, Rank (xx, #T.
Σ does not hold with r, where u, represents any vector. Let u, @ ... @ un be a rank-one tensor of P(X1, I = PS = i) due to IP(S = i) is constant. In other words, one can construct variable set S with [supp(S)] = r. For any S constructed from parameter space (i.e., is not a true node set in the causal graph), (x.,....... [==) un @ un one can let u [[x, ''', "",, Un Txx, (8=1), which violates the faithfulness assumption. Based on the above analysis, there does not exist S by any constructed such that (x.) have the summation rank-one decomposition, i.e., Rank(T(x,.".,,,, #
Case 2: we further show that for the parameter space, the tensor T(x,
up
Now, analyze the condition (ii), i.e., there exists conditional set $ with supp(S) Let supp(S)= = k; & < r, we have T(X, = Ex=, Txx "- @ [sx,, T(s=i) is a smaller rank-one decomposition than T..))....) Σj=ı u'1 un According the definition of tensor rank, we have Rank (Tx,((( In summary, the theorem proven.
k #
Lemma D.1. Let Tnp be the parent of Xp. Consider P(X,IS= = i) and P(X,IS= r), where can be any variable set. Under the Assumption 2.4, for constant the following inequality holds:
Jsuppí E,)1
(aup
(ix # c
Proof. We prove it by contradiction. For convenience of symbols, let let = Ix,xII,,=1); and azli P(Ipp = = i) and Brr- P(Lp = = = r) (0r)) # 331r), if the equality hold, we have
|supp(T.pp)
[.,))(.,))1
Σ
R =
B
(11)
which means that
|supp( ket (aula cBBRp)VKk
V1
(12)
adje
cBerr
That is, V, is a linear combination of other vectors V₁ with /. k. i.e., the linear combination of other column vectors in the conditional probability contingency table, which is contrary to the Assumption 2.4.
17

---

Lemma D.2. Let Lp be the parent of Xp. Suppose Assumption 2.2 ~ Assumption 2.4 hold. (sx)) cannot be expressed as a linear combination of other q vectors T(x,1S=r) i.e. ((,,s==)) E/=1 7o (xx,lsSmr)
Proof. We prove it by contradiction. For convenience of symbols, let v, = ( and agii P(Lp j|s i) and 8y1r PLL = j|S r), if the equality hold, one have
Jsupp( 11) Σ
Isupl(
ajkV
7h
r=1
j=1
(13)
7,
r=1
there exist a vector V, with atji
Σn-1 Yr YrIr * 0. such that
Σ supp([),))
( 7r axlivv
V2
(14)
Σ Br
means T4,,1 is a linear combination other column vectors the conditional probability contingency table, which is contrary to Assumption 2.4.
Lemma D.3. For the set of variables {X,,"., X,). i is not conditional set that d-separates any
pair of variables in (X1,"* "",",,, x,, in the causal graph and S DeD Ø, then T(x, ((. ($=)) not a rank-one tensor.
Proof. Let S be the minimal conditional set, (e.g., S (X,, '': xn-1)) denote [supp(S)] under the faithfulness assumption and the Markov assumption, IPS) PPS)) if T(x (S=j) is rank-one tensor, we have
Tx (xx,..X,115 x,,55=)
@ i= T=x
(15)
1=1
U1 @ Un
which means that for any X, E (X,, 1.,.,,,,,,) X,). T(x, = 02T((x18-2) = "TTTxx,iss))
Xp has a parent variable Lp in the causal graph, by Lemma D.I. the equality does not hold. Thus, (1,E)))) is not rank-one tensor.
X, is root node in the causal graph, and is conditional set that d-separates X,, and {X,, ...
(X,). we have T(x,1s) is full rank. The reason is the following.
Since IS))))))((S) TP(S) X, P)Xp) by Bayes' theorem Koch and Koch 1990). and due to all
marginal probabilities are not zero, then we have T(x,19) Tis Diag Diag(T(x,)) Diag (T(s)) where + is inverse of matrix, and Xp is ancestor of S. By Lemma [D2] S has parent variables and hence T(s)x,) is full rank (one can vectorize the variable set S as a variable). Now, we have T(x,1s) is full rank due to the three matrices on the right are all full rank.
Thus, T(x,18-1) 02 T(x,1s-2) ...T(xx,(S-)) does not hold, i.e., T(x,".X.,Is.)) not a rank-one tensor.
Lemma D.4. In discrete causal graph, for the variable Xp let I.p represent the vectorized parent set of Xxp and let Desx, denote the set of descendant variables of Xy- Under this setup, T(X, T(x,Le LL Deex, -3) is full rank.
18

---

Proof. By Bayes" theorem Koch and Koch 1990), we have
T(xy.Ip Desx,=1)
= =Xxx (1) Diag( Dex, -3))
(16)
=T,,,IXp.Dusx =f} Diag( T(x, Desx,=)) =f))
Since Xp and Desx, both are the descendant set Li. we have
Tee Dest,) TeDee,, Diag(TT. Diag(T(Des)
(17)
due to the fact that all marginal distribution probabilities are not zero. Then T(z, Dest,) is full rank, Desx, DDsxx==1 =f) also full rank.
i.., T(I,, (,,
Moreover, for any T(L,-i|Dessp) we have
T(e -Dxx, - -i) = Ti =i) # O,
(18)
T(Desx, -5)
because all marginal distribution probabilities are not zero. Thus, we have
((,p.I,.Desxx =j)
(19)
TTL,, -3) Diay(((Xx, Desx, (exx,/Dex,,)))DDD Dia((T =)))*
One can see that T(xy LDD,: is full rank due to three matrices on the right side being full rank.
D.2 Proof of Proposition 4.2
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,x,) is the dimension of latent support.
D.3 Proof of Proposition 4.3
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, that d-separates any pair variables in (X,, X,, X i.e., the rank of tensor T(x,X,X, ) is not (by Theorem 1), it must be the full-connection structure among latent variables, as shown in Fig. (d). Otherwise, one can find one latent variable I. that can d-separates (X,, X,. )x). as shwon Fig.
(a) (c). We will show that, if only consider one (d,, the tensor of Xx.) can not have rank-one
of the latent variables of {L1, L2, L3} in Fig. decomposition.
h
L
h
L2
X
X
X
X;
Xx
X
X
k
X
Xj
X k
(a)
(b)
(c)
(d)
Figure 4: Illustrative example for Rule 1.
According to the graphical criteria tensor rank and r < d, the definition of discrete L.M,, and suppose all latent variables have the same state space, for X,, X, and Xt. there is not only one latent
19

---

variable is conditional set, i.e., but there also is not one latent variable that d-separates any pair variables in X,, Xx}. Thus, Rank Rank(T[x,xx, (Txx,x,x,))
Proof of Rule 2:
We aim to show if Rank (xxx(((xxxxxxx,))
for any X, E X Xx, then there exists latent variable Lp that d d-separates (X,,... X,) and Lp is the parent variable of (X,, discrete 3PLSM. We first prove it by the contradiction. (X,, Xx) does not share one common latent parent, e.g,, L1 {X;,, Xy) and L2 + (Xx). due to the structure assumption in discrete 3PLSM, there exist X, E Ch as shown in Fig 5
Xx) xx) in the
L
L2
Xi
Xj
X
X5
Figure 5: Illustrative example for Rule 2.
By the graphical criteria of tensor rank condition and r < d,, one has Rank(T(x Xxxx,, # since L1 or Ly is not the conditional set that d-separates any pair variable of (X;,, X Xss X,) ( X, not be d-separates given L1), which contrary the condition Rank Xxxx =r.
D.4 Proof of Proposition 4.5
Proof. Since C1 and C2 are two causal clusters, then the elements in C1 have only one common latent variable. Without loss of generality, we L, denote the parental latent variable of C₁. Similarly, L2 denotes the parental latent variable of C2. Since C₁ and C2 are overlapping, then they have least one shared element. Let X; denote the shared element of C₁. then X, has two latent parents L₁ and T22 which contradicts with the pure child assumption in the discrete 3PLSM model. This finishes the proof.
D.5 Proof of Theorem 4.6
Proof. Based Prop. 4.3, one 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.
D.6 Proof of Theorem 4.7
Proof. We first prove this result by specific case and then extend it general case result.
Proof by Specific case
X
XA
X
XA
L
L2
L
L
L
X1
X2
X1
X
X5
X
X5
X
Figure 6: d-separation and d-connection example.
20

---

'If' part: as shown in Fig 6 suppose all support of latent space is r and r. < d,, d; is the dimension of the rank of Txx........ are r². Let L be the vectorization of joint distribution P(L3, L4) with |supp(L) =
any support of observed variables. We will show that, for
Since L2, L3 is a conditional set that d-separates all variables in (X1, '", Xg) and there is no other conditional set with smaller support, according to the graphical criteria of tensor rank, ((n. [L) = =r"
'Only if" part: now, consider the that if 1 and L2 are d-connection (Fig. In this case, given L( (represented by P(L)) x(x,Xg|L=i) cannot be decomposition as the outer product of two vectors since the contingeney table of 7rx, is not rank-one tensor by Markov assumption. That is, L is not conditional set that d-separates X1 and X2.
According to the graphical criteria of tensor rank condition, one infer that Rank (Txx (x)) [sup 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, and X, that are pure children of Lg. it is evident that Ly is the only minimal conditional set that d-separates X; from Xj. Consider a set of latent variables L, and their corresponding child sets X51 and X22. where each latent variable has least two child variables included in Xp1 p1 and X The minimal conditional set that d-separates all variables in Xp1 from those in x2 is their common latent parent set Lp. Moreover, for two variables X; and X, that do not share common latent parent, if Lp d d-separates X; and X,. then L, also d d-separates all variables in X,1 U X2 {X,, ), 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, X,, pl. x,2)) = [supp(L,)]. As all latent variables share the same state space, deduce that (supp(L,))) / !T,,
"Only if' part: if X, and X, cannot be d-separated by L, then L, does not constitute a conditional set for X U UX,, U (X, X, under Assumptions 2.2 ~ 2.4. According to the graphical criteria of tensor rank, Rank((P(X, (X,, X,, Xp1: X,2)) # [L,))(L,,)I.
D.7 Proof of Theorem 4.9
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; (remark 1). Thus, the causal structure among latent variables can identified up to Markov equivalent class by Algorithm 2 SSprtess et al. (2000).
Proof.
E Extension of Different Latent State Space
To extend our theoretical result to the case in which the state space of the latent variable may be different (i.e., r. # r,). 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, and X,, let L, and L, be their latent parent respectively, and let r be the cardinality of supp(L.) and T2 be the cardinality of supp( Lÿ), there (ank(([(x,xx))) min(r1.72).
Proof. In the discrete 3PLSM model, for two observed variables, we have x; and any one of the latent parents can d-separate X, from X,. 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.
21

---

E.1 Identification of causal cluster
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 variables Xi,X,, XR E = r for any X, Rank(T(x....
X. then (X,, x,.Xx) share the same latent parent if (x.,, X (X,, Xz. Xu3, where r RaRRaa x)),)) Rx,n(((x....)))
Proof. If RaRka(TTTT.a (x.,,.,,.. = r, there exist a variable set S with [supp(S)] = r that d-separates any pair variables in {X,, X.. X.). according to the graphical criteria tensor rank condition. In the discret LSM model and < d; (any support dimension of latent variable is less than the support dimension of observed variable), r = Rank(((x,,
Rank (T(,,, = Rank ((x,,x,)). we the conditional set is one of the latent parent of X; and X,. X, X, and X do not share the common latent parent, without loss of generality, let Ln be the parent of X;, Xj and Le be the parent of X2,, there exist the X, E Chi, such that X5 and X, cannot be d-separated given L1 X, and X, cannot be d-separated given L2. By the graphical criteria of tensor rank condition, Rank(T(x. XxX,.))) # [supp(L,) L,) or Rank(T(x, N.N, # (supp( I- Letr = min( (nnpp//pp(pp I. I. |supp( I2) we have Rank Xx,,,.,,,xxxx., # r Xf, X and X, are not a causal cluster.
have for any X;, X, E {X,, X xx. X.).
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 set of measured variables X
Output: Causal cluster C
1: Initialize the causal cluster set Ø, and g' Ø;
2: Begin the recursive procedure
3: repeat
4: for each Xj and Xx X do
5: Apply the minimal state space criteria
min(Rank(T) (T(x..x,) Rank)).aa........ ).xx,,))).Raan((TTx (x,.)) (Raan(T(X...))) 7: if RaRR (Txx,,,, Xx)... =r, for all X, X (X, X,;X,) then
6:
8:
C= CU X,,,, Xt]3:
9: end if
end for
11: until no causal cluster is found.
// Merging cluster and introducing latent variables
13: Merge all the overlapping sets in C by Prop. 4.5.
14: for each C. E C do
15: Introduce a latent variable for C
16: u + XylX, E C.).
17: end for
18: return Graph G and causal cluster C.
E.2 Conditional independence test among latent variables
Proposition F.3 (conditional independence among latent variables in different state space). In the discrete 3PLSM, suppose Assumption 2.2 ~ Assumption 2.4 holds. Let X, and X, be the pure child of T4 and T. respectively, Xp1 and X,2 be two disjoint child set of the latent set L, with 1 = 1X = LLpl then L, Lp if and only if Rank ( X = r, where r = II,,,, [s.))(L.)1-
Proof. 'If' part: in the discrete 3PLSM, we have r; < dly for any i E [k],j [p]. where k is the number of latent variables while is the number of observed variables. In the causal graph, for X₂1 X,1 and Xg2 X,2, Xa1: X22 Ch((2) for VT,, E Lp we have L, the only conditional set that d-separates Xy1 and X4e with minimal support dimension. Thus, L, also be
22

---

the minimal conditional set that d-separates any pair variables in XpI U U Now, if X; and X, are d-separated by Lp. according to the graphical criteria of tensor rank condition, one have Rank(T(x, Xx .I. xpx)) [supp(L,p]-- Since L is the joint distribution of latent variable set, we have II,,LL [supp(L.)]-
"Only if" part: the other hand. if X; and Xj are not d-separated by p, for example, L; - Li in the causal graph, then L is not a conditional set that d-separates all pair variables in {X,, X,, Xp1: X According the graphical criteria of tensor rank condition, we have Rank( X,,,,, X, xx,)) |supp(L,)) i... Rank(T(n,,a. (X,,, x x2)) IL,EL (supp(L.)]- This completes the proof.
In particular, |supp(L:) can be identified by their pure child variable, according minimal state space criteria. An intuition illustration is by mapping the conditional set variable Lp to one new latent variable (i.e., vectorization), the graphical criteria of causal cluster still hold, e.g., (Xpl Xp2 X;} causal cluster that shares 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 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 n-way tensor T(x that is used test the d-separation relations among latent variables, such CI relation is testable if | rj I.. de - max(d1..... d,)).
[p IL,
Proof. We prove it by contradiction. If [ rj >
[Lp |L,l
>
( d; - max(d),... dn), assume that
d, = max(dd, di, '., ".,d)))) where d; is the support of observed X,, there are
T(xI-xX.)= =
Σ
Xn- X
(20)
u
which is smaller rank-one decomposition than L, with support 1 !T, of tensor rank and the graphical criteria of tensor rank, have Ran.(TTx,.......) max(d)..... d. That is, no matter whether the conditional independent relations hold given Lp, the rank tensor still be the dimension of the support of (.....X It means that the CI relations can not be detected.
According to the definition
I 1 d;
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,, ..., X,,) - PXX,, .., X, XX,, ..., X, P(X,, .',, Xn.1). Thus, if the increasing of latent state space less than the sum of tensor dimensions, the CI relations among latent variable are testable. Due to assuming that > r, the CI relations among latent variables are generally testable when the causal structure sparse.
F Discussion with the Hierarchical Structures
Actually, our result can be extended to specific hierarchical structure, by constraining the structure of hidden variables. For instance, consider 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 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, demonstrated by Proposition 2. For instance, the sets (X1, X2, Xs).
23

---

X5, X6), X8. and (o X11, (12) are recognized as four distinct causal clusters. The pure measured variables from each cluster can as surrogates for their corresponding latent parents, allowing the causal cluster learning procedure to be repeated. For example, if X serves as the surrogate for 122 and X4, X7, 1 as surrogates for T.3, I.,, T.s, then (T22, T.g, I4, To) can be identified as 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.
X1 X2 Xg
Xg
X7
X5
X9
X1oX11
X12
Figure 7: Example of hierarchical structure.
G Practical Estimation of Tensor Rank
Here, 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
Algorithm 4 Practial tensor rank estimation
Input: X, (X,,, x,..., N....,,,,, ), iteration number n, threshold E,- and tested rank r Output: Boolean of rank test Initialize the minimal reconstructed error Emin + :00;
2: for < or Emin $ E do
3: i i 1;
4: T - wwwennatvvv-aaaaac(((
5:
E ||Txx,)- T |I:
6:
if E S Emin then
7:
Emii E::
8: end if
9: end for
10: p-val < Chii-Square(''s ( vec(T));
11: if p-val < then
12: return True;
13: end if
14: return False.
Besides, in the PC-TENSOR-RANC algorithm, further identify the V-structure among latent variables, the stadistic-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, and X, of latent variable L; and Lj. then L, 11 L, if (Pan,(P(X;;))) X,)) 1.
Proof. Since L; 1l Lj. we have X; 11 X, also hold in the causal graph. We have P(X,X,) P(X))((X,) T(x.) T(x,)- According to the definition of tensor rank, Rank (ank((T(x..x,))) 0
G.1 Goodness of test for CI test among latent variables
Although the proposed tool is theoretically testable, it still is approximate estimation of tensor rank by
CP decomposition in practice, How to consider a more robust approach to examine the tensor rank still be open problem in the related literature. It significantly restricts
24

---

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 3PL.SM model.
Next, 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 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, L3 {L1 L2, L3. La} given Lp E {LI L2, La. La} \ (L,, L,). The results are reported on the right side of Fig. g in which each red point represents CI test result, e.g.. the second point in the graph represents to test 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, # 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.
L2 Il La ر by examining Faak((T(,,.x,,
i.e., (Ti,,
1.
0.4-
X1 X2
X3
X4
X5
%6
X7
Xg
o'iggiffaae knd
GE
G Sd Gell ha GRAA
01 test anong latant salle
Figure 8: Goodness of fit test for conditional independent test among latent variables
H More Experimental Results
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
We first give a details definition of evaluation metrics. Specifically, the performance of causal cluster evaluated by following scores for the output model Gout from each algorithm, where the true graph is labelled G:
latent omission, the number of latents in G that do not appear in Gout divided by the total number of true latents in G;
latent commission, the number of latents in Gout that could not be mapped to a latent in G divided by the total number of true latents in G;
mismeasurementt, the number of observed variables in Gout that measuring 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 the structural model of G that do not appear in Gout divided by the possible number of edge omissions;
edge commission (EC), the number of edges in the structural model of Gout that do not exist in divided by the possible number of edge commissions;
orientation omission (00), the number of arrows in the structural model of G that do not appear in Gout divided by the possible number of orientation omissions in G;
25

---

These evaluation indicators are derived from Silva et al. (2066)
Next, we give a concrete implementation of baseline methods.
BayPy: The Bayesian Pyramid Mode (BayPy) is discrete latent variable structure learning method that assumes the latent structure is pyramid structure and the latent variable is binary. We use the implementation Gf and Dunson 2023). We set the iteration parameter to 1500 and set the search upper bound of the number of latent variables to 5.
LTM: 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 al. (201T) (since has better performance), and use the discrete information distance to learn the structure of the discrete 3PLSM model.
BPC: The Building Pure Cluster (BPC) algorithm Silva et al. (2006) is classic causal discovery method for the linear latent variable model. We use the implementation from the Tetrad Project package
Non-negative CP decomposition: To perform non-negative CP decomposition in our algorithm, use the implementation from the python package, tensorly 4 and set the maximum iteration parameter
to 1000, the ovg criterion parameter to "rec_error".
Data Generation: To generate the probability contingeney table conditional probability con- tingency table for latent variables and observed variables in our simulation studies, we use the implementation from the python package, pgmpy 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 SM3 structure, and the measurement model with MM. The data generation process follows the description in the main context and we let the support of latent variable L1, Lg to be {0, 1} and the support of latent variable T,3, Tıg 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). 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.
our
The results are presented in Table 4 and Table The performance of our method appears superior in scenarios where latent variables have differing state spaces. This improvement is attributed to the reduction the frequency of higher-order tensor rank testing, facilitated by evaluating the consistency of ranks such as Rank(T(X, 2, X,)) = Rank Xx)) Rank(T(x,.xx)) 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.
In
Table 4: Results on learning pure measurement models in the case that latent variables have different state spaces. Lower value means higher accuracy.
omissson
Lateni commission
Mismcanurements
Algorithm
Our
BayPy
1TM
BPC
Our
BayPy
1.T
BPC
Our
BayPy L.M
BPC
Sk
0.09(3)
0.2004)
0.2315)
039((1))
8.000)
0,2084)
0.030)
6.000)
0333(1
0.18(4
0.23(5)
0.3K0)
Stor M.M,
0.06()
0.17(3)
0.19(4)
0.96(1))
0.000)
0.15(3)
0.000)
0.0001
0.000)
0.15(3)
0.13(4)
0.30()
50L
0.000)
0.134))
0.10(3)
093(10)
0.000)
0.15(3)
0.000
0.000)
0.000)
0.1333
0.10()
0.90()
5%
0.1213)
0.33(7)
0.55(10)
0.95(10)
0.0000
0.306)
0.030)
0.0000
0.062))
0.50.7)
0.55(10)
0.50t0)
SMG M.M,
0.062)
0.2665)
0.50(10)
0.9((10)
0.0000
0.20(5)
0.000)
0.0000
0.00/0)
0.19(5)
0.50(10)
0.90/0)
0.03()
0,2044)
0.50 10)
0.9((10)
0.0000
0.15(4)
0.00/0)
0.0000
0.00(0)
0.11(4)
0.50(10)
0.90(0)
"htps:///itthubb.
26

---

Table 5: Results learning the structure model in the that latent variables have different state spaces. The symbol '-' indicates that the current method does not output this information. Lower value means higher accuracy.
Edge omnission
Edge commission
Orientation omisssin
Algorithm
Our
BuyPy
LTM
BPC
Our
BayPy
LTM
BPC
Our
BayPy
LTM
BPC
(.2063)
100010)
0.9000
0.000)
0.30(1]
100011)
10000)
Store Mr
10L
0.00011
1.00(10)
0.2366)
1.00(10)
0.3000
0.02(1)
0.00)
0.000)
(.00))
1.00(100
1000)))
50k
0,0000)
1,00110)
0.10K)
100010)
0.900)
0.9000
0.000)
0.000)
0.000)
1000100
10000)
0.15(3)
1000C10)
0.106)
(0010)
0.10(1)
0.900)
0.000)
0.000)
D.00)
0.0(()
0.00(
SM,+ + Mraf,
10k
0.05(1)
1.00(10)
0.13,4)
(00,10)
0.01(1
0.0000
0.000)
0.000)
(0000)
0.00())
0.00(0)
50K
0.0000)
1,00110)
0.1033
1.0010)
0.900)
0.900)
0.0000
0.0000
0.000)
0.00()
0.00(0)
I Experimental Results on Real-world Dataset
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 proos-nattional survey designed to capture information on both conventional and unconventional forms political participation in industrial societies. This dataset includes 1719 cases obtained in 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 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' TOUCCH, 'INTEREST) ("NOSAY', 'VOTING', "COMPLEX", These clusters correspond to the latent variables 'EFFI- CACY' and RRESPNNSE', respectively. In our implementation, we set the significance level to 0.0015. The result is aligned with the ground truth provided Jöreskog and Sörbom (1996).
For the depress dataset, the ground truth structure Jöreskog and Sörbom (996) includes three latent factors: Self-esteem, Depression, and Impulsiveness, with the corresponding observed clusters:
{'SELFI', 'SELF2', 'SELF3', 'SELF4' 'SELF5';
('DEPRESI', 'DEPRES2', 'DEPRES3', 'DEPRES4'); ('IMPULSI', 'IMPULS2', 'IMPULS3'.
In our implementation, we utilize 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 follows.
('SELFI', 'SELF2', 'SELF3', 'SELF5');
('DEPRESI', 'DEPRES'', 'DEPRES4'); ('IMPULSI' 'IMPULS2', "MM 'IMPULS3'.
One can see that our algorithm can learn three causal clusters corresponding to three latent factors. Such result shows that our method finds all latent variables from the depress data. In the latent structure learning process, the PC-TENSOR TEENSOR-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 (aales al.) (2024).
J Broader Impacts
The proposed Tensor Rank Condition identifies the causal structure of latent variables the discrete L.S model. Our theoretical results extend the identification bounds of causal discovery with latent variables and expand the application scope of latent variable models. instance, in psychology and social sciences, algorithm can learn the causal structure of the latent factors of interest from
27

---

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.
K
Limitation
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 high-dimensional real-works world datasets would be meaningful future direction.
28

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We emphasize our contributions in the abstract and introduction.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We have discussed the limitations of our works in Appendix.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We have provided the full set of assumptions and a complete proof.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed reproduce the main perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: We have provided the implementation details in Appendix.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: We have provided the implementation details in Appendix.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We have provided the training details in the simulation study section.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We conduct the experiments over three different random seeds.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [NA]
Justification: We do not provide the information on the computer resources.
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics http://pw//eaaapp..cooo///////aa

---

Answer: [Yes]
Justification: The datasets, that we used in the paper are properly cited.
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We have provided the broader impacts in the appendix.
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, scraped datasets)?
Answer: [NA]
Justification: the paper does not pose such risk.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: The datasets, that used in the paper are properly cited.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We have provided the synthetic datase.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects. 15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
30


Reviews:
[{"review_id": "nB3kskI7O9", "reviewer": "Reviewer_tR91", "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:\n1) All latent variables are discrete \n2) There are no connections between observed variables (i.e. observed variables are independent when conditioned on latent variables\n3) In the unknown causal structure graph, each observed variable has exactly one latent variable parent.\n4) The joint probability distribution of observed variables is fully known, and there is no noise in the measurement.\n5) Each latent variable has at least three pure variables as children.\n6) Other technical assumptions.\n\nThe 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.", "questions": "see above\n\n-----\nDuring rebuttal score was increased 3 --> 4", "limitations": "na", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The problem studied in this paper covers an important case in causal structure learning literature. The measurement model with discrete latent variables is an important special case of causal structure models observed in practice, hence identifiability results and structure learning algorithms are important for this problem.\n\nThe paper is well-written, and the claims are sound. Theoretical results are supported by experiments.", "weaknesses": "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].\n\n[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. \n\nThe 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)).\n\nConsidering 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]? \n\n[1] Learning latent causal graphs via mixture oracles\nB Kivva, G Rajendran, P Ravikumar, B Aragam - Advances in Neural Information Processing Systems, 2021", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your careful and valuable comments. We will respond to these issues point by point.\n\n> Q1: [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.\nIn particular, [1] seems to obtain a stronger result under similar, if not weaker, assumptions, and this paper does not cite [1].\n\n\n**A1**: Thank you for pointing us to this interesting work. We would like to discuss its connection with our work. \n\nThe main difference is that the identifiability of [1] requires to assume that the \"Mixture Oracle\" is known (i.e., the mixture model over $\\mathbf{X}$ is identifiable), without discussing how to obtain it, especially in discrete data while we do not require such an assumption. 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. For instance, [2] indicates that a sufficient and necessary condition for identifying the parameters of a discrete mixture model is the presence of $2K-1$ strongly separate variables, where $K$ is the number of mixture components. This structural condition is more stringent than compared to our requirements.\nThe reason is that identifying the mixture model requires learning the latent distribution $P(\\mathbf{L})$, while our method does not rely on this.\nFurthermore, as discussed in Sec. 6 in [1], learning mixture models is a nontrivial problem. The author in [1] uses the approximate method, such as the K-means algorithm, to estimate the number of mixture components $k(S)$ for all $S \\subset X$, which can affect the accuracy of the estimates in practice. Meanwhile, the K-means algorithm cannot be directly used in the discrete data, we thus do not include it in our baselines.\n\n\n>Q2:  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)).\nConsidering 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]?\n\n**A2**: We would like to clarify the following points:\n\n**Identification based on Tensor Decomposition.**\n Roughly speaking, [1] depends on unique tensor decomposition (actually, a technology of parameter estimation) and requires partial information from a Mixture Oracle. However, it is difficult to obtain the Mixture Oracle and unbiased parameter estimates. In contrast, our theoretical approach focuses on tensor rank constraints across different sets of variables, without directly relying on unique tensor decomposition or any prior information about the Mixture Oracle.\n\nSpecifically, in [1], the identification of the measurement model relies on unique tensor decomposition, such as the generalized Kruskal's theorem. To construct such a tensor, we require partial information from a Mixture Oracle, such as $k(S)$, where $k(S) = dim(Pa(S))$ according to observation 2.7 in [1]. It is important to note that $k(S)$ for any subset $S \\subset X$  cannot be estimated from the tensor rank. As demonstrated by the graphical implications of tensor rank, the tensor rank is determined by the cardinality of the conditional set. That is, $Rank(P(S)) \\neq dim(Pa(S)) = k(S)$. For example, consider a structure $L_1 \\to L_2$, $X_1$ is children of $L_1$ and $\\{X_2, X_3\\}$ are children set of $L_2$. In this case, the tensor rank of the joint probability tensor over $S = \\{X_1, X_2, X_3\\}$ is $|supp(L_2)|$. According to the mixture oracle in [1], it requires that $k(S) = |supp(L_1, L_2)|$. In contrast, our theoretical result does not directly rely on the unique decomposition of tensors, but rather examines tensor rank constraints over various variable sets.\nA key challenge with the decomposition-based method is the difficulty in obtaining unbiased parameter estimates. Our method avoids this issue by focusing on the number of parameters, specifically the cardinality of latent support, making it a more practical solution.\n\n**Novelty.**\nIn our paper, we propose a statistically testable method, termed the tensor rank condition, which establishes the connection between tensor rank and d-separation among observed variables. The tensor rank condition is applicable to general discrete causal models and is not restricted to measurement models. This represents one of our main contributions compared to [1]. Based on the tensor rank condition, we provide an identification algorithm that can determine the causal structure of discrete latent structure models with a theoretical guarantee. Unlike [1], our algorithm offers a solution for discrete latent variable models without requiring any prior knowledge about the mixture model, thereby elegantly eliminating the need for a mixture oracle. Moreover, our method offers a theoretical guarantee and is simple and efficient due to the testability of the tensor rank condition.\n\n**Acknowledgements.**\nThank you for raising the constructive questions, which have inspired us to further explore discrete latent variable models. We will incorporate these discussions in the revised version, specifically in the 'Related Works' section. If you believe your concerns have been addressed, we kindly request that you consider adjusting your initial score accordingly. If any explanations remain unclear, we are open to further discussion.\n\nReference:\n\n[1]. Kivva B, Rajendran G, Ravikumar P, et al. Learning latent causal graphs via mixture oracles.\n\n[2]. Tahmasebi B, Motahari S A, Maddah-Ali M A. On the identifiability of finite mixtures of finite product measures.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "oTu2EBbzS6", "reviewer": "Reviewer_hs7U", "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.", "questions": "typo: In Figure 2(b), LVM should be LSM.", "limitations": "see weakness", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is clearly written and well-organized.\n\n2. The proposed tensor rank condition establishes the connection between algebraic constraints and d-separation relations in discrete causal models. This tool has the potential to explore more causal discovery problems in discrete causal models\n\n3. Compared to traditional methods of the linear latent variable model, such as rank constraints of the covariance matrix, the tensor rank condition takes a meaningful step in latent variable modeling in more general cases.\n\n4. The proposed algorithm looks simple but effective, addressing the identification of discrete latent variable models.", "weaknesses": "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?\n\n2. 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?\n\n3. 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}$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your valuable comments and suggestions and thank you for your positive assessment of our work.\n\n>Q1: 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?\n\n**A1**: Thank you for your suggestion. You are correct. We only require the cardinality of the observed variables to equal that of the latent variables. We will revise this in the revision.\n\n>Q2: 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? \n\n**A2**: Thanks for raising these critical questions. If there are only two pure-measured children for each latent variable, it can result in an indistinguishable structure. For instance, as shown in the proof of Proposition 4.3, the tensor rank condition for a three-variable probability tensor leads to equivalence classes (Fig. 4 (a) $\\sim$ (c)). However, with the four-way tensor, the cluster cannot be identified due to the structure illustrated in Fig. 5. Thus, the three-pure measured variable assumption is a sufficient condition to ensure the identification of the measurement model. If this assumption is not met, our algorithm may output a causal structure where the number of latent variables is smaller than the true number. However, to test the conditional independence (CI) relations among the latent variables, only two pure children for each latent variable are necessary (See Theorem 4.7). Thus, given the causal cluster with only two pure children for each latent variable, the CI relations can be tested, and the structure model remains identifiable. One can see more discussions in the general response.\n\n> Q3: In Proposition F.3,  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 r. \n\n**A3**: Thank you for your suggestion. We have revised it in the revision.\n\n> Q4: typo: In Figure 2(b), LVM should be LSM.\n\n**A4**: Thank you for your suggestion. We have corrected it in the revision.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "48Dbuxy6TZ", "reviewer": "Reviewer_Snze", "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.", "questions": "**Critical points on assumptions**\n- *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)$?\n- *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?\n- 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). \n- *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.\n\n\n**Experiments related**:\n\n- 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.  \n- 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.\n-  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.\n- 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.\n\n**Relatively minor notes**:\n- *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.\n- *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.\n- *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\n\n**Typos etc.**:\n- Prop 4.3: I think Rule 2 statement is missing “if”. Also, why $L_i$ instead of $L$?\n- Theorem 4.7: varaible\n- Theorem 4.9: TESNOR\n- L177: missing period\n- L800: TENSKR\n- CP decomposition: please spell out at the first appearance\n- Figure 8: make the markers larger, please.", "limitations": "Limitations are mostly addressed. I suggest the authors to see my comments on questions to further clarify them.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The literature mostly focuses on learning linear latent models. Instead, this paper aims to address discrete latent models for which the existing work is scarce (the paper outlines that they are limited to very restrictive structures, e.g., trees).\n\nThe whole paper builds on making a nice observation: the tensor rank of the contingency tables of the joint dist. of the observed variables are connected to the support of the variables that d-separate them. This observation is substantiated in the main result Theorem 3.3. All the subsequent results (mainly the algorithms) build on this main observation, which leads to rather simple proofs. I find this simplicity as a strength. The practical implementation of the proposed method is also clearly explained using existing techniques to test the tensor rank.", "weaknesses": "- *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.\n- 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). \n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful and valuable questions and for spending the time and effort on this review. We will respond to these issues point by point.\n\n>Q1: Allowing edges between observed variables: ... I think you can be more open about it, e.g., what are the challenges, what are the missing pieces?\n\n**A1**: One of the challenges in impure structure is accurately identifying the number of latent variables. As shown in Figure 1 in our attached PDF, the rank constraints over the probability tensor can be equal by the graphical implication of tensor rank, hindering the identification of latent variables. Although we can detect the absence of edges between pairs of variables (as in the structure described in Sec. 7), a careful search strategy is still required, along with proper assumptions on the cardinality of latent support, to distinguish these equivalent classes. We will address this issue in our future work.\n\n>Q2: Structural constraints in the literature: I think you need to be more direct and provide exact requirements/structural constraints and results. ... Can you elaborate on the similarities and differences between the roles of these assumptions? \n\n**A2**: In the linear non-Gaussian model, Cai et al. and Xie et al. show that the identification of the measurement model only relies on the two-pure children assumption, due to the availability of higher-order statistics from non-Gaussianity. However, in the linear Gaussian model, the three-pure children assumption is necessary, due to the indistinguishable equivalence classes in two-pure condition by Tetrad constraints (as noted by Silva et al. and Kummerfeld et al.).  Interestingly, when only four-way tensors are considered in discrete models, the tensor rank condition serves as a 'nonlinear' version of the Tetrad constraints, resulting in similar structural limitations. Moreover, for discrete latent variable models, Gu and Dunson (2023) and Gu (2022) address only partial structures and their identifiability. For instance, they focus on either measurement models (under the same three-pure children assumption) or pyramid structures, without providing a comprehensive approach for all possible structures. We will include this discussion in the `Related Works' Section.\n\n>Q3: In Appendix D, ... 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.\n\n**A3**: The three-pure children assumption is a sufficient condition that ensures the identifiability of latent variables using the tensor rank condition over a four-way tensor (see more details in the general response). A similar reasoning applies in linear Gaussian latent variable models (e.g., Silva et al. and Kummerfeld et al.).\n\nIn the presence of an impure structure, the latent variable may not be correctly identified (see **A1**). Additionally, impure structures can arise when the collected variables have direct causal relationships. For example, in a questionnaire survey, the observed variables ‘occupations' and ‘income' may exhibit an impure structure because the attributes of different occupations can directly impact income.\n\n>Q4: Support of latent variables: … all latent variables have the same number of categories, with extensions provided in Appendix F”. ... If this is indeed the case, then I suggest the authors explicitly state it in the main paper. \n\n**Q4**: Thank you for your careful observation. We will add the following illustrations to Section 4 to avoid confusion.\n\n\"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 by sequentially testing the cardinality of the latent support (see details in Appendix F).\"\n\n>Q5&6: I see that the definitions of metrics are in Appendix I. It would have been nicer to squeeze them into the main paper.\n\n**A5&6**: Thank you for your suggestion. We will move the real-world application section into the appendix and add the details of evaluation metrics into the simulation experiment section.\n\n>Q7&8: I think your method should be able to handle an arbitrary number of children as long as there are at least 3. …. Perhaps starting from 1k would show the limits of the approach and help us to understand the performance better.\n\n**A7&8**: Due to limited space, please see our response in the `Supplementary Experiments' part of the general response section.\n\n>Q9: Definition 2.1 (Discrete LSM): Is this a proper name? \n\n**A9**: Thank you for your constructive suggestion. We will revise \"discrete LSM\" to \"three-pure discrete LSM (abbreviated as *discrete 3PLSM*) in the revision.\" \n\n>Q10: Theorem 4.7: Please be careful when using $p$ in notations.\n\n **A10**: We have revised them to $L_q$ and $X_p$ to avoid confusion.\n\n>Q11: Conclusion Section 8: Overall, I liked this conclusion. That being said, being more direct and recalling the main structural assumptions would have been good.\n\n**A11**: We have added a recall of the three-pure children assumption and revised the last paragraph in the conclusion as follows:\n\n\"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, such as impure structures and hierarchical structures, would be a meaningful future direction.\"\n\n>Q12: Typos etc.\n\n**A12**: Thank you very much for your careful review. We have corrected these issues in the revision.\n\nWe sincerely thank the reviewer for their careful review and thoughtful suggestions, which have been very instructive. We will incorporate these discussions in the revision to improve our manuscript. If any explanations remain unclear, we welcome further discussion.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "U9Qw9mV3Mb", "reviewer": "Reviewer_Upr4", "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.", "questions": "1. How does this paper compare to works like [1] where rank constraint is also used in a non-linear setting?\n\n[1] Kong, Lingjing, et al. \"Learning Discrete Concepts in Latent Hierarchical Models.\" *arXiv preprint arXiv:2406.00519* (2024).", "limitations": "See weakness.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. As far as I know, the tensor rank condition is a novel contribution. Unlike previous on rank deficiency, this method can handle non linear relations. \n2. The experiments are done on both simulated and real-world dataset.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your careful review and suggestions and would like to thank you for your positive assessment of our work.\n\n>Q1: 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.\n\n**A1**: We would like to mention that to render the identifiability of the latent variable structure, we introduce the assumptions of the three pure children and faithfulness. \n\nRegarding the three-pure child assumption, it is a commonly used condition, well-studied in both linear and discrete models, as demonstrated by Silva et al., 2006, Kummerfeld and Ramsey, 2016, and Chen et al., 2024 (more related works can be found in the introduction of our manuscript). It is worth noting that the pure child assumption is often valid when data is collected through questionnaires, which is a common practice in fields such as social science, psychology, and medical science. For a more detailed discussion of the three-pure children assumption, please refer to the general response.\n\nRegarding the faithfulness assumption, it plays a significant role in constraint-based methods, ensuring that the learned structure accurately represents a causal graph. It is considered a standard assumption, which is known to hold in simple systems such as linear Gaussian models [Meek (1995)]. This concept has been extensively discussed in the literature [Spirtes et al., 2000; Spirtes and Glymour, 1991].\n\nWe appreciate your comments and will discuss these assumptions further in the revision.\n\n>Q2: \nHow does this paper compare to works like [1] where rank constraint is also used in a non-linear setting?\n\n**A2**: We would like to clarify that there are two main differences compared to [1].\n\nFirst, the tensor rank condition in our work can capture more d-separation information among observed variable sets. For example, the graphical implications of tensor rank allow us to infer the d-separation among any pair of variables within the variable set $\\mathbf{X}_p$, whereas the rank of the probability table only infers the d-separation between two variables (or vectors). In particular, when only two-way tensors are considered, [1] can be seen as a specific case of our approach.\n\nSecond, in [1], the observed variables are continuous, making the recovery of the distribution of discrete variables untestable. Additionally, the model in [1] does not allow for 'triangle structures' among the latent variables. In contrast, our work does not require the recovery of the distribution of discrete variables and allows for any dependence among latent variables. Furthermore, [1] assumes that the cardinality of latent support is the same, whereas our work allows for different cardinalities of latent support (see Appendix F).\n\n\nReference:\n\n[1] Kong, Lingjing, et al. \"Learning Discrete Concepts in Latent Hierarchical Models.\" arXiv preprint arXiv:2406.00519 (2024).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
**General Response**

We thank the reviewers for their efforts in reviewing our manuscript and for the insightful comments and suggestions. Please see below for our general response.

**Sufficient Condition: Three-Pure Children Assumption.**
To ensure the identifiability of latent variables, the pure children assumption is generally required and well-studied in the related literature (e.g., Silva et al., 2006; Kummerfeld and Ramsey, 2016; Chen et al., 2024; Bollen, 2002; Bartholomew et al., 2011), as discussed in the first paragraph of the introduction in our manuscript. Besides, the three-pure children assumption is necessary to ensure that the latent variable can be identified by the tensor rank condition. The reason is as follows. If there are only two pure-measured children for each latent variable, it can lead to an indistinguishable structure. For example, as shown in the proof of Proposition 4.3, the tensor rank condition for a three-variable probability tensor has equivalence classes (Fig. 4 (a) $\sim$ (c)). However, for the four-way tensor, the cluster cannot be identified due to the structure shown in Fig. 5. Thus, the three-pure measured variable assumption is a sufficient condition to ensure the identification of the measurement model. If this assumption is violated, our algorithm may output a causal structure where the number of latent variables is smaller than the true number. However, to test the conditional independence (CI) relations among the latent variables, only two pure children for each latent variable are required (See Theorem 4.7). That is, given the causal cluster with only two pure children for each latent variable, the CI relations can still be tested, and the structure model remains identifiable.

**Supplementary Experiments (Response to #Reviewer Snze).**
Due to limited space, we are responding to the supplementary experimental part here. We aim to (i) evaluate the performance of our algorithm with different numbers of measured variables, and (ii) explore the behavior of our algorithm when the number of samples is much smaller. The results are reported in Tables 1 to 4 in our attached PDF.

In Table 1 $\sim$ 2, one can see that our method still achieves good performance even when the number of measured variables is different. In fact, it can enhance the accuracy in determining the number of latent variables, as a latent variable can be identified from only its three pure children using the tensor rank condition. 


Moreover, in Table 3 $\sim$ 4, the performance of our method is not good when the sample size is small (e.g., 1k sample size) because the tensor rank is inaccurately calculated in such cases. The 'mismeasurements' metrics are also lower because most of the observed variables are grouped into the same cluster in the procedure of finding causal clusters. As the sample size increases, our method achieves better performance.

Meta-review: 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
Decision: Accept (poster)