Learning latent causal graphs via mixture oracles

Introduction

Understanding causal relationships between objects and/or concepts is a core component of human reasoning, and by extension, a core component of artificial intelligence . 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 . This problem should be contrasted with the equally important problem of causal inference in the presence of latent confounders [16, 69, 5, 34, 71, e.g.]; see also Remark 2.1.

Causal graphical models provide a natural framework for this problem, and have long been used to model causal systems with hidden variables . 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 [54, 65, e.g.,]. 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 , independence , rank , sparsity , and graphical constraints .

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.

Our starting point is a simple reduction of the graphical model recovery problem to three modular subproblems:

The bipartite graph $\Gamma$ between hidden and observed nodes,

A directed acyclic graph (DAG) $\Lambda$ over the latent distribution.

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:

(Section 3) We provide general conditions under which the latent causal model $G$ 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.

(Section 4) We carefully analyze the problem of reconstructing $\Gamma$ under progressively weaker assumptions: First, we derive a brute-force algorithm that identifies $\Gamma$ 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).

(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 Martin and VanLehn , Friedman et al. Elidan et al. . More recent work has focused on linear models or known structure . 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 . For example, 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 . 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 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 , 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 , phylogenetics , and hidden Markov models .

A prevailing theme in the causal inference literature has been negative results asserting that in the presence of latent variables, causal inference is impossible . 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 , causal feature learning , and interaction modeling . 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 [40, e.g.], of more interest to us are nonparametric models in which the mixture components are allowed to be flexible, such as mixtures of product distributions , grouped observations and general nonparametric mixtures . In each of these cases, a mixture oracle can be implemented without parametric assumptions. In practice, we use clustering algorithms such as $K$-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 [46, 38, 20, 15, e.g.].

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.

Notation

An important consequence of the Markov property is that it allows one to read off conditional independence relations from the graph $G$. More specifically, we have the following [see 54, 65, for details]:

For each $v\in V$, $v$ is independent of its non-descendants, given its parents.

Throughout this paper, we use standard notation such as $\pa(j)$ for parents, $\ch(j)$ for children, and $\nbhd(j)$ for neighbors. Specifically, we define

The parents of a node $v\in V$ are denoted by $\pa(v)=\{u\in V:(u,v)\in E\}$;

The children of a node $v\in V$ are denoted by $\ch(v)=\{u\in V:(v,u)\in E\}$;

The neighborhood of a node $v\in V$ is denoted by $\nbhd(v)=\pa(v)\cup\ch(v)$.

Given a subset $V^{\prime}\subset V$, $\pa(V^{\prime}):=\cup_{j\in V^{\prime}}\pa(j)$ and given a subgraph $G^{\prime}\subset G$, $\pa_{G^{\prime}}(V^{\prime}):=\pa(V^{\prime})\cap G^{\prime}$, with similar notation for children and neighbors. We let $A\in\{0,1\}^{|X|\times|H|}$ denote the adjacency matrix of $\Gamma$ and denote its columns by $a_{j}\in\{0,1\}^{|X|}$. Finally, we adopt the convention that $H$ is identified with the indices $[m]=\{1,\ldots,m\}$, and similar $X$ is identified with $[n]=\{1,\ldots,n\}$. In particular, we use $\pa(i)$ and $\pa(H_{i})$ interchangeably when the context is clear.

Background

Throughout this paper, we use standard notation such as $\pa(j)$ for parents, $\ch(j)$ for children, and $\nbhd(j)$ for neighbors. Given a subset $V^{\prime}\subset V$, $\pa(V^{\prime}):=\cup_{j\in V^{\prime}}\pa(j)$ and given a subgraph $G^{\prime}\subset G$, $\pa_{G^{\prime}}(V^{\prime}):=\pa(V^{\prime})\cap G^{\prime}$, with similar notation for children and neighbors. We let $A\in\{0,1\}^{|X|\times|H|}$ denote the adjacency matrix of $\Gamma$ and denote its columns by $a_{j}\in\{0,1\}^{|X|}$.

It is well-known that without additional assumptions, the latent variables $H$ cannot be identified from $X$, let alone the DAG $\Lambda$. For example, we can always replace a pair of distinct hidden variables $H_{i}$ and $H_{j}$ with a single hidden variable $H_{0}$ that takes values in $\Omega_{i}\times\Omega_{j}$. 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:

For any hidden variables $H_{i}\neq H_{j}$ we have $\nbhd_{\Gamma}(H_{i})\neq\nbhd_{\Gamma}(H_{j})$.

There is no DAG $G^{\prime}=((X,H^{\prime}),E^{\prime})$ such that:

$G^{\prime}$ is obtained from $G$ by splitting a hidden variable (equivalently, $G$ is obtained from $G^{\prime}$ by merging a pair of vertices);

The distribution over $V=(X,H)$ satisfies:

$\prob(H=h)>0$ for all $h\in\Omega_{1}\times\ldots\times\Omega_{k}$.

For all $S\subset X$ and $a\neq b$, $\prob(S|\pa(S)=a)\neq\prob(S|\pa(S)=b)$, where $a$ and $b$ are distinct configurations of $\pa(S)$.

Without this nondegeneracy condition, $H$ cannot be identified; see Appendix A for details.

2 Mixture oracles

When $S=X$, this can be interpreted as a mixture model with $K:=|\Omega|$ components. When $S\subsetneq X$, however, multiple components can “collapse” onto the same component, resulting in a mixture with fewer than $K$ components. Let $k(S)$ denote this number, so that we may define a discrete random variable $Z$ with $k(S)$ states such that for all $j\in[k(S)]$, we have

Then $\pi(S,j)$ is the weight of the $j$th mixture component over $S$, and $C(S,j)$ is the corresponding $j$th component. It turns out that these probabilities precisely encode the conditional independence structure of $H$. To make this formal, we define the following oracle:

A mixture oracle is an oracle that takes $S\subset X$ as input and returns the number of components $k(S)$ as well as the weights $\pi(S,j)$ and components $C(S,j)$ for each $j\in[k(S)]$. This oracle will be denoted by $\mathsf{MixOracle}(S)$.

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.

In fact, we do not need the full power of $\mathsf{MixOracle}$. For our algorithms it is sufficient to have access to $k(S)$ for a sufficiently large family of $S\subset X$, the list of weights $\pi(X,j)$, and a map that relates components in the full mixture over $X$ to the components in the marginal mixtures over each variable $X_{i}$ (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:

Under Assumption 2.4, for any $S\subseteq X$

By the Markov property, $S$ is independent of $H\setminus\pa(S)$. There are $\dim(\pa(S))$ possible assignments to the hidden variables in $\pa(S)$ and by Assumption 2.4, distinct assignments to the hidden variables induce distinct components in the marginal distribution $P(S)$. Hence, by definition, $k(S)=\dim(\pa(S))$. ∎

Recovery of the latent causal graph

We first consider the oracle setting in which we have access to $\mathsf{MixOracle}(S)$.

Thus, the problem of learning $G$ is reduced to the mixture oracle:

We say that the bipartite graph $\Gamma$ satisfies the subset condition (SSC) if for any pair of distinct hidden variables $H_{i},H_{j}$ the set $\nbhd_{\Gamma}(H_{i})$ is not a subset of $\nbhd_{\Gamma}(H_{j})$.

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 .

Under Assumption 3.1, we have the following key result:

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 Appendices B-D.

A mixture oracle exists if the mixture model over $X$ is identifiable. As discussed in Section 1, such identifiability results are readily available in the literature. For example, assume that for every $S\subseteq X$, the mixture model (2) comes from any of the following families:

a well-separated (i.e. in TV distance) nonparametric mixture .

Identifiability of Λ\Lambda

Learning the bipartite graph

In this section we outline the main ideas behind the recovery of $\Gamma$ in Theorem 3.2. We begin by establishing conditions that ensure $\Gamma$ is identifiable, and then proceed to consider efficient algorithms for its recovery.

We study a slightly more general setup in which the identifiability of $\Gamma$ depends on how much information we request from the $\mathsf{MixOracle}$. Clearly, we want to rely on $\mathsf{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.

We say that $\Gamma$ is $t$-recoverable if $\Gamma$ can be uniquely recovered from $X$ and the sequence $(\mathsf{MixOracle}(S)\mid|S|\leq t)$.

Let $\Gamma$ be the bipartite graph between $X$ and $H$.

Assume that $\nbhd_{\Gamma}(H_{i})\neq\nbhd_{\Gamma}(H_{j})$ for any $i\neq j$. Then $\Gamma$ and $\dim(H_{i})$ are $n$-recoverable.

Let $t\geq 3$. Assume that for every $S\subseteq H$ with $|S|\geq 2$ we have

then $\Gamma$ and $\dim(H_{i})$ are $t$-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:

If there is a pair of distinct variables $H_{i},H_{j}\in H$ such that $\nbhd_{\Gamma}(H_{1})=\nbhd_{\Gamma}(H_{2})$, then $\Gamma$ is not $n$-recoverable.

2 Ideas behind the recovery

In Corollary 4.4 below, we recast Observation 2.7 as an additive identity. This transforms the problem of learning $\Gamma$ into an instance of more general problem that is discussed in the appendix. The results of this section apply to this more general version.

Assume that Assumptions 2.4 hold. For $H_{i}\in H$ define $w(H_{i})=\log(\dim(H_{i}))$. Then for every set $S\subseteq X$

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 $\nbhd_{\Gamma}(H_{i})$ of observed variables it affects. In particular, note that $H_{i}\in\bigcap_{X_{s}\in\nbhd_{\Gamma}(H_{i})}\pa(X_{s})$, and if there is no $H_{j}$ with $\nbhd_{\Gamma}(H_{i})\subset\nbhd_{\Gamma}(H_{j})$, then $H_{i}$ 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.

The proof of this lemma is a simple application of the Inclusion-Exclusion principle.

The RHS of Eq. (6) only depends on $W$ evaluated on subsets of $S$. Thus, in particular, if $|S|\leq t$ to compute $\comW(S)$ it is enough to know $\mathsf{MixOracle}$ on all sets of size $\leq t$.

Finally, the values of the function $\comW_{\Gamma}$ can be organized into a tensor, and from here the problem of learning $\Gamma$ can be cast as decomposition problem for this tensor. These proof details are spelled out in Appendix B; in the next section we illustrate this procedure for the special case of 3-recovery.

3 Efficient 33-recovery

Under a simple additional assumption $\Gamma$ can be recovered efficiently. We are primarily interested in the case $t=3$. The main idea is to note that a rank-three tensor involving the columns of $A$ can be written in terms of $\comW_{\Gamma}$. We can then apply Jennrich’s algorithm to decompose the tensor and recover these columns, which yield $\Gamma$. To see this, let $I=(i_{1},i_{2},i_{3})\subseteq X$ be a triple of indices, and note that

Assume that the columns of $A$ are linearly independent. Then $\Gamma$ and $\dim(H_{i})$, for all $i$, are $3$-recoverable in $O(n^{3})$ space and $O(n^{4})$ time.

It takes $O(n^{3})$ space and $O(n^{3})$ time to compute $M_{3}$ and then Jennrich’s algorithm can decompose the tensor in $O(n^{3})$ space and $O(n^{4})$ time. ∎

Learning the latent distribution

Since the variables $H$ are not observed, $\mathsf{MixOracle}(S)$ only tells us the set

But the correspondence $\Omega\ni h\leftrightarrow j\in[K]$ between a possible tuple $h$ of values of hidden variables and the corresponding mixture component is unknown.

Since the values of $H$ are not observed, we may learn this correspondence only up to a relabeling of $\Omega_{i}$. By definition, the input distribution has $K=|\Omega|$ mixture components over $X$ and $k_{i}=k(X_{i})$ mixture components over $X_{i}$. Fix any enumeration of these components by $[K]$ and $[k_{i}]$, respectively. To recover the correspondence $\Omega\ni h\leftrightarrow j\in[K]$, we will need access to the map

defined so that $[L(j)]_{i}$ equals to the index of the mixture component $C(X,j)$ (marginalized over $X_{i}$) in the marginal distribution over $X_{i}$. Crucially, this discussion establishes that $L$ can be computed from a combination of $\mathsf{MixOracle}(X)$ and $\mathsf{MixOracle}(X_{i})$ for each $i$.

The map $L$ encodes partial information about the causal structure in $G$. Indeed, if $h_{1},h_{2}\in\Omega$ are a pair of states of hidden variables $H$ that coincide on $\pa(X_{i})$ for some $X_{i}\in X$, then by the Markov property the components that correspond to $h_{1}$ and $h_{2}$ should have the same marginal distribution over $X_{i}$.

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 $X$ is a mixture of $8$ components. Note that the anchor word assumption is violated here, while (SSC) assumption is satisfied. The map $L:\rightarrow\times\times$ for an example as in Fig. 2 has form

Our goal is to find the correspondence between $h\in\Omega=\{0,1\}^{3}$ and $i\in$. (The projection on the third variable is not shown on Figure 2, so the third coordinate of $L$ cannot be deduced from the plot.)

We now show that there is an algorithm that exactly recovers $\prob(H)$ from the bipartite graph $\Gamma$, the map $L:[K]\to[k_{1}]\times\cdots\times[k_{n}]$, and the mixture weights (probabilities) $\{\pi(X,i)\mid i\in[K]\}=\{\prob(Z=i)\mid i\in[K]\}$. Each of these inputs can be computed from $\mathsf{MixOracle}$.

Let $J$ be an order-$m$ tensor whose $i$-th mode is indexed by values of $H_{i}$, such that $J(h_{1},h_{2},\ldots,h_{m})=\prob(H=h)$. That is, $J$ is the joint probability table of $H$.

Suppose Assumptions 2.4 and 3.1 hold. Then the correspondence $\Omega\ni h\leftrightarrow C(X,i)$ and the tensor $J(h_{1},h_{2},\ldots,h_{m})=\prob(H=(h_{1},h_{2},\ldots,h_{m}))$ can be efficiently reconstructed from $L$, $\Gamma$ and $\{\pi(X,i)\}_{i\in[K]}$.

If Assumption 3.1 is violated, then in general $J$ cannot be reconstructed uniquely and moreover, $G$ cannot be uniquely identified. See Appendix C for details.

Note that $h^{*}$ and $e_{i}$ differ in exactly one coordinate. We then repeat this process until all states have been exhausted. The following example illustrates the procedure and explains how Lemma C.1 helps to resolve the ambiguity regarding the assignment of components to hidden states in each step.

Consider the DAG $G$ in Fig. 2. It has $3$ hidden variables, each of which takes values in $\{0,1\}$. By Assumption 2.4 every observed variable is a mixture of $4$ components, while the distribution on $X$ is a mixture of $8$ components. Note that the anchor word assumption is violated here, while SSC (Assumption 3.1) is satisfied. The map $L:\rightarrow\times\times$ can be written as:

We want to find the correspondence between $h\in\Omega=\{0,1\}^{3}$ and $i\in$.

We start by picking an arbitrary component, say 1, and assign it to $(H_{1},H_{2},H_{3})=(0,0,0)$. Next, we make use of Lemma C.1. Since we know $\Gamma$, we know $\ch(H_{i})$ for each $i$. In particular, for the hidden variable $H_{1}$, we know $\ch(H_{1})=\{X_{1},X_{2}\}$. This implies that if $H_{2},H_{3}$ are fixed while $H_{1}$ changes its value, then the component of $X_{3}$ is unchanged. It follows that the third coordinate of $L$ is also unchanged. This gives us a way to pair up the components that have the same third coordinate $L(i)_{3}$; the pairs are $(1,6)$, $(2,4)$, $(3,7)$ and $(5,8)$. By our previous observation, these pairs are in one-to-one correspondence with unique states of $(H_{1},H_{2})=(h_{1},h_{2})$, and each pair identifies the pair of components $(P(X\,|\,H_{1}=0,H_{2}=h_{2},H_{3}=h_{3}),P(X\,|\,H_{1}=1,H_{2}=h_{2},H_{3}=h_{3}))$. Note that at this stage, there is still ambiguity as to which coordinate of each pair corresponds to which component.

Similarly, we can pair up the components that correspond to assignments of hidden variables that differ only in the value of $H_{2}$. The pairs are $(1,3)$, $(2,5)$, $(4,8)$ and $(6,7)$. Finally, for $H_{3}$ the pairs are $(1,5)$, $(2,3)$, $(4,7)$ and $(6,8)$.

Since component 1 is assigned to $(H_{1},H_{2},H_{3})=(0,0,0)$ we can deduce that

Assume that we know which components correspond to the hidden variable state $(H_{1},H_{2},H_{3})=(h_{1},h_{2}^{\prime},h_{3})$ and $(H_{1},H_{2},H_{3})=(h_{1}^{\prime},h_{2},h_{3})$, with $h_{1}\neq h_{1}^{\prime}$ and $h_{2}\neq h_{2}^{\prime}$. Then we can use the information above to deduce which components correspond to the hidden state $(h_{1}^{\prime},h_{2}^{\prime},h_{3})$ since it differs from them in just 1 position. Hence, we can deduce

Note that since $(1,1,1)$ differs from the four states identified in the first step in two entries, this has not been determined yet. However, repeating this argument a third time we can deduce that component 4 corresponds to $(H_{1},H_{2},H_{3})=(1,1,1)$.

To illustrate how this algorithm works in the case of non-binary latent variables we provide one more example.

Suppose that the map $L:\rightarrow\times\times\times$ is given by:

We want to find the correspondence between $h\in\Omega=\{0,1,2\}^{2}$ and $i\in$.

As in the previous example, in order to see which components correspond to the states of latent variables where $H_{2}$ is fixed and $H_{1}$ takes all values in $\{0,1,2\}$ we group together the components that have the same value of $L$ on $X\setminus\ch(H_{1})=\{X_{4}\}$. We get the following groups $(1,7,8)$, $(2,4,6)$ and $(3,5,9)$.

Similarly, by comparing the values of $L$ on $X\setminus\ch(H_{2})=\{X_{2},X_{3}\}$ we get that the following groups correspond to a fixed value of $H_{1}$, while $H_{2}$ vary: $(1,4,5)$, $(2,8,9)$ and $(3,6,7)$.

Since values of $H_{i}$ are determined up to relabeling we can arbitrarily assign a component, say 1, to $(H_{1}=0,H_{2}=0)$. Now, using Lemma C.1, we know that components that correspond to $(H_{1}=1,H_{2}=0)$ and $(H_{1}=2,H_{2}=0)$ are $7$ and $8$, and again because values of $H_{i}$ can be relabeled, at this point the choice is arbitrary. Using the similar argument for $H_{2}$, we can deduce the following correspondence:

At this point the labeling of the values of hidden variables is fixed. Now let us consider an index of hamming weight 2, say $(1,1)$. We know that the component, that corresponds to this state of latent variables, differs from the component $4$, that corresponds to $(0,1)$, only due to the change of $H_{1}$. Hence, the component that corresponds to $(1,1)$ is in the set $\{2,4,6\}$. At the same time, we know that it differs from the component $7$ that corresponds to $(1,0)$ only due to the change of $H_{2}$. Hence, the desired component is in the set $\{3,6,7\}$. By taking the intersection of sets $\{2,4,6\}$ and $\{3,6,7\}$ we deduce that the value that corresponds to $(1,1)$ is 6. Similarly we can determine the rest of the values.

Implementation details

The results in Section 3 assume access to the mixture oracle $\mathsf{MixOracle}(S)$. Of course, in practice, learning mixture models is a nontrivial problem. Fortunately, many algorithms exist for approximating this oracle: In our implementation, we used $K$-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; a complete outline of the entire pipeline can be found in Appendix E.

In order to estimate the number of components in a marginal distribution for a subset $S$ of observed variables with $|S|\leq 3$, we use $K$-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 $S$ of observed variables is divisible by a number of components we observe on the subset $S^{\prime}\subset S$ 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 $S$ are the same as the means of mixture components over variables $S^{\prime}$ for every $S^{\prime}\subseteq S$. Hence, if we learn the mixture models over $S$ and $S^{\prime}$ with the correct numbers of components $k(S)$ and $k(S^{\prime})$, we expect the projections to be close.

Suppose we are confident that the number of components in the mixture over $X_{1}$ is in the set $\{6,7,8\}$, over $X_{2}$ is in $\{4,5,6\}$ and the number of components in the mixture over $\{X_{1},X_{2}\}$ is in the set $\{20,21,22,23,24,25,26\}$. Using divisibility condition between $X_{1}$ and $\{X_{1},X_{2}\}$ we may shrink the set of candidates to $\{21,24\}$. Next using the divisibility condition for $X_{2}$ and $\{X_{1},X_{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 $S$ 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 LL

In order to estimate $L$ 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 $X_{i}$ is defined and pick the closest mean in $L_{2}$ distance (see Figure 2).

Reconstructing the latent graphical model

Once we obtain the joint probability table of $H$, the final piece is to learn the latent DAG $\Lambda$ on $H$. This is a standard problem of learning the causal structure among $m$ 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 or the GES algorithm . In our experiments, we use the Fast Greedy Equivalence Search with the discrete BIC score, without assuming faithfulness. The final graph $G$ is therefore obtained from $\Gamma$ and $\Lambda$.

Experiments

We implemented these algorithms in an end-to-end pipeline that inputs observed data and outputs an estimate of the causal graph $G$ and an estimate for the joint probability table $\prob(H)$. 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 F.

We start with a causal DAG $G$ generated from the Erdös-Rényi model, for different settings of $m,n$ and $|\Omega_{i}|$. We then generate samples from the probability distribution that corresponds to $G$. 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 (e.g. we may have less than $30$ points in one component and over $1000$ in another). Figure 4 reports the results of $600$ simulations; $300$ each for $N=10000$ samples and $N=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 $K$-means implementation of $\mathsf{MixOracle}$, which we expect can be improved significantly. In the supplement we also report on experiments with much smaller sample size $N=1000$ (Fig. 6). These results indicate that the proposed pipeline is surprisingly effective at recovering the causal graph.

Discussion

In this paper, we established general conditions under which the latent causal model $G$ is identifiable (Theorem 3.2). We show that these conditions are essentially necessary, and mostly amount to non-degeneracy conditions on the joint distribution. Under a linear independence condition on columns of the bipartite adjacency matrix of $\Gamma$, we propose a polynomial time algorithm for recovering $\Gamma$ and $\prob(H)$. Our algorithms work by reduction to the mixture oracle, which exists whenever the mixture model over $X$, 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.

Acknowledgements

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.

References

Appendix A Non-identifiability if Assumption 2.4 is violated

In this appendix we are going to show that Assumptions 2.2 and 2.3 on the graph $G$ are not sufficient for identifiability, and therefore additional assumptions on the distribution of $H$ over $\Omega$ are required as well.

For distributions $D_{1},D_{2}$, let $D_{1}\otimes D_{2}$ denote the product of the distributions $D_{1}$ and $D_{2}$.

That is, if $X\sim D_{1}$ and $Y\sim D_{2}$ are independent, then their joint distribution is $D_{1}\otimes D_{2}$.

The following example illustrates an important case of non-identifiability and motivates the need for Assumption 2.4.

Let $N_{0},N_{1},N_{0}^{\prime},N_{1}^{\prime}$ be independent Gaussian distributions with distinct parameters (means and variances). Consider

We claim that $(X_{1},X_{2})$ is consistent with (i.e., satisfies Markov property with respect to) each of the following three models below. Here, in the model $S_{3}$ the hidden variable $H_{1}$ can take three values $\{0,1,2\}$, and in models $A$ and $B$, hidden variables take values in $\{0,1\}$.

$H_{1}<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><msub><mi>X</mi><mn>1</mn></msub></mrow><annotation encoding="application/x-tex">X_{1}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8333em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathnormal" style="margin-right:0.0785em;">X</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3011em;"><span style="top:-2.55em;margin-left:-0.0785em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">1</span></span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span></span>H_{2}$$X_{2}$ Model $A$ $H_{1}<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><msub><mi>X</mi><mn>1</mn></msub></mrow><annotation encoding="application/x-tex">X_{1}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8333em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathnormal" style="margin-right:0.0785em;">X</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3011em;"><span style="top:-2.55em;margin-left:-0.0785em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">1</span></span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span></span>H_{2}$$X_{2}$ Model $B$ $X_{2}<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><msub><mi>X</mi><mn>1</mn></msub></mrow><annotation encoding="application/x-tex">X_{1}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8333em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathnormal" style="margin-right:0.0785em;">X</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3011em;"><span style="top:-2.55em;margin-left:-0.0785em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">1</span></span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span></span>H_{1}$ Model $S_{3}$ Note that all these models satisfy “no-twins” Assumption 2.2 and minimality Assumption 2.3, while Assumptions 2.4 are violated by models $A$ and $B$.

Consistency with $S_{3}$. Let $H_{1}$ be a random variable that takes values $0,1,2$ with probabilities $(1/2,1/4,1/4)$. Then

Consistency with $A$. Let $H_{1}$ and $H_{2}$ be i.i.d random variables that take values $0,1$ with probabilities $(1/2,1/2)$. Then

Consistency with $B$. Let $H_{1}$ be a random variable that takes values ${0,1}$ with probabilities $(1/2,1/2)$. Let $H_{2}$ be a dependent random variable that takes values $0,1$ with probabilities $(1,0)$, if $H_{1}=0$, and with probabilities $(1/2,1/2)$, if $H_{1}=1$.

Observe that among the models $A,B$ and $S_{3}$, only $S_{3}$ satisfies Assumption 2.4. Observe that the model $A$ satisfies part (a), but not (b), and the model $B$ satisfies part (b), but not (a), of Assumption 2.4. This shows that only one of these assumptions is still not sufficient for identifiability of a latent causal model.

Appendix B Reconstructing bipartite part Γ\Gamma. Proofs for Sections 4

Recall that (cf. Section 4.2), that for $w(H_{i})=\log(\dim(H_{i}))$ and every subset $S\subseteq X$ the parameters of the latent DAG satisfy