Learning latent causal graphs via mixture oracles
Year: 2021

Abstract:
We study the problem of reconstructing a causal graphical model from data in the presence of latent variables. The main problem of interest is recovering the causal structure over the latent variables while allowing for general, potentially nonlinear dependencies. In many practical problems, the dependence between raw observations (e.g. pixels in an image) is much less relevant than the dependence between certain high-level, latent features (e.g. concepts or objects), and this is the setting of interest. We provide conditions under which both the latent representations and the underlying latent causal model are identifiable by a reduction to a mixture oracle. These results highlight an intriguing connection between the well-studied problem of learning the order of a mixture model and the problem of learning the bipartite structure between observables and unobservables. The proof is constructive, and leads to several algorithms for explicitly reconstructing the full graphical model. We discuss efficient algorithms and provide experiments illustrating the algorithms in practice.

heading: 1 Introduction
text: Understanding causal relationships between objects and/or concepts is a core component of human reasoning, and by extension, a core component of artificial intelligence [40, 53]. Causal relationships are robust to perturbations, encode invariances in a system, and enable agents to reason effectively about the effects of their actions in an environment. Broadly speaking, the problem of inferring causal relationships can be broken down into two main steps: 1) The extraction of high-level causal features from raw data, and 2) The inference of causal relationships between these high-level features. From here, one may consider estimating the magnitude of causal effects, the effect of interventions, reasoning about counterfactuals, etc. Our focus in this paper will be the problem of learning causal relationships between latent variables, which is closely related to the problem of learning causal representations [63]. This problem should be contrasted with the equally important problem of causal inference in the presence of latent confounders [e.g. 3, 18, 35, 68, 72]; see also Remark 2.1.
Causal graphical models [53, 54] provide a natural framework for this problem, and have long been used to model causal systems with hidden variables [23–26, 58, 59]. It is well-known that in general, without additional assumptions, a causal graphical model given by a directed acyclic graph (DAG) is not identifiable in the presence of latent variables [e.g., 53, 71]. In fact, this is a generic property of nonparametric structural models: Without assumptions, identifiability is impossible, however, given enough structure, identifiability can be rescued. Examples of this phenomenon include linearity [3, 6, 15, 28, 78], independence [1, 10, 78], rank [15, 28], sparsity [6], and graphical constraints [3, 4].
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
In this paper, we consider a general setting for this problem with discrete latent variables, while allowing otherwise arbitrary (possibly nonlinear) dependencies. The latent causal graph between the latent variables is also allowed to be arbitrary: No assumptions are placed on the structure of this DAG. We do not assume that the number of hidden variables, their state spaces, or their relationships are known; in fact, we provide explicit conditions under which all of this can be recovered uniquely. To accomplish this, we highlight a crucial reduction between the problem of learning a DAG model over these variables—given access only to the observed data—and learning the parameters of a finite mixture model. This observation leads to new identifiability conditions and algorithms for learning causal models with latent structure.
Overview Our starting point is a simple reduction of the graphical model recovery problem to three modular subproblems:
1. The bipartite graph Γ between hidden and observed nodes, 2. The latent distribution P(𝐻) over the hidden variables 𝐻 , and 3. A directed acyclic graph (DAG) Λ over the latent distribution.
From here, the crucial observation is to reduce the recovery problems for Γ and P(𝐻) to the problem of learning a finite mixture over the observed data. The latter is a well-studied problem with many practical algorithms and theoretical guarantees. We do not require parametric assumptions on this mixture, which allows for very general dependencies between the observed and hidden variables. From this mixture model, we extract what is needed to learn the full graph structure.
This perspective leads to a systematic, modular approach for learning the latent causal graph via mixture oracles (see Section 2 for definitions). Ultimately, the application of these ideas requires a practical implementation of this mixture oracle, which is discussed in Section 6.
Contributions More precisely, we make the following contributions:
1. (Section 3) We provide general conditions under which the latent causal model 𝐺 is identifiable (Theorem 3.2). Surprisingly, these conditions mostly amount to nondegeneracy conditions on the joint distribution. As we show, without these assumptions identifiability breaks down and reconstruction becomes impossible.
2. (Section 4) We carefully analyze the problem of reconstructing Γ under progressively weaker assumptions: First, we derive a brute-force algorithm that identifies Γ in a general setting (Theorem 4.2), and then under a linear independence condition we derive a polynomial-time algorithm based on tensor decomposition and Jennrich’s algorithm (Theorem 4.8).
3. (Section 5) Building on top of the previous step, where we learn the bipartite graph and sizes of the domains of latent variables, we develop an efficient algorithm for learning the latent distribution P(𝐻) from observed data (Theorem 5.4).
4. (Section 6-7) We implement these algorithms as part of an end-to-end pipeline for learning the full causal graph and illustrate its performance on simulated data.
A prevailing theme throughout is the fact that the hidden variables leave a recognizable “signature” in the observed data through the marginal mixture models induced over subsets of observed variables. By cleverly exploiting these signatures, the number of hidden variables, their states, and their relationships can be recovered exactly.
Previous work Latent variable graphical models have been extensively studied in the literature; as such we focus only on the most closely related work on causal graphical models here. Early work on this problem includes seminal work by Elidan et al. [22], Friedman et al. [27], Martin and VanLehn [47]. More recent work has focused on linear models [3, 28, 68, 78] or known structure [21, 38, 65]. When the structure is not known a priori, we find ourselves in the realm of structure learning, which is our focus. Less is known regarding structure learning between latent variables for nonlinear models, although there has been recent progress based on nonlinear ICA [36, 50]. For example, [80] proposed CausalVAE, which assumes a linear structural equation model and knowledge of the concept labels for the latent variables, in order to leverage the iVAE model from [36]. By contrast, our results make no linearity assumptions and do not require these additional labels. While this paper was under
review, we were made aware of the recent work [46] that studies a similar problem to ours in a general, nonlinear setting under faithfulness assumptions. It is also worth noting recent progress on learning discrete Boltzmann machines [11, 12], which can be interpreted as an Ising model with a bipartite structure and a single hidden layer—in particular, there is no hidden causal structure. Nevertheless, this line of work shows that learning Boltzmann machines is computationally hard in a precise sense. More broadly, the problem of learning latent structure has been studied in a variety of other applications including latent Dirichlet allocation [8, 9], phylogenetics [51, 64], and hidden Markov models [2, 30].
A prevailing theme in the causal inference literature has been negative results asserting that in the presence of latent variables, causal inference is impossible [20, 32, 61, 62]. Our results do not contradict this important line of work, and instead adopts a more optimistic tone: We show that under reasonable assumptions—essentially that the latent variables are discrete and well-separated— identifiability and exact recovery of latent causal relationships is indeed possible. This optimistic approach is implicit in recent progress on visual relationship detection [52], causal feature learning [14, 43], and interaction modeling [37, 41]. In this spirit, our work provides theoretical grounding for some of these ideas.
Mixture models and clustering While our theoretical results in Sections 3-5 assume access to a mixture oracle (see Definition 2.5), in Section 6 we discuss how this oracle can be implemented in practice. To provide context for these results, we briefly mention related work on learning mixture models from data. Mixture models can be learned under a variety of parametric and nonparametric assumptions. Although much is known about parametric models [e.g. 42], of more interest to us are nonparametric models in which the mixture components are allowed to be flexible, such as mixtures of product distributions [31, 33], grouped observations [60, 75] and general nonparametric mixtures [7, 66]. In each of these cases, a mixture oracle can be implemented without parametric assumptions. In practice, we use clustering algorithms such as 𝐾-means or hierarchical clustering to implement this oracle. We note also that the specific problem of consistently estimating the order of a mixture model, which will be of particular importance in the sequel, has been the subject of intense scrutiny in the statistics literature [e.g. 16, 19, 39, 45].
Broader impacts and societal impact Latent variable models have numerous practical applications. Many of these applications positively address important social problems, however, these models can certainly be applied nefariously. For example, if the latent variables represent private, protected information, our results imply that this hidden private data can be leaked into publicly released data, which is obviously undesirable. Understanding how to infer unprotected data while safeguarding protected data is an important problem, and our results shed light on when this is and isn’t possible.

heading: 2 Background
text: Let 𝐺 = (𝑉,𝐸) be a DAG with 𝑉 = (𝑋,𝐻), where 𝑋 ∈ R𝑛 denotes the observed part and 𝐻 ∈ Ω := Ω1 × · · · × Ω𝑚 denotes the hidden, or latent, part. Throughout this paper, we assume that each Ω𝑖 is a discrete space with |Ω𝑖| ≥ 2. We assume further that there are no edges between
observed variables and no edges from observed to hidden variables, and that the distribution of 𝑉 satisfies the Markov property with respect to 𝐺 (see the supplement for definitions). Under these assumptions, 𝐺 decomposes as the union of two subgraphs 𝐺 = Γ ∪ Λ, where Γ is a directed, bipartite graph of edges pointing from 𝐻 to 𝑋 , and Λ is a DAG over the latent variables 𝐻 . Similar assumptions have appeared in previous work [3, 46, 78], and although nontrivial, they encapsulate our keen interest in reconstructing the structure Λ amongst the latent variables, and captures relevant applications where the relationships between raw observations is less relevant than so-called “causal features” [13, 14]. See Figure 1 for examples.
Throughout this paper, we use standard notation such as pa(𝑗) for parents, ch(𝑗) for children, and ne(𝑗) for neighbors. Given a subset 𝑉 ′ ⊂ 𝑉 , pa(𝑉 ′) := ∪𝑗∈𝑉 ′ pa(𝑗) and given a subgraph 𝐺′ ⊂ 𝐺, pa𝐺′(𝑉
′) := pa(𝑉 ′)∩𝐺′, with similar notation for children and neighbors. We let 𝐴 ∈ {0, 1}|𝑋|×|𝐻| denote the adjacency matrix of Γ and denote its columns by 𝑎𝑗 ∈ {0, 1}|𝑋|. Remark 2.1. Our goal is to learn the hidden variables 𝐻 and the causal graph between them, defined above by Λ. To accomplish this, our main result (Theorem 3.2) shows how to identify (Γ,P(𝐻)), from which Λ can be recovered (see Section 3 for details). It is important to contrast this problem with problems involving latent confounders [e.g. 3, 18, 35, 68, 72], where the goal is to learn the causal graph between the observed variables 𝑋 . In our setting, there are no edges between the observed variables.

heading: 2.1 Assumptions
text: It is well-known that without additional assumptions, the latent variables 𝐻 cannot be identified from 𝑋 , let alone the DAG Λ. For example, we can always replace a pair of distinct hidden variables 𝐻𝑖 and 𝐻𝑗 with a single hidden variable 𝐻0 that takes values in Ω𝑖 × Ω𝑗 . Similarly, a single latent variable can be split into two or more latent variables. In order to avoid this type of degeneracy, we make the following assumptions: Assumption 2.2 (No twins). For any hidden variables 𝐻𝑖 ̸= 𝐻𝑗 we have neΓ(𝐻𝑖) ̸= neΓ(𝐻𝑗). Assumption 2.3 (Maximality). There is no DAG 𝐺′ = ((𝑋,𝐻 ′), 𝐸′) such that:
1. P(𝑋,𝐻 ′) is Markov with respect to 𝐺′;
2. 𝐺′ is obtained from 𝐺 by splitting a hidden variable (equivalently, 𝐺 is obtained from 𝐺′ by merging a pair of vertices);
3. 𝐺′ satisfies Assumption 2.2.
These assumptions are necessary for the recovery of Λ in the sense that, without these assumptions, latent variables can be created or destroyed without changing the observed distribution P(𝑋). Informally, the maximality assumption says that if there are several DAGs that are Markov with respect to the given distribution, we are interested in recovering the most informative among them. Finally, we make a mild assumption on the probabilities, in order to avoid degenerate cases where certain configurations of the latent variables have zero probability: Assumption 2.4 (Nondegeneracy). The distribution over 𝑉 = (𝑋,𝐻) satisfies:
(a) P(𝐻 = ℎ) > 0 for all ℎ ∈ Ω1 × . . .× Ω𝑘.
(b) For all 𝑆 ⊂ 𝑋 and 𝑎 ̸= 𝑏, P(𝑆|pa(𝑆) = 𝑎) ̸= P(𝑆|pa(𝑆) = 𝑏), where 𝑎 and 𝑏 are distinct configurations of pa(𝑆).
Without this nondegeneracy condition, 𝐻 cannot be identified; see the supplement for details.

heading: 2.2 Mixture oracles
text: Let 𝑆 ⊂ 𝑋 be a subset of the observed variables. We can always write the marginal distribution P(𝑆) as
P(𝑆) = ∑︁ ℎ∈Ω P(𝐻 = ℎ)P(𝑆 |𝐻 = ℎ). (1)
When 𝑆 = 𝑋 , this can be interpreted as a mixture model with 𝐾 := |Ω| components. When 𝑆 ( 𝑋 , however, multiple components can “collapse” onto the same component, resulting in a mixture with fewer than 𝐾 components. Let 𝑘(𝑆) denote this number, so that we may define a discrete random variable 𝑍 with 𝑘(𝑆) states such that for all 𝑗 ∈ [𝑘(𝑆)], we have
P(𝑆) = 𝑘(𝑆)∑︁ 𝑗=1 P(𝑍 = 𝑗)⏟ ⏞ :=𝜋(𝑆,𝑗) P(𝑆 |𝑍 = 𝑗)⏟ ⏞ :=𝐶(𝑆,𝑗) = 𝑘(𝑆)∑︁ 𝑗=1 𝜋(𝑆, 𝑗)𝐶(𝑆, 𝑗). (2)
Then 𝜋(𝑆, 𝑗) is the weight of the 𝑗th mixture component over 𝑆, and 𝐶(𝑆, 𝑗) is the corresponding 𝑗th component. It turns out that these probabilities precisely encode the conditional independence structure of 𝐻 . To make this formal, we define the following oracle: Definition 2.5. A mixture oracle is an oracle that takes 𝑆 ⊂ 𝑋 as input and returns the number of components 𝑘(𝑆) as well as the weights 𝜋(𝑆, 𝑗) and components 𝐶(𝑆, 𝑗) for each 𝑗 ∈ [𝑘(𝑆)]. This oracle will be denoted by MixOracle(𝑆).
Although our theoretical results are couched in the language of this oracle, we provide practical implementation details in Section 6 and experiments to validate our approach in Section 7.
A sufficient condition for the existence of a mixture oracle is that the mixture model over 𝑋 is identifiable. This is because identifiability implies that the number of components 𝐾, the weights P(𝑍 = 𝑗), and the mixture components P(𝑋 |𝑍 = 𝑗) are determined by P(𝑋). The marginal weights 𝜋(𝑆, 𝑗) and components 𝐶(𝑆, 𝑗) can then be recovered by simply projecting the full mixture over 𝑋 onto 𝑆. Remark 2.6. In fact, we do not need the full power of MixOracle. For our algorithms it is sufficient to have access to 𝑘(𝑆) for a sufficiently large family of 𝑆 ⊂ 𝑋 , the list of weights 𝜋(𝑋, 𝑗), and a map that relates components in the full mixture over 𝑋 to the components in the marginal mixtures over each variable 𝑋𝑖 (see Section 5 for details).
Before concluding this section, we note an important consequence of Assumption 2.4 that will be used in the sequel: Observation 2.7. Under Assumption 2.4, for any 𝑆 ⊆ 𝑋
𝑘(𝑆) = ∏︁
𝐻𝑖∈pa(𝑆)
dim(𝐻𝑖) =: dim(pa(𝑆)).
Proof. By the Markov property, 𝑆 is independent of 𝐻 ∖ pa(𝑆). There are dim(pa(𝑆)) possible assignments to the hidden variables in pa(𝑆) and by Assumption 2.4, distinct assignments to the hidden variables induce distinct components in the marginal distribution 𝑃 (𝑆). Hence, by definition, 𝑘(𝑆) = dim(pa(𝑆)).

heading: 3 Recovery of the latent causal graph
text: We first consider the oracle setting in which we have access to MixOracle(𝑆).
Observe that the problem of learning 𝐺 can be reduced to learning (Γ,P(𝐻)): Since we can decompose 𝐺 into a bipartite subgraph Γ and a latent subgraph Λ, it suffices to learn these two components separately. We then further reduce the problem of learning Λ to learning the latent distribution P(𝐻). First, we will show how to reconstruct Γ from MixOracle(𝑆). Then, we will show how to learn the latent distribution P(𝐻) from MixOracle(𝑆). Thus, the problem of learning 𝐺 is reduced to the mixture oracle:
𝐺 → (Γ,P(𝐻)) → MixOracle(𝑆).
In the sequel, we focus our attention on recovering (Γ,P(𝐻)). In order to recover P(𝐻), we will require the following assumption: Assumption 3.1 (Subset condition). We say that the bipartite graph Γ satisfies the subset condition (SSC) if for any pair of distinct hidden variables 𝐻𝑖, 𝐻𝑗 the set neΓ(𝐻𝑖) is not a subset of neΓ(𝐻𝑗).
This assumption is weaker than the common “anchor words" assumption from the topic modeling literature. The latter assumption says that every topic has a word that is unique to this topic, and it is commonly assumed for efficient recovery of latent structure [8, 9].
Under Assumption 3.1, we have the following key result: Theorem 3.2. Under Assumptions 2.2, 2.3, 2.4, and 3.1, (Γ,P(𝐻)) can be reconstructed from P(𝑋) and MixOracle(𝑆). Furthermore, if additionally the columns of the bipartite adjacency matrix 𝐴 are linearly independent, there is an efficient algorithm for this reconstruction.
The proof is constructive and leads to an efficient algorithm as alluded to in the previous theorem. An overview of the main ideas behind the proof of this result are presented in Sections 4 and 5; the complete proof of this theorem can be found in the supplement.
As presented, Theorem 3.2 leaves two aspects of the problem unresolved: 1) Under what conditions does MixOracle(𝑆) exist, and 2) How can we identify Λ from P(𝐻)? As it turns out, each of these problems is well-studied in previous work, which explains our presentation of Theorem 3.2. For completeness, we address these problems briefly below.
Existence of MixOracle(𝑆) A mixture oracle exists if the mixture model over 𝑋 is identifiable. As discussed in Section 1, such identifiability results are readily available in the literature. For example, assume that for every 𝑆 ⊆ 𝑋 , the mixture model (1) comes from any of the following families:
1. a mixture of gaussian distributions [73, 79], or 2. a mixture of Gamma distributions [73], or 3. an exponential family mixture [79], or 4. a mixture of product distributions [74], or 5. a well-separated (i.e. in TV distance) nonparametric mixture [7].
Then (Γ,P(𝐻)) is identifiable. The list above is by no means exhaustive, and many other results on identifiability of mixture models are known (e.g., see the survey [48]).
Identifiability of Λ Once we know P(𝐻) (e.g. via Theorem 3.2), identifying Λ from P(𝐻) is a well-studied problem with many solutions [53, 71]. For simplicity, it suffices to assume that P(𝐻) is faithful to Λ, which implies that Λ can be learned up to Markov equivalence. This assumption is not necessary, and any number of alternative identifiability assumptions on P(𝐻) can be plugged in place of faithfulness, for example triangle faithfulness [70], independent noise [56, 67], post-nonlinearity [81], equality of variances [29, 55], etc.

heading: 4 Learning the bipartite graph
text: In this section we outline the main ideas behind the recovery of Γ in Theorem 3.2. We begin by establishing conditions that ensure Γ is identifiable, and then proceed to consider efficient algorithms for its recovery.

heading: 4.1 Identifiability result
text: We study a slightly more general setup in which the identifiability of Γ depends on how much information we request from the MixOracle. Clearly, we want to rely on MixOracle as little as possible. As the proofs in the supplement indicate, the only information required for this step are the number of components. Neither the weights nor the components are needed. Definition 4.1. We say that Γ is 𝑡-recoverable if Γ can be uniquely recovered from 𝑋 and the sequence (MixOracle(𝑆) | |𝑆| ≤ 𝑡). Theorem 4.2. Let Γ be the bipartite graph between 𝑋 and 𝐻 .
(a) Assume that neΓ(𝐻𝑖) ̸= neΓ(𝐻𝑗) for any 𝑖 ̸= 𝑗. Then Γ and dim(𝐻𝑖) are 𝑛-recoverable.
(b) Let 𝑡 ≥ 3. Assume that for every 𝑆 ⊆ 𝐻 with |𝑆| ≥ 2 we have
dim span{𝑎𝑗 | 𝑗 ∈ 𝑆} ≥ 2
𝑡 |𝑆| + 1,
then Γ and dim(𝐻𝑖) are 𝑡-recoverable.
Note that Assumption 3.1 implies the assumption in Theorem 4.2(a). Finally, as in Section 2, we argue that in the absence of additional assumptions, this assumption is in fact necessary: Observation 4.3. If there is a pair of distinct variables 𝐻𝑖, 𝐻𝑗 ∈ 𝐻 such that neΓ(𝐻1) = neΓ(𝐻2), then Γ is not 𝑛-recoverable.

heading: 4.2 Ideas behind the recovery
text: In Corollary 4.4 below, we recast Observation 2.7 as an additive identity. This transforms the problem of learning Γ into an instance of more general problem that is discussed in the appendix. The results of this section apply to this more general version. Corollary 4.4. Assume that Assumptions 2.4 hold. For 𝐻𝑖 ∈ 𝐻 define 𝑤(𝐻𝑖) = log(dim(𝐻𝑖)). Then for every set 𝑆 ⊆ 𝑋
log(𝑘(𝑆)) = ∑︁
𝐻𝑖∈pa(𝑆)
𝑤(𝐻𝑖). (3)
In order to argue about the causal structure of the hidden variables we first need to identify the variables themselves. By Assumption 2.2, every hidden variable leaves a “signature” among the observed variables, which is the set neΓ(𝐻𝑖) of observed variables it affects. In particular, note that 𝐻𝑖 ∈ ⋂︀ 𝑋𝑠∈neΓ(𝐻𝑖) pa(𝑋𝑠), and if there is no 𝐻𝑗 with neΓ(𝐻𝑖) ⊂ neΓ(𝐻𝑗), then 𝐻𝑖 is the unique element of the intersection. The lemma above allows us to extract information about the union of parent sets, and we wish to turn it into the information about intersections. This motivates the following definitions. Definition 4.5. Let Γ and 𝑤 be as above. Define
sneΓ(𝑆) = ⋂︁ 𝑥∈𝑆 neΓ(𝑥) and WsneΓ(𝑆) = ∑︁
𝑣∈sneΓ(𝑆)
𝑤(𝑣) (4)
Lemma 4.6. For a set 𝑆 ⊆ 𝑋 we have WsneΓ(𝑆) = ∑︁
𝑈⊆𝑆,𝑈 ̸=∅
(−1)|𝑈 |+1𝑊Γ(𝑈), where 𝑊Γ(𝑆) = ∑︁
𝑣∈neΓ(𝑆)
𝑤(𝑣). (5)
The proof of this lemma is a simple application of the Inclusion-Exclusion principle. Remark 4.7. The RHS of Eq. (5) only depends on 𝑊 evaluated on subsets of 𝑆. Thus, in particular, if |𝑆| ≤ 𝑡 to compute Wsne(𝑆) it is enough to know MixOracle on all sets of size ≤ 𝑡.
Finally, the values of the function WsneΓ can be organized into a tensor, and from here the problem of learning Γ can be cast as decomposition problem for this tensor. These proof details are spelled out in the supplement; in the next section we illustrate this procedure for the special case of 3-recovery.
4.3 Efficient 3-recovery
Under a simple additional assumption Γ can be recovered efficiently. We are primarily interested in the case 𝑡 = 3. The main idea is to note that a rank-three tensor involving the columns of 𝐴 can be written in terms of WsneΓ. We can then apply Jennrich’s algorithm [34] to decompose the tensor and recover these columns, which yield Γ. To see this, let 𝐼 = (𝑖1, 𝑖2, 𝑖3) ⊆ 𝑋 be a triple of indices, and note that ∑︁
𝑗∈𝐻 𝑤(𝑗)(𝑎𝑗)𝑖1(𝑎𝑗)𝑖2(𝑎𝑗)𝑖3 = (︁ ∑︁ 𝑗∈𝐻 𝑤(𝑗)𝑎𝑗 ⊗ 𝑎𝑗 ⊗ 𝑎𝑗 )︁ (𝑖1,𝑖2,𝑖3) = WsneΓ(𝐼). (6)
Theorem 4.8. Assume that the columns of 𝐴 are linearly independent. Then Γ and dim(𝐻𝑖), for all 𝑖, are 3-recoverable in 𝑂(𝑛3) space and 𝑂(𝑛4) time.
Proof. It takes 𝑂(𝑛3) space and 𝑂(𝑛3) time to compute 𝑀3 and then Jennrich’s algorithm can decompose the tensor in 𝑂(𝑛3) space and 𝑂(𝑛4) time.

heading: 5 Learning the latent distribution
text: In this section we outline the main ideas behind the recovery of P(𝐻) in Theorem 3.2. Remark 5.1. Since the variables 𝐻 are not observed, MixOracle(𝑆) only tells us the set
{(𝑖, 𝜋(𝑆, 𝑖), 𝐶(𝑆, 𝑖)) | 𝑖 ∈ [𝑘(𝑆)]}. But the correspondence Ω ∋ ℎ ↔ 𝑗 ∈ [𝐾] between a possible tuple ℎ of values of hidden variables and the corresponding mixture component is unknown.
Since the values of 𝐻 are not observed, we may learn this correspondence only up to a relabeling of Ω𝑖. By definition, the input distribution has 𝐾 = |Ω| mixture components over 𝑋 and 𝑘𝑖 = 𝑘(𝑋𝑖) mixture components over 𝑋𝑖. Fix any enumeration of these components by [𝐾] and [𝑘𝑖], respectively. To recover the correspondence Ω ∋ ℎ ↔ 𝑗 ∈ [𝐾], we will need access to the map
𝐿 : [𝐾] → [𝑘1] × · · · × [𝑘𝑛], (7) defined so that [𝐿(𝑗)]𝑖 equals to the index of the mixture component 𝐶(𝑋, 𝑗) (marginalized over 𝑋𝑖) in the marginal distribution over 𝑋𝑖. Crucially, this discussion establishes that 𝐿 can be computed from a combination of MixOracle(𝑋) and MixOracle(𝑋𝑖) for each 𝑖.
The map 𝐿 encodes partial information about the causal structure in 𝐺. Indeed, if ℎ1, ℎ2 ∈ Ω are a pair of states of hidden variables 𝐻 that coincide on pa(𝑋𝑖) for some 𝑋𝑖 ∈ 𝑋 , then by the Markov property the components that correspond to ℎ1 and ℎ2 should have the same marginal distribution over 𝑋𝑖. Example 5.2. Consider the DAG on Figure 2. We do not make any assumptions about the causal structure between hidden variables. This DAG has 3 hidden variables, and we assume that each of them takes values in the set {0, 1}. Then by Assumption 2.4, every observed variable is a mixture of 4 components, while the distribution on 𝑋 is a mixture of 8 components. Note that the anchor word assumption is violated here, while (SSC) assumption is satisfied. The map 𝐿 : [8] → [4] × [4] × [4] for an example as in Fig. 2 has form
𝑖 : 1 2 3 4 5 6 7 8 𝐿(𝑖) : (2, 4, 3), (4, 3, 4), (4, 4, 2), (3, 2, 4), (2, 3, 1), (1, 1, 3), (3, 1, 2), (1, 2, 1)
Our goal is to find the correspondence between ℎ ∈ Ω = {0, 1}3 and 𝑖 ∈ [8]. (The projection on the third variable is not shown on Figure 2, so the third coordinate of 𝐿 cannot be deduced from the plot.)
We now show that there is an algorithm that exactly recovers P(𝐻) from the bipartite graph Γ, the map 𝐿 : [𝐾] → [𝑘1] × · · · × [𝑘𝑛], and the mixture weights (probabilities) {𝜋(𝑋, 𝑖) | 𝑖 ∈ [𝐾]} = {P(𝑍 = 𝑖) | 𝑖 ∈ [𝐾]}. Each of these inputs can be computed from MixOracle. Definition 5.3. Let 𝐽 be an order-𝑚 tensor whose 𝑖-th mode is indexed by values of 𝐻𝑖, such that 𝐽(ℎ1, ℎ2, . . . , ℎ𝑚) = P(𝐻 = ℎ). That is, 𝐽 is the joint probability table of 𝐻 . Theorem 5.4. Suppose Assumptions 2.4 and 3.1 hold. Then the correspondence Ω ∋ ℎ ↔ 𝐶(𝑋, 𝑖) and the tensor 𝐽(ℎ1, ℎ2, . . . , ℎ𝑚) = P(𝐻 = (ℎ1, ℎ2, . . . , ℎ𝑚)) can be efficiently reconstructed from 𝐿, Γ and {𝜋(𝑋, 𝑖)}𝑖∈[𝐾]. Observation 5.5. If Assumption 3.1 is violated, then 𝐽 cannot be reconstructed uniquely. Moreover, in this case 𝐺 cannot be uniquely identified.

heading: 6 Implementation details
text: The results in Section 3 assume access to the mixture oracle MixOracle(𝑆). Of course, in practice, learning mixture models is a nontrivial problem. Fortunately, many algorithms exist for approximating this oracle: In our implementation, we used 𝐾-means. A naïve application of clustering algorithms, however, ignores the significant structure between different subsets of observed variables. Thus, we also enforce internal consistency amongst these computations, which makes estimation much more robust in practice. In the remainder of this section, we describe the details of these computations.
Estimating the number of marginal components In order to estimate the number of components in a marginal distribution for a subset 𝑆 of observed variables with |𝑆| ≤ 3, we use 𝐾-means combined with agglomerative clustering to merge nearby cluster centers, and then select the number of components that has the highest silhouette score. Done independently, this step ignores the structure of the global mixture, and is not robust. In order to make learning more robust we observe that the assumptions on the distribution imply the following properties:
• Divisibility condition: The number of components we expect to observe over a set 𝑆 of observed variables is divisible by a number of components we observe on the subset 𝑆′ ⊂ 𝑆 of observed variables (see Obs. 2.7).
• Structure of means: Observe that the projections of the means of mixture clusters in the marginal distribution over 𝑆 are the same as the means of mixture components over variables 𝑆′ for every 𝑆′ ⊆ 𝑆. Hence, if we learn the mixture models over 𝑆 and 𝑆′ with the correct numbers of components 𝑘(𝑆) and 𝑘(𝑆′), we expect the projections to be close.
Example 6.1. Suppose we are confident that the number of components in the mixture over 𝑋1 is in the set {6, 7, 8}, over 𝑋2 is in {4, 5, 6} and the number of components in the mixture over {𝑋1, 𝑋2} is in the set {20, 21, 22, 23, 24, 25, 26}. Using divisibility condition between 𝑋1 and {𝑋1, 𝑋2} we may shrink the set of candidates to {21, 24}. Next using the divisibility condition for 𝑋2 and {𝑋1, 𝑋2} we may determine that the number of components should be 24.
With these observations in mind, we use a weighted voting procedure, where every set 𝑆 votes for the number of components in every superset and every subset based on divisibility or means alignment. We then predict the true number of components by picking the candidate with the most votes.
Constructing 𝐿 In order to estimate 𝐿 from samples we learn the mixture over the entire set of variables (using K-means and the number of components predicted on the previous step) and over each variable separately (again, using previous step). After this we project the mean of each component to a space over which 𝑋𝑖 is defined and pick the closest mean in 𝐿2 distance (see Figure 2).
Reconstructing the latent graphical model Once we obtain the joint probability table of 𝐻 , the final piece is to learn the latent DAG Λ on 𝐻 . This is a standard problem of learning the causal structure among 𝑚 discrete variables given samples from their joint distribution. For this a multitude of approaches have been proposed in the literature, for instance the PC algorithm [69] or the GES algorithm [17]. In our experiments, we use the Fast Greedy Equivalence Search [57] with the discrete BIC score, without assuming faithfulness. The final graph 𝐺 is therefore obtained from Γ and Λ.

heading: 7 Experiments
text: We implemented these algorithms in an end-to-end pipeline that inputs observed data and outputs an estimate of the causal graph 𝐺 and an estimate for the joint probability table P(𝐻). To test this pipeline, we ran experiments on synthetic data. Full details about these experiments, including a detailed description of the entire pipeline, can be found in Appendix G in the supplement.
Data generation We start with a causal DAG 𝐺 generated from the Erdös-Rényi model, for different settings of 𝑚,𝑛 and |Ω𝑖|. We then generate samples from the probability distribution that corresponds to 𝐺. We take each mixture component to be a Gaussian distribution with random mean and covariance (we do not force mixture components to be well-separated, aside from constraining the covariances to be small). Additionally, we do not impose restrictions on the weights of the components, which may be very small. As a result, it is common to have highly unbalanced clusters
Box plots of Structural Hamming Distance (SHD) and Unoriented Correct Edges (UCE)
(e.g. we may have less than 30 points in one component and over 1000 in another). Figure 3 reports the results of 600 simulations; 300 each for 𝑁 = 10000 samples and 𝑁 = 15000 samples.
Results To compare how well our model recovers the underlying DAG, we compute the Structural Hamming Distance (SHD) between our estimated DAG and the true DAG. Since GES returns a CPDAG instead of a DAG, we also report the number of correct but unoriented edges in the estimated DAG. The average SHD across different problems sizes ranged from zero to 1.33. The highest SHD for any single run was 6. For context, the simulated DAGs had between 3 and 25 edges. Note that any errors are entirely due to estimation error in the 𝐾-means implementation of MixOracle, which we expect can be improved significantly. In the supplement we also report on experiments with much smaller sample size 𝑁 = 1000 (Fig. 7). These results indicate that the proposed pipeline is surprisingly effective at recovering the causal graph.

heading: 8 Discussion
text: In this paper, we established general conditions under which the latent causal model 𝐺 is identifiable (Theorem 3.2). We show that these conditions are essentially necessary, and mostly amount to nondegeneracy conditions on the joint distribution. Under a linear independence condition on columns of the bipartite adjacency matrix of Γ, we propose a polynomial time algorithm for recovering Γ and P(𝐻). Our algorithms work by reduction to the mixture oracle, which exists whenever the mixture model over 𝑋 , naturally induced by discrete latent variables, is identifiable. Experimental results show effectiveness of our approach. Even though identifiability of mixture models is a long-studied problem, a good mixture oracle implementation is a bottleneck for scalability of our approach. We believe that it may be improved significantly, and consider this as a promising future direction. In this paper, we work under the measurement model that does not allow direct causal relationships between observed variables. We believe that this condition may be relaxed and are eager to explore this direction in future work.

heading: 9 Acknowledgements
text: G.R. thanks Aravindan Vijayaraghavan for pointers to useful references. B.K. was partially supported by advisor László Babai’s NSF grant CCF 1718902. G.R. was partially supported by NSF grant CCF-1816372. P.R. was supported by NSF IIS-1955532. B.A. was supported by NSF IIS-1956330, NIH R01GM140467, and the Robert H. Topel Faculty Research Fund at the University of Chicago Booth School of Business.

Review summaries:
This is a paper that focuses on causal discovery especially focusing on the causal relation among discrete latent variables.  The basic idea is that by mixture oracles, one can locate the latent variables and recovery their distribution. The main contribution is the model identification theory, including bipartite graph, latent distribution $P(H)$.

This paper considers learning discrete latent variables (the causes) and their dependencies, given observed variables. It is assumed that there is a DAG between the hidden nodes and a bipartite graph with edges from the hidden nodes to the obseved nodes, and no edges between the observed nodes. The idea is that a distribution of each subset of observed variables is described by a mixture model where each component corresponds to an assignment of values to  hidden variables which are the causes of these observed variables. The paper then presents proofs that from such mixture models (leaned in practice by k-means in the article), the distribution and the graphs related to the hidden nodes can be recovered.

The authors identify a set of assumptions under which it is possible to recover the joint distribution over the latent variables. My understanding is that they extend NMF to use tensor factorization and under suitable assumptions show that the tensor factorization solution is the unique solution - up to relabeling. I however have several issues parsing some of the results. I would appreciate feedback from the authors to help clarify the points below.  

This paper proposes a method for recovering a distribution over a set of discrete latent random variables, given observations from a set of observed children of these variables. The method additionally recovers the set of edges between latent and observed variables. The method is written in terms of a “mixture oracle”, i.e., a subroutine which returns mixture weights and components for the distribution over any subset of observed variables. Empirical results show that the method is effective at recovering the underlying causal graph.